基于群智能算法的仓库拣选路径优化

来源：本站 | 发布日期：2023-03-04

长期以来, 订单拣选被认为是仓库作业中劳动密集度最高, 成本最高的环节, 占仓库总运营费用的55%用于这一环节[1]。订单拣选领域主要的研究有布局设计[2], 货位分配[3], 作业分区[4], 订单捆绑[5]和路线算法[6]。传统的路径规划方法有栅格法[7]、可视图法[8,9]、和自由空间法[10]等, 这些传统的方法存在计算效率低不适用于高维度优化的缺陷[11]。群智能算法[12]作为一种新型的源于大自然仿生类算法, 成功应用于一些实际问题, 如商旅问题、分配问题、加工车间调度问题和网络设计问题等, 取得一系列较好的实验结果[13,14,15]。群智能算法的特点是并行性和简单性。本文首先以群智能控制系统 (Insect Intelligent Control System, I2CS) 为架构, 通过群智能算法并行性和简单性的特点对仓库拣选路径进行优化, 提高仓库拣选环节的工作效率。

1 群智能控制系统架构

1.1 集散式控制系统

集散式控制系统 (Distributed Control System, DCS) 是20世纪70年代中期诞生的, 是数字技术、微电子技术、通信技术、屏幕显示技术与过程控制技术紧密结合的新一代控制系统新模式[16]。本文主要以建筑中的集散式控制系统为例作为比较。

特点: (1) 面向设备子系统; (2) 需要配置数据的地理位置信息, 建立控制逻辑网络; (3) 跨专业:建筑、暖通、照明、给排水、电梯、视频监控、安防、消防、IT等专业。

存在问题: (1) 跨子系统集成困难, 信息孤岛, 协议不兼容; (2) 需要大量的组网配置工作 (10万m2建筑, 几万个信息点和传感器等实物的人工校对工作) ; (3) 设备专业和IT专业的知识难以融合。

1.2 群智能控制系统

群智能控制系统I2CS是清华大学建筑节能研究中心开发的一种新型控制系统, 群智能控制系统以现场的智能末端设备和智能传感器、智能执行器为网络节点, 各节点地位平等, 通过自组织的方式与其他节点构建无中心网络拓扑, 计算模式为各节点的本地独立运算以及相邻节点间基于信息互传的协同运算, 实现同等于集中式计算的效果[17,18]。

特点: (1) 基于智能空间控制单元、控制子系统的智能终端; (2) 面向空间:网络结构与空间位置网络一致; (3) 支持标准化的分布式计算能力, 支持基于分布式任务的多任务同步处理。

解决的问题: (1) 实现机电一体化, 解决局部跨设备子系统的集成问题; (2) 网络结构与空间位置网络一致, 大幅度降低组网配置工作; (3) 降低建筑设备专业人员的IT技术门槛。

1.3 仓库管理群智能控制系统

仓库管理群智能控制系统包括分布在各个空间区域智能控制器、智能传感器、移动或固定的智能执行器。如图1所示, 智能控制器、智能传感器和智能执行器通过485总线或Wi-Fi连接, 形成无中心扁平化的网络。建立分布于设定区域范围内的多个不同类型的仓位的无中心自组织控制网络, 以总能耗最小、总运行效率最高和总费用最少为目标, 实现仓库管理控制系统的优化运行。与现有技术相比, 实现仓库管理系统的自组网、控制设备的即插即用、基于群智能算法的全局优化控制。

图1 仓库管理群智能控制系统架构

2 群智能算法

群智能算法是一种概率搜索算法, 其思路就是模仿自然界中生物群例如蚁群、鸟群和鱼群等觅食的过程, 衍生出了以下三种算法:蚁群算法 (Ant Colony Optimization, ACO) 、微粒群算法 (Particle Swarm Optimization, PSO) 和人工鱼群算法 (Arti-ficial Fish-swarm Algorithm, AFA) 。

2.1 算法结构

正如上文对群智能架构及算法特点和性能的分析比较, 本文基于群智能控制系统, 提出一种仓库拣选路径优化的群智能算法。通过利用群智能控制系统的自组织、即插即用等特点结合蚁群算法在信息素指导情况下求解的快速性和精确性, 从而实现拣选路径的全局优化。该算法的基本结构如2所示。

2.2 采用并行蚁群算法求解最优路径

蚁群算法实质是一种使用信息正反馈机制的算法, 一旦具有正确的初始信息素作为引导, 蚁群就能够快速地收敛于最优解。具体内容包括:

图2 算法结构

(1) 信息素的表示

“信息素”分布在相邻两个点的连线上, 通往路径上障碍连线的信息素为0。蚂蚁从起始点开始搜索, 蚂蚁的每一步搜索的方向是与其当前所在点相邻的上、下、左、右4个方位的点上。t时刻每一自由点i到其相邻自由点j的信息素的值为τij (t) 。

(2) 路径点的选择

t时刻蚂蚁k选择下一个点的转移概率由以下公式确定:

其中, ηij (t) 为启发函数, α为信息素的重要程度因子;β为启发函数重要程度因子;allowk (k=1, 2, …, m) 为蚂蚁k待访问点的集合。

(3) 信息素的更新机制

其中, △τkij表示第k只蚂蚁在点i与点j连接路径上释放的信息素浓度, △τij表示所有蚂蚁在点i与点j连接路径上释放的信息素浓度总和。

其中, Q为常数, 表示蚂蚁循环一次所释放的信息素总量;Lk为第k只蚂蚁经过路径的长度。

(4) 算法并行化策略

蚁群的并行化策略主要有5种:并行独立蚁群、并行交互蚁群、并行蚂蚁、结决方案元素的并行评估、蚂蚁和结决方案元素的并行结合[20]。本文采用的是并行交互蚁群的方法, 该方法不但具有并行独立蚁群简单方便的特点, 同时还弥补了各蚁群之前没有交互, 信息传递方向是单向的局限性。

2.3 算法描述

该算法的基本步骤:

1) 初始化算法运行参数, 建立抽象仓库环境模型;确定起点和目标点在抽象仓库环境模型中的位置。

2) 计算下一选择区域内各点的信息值, 依据信息值和信息素值, 确定下一路径点。

3) 移动到下一路径点, 进行局部信息素更新。

4) 判断是否所有节点完成一次路径构建, 若否, 则转到步骤2) 。

5) 判断算法是否满足停止条件, 若满足则输出最优结果, 否则, 转到步骤2) 。

3 仿真实验与分析

由于仓库拣选路径优化问题是一种特殊的TSP (Travelling Salesman Problem) 问题, 并且不同类型仓库存储区域的模型参数设置不同, 很难使用具体的例子来同其他学者的不同算法进行性能比较, 为了验证群智能算法的性能, 因此选择标准的TSP问题, 并与其他学者的遗传算法和蚁群算法进行比较。

本次实验选取的是Oliver30城市模型进行测试, 每组实验做1 0 次, 并设计遗传算法、蚁群算法作为并行化蚁群算法的对比实验。实验结果如表1所示。其中, Oliver30问题的最优解为423.74。

表1 并行化蚁群算法的性能对比试验结果

从表1的实验结果可以看出, 在求解Oliver30城市模型时, 本文提出的并行蚁群算法的寻优结果中的最小值小于遗传算法和蚁群算法的结果最小值, 10次试验的均值也是三种算法中最小的, 并且在求解Oliver30城市模型过程中, 并行蚁群算法能稳定的找到当前的已知的全局最优解;这说明并行蚁群算法的寻优能力和算法稳定性要远优于蚁群算法和遗传算法。