基于遗传算法的仓储管理优化研究

郑 斌，林 钦

福建江夏学院 电子信息科学学院，福建 福州 350108

随着城市轨道交通行业的迅速发展，轨道交通企业的仓储需求逐渐增大。轨道交通企业的仓储货物中，机电设备占了较大比例，机电设备种类繁多、需求的时间和数量不一，每当有出库作业要求时，备货速度就成了影响出库效率的关键环节。因此，如何通过优化管理方法、提升备货效率，来降低仓储管理的成本，成为轨道交通企业越来越关心的问题[1]。

1 仓储管理研究现状

现阶段，轨道交通行业的仓储管理中仍然存在不少问题，如储货仓库货位安排不合理，仓库基础设施较为落后，信息化程度不高等，这些都会导致仓储管理成本过高。轨道交通企业的仓库大多仍采取人工备货方式。据研究，在物流订单的备货总耗时中，行走时间占总耗时的50%左右，如图1 所示。针对不同出库单，采用合适方法优化备货路径，对提高备货效率，减少仓储管理成本具有重要意义。

现阶段，针对仓库备货路径优化的研究大部分集中在减少拣选时间方面。朱文真等采用遗传算法和其他禁忌搜索算法结合，得出立体仓库的优化拣选路径[2]；李梅娟等研究静态情况下立体仓库货位的调度优化，设计出合理的拣选路径[3]；王占磊分别使用S 型策略和遗传算法来优化拣选路径[4]。

各个行业的仓储存在业务、货物规格形状、存储要求等诸多不同，在实际生产过程中需具体分析实际情况，根据轨道交通企业的仓储特点和要求，实现仓储管理备货拣选路径的优化，满足轨道交通企业对仓储的要求。

2 基于遗传算法的仓储货物拣选路径优化

2.1 遗传算法简介

遗传算法是最早提出的模拟生物遗传系统的算法模型，模拟基因的进化，通过选择操作与重组操作进行驱动。算法过程从初始种群开始，先得到一个初始解，然后经过反复调整优化，不断产生新的可行解，其演化过程模拟自然界生物优胜劣汰的法则，直至最终出现最优解。遗传算法的基本过程示意图如图2。

2.2 拣货路径优化模型构建

研究对象是某轨道交通企业的一个仓库，通过用遗传算法针对该仓库建立数学模型，来解决仓库备货拣选的路径问题，计算出最优拣货路径，来达到提升备货效率的目的。

2.2.1 模型假设条件

目前遗传算法在路径优化方面应用的频率较高。对于某轨道交通企业仓库的机电设备拣货路径优化问题，选取了几种不同的方法来求解，并对各种方法得到的解进行对比分析，以此来确定最优算法和最优路径，达到最大限度降低备货拣选时间，提高出库作业效率的目的。基于研究的仓库和货物的情况，在构建模型时，做如下几点假设：

（1）每次拣货时，如一批拣货订单中包含多种货物，则至少需一个高位叉车来完成拣选作业。

（2）根据高位叉车的承载重量来拣选货物，所拣选的货物总重量需小于等于高位叉车的承载重量，根据不同拣选能力分配不同种类零部件。

（3）仓库内的货架布局为：所有单个货架水平、双排并列排放。

（4）所有叉车在行驶和取货过程中都是匀速的，要取的货物所存放的位置设为已知变量。

（5）每个设备的大小尺寸不同，研究时不考虑尺寸因素，认为设备大小一致。

2.2.2 模型建立

在优化拣选路径、提高备货效率方面，主要考虑实现两个目标，一是拣选时间最短，二是拣选路程最近。可设定模型如式（1）、（2）所示。

2.2.3 遗传算法步骤设计

针对订单备货拣货路径优化这一问题，采取遗传算法来进行最优解的计算，以期能较快得到货物拣选的最优路径，同时节省拣货时间。主要步骤如下：

染色体编码：按完成一次拣选L 种货品的顺序组成一条染色体，采用整数编码，每条染色体由L段基因构成，每个基因对应一个货位，货位用行、列、层表示。如“{3，6，7，2}”表示拣选路径为“I/O→货位3→货位6→货位7→货位2→I/O”。

适应度函数：目标函数是求最小值，优化效果越好的个体适应度值越大，因此设计适应度函数为

交叉算子：染色体中基因表示要选取的货品，不能缺漏或重复，因此对两个染色体分别选取一个交叉点进行基因的配对交换，即采用单点交叉，步骤如图3 所示：

交叉概率取值为PC=0.85，对每条染色体，根据随机数P∈[0,1]，如果P＜PC则对该染色体进行交叉操作。

所有个体筛选操作：所有个体按照相对种群的适应度值由大到小排列，选择优秀染色体遗传下一代。

计算终止条件：按照一般的参数取值推荐，种群规模取值为50，变异概率取值为0.05，迭代次数到了500 时终止算法。

2.3 仿真分析

研究的轨道交通企业的仓库是35m*28m 的立体仓库，摆放有货架12 行*12 列*6 层，每个货位尺寸为2.5m*1.3m*1.6m，叉车通道宽1.2m，叉车在通道的平均水平行驶速度Vx=0.9m/s，垂直移动速度Vy=0.3m/s。

通过模型分析，根据所研究的仓库的布局情况[5]，设定初始参数。从库存的机电设备中选取了20种不同类别的货物，各类货物位置及仿真参数如表1 所示。各货品在仓库中的简易布局如图3 所示。

表1 仿真数据

选用混合型策略、S-shape 策略、最大间隙法和遗传算法分别对表1 中的具体参数进行仿真计算，通过MATLAB 编程实现各个方法，求出四种方法的时间和最有路径，结果如下：

2.3.1 S-shape 策略

S-shape 路径优化策略先要通过每个拣货通道，再根据订单来选取不同的货物[6]。通过该策略优化后所需要的订单备货拣选距离为249m，订单备货拣选时间为617 秒，得到的订单备货拣选路径如下，如图5 所示。

2.3.2 混合型策略

混合型策略包含两种策略，分别是退回策略与S-shape 策略，将这两种策略相结合得到的优化策略即为混合型策略[7]，利用该策略进行优化后的订单备货拣选距离为256m，订单备货拣选时间632s，得到订单备货拣选路径如下，如图6 所示。

2.3.3 最大间隙法

最大间隙法首先要选出订单货物所在区域的通道，然后叉车只走这些通道取货，直接省略无关通道[8]。应用此法计算叉车拣货行走距离为253m，订单备货拣选耗时627 秒，得到的订单备货拣选路径如下，如图7 所示。

2.3.4 遗传算法按照3.2.3 节的设计步骤，应用遗传算法进行优化后，计算得叉车拣货行走距离为215m，订单备货拣选耗时575s，订单备货拣选优化的路径如下，如图8 所示。

对比四种方法得到的路径长度和拣选时间如表2 所示。

表2 四种策略结果对比

通过表2 数据对比，遗传算法相较于其他三种方法，拣选路径最短，拣选耗时最少，采用遗传算法优化轨道交通企业的仓库备货路径问题，可以有效的提高订单的备货工作效率。

3 结语

通过分析轨道交通企业仓储管理的现状与存在的问题，针对提升仓储作业效率问题，采用遗传算法对仓储货物拣选路径模型进行了优化，通过与仿真结果的对比，证明采用遗传算法得出的货物拣选路径最优解对仓储作业效率提升最大。结论可为后续仓储管理优化提供理论依据与实际参考。