多区型仓库多复核台场景的拣货路径优化研究

doi:10.3969/j.issn.0255-8297.2021.04.006

摘要/Abstract

摘要： 与小型仓库传统的单出口、单复核台不同，大型仓库往往配设多复核台、多出口以提升拣货出库效率。该文提出了基于替换复核台的动态调整算法以解决多复核台场景下因起止点不确定而导致的遍历搜索困难的问题；并在此基础上给出了在多拣货员情况下多拣货单的路径优化与合理分配的动态调整策略，以满足大规模、复杂场景下的拣货作业要求。结合京东物流实例表明，所提出的基于替换复核台的动态调整算法计算效率更高，在同等条件下的拣货路径更短，拣货耗时更少，能够为仓库拣货提供更加准确的拣货路径规划。

关键词: 路径优化, 遗传算法, 替换复核台, 动态调整

Abstract: Different from traditional single-export and single-check stations in small warehouses, large warehouses are often equipped with multiple check stations and multiple outlets to improve the efficiency of warehouse picking and leaving. This article proposes a dynamic adjustment algorithm based on replacing review station to solve the difficulty in traversal search caused by the uncertainty of the start and end points in the scenario of multiple review stations. On this basis, dynamical adjustment strategies with path optimization and reasonable allocation of multi-task orders are provided to meet the requirement of picking operations in large-scale and complex scenarios. Compared with the example of Jingdong logistics, it is shown that the dynamic adjustment algorithm based on the replacement of review station proposed in this paper is more efficient, with shorter picking path, less picking time and more accurate warehouse picking under the same conditions.

Key words: route optimization, genetic algorithm, replacement review stations, dynamic adjustment

中图分类号:

TP181

叶楠, 毕忠勤, 魏恒达, 吴迪. 多区型仓库多复核台场景的拣货路径优化研究[J]. 应用科学学报, 2021, 39(4): 581-593.

YE Nan, BI Zhongqin, WEI Hengda, WU Di. Research on Optimizing Picking Route of Multi-zone Warehouse and Multi-checking Station[J]. Journal of Applied Sciences, 2021, 39(4): 581-593.

参考文献

[1] 孙军艳, 牛亚儒, 苏宝, 等. 双区型仓库动态拣货策略的设计及路径优化研究[J]. 包装工程, 2018, 39(23):1-8. Sun J Y, Niu Y R, Su B, et al. The design and path optimization of dynamic picking strategy of two-zone warehouse[J]. Packaging Engineering, 2018, 39(23):1-8. (in Chinese)
[2] Roodbergen K J, Koster R D. Routing order pickers in a warehouse with a middle aisle[J]. European Journal of Operational Research, 2001, 133(1):32-43.
[3] Vaughan T S. The effect of warehouse cross aisles on order picking efficiency[J]. International Journal of Production Research, 1999, 37(4), 881-897.
[4] 刘建胜, 欧阳昌峰, 涂海宁. 鱼骨型布局拣货路径多车调度混合优化方法[J]. 华中科技大学学报(自然科学版), 2020, 48(4):67-72. Liu J S, Ou Yang C F, Tu H N. Fish bone layout picking path multi-vehicle scheduling hybrid optimization method[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2020, 48(4):67-72. (in Chinese)
[5] Zhou H L, Song M L, Pedrycz W. A comparative study of improved GA and PSO in solving multiple traveling salesmen problem[J]. Applied Soft Computing, 2018, 64:564-580.
[6] Dhein G, Neto A F K. The multiple traveling salesman problem with backup coverage[J]. Electronic Notes in Discrete Mathematics, 2018, 66:135-142.
[7] Liao E, Liu C. A hierarchical algorithm based on density peaks clustering and ant colony optimization for traveling salesman problem[J]. IEEE Access, 2018, 6:38921-38933.
[8] Dhein G, Neto A F K. The multiple traveling salesman problem with backup coverage[J]. Electronic Notes in Discrete Mathematics, 2018, 66:135-142.
[9] 佘智勇, 庄健敏, 翟旭平. 双区型仓库拣选路径优化研究[J]. 工业控制计算机, 2018, 31(4):90-91, 94. She Z Y, Zhuang J M, Zhai X P. A study on the optimization of the selection path of dual-zone warehouse[J]. Industrial Control Computer, 2018, 31(4):90-91, 94. (in Chinese)
[10] 李悦. 基于随机需求的双区型仓库货位分配与拣货路径优化[J]. 综合运输, 2020, 42(6):85-89. Li Y. Two-zone warehouse location allocation and picking path optimization based on random demand[J]. China Transportation Review, 2020, 42(6):85-89. (in Chinese)
[11] Giannikas V, Lu W, Robertson B, et al. An interventionist strategy for warehouse order picking:Evidence from two case studies[J]. International Journal of Production Economics, 2017, 189:63-76.
[12] 孟鑫, 杨琴, 郝婷婷, 等. 不同订单分配和算法下的拣货路径优化组合[J]. 计算机工程与应用, 2020, 56(23):229-236. Meng X, Yang Q, Hao T T, et al. An optimized combination of picking paths under different order allocations and algorithms[J]. Computer Engineering and Applications, 2020, 56(23):229-236. (in Chinese)
[13] 孙军艳, 陈智瑞, 牛亚儒, 等. 基于嵌套遗传算法的拣货作业联合优化[J]. 计算机应用, 2020, 40(12):3687-3694. Sun J Y, Chen Z R, Niu Y R, et al. The picking operation is jointly optimized based on nested genetic algorithm[J]. Journal of Computer Applications, 2020, 40(12):3687-3694. (in Chinese)
[14] 李建斌, 周玮, 陈峰. B2C电子商务仓库拣货路径优化策略应用研究[J]. 运筹与管理, 2014, 23(1):7-14. Li J B, Zhou W, Chen F. B2C e-commerce warehouse picking path optimization strategy application research[J]. Operations Research and Management Science. 2014, 23(1):7-14. (in Chinese)
[15] Azadnia A H, Taheri S, Ghadimi P, et al. Order batching in warehouses by minimizing total tardiness:a hybrid approach of weighted association rule mining and genetic algorithms[J]. The Scientific World Journal, 2013:246578. DOI:10.1155/2013/246578
[16] 杨景祥. 货架式仓储中心货位分配及拣货路径优化研究[D]. 北京:北京交通大学, 2016.
[17] 于浩洋. 基于遗传算法的拣货路径优化方法[J]. 中国科技信息, 2019(8):91-94. Yu H Y. Picking path optimization method based on genetic algorithm[J]. China Science and Technology Information, 2019(8):91-94. (in Chinese)