某航空标准件企业成品库拣货路径优化研究

李健

摘要：以航空标准件企业的产品库拣货问题为研究对象，建立了以拣货总时间最小化为目标的路径优化模型，并采用遗传算法对路径优化模型进行求解，通过实际案例应用与传统的穿越式拣货策略相对比，验证了模型的有效性。

Abstract： Taking the picking problem of product warehouse in aeronautical standard parts enterprises as the research object， a path optimization model aiming at minimizing the total picking time is established. Based on the characteristics of product warehouse in aeronautical standard parts enterprises， the practical case is compared with the traditional traversing picking strategy. The validity of the model is verified.

关键词：航空标准件;拣货路径优化;成品库

Key words： aerospace standard parts;order picking routing optimization;production warehouse

0  引言

航空标准件企业属于多品种、混批量的的制造型企业，近年来，随着航空工业的快速发展，航空标准件产品的数量和种类日益激增，企业传统的拣货作业模式已无法满足市场需求，导致企业成品库存周转效率低下，拣货作业是仓储管理中十分重要的一个环节，据统计，拣货作业所耗费的时间约占整个仓储作业所用时间的60%[1]，而拣货作业大量的时间耗费在货物的寻找过程中，因此，寻求最优的拣货路径，可以加快产品周转效率，对于进一步提升公司的快速响应能力具有重要的意义。

1959年，学者Dantzig G B和Ramser J H首次提出路径优化问题[2]。随着物流活动的日益增多，该类问题日益受到学者们的重视，学者Felix T.S.Chan等从仓储布局、存储策略和订单分配等三个角度出发，通过对于不同种组合下的策略进行仿真实验，从而得出有效的组合策略[3]。J Renaud等将储位分配与路径优化相结合，结合产品的特点合理安排储位和拣选路径，有效的减少了拣选距离[4]。Kulak O等将订单分批问题与路径优化问題相结合，并采用改进的禁忌搜索算法来寻求最佳的拣货路径[5]。国内学者李军将偏离度思想引入到路径优化方面，并与传统的穿越式策略和S型启发式算法通过仿真进行对比，验证模型的有效性[6]。刘建胜针对双区型仓库中拣货的特点，采用蚁群算法优化拣货路径，并与传统的穿越策略和S型启发式算法进行了比较，验证了算法的适用性[7]。

综上可知，学者们在拣货路径优化领域的研究中大多以最短拣货距离为优化目标，在计算最短距离时仅考虑两个货位点间的距离最短，并未将仓库入口到第一个拣货点的距离和最后一个拣货点到仓库出口的距离引入拣货模型，并不能真实的反应拣货实际距离;另一方面，以往的拣货模型仅考虑拣货的路径最短，并未将拣货过程中的拣货时间并未计算在内。因此，本文综合考虑拣货时间和拣货路径时间，以拣货总时间最短建立优化模型，从而更真实的反映整个拣货过程。

1  模型建立

1.1 问题描述

航空标准件企业成品根据产品类型分区管理，拣货单根据产品类型分派到各拣货员手中，在拣货过程中不存在跨区拣货的现象，因此，本文所研究的仓库类型为单区型仓库，拣货路径优化模型可以用图论描述为：成品仓库可视作一组网络，一个周期内某拣选单中有多个产品待拣选，即多个顶点构成的顶点集N，A为各顶点间的连接所构成的边集合，C=[dij]为距离矩阵，出入口为同一点，要求一名拣选人员或拣选设备进行拣选，从仓库出入口出发，完成该次拣选任务并返回到出入口构成闭合回路，在遍历每个待拣货点（每个点只经过一次）的同时保证总拣货时间最短。

1.2 模型假设

①拣货方式：航空标准件企业目前主要采用的是人到货的拣货模式（Picker to Part）、根据订单拣选系统生成的拣货单进行拣货，空闲等待的时间可以忽略不计。

②行走规则：每个拣货员的分管区域可视为单区型仓库，拣货员可以横向和纵向巷道行走。

③存储状态：每个货架的规格相同，即每个库位的大小、承载力均相同。本文研究的产品每个图号代表一类产品，且产品体积较小，因此每个库位可以完全存储一个图号的产品，每个库位仅有一个图号的产品。

④人工式拣货的仓库条件下，货架高度与拣货人员身高相近，忽略配货区货架的垂直高度，拣货人员在拣选作业中垂直方向上的位移可忽略不计。将货架视为单层货架。

⑤拣货执行过程中不存在缺货情况，即补货时间可视为瞬时的。

⑥每份拣货单的容量不能超过拣货员的最大拣货量。

1.3 变量描述与符号说明

1.3.1 仓库相关量描述

1.4 模型构建

1.4.1 拣货路径模型构建

2  模型求解

本文所研究的问题属于问题，采用遗传算法对模型进行求解，遗传算法的具体求解步骤如图3所示。

①确定拣货单中的待拣货产品坐标构成问题参数集。

②设定编码规则。拣选单中的待拣货货位总计n个，本文采用十进制编码规则对问题参数集进行编码，采用自然数序列{1，2，…，n}表示每个待拣货位的编号（每个货位编号唯一），由此构成一定序列的染色体。

③产生初始化种群。根据模型规则随机求解出一组50个包含计n个待拣货位的初始方案。

④适应度评估。适应度函数是仓储拣货人员遍历所有的待拣库位一次所行走的所用的时间。拣货路径的优化问题是以拣货总时间最小化为目标，可建立适应度函数评价求解结果与最优情景的接近程度，即找出适应度最大的染色体。

⑤选择操作。选择操作主要是指通过个体的适应度的优劣程度来决定个体的淘汰或者遺传，通过联赛选择法从种群中随机选择n个个体（种群中个体被选择的概率相同），并计算每个个体的适应度值，比较其适应度大小，选择适应度最大的个体进入下一代的种群。迭代多次，直到新的种群规模达到原来的种群规模。

⑥交叉操作。采用段交叉法以概率随机地交换染色体群中的两个个体的某些片段产生新的个体。

⑦变异操作。变异操作对遗传算法的局部搜索能力进行优化，从而维持遗传算法的群体的多样性，同时防止早熟现象的发生。采用对换变异操作。以pm的变异概率从当前代的种群中选择进行变异的个体，并随机选择两个不同的点，对这两个点的编号进行交换从而得到新的个体。

⑧是否满足停止准则。对形成的可行解的适应度进行判断，如果其适应度不再上升或者达到设定的相应的阀值，则结束迭代计算;否则继续计算或者改进遗传策略后再进行计算。

⑨输出最优解P（t+n）。在使用遗传算法进行n次迭代后，若满足目标最小化需求，则停止运算，输出最优拣货路径。

3  实例分析

H公司是我国航空工业集团下属的一家航空标准件制造三级供应商，随机选取某段时间内到达的1组拣货单，产品信息如表1所示，其中L1=0.5m，L2=0.5m，L3=0.5m，L4=1.75m，tm=3.4m，v=1.2m/s。

3.1 原有拣货模式拣货总时间

按订单顺序进行拣选时，每批拣选单按公司原有的穿越式策略进行拣货，设总拣选时间为T′，可求得拣货总时间为T′=2309.7s。

3.2 改进拣货模式拣货总时间

设置遗传算法种群规模为50，交叉概率为pc=0.9，变异概率为pm=0.1，迭代次数为500次，在VS2015软件中，通过C#编程求解可得，拣货作业顺序为P0-P1-P2-P7-P9-P8-P11-P10-P12-P13-P16-P15-P14-P20-P19-P18-P17-P4-P5-P6-P3-P0，设总拣选时间为，拣货总时间为T=2275.5s。

如图4所示，对比公司传统的拣货模式，可以节省拣货总时间，提高拣货效率。

4  总结

针对航空标准件企业的单区型仓库，以拣货总时间最短为优化目标，设计了路径优化模型，并采用GA算法通过企业实际案例进行求解，对比航空标准件企业传统的穿越式拣货模式，可以有效节省拣货时间，提高拣货效率，可为同类型制造企业规划拣货路径提供相应的决策参考。

参考文献：

[1]王转，陈国全.配送中心系统规划[M].北京：中国物资出版社，2003：148.

[2]Dantzig G B， Ramser J H. The Truck Dispatching Problem[J]. Management Science， 1959， 6（1）：80-91.

[3]Chan F T S， Chan H K . Improving the productivity of order picking of a manual-pick and multi-level rack distribution warehouse through the implementation of class-based storage[J]. Expert Systems with Applications， 2011， 38（3）：2686-2700.

[4] Renaud J ， Ruiz A . Improving product location and order picking activities in a distribution centre[J]. Journal of the Operational Research Society， 2008， 59（12）：1603-1613.

[5]Kulak O ， Sahin Y ， Taner M E . Joint order batching and picker routing in single and multiple-cross-aisle warehouses using cluster-based tabu search algorithms[J]. Flexible Services and Manufacturing Journal， 2012， 24（1）：52-80.

[6]李军，魏玲艳，李翔宇.基于偏离度的仓储中心拣货路径优化研究[J].辽东学院学报（社会科学版），2018，20（2）：29-37.

[7]刘建胜，熊峰，陈景坤，等.基于蚁群算法的双分区仓库拣货路径的优化[J].高技术通讯，2017，27（1）：72-80.