考虑工作量平衡的大型商超订单分批与拣货路径优化研究

展开
  • (1大连海事大学 交通运输工程学院,辽宁 大连 116026;2北京顺丰速运有限公司,北京,101300)
刘进平(1976 — ),女,博士,讲师,研究方向:仓储优化。徐宁(1998 — ),女,硕士,研究方向:仓储物流。E-mail:liujping@dlmu.edu.cn。

网络出版日期: 2025-01-23

基金资助

辽宁省“兴辽英才计划”项目(XLYC1902071),智能船舶安全航行岸基监测预警关键技术研究

On-line order picking optimization considering workload balance for large supermarkets

Expand
  • (1.Transportation Engineering College, Dalian Maritime University, Dalian 116026, China;2.Beijing SF Express Co., Ltd, Beijing  101300, China)

Online published: 2025-01-23

摘要

在大型商超线上订单分拣系统中,考虑分拣员之间工作量平衡,研究了订单分批与拣货路径优化问题。针对拣货员数量有限的“先拣后分”仓店一体分批拣货场景,构建考虑工作量平衡和拣货效率双目标的订单分批与拣货路径优化模型,结合K-means聚类和贪婪算法的最近邻点策略设计改进的NSGA-Ⅱ算法进行求解。基于沃尔玛等超市运作情况设置拣货布局和算例参数,通过不同规模的算例验证了模型正确性和算法有效性。实验结果表明,以极差作为平衡指标的双目标订单分批与拣货路径优化模型不仅可以实现工作量平衡而且对拣货效率的负面影响更小;当种群规模设置为50和迭代次数为100时算法可以获得优质解;基于“先拣后分”的订单分批与路径优化策略比按单分拣可以平均缩短订单最终完成时间44.37%。结论表明,双目标模型和算法有利于在工作量平衡和拣货效率两个目标之间取得平衡,既可以提高拣货效率,又可以满足拣货员之间工作量平衡的要求。

本文引用格式

刘进平, 徐宁 . 考虑工作量平衡的大型商超订单分批与拣货路径优化研究[J]. 大连海事大学学报, 2025 , 51(2) : 87 -96 . DOI: 10.16411/j.cnki.issn1006-7736.2025.02.010

Abstract

 In the online order picking system of large supermarkets, considering the workload balance among pickers, the optimization of order batching and picking route was studied. For the scenario of " sort-after-pick" batch picking in large supermarkets with a limited number of pickers during peak periods, a dual-objective optimization model was constructed with two objectives of minimizing total completion time and minimizing the range in completion times. According to the problem feature and the dual-objective solution method, an improved NSGA-II algorithm was designed by combining the K-means clustering algorithm and the nearest neighbor strategy of the greedy algorithm. Based on the practical operation of large supermarkets such as Walmart, a picking layout and case parameters were set. The correctness of the model and the effectiveness of the algorithm were verified through examples of different scales. Numerical experiments show that range as workload balance criteria in a dual-objective model not only achieve workload balance but also has fewer negative impacts on picking efficiency. A further sensitivity analysis indicates that a population size of 50 and an iteration number of 100 are conducive to obtaining quality solutions. Comparative experiments conducted on datasets of different sizes reveals that the "sort-after-pick" method can reduce the average completion time of orders by 44.37% in comparison to the single order picking strategy. The conclusion indicates that the dual-objective model and algorithm can achieve a balance between workload balance and picking efficiency, improving picking efficiency while satisfying workload balance requirement from pickers’ perspective.

参考文献

[1]VAN GILS T, RAMAEKERS K, CARIS A, et al. Designing efficient order picking systems by combining planning problems: State-of-the-art classification and review[J]. European Journal of Operational Research, 2018, 267(1): 1-15.
[2]HINTSCH T, IRNICH S. Exact solution of the soft-clustered vehicle-routing problem[J]. European Journal of Operational Research, 2020, 280(1): 164-178.
[3]AERTS B, CORNELISSENS T, SöRENSEN K. The joint order batching and picker routing problem: Modelled and solved as a clustered vehicle routing problem[J]. Computers & Operations Research, 2021, 129:105168.
[4]DEFRYN C, SöRENSEN K. A fast two-level variable neighborhood search for the clustered vehicle routing problem[J]. Computers & Operations Research, 2017, 83:78-94.
[5]MALT, P, HARTL R F, and VIDAL T. Workload Equity in Vehicle Routing Problems: A Survey and Analysis[J]. Transportation Science, 2017, 52(2): 239-260.
[6]LACOMME P, PRINS C, RAMDANE-CHERIF W. Competitive memetic algorithms for arc routing problems [J]. Annals of Operations Research, 2004, 131(1): 159-185.
[7]CHIANG W C, CHENG C Y. Considering the performance bonus balance in the Vehicle Routing Problem with soft time windows[J]. Procedia Manufacturing, 2017, 11:2156-2163. 
[8]程传兴.社会主义公平与效率的实现条件[J].河南大学学报(社会科学版),2004,44(06):26-29.
CHENG C X. Conditions for actualizing the socialist justice and efficiency[J]. Journal of Henan University (Social Sciences),2004,44(06):26-29. 
[9]JOZEFOWIEZ N, SEMET F, TALBI E G. An evolutionary algorithm for the vehicle routing problem with route balancing[J]. European Journal of Operational Research, 2009, 195(3): 761-769.
[10]李珍萍, 杨光, 韩倩倩. 考虑工作量平衡的成品油二次配送车辆路径问题[J]. 系统仿真学报, 2022, 34(02): 221-233.
LI Z P, YANG G, HAN Q Q. Vehicle routing problem with refined oil secondary distribution considering workload balance[J]. Journal of System Simulation, 2022, 34(02): 221-233. (in Chinese)
[11]LI J, FANG Y, TANG N. A cluster-based optimization framework for vehicle routing problem with workload balance[J]. Computers & Industrial Engineering, 2022, 169:108221.
[12]REITER P, GUTJAHR W J. Exact hybrid algorithms for solving a bi-objective vehicle routing problem[J]. Central European Journal of Operations Research, 2012,20(1):19–43.
[13]SARPONG B M, ARTIGUES C, JOZEFOWIEZ N. Column generation for bi-objective vehicle routing problems with a min-max objective[C]. ATMOS-13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems.2013,33: 137-149.
[14]孙丽君, 石海洋, 胡祥培. 考虑司机工作量平衡的成品油配送优化[J]. 系统工程理论与实践, 2018, 38(03): 677-686.
SUN L J, SHI H Y, HU X P. An optimization method of product oil distribution considering driver's workload balance[J]. Systems Engineering--Theory and Practice, 2018, 38(03): 677-686.(in Chinese)
[15]VAN GILS T, RAMAEKERS K, BRAEKERS K, et al. Increasing order picking efficiency by integrating storage, batching, zone picking, and routing policy decisions[J]. International Journal of Production Economics, 2018, 197: 243-261.
[16]JANE C C, LAIH Y W. A clustering algorithm for item assignment in a synchronized zone order picking system[J]. European Journal of Operational Research, 2005, 166:489-496.
[17]SAYLAM S, ÇELIK M, SüRAL H. The min–max order picking problem in synchronized dynamic zone-picking systems[J]. International Journal of Production Research, 2023, 61(7): 2086-2104.
[18]VANHEUSDEN S, VAN GILS T, CARIS A, et al. Operational workload balancing in manual order picking[J]. Computers & Industrial Engineering, 2020, 141:106269.
[19]ARDJMAND E, SHAKERI H, SINGH M, et al. Minimizing order picking makespan with multiple pickers in a wave picking warehouse[J]. International Journal of Production Economics, 2018, 206:169-183.
[20]DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-II [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
[21]胡小建, 袁丁.基于鱼骨型仓库布局的多车拣选路径问题优化[J]. 工业工程, 2022, 25(01): 45-53.
HU X J, YUAN D. An optimization of multi-vehicle picking routing problem based on fishbone warehouse layout [J]. Industrial Engineering Journal, 2022, 25(01): 45-53.(in Chinese)
[22]PIETRI N O, CHOU X, LOSKE D, et al. The buy-online-pick-up-in-store retailing model: optimization strategies for in-store picking and packing[J]. Algorithms, 2021, 14(12): 350.
文章导航

/