Volume 40 Issue 3
Jun.  2022
Turn off MathJax
Article Contents
Article Navigation >  Journal of Transport Information and Safety  > 2022  >  40(3): 96-107
DING Yi, YUAN Hao, FANG Huaijin, TIAN Yu. An Optimal Scheduling Method of AGVs at Automated Container Terminal Considering Conflict Avoidance[J]. Journal of Transport Information and Safety, 2022, 40(3): 96-107. doi: 10.3963/j.jssn.1674-4861.2022.03.010
Citation: DING Yi, YUAN Hao, FANG Huaijin, TIAN Yu. An Optimal Scheduling Method of AGVs at Automated Container Terminal Considering Conflict Avoidance[J]. Journal of Transport Information and Safety, 2022, 40(3): 96-107. doi: 10.3963/j.jssn.1674-4861.2022.03.010
shu

An Optimal Scheduling Method of AGVs at Automated Container Terminal Considering Conflict Avoidance

doi: 10.3963/j.jssn.1674-4861.2022.03.010
  • 1.

    Institute of Logistics Science and Engineering, Shanghai Maritime University Shanghai 201306, China

  • 2.

    Shanghai International Port (Group) Co., Ltd., Shanghai 201306, China

  • Received Date: 2022-01-21
    Available Online: 2022-07-25
    Abstract
  • Scheduling of automated guided vehicles (AGVs) is crucial for improving the operational efficiency of automated container terminals. In this paper, a two-stage optimization model is proposed for task allocation and path planning of AGVs with the consideration of the following factors: the remaining power supply of the AGV, multiple loads, and the characteristics of automated port layout. During the first stage of the optimization, a task allocation model is used to minimize the total operation time of AGVs, while a path planning model is used to optimize the operation paths of AGVs in the second stage, which will prevent the conflicts between AGVs. A new simulated annealing algorithm is developed to solve the proposed task allocation model. To guarantee an acceptable running time of the algorithm and the quality of the solution, the time cost of the task and the number of AGVs are prioritized in the process of improving the solution algorithm. A path planning algorithm based on time-space network is designed to solve the path planning problem, which discretizes the work area into a grid network and adds revised time information to develop an updated time-space network. It searches for the shortest path based on the network, while detecting conflicts and adjusting routes to avoid collisions and congestion of paths. Under the congestion scenarios, where there is no feasible solution for path planning due to unbalanced task assignment, the cost of AGV tasks will be recalculated based on conflict avoidance and their tasks will be reassigned again. Simulation experiment and comparative analysis are carried out for the case study automated container terminal (Phase Ⅳ) of the Yangshan Port. The proposed method for scheduling of AGVs is compared with a traditional path planning and obstacle avoidance model. study results show that the total operation time is reduced by 7.31% on average. The conflicts between AGVs are totally removed. The total task delay is reduced by 2 895 s, and the network congestion is reduced by 10.79%.

     

    • FullText(HTML)
  • loading
    • References(22)
  • [1]
    GRUNOW M, GUNTHER H, LEHMANN M. Dispatching multi-load AGVs in highly automated seaport container terminals[J]. OR Spectrum, 2006(26): 211–235.
    [2]
    霍凯歌, 张亚琦, 胡志华. 自动化集装箱码头多载AGV调度问题研究[J]. 大连理工大学学报, 2016, 56(3): 244–251. https://www.cnki.com.cn/Article/CJFDTOTAL-DLLG201603004.htm

    HUO K G, ZHANG Y Q, HU Z H. Research on scheduling problem of multi-load AGV at automated container terminal[J]. Journal of Dalian University of Technology, 2016, 56 (3): 244–251(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-DLLG201603004.htm
    [3]
    杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056–3062. doi: 10.11772/j.issn.1001-9081.2020121919

    YANG W, LI R, ZHANG K. Multi-AGV task allocation optimization based on variable neighborhood simulation annealing algorithm[J]. Journal of Computer Applications, 2021, 41 (10): 3056–3062. (in Chinese). doi: 10.11772/j.issn.1001-9081.2020121919
    [4]
    LIM J, KIM K, YOSHIMOTO K. et al. A dispatching method for automated guided vehicles by using a bidding concept[J]. OR Spectrum, 2003, 25(1): 25–44. doi: 10.1007/s00291-002-0116-0
    [5]
    周润, 龙伟, 李炎炎, 等. 面向绿色再制造系统的AGV路径规划研究[J]. 四川大学学报(自然科学版), 2019, 56(5): 883–889. doi: 10.3969/j.issn.0490-6756.2019.05.014

    ZHOU R, LONG W, LI Y Y, et al. Research on AGV path planning for green remanufacturing systems[J]. Sichuan University Journal(Natural Science Edition), 2019, 56(5): 883–889. (in Chinese) doi: 10.3969/j.issn.0490-6756.2019.05.014
    [6]
    QING G, ZHENG Z, YUE X. Path-planning of automated guided vehicle based on improved Dijkstra algorithm[C]. Control Decision Conference, Melbourne, Australia: IEEE, 2017.
    [7]
    LYU X, SONG Y, HE C, et al. Approach to integrated scheduling problems considering optimal number of automated guided vehicles and conflict-free routing in flexible manufacturing systems[J]. IEEE Access, 2019, 7(1): 74909–74924.
    [8]
    张中伟, 张博晖, 代争争. 基于动态优先级策略的多AGV无冲突路径规划[J]. 计算机应用, 2021, 38(7): 2108–2111. https://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ202107035.htm

    ZHANG Z W, ZHANG B H, DAI Z Z. Multi-AGV conflict-free path planning based on dynamic priority strategy[J]. Computer Applications, 2021, 38(7): 2108–2111. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ202107035.htm
    [9]
    KRISHNAMURTHY N, BATTA R, KARWAN M. Developing conflict-free routes for automated guided vehicles[J]. Operations Research, 1993, 41(6): 1077–1090. doi: 10.1287/opre.41.6.1077
    [10]
    CORREA A I, ANDRE L, LOUIS R. Scheduling and routing of automated guided vehicles: A hybrid approach[J]. Computers & Operations Research, 2007, 34(6): 1688–1707.
    [11]
    余娜娜, 李铁克, 王柏琳, 等. 自动化分拣仓库中多AGV调度与路径规划算法[J]. 计算机集成制造系统, 2020, 26(1): 171–180.

    YU N N, LI T K, WANG B L, et al. Multi-AGV scheduling and path planning algorithms in automated sorting warehouses[J]. Computer Integrated Manufacturing Systems, 2020, 26 (1): 171–180. (in Chinese)
    [12]
    KEISUKE M. Time-space network model and MILP formulation of the conflict-free routing problem of a capacitated AGV system[J]. Computers & Industrial Engineering, 2020, 141(1): 1–10.
    [13]
    HU Y, DONG L, XU L. 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
    [14]
    李静, 朱小林. 集装箱码头上多自动引导车的调度和路径规划[J/OL]. (2022-01-25)[2022-1-20]. http://kns.cnki.net/kcms/detail/11.5946.TP.20210618.1850.016.html.

    LI J, ZHU X L. Scheduling and path planning of multi-AVS on container terminals[J/OL]. (2022-01-25)[2022-1-20]. http://kns.cnki.net/kcms/detail/11.5946.TP.20210618.1850.016.html.
    [15]
    JI S, LUAN D, CHEN Z, et al. Integrated scheduling in automated container terminals considering AGV conflict-free routing[J]. Transportation Letters-the International Journal of Transportation Research, 2020, 13(2): 1–14.
    [16]
    曾庆成, 李明泽, 薛广顺. 考虑拥堵因素的自动化码头多AGV无冲突动态路径规划模型[J]. 大连海事大学学报, 2019, 45(4): 35–44.

    ZENG Q C, LI M Z, XUE G S. Multi-AGV conflict-free dynamic path planning model for automated terminals considering congestion factors[J]. Journal of Dalian Maritime University, 2019, 45(4): 35–44. (in Chinese)
    [17]
    张素云, 杨勇生, 梁承姬, 等. 自动化码头多AGV路径冲突的优化控制研究[J]. 交通运输系统工程与信息, 2017, 17 (2): 83–89. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201702013.htm

    ZHANG S Y, YANG Y S, LIANG C J, et al. Optimal control of multiple AGV path conflict in automated terminals[J]. Transportation Systems Engineering and Information Technology, 2017, 17(2): 83–89. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201702013.htm
    [18]
    祁文祥, 陆志强, 孙小明. 带软时间窗的集货与送货多车辆路径问题节约算法[J]. 交通运输工程学报, 2010, 10(2): 99–103. doi: 10.3969/j.issn.1671-1637.2010.02.018

    QI W X, LU Z Q, SUN X M. Saving Algorithm for Collecting and Delivery Multi-vehicle Path Problem with Soft Time Window[J]. Journal of Transportation Engineering, 2010, 10 (2): 99–103(in Chinese). doi: 10.3969/j.issn.1671-1637.2010.02.018
    [19]
    高一鹭, 胡志华. 基于时空网络的自动化集装箱码头自动化导引车路径规划[J]. 计算机应用, 2020, 40(7): 2155–2163.

    GAO Y L, HU Z H. Path planning for automated guided vehicles based on tempo-spatial network at automated container terminal[J]. Computer Applications, 2020, 40 (7): 2155–2163(in Chinese)
    [20]
    李文霞, 张春民, 马昌喜. 多目标低碳车辆路径优化模型及求解算法[J]. 交通信息与安全, 2020, 38(1): 118–126. https://www.cnki.com.cn/Article/CJFDTOTAL-JTJS202001018.htm

    LI W X, ZHANG C M, MA C X. Multi-objective low-carbon vehicle routing optimization model and solution algorithm[J]. Journal of Transport Information and Safety, 2020, 38(1): 118–126(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JTJS202001018.htm
    [21]
    VU D N, KAP H K. Dispatching method for automated lifting vehicles in automated port container terminals[J]. Computers & Industrial Engineering, 2009, 56(3): 1002–1020.
    [22]
    KIM K H, JEON S M, RYU K R. Deadlock prevention for auto-mated guided vehicles in automated container terminals[J]. ORSpectrum, 2006, 28(4): 659–679.
    • Relative Articles
    • Supplements(0)
    • Cited By
  • 加载中

Catalog

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

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

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

    Figures(10)  / Tables(10)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (1455) PDF downloads(109) Cited by()
    Proportional views
    Related

    Copyright Editorial Office of Transport Information and Safety鄂ICP备05003336号-2

    Address：No. 1178，Heping Avenue, Wuchang, Wuhan, CHINA (430063)

    Tel：027-86580355 Email：jtjsj@vip.163.com

    Supported by: Beijing Renhe Information Technology Co. Ltd  

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return