基于遗传算法的高架立体仓库拣选路径优化

2015-04-25夏贤康

铁道货运 2015年9期

关键词：货位立体仓库叉车

夏贤康

（兰州交通大学交通运输学院，甘肃兰州 730070 ）

基于遗传算法的高架立体仓库拣选路径优化

夏贤康

（兰州交通大学交通运输学院，甘肃兰州 730070 ）

在阐述高架立体仓库拣选路径优化模型的基础上，以拣选时间最小为优化目标，将目标进行量化建立数学模型，并且采用遗传算法对优化模型进行求解，最后选用Matlab软件设计算法求解最优解。在拣选路径优化求解过程中，通过设定模拟参数，选用S-shape策略、混合型策略和遗传算法分别对20种货物进行仿真求解，最后进行结果比较以验证拣货优化模型的有效性。

拣选路径优化；遗传算法；Matlab；仿真

随着机械化和计算机技术信息化的快速发展，仓库管理已经成为现代企业物流管理系统的重要组成部分[1]。为提高仓库管理效率，一方面可以优化货位设置，另一方面应考虑尽量提高拣选货物效率。在货物的拣选过程中，路径的选取至关重要。因此，以提高仓储作业效率、节约仓储成本为目标，对货物拣选路径进行优化以降低物流成本、提高经济效益的研究非常必要。目前国内关于货物拣选路径优化的研究很多，大部分以时间最少为目标[2]，选用的优化方法有启发式算法[3]、神经网络法、遗传算法、禁忌搜索法、蚁群算法及模拟退火算法等[4]，而在解决优化问题时，大部分学者会选择遗传算法来建立优化模型，通过采用遗传算法可以实现对仓库拣选路径的优化，提高拣货作业效率[5]，减少拣货作业时间。

1 数学模型的建立

1.1 模型的描述和假设

在分析模型目的和特征的基础上，对模型进行描述和假设。①在生成拣货订单过程中，有 1 种或多种货物合并为 1 批的订单，需要通过 1 个高位叉车进行拣选。②需要拣选的货物总容积和质量不会超过高位叉车的最大承载质量和最大拣选能力。③仓库中存储区的货架为双排型连接，并且为水平排列。④货架每层垂直间距为 h，忽略叉车取货时间，已知拣选货物的品种和货位位置并且叉车匀速行驶。

1.2 建立拣选路径优化模型

拣选路径优化过程是以拣选时间最短为目标，通过降低拣选路程来提高拣选作业效率。假设高位叉车 1 次需要拣选 L 种货物，根据假设建立拣选路径优化模型如下。拣选完 i 后立即拣选 j否则

ci＞0 并且为整数

2 遗传算法的设计

在解决一般路径优化问题时，遗传算法可以发挥较好的效果[6]。遗传算法的主要步骤包括编码设计、适应度函数确定、选择操作、交叉操作及变异操作等[7]。通过采用遗传算法求解上述模型最优解，找出高架仓库拣选的最优路径，算法步骤如下。

（1）采用整数编码，每条染色体有 L 段基因表示L 种货物，染色体上每个基因表示 1 个货位 (x，y，z)。

[8]。

（3）选择操作，所有个体按照适应度值从小到大排列，选择中间和尾部的个体进行复制，保留优秀个体。

（4）交叉操作，采用单点交叉，只互换 2 个染色体的一个交叉点的基因。

（5）变异操作，随机选择父代个体染色体的 2 个位置，将处于二者间的基因顺序颠倒，形成新个体。

（6）终止条件，设种群规模为 50，交叉概率为 0.85，变异概率为 0.05，当迭代次数达到 1 000时，算法终止。

3 拣选路径优化仿真过程

3.1 模拟参数设定

通过对拣选路径优化模型的分析，根据高架仓库的整体布局进行模拟参数设定，选取 20 种不同类别的货物作为研究对象，在这 20 种货物总质量不超过叉车最大负荷的情况下，分别选用 S 型拣选方法、混合拣选方法和遗传算法对 20 种货物拣选最优路径进行求解，然后进行比较分析，选出最佳拣选方案。参数设定的初始化货物货位信息如表 1 所示。

表 1 货物货位信息

模拟的立体仓库仓储区的长为 32 000 mm、宽为 30 000 mm，有货架 12 排 12 列 6 层，每个货位长2 300 mm、宽 1 200 mm、高 1 500 mm，拣货通道宽2 300 mm，有高位叉车 1 台，叉车水平运行速度 vx= 1 000 mm/s，垂直运行速度 vy=250 mm/s，根据表 1 的货位信息绘制仓库拣选区的简易布局如图 1 所示，其中从左至右为 1—12 列，从上至下为 1—12 排，黑色方格为 20 种货物所在位置，白色方格为非选取货位。

3.2 仿真结果分析

选用 S-shape 策略、混合型策略和遗传算法分别对 20 种货物进行仿真求解，通过 Matlab 软件设计算法求解结果如下。

（1）S-shape 策略。S-shape 策略是指穿越策略[9]，需要把每个通道都走一遍，然后拣选出所需要的货物。首先对 20 种货物进行编码，通过 S-shape 策略优化后所需要的拣选时间为 848.8 s，得到拣选路径：14→12→16→13→20→17→9→2→1→15→18→6→11→7→4→3→5→8→10→19。

图 1 仓库拣选区的简易布局

（2）混合型策略。混合型策略是指退回策略和S-shape策略相结合的策略[10]，通过混合型策略优化后所需要的拣选时间为 856 s，得到拣选路径：14→12→16→13→20→6→11→19→5→10→8→3→4→7→18→15→1→17→9→2。

（3）遗传算法。采用 Matlab 软件对拣选路径优化模型进行求解[11]，设种群规模为 50，交叉概率为0.85，变异概率为 0.05，迭代次数为 1 000 次。通过遗传算法优化后所需要的拣选时间为 827.3 s，得到拣选路径：14→12→16→13→20→6→11→7→4→3→8→10→5→19→18→15→1→17→9→2。

比较这 3 种方法得到的优化结果如表 2 所示。

表 2 3 种拣选方法优化结果对比 s

通过表 2 可以看出，相对于混合型策略和 S-shape策略而言，采用遗传算法对仓储货物拣选路径优化可以有效减少拣选时间，提高拣选工作效率。

4 结束语

通过改进货物拣选路径优化模型，采用遗传算法进行求解，并且使用 Matlab 软件对拣选路径优化进行仿真设计。为验证模型的有效性，采用混合型策略、S-shape 策略和遗传算法分别求解，得出最优解即拣货作业时间和拣选路径最优，对优化结果进行比较可以看出遗传算法求解模型优于其他算法，实现拣选路径优化的目的。由于所建立的模型适用于小件货物拣选，如果在大型仓库，随着拣选货物量和货物体积质量的增加，模型优化结果将不明显。此外，建立模型时仅考虑叉车水平和垂直方向的位移，而没有将拣货时间和寻找货物时间考虑在内，还有待继续深入研究。

[1]吴耀华，王莹，肖际伟，等.现代物流系统技术的研究现状及发展趋势[J].机械工程学报，1999，35(4)：1-5.

[2]王占磊.配送中心订单分批及拣选路径优化问题研究[D].长春：吉林大学，2013.

[3]王梦楠.基于遗传算法的物流中心货位优化研究[D].大连：大连海事大学，2012.

[4]DukicG，OluicC.Order-pickingRoutingPolicies：SimpleHeuirstics，AdvancedHeuirstics orPrimalAlgorithrn[J].JournalofMachenicalEnginnering，2004，50(11)：530-535.

[5]石梦竹.基于动力贯穿式货架的自动化立体仓库的入库调度优化研究[D].济南：山东大学，2013.

[6]别文群，李拥军.遗传算法在立体仓库货位优化分配中的研究[J].计算机工程与运用，2009，45(29)：211-213.

[7]刘宝碇，赵瑞清，王纲.不确定规划及应用[M].北京：清华大学出版社，2003.

[8]刘思佳.A公司仓储中心出库作业优化研究[D].长春：吉林大学，2014.

[9]白寅.基于偏离度的仓库拣选路径优化方法及应用[D].武汉：华中科技大学，2012.

[10]高亮，张国辉，王晓娟.柔性作业车间调度智能算法及其应用[M].武汉：华中科技大学出版社，2012.

[11]吴婷.基于遗传算法的仓储系统多目标货位优化的研究[D].武汉：武汉理工大学，2011.

责任编辑：吴文娟