安徽工业大学 安徽马鞍山 243032
Warehouse robot scheduling based on improved simulated annealing algorithm
Zhang Wenzhong，Wu Yuxiu，Zhang Dong-hong
（School of Electrical and Information Engineering, Anhui University of Technology, Maanshan, Anhui 243000, China）
Abstract:Intelligent warehouse robot scheduling problem, can through to the warehouse model map modeling, it is concluded that the scheduling problem is mainly the robot path planning problem using ant colony algorithm, genetic algorithm and particle swarm optimization (pso) method can effectively solve the problem of the class, but these algorithms are the pros and cons of mixed therefore an improved algorithm of simulated annealing algorithm to set initial annealing temperature, improve the cooling mode, the temperature setting a energy value, by comparing the size of the energy value of selective large cooling cycles and set up many times, can ensure the precision of the algorithm Finally, through experimental simulation and comparison with other algorithms, the efficiency of the improved algorithm is proved.
Keywords：Path planning, Ant colony algorithm, genetic algorithm, particle swarm algorithm, inner loop
摘要：智能仓库机器人调度问题，可以通过对仓库模型地图建模，得出调度问题其实主要是机器人路径规划问题。利用蚁群算法、遗传算法以及粒子群算法等方法可以有效解决该类问题，可是这些算法均利弊相杂。因此提出了一种改进的模拟退火算法，该算法对初始退火温度进行设置。改善了降温方式，对温度设定一个能量值，通过比较能量值的大小对其进行选择性的大幅度降温。并设置多次内循环次数，能够确保算法的精准性。最后通过实验仿真，通过对另外一些算法对比，证明了其改进的算法的高效性。
关键词：路径规划；蚁群算法；遗传算法；粒子群算法；内循环
一、 问题的提出
随着电子商务、快递、互联网以及新能源等技术的日新月异，人们对物质生活的需求也会越来越大，电商行业的订单迈向多种类、小层次、高频次的步伐。这种消费模式给传统“人到货”的拣选方式带来巨大挑战，尤其像“双十一”，“618”这类电商活动时，商品货量多、品种多、时间紧。为了针对这种问题，现代的智能仓储系统提出了“货到人”的分拣观点。在这种智能仓库中，大多采用定制的仓库机器人（AGV）代替人工来实现货物的拣货、分拣、搬运到派送等一些操作。
AGV的协调调度问题属于经典的NP-hard问题，可采用旅行商问题(TSP)模型[1]来求解。该问题分析情况复杂，并且随着城市数量的增多，问题复杂度呈现爆炸式增长。针对这一问题，国内外相关的学者提出了很多种算法。Colorni A等人[2]提出了蚁群算法来求解TSP问题，利用判断信息素在路径下未挥发的量的大小来选择最优路径，该算法虽然有着较高的收敛性，但容易陷入局部最优解，使得无法寻找到最优路径。郝翔，李仁厚等人[3-4]对基本遗传算法进行了分析，得出其搜索速度慢，且容易陷入局部最优，故进行改进提出了双群体遗传算法与多群体遗传算法。利用两个种群分工协作，一个是全局种群，一个是局部种群，首先获取可能解的临近区域，再进行精细搜索得到最优解。但该方法随着解空间的增大，耗费时间也是巨大的。雷开友等人[5]则提出了粒子群算法，对可能解不断跟新其位置与粒子速度来获取最优解，该算法对于低维函数的全局搜索能力强，寻优速度快。然而，当函数处于多波峰且高维时，容易得到局部最优解，迫使粒子趋于同化，有收敛过早的现象。
以上算法虽然比较效率高且运作简单，但都存在着陷入局部最优解的窘境。为此，本文在传统的模拟退火算法[6]的基础上，改进了该方法初始温度的设定，降温过程以及降温函数的选择，使得该算法精度与收敛速度有着很大的提升。
二、 问题描述
智能调度仓库采用最简单的栅格图法[7]来进行建立模型，如下图1所示。本文研究n个货物m个机器人运货过程，各个货物存在于货架上，分散在仓库的各个不同的位置。每台机器人均存在一组任务序列，机器人从运货起点出发，游历自己的任务序列进行取货，运送到包裹分拣区，直至本轮所有任务全部完成。
.png)
图1 简易栅格图
AGV调度问题还有一些其它的一般性假设：
（1）一个机器人在同一时刻一次只能运送一件货物。
（2）不考虑机器人在上货与下货过程中的时间，即此过程需要时间为0；
（3）机器人在仓库中运送货物时始终保持匀速，不存在突然加速或者减速。
（4）不考虑机器人电量问题，机器人始终工作在电量充足的情况下，且空载机器人与负载机器人运行速度也是一致的。
问题模型描述如下：m个机器人一共存在着n个任务，平均分配给每
.png)
三、 基于改进的模拟退火算法
模拟退火算法（Simulated Annealing, SA）是源于对热力学中退火过程的模拟，如下图2所示，对于一个非晶体状态的物体，先通过升温至一个较高的温度，此时粒子会因温度的升高变为无序状态，同时内能增大，再通过缓慢下降温度参数，即退火过程，这样物体粒子就逐步变成有序状态，此时粒子间的内能也会达到最低。
该算法属于一种常用的随机搜索算法，通过扩展局部搜索算法得到的。与常见的局部搜索算法相异的是，SA算法在迭代更新可行解时，还会以一定的概率来接受一个比当前解要差的解，因此可能会通过这样一定的概率跳出局部最优的状态，从而可以得到全局的最优解。如下图3所示，设初始解为G点，由此出发搜索，到达A点后，若不加随机因素，则在此点陷入局部最优，A点左右均是A点能量最低。但由于加入随机因素，到达A点时，还是有一定概率跳出A点，从而到达B点，最终到达G点，也就是全局最优解，从而获得最短移动时间。
.png)
图3 数学描述
（一） 初始解
由问题模型描述，本文初始解空间就采用常用的随机构造一组任务序列。针对AGV调度问题，选取一组路径[o,n1,c,n2,...,c]为初始解，其中该一维矩阵中的每一个元素均是机器人需要移动的目标点。
（二）领域解空间构造以及终止条件
在小规模任务序列中，单一的搜索方式就可以完成解的构造。但在多任务大规模的任务序列中，单一的搜索方式容易导致陷入局部最优解，从而降低解的质量。为了避免出现这样的问题，本文提出基于一定概率的选取构造解的方式。3种领域构造解的操作如下：
两点交换：随机从任务序列中抽选两个任务序列点，进行交换，从而得到新的任务序列。
组块交换：将多任务序列平均切分为若干组，每组均有几个元素，然后挑选两组，进行组间交换位置，从而组成新的任务序列。
颠倒交换：将一维数组中的除起始终止点的元素之外的所有一个元素向后移动一个位置，最后的元素移动到第一个元素的位置，从而组成新的一组序列。
算法的终止条件为：当温度到达了临界点或者解的目标函数值不在改变。其中终止温度临界点一般不设置为0，因为在温度较低情况下，接受移动的概率极低。
（三） 初始温度的设定
验值一般在（0.80,0.99）之间。可该方法收敛速度较慢，会损耗大量时间。因此，本文采用一次性跳跃与二次跳跃的降温方式。
一次性跳跃：每个温度都会有能量值P，在某个温度下的M次迭代，迭代成功的次数越多表明该温度的能量值越大。给定一个能量标准值N,通过将P值与N值相比，如果P值大于N值，则表明该温度在临近的温度之中，迭代成功次数最多，此时可以一次性跳跃，这样临近的温度所需要的降温环节省略，可以进行一次大幅度降温过程。
二次跳跃：上述的一次性跳跃会存在一个问题，选择某一个温度大幅度降温，这样它的临近温度会直接被省略，如果它的临近温度的区域内还存在另一个这样可以大幅度降温的温度也将会被省略，这样可能就会跳过全局最优解，为此提出了二次跳跃。通过对第一次获取的较优解重新放回高温条件下再次迭代。这样第二次退火后，会将第一次退火存在的一次性跳跃的温度重新找出来继续跳跃。经过两次迭代后，整体的精度会有一个很大的提高，而且更容易获取全局最优解。
（五） 内循环搜索次数
为了使得结果更稳定真实，故采取3次内循环搜索，即对某温度下搜索迭代次数为3次。
（六） 执行Metropolis准则
此步骤与一般的SA相同，利用Metropolis准则[8]判断是否接受新解，
由该模型可知：温度越高，退火的降温概率越大；温度越低，降温概率就越小。
（七） 目标函数
由问题模型描述可知，为了检验和比较算法准确性，本文以获取最小移动时间为唯一的优化目标。即利用公式3作为目标函数的设定。
（八） 算法流程
改进后的SA算法流程如图4所示，初始化初始解后经过领域解空间生成、搜索、执行Metropolis准则、降温等一系列操作的不断循环完成退火，直至得到最优解。
.png)
图4 改进的SA算法流程图
四、 仿真实验分析
本文从TA数据[9]集中选择一些案例（TA61~TA100），通过对混合遗传算法（Hybrid Genetic Algorithm,HGA）[10]、利用禁忌搜索改进的贪婪迭代法（Tabu-Mechanism Improved Iterated Greedy,TMIIG）[11]、反向差分进化算法（Opposition based Differential Evolution algorithm,ODDE）[12]、扩展的人工染色体遗传算法（extended Artificial Chromosomes Genetic Algorithm,eACGA）[13]、标准SA算法进行实验对比，具体结果如下表1所示：
表1 TA数据集实验结果
.png)
注：以上数据的单位为： 。
通过仿真实验结果表明,改进的SA算法与其他算法相比，尤其是标准的SA算法相比，具有更短的搜索运行时间，可以得到较为满意的全局最优解。
五 总结
模拟退火算法应用广泛，通过对解的交换方式、初始温度以及降温方式的一系列的改进操作，使得可以高效的解决TSP问题以及AGV调度等问题。改进的模拟退火算法具有鲁棒性更强，运行速度更快等优点，但是也存在一些缺陷。比如：一次性降温跳跃目前只能对能量值做一个定性的分析，不能达到定量的控制。还有就是改进后的算法中，对于温度的管控也是一个比较复杂的问题。并且在实际应用开发中，还必须要考虑到计算复杂度的可实现等问题。
参考文献：
[1] 俞庆生, 林冬梅, 王东. 多旅行商问题研究综述[J]. 价值工程, 2012, 31(02): 166-168.
[2] Colorni A, Dorigo M, Maniezzo V, et al. Distributed Optimization by Ant Colonies. Proceedings of European Conference on Artificial Life, Paris 1991: 134-142.
[3] 郝翔，李人厚. 一种快速有效的多模态函数优化方法：双群体遗传算法. 控制理论与应用，1997，(5)：765-769
[4] 郝翔， 李人厚. 适用于复杂函数寻优的多群体遗传算法. 控制与决策，1997， (3)：236-266
[5] 雷开友. 粒子群算法及其应用研究[D]. 重庆：西南大学，2006
[6] 王银年, 葛洪伟. 求解TSP问题的改进模拟退火遗传算法[J]. 计算机工程与应用, 2010, 46(05): 44-47+85.
[7] 余娜娜，李铁克，王柏琳，袁鹏. 自动化分拣仓库中多AGV调度与路径规划算法[D] 北京：北京科技大学 2020.
[8] 宋锦河. 基于模拟退火算法的生产调度问题 [J]. 长春工程学院学报 (自然科学版), 2004(1): 63-65.
[9] FU Yaping, ZHOU Mengchu, GUO Xiwang, et al. Schedu-ling dual-objective stochastic hybrid flow shop with deteriora-ting jobs via bi-population evolutionary algorithm[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2019.
[10] A hybrid genetic algorithm for no-wait flowshop scheduling problem[J] . Lin-Yu Tseng,Ya-Tai Lin. International Journal of Production Economics, 2010, 128(1): 144-152.
[11] An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion[J]. Quan-Ke Pan,Ling Wang, Bao-Hua Zhao. The International Journal of Advanced Manufacturing Technology. 2015, 30: 604-613.
[12] An opposition-based differential evolution algorithm for permutation flow shop scheduling based on diversity measure[J]. Xiangtao Li,Minghao Yin. Advances in Engineering Software, 2013, 55: 10-31
[13] Extended artificial chromosomes genetic algorithm for permutation flowshop scheduling problems[J] . Yuh-Min Chen,Min-Chih Chen,Pei-Chann Chang,Shih-Hsin Chen. Computers & Industrial Engineering, 2012, 62 (2): 536-545.
作者简介：
张文忠（1997-），男，安徽铜陵人，在读硕士研究生，研究方向为机器人调度，安徽工业大学；
张东红（1995-），男，安徽庐江人，在读硕士研究生，研究方向为计算机视觉，安徽工业大学。