Journal of Shanghai Jiao Tong University

Journal of Shanghai Jiaotong University >

2023 , Vol. 57 >Issue 1: 93 - 102

DOI: https://doi.org/10.16183/j.cnki.jsjtu.2021.223

Mechanical Engineering

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

Expand
  • School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China

Received date: 2021-06-05

  Revised date: 2021-08-03

  Online published: 2022-08-12

Fold

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

Cite this article

QIU Kejun, BAO Zhongkai, CHEN Lu . Task Assignment and Path Planning for Automatic Guided Vehicles in Aircraft Assembly Workshop[J]. Journal of Shanghai Jiaotong University, 2023 , 57(1) : 93 -102 . DOI: 10.16183/j.cnki.jsjtu.2021.223

References

[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.
[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.
[3] 夏扬坤, 符卓, 谢九勇. 依订单拆分的多自动导引车物料配送路径规划[J]. 计算机集成制造系统, 2017, 23(7): 1520-1528.
[3] 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.
[5] 汤红杰, 王鼎, 皇攀凌, 等. 优化Dijkstra算法在工厂内物流AGV路径规划的研究[J]. 机械设计与制造, 2018(1): 117-120.
[5] 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.
[9] 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
[11] 罗强, 王海宝, 崔小劲, 等. 改进人工势场法自主移动机器人路径规划[J]. 控制工程, 2019, 26(6): 1091-1098.
[11] 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.
[12] 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.
[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.
[14] 曾庆成, 李明泽, 薛广顺. 考虑拥堵因素的自动化码头多AGV无冲突动态路径规划模型[J]. 大连海事大学学报, 2019, 45(4): 35-44.
[14] 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.
[15] 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.
[17] 杨雅洁, 苌道方, 余芳. 考虑AGV避碰的自动化码头多资源协同调度[J]. 计算机工程与应用, 2020, 56(6): 246-253.
[17] 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.
[18] 泰应鹏, 邢科新, 林叶贵, 等. 多AGV路径规划方法研究[J]. 计算机科学, 2017(Sup.2): 84-87.
[18] 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.
[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.
[22] 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.
[23] 胡彬, 王冰, 王春香, 等. 一种基于时间窗的自动导引车动态路径规划方法[J]. 上海交通大学学报, 2012, 46(6): 967-971.
[23] 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.
Options
Outlines

/

〈 〉