基于蚁群-改进遗传算法的双工位堆垛机存取路径优化研究

王长辉

（江苏大学汽车与交通工程学院，江苏 镇江 212000）

自动化立体仓库主要由计算机控制系统、堆垛机、货架、出入库站台组成，由计算机控制系统发出指令控制堆垛机在巷道内来回运动，进行出入库作业[1]。传统的堆垛机主要是单工位的，一次入库或出库作业只能承载一个货物单元，作业效率不高；而双工位堆垛机一次入库作业或出库作业可以承载两个货物单元，提高仓库周转率[2]。如何提高货物的出入库作业效率是很多学者研究的重要内容，堆垛机的作业路径是否合理对出入库的效率有很大的影响。文献[3]采用优化算法对建立的堆垛机进行出入库作业的数学模型求解，得到了最短路；文献[4]利用启发式算法对货物出入库作业时间模型进行求解；文献[5-9]采用遗传算法对货物出入库路径优化进行研究，但是考虑的因素单一，模型相对简单；文献[10]通过分析立体仓库中堆垛机的工作特点与运行情况，提出了基于混合蚁群粒子群算法的路径优化方法；文献[11]建立了堆垛机在单周期和双周期下作业时最短行程时间数学模型，利用遗传蚁群算法对堆垛机的数学作业模型进行了分析和求解；文献[12]采用了改进的遗传算法求解堆垛机作业路径优化问题；文献[13-15]对堆垛机作业的路径选择和存储策略分析，提出优化路径的搜索方法。综上所述，针对堆垛机作业路径优化的问题，目前研究重点集中在两个方面：路径优化数学模型和求解方法。但是大部分路径优化数学模型没有考虑堆垛机启动和制动的时间，由于货叉上的货物本身具有惯性，堆垛机的加速与制动不宜过大，因此堆垛机的加速与制动时间不会很小，而且在多次出入库作业累加后，加速与制动时间总和将变得很大。因此忽略不计堆垛机的启动与制动时间，将对模型的精确计算产生误差，从而影响双工位仓库的自动化精度；目前常用的求解方法是智能寻优算法，但是大部分智能寻优算法存在容易陷入局部最优和搜索效率低的缺陷；另外大部分学者都是选择单工位堆垛机进行研究，单工位堆垛机存取量小、存取效率也不高。

为此，该文的研究对象是双工位堆垛机进行出入库作业时的最优路径，在考虑了加速与制动对货物稳定影响的基础上，提出了一个变加速度的双工位堆垛机运行方法，提出自动存取路径数学模型以及蚁群-改进遗传算法处理多任务的存取路径优化的问题，实现提高货物存取效率的目的。

1 双工位堆垛机运行方法分析与改进

传统堆垛机运行方法如图1所示。其水平速度vx与竖直速度vy均为固定值，但这种方法对于货物位置较远、存取路径较长的作业，速度固定就显得效率很低。

图1 传统堆垛机运行速度示意图

将固定的水平与竖直速度改为水平、垂直速度随角度θ变化；双工位堆垛机出入库作业运行速度改进方案如图2所示，这里的角度θ由初始位置与目标位置决定，货位的长度和高度分别为L和H。

图2 双工位堆垛机运行速度改进图

假设货物的初始位置O为（0，0），沿直线OD的速度v采用变加速度的方法（如图3），在保证货叉上货物稳定的前提下，实现双工位堆垛机出入库复合作业一个环节运行时间的优化。

图3 双工位堆垛机运行变加速度示意图

如图3所示，双工位堆垛机的速度v随时间t变化的数学模型为：

式中，r为数学模型中的二次项系数，且r>0，tD为到达目标位置D（i，j）的时间，且 0＜t＜tD。进一步求导，可得到加速度a的数学表达式为：

但是，如何保证货叉上的货物在沿直线OD作变加速度运行过程中始终保持稳定平衡，是实现堆垛机出入库运行时间优化的一个重要问题。假如堆垛机上的货物受力平衡，如图4所示。

则货物由于惯性受到货叉的水平推力应小于最大静摩擦力fmax，直线OD与水平面的夹角θ是有方向的，其范围为[-π/2，π/2]。则由图4可知，货物相对于货叉始终保持静止的关系可表示为：

图4 加速时货物平衡稳定的受力图

进一步推导可得：

μ为摩擦系数，F2为变加速度运动的反作用力，任意F2都必须满足上述公式，则F2的最大值也必须满足，将F2的最大值代入不等式，化简得到：

根据公式（6）可知，除了垂直上升之外，tD与两个货物之间的距离没有关系，只与两个货位与水平面的角度有关。

双工位堆垛机在多任务存取情况下，假设先不考虑θ=π/2的情况，由公式（6）求导可得：

由于-π/2≤θ＜arctan（1/μ），因此cosθ-μsinθ>0。设 g（θ）=sinθ+μcosθ，则其导数为g′（θ）=cosθμsinθ>0 ，则 g（θ）单调递增。因此当 g（θ）>0 时，即-arctanμ＜θ＜arctan（1/μ）时 ，tD（θ）单调递增；当g（θ）＜0 时，即 -π/2＜θ＜-arctanμ ，则 tD（θ）单调递减，如图5所示。在该文中，设置参数 μ=0.05，从货位位置来看，tanθ=-0.05就相当于水平移动，即θ=0。因此当-π/2≤θ＜0时，时间函数 tD（θ）单调递增；当 0＜θ＜arctan（1/μ）时，时间函数 tD（θ）单调递减。由上述分析可知，双工位堆垛机作业时间与角度的绝对值成反比。

图5 双工位堆垛机运行时间函数变化图

2 双工位堆垛机自动存取路径数学模型

采取复合作业存取方式，双工位堆垛机一次复合作业分别访问2个存货货位和2个取货货位，最后回到初始位置O的方式。设出入库初始位置为O（0，0），货位对应的坐标为D（y，z），其中y表示货位所在的列，z表示货位所在的层。

为了方便构建出改进的自动存取路径数学模型，假设出库任务与入库任务数量相同，且任务数量都为偶数。在双工位堆垛机出入库复合作业中，设入库任务有2N个，分别表示为（P1，P2，…，P2N），对应的坐标为 （yp1，zp1），（yp2，zp2），… ，（yp2N，zp2N）；同样，出库任务有2N个，分别表示为（Q1，Q2，…，Q2N），对应的坐标为 （yq1，zq1），（yq2，zq2），… ，（yq2N，zq2N）。在一个出入库行程周期中，两个入库任务（P2k-1，P2k）与两个出库任务 （Q2k-1，Q2k）进行匹配，其中 k=1，2，…，N。根据第一步先存货、货叉上货物不超过两个的原则，则有存存取取、存取存取两种情况，以存存取取为例，如图6所示，总共有OP2k-1P2kQ2k-1Q2kO、OP2k-1P2kQ2kQ2k-1O、OP2kP2k-1Q2k-1Q2kO、OP2kP2k-1Q2kQ2k-1O 4种组合情况。

图6 双工位堆垛机复合作业中“存存取取”可能的路径组合图

完成一次复合作业的过程中其中一个可能路径OP2k-1P2kQ2k-1Q2kO需要的总时间为：

3 蚁群-改进遗传算法的设计

3.1 蚁群算法

假设t时刻，蚂蚁k由一端点i转移到另一端点j的概率为[16]：

式中，τij（t）表示蚂蚁经过路径（i，j）后的信息残留量，nij（t）为启发信息量，α与β表示特定的影响力因素，allowedk表示定位蚂蚁k下一步运动中被允许选择的剩余货位集合。经过n个时刻后，路径（i，j）上的信息素调整公式为：

式中，ρ为信息量的保留度，Δτijk为一次循环中第k只蚂蚁在路径（i，j）上留下的信息量，Δτij表示蚂蚁群在一次循环中留下的信息量，m表示蚂蚁的数量。

3.2 蚁群-改进遗传算法

利用蚁群算法生成优异初始种群，优化改进遗传算法对双工位堆垛机作业路径进行寻优。由蚁群算法优化初始种群，由改进遗传算法优化选择算子、交叉算子与交叉策略，提高了优秀基因快速占据统治地位的效率，减少或避免了不合法的染色体的出现。利用蚁群-改进遗传算法求解双工位堆垛机作业路径优化问题的具体步骤为：

1）编码

采用顺序编码的方法，每一个货位都进行编码，且顺序不允许重复。设入库任务序列为P={1，2，3，4，5，6，7，8}，出库任务序列为Q={3，8，1，5，7，6，2，4}，假设复合作业采取“存存取取”的方式，则2个入库与2个出库配对，则第一个周期为W1={P1，Q1}={（1，2），（3，8）}，第二个周期为W2={P2，Q2}={（3，4），（1，5）}，第三个周期为 W3={P3，Q3}={（5，6），（7，6）}，第四个周期为W4={P4，Q4}={（7，8），（2，4）}。

2）适应度函数确定

目标函数为时间函数，优化的问题是求解时间函数的最小值，目标函数与适应度函数值成反比关系，因此将适应度函数设置为目标函数的倒数：

式中，Ffitness为个体的适应度函数，FT为双工位堆垛机存取过程中一个可能路径的时间函数，具体函数详见公式（6）与（8），tanθ＜12.5＜1/μ，因此设静摩擦系数 μ=0.05，二次项系数r=0.25，重力常数g=10 N/kg。

3）产生初始种群

利用蚁群算法产生较优异的初始种群，步骤如下：

步骤1：初始化参数。设置初始循环次数为N=0 ，设置最大循环次数为 Nmax，路径（i，j）的初始化信息量为τij=const，设置初始时刻的信息量为0，同时将m只蚂蚁随机放在n个位置上；

步骤2：设置循环次数满足N=N+1，同时设置蚂蚁禁忌表索引号为k=1；

步骤3：k=k+1；

步骤4：利用状态转移概率公式（9）得到蚂蚁k爬到位置j的概率值；

步骤5：根据步骤4计算得到的状态转移概率值，将蚂蚁移动到具有最大状态转移概率的位置上，同时把该位置信息存储到禁忌表中。

步骤6：若没有访问完集合Wi中的所有位置，即k＜m，跳转至步骤3；否则转步骤7；

步骤7：根据公式（10）更新每条路径上的信息量；

步骤8：若满足结束条件，则循环结束，并输出计算结果；否则清空禁忌表并跳转到步骤3。

4）改进选择操作

使用两种选择算子，以使适应度高的基因更快速占据统治地位，假设种群大小为M，个体的适应度值为Fi，若第一种算子采用比例选择算子，采用轮盘赌模型对种群做出选择。比例选择算子的选择概率为：

step1随机抽取一个在[0，1]之间的数s，再随机抽取一个在[0，1]区间的概率p，若 p≤0.5，则进入step2，若 p>0.5 ，则进入step3；

step2 如果 s≤p1+p2+...+pi，则选择个体 s，否则不选择；

5）改进交叉操作

改进交叉算子采用的是部分映射交叉算子，首先对由多个个体所组成的群体进行两两随机配对。设群体的大小为M，则共有[M/2]个配对组，其中y=[x]为高斯取整函数。首先，将配对的两个个体中的两列基因随机交叉，同时确定基因之间的映射关系，然后利用映射关系合法化两个个体的后代，如图7所示。

图7 改进交叉算子进行基因交叉操作

6）变异操作

在个体的基因列上随机互换两个基因点的位置，从而进行变异操作。例如，随机变异操作将个体的第2个基因与第6个基因位置互换，结果如图8所示。

图8 变异操作过程图

7）算法停止准则

设置算法遗传代数在200代后停止。

4 数值实验结果与分析

采取的实验方案：随机选择自动化仓库的一排货架，其中，这一排货架有10层12列，一共120个货位，每个货位的规格为长L=2m，高H=2.5m，双工位堆垛机的运行速度改进方法如上文所述，其中二次项系数取r=0.25。利用蚁群-改进遗传算法求解双工位堆垛机自动化存取路径优化问题，同时设置算法的主要参数如下：α=1，β=5，ρ=0.5，Nmax=1 000，遗传种群迭代次数为200代，交叉概率为0.9，变异概率为0.05，选取8个入库任务与8个出库任务进行仿真实验。另外，在研究路径优化过程中，忽略双工位堆垛机货叉存取货物的时间。

1）确认实验存取货位坐标位置

根据路径自动化存取原则，为了简便分析，按照复合作业“存存取取”方式进行分析；已知8个存货货位的坐标为 P={P1，P2，P3，P4，P5，P6，P7，P8}={（4，8），（7，6），（5，2），（12，4），（3，5），（9，10），（10，2），（1，7）}，同时 8个取货货位的坐标为 Q={Q1，Q2，Q3，Q4，Q5，Q6，Q7，Q8}={（9，5），（3，6），（7，2），（1，4），（10，9），（5，7），（1，9），（12，3）}，存取货位的位置如图9所示。

2）Matlab仿真优化双工位存取路径

利用提出的算法，结合改进的自动化复合作业的“存存取取”时间模型，在给定双工位自动化立体仓库的相关数据信息基础上，对双工位堆垛机的存取路径进行仿真优化。其中，将蚁群-改进遗传算法进行路径优化的结果与基本遗传算法的优化结果进行对比，两者的迭代曲线对比图如图10所示。由图可知，在两种算法的优化下，双工位堆垛机路径优化的时间目标函数值都随着迭代次数增加而不断减小；当遗传算法的种群迭代到42代左右接近最优解，但是还未达到平稳状态，在迭代至80代，达到最优解。相比于提出的算法，遗传算法的种群在迭代到42代后的最优解只达到了局部最优解，而提出的算法则迭代到18代后就达到最优解。因此，通过仿真验证，蚁群-改进遗传算法相比于基本遗传算法不仅提高了迭代效率，且提升了最优解的准确率。

图9 货物入库出库任务分布图

图10 遗传算法与蚁群-改进遗传算法的仿真结果对比图

路径优化前，可能采用随机组合的方式，优化前堆垛机多任务存取路径分布如图11所示。有很多路径很杂乱，导致有很多角度很小的运行路径，需要的运行时间更长。路径优化后的堆垛机多任务存取路径组合图如图12所示，与优化前组合图作对比，发现优化后的路径组合图路径角度明显比优化前大。根据该文改进的模型，除了角度θ=π/2时，路径时间函数只与两个货物之间的角度有关，与经过的路径大小没有关系。优化后的路径组合明显比优化前的用时少，可以明显地看出每个周期路径缩短，相对应地完成任务所需时间也减少，进而提高仓库运转效率。

5 结束语

传统双工位堆垛机采用的固定运行速度策略，忽略了影响货物稳定的加速与制动，且运行效率低下。针对上述问题，提出一种基于变加速度的双工位堆垛机出入库复合作业存取路径的运行方法；该方法考虑了加速与制动对货物稳定的影响问题，在保证堆垛机货叉上货物稳定的同时，极大地提高了双工位堆垛机路径的运行效率。另外，针对传统遗传算法对路径优化研究的问题，提出一种基于蚁群-改进遗传算法对双工位复合作业路径寻优的方法，提高了双工位堆垛机复合作业路径优化的效率与准确率。该方法采用蚁群算法生成遗传算法的优异初始种群，并通过改进遗传算法对双工位自动存取路径进行寻优。结果表明，相比于传统遗传算法，蚁群-改进遗传算法可以更快、更准确地实现双工位复合作业路径的寻优。

图11 优化前“存存取取”路径组合图

图12 优化后“存存取取”路径组合图