Modeling and Optimization of Smart Warehouse Order Sorting Considering Splitting Strategy

doi:10.16182/j.issn1004731x.joss.23-0422

Abstract

Abstract:

For an automatic vehicle sorting problem involving mixed sorting of two types of orders, an order splitting strategy and a method for batch adjustment of sub-orders after splitting are proposed by considering the phenomena of blockage of automatic guided vehicles (AGVs) and idleness of manual collection stations in the order sorting process. In addition, with the optimization objective of minimizing the total order completion time, an order sorting integer planning model with order splitting is established. An improved discrete grey wolf optimization algorithm is proposed to jointly optimize the three sub-problems of order batching, batch sorting, and product unloading location selection. Numerical experimental results show that the order splitting strategy leads to a significant reduction in the total order completion time, and the superiority of the proposed algorithm is verified by comparing it with the classical algorithm and other algorithms of the same type.

Key words: order splitting, order batching, batch sorting, discrete grey wolf optimization algorithm, automatic vehicle sorting system

CLC Number:

TP278

Xu Yuze, Zhang Linxuan, Li Hui, Ge Ming, He Wanyi. Modeling and Optimization of Smart Warehouse Order Sorting Considering Splitting Strategy[J]. Journal of System Simulation, 2024, 36(3): 564-577.

Figures/Tables 14

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Table 1

Table 2

Fig. 6

Table 3

Table 4

Fig. 7

Fig. 8

Fig. 9

Fig. 10

References 23

1	Boysen Nils, René de Koster, Weidinger Felix. Warehousing in the E-commerce Era: A Survey[J]. European Journal of Operational Research, 2019, 277(2): 396-411.
2	Winkelhaus Sven, Grosse Eric H. Logistics 4.0: A Systematic Review Towards a New Logistics System[J]. International Journal of Production Research, 2020, 58(1): 18-43.
3	van Gils Teun, Ramaekers Katrien, An Caris, 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.
4	Winkelhaus Sven, Zhang Minqi, Grosse Eric H, et al. Hybrid Order Picking: A Simulation Model of a Joint Manual and Autonomous Order Picking System[J]. Computers & Industrial Engineering, 2022, 167: 107981.
5	廉胤东, 谢巍. 基于视觉引导多AGV系统的改进A*路径规划算法[J]. 控制与决策, 2021, 36(8): 1881-1890.
	Lian Yindong, Xie Wei. Improved A* Path Planning Algorithm for Vision-Guided Multi-AGV System[J]. Control and Decision, 2021, 36(8): 1881-1890.
6	Liu Yubang, Ji Shouwen, Su Zengrong, et al. Multi-objective AGV Scheduling in an Automatic Sorting System of an Unmanned (Intelligent) Warehouse by Using Two Adaptive Genetic Algorithms and a Multi-adaptive Genetic Algorithm[J]. PloS one, 2019, 14(12): e0226161.
7	He Xueting, Quan Hao, Lin Wanlong, et al. AGV Scheduling Optimization for Medical Waste Sorting System[J]. Scientific Programming, 2021, 2021: 4313749.
8	张镜辉. 图书馆AGV智能分拣系统构成分析与规划设计-以汕头市图书馆为例[J]. 图书馆学研究, 2021(4): 23-28.
	Zhang Jinghui. Composition Analysis and Planning Design of Library AGV Intelligent Sorting System-A Case Study of Shantou Library[J]. Researches on Library Science, 2021(4): 23-28.
9	Zou Wenqiang, Pan Quanke, Wang Ling, et al. Efficient Multiobjective Optimization for an AGV Energy-efficient Scheduling Problem with Release Time[J]. Knowledge-based Systems, 2022, 242: 108334.
10	余娜娜, 李铁克, 王柏琳, 等. 自动化分拣仓库中多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.
11	Gibson D R, Sharp G P. Order Batching Procedures[J]. European Journal of Operational Research, 1992, 58(1): 57-67.
12	吴仁超, 贺建军, 李欣, 等. 基于混合元启发式算法的订单分批问题[J]. 控制与决策, 2022, 37(8): 2110-2118.
	Wu Renchao, He Jianjun, Li Xin, et al. Hybrid Metaheuristic Algorithm for Order Batching Problem[J]. Control and Decision, 2022, 37(8): 2110-2118.
13	Jiang Xiaowei, Sun Lijun, Zhang Yuankai, et al. Order Batching and Sequencing for Minimising the Total Order Completion Time in Pick-and-sort Warehouses[J]. Expert Systems with Applications, 2022, 187: 115943.
14	李珍萍, 田宇璇, 卜晓奇, 等. 无人仓系统订单分批问题及K-max聚类算法[J]. 计算机集成制造系统, 2021, 27(5): 1506-1517.
	Li Zhenping, Tian Yuxuan, Bu Xiaoqi, et al. Order Batching Problem of Unmanned Warehouse System and K-max Clustering Algorithm[J]. Computer Integrated Manufacturing Systems, 2021, 27(5): 1506-1517.
15	潘晓, 鹿冬娜, 王书海. 基于订单拆分的容量限制商超配送路径规划[J]. 华东师范大学学报(自然科学版), 2022(5): 147-164.
	Pan Xiao, Lu Dongna, Wang Shuhai. Capacitated Route Planning for Supermarket Distribution Based on Order Splitting[J]. Journal of East China Normal University(Natural Science), 2022(5): 147-164.
16	Briant Olivier, Cambazard Hadrien, Cattaruzza Diego, et al. An Efficient and General Approach for the Joint Order Batching and Picker Routing Problem[J]. European Journal of Operational Research, 2020, 285(2): 497-512.
17	万明重, 蒋忠中, 秦绪伟, 等. 考虑拆分策略的智能仓库订单拣选优化问题[J]. 计算机集成制造系统, 2021, 27(6): 1809-1819.
	Wan Mingzhong, Jiang Zhongzhong, Qin Xuwei, et al. Optimization for Order Picking Problem with Splitting Policy in Smart Warehouses[J]. Computer Integrated Manufacturing Systems, 2021, 27(6): 1809-1819.
18	Zhong Shuya, Giannikas V, Merino J, et al. Evaluating the Benefits of Picking and Packing Planning Integration in E-commerce Warehouses[J]. European Journal of Operational Research, 2022, 301(1): 67-81.
19	Weidinger Felix, Boysen Nils. Scattered Storage: How to Distribute Stock Keeping Units All Around a Mixed-shelves Warehouse[J]. Transportation Science, 2018, 52(6): 1412-1427.
20	Gademann Noud, Van de Steef Velde. Order Batching to Minimize Total Travel Time in a Parallel-aisle Warehouse[J]. IIE Transactions, 2005, 37(1): 63-75.
21	Mirjalili S, Seyed Mohammad Mirjalili, Lewis A. Grey Wolf Optimizer[J]. Advances in Engineering Software, 2014, 69: 46-61.
22	李维刚, 李阳, 赵云涛, 等. 基于改进灰狼算法的粒子滤波算法研究[J]. 系统仿真学报, 2021, 33(1): 37-45.
	Li Weigang, Li Yang, Zhao Yuntao, et al. Research on Particle Filter Algorithm Based on Improved Grey Wolf Algorithm[J]. Journal of System Simulation, 2021, 33(1): 37-45.
23	顾九春, 姜天华, 朱惠琦. 多目标离散灰狼优化算法求解作业车间节能调度问题[J]. 计算机集成制造系统, 2021, 27(8): 2295-2306.
	Gu Jiuchun, Jiang Tianhua, Zhu Huiqi. Energy-Saving Job Shop Scheduling Problem with Multi-objective Discrete Grey Wolf Optimization Algorithm[J]. Computer Integrated Manufacturing Systems, 2021, 27(8): 2295-2306.

参数	数值
巷道(条)	40
货架长/m	7.9
货架高/m	2.8
传送带缓存区存量(件)	3
周转AGV数量(台)	100
分拣AGV数量(台)	100
传送带速度/(m/s)	1
周转AGV速度/(m/s)	1.5
分拣AGV速度/(m/s)	1.5
自动包装机(个)	14
人工收集站(个)	3
产品交接时间/s	5
机械手下架操作时间/s	10~18
每张子订单包含的产品数量(个)	20
人工订单转移时间/s	30
平均每件人工订单产品的包装时间/s	1.2

算例	订单数量	总产品数量	SKU 数量	人工订单数量	人工订单产品数量
1	500	6 000	2 300	2	645
2	500	8 000	3 000	4	1 206
3	1 000	11 000	5 000	4	1 237
4	1 000	15 000	6 000	6	1 933
5	1 500	18 000	7 000	8	2 310
6	1 500	20 000	7 000	10	3 092

算例	IDGWO(不拆)		IDGWO		p₁/%
算例	t/h	t₁/min	t/h	t₁/min	p₁/%
1	1.228	4.20	0.920	4.36	25.08
2	1.450	4.40	1.274	5.57	12.14
3	2.162	7.01	1.666	8.14	22.94
4	2.640	9.24	1.951	10.95	26.10
5	3.513	12.07	2.529	14.72	28.01
6	3.984	18.49	2.843	15.98	28.64

算例	GA		SFOA		GWO		IDGWO		p₂/%	p₃/%	p₄/%
算例	t/h	t₁/min	t/h	t₁/min	t/h	t₁/min	t/h	t₁/min	p₂/%	p₃/%	p₄/%
1	1.010	2.42	0.936	2.63	0.997	2.28	0.920	4.36	8.91	1.71	7.72
2	1.622	3.49	1.301	3.27	1.629	3.07	1.274	5.57	21.46	2.08	21.79
3	1.861	4.56	1.679	5.14	1.829	3.86	1.666	8.14	10.48	0.77	8.91
4	2.531	8.61	2.005	6.69	2.515	5.70	1.951	10.95	22.92	2.69	22.43
5	3.073	11.91	2.548	9.08	3.079	7.35	2.529	14.72	17.70	0.75	17.86
6	3.865	10.13	2.885	10.08	3.850	8.80	2.843	15.98	26.44	1.46	26.16

[1]	Chaoyang Zhang, Liping Xu, Jian Li, Yihao Zhao, Kui He. Flexible Job-Shop Scheduling Problem Based on Improved Wolf Pack Algorithm [J]. Journal of System Simulation, 2023, 35(3): 534-543.
[2]	You Yichen, Wang Yan, Ji Zhicheng. Research on Flexible Job-shop Dynamic Scheduling Based on Game Theory [J]. Journal of System Simulation, 2021, 33(11): 2579-2588.
[3]	Cai Min, Wang Yan, Ji Zhicheng. Research on MOFFJSP Based on Multi-strategy Fusion Quantum Particle Swarm Optimization [J]. Journal of System Simulation, 2021, 33(11): 2615-2626.
[4]	Zhang Xiang, Wang Yan, Ji Zhicheng. Research on Dynamic Flexible Job Shop Scheduling Problem Based on Dynamic Interaction Layer [J]. Journal of System Simulation, 2020, 32(11): 2129-2137.
[5]	Shen Peng, Wang Yan, Ji Zhicheng, Zhang Jianhua. Hyper-heuristic DE Algorithm for Solving Zero-wait Fermentation Process Schedulinge [J]. Journal of System Simulation, 2020, 32(11): 2235-2243.
[6]	Li Junxuan, Wang Yan, Ji Zhicheng. Research on Fuzzy Flexible Job Shop Scheduling Problem Based on Hybrid QPSO [J]. Journal of System Simulation, 2020, 32(10): 2010-2021.
[7]	Dai Yueming, Wang Minghui, Wang Chun, Wang Yan. Double Bare Bones Particle Swarm Algorithm for Solving Flexible Job-shop Scheduling Problem [J]. Journal of System Simulation, 2017, 29(6): 1268-1276.
[8]	Li Linying, Lu Rui, Li Shaohua, Jing Yu, Diao Jianhua. Online Scheduling Method of Cluster Tools with Residency Time Constraint [J]. Journal of System Simulation, 2017, 29(2): 337-345.
[9]	Xu Junhui, Wang Yan. Energy Efficiency Optimization for Discrete Manufacturing Workshop Based on Discrete Teaching-learning-based Optimization Algorithm [J]. Journal of System Simulation, 2016, 28(12): 3019-3026.
[10]	Chen Yan, Wang Yan. Energy Consumption Analysis of Discrete Manufacturing Based on Improved Principal Component Analysis Method [J]. Journal of System Simulation, 2016, 28(12): 3087-3094.
[11]	Pan Chunrong, Li Liang. Research on Modeling and Scheduling of Cluster Tools with Reentrant Process [J]. Journal of System Simulation, 2016, 28(4): 772-782.
[12]	Zhang Xiaoxing, Wang Yan, Yan Dahu, Ji Zhicheng. Improved Shuffled Frog-Leaping Algorithm for Solving Flexible Job Shop Scheduling Problem [J]. Journal of System Simulation, 2017, 29(9): 2093-2099.
[13]	Shan Xin, Wang Yan, Ji Zhicheng. Energy Efficiency Optimization for Discrete Workshop Based on Parametric Knowledge Pigeon Swarm Algorithm [J]. Journal of System Simulation, 2017, 29(9): 2140-2148.
[14]	Chen Chao, Wang Yan, Yan Dahu, Ji Zhicheng. Research on Dynamic Flexible Job Shop Scheduling Problem for Energy Consumption [J]. Journal of System Simulation, 2017, 29(9): 2168-2175.
[15]	Lu Shaowen, Luo Xiaochuan. Design of Multi-Scenario Simulation of Molten Iron Logistics System with Cranes and Cross-Train AGVs [J]. Journal of System Simulation, 2017, 29(10): 2549-2555.