Please wait a minute...
工程设计学报
工程设计学报  2018, Vol. 25 Issue (2): 200-208    DOI: 10.3785/j.issn.1006-754X.2018.02.011
建模、仿真、分析与决策     
基于路段时间窗考虑备选路径的AGV路径规划
梁承姬1, 沈珊珊1, 胡文辉2
1. 上海海事大学 物流研究中心, 上海 201306;
2. 上海振华重工(集团)股份有限公司, 上海 200125
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
 全文: PDF(2244 KB)   HTML
摘要：

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

国家自然科学基金资助项目（71471110）；上海市科委创新项目（16040501500，16DZ1201402）
作者简介: 梁承姬(1970-),女,朝鲜族,吉林龙井人,教授,博士生导师,博士,从事集装箱港口物流研究,E-mail:liangcj@shmtu.edu.cn,http://orcid.org/0000-0001-6693-7347
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
梁承姬
沈珊珊
胡文辉

引用本文:

梁承姬, 沈珊珊, 胡文辉. 基于路段时间窗考虑备选路径的AGV路径规划[J]. 工程设计学报, 2018, 25(2): 200-208.

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.

链接本文:

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

[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] 唐东林, 龙再勇, 汤炎锦, 潘峰, 游传坤. 储罐检测爬壁机器人全遍历路径规划[J]. 工程设计学报, 2020, 27(2): 162-171.
[2] 周结华, 代冀阳, 周继强, 张孝勇. 面向大型机场草坪的割草机器人路径规划及轨迹跟踪控制研究[J]. 工程设计学报, 2019, 26(2): 146-152.
[3] 唐东林, 袁波, 胡琳, 李茂扬, 魏子兵. 储罐探伤爬壁机器人全遍历路径规划方法[J]. 工程设计学报, 2018, 25(3): 253-261.
[4] 朱龙彪, 王辉, 王景良, 邵小江, 朱志慧. 基于动态时间窗的泊车系统路径规划研究[J]. 工程设计学报, 2017, 24(4): 440-448.
[5] 李保坤, 韩迎鸽, 郭永存, 曹毅, 王成军. Gough-Stewart并联机构无奇异位置路径规划[J]. 工程设计学报, 2016, 23(6): 544-552.
[6] 王辉, 朱龙彪, 王景良, 陈红艳, 邵小江, 朱志慧. 基于Dijkstra-蚁群算法的泊车系统路径规划研究[J]. 工程设计学报, 2016, 23(5): 489-496.
[7] 王辉, 朱龙彪, 朱天成, 陈红艳, 邵小江, 朱志慧. 基于粒子群遗传算法的泊车系统路径规划研究[J]. 工程设计学报, 2016, 23(2): 195-200.
[8] 肖浩, 宋晓琳, 曹昊天. 基于危险斥力场的自动驾驶汽车主动避撞局部路径规划[J]. 工程设计学报, 2012, 19(5): 379-384.
[9] 孙亮, 孙建镇. 自动导引小车系统运输能力的设计研究[J]. 工程设计学报, 2005, 12(6): 359-362.