基于遗传算法的自动化立体仓库货位优化研究

0 引言

现代物流企业对于仓储的现代化管理要求越来越高，自动化立体仓库（AS/RS）在提升库存量，提升空间利用率、减少占地和节约人力等方面具有巨大优势，是物流系统发展和优化的关键环节。如何进行货位分配是影响自动化立体仓经济效益和安全性的核心问题，货位在遵循货位分配原则的基础上如何优化，通常从优化目标以及优化算法入手。由于自动化立体仓库会因为建筑形式、货架样式等因素产生不同的细分类别，也会因为拣选输送系统、存取作业设备、存储条件和策略等因素的不同，在对货位分配问题上应用的优化方法有很大的区别。

Fonseca[1]将货位优化问题总结为多目标的求解问题，并且分析了多目标进化方法，提出多目标优化问题难以求得最优解，只能通过平衡、协调多个目标达到Pareto 最优解。此外，许多国内外学者把货位优化问题总结为以出入库效率、货架稳定性、堆垛机路径优化为主的多目标优化模型[2-4]。对于货位优化的多目标优化问题，在优化算法的选择上许多学者采用遗传算法进行求解。邓爱民等[5]以货架稳定性、分巷道存放和出入库效率为目标的基于时间的多目标模型，李梅娟[6]提出了采用Pareto 遗传算法解决该问题，针对提高货架稳定性和存取效率取得了不错的优化效果。

除此之外有非常多的优化算法被应用在货位优化问题上，陈月婷、何芳[7]提出了基于Pareto 最优解的改进粒子群算法来解决货位优化问题。李鹏飞等[8]通过对比分析提出病毒协同遗传算法是解决货位优化问题的一种有效方法。大量学者热衷于算法应用上的创新，在优化目标选择上主要集中于提高存取效率以及货架稳定性，鲜有考虑工作量均衡的研究，虽然目标优先级是次要的，在实际应用中也是容易被忽视，但却是很可能出现的问题。此方面的研究首先要界定工作量的定义，通常是指进行存取作业的设备工作量，立体仓库的作业设备不尽相同，除堆垛机外也有应用提升机与子母穿梭车的立体仓库，着眼于作业设备工作量均衡的优化模型在设计过程中要考虑实际情况下会产生许多工程上的限制因素，同时模型所需数据存在一定的难度，在寻求通用的优化模型上，唐文献等[9]在货位优化模型中设计了以出入库频率为核心的巷道工作量均衡模型，并以细菌觅食算法进行求解，在仿真过程中验证了单一考虑某个优化目标时的优化效果，由于目标函数之间可能存在约束或冲突，同时考虑多个优化目标才更符合自动化立体仓库的实际需求。

本文正是针对我国应用最为广泛的单元货格式立体仓库[10]，在以提高存取效率和货架稳定性为优化目标以外，考虑到可能出现部分巷道任务过多，而部分巷道任务偏少的工作量不均衡问题，为减少此类生产浪费，额外设置工作量均衡的优化目标。考虑到数据的获取难度，在模型中通过控制巷道与巷道之间总出入库数量差值最小来达到基于任务量的巷道工作量均衡目标，该模型不会被巷道操作设备的选择所影响，对这个多目标优化问题采用遗传算法进行求解，通过仿真验证模型的优化效果良好。

1 货位分配原则

对自动化立体仓库进行货位分配时应当遵循以下原则：（1）货架稳定性原则。货架首先应当保证具有足够安全性，货品的存放应当从下至上，上轻下重，降低货架重心。（2）就近出入库原则。在自动化立体仓库中，使存储位置放置在距离出库台附近，尤其是出入库频率高的货物，存放在出库口附近可以有效减少作业距离，从而提高存取效率。（3）先进先出原则。同一种货物在出库时，应当遵循入库早的先出库的原则。避免货物存放时间过长而造成不必要的损失。

2 问题描述与基本假设

描述如下：在M 公司的仓库库区中选择共有a 排货架，每排货架有b 列c 层，将距离出库口最近的一排货架记为第一排，最近的一列记为第一列，最底下一层为第一层。那么，货位坐标(x,y,z)代表位于第X 排Y 列Z 层的货格，（x=1,2,…,a;y=1,2,…,b；z=1,2,…,c；a 为偶数）。每一组货架都由两排货架组成，两排货架共用一台堆垛机完成出入库作业，如图1 所示。出库台位置记作(0,0,0)，数学模型涉及的符号说明如表1 所示。

图1 一组货架示意图

表1 符号说明

根据如上描述，将本文进行货位优化的基本假设总结如下：（1）该自动化立体仓库系统的存取方式是单元货格式，即仓库的每一个通道中都有一台巷道堆垛机，其两侧各有一排货架，每一排货架都是相同的，货架上的每个货格也都大小相同，每个货格只能存储一个货品，由托盘承托，所有托盘尺寸相同。（2）堆垛机可以对其两侧的货架托盘进行存取作业且两侧作业情况一致。（3）立体仓库的出入库方式为单端口，采用随机存储策略。（4）存取货品消耗时间忽略不计。（5）巷道堆垛机可以在水平和垂直方向即Y 向和Z 向向上同时做匀速运动。

3 数学模型的建立

3.1 出入库效率最高的目标

根据就近出入库原则，要实现距离最短，使得作业时间最短即可，则所有货物的存取频率和堆垛机运行时间乘积之和最小，由此建立数学模型：

3.2 货架稳定性的目标

根据货架稳定性原则，要降低货架整体的重心，使得货架整体下重上轻，即使货品的质量mxyz与货位(x,y,z)所在的层数z的乘积之和最小，由此建立数学模型：

3.3 工作量均衡的目标

为了达到工作量均衡的目标，即每个巷道的工作量均衡，通过控制巷道与巷道之间的出库任务量差来使得巷道达到工作量均衡的状态，在此策略下还能一定程度上使得货位数量均匀分布，间接达到工作量均衡的目的，配合目标函数（2）可以使货架有较好的抗倾覆能力[11]，由此建立数学模型：

3.4 约束条件

由空间约束条件可知，货位(x,y,z)是处于货架内的坐标，因此有：

3.5 多目标货位优化模型

根据以上三个目标函数和约束条件可得货位优化的多目标函数表达为：

4 多目标遗传算法模型求解

解决多目标优化问题的基本思路是把多目标问题转化为单目标问题，遗传算法全局搜索能力强，鲁棒性好，在解决多目标优化问题的研究领域内应用广泛且效果显著。故本文采用遗传算法对模型进行求解。

4.1 多目标问题转化

给三个目标函数分别赋予目标相应的权重值Wi(i=1,2,3)，权重越大表示目标函数的重要程度越大，因此多目标优化问题可以表示为：

4.2 编 码

编码方式选择自然数编码。用自然数1,2,3…来代表货位(x,y,z)，那么染色体的长度就与货物的总数量一致。

4.3 种群初始化

初始化工作采用随机方法产生种群规模K=100 的初始种群。

4.4 适应度函数的确定

遗传算法中采用适应度函数来衡量个体的优劣，适应度值要求必须为负数，适应度值较大的个体被认为是优良的个体，所以适应度值越大越好。遗传算法经常把目标函数作为适应度函数，对于本文三个目标函数都是求全局最小值，而且都是非负数，那么可以直接取目标函数的倒数作为适应度函数。

为了防止函数值差值过大影响遗传算法的性能，在进行倒数操作前，先将各目标函数去量纲处理，消除单位对数值的影响后再对目标函数求倒数来构造适应度函数。对目标函数线性变换处理，转化为无量纲函数。

经过线性变换后三个目标函数均映射到(0,1)区间，式中fi代表第i 个目标函数，原目标函数分布情况不会因为线性变换而改变，不会影响遗传算法的性能。为了避免出现数据溢出的情况，在分母上加1 避免适应度函数值趋向于无穷大。转换后的适应度函数表达式为：

4.5 选择操作

选择操作对初始种群的各个染色体进行评价，本文选择轮盘赌选择法，首先计算每个染色体得到适应度值Fi和整个初始种群的适应度总和；其次计算种群中每个染色体个体被选中的概率pi；然后按照次序计算每个染色体个体被选择的累计概率；最后随机生成一个介于0 到1 之间的随机数R,依次与累计概率进行对比，如果满足在累计概率范围内则被选中。即R＜P1，就选择第一个个体，如果PK-1≤R≤PK,则选择第K 个个体。

4.6 交叉算子

交叉操作是按照一定的方法交换染色体上的部分，从而得到两个全新的个体。随机从(0,1)之间生成一个数r，将这个数与交叉概率pc进行比较，pc一般取0.4 到0.99 之间，如果r≤pc就进行交叉运算，如果r＞pc则将两个母代个体重新加入下一代的种群中。结合自然数编码的编码方式，本文选择基于位置的交叉（Position-based Crossove）r。

5 基于Matlab 的模型求解和仿真分析

5.1 参数设定

本文对M 公司的仓储信息系统中选择某一区域进行采样，经过处理和计算得到重量和初始坐标等信息，为了方便研究，只提取货架的部分区域，对此优化区域的参数作一些假设，该货架区域由4 排，5 列和8 层的货架构成，共160 个货位，当前优化区域有100 个货品。立体仓库货架和堆垛机的基本参数、遗传算法所需要的基本参数以及多目标模型的权重设置具体如表2 所示：

表2 仿真基本参数表

5.2 结果分析

为了验证模型的有效性，对优化前后的货位分配布局和目标函数值进行对比，优化前货物分布图如图2 所示。

图2 初始货物分布图

优化后的货位分配情况如图3 所示。

图3 优化后货位分配模拟图

目标函数由三个子函数构成，每个子函数的权重都会直接影响最终的优化效果，权重的大小可以根据企业对于目标函数体现的存储策略的侧重程度灵活调整，在三个权重分别为0.4、0.3 和0.3 时货位分配结果合理，模型运行结果如图4 所示。

图4 优化算法迭代曲线图

将优化前后三个目标函数值及加权结果进行对比，结果如表3 所示。

由表3 可知，三个目标函数经过优化后都有不同程度的降低，三个目标函数的降低比率分别为15.83%,50.24%和100%，加权后的目标函数值降低比率达到50.21%。

表3 优化效果对比表

对子目标的权重进行调整，观察权重对于优化结果的影响程度。仓储货品重量普遍较大的企业较之于货品重量普遍较轻的企业，在存储策略上往往在注重提高存取效率的前提下同样非常重视货架稳定性，因此将目标函数f1的权重保持不变，目标函数f2的权重提高0.1 之后重新运行，最终模型得出的优化结果如表4 所示。

表4 重设权重后的优化效果对比表

由表4 可以看出，再对目标函数的权重进行略微调整之后，总体优化效果依然超过了50%，优化效果显著。

实际应用中部分立体仓库对于货架稳定性的要求不高，例如蔬果类乳品类企业会更加追求存取效率上的优化提升，出于对比目的以便观察目标函数（1）的权重对于优化效果的影响，再次对子目标的权重进行调整，当三个目标函数的权重分别为0.5、0.3 和0.2 时，模型运行结果如表5 所示：

表5 二次调整权重后的优化效果对比表

由表5 数据可以发现，再次微调权重后的运行结果有略微变化，优化效果相比前文两种权重配比变化不大，模型的优化效果仍然比较显著，说明优化模型依旧充分发挥作用，起到了较明显的优化效果。

6 结论与展望

本文通过对某食品企业M 公司自动化立体仓库作业案例的考察，建立多目标优化的数学模型并以真实数据进行Matlab 仿真研究，优化结果表明该模型可以提高存取效率以及货架稳定性，除此以外还能有效解决巷道工作量均衡的问题，以加权后的目标函数值为例，试用三种不同比例的权重分配模拟不同类型企业在存储策略上可能做出的微调，模型运行结果比较稳定，加权后的目标函数值平均降低比率为50.23%，说明此优化模型在常规权重设置的条件下能够达到50%左右的优化效果，对于不同存储策略的单元货格式自动化立体仓库都可以发挥出实际应用价值。

本文是基于我国目前广泛应用的单元或格式立体仓库，随着技术与设备的更新升级，像双深位立体仓等新式立体仓不断出现，也为该领域的研究开辟了新的疆土。另一方面，一些对模型的简化所作的假设会对实际运行效果产生不同程度的影响，此方面仍有改善的空间，将作为今后进一步研究的方向。