货箱到人模式下的AMR 拣选路径规划

俞明哲，董宝力，张书亭 YU Mingzhe, DONG Baoli, ZHANG Shuting

（浙江理工大学 机械与自动控制学院，浙江 杭州 310018）

0 引 言

随着市场经济的迅速发展，客户需求逐渐从大批量少批次向小批量个性化方向转变，客户对订单的配送时限和服务质量要求越来越高。传统人到货拣选方式逐渐向更有效率的货到人拣选方式转变。货到人拣选方式避免了传统拣选方式拣选时间长、效率低、容易出错、需要大量人力等缺点，能更好适应新市场环境对企业订单的需求。货箱到人拣选系统作为一种新兴拣选方式，属于货到人拣选方式的一种。相比其他货到人拣选方式，其具有仓库改造成本低，拣选效率高，目标更精准，投入便能迅速应用等优点。货箱到人拣选方式对拣选机器人的功能要求更高，传统拣选用的自动导向车（Automated Guided Vehicle，AGV） 并不能满足要求，于是更为智能和灵活的自主移动机器人（Autonomous Mobile Robot，AMR） 就成为该拣选系统最合适的拣选执行者。

货箱到人模式下AMR 的拣选过程与人到货模式下人的拣选过程较为相似，目前人到货模式下拣选系统的优化研究主要集中在拣货策略和拣选路径优化上。拣货策略主要有订单别拣货策略和批量拣货策略。随着订单数量的增长，订单别拣选的效率逐渐满足不了系统需求，学术界开始越来越重视批量拣货策略的研究。批量拣货时的首要问题是订单分批，时窗分批是一种适用于密集订单的分批策略。学者们在此基础上设计了动态时窗分批，提升了拣货系统的均衡性。针对货到人拣选模式，现有研究主要构建以设备搬运次数最小化为目标的数学模型，通过优化订单的分批方法来实现目标。何其超等建立并求解0～1整数线性规划模型，使AGV 小车搬运次数显著减少。杨鸿雪和徐冉分别通过聚类算法和启发式算法对订单进行分批，提升了货到人拣选系统的运行效率。

拣选路径优化的研究主要构建以拣选时间或路程最小化为目标的数学模型，并用算法求得最优解。现有研究主要采用启发式算法对问题进行求解，找到最优的拣选路径。张娟等使用禁忌搜索算法对单区型物流配送中心拣选路径进行优化，证明其总体优化效果比只使用聚类算法对订单分批更好。在货到人拣选模式下，张彩霞和宁新杰分别通过遗传算法和改进的PRM算法优化了AGV 的拣选路径。闫妍等使用A*算法对菜鸟智能仓库的搬运机器人路径规划，解决了机器人碰撞冲突和死锁等问题。通过蚁群算法等启发式算法，同样可以对堆垛机等自动化分拣系统的拣选路径进行优化，提高系统效率。相较于人到货模式拣选系统，货箱到人模式下AMR 拣选系统具有拣选路径更为复杂等特点，拣选过程中总作业效率受拣选路径规划影响更大，因此在对该系统的优化研究中拣选路径的优化更为重要。以上研究尚未解决货箱到人模式下AMR 的三维拣选路径问题，同时也未能考虑到拣选货箱数受到拣选设备存储容量约束下的作业情况。

本文根据货箱到人模式下AMR 拣选系统的具体特点，构建以总作业时间最小化为目标的AMR 拣选作业优化模型，并设计改进的粒子群算法进行求解，通过实例对模型和算法进行验证。

1 问题描述与模型建立

1.1 问题描述

本文研究某仓库分拣系统基于货箱到人拣选模式下AMR 的拣选路径规划问题。仓库主要由货架和AMR 组成，AMR 拣选使用整箱拣货方案。仓库内进行分区作业，AMR 与仓库原理图如图1 所示。O 点为分拣台位置，货架纵向排列。设货架上单元货格的深度为l，宽度为w，层高为h，货架列数为s, 巷道宽度为f。

图1 AMR 与仓库原理图

系统中负责拣选作业的AMR 单一执行出库或入库工作，本文仅研究出库工作时的AMR 拣选作业，其具体样式如图2 所示，AMR 从拣选台出发在仓库巷道中移动，按照任务清单对货箱进行拣选。假定某一时间段内的任务清单上有n 个拣选任务，每个任务有且只有一个对应货箱，以拣选台位置O 为坐标原点，横向为X 轴，纵向为Y 轴建立坐标系，待拣货箱i 的信息表示为(x, y,z)，x为货箱i 横坐标所在位置，y为货箱i 纵坐标所在位置，z为货箱i所在层。如： (6,2,3 )表示该货箱存储在第6 排货架、第2 列的第3 层货格。

图2 AMR 立体图

考虑到实际问题的复杂性和不确定性，在对AMR 拣选作业路径规划问题建立模型之前，需要对该问题进行必要的简化并设定条件参数，本文对货架和AMR 做以下假设和参数设定：（1） AMR 的最大存储货箱数量为M；（2） AMR 在进行拣选作业时由下至上将被拣货箱放入自身的存储货格中；（3） AMR 在停止水平移动的情况下才可以升降货叉；（4） AMR 需要经过加速、匀速和减速才能完成一次水平运动，设其运动变化的加减速度为a, 最大速度为v；（5） 拣选作业中单个货箱的存取时间固定，设为b；（6） 货叉升降时的速度固定，设为v；（7） 不考虑缺货和插单等意外情况。

1.2 模型建立

AMR 执行拣选作业工作由移动、升降和存取3 个动作组成，设完成一次拣选任务需要的时间为T。

其中：T为AMR 水平移动所耗时间；T为AMR 垂直移动所耗时间；T为AMR 存取货箱的时间。

图3 AMR 行驶速度未达到v1 时的移动距离

图4 AMR 行驶速度达到v1 时的移动距离

设T为各阶段AMR 水平运动时间，其计算公式如式（3） 所示：其中：式（10） 至式（12） 保证货物的先后拣选关系，且每个车次货物会优先被拣选至AMR 自身的最下方空闲货格；式（13） 保证AMR 每次拣选车次的起始位置和终止位置都在分拣台O 处。

2 算法设计

粒子群算法（Particle Swarm Optimization，PSO） 是解决路径规划问题常用的算法之一。它的实现简单高效，搜索速度快。但在求解过程中，各粒子易受其自身的最佳过去位置p和整个群或近邻最佳过去位置g的影响，陷入局部最优解。基于上述缺点，本文提出一种改进的PSO 进行模型求解。

2.1 改进的粒子群优化算法

本文在标准PSO 的基础上，设置二阶震荡环节和随机惯性权重，通过前期全局搜索和后期局部搜索的方式来寻找最优解，标准的PSO 算法公式为：

2.1.3 随机权重

惯性权重ω 的取值对算法的搜索能力有着重要的影响作用，较大的ω 有利于跳出局部最小点，提高算法的全局搜索能力；而较小的ω 有利于提高当前搜索区域的搜索精度，增强算法的局部搜索能力。Eberhart 等人提出了线性递减惯性权重，更好地平衡算法的全局搜索能力和局部搜索能力。但这种方法需要反复实验确定参数最优值，且易陷入局部最优解。本文设置一种随机分布惯性权重，当在算法前期找到最优值，则易产生较小的ω 值，加快收敛速度；当在算法前期找不到最优值，则易产生较大的ω 值，扩大搜索范围。其计算公式如下：

Step4：根据式（18） 更新惯性权重ω。

Step5：对于每个粒子，将其适应值与其经历过的最好位置作比较，如果较好，则将其作为当前的最好位置p。

Step6：比较当前所有p和g的值，更新g。

Step7： 若达到最大迭代次数，则结束搜索并输出最优个体作为结果。否则返回Step2 继续搜索。

3 实例验证

本文以某配送中心AMR 库中的一个分区为例，对该AMR 库分区一定时间内的拣选订单数据进行仿真实验。已知该AMR库分区共有10 排货架，作业AMR 数量为1 台。货架有6 层，每排每层有15 个货位。货位尺寸为：深度l=0.6m，宽度w=0.6m，高度h=0.42m；巷道宽度f=1.2 米；AMR 的货位M=6，行驶速度v=2.5m/s，加速度a=1m/s，货叉垂直升降速度v=0.3m/s。

图5 改进的PSO 流程图

实验所用数据选取该配送中心系统中某时间段内的拣选作业任务单，其中含有30 个不同的待捡货物，具体信息如表1 所示。

表1 拣选任务清单

利用改进的PSO 对数据进行仿真模拟，具体参数为：设PSO 的种群规模为100，学习因子为c=c=2.0，惯性权重为w=0.5，最大迭代次数为1 000，前500 次迭代渐进收敛，后500 次迭代振荡收敛。并利用标准PSO 对数据进行仿真模拟，具体参数与改进的PSO 相同，但不设置二阶振荡环节和随机惯性权重。

图6 反映了在两种算法的求解过程中最优值随迭代次数的演化，与标准PSO 相比，改进的PSO 前500 次迭代最小化目标函数值快速下降，后500 次迭代最小化目标函数值跳出局部最优，进一步降低。最终优化结果如表2 所示。

表2 基于两种PSO 的拣选路径优化结果对比

图6 改进的PSO 迭代曲线

AMR 完成任务清单上的拣货任务共需要5 个车次，总的最优作业顺序为(23,26,4,7,1,19 )→(29,21,5,2,15,16 )→(8,24,17,28,30,11)→(22,10,6,9,14,13 )→(3,18,25,20,27,12 )，拣选作业共耗时1 378s。若按照标准PSO 算法进行求解，则得到的拣选作业优化结果为 (28,18,21,2,3,24 )→ (6,17,9,10,14,8 )→ (30,25,5,15,12,23 )→ (26,27,20,11,29,16 )→ (7,4,1,19,13,22 )，其拣选作业共耗时1 633s。比较可发现利用改进的粒子群算法能够获得更优的结果，可以有效降低货箱到人模式下AMR 拣选作业的时间。

4 结 论

本文构建了以总作业时间最小化为目标的AMR 拣选作业优化模型，并设计一种改进的PSO 用于求解最优AMR 拣选路径，实例实证表明该方法是可行的。通过算法前期渐进收敛和后期振荡收敛，提高了逼近最小化目标的速度并实现跳出局部最优值，保证了算法精度的同时提高了迭代效率。改进的PSO 优化后拣选时间比标准PSO 节约了15.6%，有效地降低了货箱到人模式下AMR 拣选作业耗时。

在货箱到人拣选模式下除了货箱的出库外，还包含回库和AMR 调度等目标或条件，在此基础上，多AMR 动态分区情况下的货箱到人拣选路径规划研究是今后工作的方向。