考虑拆分策略的智能仓库订单分拣建模与优化

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

系统仿真学报 ›› 2024, Vol. 36 ›› Issue (3): 564-577.doi: 10.16182/j.issn1004731x.joss.23-0422

考虑拆分策略的智能仓库订单分拣建模与优化

徐毓泽¹(), 张林鍹¹^,²(), 李惠³, 葛明⁴, 何莞依⁴

^1.新疆大学电气工程学院, 新疆乌鲁木齐 830000
^2.清华大学自动化系, 北京 100089
^3.中央财经大学信息学院, 北京 102206
^4.香港工业人工智能及机械人研发中心, 香港 999077

收稿日期:2023-04-07 修回日期:2023-06-13 出版日期:2024-03-15 发布日期:2024-03-14
通讯作者: 张林鍹 E-mail:1072979947@qq.com;lxzhang@mail.tsinghua.edu.cn
第一作者简介:徐毓泽(1996-)，男，硕士生，研究方向为生产计划排程、物流分拣。E-mail：1072979947@qq.com
基金资助:
国家重点研发计划(2018YFB1703103);香港创科平台InnoHK资助项目(20213000116);新疆维吾尔自治区研究生科研创新项目(XJ2022G042)

Modeling and Optimization of Smart Warehouse Order Sorting Considering Splitting Strategy

Xu Yuze¹(), Zhang Linxuan¹^,²(), Li Hui³, Ge Ming⁴, He Wanyi⁴

^1.School of Electrical Engineering, Xinjiang University, Urumqi 830000, China
^2.Department of Automation, Tsinghua University, Beijing 100089, China
^3.School of Information, Central University of Finance and Economics, Beijing 102206, China
^4.Hong Kong Industrial Artificial Intelligence and Robotics Centre, Hong Kong 999077, China

Received:2023-04-07 Revised:2023-06-13 Online:2024-03-15 Published:2024-03-14
Contact: Zhang Linxuan E-mail:1072979947@qq.com;lxzhang@mail.tsinghua.edu.cn

摘要/Abstract

摘要：

针对一种两类订单混合分拣的自动小车分拣问题，考虑其在订单分拣过程中出现的分拣AGV(automatic guided vehicle)堵塞和人工收集站闲置的现象，提出一种订单拆分的策略及拆分后子订单批次调整的方法，并以总订单完工时间最小化为优化目标，建立了订单拆分的订单分拣整数规划模型；提出一种改进离散灰狼优化算法，将订单分批、批次排序以及下架库位选取3个子问题进行联合优化。数值实验结果表明，订单拆分策略使总订单完工时间显著减少，并且通过与经典算法以及其他同类型算法的对比，验证了所提算法的优越性。

关键词: 订单拆分, 订单分批, 批次排序, 离散灰狼优化算法, 自动小车分拣系统

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

中图分类号:

TP278

徐毓泽,张林鍹,李惠等 . 考虑拆分策略的智能仓库订单分拣建模与优化[J]. 系统仿真学报, 2024, 36(3): 564-577.

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

图/表 14

图1

图2

图3

图4

图5

表1

表2

图6

表3

表4

图7

图8

图9

图10

参考文献 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]	张朝阳, 徐莉萍, 李健, 赵义豪, 何奎. 基于改进狼群算法的柔性作业车间调度研究[J]. 系统仿真学报, 2023, 35(3): 534-543.
[2]	尤一琛, 王艳, 纪志成. 基于博弈论的柔性作业车间动态调度研究[J]. 系统仿真学报, 2021, 33(11): 2579-2588.
[3]	蔡敏, 王艳, 纪志成. 基于多策略融合量子粒子群算法的MOFFJSP研究[J]. 系统仿真学报, 2021, 33(11): 2615-2626.
[4]	张祥, 王艳, 纪志成. 基于动态交互层的柔性作业车间动态调度问题研究[J]. 系统仿真学报, 2020, 32(11): 2129-2137.
[5]	沈鹏, 王艳, 纪志成, 张建华. 超启发式DE算法求解零等待发酵工艺调度[J]. 系统仿真学报, 2020, 32(11): 2235-2243.
[6]	李俊萱, 王艳, 纪志成. 基于混合QPSO的模糊柔性作业车间调度问题研究[J]. 系统仿真学报, 2020, 32(10): 2010-2021.
[7]	戴月明, 王明慧, 王春, 王艳. 骨干双粒子群算法求解柔性作业车间调度问题[J]. 系统仿真学报, 2017, 29(6): 1268-1276.
[8]	李林瑛, 卢睿, 李绍华, 景雨, 刁建华. 有滞留时间约束的集束型装备在线调度方法[J]. 系统仿真学报, 2017, 29(2): 337-345.
[9]	徐军辉, 王艳. 基于改进教与学算法的离散制造车间能效优化[J]. 系统仿真学报, 2016, 28(12): 3019-3026.
[10]	陈彦, 王艳. 基于改进主成分分析法的离散制造能耗分析[J]. 系统仿真学报, 2016, 28(12): 3087-3094.
[11]	潘春荣, 黎良. 基于可重入加工组合设备的建模与调度研究[J]. 系统仿真学报, 2016, 28(4): 772-782.
[12]	张晓星, 王艳, 严大虎, 纪志成. 改进的混合蛙跳算法求解柔性作业车间调度[J]. 系统仿真学报, 2017, 29(9): 2093-2099.
[13]	单鑫, 王艳, 纪志成. 基于参数知识鸽群算法的离散车间能效优化[J]. 系统仿真学报, 2017, 29(9): 2140-2148.
[14]	陈超, 王艳, 严大虎, 纪志成. 面向能耗的柔性作业车间动态调度研究[J]. 系统仿真学报, 2017, 29(9): 2168-2175.
[15]	卢绍文, 罗小川. “起重机+过跨车”铁水物流多场景仿真[J]. 系统仿真学报, 2017, 29(10): 2549-2555.

考虑拆分策略的智能仓库订单分拣建模与优化

Modeling and Optimization of Smart Warehouse Order Sorting Considering Splitting Strategy

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 23

相关文章 15

编辑推荐

Metrics

本文评价