Please wait a minute...
工程设计学报
Chinese Journal of Engineering Design  2016, Vol. 23 Issue (5): 489-496    DOI: 10.3785/j.issn.1006-754X.2016.05.012
    
Research on path planing of parking system based on Dijkstra-Ant colony hybrid algorithm
WANG Hui1, ZHU Long-biao1, WANG Jing-liang2, CHEN Hong-yan1, 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(3298KB)
Export: BibTeX | EndNote (RIS)      

Abstract  

Aiming at path planning problem of AGV accessing cars in intelligent solid garage, a hybrid algorithm is proposed by combining Dijkstra algorithm with ant colony algorithm. Firstly, Link Method was used to establish environment model of AGV, Dijkstra algorithm was applied to plan the initial path of AGV. Then, with the methods of nodes random selection mechanism and the combination of local renewal and global renewal of the pheromone, the traditional ant colony algorithm was optimized and improved. Finally, the initial path planned by Dijkstra algorithm was optimized by improved ant colony algorithm. The simulation results showed that the optimized path from starting point to ending point could be attained with Dijkstra algorithm and Dijkstra-Ant colony algorithm on the premise of effectively avoiding obstacles. Moreover, compared with Dijkstra algorithm, Dijkstra-Ant colony algorithm could effectively raise search efficiency, shorten the search path length, and improve the quality of search path. The results indicate that Dijkstra-Ant colony hybrid algorithm is correct, feasible and effective, and simultaneously exhibits stronger global search ability and better convergence performance, and can meet the requirement of AGV accessing cars in path planning.

Key words： Dijkstra algorithm      ant colony algorithm      parking system      AGV      path planning     
Received: 23 February 2016      Published: 28 October 2016
CLC:  TP301.6  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
WANG Hui
ZHU Long-biao
WANG Jing-liang
CHEN Hong-yan
SHAO Xiao-jiang
ZHU Zhi-hui
Cite this article:

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. Chinese Journal of Engineering Design, 2016, 23(5): 489-496.

URL:

https://www.zjujournals.com/gcsjxb/10.3785/j.issn.1006-754X.2016.05.012     OR     https://www.zjujournals.com/gcsjxb/Y2016/V23/I5/489


基于Dijkstra-蚁群算法的泊车系统路径规划研究

针对智能停车库中自动导引运输车（automated guided vehicle，AGV）存取车路径规划问题，提出了一种基于Dijkstra-蚁群算法（Dijkstra-ACO）的泊车系统路径规划方法.首先利用链接可视图法建立环境模型，并在此环境模型下，采用Dijkstra算法规划出AGV的初始路径；其次，通过引入节点随机选择机制、调整信息素更新方式和限定信息素阈值策略等对基本蚁群算法进行优化改进；最后，选用改进的蚁群算法对初始路径进行优化.结果显示：Dijkstra算法和混合算法均能使AGV有效避开障碍物，然后搜索到一条从起点到终点的无碰优化路径；与Dijkstra算法相比，混合算法能有效提高路径搜索效率，缩短搜索路径长度，改善搜索路径质量，表明该算法正确、可行及有效，且具有较强的全局搜索能力和较好的收敛性能，能够满足AGV存取车路径规划的要求.


关键词： Dijkstra算法,  蚁群算法,  泊车系统,  AGV,  路径规划 

[1] 万晓凤,胡伟,方武义,等.基于改进蚁群算法的机器人路径规划研究[J].计算机工程与应用,2014,50(18): 63-66. WAN Xiao-feng, HU Wei, FANG Wu-yi, et al. Research on path planning of robot based on improved ant colony algorithm[J]. Computer Engineering and Applications, 2014, 50(18): 63-66.
[2] JOHNSON F, VEGA J, CABRERA G. Ant colony system for a problem in reverse logistic[J]. Studies in Informatics and Control, 2015, 22(2): 133-140.
[3] 王树西,李安渝.Dijkstra算法中的多邻接点与多条最短路径问题[J].计算机科学, 2014, 41(6): 217-224. WANG Shu-xi, LI An-yu. Multi-adjacent-vertexes and multi-shortest-paths problem of Dijkstra algorithm[J]. Computer Science, 2014, 41(6): 217-224.
[4] 康冰,王曦辉,刘富.基于改进蚁群算法的搜索机器人路径规划[J].吉林大学学报(工学版), 2014, 44(4): 1062-1068. KANG Bing, WANG Xi-hui, LIU Fu. Path planning of searching robot based on improved ant colony algorithm[J]. Journal of Jilin University (Engineering and Technology Edition), 2014, 44(4): 1062-1068.
[5] JIANG Kai, LI Chun-gui. Path planning of robot based on ant colony algorithm[C]. Paris: Atlantis Press, 2015: 757-761.
[6] WANG Jin-guo, WANG Na, JIANG Hui-yu. Robot global path planning based on improved ant colony algorithm[C]. Paris: Atlantis Press, 2015: 2099-2102.
[7] BRAND M, MASUDA M, WEHNER N, et al. Ant colony optimization algorithm for robot path planning[C]. Washington: IEEE Computer Society, 2010: 3436-3440.
[8] 黄震,罗中良,黄时慰.一种带时间窗车辆路径问题的混合蚁群算法[J].中山大学学报(自然科学版), 2015, 54(1): 41-46. HUANG Zhen, LUO Zhong-liang, HUANG Shi-wei. Application research of hybrid ant colony algorithm in vehicle routing problem with time windows[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2015, 54(1): 41-46.
[9] CHAARI I, KOUBAA A, TRIGUI S, et al. Smart path: an efficient hybrid ACO-GA algorithm for solving the global path planning problem of mobile robots[J]. International Journal of Advanced Robotic System, 2014, 11(11): 399-412.
[10] 王美珍,刘学军,吴勇,等.基于可定位视频的电子导游系统[J].测绘通报,2011(2): 48-51. WANG Mei-zhen, LIU Xue-jun, WU Yong, et al. Design of tour guide map based on locatable video[J]. Bulletin of Surveying and Mapping, 2011(2): 48-51.
[11] 何少佳,史剑清,王海坤.基于改进蚁群粒子群算法的移动机器人路径规划[J].桂林理工大学学报, 2014, 34(4): 765-770. HE Shao-jia, SHI Jian-qing, WANG Hai-kun. Path planning for mobile robot based on improved ant colony and particle swarm optimization[J]. Journal of Guilin University of Technology, 2014, 34(4): 765-770.
[12] 李青欣.自动导引车路径规划的遗传算法研究[D].广州:广东工业大学自动化学院,2011: 12-18. LI Qing-xin. Research on genetic algorithm for automated guided vehicle path planning problem[D]. Guangzhou: Guangdong University of Technology, College of Automation, 2011: 12-18.
[13] 黄月,吴成东,董晶晶,等.基于WSN的灾难现场最优逃生路径规划[J].东北大学学报(自然科学版),2013, 34(2): 162-165. HUANG Yue, WU Cheng-dong, DONG Jing-jing, et al. WSN-based optimal path planning for escaping from disaster scene[J]. Journal of Northeastern University (Natural Science), 2013, 34(2): 162-165.
[14] 李明.详解MATLAB在最优化计算中的应用[M].北京:电子工业出版社,2011: 340-362. LI Ming. The application of MATLAB in the optimal calculation[M]. Beijing: Publishing House of Electronics Industry, 2011: 340-362.
[15] 金纯,王升刚,尹远阳.矿井中多机器人搜救系统路径规划[J].机床与液压, 2014, 42(15): 10-14. JIN Chun, WANG Sheng-gang, YIN Yuan-yang. Path planning for multi-robot rescue system under coal mine[J]. Machine Tool & Hydraulics, 2014, 42(15): 10-14.
[16] 王沛栋,唐功友,李扬.带容量约束车辆路由问题的改进蚁群算法[J].控制与决策,2012, 27(11): 1633-1638. WANG Pei-dong, TANG Gong-you, LI Yang. Improved ant colony algorithm for capacitated vehicle routing problems[J]. Control and Decision, 2012, 27(11): 1633-1638.
[17] CHEN Xiong, KONG Ying-ying, FANG Xiang, et al. Fast two-stage ACO algorithm for robotic path planning[J]. Neural Computing and Applications, 2013, 22(2): 313-319.
[18] 谈晓勇,林鹰.基于改进遗传蚁群算法的灾后救援路径规划[J].计算机工程与设计, 2014, 35(7): 2526-2530. TAN Xiao-yong, LIN Ying. Study of disaster relief path planning based on improved genetic ant colony hybrid algorithm[J]. Computer Engineering and Design, 2014, 35(7): 2526-2530.
[19] 屈鸿,黄利伟,柯星.动态环境下基于改进蚁群算法的机器人路径规划研究[J].电子科技大学学报, 2015, 44(2): 260-265. QU Hong, HUANG Li-wei, KE Xing. Research of improved ant colony based robot path planning under dynamic environment[J]. Journal of University of Electronic Science and Technology of China, 2015, 44(2): 260-265.
[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] 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.
[6] 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.
[7] DENG Li, WANG Guo-hua, YU Sui-huai. Genetic-ant colony algorithm to solve layout optimization of manipulators of driller control room[J]. Chinese Journal of Engineering Design, 2016, 23(2): 143-151.
[8] 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.
[9] 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.
[10] SUN Liang, SUN Jian-Zhen. Research on designing of transportation capability in AGVS[J]. Chinese Journal of Engineering Design, 2005, 12(6): 359-362.
[11] LIU Guo-Guang, ZHOU Jian-Ping. Improved ant colony algorithm for optim ization design of pull-type clutch diaphragm spring[J]. Chinese Journal of Engineering Design, 2004, 11(6): 334-337.
[12] 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.