Please wait a minute...
Chinese Journal of Engineering Design  2017, Vol. 24 Issue (4): 440-448    DOI: 10.3785/j.issn.1006-754X.2017.04.011
    
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
Download: HTML     PDF(9733KB)
Export: BibTeX | EndNote (RIS)      

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 wordsDijkstra algorithm      time window      parking system      AGV      path planning     
Received: 25 October 2016      Published: 28 August 2017
CLC:  TP249  
  TP301.6  
Cite this article:

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. Chinese Journal of Engineering Design, 2017, 24(4): 440-448.

URL:

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


基于动态时间窗的泊车系统路径规划研究

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


关键词: Dijkstra算法,  时间窗,  泊车系统,  AGV,  路径规划 
[[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] 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] LIANG Cheng-ji, SHEN Shan-shan, HU Wen-hui. AGV path planning considering alternative paths based on time window of road section[J]. Chinese Journal of Engineering Design, 2018, 25(2): 200-208.
[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.
[10] CHEN Shun-Ping, MEI De-Qing, CHEN Zi-Chen. Design of intelligent navigation system for laser assisted autom ated guided vehicle[J]. Chinese Journal of Engineering Design, 2003, 10(5): 279-282.