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

0 引言
随着市场经济的迅速发展，客户需求逐渐从大批量少批次向小批量个性化方向转变，客户对订单的配送时限和服务质量要求越来越高。传统人到货拣选方式逐渐向更有效率的货到人拣选方式转变。货到人拣选方式避免了传统拣选方式拣选时间长、效率低、容易出错、需要大量人力等缺点，能更好适应新市场环境对企业订单的需求[1]。货箱到人拣选系统作为一种新兴拣选方式，属于货到人拣选方式的一种。相比其他货到人拣选方式，其具有仓库改造成本低，拣选效率高，目标更精准，投入便能迅速应用等优点。货箱到人拣选方式对拣选机器人的功能要求更高，传统拣选用的自动导向车（Automated Guided Vehicle，AGV）并不能满足要求，于是更为智能和灵活的自主移动机器人（Autonomous Mobile Robot，AMR）就成为该拣选系统最合适的拣选执行者[2-4]。
货箱到人模式下 AMR 的拣选过程与人到货模式下人的拣选过程较为相似，目前人到货模式下拣选系统的优化研究主要集中在拣货策略和拣选路径优化上。拣货策略主要有订单别拣货策略和批量拣货策略[5]。随着订单数量的增长，订单别拣选的效率逐渐满足不了系统需求，学术界开始越来越重视批量拣货策略的研究[6]。批量拣货时的首要问题是订单分批，时窗分批是一种适用于密集订单的分批策略。学者们在此基础上设计了动态时窗分批，提升了拣货系统的均衡性[7-9]。针对货到人拣选模式，现有研究主要构建以设备搬运次数最小化为目标的数学模型，通过优化订单的分批方法来实现目标。何其超等建立并求解 0~1整数线性规划模型，使 AGV 小车搬运次数显著减少[10]。杨鸿雪和徐冉分别通过聚类算法和启发式算法对订单进行分批，提升了货到人拣选系统的运行效率[11-12]。
拣选路径优化的研究主要构建以拣选时间或路程最小化为目标的数学模型，并用算法求得最优解。现有研究主要采用启发式算法对问题进行求解，找到最优的拣选路径[13-16]。张娟等使用禁忌搜索算法对单区型物流配送中心拣选路径进行优化，证明其总体优化效果比只使用聚类算法对订单分批更好[17]。在货到人拣选模式下，张彩霞和宁新杰分别通过遗传算法和改进的 PRM算法优化了 AGV 的拣选路径[18-19]。闫妍等使用 A* 算法对菜鸟智能仓库的搬运机器人路径规划，解决了机器人碰撞冲突和死锁等问题[20]。通过蚁群算法等启发式算法，同样可以对堆垛机等自动化分拣系统的拣选路径进行优化，提高系统效率[21-22]。相较于人到货模式拣选系统，货箱到人模式下 AMR 拣选系统具有拣选路径更为复杂等特点，拣选过程中总作业效率受拣选路径规划影响更大，因此在对该系统的优化研究中拣选路径的优化更为重要。以上研究尚未解决货箱到人模式下 AMR 的三维拣选路径问题，同时也未能考虑到拣选货箱数受到拣选设备存储容量约束下的作业情况。
本文根据货箱到人模式下 AMR 拣选系统的具体特点，构建以总作业时间最小化为目标的 AMR 拣选作业优化模型，并设计改进的粒子群算法进行求解，通过实例对模型和算法进行验证。
1 问题描述与模型建立
1.1 问题描述
本文研究某仓库分拣系统基于货箱到人拣选模式下 AMR 的拣选路径规划问题。仓库主要由货架和 AMR 组成，AMR 拣选使用整箱拣货方案。仓库内进行分区作业，AMR 与仓库原理图如图 1 所示。O 点为分拣台位置，货架纵向排列。设货架上单元货格的深度为 l，宽度为 w，层高为 h，货架列数为 s, 巷道宽度为 f。

系统中负责拣选作业的 AMR 单一执行出库或入库工作，本文仅研究出库工作时的 AMR 拣选作业，其具体样式如图 2 所示，AMR 从拣选台出发在仓库巷道中移动，按照任务清单对货箱进行拣选。假定某一时间段内的任务清单上有 n 个拣选任务，每个任务有且只有一个对应货箱，以拣选台位置 O 为坐标原点，横向为 X 轴，纵向为 Y 轴建立坐标系，待拣货箱 i 的信息表示为xi ,yi ,z ( )i ，xi为货箱 i 横坐标所在位置，yi为货箱 i 纵坐标所在位置，zi为货箱所在层。如：( ) 6,2,3 表示该货箱存储在第 6 排货架、第 2 列的第 3 层货格。
考虑到实际问题的复杂性和不确定性，在对 AMR 拣选作业路径规划问题建立模型之前，需要对该问题进行必要的简化并设定条件参数，本文对货架和 AMR 做以下假设和参数设定：
（1） AMR 的最大存储货箱数量为 M；
（2） AMR 在进行拣选作业时由下至上将被拣货箱放入自身的存储货格中；
（3） AMR 在停止水平移动的情况下才可以升降货叉；
（4） AMR 需要经过加速、匀速和减速才能完成一次水平运动，设其运动变化的加减速度为 a, 最大速度为 v1 ；
（5）拣选作业中单个货箱的存取时间固定，设为 b；
（6）货叉升降时的速度固定，设为 v2 ；
（7）不考虑缺货和插单等意外情况。
1.2 模型建立
AMR 执行拣选作业工作由移动、升降和存取 3 个动作组成，设完成一次拣选任务需要的时间为 T。