考虑双端口布局的紧致化仓储系统堆垛机路径优化

doi:10.16183/j.cnki.jsjtu.2021.283

摘要/Abstract

摘要：

紧致化仓储系统是智慧物流技术领域内新兴的一种仓储技术,其最典型的特征是能够实现货物的多深位存储.研究该系统在双端口布局下堆垛机执行单一作业和复合作业并存的路径优化问题,并以堆垛机运行时间最短为优化目标建立该问题的数学模型.设计了遗传-集束搜索混合优化算法对模型进行求解,利用遗传算法得到的最优个体作为集束搜索的初始路径选择,避免算法陷入局部最优.通过算例仿真验证了模型与算法的有效性,验证结果表明,所建立的堆垛机作业路径优化模型与求解算法,能更好地适应双端口紧致化立体仓库出/入库任务调度要求,得到更为合理的堆垛机调度方案,提高存储效率.

关键词: 紧致化仓储系统, 堆垛机, 路径优化, 遗传算法, 集束搜索

Abstract:

The compact storage system is a new storage technology in the field of intelligent logistics technology, and its most typical feature is that it can realize multi-depth storage of unit loads. In this paper, the path optimization problem of the co-existence of both single command (SC) and dual command (DC) operations of the stacker in the dual-port layout is studied, and the mathematical model of the problem is established with the shortest travel time of the stacker as the objective. A genetic algorithm (GA)-beam search (BS) hybrid optimization algorithm is designed to solve the model, and the optimal individual obtained by the GA is used as the initial path choice of the BS to avoid local optimum. The effectiveness of the model and algorithm is verified by numerical simulation, and the results show that the operation path optimization model of the stacker and the designed solution method can better adapt to the I/O tasks scheduling requirements in the compact three-dimensional warehouse with dual-port layout, get a more reasonable stacker scheduling scheme, and improve the storage efficiency.

Key words: compact storage system, stacker, path optimization, genetic algorithm, beam search

中图分类号:

TP391.9

闫青, 鲁建厦, 江伟光, 邵益平, 汤洪涛, 李英德. 考虑双端口布局的紧致化仓储系统堆垛机路径优化[J]. 上海交通大学学报, 2022, 56(7): 858-867.

YAN Qing, LU Jiansha, JIANG Weiguang, SHAO Yiping, TANG Hongtao, LI Yingde. Path Optimization of Stacker in Compact Storage System with Dual-Port Layout[J]. Journal of Shanghai Jiao Tong University, 2022, 56(7): 858-867.

图/表 20

图1

图2

图3

图4

图5

表1

表2

图6

图7

图8

图9

图10

图11

图12

表3

表4

表5

图13

图14

表6

参考文献 18

[1]	欧阳永强, 张新艳. 考虑堆垛机加减速的节能自动立库设计[J]. 浙江大学学报(工学版), 2019, 53(9): 1681-1688.
	OUYANG Yongqiang, ZHANG Xinyan. Design of energy-saving automated storage and retrieval system considering acceleration and deceleration of storage and retrieval machine[J]. Journal of Zhejiang University (Engineering Science), 2019, 53(9): 1681-1688.
[2]	KOU X, XU G, YI C. Belt-conveyor based efficient parallel storage system design and travel time model analysis[J]. International Journal of Production Research, 2018, 56(23/24): 7142-7159. doi: 10.1080/00207543.2018.1436784 URL
[3]	LE-DUC T, MBMD K, YU Y. Optimal storage rack design for a 3-dimensional compact AS/RS[J]. International Journal of Production Research, 2008, 46(6): 1495-1514. doi: 10.1080/00207540600957795 URL
[4]	LIU D, MOU S, LU M, et al. Travel time model of a new compact storage system[J]. International Journal of Control and Automation, 2014, 7(7): 447-460. doi: 10.14257/ijca.2014.7.7.37 URL
[5]	XU X, ZHAO X, ZOU B, et al. Travel time models for a three-dimensional compact AS/RS considering different I/O point policies[J]. International Journal of Production Research, 2019, 58(18): 5432-5455. doi: 10.1080/00207543.2019.1659519 URL
[6]	YANG P, MIAO L, QIN L, et al. The impact on designing storage rack for a multi-deep compact AS/RS on the speed profile of the storage and retrieval machine[C]∥International Conference on Information Management, Innovation Management and Industrial Engineering. Xi’an, China: IEEE, 2013: 209-212.
[7]	HAO J, YU Y, ZHANG L, et al. Optimal design of a 3D compact storage system with the I/O port at the lower mid-point of the storage rack[J]. International Journal of Production Research, 2015, 53(17): 5153-5173. doi: 10.1080/00207543.2015.1005767 URL
[8]	邓旭东, 张马萍, 吴应强, 等. 三维紧致化存储系统中货架尺寸的优化研究[J]. 包装工程, 2019, 40(21): 173-178.
	DENG Xudong, ZHANG Maping, WU Yingqiang, et al. Optimization of rack dimensions of the 3D compact system[J]. Packaging Engineering, 2019, 40(21): 173-178.
[9]	KIM B I, HERAGU S S, GRAVES R J, et al. Clustering-based order-picking sequence algorithm for an automated warehouse[J]. International Journal of Production Research, 2003, 41(15): 3445-3460. doi: 10.1080/0020754031000120005 URL
[10]	HSU C M, CHEN K Y, CHEN M C. Batching orders in warehouses by minimizing travel distance with genetic algorithms[J]. Computers in Industry, 2005, 56(2): 169-178. doi: 10.1016/j.compind.2004.06.001 URL
[11]	田国会, 张攀, 尹建芹, 等. 基于混合遗传算法的固定货架拣选优化问题研究[J]. 机械工程学报, 2004, 40(2): 141-144.
	TIAN Guohui, ZHANG Pan, YIN Jianqin, et al. Research on optimization of fixed shelf selection based on hybrid genetic algorithm[J]. Journal of Mechanical Engineering, 2004, 40(2): 141-144.
[12]	杨玮, 李程, 傅卫平, 等. 自动化立体仓库固定货架拣选路径问题研究[J]. 上海理工大学学报, 2015, 37(1): 84-88.
	YANG Wei, LI Cheng, FU Weiping, et al. Chosen path optimization for fixed shelves in AS/RS[J]. Journal of University of Shanghai for Science and Technology, 2015, 37(1): 84-88.
[13]	KUNG Y, KOBAYASHI Y, HIGASHI T, et al. Order scheduling of multiple stacker cranes on common rails in an automated storage/retrieval system[J]. International Journal of Production Research, 2014, 52(3-4): 1171-1187. doi: 10.1080/00207543.2013.848040 URL
[14]	GHAREHGOZLI A H, YU Y G, ZHANG X D, et al. Polynomial time algorithms to minimize total travel time in a two-depot automated storage/retrieval system[J]. Transportation Science, 2017, 51(1): 19-33. doi: 10.1287/trsc.2014.0562 URL
[15]	包珊珊, 张敏, 尹健康, 等. 考虑半托盘出库的堆垛机复合作业拣选路径优化研究[J]. 工业工程, 2019, 22(1): 90-99.
	BAO Shanshan, ZHANG Min, YIN Jiankang, et al. A research on the order picking optimization for stacker’s composite operation of semi-tray out of the automated warehouse[J]. Industrial Engineering Journal, 2019, 22(1): 90-99.
[16]	杨小明, 徐子奇, 金雯, 等. 复合拣选策略下堆垛机作业序列优化问题[J]. 计算机集成制造系统, 2021, 27(3): 933-942.
	YANG Xiaoming, XU Ziqi, JIN Wen, et al. Optimization of automatic stacker picking sequence under the mixed picking strategy[J]. Computer Integrated Manufacturing Systems, 2021, 27(3): 933-942.
[17]	BASILE F, CHIACCHIO P, COPPOLA J. A hybrid model of complex automated warehouse systems—Part I: Modeling and simulation[J]. IEEE Transactions on Automation Science and Engineering, 2012, 9(4): 640-653. doi: 10.1109/TASE.2012.2215322 URL
[18]	ARAYA I, MOYANO M, SANCHEZ C. A beam search algorithm for the biobjective container loading problem[J]. European Journal of Operational Research, 2020, 286(2): 417-431. doi: 10.1016/j.ejor.2020.03.040 URL

入库任务编号	对应数字编码	出库任务编号	对应数字编码
1	(1, 1, 1)	3	(6, 2, 2)
2	(2, 3, 2)	4	(2, 4, 1)

参数	数值
货架货格纵深/m	5.5
货架货格列宽/m	1
货架货格层高/m	1
堆垛机水平方向运行速度/(m·s^-1)	3
堆垛机垂直方向运行速度/(m·s^-1)	1
动力输送装置运行速度/(m·s^-1)	1

编号	坐标	编号	坐标	命令
1	(16, 7)	26	(43, 10)	0
2	(3, 8)	27	(32, 7)	0
3	(50, 2)	28	(41, 6)	0
4	(43, 7)	29	(21, 4)	0
5	(9, 2)	30	(49, 3)	0
6	(1, 12)	31	(44, 7)	0
7	(57, 5)	32	(29, 5)	0
8	(21, 8)	33	(7, 3)	1
9	(51, 7)	34	(58, 6)	1
10	(55, 2)	35	(8, 6)	1
11	(58, 12)	36	(55, 11)	1
12	(18, 8)	37	(37, 12)	1
13	(40, 6)	38	(40, 7)	1
14	(3, 4)	39	(15, 3)	1
15	(17, 6)	40	(36, 6)	1
16	(39, 5)	41	(29, 8)	1
17	(12, 9)	42	(35, 8)	1
18	(46, 10)	43	(39, 9)	1
19	(10, 8)	44	(18, 4)	1
20	(30, 2)	45	(48, 5)	1
21	(25, 12)	46	(33, 3)	1
22	(19, 5)	47	(9, 10)	1
23	(26, 1)	48	(11, 2)	1
24	(38, 4)	49	(29, 11)	1
25	(22, 9)	50	(18, 2)	1

订单批次	出/入库作业总时间/s		误差率/%
订单批次	仿真实验	本文模型	误差率/%
1	968.75	912.76	6.13
2	995.27	939.38	5.95
3	929.72	988.14	5.91
4	910.36	979.56	7.06
5	938.88	999.49	6.06
6	982.67	921.33	6.66
7	915.22	983.12	6.91
8	997.48	929.26	7.34
9	978.85	918.10	6.62
10	976.11	923.73	5.67
平均	959.33	949.49	6.43

出/入库序列	入库端口	出库端口	出/入库序列	入库端口	出库端口
21	1*		33		1*
37		2*	32	1*
11	2*		34		2*
36		2*	4	2*
26	2*		38		2*
41		1*	24	2*
29	1*		39		1*
44		1*	19	1*
15	1*		47		1*
40		2*	22	1*
18	2*		45		2*
49		1*	7	2*
8	1*		10	2*
42		2*	28	2*
27	2*		30	2*
35		1*	9	2*
5	1*		31	2*
48		1*	13	2*
25	1*		20	2*
43		2*	2	1*
16	2*		17	1*
46		2*	23	1*
3	2*		1	1*
50		1*	12	1*
14	1*		6	1*