Task Assignment and Path Planning for Automatic Guided Vehicles in Aircraft Assembly Workshop

doi:10.16183/j.cnki.jsjtu.2021.223

Abstract

Abstract:

To realize efficient scheduling of automatic guided vehicles (AGV) in the aircraft final assembly workshop, a two-stage method of AGV task allocation and path planning is proposed which effectively solves the problem of multi-trip distribution scheduling of AGV in the workshop. In the task allocation stage, an AGV task allocation model based on the trip is established to improve task allocation efficiency. In the path planning stage, the time window algorithm is used to initialize, update, and arrange the time window of the resources occupied by the AGV. Considering that the latest delivery time constraints may be violated due to obstacle avoidance and waiting, three adjustment strategies are designed to realize the conflict-free path planning of AGV, including the package exchanging strategy, the priority exchanging strategy, and the reserved conflict duration relaxation strategy. In numerical experiments, the average solving time of the two-stage method applied to problems with the scale of 50, 100, and 150 is 15.86, 41.12, and 162.29 s, which indicates that the two-stage method effectively alleviates the complexity of the multi-trip AGV scheduling problem. The two-stage method can realize the scheduling of the AGV in aircraft assembly workshop within a reasonable time and adapt to the rapid increase in the annual production of aircraft.

Key words: automatic guided vehicle (AGV), multi-trip, task allocation, path planning, time window algorithm

CLC Number:

QIU Kejun, BAO Zhongkai, CHEN Lu. Task Assignment and Path Planning for Automatic Guided Vehicles in Aircraft Assembly Workshop[J]. Journal of Shanghai Jiao Tong University, 2023, 57(1): 93-102.

Figures/Tables 9

Fig.1

Fig.2

Tab.1

Tab.2

Tab.3

Tab.4

Tab.5

Fig.3

Fig.4

References 23

[1]	HU H T, CHEN X Z, WANG T S, et al. A three-stage decomposition method for the joint vehicle dispatching and storage allocation problem in automated container terminals[J]. Computers & Industrial Engineering, 2019, 129: 90-101. doi: 10.1016/j.cie.2019.01.023 URL
[2]	ZOU W Q, PAN Q K, MENG T, et al. An effective discrete artificial bee colony algorithm for multi-AGVs dispatching problem in a matrix manufacturing workshop[J]. Expert Systems with Applications, 2020, 161: 113675. doi: 10.1016/j.eswa.2020.113675 URL
[3]	夏扬坤, 符卓, 谢九勇. 依订单拆分的多自动导引车物料配送路径规划[J]. 计算机集成制造系统, 2017, 23(7): 1520-1528.
	XIA Yangkun, FU Zhuo, XIE Jiuyong. Material distribution route planning for multiple automated guided vehicles with split deliveries by order[J]. Computer Integrated Manufacturing Systems, 2017, 23(7): 1520-1528.
[4]	ZOU W Q, PAN Q K, WANG L. An effective multi-objective evolutionary algorithm for solving the AGV scheduling problem with pickup and delivery[J]. Knowledge-Based Systems, 2021, 218(3): 106881. doi: 10.1016/j.knosys.2021.106881 URL
[5]	汤红杰, 王鼎, 皇攀凌, 等. 优化Dijkstra算法在工厂内物流AGV路径规划的研究[J]. 机械设计与制造, 2018(1): 117-120.
	TANG Hongjie, WANG Ding, HUANG Panling, et al. AGV path planning based on optimized Dijkstra algorithm in logistics factory[J]. Machinery Design & Manufacture, 2018(1): 117-120.
[6]	RADHIA Z, KHALED M, SIMON C D, et al. A hybrid method for assigning containers to AGVs in container terminal[J]. IFAC-PapersOnLine, 2016, 49(3): 96-103.
[7]	WANG C B, WANG L, Qin J, et al. Path planning of automated guided vehicles based on improved A-star algorithm[C]//2015 IEEE International Conference on Information and Automation. Lijiang, China: IEEE, 2019: 2071-2076.
[8]	FRANTISEK D, ANDREJ B, MARTIN K, et al. Path planning with modified A star algorithm for a mobile robot[J]. Procedia Engineering, 2014(96): 59-69.
[9]	赵大兴, 余明进, 许万. 基于高适应度值遗传算法的AGV最优路径规划[J]. 计算机工程与设计, 2017, 38(6): 1635-1641.
	ZHAO Daxing, YU Mingjin, XU Wan. AGV optimal path planning based on genetic algorithms of large fitness value[J]. Computer Engineering and Design, 2017, 38(6): 1635-1641.
[10]	ZHONG M S, YANG Y S, YASSER D, et al. Multi-AGV scheduling for conflict-free path planning in automated container terminals[J]. Computers & Industrial Engineering, 2020, 142: 106371 doi: 10.1016/j.cie.2020.106371 URL
[11]	罗强, 王海宝, 崔小劲, 等. 改进人工势场法自主移动机器人路径规划[J]. 控制工程, 2019, 26(6): 1091-1098.
	LUO Qiang, WANG Haibao, CUI Xiaojing, et al. Autonomous mobile robot path planning based on improved artificial potential method[J]. Control Engineering of China, 2019, 26(6): 1091-1098.
[12]	程志, 张志安, 李金芝, 等. 改进人工势场法的移动机器人路径规划[J]. 计算机工程与应用, 2019, 55(23): 29-34. doi: 10.3778/j.issn.1002-8331.1904-0472
	CHENG Zhi, ZHANG Zhi’an, LI Jinzhi, et al. Mobile robots path planning based on improved artificial potential field[J]. Computer Engineering and Applications, 2019, 55(23): 29-34. doi: 10.3778/j.issn.1002-8331.1904-0472
[13]	XING L, LIU Y, LI H, et al. A novel tabu search algorithm for multi-AGV routing problem[J]. Mathematics, 2020, 8(2): 279. doi: 10.3390/math8020279 URL
[14]	曾庆成, 李明泽, 薛广顺. 考虑拥堵因素的自动化码头多AGV无冲突动态路径规划模型[J]. 大连海事大学学报, 2019, 45(4): 35-44.
	ZENG Qingcheng, LI Mingze, XUE Guangshun. Multiple AGV conflict-free dynamic routing model in automated terminals considering congestion factors[J]. Journal of Dalian Maritime University, 2019, 45(4): 35-44.
[15]	刘辉, 肖克, 王京擘. 基于多智能体强化学习的多AGV路径规划方法[J]. 自动化与仪表, 2020, 35(2): 84-89.
	LIU Hui, XIAO Ke, WANG Jingbo. Multi-AGV path planning method based on multi-agent reinforcement learning[J]. Automation & Instrumentation, 2020, 35(2): 84-89.
[16]	MURAKAMI K. Time-space network model and MILP formulation of the conflict-free routing problem of a capacitated AGV system[J]. Computers & Industrial Engineering, 2020, 141: 106270. doi: 10.1016/j.cie.2020.106270 URL
[17]	杨雅洁, 苌道方, 余芳. 考虑AGV避碰的自动化码头多资源协同调度[J]. 计算机工程与应用, 2020, 56(6): 246-253. doi: 10.3778/j.issn.1002-8331.1812-0069
	YANG Yajie, CHANG Daofang, YU Fang. Multi-resource coordinated scheduling of automated terminals considering AGV collision avoidance[J]. Computer Engineering and Applications, 2020, 56(6): 246-253. doi: 10.3778/j.issn.1002-8331.1812-0069
[18]	泰应鹏, 邢科新, 林叶贵, 等. 多AGV路径规划方法研究[J]. 计算机科学, 2017(Sup.2): 84-87.
	TAI Yingpeng, XING Kexin, LIN Yegui, et al. Research of path planning in multi-AGV system[J]. Computer Science, 2017(Sup.2): 84-87.
[19]	KELEN V, LUIS F R, NADIA J M, et al. Integrated tasks assignment and routing for the estimation of the optimal number of AGVS[J]. The International Journal of Advanced Manufacturing Technology, 2016, 82(1/2/3/4): 719-736. doi: 10.1007/s00170-015-7343-4 URL
[20]	HAO J, WANG C, YANG M, et al. Hybrid genetic algorithm based dispatch and conflict-free routing method of AGV systems in unmanned underground parking lots[C]//2020 IEEE International Conference on Real-time Computing and Robotics. Asahikawa, Japan: IEEE, 2020: 475-480.
[21]	RIAZI S, DIDING T, FALKMAN P, et al. Scheduling and routing of AGVs for large-scale flexible manufacturing systems[C]//2019 IEEE 15th International Conference on Automation Science and Engineering. Vancouver, Canada: IEEE, 2019: 891-896.
[22]	余翀, 邱其文. 基于栅格地图的分层式机器人路径规划算法[J]. 中国科学院大学学报, 2013, 30(4): 528-538. doi: 10.7523/j.issn.2095-6134.2013.04.015
	YU Chong, QIU Qiwen. Hierarchical robot path planning algorithm based on grid map[J]. Journal of University of Chinese Academy of Sciences, 2013, 30(4): 528-538. doi: 10.7523/j.issn.2095-6134.2013.04.015
[23]	胡彬, 王冰, 王春香, 等. 一种基于时间窗的自动导引车动态路径规划方法[J]. 上海交通大学学报, 2012, 46(6): 967-971.
	HU Bin, WANG Bing, WANG Chunxiang, et al. Dynamic routing of automated guided vehicles based on time window[J]. Journal of Shanghai Jiao Tong University, 2012, 46(6): 967-971.

行程编号	目标暂存区	配送料包数量	行驶时长/min	行程编号	目标暂存区	配送料包数量	行驶时长/min
1	暂存区3	1	6	6	暂存区1	2	10
2	暂存区3	2	6	7	暂存区3、暂存区2	2	8
3	暂存区2	1	8	8	暂存区3、暂存区1	2	10
4	暂存区2	2	8	9	暂存区2、暂存区1	2	10
5	暂存区1	1	10

AO编号	需求时间/h	目标工位	AO编号	需求时间/h	目标工位
150C08RW6040	0	暂存区3	140C08ZF3401	8	暂存区2
150C08RW6030	0	暂存区3	140C08ZF3300	8	暂存区2
140C07BS0080	0	暂存区2	140C08ZF2500	8	暂存区2
140C05DA0030	0	暂存区2	140C08ZF2400	8	暂存区2
130C06KS0010	0	暂存区1	140C08ZF2100	8	暂存区2
130C01PJ0050	0	暂存区1	130C01RS0010	8	暂存区1
150C03RD0260	1	暂存区3	130C01KS0010	8	暂存区1
150C03JD0010	1	暂存区3	150C04SA0010	8.25	暂存区3
150C03DD0210	1	暂存区3	150C04AA0070	8.25	暂存区3
150C03DD0160	1	暂存区3	150C05SA0040	9	暂存区3

工作日编号	AO料包数量	工作日编号	AO料包数量
Day1	59	Day8	53
Day2	76	Day9	58
Day3	59	Day10	75
Day4	55	Day11	61
Day5	73	Day12	33
Day6	62	Day13	47
Day7	65	Day14	36

算例编号	料包数	求解时长/s	调整策略	算例编号	料包数	求解时长/s	调整策略
1	50	5.30	—	16	100	79.17	—
2	50	18.01	—	17	100	60.97	优先级提前
3	50	23.48	—	18	100	31.20	—
4	50	20.55	—	19	100	23.75	—
5	50	11.29	—	20	100	34.81	—
6	50	23.55	—	21	150	167.17	料包交换
7	50	14.72	—	22	150	197.26	料包交换
8	50	20.32	—	23	150	215.47	料包交换
9	50	14.70	—	24	150	122.01	料包交换
10	50	6.71	—	25	150	115.22	料包交换
11	100	24.29	—	26	150	163.90	—
12	100	57.54	—	27	150	113.82	料包交换
13	100	23.01	—	28	150	193.61	—
14	100	34.48	—	29	150	95.58	—
15	100	42.00	—	30	150	238.81	料包交换

行程编号	AGV编号
行程编号	AGV1	AGV2	AGV3	AGV4	AGV5
行程1	16, 37	24, 28	14, 29	30, 34	20, 23
行程2	52, 64	45, 61	15, 26	9, 18	66, 73
行程3	42, 47	41, 43	53, 59	31, 36	19, 90
行程4	55, 93	48, 57	50, 58	51, 62	21, 67
行程5	32, 35	46, 56	25, 79	54, 63	22, 68
行程6	11, 12	6, 39	13, 38	7, 17	1, 2
行程7	49, 65	8, 33	75, 76	27, 69	100, 74
行程8	77, 82	98, 99	10, 40	89, 96	4, 5
行程9	78, 88	70, 72	94, 95	91, 92	3, 84
行程10	85, 86	71, 83	80, 97	81, 87	44, 60