Urban Vehicle Routing Based on Ant Colony Algorithm
-
摘要: 针对城市交通路径选择问题,引入蚁群算法并将其改进为可同时满足对路程和时间最优的路径搜索算法,设计了相关的搜索规则和流程.在大量试验的基础上,讨论了算法中各种参数对路径搜索算法收敛性(包括收敛速度和准确度)的影响,并获得了一组最优的经验参数.分析了搜索中产生伪最优解路径的规律,并通过控制收敛速度和加快趋向最优路径对蚁群算法进行了优化.结果显示,所进行的优化能有效抑制伪最优路径的产生,在2个周期内即可完成搜索.Abstract: To solve the problem of urban traffic vehicle routing,an improved ant colony system(ACS) algorithm was proposed.The algorithm focuses on both distance and time costs of path planning.Its search rules and flow charts were given.Based on extensive simulation results,the effects of parameters of the algorithm on the convergence performance,including convergence rate and convergence accuracy,were discussed,and a set of empirical parameters were obtained.The reasons for fake optimal paths involved in the search were analyzed.Further,the algorithm was optimized by controlling the convergence rate and forcing the convergence toward to the optimal path.The simulation result indicates that the optimization is effective in restraining fake optimal paths and has a convergence rate within 2 cycles per search.
-
Key words:
- ant colony system algorithm /
- urban traffic /
- path planning /
- inspired heuristics search
-
吴启迪,汪镭.智能蚁群算法及应用[M].上海:上海科技出版社,2004.[2] VLACHOGIANNIS J G,HATZIARGYRIOU N D,LEE K Y.Ant colony system-based algorithm for constrained load flow problem[J].IEEE Transactions on Power Systems,2005,20(3):1241-1249.[3] DORIGO M,GAMBARDELLA M.Ant colonies for the travelling salesman problem[J].BioSystems,1997:73-81.[4] DORIGO M,GAMBARDELLA M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997,1 (1):53-66.[5] RIZZOLI A E,OLIVERIO F,MONTEMANNI R,et al.Ant colony optimisation for vehicle routing problems:from theory to applications[J].Reports of Istituto Dalle Molle di Studi sullIntelligenza Artificiale,2004,9 (1):1-50.[6] 刘志硕,中金升,柴跃廷.基于自适应蚁群算法的车辆路径问题研究[J].控制与决策,2005,20(5):562-566.LIU Zhishuo,SHEN Jinsheng,CHAI Yueting.Vehicle routing problem based on an adaptive ant colony algorithm[J].Control and Decision,2005,20(5):562-566.[7] 王旭,崔平远,陈阳舟.基于蚁群算法求路径规划问题的新方法及仿真[J].计算机仿真,2005,22(7):60-64.WANG Xu,CUI Pingyuan,CHEN Yangzhou.A new method and simulation for path planning problem based on ant colony algorithm[J].Computer Simulation,2005,22 (7):60-64.[8] BULLNHEIMER B,HARTL R F,STRAUSS C.Applying the ant system to the vehicle routing problem[C]//Proceeligs of 2nd International Conference on Metaheuristies.Vienna,INRIA PRiSM-Versailles,1997:1-12.[9] 吴必军,李利新,雷小平.基于城市道路数据库的最短路径搜索[J].西南交通大学学报,2003,38(1):80-83.WU Bijun,LI Lixin,LEI Xiaoping.Shortest path searching based on city road database[J].Journal of Southwest Jiaotong University,2003,38(1):80-83.[10] BULLNHEIMER B,HARTL R F,STRAUSS C.An improved ant system algorithm for the vehicle routing problem[J].Annals of Operations Research,1999,8(9):319-328.[11] 金飞虎,洪炳熔,高庆吉.基于蚁群算法的自由飞行空间机器人路径规划[J].机器人,2002,24(6):526-529.JIN Feihu,HONG Binrong,GAO Qingji.Path planning for free-flying space robot using ant algorithm[J].Robot,2002,24(6):526-529.
点击查看大图
计量
- 文章访问数: 1683
- HTML全文浏览量: 92
- PDF下载量: 615
- 被引次数: 0