Research on path planing of parking system based on the improved Dijkstra algorithm

doi:10.16731/j.cnki.1671-3133.2017.08.012

Abstract

Abstract: In order to solve the path planning problem of AGV accessing cars in intelligent garage,and overcome the defect of traditional Dijkstra algorithm,which includes higher time complexity,larger search scope and lower search efficiency etc,the path planning method of parking system based on the bi-directional Dijkstra algorithm was proposed.In this paper,firstly,the weighted undirected graph of the target parking spot was created on the basis of the distribution of free parking spot at a certain time in intelligent garage.Secondly,the traditional Dijkstra algorithm was optimized and improved through altering the data storage structure and introducing the bidirectional search strategy.Finally,the shortest path length was used as evaluation index,the traditional Dijkstra algorithm and improved Dijkstra algorithm used as search strategy,the path planning process of AGV accessing cars was simulated with MATLAB software.The simulation results show improved Dijkstra algorithm is correct,feasible and effective.Moreover,compared with traditional Dijkstra algorithm,improved Dijkstra algorithm can effectively reduce data store space and improve search efficiency,and can meet the requirement of AGV accessing cars in path planning.

Key words: Dijkstra algorithm, parking system, Automated Guided Vehicle (AGV), path planning

CLC Number:

Chen Yalin, Zhuang Liyang, Zhu Longbiao, Shao Xiaojiang, Wang Heng. Research on path planing of parking system based on the improved Dijkstra algorithm[J]. Modern Manufacturing Engineering, 2017, 443(8): 63-67.

References

[1] CHARLES E Benedict,BRIAN G Pfeifer,CHRISTIAN A Yates,et al.Automated automotive vehicle parking/storage system[P].US Patent:US12855017,2014-05-27.
[2] 王辉,朱龙彪,朱天成,等.基于粒子群遗传算法的泊车系统路径规划研究[J].工程设计学报,2016,23(2):195-200.
[3] LI D L,NIU K.Dijkstra’s algorithm in AGV.Proceedings of the 2014 9th IEEE Conference on Industrial Electronics and Applications,ICIEA[C].New York,United states:Institute of Electrical and Electronics Engineers Inc,2014:1867-1871.
[4] 马飞,杨皞屾,顾青,等.基于改进A^*算法的地下无人铲运机导航路径规划[J].农业机械学报,2015,46(7):303-309.
[5] JOHNSON F,VEGA J,CABRERA G,et al.Ant colony system for a problem in reverse logistic[J].Studies In Informatics And Control,2015,24(2):133-140.
[6] LEE J,KANG BY,KIM DW.Fast genetic algorithm for robot path planning[J].Electronics Letters,2013,49(23):1449-1451.
[7] WANG S X.The improved Dijkstra’s shortest path algorithm and its application[J].Procedia Engineering,2012(29):1186-1190.
[8] DENG Y,CHEN Y X,ZHANG Y J,et al.Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment[J].Applied Soft Computing,2012,12(3):1231-1237.
[9] HUANG Y Z,YI QM,SHI M.An improved Dijkstra’s algorithm based on search strategy[J].Applied Mechanics and Materials,2013(380-384):1625-1628.
[10] ZHENG Y C,DENG Y,ZHU Q M.Ship damage control as a service based on spatio-temporal database.IEEE International Conference on Cloud Engineering (IC2E)[C].Boston,United states:Institute of Electrical and Electronics Engineers Inc,2014:500-504.
[11] WANG R,WANG N.Research on vehicle path planning base on Intelligent transport system[J].Applied Mechanics and Materials,2014(513-517):1822-1825.
[12] GAYATHRI N,CHANDRAKALA K R M V.A novel technique for optimal vehicle routing.International Conference on Electronics and Communication Systems (ICECS)[C].NY,USA:IEEE,2014:1-5.
[13] 彭红星,解凤玲.改进Dijkstra算法在停车诱导系统中的应用与仿真[J].计算机应用,2011,31(z2):63-66.
[14] 刘姣,葛召炎,谢静,等.停车场泊车问题的研究与仿真[J].计算机仿真,2011,28(7):340-344.
[15] 李明.详解MATLAB在最优化计算中的应用[M].北京:电子工业出版社,2011:353-363.
[16] 李伟,余森,王伟.基于时间最短路径的停车场车位引导算法[J].自动化仪表,2015(8):23-25.
[17] 唐彩红.基于方向优先和对向搜索的改进Dijkstra算法[J].计算机与现代化,2014(7):113-116.
[18] 李杰,张文栋,杨卫.双向Dijkstra算法设计与实现[J].测试技术学报(增刊),2007(21):110-114.
[19] GAO J,JIN RM,ZHOU JS,et al.Relational approach for shortest path discovery over large graphs[J].Proceedings of the VLDB Endowment,2011,5(4):358-369.