“货到人”系统订单拣选和分拣协同优化问题

doi:10.16182/j.issn1004731x.joss.24-0705

摘要/Abstract

摘要：

针对“货到人”系统中带时间窗的订单拣选和分拣协同问题，建立以分拣批次数量最小为目标的数学模型，结合问题特点提出基于“分类装载”策略的混合变邻域搜索算法(hybrid variable neighborhood search，HVNS)进行求解。数值实验结果表明：HVNS算法能够在缩短求解时间的前提下获得高质量的解；不同订单结构对分拣AGV装载能力的利用效果不同；在测试的实验环境下，通过与先拣选后分拣的传统作业模式相比，协同作业模式在完工时间上可以缩短约31%，在订单满足率上可以提升约38%。

关键词: “货到人”系统, 拣选分拣协同, 自动导引小车, 变邻域搜索算法, 时间窗

Abstract:

To improve the order picking and sorting collaboration with time windows in the "goods-to-person" system, a mathematical model aiming to minimize the number of sorting batches was established. With the characteristics of this issue considered, a hybrid variable neighborhood search (HVNS) algorithm based on the "classified loading" strategy was proposed for solutions. The numerical experimental results show that the HVNS algorithm can obtain high-quality solutions while shortening the solution time; different order structures have varying effects on the utilization of the loading capacity of sorting automated guided vehicles (AGVs); under the tested experimental conditions, the collaborative operation mode can reduce the makespan by approximately 31% and increase the order fulfillment rate by approximately 38% compared with the traditional operation mode of picking followed by sorting.

Key words: "goods-to-person" system, picking and sorting collaboration, automated guided vehicle, variable neighborhood search algorithm, time window

中图分类号:

TP391.1

任亮,周泽榕,马云峰 . “货到人”系统订单拣选和分拣协同优化问题[J]. 系统仿真学报, 2025, 37(12): 3128-3139.

Ren Liang,Zhou Zerong,Ma Yunfeng . Optimization of Order Picking and Sorting Coordintion in “Goods-to-person” System[J]. Journal of System Simulation, 2025, 37(12): 3128-3139.

图/表 11

图1

图2

表1

表2

算例参数

描述	小规模	中大规模
订单数量S	${10,30,50,70,80}$	$100,150, ⋯, 300$
订单包含SKU数量 $q s$	${1,2, 3}$	${1,2, 3}$
投递口数量D	${3,5, 7}$	${10,15,20}$
拣选货架数R	${5,7, 9}$	${15,20,30}$

表2

表3

HVNS与Gurobi结果对比

S	R		D		Gurobi		HVNS		$G a p / %$
S	R		D		$t / s$	$f$	$t / s$	$f$	$G a p / %$
10		5		3	0.11	6	2.88	6	0
10		7		5	0.13	6	3.02	6	0
10		9		7	0.15	7	3.14	7	0
30		5		3	1.17	15	9.61	16	6.67
30		7		5	1.24	17	10.12	17	0
30		9		7	1.36	16	11.60	17	6.25
50		5		3	6.18	25	19.53	25	0
50		7		5	9.65	26	21.34	24	-7.69
50		9		7	32.52	26	19.27	26	0
70		5		3	23.76	36	27.09	36	0
70		7		5	38.79	36	32.72	36	0
70		9		7	70.36	38	35.31	38	0
80		5		3	58.36	39	28.77	39	0
80		7		5	1 800+	—	47.28	40	—
80		9		7	1 800+	—	53.41	42	—

表3

表4

HVNS、VNS和GA结果对比

S	R	D	HVNS				VNS				贪心算法
S	R	D	CPU/s	$A v g$	$b e s t$	$S t d$	CPU/s	$A v g$	$b e s t$	$S t d$	CPU/s	$A v g$	$b e s t$	$S t d$
100	15	10	98.14	53	50	3.03	221.70	54	51	3.04	0.20	58	54	3.56
100	20	15	98.22	55	53	1.71	225.14	54	52	1.87	0.31	61	56	2.07
100	30	20	138.32	57	53	3.66	262.44	58	55	2.45	0.33	64	61	3.46
150	15	10	148.23	78	74	2.17	322.25	79	74	2.93	0.30	84	80	1.20
150	20	15	149.22	78	77	2.01	329.85	79	77	1.90	0.35	86	81	2.16
150	30	20	140.45	80	76	4.18	302.81	82	76	9.88	0.32	90	82	2.56
200	15	10	198.45	106	100	4.48	257.82	108	101	4.70	0.36	113	107	5.98
200	20	15	196.61	104	101	3.03	435.15	105	101	3.32	0.55	111	108	3.07
200	30	20	185.44	111	105	4.58	272.31	108	106	4.14	0.42	120	114	3.51
250	15	10	238.27	131	125	4.39	524.63	133	126	4.95	0.47	137	134	5.02
250	20	15	240.88	130	123	2.97	535.78	131	126	4.12	0.48	138	133	3.06
250	30	20	228.29	136	126	5.48	509.27	139	128	6.46	0.59	146	137	6.40
300	15	10	280.67	160	153	4.36	379.36	161	155	4.90	0.58	165	161	4.51
300	20	15	283.25	159	151	6.46	625.89	162	153	7.21	0.66	172	160	8.46
300	30	20	293.26	163	150	7.32	889.82	174	154	9.98	0.73	175	162	8.65

表4

图3

图4

图5

表5

作业模式完工时间

S	R	D	$f$	$T 2 / s$	$T 1 / s$	$G a p / %$
10	5	3	5	127	155	22.05
10	7	5	7	161	217	34.78
30	10	5	17	276	408	47.83
30	15	7	16	381	479	25.72
50	10	7	24	424	506	19.34
50	15	10	27	459	633	37.91
60	12	7	32	509	652	28.09
60	16	9	33	536	734	36.94

表5

表6

订单满足率

紧急程度	时间窗 $[a s, e s]$ 生成范围	HVNS		I-FCFS		传统模式
紧急程度	时间窗 $[a s, e s]$ 生成范围	完成订单	满足率/%	完成订单	满足率/%	完成订单	满足率/%
1	$a s ~ U (1,25) e s ~ U (a s + t h, a s + t h + x) x ~ U (10,30)$	195	97.5	194	97.0	142	71.0
2	$a s ~ U (1,20) e s ~ U (a s + t h, a s + t h + x) x ~ U (10,25)$	192	96.0	190	95.0	120	60.0
3	$a s ~ U (1,15) e s ~ U (a s + t h, a s + t h + x) x ~ U (5,20)$	164	82.0	158	79.0	51	25.5

表6

参考文献 26

[1]	付建林, 张恒志, 张剑, 等. 自动导引车调度优化研究综述[J]. 系统仿真学报, 2020, 32(9): 1664-1675.
	Fu Jianlin, Zhang Hengzhi, Zhang Jian, et al. Review on AGV Scheduling Optimization[J]. Journal of System Simulation, 2020, 32(9): 1664-1675.
[2]	袁瑞萍, 邹顺洁, 潘路可, 等. 基于移动机器人的拣选系统货架动态储位分配研究[J]. 系统科学与数学, 2024, 44(3): 780-791.
	Yuan Ruiping, Zou Shunjie, Pan Luke, et al. Research on Dynamic Storage Allocation of Shelves in Robotic Mobile Fulfillment Systems[J]. Journal of Systems Science and Mathematical Sciences, 2024, 44(3): 780-791.
[3]	江宏, 王玉, 林振强. 物流系统集成与自动化领域: 市场信心有待恢复, 行业需要转型升级[J]. 物流技术与应用, 2023, 28(12): 56-73.
[4]	黄刚. 亚马逊仓库-不为人知的亚马逊10大物流技术[J]. 金卡工程, 2016(增1): 33-36.
[5]	蔡永石. 物联网技术在智慧物流中的应用[J]. 无线互联科技, 2022, 19(17): 33-35.
	Cai Yongshi. Application of Internet of Things Technology in Smart Logistics[J]. Wireless Internet Technology, 2022, 19(17): 33-35.
[6]	中国仓储与配送协会研究室. 2024仓储配送业发展与趋势展望[J]. 物流技术与应用, 2024, 29(7): 50-57.
	China Association of Warehousing and Distribution. Outlook on the Development and Trends of Warehousing and Distribution Industry in 2024[J]. Logistics & Material Handling, 2024, 29(7): 50-57.
[7]	Zhuang Yanling, Zhou Yun, Yuan Yufei, et al. Order Picking Optimization with Rack-moving Mobile Robots and Multiple Workstations[J]. European Journal of Operational Research, 2022, 300(2): 527-544.
[8]	Boysen Nils, Fedtke Stefan, Weidinger Felix. Optimizing Automated Sorting in Warehouses: The Minimum Order Spread Sequencing Problem[J]. European Journal of Operational Research, 2018, 270(1): 386-400.
[9]	李腾, 冯珊, 宋君, 等. "货到人"拣选系统机器人任务分配的鲁棒双层规划模型[J]. 运筹与管理, 2019, 28(12): 25-34.
	Li Teng, Feng Shan, Song Jun, et al. Robust Bi-level Programming Model for Robot Task Assignment of "Rack-to-picker" Picking System[J]. Operations Research and Management Science, 2019, 28(12): 25-34.
[10]	袁瑞萍, 王慧玲, 孙利瑞, 等. 基于物流AGV的"货到人"订单拣选系统任务调度研究[J]. 运筹与管理, 2018, 27(10): 133-138.
	Yuan Ruiping, Wang Huiling, Sun Lirui, et al. Research on the Task Scheduling of "Goods to Picker" Order Picking System Based on Logistics AGV[J]. Operations Research and Management Science, 2018, 27(10): 133-138.
[11]	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.
[12]	李昆鹏, 刘腾博, 李文莉. 改进自适应遗传算法求解"货到人"拣选系统订单分批问题[J]. 机械工程学报, 2023, 59(4): 308-317.
	Li Kunpeng, Liu Tengbo, Li Wenli. Improved Adaptive Genetic Algorithm for Order Batching of "Part-to-picker" Picking System[J]. Journal of Mechanical Engineering, 2023, 59(4): 308-317.
[13]	李昆鹏, 刘腾博, 贺冰倩, 等. "货到人"拣选系统中AGV路径规划与调度研究[J]. 中国管理科学, 2022, 30(4): 240-251.
	Li Kunpeng, Liu Tengbo, He Bingqian, et al. A Study on Routing and Scheduling of Automated Guided Vehicle in "Cargo-to-picker" System[J]. Chinese Journal of Management Science, 2022, 30(4): 240-251.
[14]	Fedtke Stefan, Boysen Nils. Layout Planning of Sortation Conveyors in Parcel Distribution Centers[J]. Transportation Science, 2017, 51(1): 3-18.
[15]	余娜娜, 李铁克, 王柏琳, 等. 自动化分拣仓库中多AGV调度与路径规划算法[J]. 计算机集成制造系统, 2020, 26(1): 171-180.
	Yu Nana, Li Tieke, Wang Bailin, et al. Multi-AGVs Scheduling and Path Planning Algorithm in Automated Sorting Warehouse[J]. Computer Integrated Manufacturing Systems, 2020, 26(1): 171-180.
[16]	余娜娜, 李铁克, 王柏琳. 自动化分拣仓库中多自动导引小车在线协同调度算法[J]. 计算机集成制造系统, 2022, 28(11): 3340-3353.
	Yu Nana, Li Tieke, Wang Bailin. Multi-AGV Online Collaborative Scheduling Algorithm in Automated Sorting Warehouse[J]. Computer Integrated Manufacturing Systems, 2022, 28(11): 3340-3353.
[17]	镇璐, 谭哲一, 萧理阳, 等. 面向双层自动分拣系统的包裹分拣优化模型与算法研究[J]. 中国管理科学, 2021, 29(7): 171-180.
	Zhen Lu, Tan Zheyi, Xiao Liyang, et al. Research on Parcel Sorting Optimization Model and Algorithm for Double-layer Automatic Sorting Systems[J]. Chinese Journal of Management Science, 2021, 29(7): 171-180.
[18]	郭超, 陈香玲, 郭鹏, 等. 基于通用变邻域搜索的多AGV分拣调度优化[J]. 河北科技大学学报, 2021, 42(5): 523-534.
	Guo Chao, Chen Xiangling, Guo Peng, et al. General Variable Neighborhood Search for the Multi-AGV Scheduling Problem with Sorting Operations[J]. Journal of Hebei University of Science and Technology, 2021, 42(5): 523-534.
[19]	Kong Xiang, Yang Xuan, Peng K L, et al. Cyber Physical System-enabled Synchronization Mechanism for Pick-and-sort Ecommerce Order Fulfilment[J]. Computers in Industry, 2020, 118: 103220.
[20]	Jiang Min, Huang G Q. Intralogistics Synchronization in Robotic Forward-reserve Warehouses for E-commerce Last-mile Delivery[J]. Transportation Research Part E: Logistics and Transportation Review, 2022, 158: 102619.
[21]	Zhang Jun, Wang Xuping, Huang Kai. On-line Scheduling of Order Picking and Delivery with Multiple Zones and Limited Vehicle Capacity[J]. Omega, 2018, 79: 104-115.
[22]	张腾飞, 胡蓉, 钱斌, 等. 学习型变邻域搜索算法求解运输-装配协同优化问题[J]. 系统仿真学报, 2023, 35(6): 1260-1277.
	Zhang Tengfei, Hu Rong, Qian Bin, et al. Learning Variable Neighborhood Search Algorithm for Transportation-assembly Collaborative Optimization Problem[J]. Journal of System Simulation, 2023, 35(6): 1260-1277.
[23]	Bukchin Yossi, Khmelnitsky Eugene, Yakuel Pini. Optimizing a Dynamic Order-picking Process[J]. European Journal of Operational Research, 2012, 219(2): 335-346.
[24]	Adulyasak Yossiri, Cordeau Jean-François, Jans Raf. Optimization-based Adaptive Large Neighborhood Search for the Production Routing Problem[J]. Transportation Science, 2014, 48(1): 20-45.
[25]	Xie Lin, Thieme Nils, Krenzler Ruslan, et al. Introducing Split Orders and Optimizing Operational Policies in Robotic Mobile Fulfillment Systems[J]. European Journal of Operational Research, 2021, 288(1): 80-97.
[26]	Boysen Nils, Schwerdfeger Stefan, Stephan Konrad. A Review of Synchronization Problems in Parts-to-picker Warehouses[J]. European Journal of Operational Research, 2023, 307(3): 1374-1390.

订单编号	订单信息	SKU编号	数量	时间窗	投递口
Order1	S1	001	1	[3,8]	h1
Order2	S2	003	1	[2,6]	h2
Order2	S2	006	2	[2,6]	h2
Order3	S3	007	1	[4,10]	h7
	S3	011	1		h7
	S3	021	1		h7
…