基于SA的PSO自动化仓库拣选作业路径优化方法

王海珍，彭梅香

（新余学院 工程系，新余 338025）

基于SA的PSO自动化仓库拣选作业路径优化方法

王海珍，彭梅香

（新余学院 工程系，新余 338025）

0 引言

现在，自动化立体仓库已经成为现代物资存取技术与自动化技术相结合的高新技术产物，是物流自动化的显著标志之一，是现代化大生产的必然产物。为满足现代生产与物流的需要，就必须采用以计算机控制技术为主要手段组成的自动化立体仓库。立体仓库制造业在国外已经发展成为一个新兴的高科技产业，取得了可观的经济效益。而我国对该课题的研究起步较晚，尤其缺少对物流信息论、输送系统控制和优化调度的系统性理论研究，使目前的自动化立体仓库不能实现物流信息化、最优化作业，大大降低了操作效率，产生高投入、低运行速度和低效率的状态。

1 自动化立体仓库和拣选作业原理

自动化立体仓库又称自动化高架仓库和自动存储系统（AS/RS系统），它是一种基于高层货架、利用电子计算机进行控制管理、采用自动化存取输送设备自动进行存取作业的仓储系统。自动化立体仓库由多排的立体货架构成，还包括物资自动存取设备、输送系统、堆垛机系统、 自动分拣系统、计算机管理与控制系统等几部分，如图1所示。

拣选操作流程通常是由堆垛机操作员先从仓库管理控制系统取得一张打印的批量拣选作业任务表单，然后乘坐巷道堆垛机按照任务表单上列出的每项存取拣选任务，通过手动或自动的操作方式，依次控制堆垛机从一个己完成的任务点移动到下一个将要进行拣选的任务点。当任务表单上的所有任务全部完成或者拣选货箱己放满时，将堆垛机开回到出/入库站台处，卸下物资。通过拣选作业流程的描述可以把堆垛机的拣选作业调度归纳成如下问题：设有n个拣选任务，即有n个货位点等待堆垛机到达，堆垛机从出/入库站台处出发，分别到达n个货位点，且每个货位点只去一次，最后回到起点，求堆垛机运行的最短路径。

图1 自动化立体仓库构成图

2 粒子算法

粒子群算法简介：粒子群算法（Particle Swarm Optimization，简称PSO）最早是在1995年由美国的Eberhart和Kennedy共同提出的，其基本思想受他们早期对许多鸟类的群体行为进行建模与仿真研究结果的启发，他们的模型及仿真算法主要利用了生物学家Hepper的模型。在粒子群算法中，每个个体称为一个“粒子”，其实每个粒子代表着一个潜在的解。例如，在一个D维的目标搜索空间中，每个粒子看成是空间内的一个点。设群体由m个粒子构成。m也被称为群体规模，过大的m会影响算法的运算速度和收敛性。

3 基于模拟退火的粒子群优化算法

3.1 固定货架堆垛机拣选作业路径优化问题

自动化立体仓库的工作效率也主要取决于固定货架的拣选作业效率，所以固定货架的拣选作业路径的优化对自动化立体仓库的自动化程度的提高有相当重要的作用。假设某自动化立体仓库的固定货架子系统共包含13排立体货架，每排货架分为10层72列共720个货位。

固定货架及堆垛机运行参数设定如下：

设定1：以拣选方式存取货物时，操作者对某一货物的拣选时间只与该货物的种类和数量有关，不随存取顺序的变化而变化；在计算拣选作业时间代价时，忽略货物存取时间。

设定2：堆垛机在不同货物之间移动时，在水平方向和垂直方向上都以恒高速运行，其制动和起动过程忽略不计；堆垛机水平运行速度为vx，垂直运行速度为vy；堆垛机运行时在水平方向和垂直方向可以同时运动。

设定3：图形结点为在单巷道内堆垛机需要存取的货位点，以坐标（x，y）标志，x和y分别表示货位点的列号和层号，将货位点（0，0）视为巷道口，并将其作为整个拣选作业的附加货位点。单个货格宽度为b，高度为h。

设定4：在拣选任务全部完成后，拣选货箱未满或刚好满。

3.2 粒子群算法求解拣选作业路径优化问题

令粒子群中的第i个粒子表示为zi=(zi1,zi2,...,zid)，由于每个位置向量zid在算法的初始阶段是随机产生的实数，并且每个位置向量通过位置-速度模型中的初等运算进行更新，粒子zi中每个向量zid在数值上存在相同的机率很小，因此，粒子zi中的所有位置向量必然存在一个次序S，这个次序S在迭代计算过程中随着粒子位置向量的不断更新也不断地发生变化。

3.2.1 粒子位置和速度

我们将zi取[zmin,zmax]之间的随机数为粒子初始位置。在迭代计算时对粒子位置向量值的大小不设定限制范围，而只是将初始粒子群中的粒子位置限定在一定的范围内产生。将vi取[vmin,vmax]之间的随机数为粒子zi初始速度的取值。

3.2.2 评价函数

3.2.3 个体和全局最优粒子

根据粒子位置向量排序生成有效拣选作业路径后计算其所花费的时间代价来确定的个体和全局最优粒子，即选择花费的时间代价最小的粒子作为个体和全局最优粒子。3.2.4 粒子群模型及参数

采用惯性权重线性递减粒子群模型，惯性权重w从0.9线性递减到0.4，学习因子c1和c2取值为2，粒子邻域大小取全部粒子种群。

3.3 基于模拟退火的粒子群优化算法

模拟退火算法（Simulated Annealing，SA）是局部搜索算法的扩展，它不同于局部搜索之处是它以一定的概率选择邻域中适应度值高的状态，理论上来说，它是一个全局优化算法。

图2 m=50，maxIteration=100时的计算结果

图3 m=50，maxIteration=200时的计算结果

图4 m=50，maxIteration=500时的计算结果

图5 m=50，maxIteration=1000时的计算结果

模拟退火法出发点是利用物理退火过程与优化问题间的相似性，将优化目标看作退火过程中金属的能量状态，模拟金属退火过程，寻求目标函数最优解。模拟退火法从某一初始温度出发，伴随系统温度的不断降低，在全局解空间中随机寻找最优解，不但接受对目标函数值有改善的好状态，还以某种概率接受使目标函数值恶化的劣状态，从而实现大范围粗略搜索与局部精细搜索的结合。基本粒子群算法中，虽然粒子速度作了限制，不会变化太大，但位置更新未作限制，就有可能新的位置会变得很坏，引起收敛速度缓慢，所以要对更新的位置作限制。论文引入模拟退火思想，计算粒子位置更新前后目标函数值的变化量ΔE，若ΔE≤0，接收新值；否则，若exp(-ΔE/T)>rand（0，1）（T为模拟退火初始控制参数，模拟退火系数α=0.99），也接受新值；否则就拒绝。

4 实验仿真与结果

自动化立体仓库其货架及堆垛机的参数设定为：b=1m，h=1m，vx=3m/s，vy=1m/s。由于受拣选台机械强度的限制，单次拣选作业拣选的货位数一般小于100个。随机产生30个货位点的拣选单，各货位点坐标如下：{（0,0），（33,5），（31,7），（3,9），（8,2），（14,6），（44,5），（0,7），（23,1），（48,1），（58,6），（25,0），（32,5），（46,5），（30,8），（29,7），（4,5），（70,9），（57,3），（66,8），（53,3），（19,8），（18,7），（55,4），（65,5），（52,1），（10,9），（13,1），（64,9），（71,1）}，应用MATLAB编辑计算。用模拟退火算法进行改进，起始温度T=10000，退火速度a=0.99，最大迭代次数maxIteration分别为100、200、500和1000，程序各运行20次，得到的计算结果，在这里不列出所有计算结果。不同最大迭代次数迭代终止时单次计算结果如图2、3、4、5所示。

从计算结果可看出，基于模拟退火的粒子群算法在求解拣选作业路径优化问题时，在最大迭代次数分别为100和1000时求解效果略差与基本粒子群算法，而在最大迭代次数为200和500时略优于基本粒子群算法，而且当最大迭代次数maxIteration=1000时反而没有最大迭代次数maxIteration=500时的求解效果好。分析其原因，是模拟退火中粒子位置更新的限制条件约束了粒子的寻优过程，导致有时粒子没有移动，减少了粒子向最佳位置靠拢的机会。所以，应用基于模拟退火的粒子群算法在最大迭代次数为200和500时可得到比基本粒子群算法较好的效果。

基于模拟退火的粒子群算法在最大迭代次数设置合适时可以得到比基本粒子群算法较好的效果，且算法复杂度和基本粒子群算法相差不大，只多了一个粒子位置更新的约束条件。所以，在实际应用中可以考虑应用基于模拟退火的粒子群算法来优化拣选作业路径。

[1]常发亮,刘增晓,辛征,刘冬冬.自动化立体仓库拣选作业路径优化问题研究[J].系统工程理论与实践,2007,27(2):139-143.

[2]李梅娟,陈雪波,刘臣奇.基于改进蚁群算法拣选作业优化问题的求解[J].计算机工程,2009,35(3):219-221.

[3]刘志雄.物流自动化仓库拣选作业调度粒子群优化研究[J].机械制造,2010,48(1):66-69.

An optimization methods of order picking path in automated warehouse based on SA

WANG Hai-zhen, PENG Mei-xiang

自动化立体仓库是现代化大生产的必然产物，立体仓库制造业是我国新兴的高科技产业。本文分析自动化立体仓库拣挑算法的路径优化问题，提出基于模拟退火的粒子算群算法，求解拣选作业路径优化问题，得到了较好的效果。

模拟退火；粒子群算法；自动化仓库

王海珍(1974 -)，女，江西樟树人，讲师，本科，研究方向为自动化。

TP311

B

1009-0134(2011)5(上)-0090-03

10.3969/j.issn.1009-0134.2011.5(上).31

2010-12-21