Research article

Multi-AGV dispatching and routing problem based on a three-stage decomposition method

  • Received: 26 April 2020 Accepted: 13 July 2020 Published: 31 July 2020
  • Automatic guided vehicle (AGV) is a device for horizontal transportation between quay cranes and yard cranes in an automated container terminal. In which dispatching and routing problem (DRP) of the AGV system is a vital as well as basic issue. In the application of the actual AGV system, several practical factors including avoiding conflicts, path smoothness, difficulty in adjusting routes and anti-interference must be considered. The present study establishes the model with the goal of minimizing AGV travel distance, reducing operation time and response time. Furthermore, a three-stage decomposition solution to the problem was proposed by combining the advantages of pre-planning algorithm and real-time planning algorithm, which combines A* algorithm with the principle of time window to plan the path of each AGV in time order. Finally, the effectiveness of this method in path search and time optimization is illustrated and the system efficiency is improved by comparing and analyzing the calculation examples of different scales.

    Citation: Yejun Hu, Liangcai Dong, Lei Xu. Multi-AGV dispatching and routing problem based on a three-stage decomposition method[J]. Mathematical Biosciences and Engineering, 2020, 17(5): 5150-5172. doi: 10.3934/mbe.2020279

    Related Papers:

  • Automatic guided vehicle (AGV) is a device for horizontal transportation between quay cranes and yard cranes in an automated container terminal. In which dispatching and routing problem (DRP) of the AGV system is a vital as well as basic issue. In the application of the actual AGV system, several practical factors including avoiding conflicts, path smoothness, difficulty in adjusting routes and anti-interference must be considered. The present study establishes the model with the goal of minimizing AGV travel distance, reducing operation time and response time. Furthermore, a three-stage decomposition solution to the problem was proposed by combining the advantages of pre-planning algorithm and real-time planning algorithm, which combines A* algorithm with the principle of time window to plan the path of each AGV in time order. Finally, the effectiveness of this method in path search and time optimization is illustrated and the system efficiency is improved by comparing and analyzing the calculation examples of different scales.


    加载中


    [1] C. L. Liu, H. Jula, P. A. Loannou, Design, simulation, and evaluation of automated container terminals, IEEE Trans. Intell. Transp. Syst., 3 (2002), 12-26.
    [2] H. T. Hu, X. Chen, T. Wang, Y. Zhang, A three-stage decomposition method for the joint vehicle dispatching and storage allocation problem in automated container terminals, Comput. Ind. Eng., 129 (2019), 90-101.
    [3] H. Fazlollahtabar, M. Saidi-Mehrabad, Autonomous guided vehicles: Methods and models for optimal path planning, Studies in Systems, Decision and Control, 20 (2015).
    [4] M. S. Zhong, Y. S. Yang, Y. M. Zhou, Free-conflict AGV path planning in automated terminals based on speed control, Comp. Sci., 2019. DOI: 10.11896/j.issn.1002-137x.2019.07.047.
    [5] I. Draganjac, T. Petrovic, D. Miklic, Z. Kovacic, J. Orsulic, Highly-scalable traffic management of autonomous industrial transportation systems, Robot Cim-Int. Manuf., 63 (2020), 101915.
    [6] J. B. Xin, R. R. Negenborn, F. Corman, G. Lodewijks, Control of interacting machines in automated container terminals using a sequential planning approach for collision avoidance, Transp. Res. Part C Emerg. Technol., 60 (2015), 377-396.
    [7] E. Gawrilow, M. Klimm, Conflict-free vehicle routing, Euro. J. Transp. Logist., 1 (2012), 87-111.
    [8] C. Oboth, R. Batta, M. Karwan, Dynamic conflict-free routing of automated guided vehicles, Int. J. Prod. Res., 37 (1999), 2003-2030.
    [9] T. J. Chen, Y. Sun, W. Dai, On the Shortest and Conflict-Free Path Planning of Multi-AGV System Based on Dijkstra Algorithm and the Dynamic Time-Window Method, Adv. Mater. Res., 645 (2013), 267-271.
    [10] L. H. He, P. H. Lou, X. M. Qian, Conflict-free automated guided vehicles routing based on time window, Comput. Integr. Manuf., 16 (2010), 2630-2634.
    [11] X. Y. Ma, Y. M. Bian, F. Gao, An improved shuffled frog leaping algorithm for multiload AGV dispatching in automated container terminals, Math. Probl. Eng., 2020 (2020), 1-13.
    [12] P. E. Hart, N. J. Nilsson, B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Trans. Syst. enc. Cybern., 4 (1972), 28-29.
    [13] K. Daniel, A. Nash, S. Koenig, A. Felner: Any-angle path planning on grids, J. Artif. Intell. Res., 39 (2010), 533-579.
    [14] Y. Xin, H. Liang, M. Du, An improved A* algorithm for searching infinite neighbourhoods, Robot, 2014. DOI: 10.13973/j.cnki.robot.2014.0627.
    [15] D. Frantiek, A. Babinec, M. Kajan, Path planning with modified a Star Algorithm for a mobile robot, Proced. Eng., 96 (2014), 59-69.
    [16] M. X. Lin, K. Yuan, C. Shi, Y. Wang, Path planning of mobile robot based on improved A∗ algorithm, IEEE Control Syst., DOI: 2017. 10.1109/CCDC.2017.7979125.
    [17] U. A. Umar, M. K. A. Ariffin, N. Ismail, Priority-based genetic algorithm for conflict-free automated guided vehicle routing, Proced. Eng., 50 (2012), DOI: 10.1016/j.proeng.2012.10.080.
    [18] J. Luo, Y. Wu, Modelling of dual-cycle strategy for container storage and vehicle scheduling problems at automated container terminals, Transp. Res. Part E., 79 (2015), 49-64.
    [19] S. Maza, P. Castagna, P, Conflict-free AGV routing in bi-directional network. Emerging Technologies and Factory Automation, IEEE Symp. Emerg. Technol. Fact. Autom. ETFA, DOI: 2001. 10.1109/ETFA.2001.997777.
    [20] M. S. Zhong, Y. S. Yang, Multi-AGV scheduling for conflict-free path planning in automated container terminals, Comput. Ind. Eng., 142 (2020), 106371.
    [21] G. Qing, Z. Zheng, X. Yue, Path-planning of automated guided vehicle based on improved Dijkstra algorithm, Control Decision Conference, IEEE, 7 (2017), 138-143.
  • Reader Comments
  • © 2020 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(6329) PDF downloads(662) Cited by(10)

Article outline

Figures and Tables

Figures(15)  /  Tables(8)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog