Please wait a minute...
工程设计学报
Chinese Journal of Engineering Design  2018, Vol. 25 Issue (2): 200-208    DOI: 10.3785/j.issn.1006-754X.2018.02.011
    
AGV path planning considering alternative paths based on time window of road section
LIANG Cheng-ji1, SHEN Shan-shan1, HU Wen-hui2
1. Logistics Research Center, Shanghai Maritime University, Shanghai 201306, China;
2. Shanghai Zhenhua Port Machinery Company Limited, Shanghai 200125, China
Download: HTML     PDF(2244KB)
Export: BibTeX | EndNote (RIS)      

Abstract  

To solve the problem of the automated guided vehicle (AGV) path planning based on the unloader task of automated container terminal, an AGV path planning method based on time window of road section was proposed through combining the optimal path mathematical model, path searching method and time window. First of all, the AGV with dispatched task was planned the shortest path by the optimal path mathematical model. Secondly, AGV alternative paths were selected through path searching method. When the path length was the same, the selection priority was determined by the number of turning times in the path, and the alternative path with fewer turning times had higher priority. Finally, time windows of road section were set up under AGV shortest path. If the time windows on the same road section were not overlapped, then the AGV was collision free on the path. As for the overlapped time window of road section, the time window would be inserted into the original path or the alternative path. Then time window's overlap test and adjustment continued if there still existed overlaps until the multiple AGV paths planning without time window overlap. In order to verify the validity of the method, a case of eight AGVs working simultaneously was experimented to prove that the proposed path planning method had good free-collision effect on AGVs. The results showed that this method could be used to plan a non-conflict optimization path for AGVs working simultaneously and to get the shorter time path availably. It was found that the method of insert time window on the alternative path was better. The reasearch shows that the proposed method has good free-collision effect on AGVs. Besides, it can effectively improve the efficiency of AGV utilization and automatic container terminal operation.

Key words： automated container terminal      automated guided vehicle(AGV)      time window      path planning     
Received: 20 November 2017      Published: 28 April 2018
CLC:  TP29  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
LIANG Cheng-ji
SHEN Shan-shan
HU Wen-hui
Cite this article:

LIANG Cheng-ji, SHEN Shan-shan, HU Wen-hui. AGV path planning considering alternative paths based on time window of road section. Chinese Journal of Engineering Design, 2018, 25(2): 200-208.

URL:

https://www.zjujournals.com/gcsjxb/10.3785/j.issn.1006-754X.2018.02.011     OR     https://www.zjujournals.com/gcsjxb/Y2018/V25/I2/200


基于路段时间窗考虑备选路径的AGV路径规划

针对自动化集装箱码头基于卸箱任务的自动导引车（automated guided vehicle，AGV）路径规划问题，结合最优路径数学模型、路径搜索方法和时间窗，提出了一种基于路段时间窗的AGV路径规划方法。首先，在给AGV下派任务的基础上，用最优路径数学模型为AGV规划出最短路径；其次，用路径搜索方法搜索AGV的备选路径，在路径长度相同的情况下，按照路径中转折次数确定备选路径优先级，转折次数少的备选路径优先级高；最后，在各AGV最短路径下，设置各个路段的时间窗，时间窗无重叠则表明AGV无冲突，对于时间窗重叠的路段，采用在原路径上插入时间窗或者在备选路径上插入时间窗的方法，再进行时间窗重叠测试，若还存在重叠的，则继续调整至最终实现多AGV的无冲突路径规划。为了验证方法的有效性，以8台AGV分区同时工作为例，用实例证明所提出的路径规划方法的避碰效果。结果显示该方法能为多台同时工作的AGV规划出一条无冲突优化路径，并且用时较短；在试验中发现选择在备选路径上插入时间窗的方法效果更好。研究表明所提方法能有效实现AGV的避碰，提高AGV利用率和自动化集装箱码头的运作效率。


关键词： 自动化集装箱码头,  AGV,  时间窗,  路径规划 

[1] 张峥炜,陈波,陈卫东.时间窗约束下的AGV动态路径规划[J].微型电脑应用,2016,32(11):46-49. ZHANG Zheng-wei, CHEN Bo, CHEN Wei-dong. Dynamic routing of automated guided vehicles with time window[J]. Microcomputer Application, 2016, 32(11):46-49.
[2] DUINKERKEN Mark B, LODEWIJKS Gabriel. Routing of AGVs on automated container terminals[C]//2015 IEEE 19th International Conference on Computer Supported Cooperative Work in Design, Calabria, May 6-8, 2015.
[3] SONG Li-qin, HUANG Shell-ying. A hybrid metaheuristic method for dispatching automated guided vehicles in container terminals[C]//2013 IEEE Symposium on Computational Intelligence in Scheduling (SCIS), Singapore, Apr.16-19, 2013.
[4] 霍凯歌,张亚琦,胡志华.自动化集装箱码头多载AGV调度问题研究[J].大连理工大学学报,2016,56(3):244-251. HUO Kai-ge, ZHANG Ya-qi, HU Zhi-hua. Research on scheduling problem of multi-load AGV at automated container terminals[J]. Journal of Dalian University of Technology, 2016, 56(3):244-251.
[5] NISHI T, HIRANAKA Y, GROSSMANN I E. A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles[J]. Computers and Operations Research, 2011, 38(5):876-888.
[6] XIN Jian-bin, NEGENBORN R R, CORMAN F, et al. Control of interacting machines in automated container terminal using a sequential planning approach for collision avoidance[J]. Transportation Research Part C:Emerging Technologies, 2015:60, 377-396.
[7] 冯海双.AGV自动运输系统调度及路径规划的研究[D].哈尔滨:哈尔滨工业大学机电工程学院,2013:1-73. FENG Hai-shuang. Research on scheduling and path planning of AGV automatic transport system[D]. Harbin:Harbin Institute of Technology, School of Mechatronics Engineering, 2013:1-73.
[8] 蓝志坤,蓝志环.多AGV系统的动态路径规划算法[J].公路交通科技,2012(10):121-125. LAN Zhi-kun, LAN Zhi-huan. Algorithm of dynamic path planning for multiple AGV system[J]. Highway Traffic Technology, 2012(10):121-125.
[9] 苏霞,李伟光.FMS中自动导引车路径规划[J].机械设计与制造,2015(1):201-203. SU Xia, LI Wei-guang. Path planning of automated guided vehicles in FMS[J]. Mechanical Design and Manufacturing, 2015(1):201-203.
[10] 乔岩,钱晓明,楼佩煌,等.基于改进时间窗的AGVs避碰路径规划[J].计算机集成制造系统,2012,18(12):2683-2688. QIAO Yan, QIAN Xiao-ming, LOU Pei-huang, et al. Improved time window based conflict-free automated guided vehicle system routing[J]. Computer Integrated Manufacturing Systems, 2012, 18(12):2683-2688.
[11] 朱龙彪,王辉,王景良,等.基于动态时间窗的泊车系统路径规划研究[J].工程设计学报,2017,24(4):440-448. ZHU Long-biao, WANG Hui, WANG Jing-liang, et al. Research on path planning of parking system based on dynamic time window[J]. Chinese Journal of Engineering Design, 2017, 24(4):440-448.
[12] 贺丽娜,楼佩煌,钱晓明,等.基于时间窗的自动导引车无碰撞路径规划[J].计算机集成制造系统,2010,16(12):2630-2634. HE Li-na, LOU Pei-huang, QIAN Xiao-ming, et al. Conflict-free automated guided vehicles routing based on time window[J]. Computer Integrated Manufacturing Systems, 2010, 16(12):2630-2634.
[13] 胡彬,王冰,王春香,等.一种基于时间窗的自动导引车动态路径规划方法[J].上海交通大学学报,2012,46(6):967-971. HU Bin, WANG Bing, WANG Chun-xiang, et al. Dynamic routing of automated guided vehicle based on time window[J]. Journal of Shanghai Jiaotong University, 2012, 46(6):967-971.
[14] SMOLIC-ROCAK N, BOGDAN S, KOVACIC Z, et al. Time windows based dynamic routing in multi-AGV systems[J]. Transactions on Automation Science and Engineering, 2010, 7(1):151-155.
[15] FAZLOLLAHTABAR H, SAIDI-MEHRABAD M, BALAKRISHNAN J. Mathematical optimization for earliness/tardiness minimization in a multiple automated guided vehicle manufacturing system via integrated heuristic algorithms[J]. Robotics and Autonomous Systems, 2015, 72:131-138.
[16] LEHMANN M, GRUNOW M, GUNTHER H O. Deadlock handling for real-time control of AGVs at automated container terminals[J]. OR Spectrum:Quantitative Approaches in Management, 2006, 28(4):631-657.
[17] PARK J H, KIM H J, LEE C. Ubiquitous software controller to prevent deadlocks for automated guided vehicle systems in a container port terminal environment[J]. Journal of Intelligent Manufacturing, 2009, 20(3):321-325.
[18] 杨勇生,崔佳羽,梁承姬,等.基于软时间窗的自动化集装箱码头AGV路径规划[J].广西大学学报(自然科学版),2017,42(5):1793-1801. YANG Yong-sheng, CUI Jia-yu, LIANG Cheng-ji, et al. Research on the routing of AGV in automated container terminal based on soft time window[J]. Journal of Guangxi University (Natural Science Edition), 2017, 42(5):1793-1801.
[1] TANG Dong-lin, LONG Zai-yong, TANG Yan-jin, PAN Feng, YOU Chuan-kun. Complete coverage path planning of oil tank detection wall climbing robot[J]. Chinese Journal of Engineering Design, 2020, 27(2): 162-171.
[2] ZHOU Jie-hua, DAI Ji-yang, ZHOU Ji-qiang, ZHANG Xiao-yong. Research on path planning and trajectory tracking control of mowing robot for large airport lawn[J]. Chinese Journal of Engineering Design, 2019, 26(2): 146-152.
[3] TANG Dong-lin, YUAN Bo, HU Lin, LI Mao-yang, WEI Zi-bing. Complete coverage path planning method for oil tank inspection wall climbing robot[J]. Chinese Journal of Engineering Design, 2018, 25(3): 253-261.
[4] ZHU Long-biao, WANG Hui, WANG Jing-liang, SHAO Xiao-jiang, ZHU Zhi-hui. Research on path planning of parking system based on dynamic time window[J]. Chinese Journal of Engineering Design, 2017, 24(4): 440-448.
[5] LI Bao-kun, HAN Ying-ge, GUO Yong-cun, CAO Yi, WANG Cheng-jun. Singularity-free position path planning of the Gough-Stewart parallel mechanism[J]. Chinese Journal of Engineering Design, 2016, 23(6): 544-552.
[6] WANG Hui, ZHU Long-biao, WANG Jing-liang, CHEN Hong-yan, SHAO Xiao-jiang, ZHU Zhi-hui. Research on path planing of parking system based on Dijkstra-Ant colony hybrid algorithm[J]. Chinese Journal of Engineering Design, 2016, 23(5): 489-496.
[7] WANG Hui, ZHU Long-biao, ZHU Tian-cheng, CHEN Hong-yan, SHAO Xiao-jiang, ZHU Zhi-hui. Research on path planning of parking system based on PSO-genetic hybrid algorithm[J]. Chinese Journal of Engineering Design, 2016, 23(2): 195-200.
[8] XIAO Hao, SONG Xiao-Lin, CAO Hao-Tian. Local path planning for autonomous vehicle collision avoidance based on dangerous repellant fields[J]. Chinese Journal of Engineering Design, 2012, 19(5): 379-384.
[9] SUN Liang, SUN Jian-Zhen. Research on designing of transportation capability in AGVS[J]. Chinese Journal of Engineering Design, 2005, 12(6): 359-362.