GASA混合优化算法在自动化立体仓库堆垛机作业调度问题中的应用

姜 山，季业飞

JIANG Shan1, JI Ye-fei2

（1. 交通运输部公路科学研究院 公路交通发展研究中心，北京 100088；2. 中国中元国际工程公司 工程事业二部，北京 100089）

GASA混合优化算法在自动化立体仓库堆垛机作业调度问题中的应用

Application of GASA hybrid optimization algorithm in the stacker’s dispatch problem in as/rs

姜 山1，季业飞2

JIANG Shan1, JI Ye-fei2

（1. 交通运输部公路科学研究院 公路交通发展研究中心，北京 100088；2. 中国中元国际工程公司 工程事业二部，北京 100089）

堆垛机出入库调度优化问题是提高自动化立体仓库工作效率的关键技术之一。本文通过对出入库调度问题中影响堆垛机作业时间因素的分析，把堆垛机调度的优化路线问题转化为TSP问题，然后采用遗传—模拟退火混合优化算法来解决。数值试验表明混合优化算法吸收了单一算法的各自优点，克服了本身的缺点，显示出较强的全局优化能力，为立体仓库任务调度问题提供了新的求解思路。

遗传算法；模拟退火算法；堆垛机；自动化立体仓库

0 引言

自动化立体仓库是物流系统的重要组成部分，又称自动存储自动检索系统（Automatedstorage/Retrieval system，As/Rs），是一种新型的仓储技术。它是以高层货架为主体，以成套搬运设备为基础，以计算机控制技术为手段的高效率物流、大容量存储的机电一体化高科技集成系统。它的出现大大拓展了仓库功能，使之从“静态仓库”变成了“动态仓库”，由单纯的保管型向综合的流通型方向发展，通过有效衔接生产与库存，加快了物资周转，大大降低了生产成本。

近30年来自动化立体仓库的硬件设备的技术、自动控制以及通讯技术己十分完善，工作效率有了大幅提高，但现代机械制造对仓库的工作效率的要求也在不断提高。如何在不增加设备投资的情况下，通过优化仓库的管理和调度，减少作业时间，就成为提高自动化立体仓库工作效率的关键研究技术，其中堆垛机出入库调度优化问题是一个重要的研究课题。本文通过对立体仓库出入库调度问题中影响堆垛机作业时间因素的分析，把堆垛机调度的优化路线问题转化为常见的TSP问题，然后采用遗传—模拟退火混合优化算法（GASA）来求解，取得了较好的效果。

1 堆垛机作业调度优化问题

自动化立体仓库货物的存取有两种基本方式：一种是单一作业方式，另一种是复合作业方式。在单一作业方式下，堆垛机作业时间是一个定值，与作业任务的执行顺序无关。在复合作业时，堆垛机接到一批出入库指令，即堆垛机从原点出发执行第一条指令，运行到指定货格取出托盘并将托盘运送到原点，由操作人员按单据具体内容取出或放人物料，接着堆垛机再将托盘放回原库位处，从而完成一个库位作业。之后，堆垛机并不回到原点而是直接执行下一个指令，即寻找下一个库位号，如此反复直到完成所有的指令为止。堆垛机复合作业方式如图1所示：

图1 堆垛机复合作业示意图

此种方式下，图1所示三个作业任务时的作业时间为：

不难推导出堆垛机执行完n条作业任务时，总的作业时间是：

其中Tn为堆垛机完成所有的作业任务所花费的总时间，T0,j为从原点P0（出入库台处）到Pi（指定库位处）所用的时间，Ti,0为堆垛机从点Pi（指定库位处）到原点P0处所用的时间， Ti-1,i为从点Pi-1（前一库位）到Pi（当前库位）所用时间。最后一项 为堆垛机完成所有出入库任务后从最后一个库位Pn处回到原点P0（出入库台处）待命所用的时间。

不难发现，当一批出入库任务指定后，不管任务执行的先后顺序如何，第一部分的值总是确定的，它对堆垛机的运行时间是没有影响的。而第二部分为一个从原点出发途经各指定库位的回路，当堆垛机采用不同的行走顺序，路径长度是不同的，执行的时间也不相同。对于这部分堆垛机所走的路径就是一个从原点出发途经各指定库位再回到原点的回路，这是一个典型的旅行商(TSP)问题。

2 GASA混合优化算法求解堆垛机作业调度优化问题

旅行商（TSP）问题是典型的非多项式时间可解难题(NP-hard Problem)。目前遗传算法(Genetic Algorithm，GA)和模拟退火算法( Simulated Annealing Algorithm， SA)等智能优化算法被广泛用于求解TSP问题。但是对于NP难问题，单一机制的优化算法很难实现全局优化，且效率也不高。遗传算法有较强的全局搜索能力，但算法的一些参数如果选取不当，易陷入局部最优解难以自拔。模拟退火算法有较强的局部搜索能力，但其参数一样很难确定，且返回一个高质近似解的时间花费较多，当问题规模增大时，难于承受的运行时间将使算法丧失可行性。多种优化机制的相互结合，是提高全局优化能力的有效途径之一。本文提出利用遗传—模拟退火混合优化算法求解堆垛机作业调度优化问题。

遗传—模拟退火混合优化算法可以归纳如下：GA利用SA得到的解作为初始种群，通过复制、交叉、变异等遗传操作使种群得以进化；SA对GA得到的进化种群进行进一步优化，温度较高时表现出较强的概率突变性，体现为对种群的“粗搜索”，温度较低时演化为局部搜索，体现为对种群的“细搜索”。混合优化算法求解堆垛机作业调度问题步骤如下：

1）对作业序列决策变量随机编码产生初始种群X(1)，确定初温和合理的适应度函数。

2）计算种群中每一个体xi(k)，k=1,2,……N的适应度。如果连续几代个体平均适应度的差异小于某一个极小的阈值，则选当前最佳的个体为最优染色体，进行解码得到最优解。否则转3）。

3）根据适应度分布复制种群X(k)。

4）根据交叉概率Pc，执行交叉操作。

5）根据变异概率Pm，执行变异操作，从而得到新种群X(k+1)。

6）对X(k+1)中每一个体进行Metropolis抽样。

7）由SA状态产生函数产生新个体。

8）以概率接受新个体。

9）若抽样稳定，退温，转2）。否则，转7）。

关于上述算法的说明：

1）在1）中，堆垛机执行复合作业要实现时间越少越好，即实际优化目标函数为因此确定混合优化算法的适应度函数为为一数值较大的实数。

2）在7）中，SA状态产生函数可设计为互换操作(SWAP)，即随机交换染色体中两不同基因的位置，也可设计为逆序操作(INV)，即将染色体中两不同随机位置间的基因串逆序。

3 数值模拟

假设某自动化立体仓库巷道堆垛机从上位管理机接受单据，任务序数为1～7，货位地址（XK，Yk）（k=l，2，…，7），其中1、4、5、7为入库任务，2、3、6为出库任务。堆垛机从出入库台O点(0，0)出发进行复合作业，最后要返回到出入库台0点。各个货位之间的运行时间如表1 所示。

表1 各个货位之间的运行时间 单位：秒

分别采取遗传算法、模拟退火算法和GASA混合优化算法求解，三种优化算法都得到相同的复合作业顺序结果，7个货位点之间进行复合作业的顺序为(1，2，5，4，6，7，3)，即堆垛机按照(0→1→2→0→5→0→4→6→0→7→3→0)完成复合作业，对应的堆垛机运行时间为264.5秒。但从表2中可以看出SA优化时间性能较差，GA略有改善，GASA混合优化算法在时间性能上优于它们。

表2 混合算法和相关算法性能统计比较

4 结束语

本文运用遗传—模拟退火混合优化算法求解自动化立体仓库堆垛机的作业调度优化问题。数值模拟实验表明，混合优化算法吸收了单一算法的各自优点，克服了它们本身的缺点，大大提高了搜索效率。遗传算法与模拟退火算法的结合显示出卓越的优势，遗传算法跟其它优化算法的结合在求解自动化立体仓库堆垛机调度问题方面也可能发挥更大的威力，对此问题我们将另文讨论。

[1] 周明,孙树栋.遗传算法原理及应用(M).北京:国防工业出版社,1999.

[2] 康立山,谢云,尤矢勇,等.非数值并行算法(第一册):模拟退火算法[M].北京:科学出版社, 1997.

[3] 王凌.智能优化算法及其应用(M).北京:清华大学出版社,2001.

[4] 刘伟铭,姜山.基于GASA混合优化策略的双层规划模型求解算法研究[J].土木工程学报,2003,36(7):27-32.

[5] 朱耀明.自动化立体仓库优化调度研究[D].济南:山东大学,2006.

[6] 刘惠.自动化立体仓库效率优化研究[D].沈阳:辽宁工程技术大学,2007.

TH166

B

1009-0134(2010)10(上)-0063-03

10.3969/j.issn.1009-0134.2010.10(上).19

2010-04-06

姜山（1977 -），男，山东诸城人，经济师，硕士，研究方向为交通运输工程与交通运输经济。