Please wait a minute...
工程设计学报  2017, Vol. 24 Issue (4): 440-448    DOI: 10.3785/j.issn.1006-754X.2017.04.011
建模、分析、优化和决策     
基于动态时间窗的泊车系统路径规划研究
朱龙彪1, 王辉1, 王景良2, 邵小江1, 朱志慧3
1. 南通大学 机械工程学院, 江苏 南通 226019;
2. 江苏海事职业技术学院, 江苏 南京 211199;
3. 江苏金冠立体停车股份有限公司, 江苏 南通 226003
Research on path planning of parking system based on dynamic time window
ZHU Long-biao1, WANG Hui1, WANG Jing-liang2, SHAO Xiao-jiang1, ZHU Zhi-hui3
1. School of Mechanical Engineering, Nantong University, Nantong 226019, China;
2. Jiangsu Maritime Institute, Nanjing 211199, China;
3. Jiangsu Jinguan Solid Parking System Engineering Co., Ltd., Nantong 226003, China
 全文: PDF(9733 KB)   HTML
摘要:

针对智能立体停车库中自动导引运输车(automated guided vehicle,AGV)存取车路径规划问题,采用分时利用策略,将Dijkstra算法和时间窗法有效结合,提出了一种基于动态时间窗的泊车系统路径规划方法。首先,通过引入优先级策略为接收任务的AGV设定优先级;其次,采用Dijkstra算法,按照任务优先级高低次序,依次为接受任务的AGV规划出最短可行路径;最后,在已知AGV可行路径基础上,通过对可行路径各路段的时间窗进行初始化、实时更新以及实时排布处理,实现多AGV的无冲突路径规划。为验证所提方法的可行性和有效性,以4台AGV同时工作的智能立体停车库为实例进行仿真测试。结果显示:所提出的路径规划方法不仅有效解决了目前多AGV路径规划柔性差、易出现死锁、碰撞冲突等问题,而且可在有效解决路径冲突的前提下,为接受任务的AGV规划出一条时间最短的优化路径。所提方法具有较好的鲁棒性和柔性,有效提高了智能立体停车系统整体运行效率,降低了存取车等待时间。

关键词: Dijkstra算法时间窗泊车系统AGV路径规划    
Abstract:

To solve path planning problems of accessing cars by AGV (automated guided vehicle) in the intelligent lift parking garage,the strategies of time-sharing use were utilized,and a path planning method of parking system based on dynamic time window was proposed through effec-tively combining Dijkstra algorithm and time window.First of all,the AGV having task was as-signed the priorities by the introduction of priority strategy.Then,according to the task priority order,Dijkstra algorithm was used to plan the shortest feasible path for the AGV having task. Finally,on the basis of feasible AGV's path,multiple AGV collision-free path planning was a-chieved by the method which contained time window initialization,time window real-time update and real-time arrangement.To test and verify the feasibility and effectiveness of path planning al-gorithm of parking system based on dynamic time window,the intelligent lift parking garage with four AGVs working at the same time was tested in the simulation experiment.The experi-mental results showed that the proposed method could solve some problems in the multiple AGV path planning,which included poor flexibility,easily arising deadlock conflict and collision con-flict,etc.Furthermore,the proposed method also could plan out a minimum-time optimal path for the AGV having task under the premise of effectively solving path conflicts.The results indi-cate that the method is correct,feasible and effective,and has a better robustness and flexible. Besides,it can effectively improve the overall operating efficiency of the intelligent parking system and reduce waiting time for accessing cars.

Key words: Dijkstra algorithm    time window    parking system    AGV    path planning
收稿日期: 2016-10-25 出版日期: 2017-08-28
CLC:  TP249  
基金资助:

国家自然科学基金资助项目(51405246);江苏省产学研联合创新资金项目(BY2014081-07);南通市重点实验室项目(CP2014001);南通市应用基础研究工业创新项目(GY12016006)

作者简介: 朱龙彪(1964-),男,江苏如皋人,教授,硕士,从事机电控制、故障诊断等研究,E-mail:zhulb@ntu.edu.cn,http://orcid.org/0000-0001-7105-4258
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章  
朱龙彪
王辉
王景良
邵小江
朱志慧

引用本文:

朱龙彪, 王辉, 王景良, 邵小江, 朱志慧. 基于动态时间窗的泊车系统路径规划研究[J]. 工程设计学报, 2017, 24(4): 440-448.

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.

链接本文:

https://www.zjujournals.com/gcsjxb/CN/10.3785/j.issn.1006-754X.2017.04.011        https://www.zjujournals.com/gcsjxb/CN/Y2017/V24/I4/440

[1] 王辉,朱龙彪,朱天成,等.基于粒子群遗传算法的泊车系统路径规划研究[J].工程设计学报,2016,23(2):195-200. WANG Hui,ZHU Long-biao,ZHU Tian-cheng,et al. Research on path planning of parking system based on PSO-genetic hybrid algorithm[J].Chinese Journal of Engineering Design,2016,23(2):195-200.
[2] FAZLOLLAHTABAR H,SAIDI M M.Optimal path in an intelligent AGV-based manufacturing system[J]. Transportation Letters:the International Journal of Transportation Research,2015,7(4):219-228.
[3] MAJDI M,ANVAR H S,BARZAMINI R,et al.Multi AGV path planning in unknown environment using fuzzy inference systems[C].20083rd IEEE International Symposium on Control, Communications and Signal Processing (ISCCSP 2008).St Julians, Malta, Mar. 12-14,2008.
[4] NISHI T,MAENO R.Petri net decomposition approach to optimization of route planning problems for AGV sys-tems[J].IEEE Transactions on Automation Science and Engineering,2010,7(3):523-537.
[5] UMAR U A,ARIFFIN M K A,ISMAIL N,et al.Hy-brid multi-objective genetic algorithms for integrated dy -namic scheduling and routing of jobs and automated guided vehicle (AGV) in flexible manufacturing systems (FMS) environment[J].International Journal of Ad-vanced Manufacturing Technology, 2015, 81(9/12):2123-2141.
[6] KRNJAK A,DRAGANJAC I,BOGDAN S,et al.De-centralized control of free ranging AGVs in warehouse environments[C].2015 IEEE International Conference on Robotics and Automation (ICRA).Seattle, May. 26-30,2015.
[7] SMOLI? R N,BOGDAN S,KOVA?I?Z,et al.Time windows based dynamic routing in multi-AGV systems[J].IEEE Transactions on Automation Science & Engi-neering,2010,7(1):151-155.
[8] RAJOTIA S, SHANKER K, BATRA J L.Semi-dynamic time window constrained routeing strategy in an AGV system[J].International Journal of Production Research,1998,36(1):35-50.
[9] CHEN T J,SUN Y,DAI W,et al.On the shortest and conflict-free path planning of multi-AGV system based on Dijkstra algorithm and the dynamic time window method[J].Advanced Materials Research,2013,645:267-271.
[10] BALSEIRO S R,LOISEAUB I,RAMONET J.An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing prob-lem with time windows[J].Computers & Operations Research,2011,38(6):954-966.
[11] GUO L X,YANG Q,YAN W J.Intelligent path plan-ning for automated guided vehicles system based on to-pological map[C].2012 IEEE Conference on Control, Systems and Industrial Informatics. Bandung, Indonesia,Sep.23-26,2012.
[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] 乔岩,钱晓明,楼佩煌,等.基于改进时间窗的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.
[14] 胡彬,王冰,王春香,等.一种基于时间窗的自动导引车动态路径规划方法[J].上海交通大学学报,2012, 46(6):967-971. HU Bin,WANG Bing,WANG Chun-xiang,et al.Dy-namic routing of automated guided vehicles based on time window[J].Journal of Shanghai Jiaotong Univer-sity,2012,46(6):967-971.
[15] 霍凯歌,张亚琦,胡志华.自动化集装箱码头多载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 terminal[J].Journal of Dalian University of Technology,2016,56(3):244-251.
[16] 苏霞,李伟光.FMS中自动导引车路径规划[J].机械设计与制造,2015(1):201-203. SU Xia, LI Wei-guang.Path planning of automated guided vehicles in FMS[J].Machinery Design & Man-ufacture,2015(1):201-203.
[17] MIYAMOTO T, INOUE K. Local and random searches for dispatch and conflict-free routing problem of capacitated AGV systems[J].Computers & Industrial Engineering,2016,91:1-9.
[1] 唐东林, 龙再勇, 汤炎锦, 潘峰, 游传坤. 储罐检测爬壁机器人全遍历路径规划[J]. 工程设计学报, 2020, 27(2): 162-171.
[2] 周结华, 代冀阳, 周继强, 张孝勇. 面向大型机场草坪的割草机器人路径规划及轨迹跟踪控制研究[J]. 工程设计学报, 2019, 26(2): 146-152.
[3] 唐东林, 袁波, 胡琳, 李茂扬, 魏子兵. 储罐探伤爬壁机器人全遍历路径规划方法[J]. 工程设计学报, 2018, 25(3): 253-261.
[4] 梁承姬, 沈珊珊, 胡文辉. 基于路段时间窗考虑备选路径的AGV路径规划[J]. 工程设计学报, 2018, 25(2): 200-208.
[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.