智能仓库中多AGV在线任务指派与全局路径规划问题研究

doi:10.16381/j.cnki.issn1003-207x.2023.0429

Abstract

Abstract:

The rapid development of artificial intelligence has accelerated the intelligent transformation of warehouses， more and more warehouses have introduced a large number of AGVs to replace manual operations. The online global scheduling problem of multi-AGV in intelligent warehouses is a hot and challenging topic. It integrates task assignment and conflict-free routing， and also needs to consider constraints such as bidirectional network， conflict-free， AGV battery limitation， task time windows， etc. The objective of this problem is to minimize the sum of AGV running time and penalty cost of AGVs waiting at grids. Exploiting the structure of the problem， a mixed-integer linear programming model is established first. Meanwhile， a multi-AGV task assignment and path planning collaborative optimization algorithm is designed： firstly， an assignment algorithm is designed based on the dual priority rules of task and AGV. Secondly， considering multiple collision situations， five strategies are introduced to improve the A* algorithm and a rescheduling mechanism is set to globally plan the AGV path. To verify the performance of our algorithm， a branch-and-cut algorithm is introduced to solve small-scale problems. The results of 12 small-scale instances show that the branch-and-cut algorithm can improve the lower bound of CPLEX by 59.89% on average. The average gap between the results of our heuristic algorithm and the lower bound of the branch-and-cut algorithm is 7.23%. The results of 96 large-scale instances show that all five strategies are valid. Compared to traditional algorithms， the results are improved by our algorithm by an average of 27.69%， the solution time is shortened to within 2s， and the solution efficiency is improved by 130.01% on average. The research is not only applicable to the scheduling decision of AGVs in intelligent warehouses， but also can be extended to closed scenarios with relatively regular networks and high automation degrees， such as production workshops and automated docks， providing a reference for multi-vehicle scheduling problems with centralized global control.

Key words: intelligent warehouse, automated guided vehicles, online scheduling, path planning, branch-and-cut

CLC Number:

F252

Kunpeng Li, Xuefang Han. Research on Online Task Assignment and Global Path Planning Problem of Multi-AGV in Intelligent Warehouses[J]. Chinese Journal of Management Science, 2025, 33(3): 264-276.

Figures/Tables 13

参数符号	定义
$N$	栅格集合， $N = {1,2, …, n 0 · n 1}$ ， $n 0$ 表示划分的栅格行数， $n 1$ 表示方向栅格列数
$f i'$	辅助0-1参数，若栅格i是货架栅格则为1，否则为0（ $i ∈ N$ ）
$f i j 2$	辅助0-1参数，若栅格i与栅格j连通则为1，否则为0（ $i, j ∈ N$ ）
$(X i, Y i)$	表示栅格i的坐标，其中， $X i$ 表示横坐标， $Y i$ 表示纵坐标， $i = n 1 · (X i - 1) + Y i$
$M$	任务集合， $M = {1,2, …, \| M \|}$ ， $M$ 表示任务数量
$s m 、 f m$	任务 $m$ 对应的货架栅格序号和拣选站台栅格序号
$l m$	任务 $m$ 对应的最晚服务时刻
$K$	路网中的AGV集合， $K = {1,2, …, \| K \|}$ ， $\| K \|$ 表示AGV数量
$c k, o k$	分别表示调度前AGV k当前位置对应的栅格序号，和对应的停靠区栅格序号
$c t$	AGV单次转向惩罚
$v t$	AGV单位栅格通行时间
$m a x T k$	AGV $k$ 到达阈值电量前剩余的工作时间
T	调度周期
B	足够大的正整数，用于公式线性化
决策变量
$q m k$	0-1变量，当任务m分配给AGV $k$ 时为1，否则为0
$x m$	整数变量，表示任务m的延误时间
$x m 1$	整数变量，表示完成任务m的时间
$y k i j t P$	0-1变量，开始执行任务前，AGV $k$ 在时刻t从栅格 $i$ 到达栅格j时为1，否则为0
$y k i j t D$	0-1变量，执行任务过程中，AGV $k$ 在时刻t从栅格 $i$ 到达栅格j时为1，否则为0
$y k i j t F$	0-1变量，完成任务后，当AGV $k$ 在时刻t从栅格 $i$ 到达栅格j时为1，否则为0
$z k i j t$	0-1变量，当AGV $k$ 在时刻t从栅格 $i$ 到达栅格j时为1，否则为0

算例	Obj1_1	Obj1_2	Obj1_3	Obj1_4	Obj1_5	Time1_1	Time1_2	Time1_3	Time1_4	Time1_5
10-3-2	67.00	67.67	67.67	66.67	66.67	0.00	0.00	0.00	0.00	0.00
10-3-3	88.67	87.00	87.00	87.00	87.00	0.00	0.01	0.00	0.02	0.00
10-3-4	126.00	118.67	118.67	116.00	118.67	0.00	0.00	0.00	0.00	0.00
10-5-4	126.33	119.33	119.33	122.00	122.67	0.01	0.02	0.01	0.01	0.00
10-5-5	153.00	285.00	149.67	151.00	152.00	0.01	0.00	0.02	0.01	0.00
10-5-6	181.67	177.00	269.33	176.33	176.67	0.00	0.00	0.00	0.00	0.01
10-7-5	165.00	172.33	172.33	173.67	168.33	0.01	0.01	0.02	0.01	0.00
10-7-7	403.67	215.33	215.33	212.33	210.33	0.01	0.01	0.01	0.01	0.00
10-7-8	631.67	252.67	252.67	242.33	243.00	0.00	0.00	0.00	0.00	0.00
10-8-6	184.67	183.33	183.33	184.33	184.00	0.04	0.01	0.01	0.01	0.00
10-8-8	425.33	383.67	383.67	256.00	233.33	0.01	0.01	0.01	0.01	0.00
10-8-9	251.33	239.33	237.33	230.67	225.67	0.00	0.00	0.00	0.00	0.02
20-20-16	897.67	859.00	853.67	819.33	814.33	0.02	0.06	0.02	0.02	0.03
20-20-20	1134.67	1055.33	1033.00	1007.33	990.00	0.03	0.04	0.02	0.03	0.03
20-20-24	1236.00	1127.67	1125.67	1106.33	1101.00	0.01	0.01	0.01	0.01	0.01
20-24-19	1147.67	1075.00	1088.33	1078.33	1047.33	0.02	0.03	0.03	0.03	0.04
20-24-24	1382.00	1228.33	1228.67	1199.67	1185.67	0.04	0.03	0.03	0.03	0.04
20-24-28	1561.33	1419.33	1397.00	1370.67	1343.00	0.02	0.02	0.02	0.02	0.01
20-30-24	1456.00	1344.00	1342.33	1277.67	1252.33	0.03	0.03	0.03	0.03	0.04
20-30-30	1934.33	1779.33	1755.67	1516.00	1486.33	0.04	0.04	0.04	0.04	0.06
20-30-36	1892.67	1977.33	1896.33	1781.00	1769.33	0.03	0.02	0.03	0.02	0.26
20-40-32	2664.67	2104.00	2094.67	1910.67	1849.67	0.09	0.05	0.05	0.07	0.08
20-40-40	2631.00	2404.67	2273.33	2209.00	2218.33	0.08	0.06	0.06	0.08	0.11
20-40-48	3111.67	2540.67	2534.00	2700.33	2522.00	0.05	0.04	0.04	0.04	0.03
40-40-32	3463.67	3217.33	3204.67	3105.00	3094.33	0.08	0.07	0.09	0.08	0.12
40-40-40	4211.00	3793.00	3793.00	3657.33	3638.67	0.12	0.11	0.09	0.08	0.14
40-40-48	4268.00	3952.33	3979.00	3929.67	3919.33	0.07	0.07	0.07	0.07	0.20
40-48-38	4544.67	3953.67	3946.33	3868.33	3873.00	0.13	0.09	0.10	0.10	0.17
40-48-48	5573.67	4772.67	4779.00	4497.67	4493.00	0.29	0.11	0.11	0.11	0.21
40-48-57	5678.67	4992.67	5050.00	4964.33	4964.00	0.11	0.09	0.10	0.09	0.27
40-60-48	5712.33	5097.67	5096.33	4882.67	4910.33	0.25	0.15	0.15	0.15	0.27
40-60-60	6938.67	6029.33	6042.33	5710.67	5647.33	0.93	0.26	0.22	0.19	0.29
40-60-72	6818.00	5812.33	5819.00	5823.00	5825.67	0.24	0.12	0.13	0.12	0.16
40-80-64	8414.67	6882.00	6797.33	6603.67	6543.00	1.75	0.65	0.29	0.31	0.50
40-80-80	10171.33	8203.00	8173.67	7622.00	7682.33	3.21	0.91	0.33	0.32	0.53
40-80-96	10313.67	9094.00	8908.67	8822.33	8664.00	0.29	0.23	0.25	0.22	0.19
60-60-48	7371.67	6751.67	6750.00	6552.00	6558.67	0.68	0.30	0.19	0.19	0.32
60-60-60	9176.67	8072.33	8082.33	7719.00	7713.33	0.54	0.24	0.23	0.24	0.41
60-60-72	9491.33	8386.33	8411.00	8278.33	8260.67	0.23	0.19	0.19	0.18	0.22

References 17

1	Yan R D， Jackson L， Dunnett S. A study for further exploring the advantages of using multi-load automated guided vehicles［J］. Journal of Manufacturing Systems， 2020， 57： 19-30.
2	Jia X， Meng M Q-H. A survey and analysis of task allocation algorithms in multi-robot systems［C］// Proceedings of 2013 IEEE international conference on robotics and biomimetics （ROBIO）， Shenzhen， China，December 12-14， IEEE， 2013： 2280-2285.
3	Xu W X， Guo S S， Li X X， et al. A dynamic scheduling method for logistics tasks oriented to intelligent manufacturing workshop［J］. Mathematical Problems in Engineering， 2019， 2019（1）： 1-18.
4	Polten L， Emde S. Scheduling automated guided vehicles in very narrow aisle warehouses［J］. Omega， 2021， 99： 1-20.
5	Chawla V K， Chanda A K， Angra S， et al. Simultaneous dispatching and scheduling of multi-load AGVs in FMS-A simulation study［J］. Materials Today： Proceedings， 2018， 5（11）： 25358-25367.
6	Heger J， Voss T. Reducing mean tardiness in a flexible job shop containing AGVs with optimized combinations of sequencing and routing rules［J］. Procedia CIRP， 2019，81：1136-1141.
7	Singh N， Dang Q V， Akcay A， et al. A matheuristic for AGV scheduling with battery constraints［J］. European Journal of Operational Research， 2022， 298（3）： 855-873.
8	Fransen K J C， Eekelen J A W M V， Pogromsky A， et al. A dynamic path planning approach for dense， large， grid-based automated guided vehicle systems［J］. Computers & Operations Research， 2020， 123： 1-10.
9	张丹露，孙小勇，傅顺，等. 智能仓库中的多机器人协同路径规划方法［J］. 计算机集成制造系统， 2018， 24（2）：410-418.
	Zhang D L， Sun X Y， Fu S， et al. Cooperative path planning in multi-robots for intelligent warehouse［J］. Computer Integrated Manufacturing Systems， 2018， 24（2）：410-418.
10	张新艳，邹亚圣. 基于改进A*算法的自动导引车无碰撞路径规划［J］. 系统工程理论与实践， 2021， 41（1）： 240-246.
	Zhang X Y， Zou Y S. Collision-free path planning for automated guided vehicles based on improved A* algorithm［J］. Systems Engineering-Theory & Practice， 2021， 41（1）： 240-246.
11	李昆鹏，刘腾博，阮炎秋. 半导体生产车间智能AGV路径规划与调度［J］. 计算机集成制造系统， 2022， 28（9）： 2970-2980.
	Li K P， Liu T B， Run Y Q. Intelligent AGV routing scheduling with applications in semi-conductor production［J］. Computer Integrated Manufacturing Systems， 2022， 28（9）： 2970-2980.
12	李昆鹏，刘腾博，贺冰倩，等. “货到人”拣选系统中AGV路径规划与调度研究［J］. 中国管理科学， 2022， 30（4）： 240-251.
	Li K P， Liu T B， He B Q， 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.
13	Wang Z H， Zeng Q C. A branch-and-bound approach for AGV dispatching and routing problems in automated container terminals［J］. Computers & Industrial Engineering， 2022， 166： 1-25.
14	余娜娜，李铁克，王柏琳. 自动化分拣仓库中多自动导引小车在线协同调度算法［J］. 计算机集成制造系统， 2022， 28（11）： 3340-3353.
	Yu N N， Li T K， Wang B L. Multi-AGV online collaborative scheduling algorithm in automated sorting warehouse［J］. Computer Integrated Manufacturing Systems， 2022， 28（11）： 3340-3353.
15	王江华，楼佩煌，钱晓明. 基于改进遗传算法的AGVS单双向混合路径规划［J］. 机械设计与制造工程， 2015， 44（6）： 20-26.
	Wang J H， Lou P H， Qian X M. Configuring mixed uni/bidirectional guide-path network for automated guided vehicle system based on improved genetic algorithm［J］. Machine Design and Manufacturing Engineering， 2015， 44（6）： 20-26.
16	Kim C W， Tanchocoj J M A. Operational control of a bidirectional automated guided vehicle system［J］. International Journal of Production Research， 1993， 31（9）： 2123-2138.
17	Lam E， Bodic P L， Harabor D， et al. Branch-and-cut-and-price for multi-agent path finding［J］. Computers & Operations Research， 2022， 144： 1-13.

路网规模	AGV数量	订单量/AGV数量	每种规模算例数目
5×5	{3，4，5}	0.8，1	1
8×8	{4，6，8}	0.8，1	1
10×10	{3，5，7，10}	0.8，1，1.2	3
20×20 40×40 60×60	单列栅格数× {1，1.2，1.5，2}	0.8，1，1.2	3

算例	CPLEX				Branch-and-cut				MA-TAPPCOA		Δ1（%）	Δ2（%）
算例	LB1	Time1	LB1-1800秒	LB1-5400秒	LB2	Time2	LB2-1800秒	LB2-5400秒	Obj	Time3	Δ1（%）	Δ2（%）
5-3-2	22.00	258	22.00	22.00	22.00	83	22.00	22.00	22.00	0.002	0.00	0.00
5-3-3	18.31	3600	18.28	20.45	34.00	3600	34.00	34.00	34.00	0.002	85.69	0.00
5-4-3	20.47	3600	18.44	24.56	34.00	3600	34.00	34.00	34.00	0.002	66.10	0.00
5-4-4	26.44	3600	26.44	26.56	39.00	3600	39.00	39.00	41.00	0.002	47.50	5.13
5-5-4	31.38	3600	30.79	31.97	33.82	3600	32.23	33.82	38.00	0.014	7.78	12.36
5-5-5	31.96	3600	31.81	35.36	44.00	3600	44.00	44.00	47.00	0.069	37.67	6.82
8-4-3	35.22	3600	34.91	35.22	52.25	3600	52.25	52.25	59.00	0.003	48.36	12.91
8-4-4	30.73	3600	28.05	31.26	63.00	3600	63.00	63.00	65.00	0.002	105.01	3.17
8-6-5	40.26	3600	39.89	40.33	81.00	3600	81.00	81.00	96.00	0.04	101.19	18.52
8-6-6	50.07	3600	49.80	50.38	94.00	3600	94.00	94.00	98.00	0.007	87.74	4.26
8-8-6	56.32	3600	56.13	56.42	89.71	3600	89.71	89.71	102.00	0.047	59.29	13.69
8-8-8	76.03	3600	72.50	76.57	131.00	3600	131.00	131.00	144.00	0.029	72.30	9.92
Ave.	—	—	—	—	—	—	—	—	—	—	59.89	7.23

算例	1	2	3	4	算例	1	2	3	4
10-3-2	53.67	53.67	53.67	53.67	40-40-32	2836.00	2821.67	2815.00	2879.67
10-3-3	69.67	67.67	69.67	69.67	40-40-40	3333.67	3392.00	3393.67	3375.67
10-3-4	96.67	163.67	210.00	127.67	40-40-48	3608.00	4359.33	4495.67	4088.67
10-5-4	97.33	99.67	96.00	97.33	40-48-38	3565.33	3496.00	3547.33	3564.67
10-5-5	118.00	118.00	112.67	116.67	40-48-48	4120.00	4135.33	4198.67	4217.00
10-5-6	143.67	295.00	256.00	219.33	40-48-57	4571.00	5245.67	5392.67	4844.00
10-7-5	134.67	135.67	132.67	134.33	40-60-48	4465.33	4412.00	4356.00	4430.00
10-7-7	166.33	172.00	162.00	164.67	40-60-60	5171.33	5143.33	5143.67	5189.00
10-7-8	198.67	322.33	285.33	227.33	40-60-72	5331.33	6804.33	7133.67	6086.33
10-8-6	141.33	137.33	137.00	142.67	40-80-64	5936.67	6030.00	5918.33	5945.67
10-8-8	177.67	177.33	180.67	178.33	40-80-80	6917.33	7179.33	6910.00	6992.00
10-8-9	180.00	338.67	253.00	248.67	40-80-96	7818.67	9110.67	9716.67	9293.67
Ave.	131.47	173.42	162.39	148.36	Ave.	4806.22	5177.47	5251.78	5075.53
20-20-16	690.00	719.33	701.00	679.33	60-60-48	6160.33	6071.00	6023.33	6084.00
20-20-20	831.33	875.00	863.00	853.00	60-60-60	7236.00	7156.33	7509.00	7384.67
20-20-24	951.67	1203.67	1637.33	1267.33	60-60-72	7770.67	9021.33	9541.33	8638.00
20-24-19	904.00	937.67	857.33	894.67	60-72-57	7323.33	7269.67	7441.67	7336.00
20-24-24	1008.67	1062.67	1019.33	1015.67	60-72-72	8615.67	8681.00	9112.67	8744.67
20-24-28	1163.00	1558.00	1664.33	1422.67	60-72-86	9497.33	10634.67	11838.67	10859.33
20-30-24	1069.67	1083.67	1116.33	1100.00	60-90-72	9765.33	9644.00	9780.67	9784.33
20-30-30	1267.33	1298.00	1350.67	1304.67	60-90-90	10752.33	11005.33	11755.67	11068.00
20-30-36	1541.00	1916.00	2161.00	1837.00	60-90-108	11957.00	12990.00	14865.33	14170.33
20-40-32	1587.67	1506.33	1520.67	1509.00	60-120-96	12728.00	12604.67	13000.00	12921.00
20-40-40	1847.67	1713.67	1789.67	1962.00	60-120-120	14311.33	14759.33	15368.00	15132.00
20-40-48	2184.67	2697.00	3372.33	2679.33	60-120-144	16120.00	17628.67	20043.67	17832.33
Ave.	1253.89	1380.92	1504.42	1377.06	Ave.	10186.44	10622.17	11356.67	10829.56

AGV数量/单列栅格数	单车总成本				单车等待成本				单车转向次数
AGV数量/单列栅格数	1	1.2	1.5	2	1	1.2	1.5	2	1	1.2	1.5	2
20×20	40.57	43.64	41.89	46.59	0.35	0.46	0.40	0.66	6.07	5.97	6.23	6.90
40×40	77.27	80.76	81.21	81.25	0.33	0.35	0.49	0.72	6.37	6.48	6.79	7.04
60×60	109.36	108.33	115.28	113.41	0.26	0.29	0.50	0.59	6.68	6.62	6.78	7.34

[1]	Kunpeng Li, Xuefang Han. Research on Autonomous Driving Control Mechanism and Vehicle Scheduling in Smart City Based on Global Perspective [J]. Chinese Journal of Management Science, 2024, 32(12): 140-152.
[2]	Xiao-yan GU,Liang CHEN,Qian LIU,Meng-di MU,Deng-sheng WU. Research on Grazing Path Planning with Time Window under Grass Livestock Balance Constraints [J]. Chinese Journal of Management Science, 2023, 31(8): 184-192.
[3]	XU Yin-feng, ZHI Rong-teng, ZHENG Fei-feng, LIU Ming. Online Strategy and Competitive Analysis of Production Order Scheduling Problem with Rental Cost of Shared Machines [J]. Chinese Journal of Management Science, 2023, 31(4): 142-150.
[4]	LI Kun-peng, LIU Teng-bo, HE Bing-qian, XU Dong-yang. 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.

Research on Online Task Assignment and Global Path Planning Problem of Multi-AGV in Intelligent Warehouses

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 17

Related Articles 4

Metrics

Comments

Recommended 0