A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Advanced Search
Volume 9 Issue 11
Nov.  2022

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2022  >  9(11): 2005-2019
L. J. Yue and H. M. Fan, “Dynamic scheduling and path planning of automated guided vehicles in automatic container terminal,” IEEE/CAA J. Autom. Sinica, vol. 9, no. 11, pp. 2005–2019, Nov. 2022. doi: 10.1109/JAS.2022.105950
Citation: L. J. Yue and H. M. Fan, “Dynamic scheduling and path planning of automated guided vehicles in automatic container terminal,” IEEE/CAA J. Autom. Sinica, vol. 9, no. 11, pp. 2005–2019, Nov. 2022. doi: 10.1109/JAS.2022.105950
shu

Dynamic Scheduling and Path Planning of Automated Guided Vehicles in Automatic Container Terminal

doi: 10.1109/JAS.2022.105950

  • Department of Transportation Engineering, Dalian Maritime University, Dalian 116026, China

Funds:  This work was supported in part by the National Natural Science Foundation of China (61473053), the Science and Technology Innovation Foundation of Dalian, China (2020JJ26GX033)
More Information
    Abstract
  • The uninterrupted operation of the quay crane (QC) ensures that the large container ship can depart port within laytime, which effectively reduces the handling cost for the container terminal and ship owners. The QC waiting caused by automated guided vehicles (AGVs) delay in the uncertain environment can be alleviated by dynamic scheduling optimization. A dynamic scheduling process is introduced in this paper to solve the AGV scheduling and path planning problems, in which the scheduling scheme determines the starting and ending nodes of paths, and the choice of paths between nodes affects the scheduling of subsequent AGVs. This work proposes a two-stage mixed integer optimization model to minimize the transportation cost of AGVs under the constraint of laytime. A dynamic optimization algorithm, including the improved rule-based heuristic algorithm and the integration of the Dijkstra algorithm and the Q-Learning algorithm, is designed to solve the optimal AGV scheduling and path schemes. A new conflict avoidance strategy based on graph theory is also proposed to reduce the probability of path conflicts between AGVs. Numerical experiments are conducted to demonstrate the effectiveness of the proposed model and algorithm over existing methods.

     

    • FullText(HTML)
  • loading
    • References(41)
  • [1]
    J. Ding, K. Xu, R. Goldman, P. Allen, D. Fowler, and N. Simaan, “Design, simulation and evaluation of kinematic alternatives for insertable robotic effectors platforms in single port access surgery,” in Proc. IEEE Int. Conf. Robotics and Automation, Anchorage, USA, 2010, pp.1053–1058.
    [2]
    C. Bierwirth and F. Meisel, “A survey of berth allocation and quay crane scheduling problems in container terminals,” European J. Operational Research, vol. 202, no. 3, pp. 615–627, 2010. doi: 10.1016/j.ejor.2009.05.031
    [3]
    C. Bierwirth and F. Meisel, “A follow-up survey of berth allocation and quay crane scheduling problems in container terminals,” European J. Operational Research, vol. 244, no. 3, pp. 675–689, 2015. doi: 10.1016/j.ejor.2014.12.030
    [4]
    V. Galle, C. Barnhart, and P. Jaillet, “Yard crane scheduling for container storage, retrieval, and relocation,” European Journal of Operational Research, vol. 271, no. 1, pp. 288–316, 2018. doi: 10.1016/j.ejor.2018.05.007
    [5]
    U. Speer and K. Fischer, “Scheduling of different automated yard crane systems at container terminals,” Transportation Science, vol. 51, no. 1, pp. 305–324, 2017. doi: 10.1287/trsc.2016.0687
    [6]
    H. Fazlollahtabar, and M. Saidi-Mehrabad, “Methodologies to optimize automated guided vehicle scheduling and routing problems: A review study,” J. Intelligent &Robotic Systems, vol. 77, no. 3–4, pp. 525–545, 2015.
    [7]
    N. Singh, P. V. Sarngadharan, and P. K. Pal, “AGV scheduling for automated material distribution: A case study,” J. Intelligent Manufacturing, vol. 22, no. 2, pp. 219–228, 2011. doi: 10.1007/s10845-009-0283-9
    [8]
    H. Yoshitake, R. Kamoshida, and Y. Nagashima, “New automated guided vehicle system using real-time holonic scheduling for warehouse picking,” IEEE Robotics and Automation Letters, vol. 4, no. 2, pp. 1045–1052, 2019. doi: 10.1109/LRA.2019.2894001
    [9]
    Y. Zhao, X. Liu, G. Wang, S. Wu, and S. Han, “Dynamic resource reservation based collision and deadlock prevention for multi-AGVs,” IEEE Access, vol. 8, pp. 82120–82130, 2020. doi: 10.1109/ACCESS.2020.2991190
    [10]
    I. Draganjac, T. Petrović, D. Miklić, Z. Kovačić, and J. Oršulić, “Highly-scalable traffic management of autonomous industrial transportation systems,” Robotics and Computer-Integrated Manufacturing, vol. 63, p. 101915, 2020.
    [11]
    K. Gao, Z. Cao, L. Zhang, Z. Chen, Y. Han, and Q. Pan, “A review on swarm intelligence and evolutionary algorithms for solving flexible job shop scheduling problems,” IEEE/CAA J. Autom. Sinica, vol. 6, no. 4, pp. 904–916, 2019. doi: 10.1109/JAS.2019.1911540
    [12]
    J. Luo and Y. Wu, “Modelling of dual-cycle strategy for container storage and vehicle scheduling problems at automated container terminals,” Transportation Research Part E: Logistics and Transportation Review, vol. 79, pp. 49–64, 2015. doi: 10.1016/j.tre.2015.03.006
    [13]
    X. Chen, S. He, Y. Zhang, L. Tong (Carol), P. Shang, and X. Zhou, “Yard crane and AGV scheduling in automated container terminal: A multi-robot task allocation framework,” Transportation Research Part C: Emerging Technologies, vol. 114, pp. 241–271, 2020. doi: 10.1016/j.trc.2020.02.012
    [14]
    L. Yue, H. Fan, and C. Zhai, “Joint configuration and scheduling optimization of a dual-trolley quay crane and automatic guided vehicles with consideration of vessel stability,” Sustainability, vol. 12, no. 1, p. 24, 2019.
    [15]
    H. Hu, X. Chen, T. Wang, and Y. Zhang, “A three-stage decomposition method for the joint vehicle dispatching and storage allocation problem in automated container terminals,” Computers &Industrial Engineering, vol. 129, pp. 90–101, 2019. doi: 10.1016/j.cie.2019.01.023
    [16]
    J. Xin, R.R. Negenborn, F. Corman, and G. Lodewijks, “Control of interacting machines in automated container terminals using a sequential planning approach for collision avoidance,” Transportation Research Part C: Emerging Technologies, vol. 60, pp. 377–396, 2015. doi: 10.1016/j.trc.2015.09.002
    [17]
    K. H. Kim, S. M. Jeon, and K. R. Ryu, “Deadlock prevention for automated guided vehicles in automated container terminals,” in Container Terminals and Cargo Systems. Berlin, Heidelberg: Springer, pp.243–263, 2007.
    [18]
    N. Wu and M. Zhou, “Shortest routing of bidirectional automated guided vehicles avoiding deadlock and blocking,” IEEE/ASME Trans. Mechatronics, vol. 12, no. 1, pp. 63–72, 2007. doi: 10.1109/TMECH.2006.886255
    [19]
    K. J. C. Fransen, J. A. W. M. van Eekelen, A. Pogromsky, M. A. A. Boon, and I. J. B. F. Adan, “A dynamic path planning approach for dense, large, grid-based automated guided vehicle systems,” Computers & Operations Research, vol. 123, p. 105046, 2020.
    [20]
    Y. Liu, S. Ji, Z. Su, and D. Guo, “Multi-objective AGV scheduling in an automatic sorting system of an unmanned (intelligent) warehouse by using two adaptive genetic algorithms and a multi-adaptive genetic algorithm,” PloS One, vol. 14, no. 12, p. e0226161, 2019.
    [21]
    H. Fazlollahtabar and S. Hassanli, “Hybrid cost and time path planning for multiple autonomous guided vehicles,” Applied Intelligence, vol. 48, no. 2, pp. 482–498, 2018. doi: 10.1007/s10489-017-0997-x
    [22]
    M. Zhong, Y. Yang, Y. Dessouky, and O. Postolache, “Multi-AGV scheduling for conflict-free path planning in automated container terminals,” Computers & Industrial Engineering, vol. 142, p. 106371, 2020.
    [23]
    Y. Yang, M. Zhong, Y. Dessouky, and O. Postolache, “An integrated scheduling method for AGV routing in automated container terminals,” Computers &Industrial Engineering, vol. 126, pp. 482–493, 2018. doi: 10.1016/j.cie.2018.10.007
    [24]
    E W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269–271, 1959. doi: 10.1007/BF01386390
    [25]
    R W. Floyd, “Algorithm 97: Shortest path,” Communications of ACM, vol. 5 no. 6, p. 345, 1962.
    [26]
    R. K. Ahuja, K. Mehlhorn, J. Orlin, and R. E. Tarjan, “Faster algorithms for the shortest path problem,” Journal of ACM, vol. 37, no. 2, pp. 213–223, 1990. doi: 10.1145/77600.77615
    [27]
    I. K. Singgih, S. Hong, and K. H. Kim, “Flow path design for automated transport systems in container terminals considering traffic congestion,” Industrial Engineering &Management Systems, vol. 15, no. 1, pp. 19–31, 2016.
    [28]
    K. Guo, J. Zhu, and L. Shen, “An improved acceleration method based on multi-agent system for AGVs conflict-free path planning in automated terminals,” IEEE Access, vol. 9, pp. 3326–3338, 2021. doi: 10.1109/ACCESS.2020.3047916
    [29]
    M. Gen and L. Lin, “Multiobjective genetic algorithm for scheduling problems in manufacturing systems,” Industrial Engineering and Management Systems, vol. 11, no. 4, pp. 310–330, 2012. doi: 10.7232/iems.2012.11.4.310
    [30]
    J. Wang, Y. Sun, Z. Zhang and S. Gao, “Solving multitrip pickup and delivery problem with time windows and manpower planning using multiobjective algorithms,” IEEE/CAA J. Autom. Sinica, vol. 4, no. 4, pp. 1134–1153, 2020.
    [31]
    A. Gola and G. Kłosowski, “Development of computer-controlled material handling model by means of fuzzy logic and genetic algorithms,” Neurocomputing, vol. 338, pp. 381–392, 2019. doi: 10.1016/j.neucom.2018.05.125
    [32]
    Y. Zheng, Y. Xiao, and Y. Seo, “A tabu search algorithm for simultaneous machine/AGV scheduling problem,” Int. J. Production Research, vol. 52, no. 19, pp. 5748–5763, 2014. doi: 10.1080/00207543.2014.910628
    [33]
    L. P. Kaelbling, M. L. Littman, and A W. Moore, “Reinforcement learning: A survey,” J. Artificial Intelligence Research, vol. 4, pp. 237–285, 1996. doi: 10.1613/jair.301
    [34]
    L. Jiang, H. Huang, and Z. Ding, “Path planning for intelligent robots based on deep Q-Learning with experience replay and heuristic knowledge,” IEEE/CAA J. Autom. Sinica, vol. 7, no. 4, pp. 1179–1189, 2019.
    [35]
    Z. Cao, C. Lin, M. Zhou, and R. Huang, “Scheduling semiconductor testing facility by using cuckoo search algorithm with reinforcement learning and surrogate modeling,” IEEE Trans. Automation Science and Engineering, vol. 16, no. 2, pp. 825–837, 2018.
    [36]
    H. Wang, B. R. Sarker, J. Li, and J. Li, “Adaptive scheduling for assembly job shop with uncertain assembly times based on dual Q-Learning,” Int. J. Production Research, vol. 59, no. 19, pp. 1–17, 2020.
    [37]
    T. Zhang, T. Gong, S. Han, Q. Deng, and X. S. Hu, “Distributed dynamic packet scheduling framework for handling disturbances in real-time wireless networks,” IEEE Trans. Mobile Computing, vol. 18, no. 11, pp. 2502–2517, 2018.
    [38]
    H. Lu and S. Wang, “A study on multi-ASC scheduling method of automated container terminals based on graph theory,” Computers &Industrial Engineering, vol. 129, pp. 404–416, 2019. doi: 10.1016/j.cie.2019.01.050
    [39]
    R. Konda, H. M. La, and J. Zhang, “Decentralized function approximated Q-Learning in multi-robot systems for predator avoidance,” IEEE Robotics and Automation Letters, vol. 5, no. 4, pp. 6342–6349, 2020. doi: 10.1109/LRA.2020.3013920
    [40]
    L. Yue, H. Fan, and M. Ma, “Optimizing configuration and scheduling of double 40 ft dual-trolley quay cranes and AGVs for improving container terminal services,” J. Cleaner Production, vol. 292, p.126019, 2021.
    [41]
    M. E. Pfund and J. W. Fowler, “Extending the boundaries between scheduling and dispatching: hedging and rescheduling techniques,” Int. J. Production Research, vol. 55, no. 11, pp. 3294–3307, 2017. doi: 10.1080/00207543.2017.1306133
    • Related Articles
    • Supplements(0)

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

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

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

    Figures(10)  / Tables(6)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (2044) PDF downloads(245) Cited by()

    Highlights

    • AGV scheduling and path planning models are established to minimize costs
    • The uncertain factor of path conflicts and failed path nodes are considered
    • A rule-based heuristic algorithm composed of five principles is proposed
    • A hybrid algorithm that combines Dijkstra and Q-Learning algorithm is proposed
    • A novel multi-AGV conflict avoidance strategy based on graph theory is designed

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return