一种多巷道立体仓库货位分配优化方法

陈港生，谢家翔，付建林，丁国富

（西南交通大学 机械工程学院，成都 610031）

0 引言

随着计算技术、人工智能等的快速发展，制造业公司的竞争也日益加剧，同时公司内对先进生产技术的需求也越来越迫切。在“德国工业4.0”的驱动下，传统的生产制造业正不断地向智慧生产过渡，而发展建设智能仓储是“工业4.0”的三大主题之一，也是“中国制造2025”的关键内涵[1]。立体仓库作为现代智能物流重要部分，合理优化立体仓库货物货位可以有效缩短堆垛机工作时间、提高工作效率、降低企业生产物流成本。

对于立体仓库货位分配问题，许多国内外学者进行了较为深入的研究，遗传算法、粒子群算法等启发式算法被大量运用于货位分配问题求解，优化目标常集中于产品出入库效率、货架稳定性、产品之间的聚集程度等。黄鹏等[2]面对大规模立体仓库货位分配问题，提出了一种两阶段混合算法，引入贪婪交叉算子，通过实验证明了算法的优越性；蔡安江[3]等关于双向式立体仓库货位分配问题，给出了一种改进混合蛙跳算法；焦玉玲等[4]以产品出入库效率、仓库货架稳定性和产品集中程度，设计了一种多种群遗传算法来提高标准遗传算法提前收敛问题，由于该问题面对的是立体仓库单一巷道内货位分配问题，因此本文在此基础上，把立体仓库货位分配问题推广至多巷道；Xie等[5]针对分组条件下的货位分配问题，设计了一个双层分组优化模型，针对该模型提出了一种多阶段随机搜索方法和禁忌搜索算法；Tu等[6]针对考虑补货时间约束以及工作负载均衡的货位分配问题，提出了一种具有随机系数的启发式多目标遗传算法；Bessenouci等[7]以作业时间为优化目标，运用模拟退火算法和禁忌搜索算法的混合算法解决了货位分配的动态调整问题，并对混合算法的实验参数进行了敏感性实验；Li等[8]以产品出入库效率、货架稳定性为优化目标，提出了一种新型帕累托遗传算法，得到了比较满意的结果。

不难看出，在研究货位分配问题时，大多数研究者都以仓库货架稳定性、产品出入库效率以及产品之间的集中程度为优化目标，研究重心在仓库某一排货架上的货位分配问题，而忽略了货物分巷道存放导致最终分配的结果使得堆垛机作业量大、巷道拥堵、作业效率低下等问题。为此，本文考虑到多巷道货位分配问题中的堆垛机负载均衡原则，构建了立体仓库多排货架货位分配多目标优化模型，并根据遗传算法存在的局部搜寻能力差、提前收敛等缺陷，给出了含进化逆转的自适应多种群遗传算法；最后仿真实验结果表明，相比于标准遗传算法，该算法寻优速度更快、分配结果更加合理，能够很好地解决立体仓库货位分配问题。

1 模型建立

1.1 问题描述及模型假设

多巷道自动化立体仓库主要由多排高层货架、堆垛机械、出入库台和周边运输设备（如传送带、AGV等）组成。为提高仓库的管理效率，一方面可以优化立体仓库布局，另一方面可以考虑优化立体仓库货位分配，但在企业中立体仓库的布局往往是已经提前设置好了，想要更改变得较为困难，因此对立体仓库内货物的货位进行优化是一种提高仓库作业效率、降低堆垛机运行作业成本的有效方法。本文以某企业小型零部件立体仓库为研究对象，综合考虑货物的出入库效率、货架整体稳定性、堆垛机负载均衡原则。在此立体仓库中，每巷道内都有一个堆垛机承担着巷道内左右两排货架上货物的存放，仓库布局如图1所示。

图1 立体仓库布局简图

针对立体仓库货位分配遇到的相关问题和应遵循的原则，为了方便建立数学模型和研究问题，现对立体仓库做出如下假设：

1）假设某仓库总共有a排、b层、c列货架。所有货位长、宽、高尺寸相等均为L。

2）货物存放在托盘中，每个货位只能存放一个托盘。

3）堆垛机的运行速度恒定，用Vy、Vz表示堆垛机在水平和垂直方向上的运行速度。

4）只考虑货物质量，不考虑货架质量。

1.2 建立货位分配多目标优化模型

用（x，y，z）表示货物在货架中分配的货位位置信息，其中，x为货物所在货架排数，y为该排货架所对应的列数，z为该排货架对应的层数，它们决定着货位分配的最终结果；用Pk表示入库订单中第k个货物的周转率，Mk表示入库订单中第k个货物的质量，它们是货物分配优化的输入参数；N表示一批入库订单中待入库货物总数；引入决策变量Skxyz用来判断第k个货物是否存放在（x，y，z）货位中，若是则为1，否则为0。

1）建立以出入库效率最高为目标的函数F1。

为满足立体仓库快速响应出入库需求，要求将出入库频率高的货物放在靠近出入口位置，从而缩短堆垛机的工作时间，提高系统运行效率，即堆垛机完成某一货物的作业时间与该货物的出入库频率的乘积最小，则构建目标函数为

2）建立以货架稳定性为原则的目标函数F2。

为了保证仓库内货架的安全性，货架上货物的存放因满足“下重上轻”原则，避免货架因重心失衡而造成倾倒。大多学者都以货物的质量与其所在层数的乘积之和最小为优化目标，但针对的是仓库某一巷道内堆垛机负责的两排货架的稳定性，并未考虑当立体仓库存在多台堆垛机同时工作时该仓库内所有货架的整体稳定性。因此，本文设计了考虑立体仓库内多台堆垛机同时工作时所有货架整体等效重心最小的目标函数式为

3）建立堆垛机负载均衡的目标函数F3。

为了降低堆垛机的负载，同时提升仓库的作业效率，因此要求均衡各个巷道内货物的出入库量，将一批入库订单中的货物分散地放在不同巷道内的货架上，以防止货物在某个巷道内大量堆积，而造成整个巷道堵塞，从而降低了堆垛机的作业效率，不利于仓库运作。建立的函数表达式如式（3）～式（6）所示：

式中：Ox表示第x排货架上存放的货物周转率之和，Qi表示第i个巷道内存放货物的周转率之和，表示一批订单中所有货物的周转率的平均值，ni表示每个巷道内分配的货位数。

可以看出该目标函数式以堆垛机作业的每个巷道为对象，考虑了每个巷道内出入库频率均衡和该巷道内货物的数量均衡，能很好地反映每个巷道内堆垛机的负载情况。

由于此优化问题是多目标优化问题，因此为了方便计算，需要将多目标函数转化为单目标函数，并根据仓库的实际情况确定相关系数。

2 算法设计

遗传算法（Genetic Algorithm,GA）是通过仿造自然科学界中的“物竞天择，适者生存”的发展规则，从随机得到的一组候选解出发，经过染色体的选择、交叉、变异，从而产生性能更为优良的下一代群体，通过不断地循环迭代搜索，最终寻找到最优解[9-10]。遗传算法全局搜寻能力很强，而局部搜寻能力薄弱。因此，本文提出了一种自适应多种群遗传算法（Adaptive Multi-population Genetic Algorithm,以下简称AMPGA）以改善传统的遗传算法，同时，引入进化逆转算子提高其局部搜寻能力。

2.1 算法流程

AMPGA则是在GA的基础上，增加了自适应选择、交叉算子以及进化逆转算子，并将之推广到了各个种群群体中，各个群体在进化的过程中不断地完成个体迁移。为了确保各群体的最优个体不被破坏和损失，通过人工选择算子筛选出各代种群中的最优个体放入精英种群中加以保存。AMPGA的算法结构示意图如图2所示。

图2 AMPGA算法流程图

2.2 算法实现

1）编码。在本文研究问题中采用十进制编码，每个自然数代表一个货位。将随机产生的自然数进行编号，然后用编号的先后顺序代表任务订单所分配的货位位置。以立体仓库第一排7×6的货架为例，如图3所示，如数字16代表分配货位坐标为（1，2，3），即分配位置为第一排、第二列、第三层货架。

图3 货位分配示意图

2）产生初始种群。根据仓库可用货位n，随机生成1～n的自然数序列代表一个个体的货位分配结果，按照此方法，产生R个种群，每个种群包含P个个体。

3）计算适应度值。根据一批入库订单总数N，取每个个体中前N个自然数代表分配的N个货位，根据分配的货位计算相应的目标函数值，适应度函数Ffit=1/(1+F)，其中Ffit是每个个体的适应度值，F为多目标优化函数化为单目标函数后的值。

4）选择。为保证上一代最优个体能顺利保存下来，按照个体的适应度值大小来进行优胜劣汰操作，采用轮盘赌选择和精英保留策略。

5）交叉。Srinvas等[11]提出了一种线性自适应遗传算法（Adaptive Genetic Algorithm,以下简称AGA）,将个体的交叉率和变异率随个体的适应度值进行线性调整，得到了比较好的收敛效果。但是，该方法在演化初期时存在停滞的缺陷，这不利于算法的迭代优化，容易导致算法陷入局部最优，提前收敛。石山等[12]通过对AGA的调整，将交叉率和变异率以余弦方式进行自适应调整，有效地避免了AGA存在的问题，构造的算子为：

式中：fmax表示种群中最大适应度值，favg表示该种群平均适应度值，Pcmax和Pcmin分别为交叉率的上限和下限，f′表示要交叉的两个个体中较大的适应度值，Pmmax和Pmmin分别为变异率的上限和下限，f表示要变异个体的适应度值。

本文使用余弦改进型自适应遗传算子，并将其运用到多个种群中。目前常用的交叉方式有单点交叉、两点交叉和顺序交叉，为了体现种群的多样性，本文将3种交叉方式同时用于多个种群中，每个种群随机选择一种交叉方式进行交叉。交叉的具体过程如图4所示。

图4 常见的3种交叉方式

6）变异。为防止非法解的产生，目前普遍采用的变异方法为两点位置互换变异，即在要变异的个体上随机产生两个突变的位点，使其基因位点顺序对调。

7）进化逆转。为继续提升遗传算法的局部搜寻能力，在完成变异后引入进化逆转，即在个体染色体上随机产生两个位点，将两点区间内的顺序倒置。与变异不同的是，变异是随机的，而这里的“进化逆转”是单方向性的，只有逆转后个体适应度值有提升才有效被接受，否则逆转无效不被接受。

8）个体迁移。个体迁移机制具体步骤如下：

Step 1：对种群个体适应度值按照从优到劣进行排序。

Step 2：设i=1。

Step 3：用第i个种群中的最优个体取代第i+1个种群中的最劣个体。

Step 4：令i=i+1。判断i是否等于种群数，如果是则转Step 5，否则转Step 3。

Step 5：将最后一个种群的最优个体取代第一个种群的最劣个体。

9）算法终止条件。将人工选择的最优个体放入精英种群。算法终止条件采用双重收敛判据，即达到最大迭代次数或者精英种群中最优个体保持代数时算法终止。

3 仿真实验

3.1 实验参数设定

以某企业小型零部件立体仓库为研究对象，来验证所建模型的有效性和算法的优越性。该仓库共有6排货架，每排货架有6层、每层10列，共有6×6×10=360个货位。根据层次分析法以及综合考虑立体仓库的实际情况，将目标函数1至目标函数3的权重分别设置为：ω1=0.375、ω2=0.372、ω3=0.253, 堆垛机水平速度Vx=2.5 m/s,垂直速度Vy=1.5 m/s,货架长L=1m,宽W=1 m，高H=1 m。本文选用SGA和未含进化逆转算子以及自适应选择、交叉算子的MPGA和含进化逆转算子和自适应选择、交叉算子的AMPGA进行实验。SGA、MPGA和AMPGA算法的实验参数设置如表1所示。

表1 3种算法实验参数设定

3.2 实验结果及分析

根据该企业入库订单中50个待入库货物样本数据，分别采用上述3种算法进行仿真实验，表2是3种算法的实验结果，表3是入库货物订单数据及优化后货位数据，图5是3种算法目标函数值随迭代次数的变化曲线，图6是优化后的货物分布图。

表2 3种算法实验结果比较

表3 入库货物订单信息及优化前后货物货位信息

图5 目标函数随迭代次数变化图

图6 50个订单优化后货物分布

从图5可见，货位分配的归一化多目标函数值随迭代次数的增加而逐渐减小，在迭代0～380次左右时精英种群最优个体的保持代数都小于事先设定的值，迭代次数大于380次时，归一化的目标函数值曲线趋于水平，直到最后达到精英种群最优个体保持代数时算法收敛。从表3和图6的结果可以发现，周转率较大的货物被分配在离出入库口近的货位上，低的被分配在了相应稍远的位置，符合出入库效率要求；从整体货架的稳定性考虑，质量大的货物被分配到了货架底层位置，而质量小的被分在了高层；从堆垛机的负载情况来看，每个巷道内货架上的货物分配基本均衡，满足堆垛机负载均衡；上述结果从侧面证明了本文所建立优化模型的有效性。从表2可见，采用多种群遗传算法的优化结果比SGA 提高了6.03%，但使用余弦自适应多种群遗传后其优化结果提高了9.03%，且由于引入了自适应交叉、变异算子，其收敛速度更快，有效地提高了求解速度和求解精度。

为了更加完全、准确地评价改进后AMPGA的优化性能，在不同规模订单下进行了50次循环实验，每个订单货物的质量和周转率都是有差异的，算法的平均实验结果如表4所示。

表4 3种算法的实验结果

从表4中的实验数据可以分析出，在不同规模订单下，3种算法的优化程度有着不同的区别，MPGA相比于SGA少2%～12%，AMPGA相比于SGA少2%～14%，且AMPG A优化程度比MPGA更显著。AMPGA在大规模订单下其优势相对于SGA更为明显，同时在收敛耗时方面，AMPGA耗时短、收敛快，能够更快得到最优解，因此AMPGA更适合大规模立体仓库货位分配优化问题。

4 结语

本研究针对多巷道立体仓库货位分配优化问题，综合考虑了出入库效率、货架稳定性与堆垛机负载均衡，建立了多巷道立体仓库货位分配优化的多目标函数模型，并设计了一种自适应多种群遗传算法（AMPGA）来优化立体仓库中货位分配。通过实验仿真验证了所建模型的有效性，比较不同订单规模下3种算法的货位分配结果，结果显示AMPGA算法在大规模订单下优化效果更佳，收敛更快，能够很好地解决多巷道立体仓库货位分配问题。