自动小车存取系统的调度优化

（北京机械工业自动化研究所有限公司，北京 100120）

1 问题的提出

根据有关部门的数据，我国2015年社会物流总费用为10.8万亿，占GDP总量的16.0%。显然，从商业的角度出发，发展物流行业，提高效率，减少支出比单纯地提高制造效率有着更重要的价值。仓储作为物流行业的一个重要环节很早就引起了重视。电子技术、电器技术、信息技术和机械设计制造的飞速发展使得一种新型的仓储方式——自动化立体仓库（Automated Storage/Retrieval System，AV/RS）的出现变得理所应当。美国的Malmborg教授领导团队于2003年首先开始了一种新型的自动化立体仓库——自动小车存取系统（Autonomous Vehicle Storage and Retrieval Systems，AVS/RS）（如图1所示[1]）的研究。自动小车存取系统可以极大地提高存取效率、满足多种复杂的存取需求，自动小车结构示意图如图2所示。它还可以避免传统堆垛机式自动化立体仓库高耦合的缺点，极大地提高存取系统的柔性。因此，对AVS/RS的研究有着非常重要的意义。

图1 自动小车存取系统的立体示意图

图2 自动小车结构示意图

当前，国内外关于AVS/RS的研究还处在起步阶段。已有的研究主要集中如何建立AVS/RS的性能评估模型、减少阻塞或死锁和AVS/RS的调度优化。Heragu等[2]先用开环排队网络（Open Queueing Network，OQN）对自动小车存取系统进行建模，然后用制造系统表现分析器（Manufacturing System Performance Analyzer，MPA）对一种AVS/RS配置进行了出入库效率分析。接着，他对多种配置的AVS/RS进行了类似的仿真研究。结果表明，当自动小车的利用率在60%到85%之间时，开环排队网络可以有效地对自动小车存取系统进行出入库效率分析。

Marchet等[3]同样用开环排队网络构建了基于平均完成指令时间和等待时间等指标的自动小车存取系统评估模型。他们综合了自动小车和升降机（Lift）的速度与加速度以及各种类型的货格参数等情况，通过仿真证实了该模型的有效性。罗建[4]和吴长庆[5]指出环路死锁是AVS/RS中死锁出现的主要类型。该团队运用着色赋时Petri网（Coloured Timed Petri Nets，CTPN）构建了自动小车存取系统的动态模型。他们基于CTPN模型，使用有向工具构建了防止环路死锁的路线图，给出了死锁释放的充分必要条件。文献[6]和文献[7]从储位分配优化的角度来提高自动小车存取系统的出入库效率。他们分别用离散粒子群算法、离散粒子群与模拟退火融合的算法建立了自动小车存取系统的货位优化模型，并用仿真的方法验证了该方法的有效性。程志江等[8,9]基于模糊控制理论，对智能小车的控制系统进行了研究。冯锋等[10]为了让自动小车适应不同场景的应用，设计了自组织模糊控制器来优化自动小车的控制。

2 问题的描述与建模

2.1 问题的描述

根据自动小车能否在升降机的协助下实现跨层作业，可将自动小车存取系统分为单层作业的自动小车存取系统和跨层作业的自动小车存取系统。为了更加体现问题的普遍性，本文选择自动小车可跨层且可在平面内做二维运动的的自动小车存取系统作为研究对象（在不作特殊说明的情况下，下文所述自动小车存取系统指的都是这种形式）。图3为自动小车存取系统水平剖面示意图。如图所示，网格线填充的矩形块表示的是标准货位，黑色填充矩形块表示的是可运输自动小车实现垂直运动的升降机，黑色填充的圆形块则表示该层的I/O点（输入或输出点）。自动小车可在空白的巷道自由运行，并可在升降机的协助下完成跨层运动。

图3 自动小车存取系统水平剖面示意图

自动小车存取系统共有3种作业方式，分别为：单指令出库方式，单指令入库方式和双指令出入库复合作业方式。单指令出库方式指的是AVS/RS在一段过程内只完成出库任务。单指令入库方式指的是AVS/RS在一段过程内只完成入库任务。而，复合作业方式下，一个作业过程要完成出库和入库两个任务，而每个任务都可能是跨层作业的。如图4所示，复合作业方式下出库货位和入库货位是逐一交替进行的。

图4 复合方式下的作业流程

复合作业方式可以有效地缩短自动小车和升降机的空载运行时间，因此可以大大提高整个系统的出入库效率[11]。本文接下来主要研究复合作业方式。

另外，自动小车在水平面选择不同的运动路径也会造成任务完成时间的不同。假设平面上有两个不重合的点，分别为点A和点B。理论上，A到B之间的路径有无数条。实际上有两类路径比较有代表性。如图5所示，一类是A到B之间的路径与经过A、B两点的直线重合，即路径2。路径2的经过的路程叫做点A与点B的欧氏距离。另一类，路径1和路径3则代表着躲避规则分布障碍的路径。容易证明，这类路径的路程都是相等的。这类路径所产生的距离可称为曼哈顿距离或出租车距离。在仓库的某一层内，自动小车需要在货位、升降机电梯和I/O间运动。而这三者往往不是沿水平或垂直分布的，即将他们之间的距离简单地认为是欧式距离是不合理的。即使只能沿水平和垂直分布的巷道运行，在确定的两点间，自动小车的运行路径也存在无数条。其中，曼哈顿距离是最短的。因此，本文在计算自动小车在水平运行的最短路程时都采用曼哈顿距离。

图5 两节点间的多种路径

此外，选择不同的任务完成顺序和在需要跨层作业时选择不同的升降机都会影响订单的完成总时间。本文调度优化的目标就是在复合作业方式下、自动小车水平运动按照曼哈顿距离运动的前提下，选择合适的任务完成顺序和在需要跨层作业时选择合适的升降机以使任务订单的完成时间最短。

2.2 系统建模

现对自动小车存取系统做如下假定：

1）自动小车可以逆向行驶，即自动小车的运行是双向的。

2）不考虑自动小车、升降机和货架等硬件设备的故障等不利因素，且不考虑货物的存取时间。

3）不考虑自动小车和升降机的加速和减速过程，即认为自动小车在水平方向上的运动和升降机在垂直方向上的运动都是匀速的。

4）系统中各层的I/O点（本文假设每层的I/O点有且只有一个）是等价的，即认为系统可借助任何一层的I/O点实现货物离开系统或进入系统的操作，且不考虑各层I/O点到系统底层的距离。

5）自动小车和升降机都是单负载的，即认为自动小车在一段时间内只能携带一个货物，升降机在一段时间只能携带一个自动小车。

6）系统中自动小车和升降机采取“上次完成位置处停靠” 的停靠策略，即自动小车和升降机完成任务后会停留在原地，不会主动去做空行程运动。

将单个复合作业过程（即，完成一次相邻出库操作和入库操作）分解为3个过程。

1）过程1：自动小车从当前位置（第一个复合作业过程时，自动小车的出发位置为I/O点。之后的复合作业过程中，自动小车的出发位置是上一个入库货位处。本文统一称之为上一个入库货位点）运行到出库货位处的过程。当上一次入库货位与当前复合作业过程中的出库货位在不同层时，系统的运行必须要用到升降机。否则，不需要升降机。

2）过程2：自动小车从出库货位运行到I/O点的过程。该过程不会涉及到升降机的调用。

3）过程3：自动小车从I/O点运行到入库货位处的过程。当自动小车当前所在的I/O点与入库货位不在同一层时，系统的运行必须要用到升降机。否则，不需要升降机。

假设当前有N个出库任务和N个入库任务，系统中有M个升降机。本文的研究侧重于调度的空间路径优化。因此，本文关于自动小车的数量设定与文献[12]相同，即认为系统中有且仅有一个自动小车。不同的任务完成顺序和在每一复合作业过程中选择不同的升降机，会产生不同的调度方案P，而这些调度方案所产生的时间效率往往是不同的。本文优化的目标是找到一个使订单完成总时间最短的作业方案。则，建立系统的数学模型如下：

其中，T(In→Out)n为第n个复合作业过程中过程1的自动小车耗时，T(Out→I/O)n为过程2的自动小车通过曼哈顿距离的耗时，T(Out→In)n为过程3的自动小车耗时。

当过程1中自动小车的运行需要借助于升降机时，自动小车的耗时如式(2)所示。

其中，TIn→Lift为过程1中，自动小车从上一次入库货位处运行到升降机电梯的耗时，TLiftwait,m为自动小车等待第m个升降机（m=1,2,3…M）的耗时，TLiftrun,m为自动小车乘坐该升降机的耗时。

当过程3中自动小车的运行需要借助于升降机时，自动小车的耗时如式(3)所示。

其中，TI/O→Lift为过程3中，自动小车从I/O点运行到升降机电梯的耗时，TLiftwait,s为自动小车等待第s个升降机（s=1,2,3…m）的耗时，TLiftrun,s为自动小车乘坐该升降机的耗时。

3 基于改进遗传算法的自动小车存取系统的调度优化

AVS/RS的调度优化问题可以用智能搜索算法求解。由于，遗传算法具有可并发处理和应用范围广泛等优点而被广泛应用于求解此类问题。而简单遗传算法又存在着收敛速度低和收敛精度差等缺点。因此，本文将使用改进的遗传算法来求解AVS/RS的调度优化问题。

3.1 编码与解码

符号编码是满足本文需求的最理想的编码方式。为了方便编程操作，编码的符号选用正整数。例如，第2个出库任务表示为2，第5个入库任务表示为5，升降机3表示3。将出库任务、入库任务和升降机的编码依次排列，则可得到染色体个体的基因型。将出库任务记为向量O，入库任务记为向量I，升降机组记为向量E，则染色体个体可表示为D=（O，I，E）。例如，某任务订单的完成顺序为A2→B2→A5→B4→A3→B1→A1→B3→A4→B5，且在5个复合作业过程中使用的电梯分别为（1，3）、（2，4）、（3，4）、（3，1）和（3，2），那么染色体个体可表示为：

假设，某任务订单中出库任务和入库任务的数量都为N，那么染色体的长度为4N。

可按照相同的原理进行解码操作。解码操作是编码操作的逆过程。例如，现有某染色体个体为：

则它表示的意义为：订单按照顺序A3→B1→A4→B2→A5→B3→A1→B5→A2→B4依次完成。在5个复合作业过程中使用的电梯分别为（3，1）、（4，1）、（2，3）、（2，1）和（2，4）。

3.1 编码与解码

这里采用传统的种群初始化方法。将染色体个体的第一部分（出库任务）、第二部分（入库任务）和第三部分（升降机组）记为Part1、Part2和Part3，并设种群规模为Popsize，且D为某个可行解的基因型，即染色体个体。

在接受康复护理前，2组患者的ADL评分、FMA评分均较低且对比差异无统计学意义（P＞0.05）；在康复护理后，观察组患者ADL评分、FMA评分结果均高于对照组，差异有统计学意义（P＜0.05）。 见表 1。

按照随机的方式分别产生基因片段Part1、Part2和Part3。拼接这三个部分，即可得一个染色体个体。如此重复Popsize次，即可得到规模为Popsize的初始化种群。

3.2 线性调整适应度值

这里的目标函数可根据上文的分析通过编写计算机程序求得，记为f(x)。为了使适应度值与任务完成时间成负相关，本文按照式(4)求适应度函数。

在遗传算法的前期，个体的适应度值往往相差较大。种群中评价特别优异的个体会得到过量的繁殖机会，容易造成早熟，即过早收敛。而，在遗传算法的后期，个体的适应度值则往往相差无几，算法的选择、交叉和变异过程几乎变成了随机过程。

为了避免以上两种情况的发生，本文采用动态的方法对适应度函数进行线性调整。将原适应度函数简记为f，调整后的适应度函数简记为f '。线性调整的表达式为：

其中，a和b为待确定的调整系数。

将种群的最大和最小适应度值分别记为fmax和fmin，平均适应度值记为favg。另外，引入复制期望参数c。一般情况下，c的取值在1.3到1.9之间。

则，调整后的适应度函数为：

则，调整后的适应度函数为：

3.3 基于混合方法的选择策略

本文采用轮盘赌法选择方式和精英个体保留法相结合的方式进行选择。该方式既可以提高优秀个体参与繁殖的机会，又可以保护优秀个体，使其不受破坏。则，遗传算法可以有效率地提高收敛速度。

具体操作过程如下：

Step1：计算个体被选中的概率。

种群中个体i被选中的概率可用式(12)表示。

其中，POPsize为种群的规模，f '(i)为个体的经过线性优化后的适应度函数。

Step2：生成一个零到适应度总和之间的随机数。

先随机生成一个0到1之间的实数w0，则待求的随机数w可表示如下：

Step3：找出满足条件的单个个体进入交叉和变异操作。

找出唯一同时满足式(14)和式(15)的个体j。

Step4：选择M个个体进入交叉和变异操作。

这里的M也是一个由概率产生的正整数。设定种群中参与到交叉和变异的概率为p，p一般为0.8到1之间的实数。M可以按照式(16)确定。

即，POPsize与p的乘积取整，可得M。

重复M次Step2到Step3的操作，则可得到M个参与交叉和变异的个体。

Step5：保留（POPsize-M）个个体。

先记录下（POPsize-M）个适应度值较高的个体。然后，将该（POPsize-M）个个体的适应度值逐一与经过交叉和变异操作的个体的适应度进行比较。如果，该（POPsize-M）个个体中的某个个体的适应度值高于M个经过交叉和变异的个体的适应度值，则用该个体替换种群中适应度最低的个体。被替换的个体数在0到（POPsize-M）之间。

3.4 交叉算子和变异算子的设计

1）交叉算子

本文将个体的编码分为三个部分，分别为出库货位排列Part1，入库货位排序Part2和升降机组Part3。其中，交叉算子必须使Part1和Part2在交叉操作后保持不重复、不遗漏。也就说，Part1和Part2在交叉以后，仍然是一个严格的新的排列。则本文针对Part1和Part2部分分别使用位置基础交叉法。而Part3的各基因片段之间并没有绝对的逻辑关系。因此，可以选择简单交叉法。

例如，D1和D2为两个未经交叉操作的染色体个体，如下：

Step1：在染色体个体D1的Part1部分随机抽取若干个基因位，将这些位置上的基因作为新个体D1'中Part1部分对应位置的基因。去掉染色体个体D2中Part1部分对应位置的基因，并将D2中Part1部分剩下的基因依次填到D1'的Part1部分剩下的基因位。

Step2：随机抽取个体D1中Part2部分的若干个基因位，将这些基因逐一复制到新个体D1'中Part2部分的对应位置。去掉染色体个体D2中Part2部分与个体D1中Part2被抽取到的相同基因，将D2中Part2部分剩下的基因依次填到D1'的Part2部分剩下的基因位。

Setp3：随机抽取个体D1中Part3部分的若干个基因位。在个体D2中Part3部分选取相同的基因位。将个体D1中Part3部分被抽取到的若干个基因位替换为个体D2中Part3部分所选取的对应位置的相同基因，则可得到新个体D1'中Part3部分。

算法经过Step1到Step3的操作，可以得到新的个体D1'。进行类似的操作以后可以得到新的个体D2'，新的个体D1'和D2'如下：

2） 变异算子

同样地，变异操作也要按照三个部分分别进行变异操作。这三个部分都可以使用移位变异法进行变异操作。

以原染色体个体D为例。其中D为：

则，对原染色体个体D中的三个部分分别使用移位变异法，可得到新的染色体D'为：

3.5 基于改进遗传算法的AVS/RS调度优化的执行步骤

基于AVS/RS自身的特点，结合本文提出的改进遗传算法，可将算法过程描述如下：

步骤1：符号式编码 本文选择符号式编码的方式编码；

步骤2：种群初始化；

步骤3：求适应度值并做线性调整 本文通过取目标函数的倒数的方法获得适应度函数，进而求得适应度值，并根据适应度值分布情况做线性调整；

步骤4：判断是否满足终止条件 如果满足终止条件，则输出可能的最优解或次优解，并对应于符号式编码进行解码得到表现型。如果不满足终止条件，则重复步骤5到步骤6；

步骤5：基于混合方式的选择操作 本文设计并采用轮盘赌法和精英个体保留法相结合的选择策略进行选择操作；

步骤6：交叉操作和变异操作。

4 实验及结果分析

4.1 实验参数

本文已经建立了自动小车存取系统的数学模型、分析了自动小车存取系统的调度内容并提出了一种改进的遗传算法以实现调度优化。为了研究优化方案的可行性，需要设计合理实验以进行仿真比较。

现对AVS/RS的各项参数做如下设定。系统包含升降机个数M=4；货架的层数T=20；巷道单侧的货位数C=11；仓储水平方向上的巷道数A=2；货位的宽度μw=1m；货位的高度μh=0.6m；货位深度为μd=0.5m；μA=0.5m；自动小车在水平X方向上的运动速度vx=1.8m/s，在水平Y方向上的运动速度vy=1.8m/s；升降机在垂直方向上的速度为2m/s。

随机生成10个出入库任务。其中，5个出库货位分别为（4，7，20）、（6，11，5）、（7，9，17）、（2，5，11）和（3，7，5），5个入库货位分别为（3，9，11）、（8，7，17）、（3，7，19）、（5，11，13）和（9，6，17）。结合系统的各项参数，可得5个出库货位和5个入库货位的自动小车映射位置的水平坐标分别如表1和表2所示。

表1 出库货位映射坐标

表2 入库货位映射坐标

4.2 实验结果分析

为了验证本文提出的改进遗传算法IGA在解决自动小车存取系统调度优化方面的优越性，本文将改进遗传算法IGA与基本遗传算法GA和离散粒子群算法PSO进行对比分析。设置这三个算法的种群规模Popsize同为30，最大迭代次数MAX_GEN为1000。IGA对适应度值做线性调整，采用混合选择策略，并采用线性下降的交叉和变异概率。GA采用简单轮盘赌选择策略，并保持交叉率和变异不变，其中Pc=0.9，Pm=0.2。PSO的学习因子设置为C1=1，C2=1，惯性权重设置为从0.8曲线下降到0.3。这三种算法分别独立运行20次，取最短订单完成时间，即目标函数的最优结果为最终的优化结果。三种算法最终优化结果的迭代趋势如图6所示。

图6 三种算法收敛过程对比图

由改进遗传算法求得的最优个体为[4 1 2 5 3丨1 4 2 5 3丨3 4 4 2 2 2 1 1 2 4]。解码得，最优完成顺序为（2，5，11）→（3，9，11）→（4，7，20）→（5，11，13）→（6，11，5）→（8，7，17）→（3，7，5）→（9，6，17）→（7，9，17）→（3，7，19）。其中第1个复合作业组使用升降机3和升降机4，第2个复合作业组使用升降机4和升降机2，第3个复合作业组使用两次升降机2，第4个复合作业组使用两次升降机1，第5个复合作业过程使用升降机3和升降机4。

由图5可知，相比于简单遗传算法和离散粒子群算法，本文提出的改进遗传算法具有更快的收敛速度和较好的收敛精度。证明了IGA是快速和较精确解决自动小车存取系统调度优化的方法。

5 结束语

本文以自动小车可跨层作业的AVS/RS的调度优化作为研究目标。分析了AVS/RS在复合作业方式下的出入库工作流程，建立了AVS/RS调度优化的数学模型。提出了一种根据现有分布线性调整适应度值，和以轮盘赌法和精英个体保留法相结合的混合选择策略的改进遗传算法。最后，通过一组实验证明了该算法在解决AVS/RS的调度优化求解时是有效的。未来可以将神经网络等人工智能算法引入到AVS/RS的调度优化求解中。

[1]Fukunari M,Malmborg C J. A network queuing approach for evaluation of performance measures in autonomous vehicle storage and retrieval systems[J].European Journal of Operational Research,2009,193(1):152-167.

[2]Heragu S S,Cai X, Krishnamurthy A,et al.Analysis of autonomous vehicle storage and retrieval system by open queueing network[A].IEEE International Conference on Automation Science and Engineering. IEEE[C],2009:455-459.

[3]Gino Marchet, Marco Melacini, Sara Perotti, et al. Analytical model to estimate performances of autonomous vehicle storage and retrieval systems for product totes[J].International Journal of Production Research,2012,50(24):7134-7148.

[4]Luo J. Deadlock control of autonomous vehicle storage and retrieval systems via coloured timed Petri nets and digraph tools[J].International Journal of Production Research,2009,47(12):3253-3263.

[5]Chang-Qing W U, Shan-Jun H E, Luo J.Cycle-deadlock control of RGVs in autonomous vehicle storage and retrieval systems[J].Computer Integrated Manufacturing Systems,2008,14(9):1766-1773.

[6]罗键,钟寿桂,吴长庆.基于离散粒子群算法的AVS/RS货位优化[J].厦门大学学报(自然版),2009,48(2):212-215.

[7]钟寿桂.基于离散粒子群与模拟退火融合算法的自动小车存取系统货位优化[D].厦门大学,2009.

[8]程志江,李剑波.基于模糊控制的智能小车控制系统开发[J].计算机应用,2008,28(s2):350-353.

[9]程志江,李剑波.基于遗传算法的智能小车模糊控制系统的研发[J].自动化仪表,2009,30(8):4-7.

[10]冯锋,邓志良,赵旭.AGV自动导航小车自组织模糊控制器研究[J].微计算机信息,2008,24(10):84-86.

[11]乔岩,钱晓明,楼佩煌.基于改进时间窗的AGVs避碰路径规划[J].计算机集成制造系统,2012,18(12):2683-2688.

[12]罗键,苏海墩,何善君,等.基于改进遗传算法的自动小车存取系统升降机调度建模与优化控制[J].厦门大学学报(自然版),2010,49(3):328-332.