Please wait a minute...
工程设计学报
工程设计学报  2016, Vol. 23 Issue (5): 489-496    DOI: 10.3785/j.issn.1006-754X.2016.05.012
整机和系统设计     
基于Dijkstra-蚁群算法的泊车系统路径规划研究
王辉1, 朱龙彪1, 王景良2, 陈红艳1, 邵小江1, 朱志慧3
1. 南通大学 机械工程学院, 江苏 南通 226019;
2. 江苏海事职业技术学院, 江苏 南京 211199;
3. 江苏金冠立体停车股份有限公司, 江苏 南通 226003
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
 全文: PDF(3298 KB)   HTML
摘要：

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

国家自然科学基金资助项目（51405246）；江苏省产学研联合创新基金资助项目（BY2014081-07）；南通市重点实验室项目（CP2014001）.
通讯作者: 朱龙彪,男,江苏如皋人,教授,硕士,从事机电控制和故障诊断等研究,E-mail:zhulb@ntu.edu.cn.http://orcid.org//0000-0002-9913-5348     E-mail: zhulb@ntu.edu.cn
作者简介: 王辉(1989-),男,河南周口人,硕士,从事机械设备可靠性分析、机电控制和智能算法等研究,E-mail:whzl2014@126.com.http://orcid.org//0000-0002-0563-5801
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
王辉
朱龙彪
王景良
陈红艳
邵小江
朱志慧

引用本文:

王辉, 朱龙彪, 王景良, 陈红艳, 邵小江, 朱志慧. 基于Dijkstra-蚁群算法的泊车系统路径规划研究[J]. 工程设计学报, 2016, 23(5): 489-496.

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.

链接本文:

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

[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] 唐东林, 龙再勇, 汤炎锦, 潘峰, 游传坤. 储罐检测爬壁机器人全遍历路径规划[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] 朱龙彪, 王辉, 王景良, 邵小江, 朱志慧. 基于动态时间窗的泊车系统路径规划研究[J]. 工程设计学报, 2017, 24(4): 440-448.
[6] 李保坤, 韩迎鸽, 郭永存, 曹毅, 王成军. Gough-Stewart并联机构无奇异位置路径规划[J]. 工程设计学报, 2016, 23(6): 544-552.
[7] 邓丽, 王国华, 余隋怀. 遗传-蚁群算法求解司钻控制室操纵器布局优化[J]. 工程设计学报, 2016, 23(2): 143-151.
[8] 王辉, 朱龙彪, 朱天成, 陈红艳, 邵小江, 朱志慧. 基于粒子群遗传算法的泊车系统路径规划研究[J]. 工程设计学报, 2016, 23(2): 195-200.
[9] 苏建宁，王瑞红 ，赵慧娟，张书涛. 基于感性意象的产品造型优化设计[J]. 工程设计学报, 2015, 22(1): 35-41.
[10] 肖浩, 宋晓琳, 曹昊天. 基于危险斥力场的自动驾驶汽车主动避撞局部路径规划[J]. 工程设计学报, 2012, 19(5): 379-384.
[11] 孙亮, 孙建镇. 自动导引小车系统运输能力的设计研究[J]. 工程设计学报, 2005, 12(6): 359-362.
[12] 刘国光, 周剑平. 改进蚁群算法设计拉式膜片弹簧[J]. 工程设计学报, 2004, 11(6): 334-337.