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

华祎明，王凯鹏，陈博翱，崔 晶，何美玲

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

0 引言

随着信息技术、物流技术和管理技术的不断发展，世界经济的进一步全球化，汽车零部件需求呈现出更高的随机性，因而使得本就需求量庞大、种类繁杂的零件分配任务更加复杂。传统的汽车零件运输模式已经很难适应如今快节奏、个性化的市场需求，因此，很多汽车产业公司为提高综合效益普遍采用了JIT（Just In Time）物流模式。与此同时，由于汽车存储系统的繁杂性，如何对仓库的设备进行合理配置以及仓库存储模式的选择便显得尤为重要。自动化立体仓库是仓储物流中出现的新型系统。自动化立体仓库大多采用混流生产模式下的信息管理中心来实现整体的自动化控制，在优化储存功能的同时，也大大降低了企业的人员成本。其仓库布局合理、操作简便，能够有效地增强物流作业的质量，从而大大提高了整个系统的工作效率。很多汽车产业公司正在逐步将JIT模式与自动化立体仓库相结合进行生产和管理，并将不断发展成为一种完善的物流供应体系。

货位优化可以有效提高存储的系统效能。何李，等将货位分配与作业调度集成优化，提出两阶段狼群算法，能够较好地满足柔性化订单。张延华，等兼顾算法的全局搜索能力和局部搜索能力，引入模拟退火算法，有效提高了算法的收敛速度。Haiping Ma，等针对自动化立体仓库的调度问题，提出了一种基于集成学习的集成多目标生物地理学优化（EMBBO）算法。Yu ling Jiao，等则证明了多种群遗传算法的结果优于简单加权遗传算法的结果。

综上所述，目前国内外学者缺少对优化结果的验证或者对优化结果的验证较为简单。考虑到Flexsim软件能高效直观地验证优化结果的有效性，可以达到一般数字证明无法实现的实际运行效果，因此本文以入库效率和货架稳定性为目标函数建立多目标优化数学模型，提出一种非线性规划的改进遗传算法，为入库的货物分配最佳的货位，并通过Flexsim建模验证该算法的有效性。

1 货位分配模型

1.1 问题描述

以某汽车零部件企业的自动化立体仓库为例，该企业的货位分配采用随机存储的方式。但由于汽车零部件种类多、数量大，该仓库出入库作业效率十分低下，而且货位分配不合理，货架稳定性差。首先对上述汽车零部件物流企业的自动化立体仓库进行分析，以明确货位优化目标。

为方便研究作出如下假设：（1）出入库口为（0，0）；（2）每个货格的基本参数（长度、宽度、重量）相同且适宜，货格为标准的正方体；存储货物后，该货位的几何中心即为该货位的重心（货物重量对货架稳定性带来的影响忽略不计）；每个货格能且只能存储一个货箱；（3）堆垛机在不同方向上的运动是独立的，堆垛机以最大速度匀速运行（忽略其启动和制动），且不考虑各种摩擦阻力的影响；（4）堆垛机一次仅能搬运一个货物；（5）不考虑取、放货时堆垛机的滞留时间；（6）忽略货架重量；（7）运行时速度不考虑货物重量。

1.2 模型符号说明

：货架列数；

：货架层数；

：货架个数；

：货架的标号；

：堆垛机的总运行时间；

f：一个周期内在第w排货架第i列第j行的某个货位的存取货物频数；

x：堆垛机在第w排货架第i列第j行的某个货位有零件存放时为1，否则为0；

v：堆垛机的水平速度；

v：堆垛机的竖直速度；

v：堆垛机的垂直提升速度；

t：堆垛机从出入库口到取货位所用的时间；

m：在第w个货架第i列第j层的货品的质量；

：堆垛机水平运动的距离；

：货位单位长度；

：巷道宽度；

：货架上各货位重心与质量之积的和。

1.3 模型的建立

根据上述的模型假设以及参数设定，建立多目标的自动化立体仓库货位分配模型：

（1）货物入库效率分析。将货物尽可能存放在离入口更近的地方，可以减少堆垛机的搬运时间，从而减少整体的入库时间。

堆垛机运行的总时间为：

堆垛机从出入库口到取货位所用的时间表达式为：

其中，堆垛机的水平位移为：

（2）货物货架稳定性分析。作业安全在入库作业中尤为重要，在入库作业时，尽量遵循“上轻下重，均匀分配”的原则，降低货物货架重心，以提高货物货架的稳定性。

在人行天桥的应用中，根据城市发展需要，可能需要对桥梁结构进行改造，钢结构拆装便捷，并且污染比较小，回收利用价值较高。

保障仓库稳定性的目标函数为：

式（4）计算的是各货位重心与质量之积的和，当某个货位上没有货物时，m的值为0。

综上所述，该仓库的货位分配模型为：

2 模型求解

2.1 算法的选择

（1）遗传算法。遗传算法在计算多目标优化问题上有较好的表现，它可以在自然环境的前提下提高自身的优越程度。这一过程首先使用染色体表示种群中的个体，通过某个种群中的个体再进行模拟进化，实现达尔文进化论中的“优胜劣汰，适者生存”。遗传算法的主要特征：它是种群中个体的适应度，当进行适应度评估时，会通过执行交叉、适应度比例再生以及变异操作生成新的种群，每次迭代，都会用新的种群来替代旧的种群。

遗传算法的优点为：可从多个初始点切入，按照不同的方法进行搜索来实现全局最优；可以高效的处理多目标优化问题，相当于在搜索范围内对多个解进行结果评估，更快跳出局部最优解，同时该算法本身易于实现并行化；可从问题解的串集开始搜索，而不是从单个解开始，覆盖面大，利于全局择优；可以通过概率机制进行迭代，使得多目标的解具有随机性。

（2）非线性规划。非线性规划是求解规划问题的一种方法，它能够求出目标函数的最优结果，也能在出现非线性函数的约束条件下求最优解。它是在多种有一定关系的变量下，变量与约束条件相互对应，计算或得出一个问题的线性目标函数最优解。

根据以上两种算法的特点，本文设计了基于遗传算法嵌套非线性规划的求解方法，进行多目标的货位分配模型求解。

2.2 操作流程

（1）编码方式。编码方式为整数编码，即每条染色体代表一个货位，货位信息由整数编码，货位信息包含货位的排数、列数、层数信息，基因的值采用整数，表示货位在立体仓库中的具体三维坐标。如本模型中（3,2,1）代表的含义是第1排货架的第3列第2行。

（3）适应度函数的建立。在上述模型中本文已经建立两个求解最小值的目标函数，在实际的求解过程中，本文将多目标函数转化为单目标函数，通过加权算法来平衡两个目标函数对整体结果的影响。

（4）选择操作。将种群中适应度高的个体选出，遗传给下一代种群，以此进行循环操作，进行不断的迭代，迭代达到一定次数后使得优化后的个体更进一步的靠近目标函数的最优解。用适应比例方法（见式（9）进行选择操作，选择概率大的个体。

（5）交叉操作与变异操作。将种群里的任意两个个体，按照一定的概率交换他们内部的部分基因，以此形成新的个体。本文设置的交叉概率为60%；新基因的产生方式是由变异操作来完成，本文设置的变异概率为1%。

（6）终止条件。将最大的迭代次数设置为100，得到最后一代种群中适应度最高的解，即为算法得出的最优解。

图1为货位分配的算法流程图。

图1 算法流程图

3 应用实例

3.1 参数设定

为了研究方便，本文选取该汽车零部件自动化立体仓库的一部分：3列9层6排作为研究对象。堆垛机的水平移动速度v为2m/s，堆垛机的竖直移动速度v为2m/s，垂直移动速度v为0.5m/s。货位单位长度L为1.1m，巷道宽度为1.5m。货物分类及其参数见表1。

表1 货物分类及其参数

3.2 仿真结果

使用MATLAB对模型进行求解，得到图2和表2。图2中虚线为遗传算法的求解结果，实线为改进遗传算法的求解结果，可以明显看出改进遗传算法的目标函数值更优且迭代次数更少。改进遗传算法在32次迭代时就已经接近最优解，此时的函数值为7 200左右，而遗传算法在70次迭代后才接近最优解，函数值在7 800左右。

表2 货位分配结果

图2 遗传算法与改进遗传算法的各代平均值

优化结果见表3将优化前后的函数目标值进行对比，与随机入库相比，优化后的函数值分别降低了34.35%和30.78%，加权后的总目标函数值降低了31.66%。仓库的货位分配主要集中在仓库的入口和货架的底层，极大地提高了入库效率和货架稳定性。

表3 优化前后函数目标值对比

3.3 Flexsim模型验证

具体实体种类及实现的功能见表4。

表4 模型实体种类及其功能

仓库模型中所需要的具体机械设备有：单元货格式货架10个；传送带18条；自动堆垛机5个；机器人6个；货格2 700个，仓库布局如图3所示。

图3 仓库仿真布局图

将Flexsim仿真模型运行8h，输出运行结果，得到实体的停留时间、阻塞时间、限制时间等数据，汇总见表5。分析表5数据可以看出，通过货位分配，自动化立体仓库设备利用率较高，不存在阻塞现象，系统可以有效持续运行。

表5 汇总统计表

4 结语

本文提出一种改进遗传算法，在JIT背景下对汽车零部件自动化立体仓库进行货位分配优化。在提高自动化立体仓库入库效率的基础上，兼顾货架稳定性构建多目标数学模型。仿真实例表明，优化后的函数值显著降低，仓库系统可以有效运行，无阻塞现象，因此该优化方案有较好的应用价值。