基于改进Dijkstra算法的泊车系统路径规划研究

doi:10.16731/j.cnki.1671-3133.2017.08.012

现代制造工程 ›› 2017, Vol. 443 ›› Issue (8): 63-67.doi: 10.16731/j.cnki.1671-3133.2017.08.012

• CAD/CAE/CAPP/CAM • 上一篇下一篇

基于改进Dijkstra算法的泊车系统路径规划研究

陈亚琳¹, 庄丽阳², 朱龙彪², 邵小江², 王恒²

1 南京工业职业技术学院电气工程学院,南京 210023;
2 南通大学机械工程学院,南通 226019

收稿日期:2016-03-28 出版日期:2017-08-20 发布日期:2018-01-09
作者简介:庄丽阳,通讯作者,实验师,主要从事机电控制、智能算法等方面的研究工作。E-mail:whzl2014@126.com
基金资助:
国家自然科学基金项目(51405246);江苏省产学研联合创新资金项目(BY2014081-07);南通市重点实验室项目(CP2014001);南通市应用基础研究-工业创新项目(GY12016006)

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

Chen Yalin¹, Zhuang Liyang², Zhu Longbiao², Shao Xiaojiang², Wang Heng²

1 School of Electrical Engineering,Nanjing Vocational Institute of Industry Technology, Nanjing 210023,China;
2 School of Mechanical Engineering,Nantong University,Nantong 226019,Jiangsu,China

Received:2016-03-28 Online:2017-08-20 Published:2018-01-09

摘要/Abstract

摘要： 为了解决智能车库中自动导引运输车(Automated Guided Vehicle,AGV)存取车路径规划问题和克服传统Dijkstra算法时间复杂度高、搜索范围大及搜索效率低等缺陷,提出了一种基于改进Dijkstra算法的泊车系统路径规划方法。首先以智能车库某时刻空闲泊车位的分布情况为背景,创建该时刻目标泊车位的带权无向图;其次,通过更改数据存储结构和引入双向搜索策略对传统Dijkstra算法进行改进;最后,以距离最短为评价指标,以传统Dijkstra算法和改进Dijkstra算法为路径寻优方法,在MATLAB环境下对AGV存取车路径规划过程进行仿真测试。结果表明:改进Dijkstra算法正确、可行及有效,与传统Dijkstra算法相比,能有效节省数据存储空间,减少搜索时间,提高搜索效率,可以满足AGV存取车路径规划要求。

关键词: Dijkstra算法, 泊车系统, 自动导引运输车, 路径规划

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

中图分类号:

陈亚琳, 庄丽阳, 朱龙彪, 邵小江, 王恒. 基于改进Dijkstra算法的泊车系统路径规划研究[J]. 现代制造工程, 2017, 443(8): 63-67.

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.

参考文献

[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.

基于改进Dijkstra算法的泊车系统路径规划研究

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	郑晓军，王琨，曹梦媛，宁诗铎. 仿真环境下的泊位指派与箱位分配协调优化[J]. 现代制造工程, 2022, 498(3): 13-18.
[2]	荆泽成，张秋菊，杨瑞. 基于改进RRT的核退役机器人避障方法[J]. 现代制造工程, 2022, 497(2): 46-51.
[3]	袁福龙，朱建平. 基于改进蚁群算法的移动机器人最优路径规划[J]. 现代制造工程, 2021, 490(7): 38-47.
[4]	王昀睿，赵旭雯，武争利，蒋子强. 基于混流生产模式的装配车间物料配送路径规划方法[J]. 现代制造工程, 2021, 490(7): 109-116.
[5]	张瑞杰，何舟，施威杰. 基于Petri网的车间物料配送及路径规划方法[J]. 现代制造工程, 2021, 489(6): 17-24.
[6]	何飞翔，朱小明，韩伟，李凤静. 模具零件数控加工在线检测宏程序编程及应用[J]. 现代制造工程, 2021, 488(5): 70-74.
[7]	袁鹏，周军，杨子兵，吴迪，皇攀凌. AGV路径规划与偏差校正研究[J]. 现代制造工程, 2021, 487(4): 26-32.
[8]	王建,张弓,何文杰,徐征,侯至丞,杨文林,王坛,脱帅华. 基于V-REP的双机器人协同运动仿真与实验研究[J]. 现代制造工程, 2021, 495(12): 21-27.
[9]	雷斌，金彦彤，王致诚，赵蕊，胡方鑫. 仓储物流机器人技术现状与发展[J]. 现代制造工程, 2021, 495(12): 143-153.
[10]	田海波，李陆军，畅科剑，高超，. 用于无人车路径规划的改进A*算法[J]. 现代制造工程, 2021, 494(11): 63-68.
[11]	孔慧芳,盛阳. 基于改进A*算法的AGV路径规划研究[J]. 现代制造工程, 2021, 493(10): 60-64.
[12]	方喜峰, 罗晓梅, 徐精英, 程德俊, 张胜文, 汪通悦, 胡传林. 大型船用螺旋桨桨毂粗加工刀具路径规划研究[J]. 现代制造工程, 2021, 484(1): 69-74.
[13]	杜玉红，张岩，赵焕峰. 基于参数优化蚁群算法的机器人路径规划研究[J]. 现代制造工程, 2020, 480(9): 7-14.
[14]	章盼梅. 单模单冲数控冲床加工路径优化方法研究[J]. 现代制造工程, 2020, 476(5): 71-76.
[15]	张维,马志华,杨洋洋,吴燕. 基于改进遗传模拟退火算法的刀具准时化配送路径规划[J]. 现代制造工程, 2020, 481(10): 83-90.