基于模拟退火蚁群算法的拣货路径规划

胡治锋，陈冬方，李庆奎，恒庆海

（1.北京信息科技大学，北京 100192；2.北京天地玛珂电液控制系统有限公司，北京 100020）

仓库集存储、输送、分发、管理于一体，在仓储物流中是非常重要的一部分。提高仓库管理效率，一方面可以优化仓位设置，另一方面可以在货物分批、货物拣选路径规划等方面进行优化。

文献[1]为提高鱼骨型仓库布局下的订单拣选效率,基于拣货路径距离计算模型和以最小化拣货路径总距离为优化目标的拣选路径优化模型,提出一种混沌模拟退火粒子群优化算法，引入混沌理论使粒子更高效地遍历搜寻空间，同时结合了模拟退火算法的概率突跳特点使算法在迭代后期仍具有较好的全局寻优能力，为鱼骨型仓库布局下拣选路径规划问题提供了新的解决思路。现在很多大中企业建设了自动化仓库，结合很多优化算法利用机器人进行拣选。文献[2]研究了基于栅格图法的移动物流机器人全局路径规划方法，针对传统方法无法有效解决物流机器人一次访问若干个节点的全局路径规划问题，通过栅格图法构造容易被移动物流机器人理解的仓储环境，效率得到了显著提高。文献[3]介绍了物流机器人路径规划研究现状，近几年物流机器人的应用已经成为物流企业市场竞争的重要手段，如何得到最优路径成为研究的关键。虽然利用物流机器人进行货物拣选或搬运有效地提高了仓储效率，但是根据不同的研究可以看出目前的路径规划研究还存在部分问题。文献[4]针对物流领域降低配送成本、提升配送效率的需求,对物流路径的优化方法进行了研究，通过数学建模的方式，将物流路径优化问题转化为数学研究领域经典的旅行商问题(TSP)，对传统的粒子群算法加以改进，引入了遗传算法的交叉操作与遗传因子。在路径规划方面，文献[5]基于A*算法和改进模拟退火算法提出了一种新型的航迹规划方法，解决了在复杂约束条件下完成多目标任务的问题。文献[6]总结了相关路径规划算法，同时也对未来路径规划算法进行了展望。文献[7]利用改进遗传算法对包装废弃物的回收车辆进行了路径规划，通过与传统算法比较，改进遗传算法取得了更好的效果。文献[8]研究了基于模拟退火蚁群算法的机器人路径规划方法，优化变电站巡检机器人巡检路线，节省巡检时间，加入了偏离度参数，但计算量略大。

1 问题提出

从目前的研究来看，国内外的相关研究相对集中于自动化拣选仓库的库位和仓库货位的优化等方面。但对于很多小型企业，仓库的运营管理依靠人工进行操作，很多企业货物拣选顺序依赖人的主观判断，导致拣货效率偏低[9]。

该文在已有研究基础上将拣选路线问题抽象成旅行商售货（TSP）问题，借鉴机器人路径规划的方法，忽略拣选人的可拣选数量以及货物的体积，应用了一种以路径最短为目标的优化数学模型，并将两种算法结合之后的算法进行仿真比较，经分析得出新算法较原先单一的算法取得了更好的效果。

2 货物拣选路径规划的数学建模

在各种仓储活动中，有各种各样的货架，文中以仓库中的最常规的多层货架为基础建立数学模型。

在货架b中有O个货位的货物，可以记作o=(1,2,…,O-1,O)，待拣选的货物位置可表示为l=1,2,…,i,j,L-1,L。两个货位i、j之间的距离可表示为：

基于这些，文中给出了一些参数：

o∈O表示所有待拣选的货物合集；

i、j∈L表示待拣选货物的位置；

dij表示两个货位之间的距离；

表示b货架是否先拣选i后拣选j；

表示拣选人员总是能一次拣选完所有位置；

表示从货架b的i位置拣选货物。

该模型忽略拣选人员的拣选容量以及货物的重量体积，将拣选最短距离作为目标函数[10]。目标函数为：

限制条件如下：

目标函数（2）最小化拣选完所有货物经过的路径距离，式（3）确保每个货位只经过一次，式（4）保证所有位置能一次拣选完，式（5）确保只拣选需要的货物的位置，式（6）（7）声明每个位置只经过一次，且只有一个前任和后继，式（8）确保访问了所有位置，避免出现子行程，式（9）指出决策变量是二进制的[11]。

在分析模型目的和特征的基础上，对模型进行描述与假设：

①在对一批货物进行拣选时，仅由一个人完成拣货。

②拣货时，拣选完所有货物时的重量和体积不会超过拣选人的最大容量。

③仓库中所有的货架全部是上下结构且水平排列的，仓位之间距离固定。

3 算法描述

模拟退火算法用于优化问题是因为物理中固体物质的退火过程和一般组合优化问题之间存在相似性。虽然它有大范围全局搜索的能力，但是模拟退火算法没有有效的正反馈机制，当求解到一定程度后，往往作一些没有用处的迭代，因此求解精度值偏低[12]。而蚁群算法的原理本质上是一种正反馈机制，但是在初期的迭代过程中产生的信息素十分有限，由于反馈的信息有限，因此需要漫长的过程，求解速度较慢[13]，不能满足要求。文中将模拟退火算法与蚁群算法混合来解决货架拣货路径规划问题，采用模拟退火算法快速生成一个解，将信息素分布在这个解上，利用蚁群算法的正反馈机制求精确解，取长补短，期望获得优化效果和快速求解的双赢[14]。

混合算法的思路是首先由模拟退火算法快速产生较优的解，较优的路径留下信息素；然后让蚂蚁按照蚁群算法，利用留下的信息素完成一次遍历后，采用模拟退火的方法在邻域内找另外一个解，这个解有可能不是更好的解，这个时候接受准则采用模拟退火的思想[15]，允许目标函数有限范围内变坏，为简化计算量并不按概率取舍，若路径长度差ΔE＜e接受，e为按允许目标函数变坏范围。

每只蚂蚁走过的路径会留下信息素，与此同时原本路径的信息素会挥发一部分，所以信息素的更新分为局部信息素更新和全局信息素更新[16]。局部信息素的更新是对于已选的边对于后来的蚂蚁有较小的影响力，从而使得蚂蚁对于没被选中的边具有较强的影响力，当蚂蚁从位置i移动到位置j之后，边(i,j)上的信息素按下式更新，其中τo为常数，η为可调参数。

当所有蚂蚁均完成一次搜索后，对全局最优解进行全局信息素更新。这时只对最优路径进行信息素加强，因此增大了最优路径和最差路径间信息素的差异，从而让蚂蚁更快集中到最优路径附近，加快全局收敛[17]。

3.1 流程图

算法流程如图1 所示。

图1 算法流程图

3.2 模拟退火蚁群算法步骤

1）模拟退火算法产生初始解；

2）较优路径留下信息素；

3）蚁群算法完成一次遍历，产生一个解；

4）模拟退火算法在蚁群算法产生的解的邻域内找出一个新解；

5）判断ΔT是否小于0，若是则蚁群更新信息素，否则回到步骤2）；

6）判断蚁群算法是否达到最大迭代次数，如果是则输出最优解，否则回到步骤2），继续循环。

4 模型仿真分析

4.1 仿真环境

文中利用Matlab R2016b 编写算法实现程序，并进行算例求解，所有的工作均在一台计算机上完成。

4.2 模拟退火蚁群算法效果分析

为了验证融合的模拟退火蚁群算法是否对货物拣选路径规划有效，应用某小型仓库货架的某一段时间的某一次拣货进行优化处理。实验时选取了16个货位，设置蚂蚁个数m=50，信息素蒸发系数r=0.1，信息素启发算子α=1，期望启发算子β=5。退火参数设置初始温度Tmax=100，终止温度Tmin=0。

该文仅展示了蚁群算法和模拟退火蚁群算法的路线规划图。如图2 所示，蚁群算法虽然也规划了行程，但是却陷入了局部最优解，得到的不是全局最优解，而图3 所示的模拟退火蚁群算法较好地规划了拣选货物时的路径。因此模拟退火蚁群算法为路径规划缩短了行程，节省了时间，提高了工作效率。

图2 蚁群算法

图3 模拟退火蚁群算法

经过多次实验求取平均值，规划最短路径时间为Tmin，输出最优解迭代次数D，最短路径为Zmin，得出结果如表1 所示。

表1 3种算法比较

4.3 大规模货架路径规划实验

实际上有的立体货架规模较大，货位数量可能达到上百个，故该文以路径最短为目标，分别用模拟退火算法、蚁群算法以及模拟退火蚁群算法对货位数为100 的立体货架进行仿真实验，分别求解得到的迭代曲线，如图4 所示。可以看出，模拟退火蚁群算法能够得出更优的解，新算法较传统的模拟退火算法，得出最优解需要的时间降低10.7%，较蚁群算法迭代次数减少28.4%，有效提高了人工拣选的效率。

图4 各算法迭代曲线图

5 结论

为了改善仓储活动中人力拣选货物时没有路径规划的情况，提高仓库的运行效率。该文分析了立体货架拣货时的特点，结合旅行商（TSP）问题中的两种常用算法——模拟退火算法和蚁群算法对立体货架的货物拣选路径进行规划。经过仿真实验，该算法有效解决了模拟退火算法无法有效利用系统中的反馈信息，使得求解到一定精度后往往作一系列无用的迭代，导致无法求精确解以及效率低的问题，同时解决了蚁群算法求解速度慢的问题，有效提高了全局搜索能力并减少了迭代次数，缩短了路径规划的时间。

总的来说，该文所研究的只是仓储活动中单一的拣货路径问题，对有关要素进行了适当的简化处理，而事实上仓储活动是一系列工作的集合，以后的研究应该着眼于整个仓储活动。