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

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

摘要/Abstract

摘要：

人工智能的快速发展加速了仓库的智慧化转型，越来越多的仓库引入大量AGV替代人工作业。智能仓库中多AGV在线全局调度问题成为当前的研究热点和难点。此问题包含任务指派和全局路径规划，需要考虑双向导引道路、无碰撞、AGV电量约束和任务时间窗等特性。针对该问题，本文以最小化AGV的运行时间和任务延迟惩罚之和为目标，建立混合整数线性规划模型。同时，设计一种多AGV任务指派与路径规划协同优化算法。首先，基于任务与AGV双重优先规则设计指派算法。其次，考虑多种碰撞情况，引入五种策略改进A*算法并设置重调度机制，全局规划AGV路径。为验证算法效果，引入分支切割算法求解小规模问题。12组小规模算例测试结果表明，本文提出的分支切割算法可将CPLEX下界平均提高59.89%，启发式算法求解结果与分支切割算法下界平均Gap值为7.23%。144组大规模算例测试结果表明，5种改进策略均能提升算法求解质量。改进算法可将传统算法的结果平均改善27.69%，且求解时间缩短至2秒内，效率提高130.01%。研究成果不仅适用于智能仓库的AGV调度决策，还能拓展至生产车间、自动化码头等路网相对规则、自动化程度较高的封闭场景中，为全局集中管控的多车调度问题提供参考。

关键词: 智能仓库, 自动导引小车, 在线调度, 路径规划, 分支切割

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

中图分类号:

F252

李昆鹏, 韩雪芳. 智能仓库中多AGV在线任务指派与全局路径规划问题研究[J]. 中国管理科学, 2025, 33(3): 264-276.

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.

图/表 13

图1

表1

模型中的参数符号及相关定义"

参数符号	定义
$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

表1

图2

图3

表2

表3

表4

表5

添加不同改进策略的算法测试结果"

算例	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

表5

图4

图5

图6

图7

表6

参考文献 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]	李昆鹏, 韩雪芳. 基于全局视角的智慧城市无人驾驶管控机制及车辆调度问题研究[J]. 中国管理科学, 2024, 32(12): 140-152.
[2]	谷晓燕,陈亮,刘倩,穆梦迪,吴登生. 草畜平衡约束下带时间窗的放牧路径规划研究[J]. 中国管理科学, 2023, 31(8): 184-192.
[3]	徐寅峰, 智荣腾, 郑斐峰, 刘明. 考虑共享机器租借费用的在线订单加工策略及竞争分析[J]. 中国管理科学, 2023, 31(4): 142-150.
[4]	李昆鹏, 刘腾博, 贺冰倩, 徐东洋. “货到人”拣选系统中AGV路径规划与调度研究[J]. 中国管理科学, 2022, 30(4): 240-251.