丁荣宽，董宝力

（浙江理工大学 机械工程学院，浙江 杭州 310018）

0 引言

自主移动机器人（Autonomous Mobile Robots，AMR）拣选［1］是“货到人”模式［2-3］下的一种方式，该方式通过系统规划AMR 行驶路线，将订单中的商品从货架拣选至固定拣货台前。拣选货物的时间是仓库提升效率的关键，因此，在AMR 执行拣选作业时，如何规划其移动路径、缩短拣选时间、提高拣选效率是亟待解决的问题［4-5］。

近年来，不少学者对仓库智能拣选进行了探究，路径规划更是成为仓库智能拣选的研究重点。如于浩洋［6］以双区型仓库为例，基于先到先服务和固定订单分批原则建立穿越策略路径进行拣选路径优化；潘鲁宁［7］建立多目标优化模型，从配送中心储位合理布局和拣选系统两个角度对拣选路径进行优化设计；胡小建等［8］针对鱼骨型仓库拣货路径规划问题，以载重和容积为约束，以多车拣货距离最短为总目标进行求解；秦德金［9］为提升多机器人协作分拣效率，构建仿真模型并提出对应路径规划算法与碰撞交通管理算法；辜勇等［10］对机器人路径栅格化，并设计一种优化转移规则和信息素更新条件的新蚁群算法进行求解；刘建胜等［11］针对Flying-V 型仓库的拣货路径优化，提出一种接收正反馈的改进蚁群算法。

此外，针对路径规划模型算法的研究也不在少数，常用于求解路径规划模型的算法包括：遗传算法、粒子群算法、人工势场法、A*算法等。张丹露等［12］针对智能仓库多机器人协同路径规划模型提出一种交通规则，并利用预约表生成基于改进A*算法的动态加权地图；胡治锋等［13］为优化多层货架人工拣选路径模型，提出一种模拟退火蚁群算法，有效提升了仓储运行效率；李艳生等［14］以路径长度、转弯次数和机器人能耗为评价指标构建节能拣选路径规划模型，设计适用于仓储机器人路径规划的人工蜂群-自适应遗传算法；李腾等［15］针对大规模多AGV 多阶段路径拣选问题，建立以任务完成时间最短为目标的路径规划模型，并通过改进A*算法解决模型中转弯避障等问题。然而，解决此类路径问题的常用智能算法只针对两点间的直线距离，并不适用于三维空间内横梁式货架［16］的路径规划问题。因此，本文针对多区型仓库［17-18］中AMR 在三维空间下的路径规划问题，考虑AMR 在拣选过程中载重以及速度变化等因素，构建以AMR 分批次拣选总时间最小化为目标的模型，并引入水平垂直叠加的折线路径［19］。算法优化方面，为避免传统粒子群算法易陷入局部最优的缺点，引入模拟退火算法（Simulated Annealing Algorithm，SAA）中 的Metropolis 准则［20-21］，设计模拟退火粒子群混合算法（Simulate Annealed Particle Swarm Mixing Algorithm，SAPSMA）对目标模型进行求解。

1 问题描述与模型建立

1.1 问题描述

在多区型仓库中，每一区型配置有一台AMR 负责该区型拣选作业。本文针对某一区型的AMR 拣选进行研究，布局如图1所示。该区型主要由横梁式货架、AMR 和I/O 起点构成，其中货架为普通、常规的多层货架，I/O 起点为AMR 的开始和结束位置。货架摆放方式：除最左最右两列货架贴墙放置外，中间货架均两列为一组，两组之间由巷道间隔，纵向平行布置。假设货架上单个货格在X方向的长度为l，Y方向的宽度为w，高度为h，巷道宽度为c，I/O 起点正对于第一条巷道。为方便观察和计算，把该区型每个货格按照网格状排列分布。

Fig.1 Three-dimensional diagram of a certain area of the warehouse图1 仓库某区型三维图

假设系统累计接收n个订单，且已知各订单中货物的存储信息。AMR 最大承载重量为M，自身货格数为Q，即AMR 单趟最多搬运Q件货物。在AMR 同时满足载货重量和货格数双约束的前提下，将订单中所有待拣货物分批次拣选完成，并将每一批次的拣选时间相加，优化目标为获得一条相加后总时间最少的拣选路径。

1.2 基本假设

建立拣选路径规划的数学模型前，对AMR 及货架作以下假设和参数设定：①订单中每一种库存量单位（Stock Keeping Uint，SKU）对应货架中的一个货格；②仓库中每一个货格规格均一致，AMR 的大小参数与货格大小相同；③每个货格中SKU 的存储数量都满足订单拣选数量；④AMR 在执行某一种动作时不能同时进行其他动作，也不会因其他因素中断当前动作，以保证拣选作业的连续性；⑤AMR 开始执行拣选任务时从I/O 起点出发，完成拣选任务或达到约束条件后均需返回I/O 点；⑥AMR 从一个拣选点移动到另一个拣选点需要经历加速、（匀速）、减速阶段，假设其空载和负载下水平方向运动的加减速度相同均为a，垂直方向升降台提升和下落速度变化相同，设为v2。

1.3 模型建立

AMR 分批次拣选货物的路径规划模型建立步骤如下。

首先对优化模型中出现的符号进行说明：

O：订单集合

S：货架集合

P：SKU 商品种类

B=｛0，1，2，……，n｝：货物拣选点集合，其中0 代表起点（拣选台）；

（xi，yi，zi，mi）为订单O上待拣SKU 的信息，例如（5，6，7，15）表示某SKU 位于仓库第5 列、第6 行、第7 层，重量为15KG。

AMR 一次完整的订单拣选时间由3 个时间段组成：①拣选点间水平移动时间，即在xoy面上移动所需时间为T1；②在z轴方向，升降台上升和下降的时间合为T2；③AMR 对SKU 取货和卸货的时间固定，合记为T3。AMR订单拣选时间表示为：

假设AMR 在水平方面的移动距离为rijs，为便于对小车路径进行规划，将小车水平方向轨迹rijs分为3 个阶段：

（1）I/O 起点到第一个货物拣选点j间的水平距离。

式中：xi，xj均表示拣选点所在的列位置。

（2）当前货物拣选点i到待拣货物拣选点j之间的水平距离。此时分为两种情况：

①货物拣选点i和j不在同一巷道时，即xi≠xj。

若i和j的行数相加小于f，则选择下巷道出。其中，f为单列货架在y轴方向上的行数。

若i和j的行数相加大于f，则选择上巷道出。

②货物拣选点i和j都在同一巷道内。

（3）AMR 单趟拣选的最后一个货架拣选点与I/O 点间的水平距离。

假设AMR 运动到待拣货物下方，升降台垂直方向移动距离为d1，公式如下：

式中：zi为货物i所在位置；zj为货物j所在位置。

AMR 在水平方向的时间T1取决于移动时的最大速度和加速度。假设AMR 水平移动时能达到的最大速度为v1，由此分为两种运动状态：①AMR 在xoy面移动过程中速度未达到最大速度v1，匀加速后做匀减速运动，即AMR 行驶的移动距离；②AMR 在xoy面移动过程中速度达到最大值v1，然后匀速运动，后再进行匀减速运动，即移动距离。

AMR 根据水平移动距离rijs以及上述是否达到最大速度的两种情况推算出第n次行驶时间。表示为：

第n次AMR 机械臂在垂直方向上升与下降的时间T2n。表示为：

假设AMR 在拣选单个货物时的取货和卸货时间相同，为s，则AMR 完成一批待拣货物所花费的取货卸货作业时间为：

根据以上描述，AMR 拣选作业时间模型可以表示为：

约束条件为：

其中：式（11）为拣选时间优化指标；式（12）表示AMR单趟拣选的货物重量不能超过M，否则需要先回起点卸货后再进行下一次拣货作业；式（13）表示AMR 的最大货格数量，即单趟最多只能容纳Q个SKU；式（14）表示订单中显示的货物都会被拣选；式（15）和（16）表示SKU 拣选的先后顺序，且保证AMR 在拣选某SKU 时的连续性；式（17）中表示AMR 在第m车次满载SKU 或重量达到上限后回到起点，表示AMR 在m+1 车次空车从起点出发拣货，即第m车次满载最终位置等于m+1车次开始位置。

2 算法设计

标准的粒子群算法（Particle Swarm Optimization，PSO）属于群智能算法，利用个体分享机制使整个群体的搜索方向从无序到有序渐变，最终产生最优解，具有操作简、收敛速度快等优点，但容易提前收敛于局部最优，影响解的精度。SAA 具有较强的全局搜索能力，前期因温度高使得算法对较差解的接受度较高，从而易于跳出局部最优，但该算法具有渐进收敛性，当搜索空间大时，SAA 需要更长的收敛时间才能得出最优解。因此，本文结合两种算法来求解AMR 分批次拣选路径规划问题，利用PSO 快速生成一定种群规模的近似解，然后得到个体最优和群体最优，最后通过SAA 的马尔科夫链和Metropolis 准则得到最优解［22］。

2.1 SAPSMA

由于PSO 收敛速度快，因而在求解过程中容易提前收敛于局部最优，影响最优解的精度。为了使PSO 能够有效跳出局部最优，增强全局搜索能力，将其与SAA 相结合，形成新的SAPSMA。

PSO 的速度和位移更新公式为：

式中：(t)表示粒子i第t次迭代后的速度；xid(t)表示粒子i第t次迭代后的位置；w为惯性权重取值；c1为个体因子；c2为社会因子；r1和r2为两个随机取值0～1 之间的数；pid和gi分别表示个体极值和群体最优值。

2.1.1 惯性权重取值

以往经典粒子群算法采用的值大多是通过实验或主观判断出来的固定值［23-25］，但是研究发现动态惯性权重取值会影响PSO 的搜索能力：当取值较大时，有助于提高算法的全局搜索能力；取值较小时，则有助于提高算法的局部搜索能力。因此，为了平衡算法的全局和局部搜索能力，设计一种非线性递减的惯性权重，选取定义域在［-3，3］之间的双曲正切函数值来控制算法搜索过程中的惯性权重取值。在初期阶段，惯性权重取值较大，然后缓慢减小，使得算法前期有充分的时间搜索全局；在中期阶段，惯性权重取值呈线性递减，在减弱全局搜索能力的同时增强局部搜索能力；到后期阶段，曲线斜率再次减小，惯性权重取值慢慢趋近于最小，局部搜索能力达到最强，进而能够进一步确定最优解。取值公式如下：

式中：wmin为惯性权重最小值，一般取0.4；wmax为惯性权重最大值，一般取0.9；通过查阅大量文献，取上述惯性权重极值能使算法性能达到最优。T 为当前迭代次数，Tmax为算法最大迭代次数。

2.1.2 引入惩罚函数

由于模型存在AMR 载重及自身货格数双约束，为了使求解过程简洁化，决定引入惩罚函数。在处理双约束问题时，将惩罚函数添加到拣选总时间最小化的目标函数中，将双约束问题转变为无约束问题来求解。其作用机理为：当满足约束条件时，求解过程将不会受到惩罚；若不满足约束条件，将会在求解过程中加入惩罚函数，使其适应度值增大，从而因不满足精度要求而被淘汰。

2.2 SAPSMA基本步骤

（1）初始化PSO，设置种群规模大小、粒子维度、速度和位置。

（2）设定初始温度t以及某一温度下马尔科夫链长度，计算每个粒子的适应度值，并将个体最优存储在pi中，种群最优存储在pg中。

（3）自适应改变w惯性权重取值。

（4）根据式（18）、（19）对粒子速度及位置进行更新，并计算新适应度值。

（5）计算新旧位置的适应度值之差△f=fitness(x') -fitness(x)，利用SAA 中的Metropolis 准则，按式（22）、（23）更新新解：

式中：fitness（x’）为新适应度值，fitness（x）为旧适应度值，T为模拟退火初始温度。

若新解适应度值优于旧解适应度值，即fitness（x’）＜fitness（x），则以概率1 接受新解；若新解适应度值差于旧解适应度值，即fitness（x’）＞fitness（x），且式（23）成立，则粒子同样接受新解。

（6）更新个体最优值和群体最优值。

（7）判断是否达到马尔科夫链长度，否则返回步骤（3）。

（8）退温操作。

其中λ为退火系数。

（9）判断是否达到终止温度，若未达到，则返回步骤（2）。

（10）输出当前最优粒子，算法结束。

总体算法运行流程如图2所示。

Fig.2 Flow of SAPSMA图2 SAPSMA流程

3 实例验证

以某拣选中心的智能仓库为工况背景，该仓库中某区型的固定货架布局方式为12 列、15 排、5 层，共900 个货格。其中，货架的各参数分别为：单个货架宽度L=1.2 m，长度w=1.2 m，高度h=1.0 m，单条巷道宽度c=1.5 m。拣选AMR 的各参数：货格总数Q=8，最大承载总重量M=200 kg，水平方向最大速度v1=1.5 m/s，加速度a=1 m/s2，垂直方向升降台恒定上升下降速度v2=0.3 m/s，单次取货卸货时间为s=3 s。

本次验证所用数据均来自于某拣选中心的订单清单，其中包含30个待拣货物，货物信息见表1。

Table 1 Cargo information repository bit settings表1 货物信息存储库位设置

通过MATLAB R2022b 对SAPSMA 进行仿真实验，将其结果与SAA 和PSO 进行对比。为增强3 种算法的可比性，均使用相同的初始参数，如下：

（1）SAPSMA。种群规模80；最大迭代次数1 500；个体因子2，社会因子2；惯性权重最大值0.9，最小值0.4；初始温度2 000 ℃；马尔科夫链长度100；终止温度0.01；温度衰减系数0.99。

（2）PSO。种群规模80；最大迭代次数1 500；个体因子2，社会因子2；惯性权重0.75。

（3）SAA。初始温度2 000 ℃；马尔科夫链长度100；终止温度0.01；温度衰减系数0.99。

图3 为采用MATLAB 对3 种算法各运行30 次的平均收敛曲线。其中横坐标为算法运行的迭代次数，纵坐标为AMR 拣选总耗时。由图3可知：在相同参数的情况下，PSO在初期收敛较快，但容易陷入局部最优，导致搜索范围不够，无法得到最优解；SAA 虽然能够有效跳出局部最优位置，但是前期收敛震荡时间过长。相较于SAA 和PSO，SAPSMA 在PSO 算法的框架中引入SAA 的Metropolis 准则和温度衰减系数，使SAPSMA 可以快速跳出局部最优处，从而搜索到更高质量的解。

Fig.3 Comparison of convergence curves of the three algorithms图3 3种算法收敛曲线对比

表2 为3 种算法独立运行30 次后的运行结果，可以得出：SAPSMA 的收敛次数优于PSO 和SAA。虽然SAPSMA的运行时间略高于PSO 和SAA，但SAPSMA 解的上下波动性范围更小，更加稳定，且SAPSMA 解的平均值更小，得到的解质量更高。

Table 2 Experimental results of three algorithms表2 3种算法实验结果

表3 为SAPSMA 和SAA 的路径优化结果，因为PSO 算法陷入局部最优，无法得出最优解，故只考虑SAPSMA 和SAA 的最优解。其中SAPSMA 的拣选作业顺序为：0-12-3-18-19-8-30-11-0-23-16-20-5-0-27-13-15-9-14-0-26-22-21-7-17-4-25-2-0-6-10-1-29-24-28-0，将30 个SKU 分5 车次拣选完成，总耗557s；SAA 的拣选作业顺序为：0-2-24-10-6-3-18-0-25-16-21-7-22-20-5-0-19-11-8-13-27-30-28-12-0-23-4-17-26-14-9-15-1-29-0，将30 个SKU 分5 车次拣选完成，总耗时596s。通过与SAPSMA 对比，SAA 拣选总时间减少39s，总拣选时间节约7.01%。

由此可知，SAPSMA 在AMR 分批次拣选多目标分批次SKU 的路径规划中有较好的应用效果，该算法在迭代收敛上速度更快，解的精确度更高。

4 结语

本文针对多区型仓库中AMR 拣选多目标分批次的拣选路径规划问题，通过构建三维空间坐标，建立能够依次拣选订单中SKU 的三维路径规划模型，设计SAPSMA 对模型进行求解。实验结果表明，与其他启发式算法相比，SAPSMA 算法在相同参数下收敛速度更快，能有效避免算法陷入局部最优，得到具有更高精度的解。综上，本文构建的AMR 拣选模型及SAPSMA 在智能拣选仓库中具有较好的拟合效果，能有效提高仓库整体拣选效率。

然而本文仅研究了多区型仓库下某区型AMR 单指令出库为背景的订单拣选路径规划，即AMR 从起点出发，沿规划的路线移动到待拣货物所在行和列，分批次装载货物后返回起点。未来将对多指令作业及多AMR 在同一区型下共同作业的拣选路径规划问题进行深入研究。