基于蚁群算法的动态路径选择优化方法

交通运输系统工程与信息 ›› 2014, Vol. 14 ›› Issue (3): 97-103.

基于蚁群算法的动态路径选择优化方法

安毅生^*，袁绍欣，赵祥模，岳云

长安大学信息工程学院，西安 710064

收稿日期:2013-08-27 修回日期:2014-03-01 出版日期:2014-06-25 发布日期:2014-07-10
作者简介:安毅生（1972-），男，陕西西安人，教授，博士后.
基金资助:
国家自然科学基金（50978030，51278058）；长江学者和创新团队发展计划（IRT0951）；中国博士后科学基金（2012M521729）；陕西省自然科学基础研究计划项目（2014JZ019）.

Optimization of Dynamic Route Choice Based on Ant Colony Algorithm

AN Yi-sheng，YUAN Shao-xin，ZHAO Xiang-mo，YUE Yun

School of Information Engineering, Chang’an University, Xi’an 710064, China

Received:2013-08-27 Revised:2014-03-01 Online:2014-06-25 Published:2014-07-10

摘要/Abstract

摘要：

为了确保城市路网交通流平稳运行和各路段交通流量合理分配，提出了一种基于伪随机状态转移规则的动态路径选择优化方法.该方法首先计算路段上流量和路阻，利用伪随机状态转移规则和路径、路段信息素更新规则，模拟了出行者在路网节点的择路行为，实现了路径选择过程中静态先验知识、动态交通状态及路径选择随机性的综合.算例结果表明，该方法能够体现不同 OD 需求下路径选择的叠加效果和时延效果，相对于平衡分配法可获得更好的路网交通均衡性，对于时变路况环境下的路径诱导系统也具有一定的应用价值.

关键词: 智能交通, 动态路径选择, 蚁群算法, 交通网络, 转移概率

Abstract:

To ensure the stable operation of urban traffic flow and the rational traffic flow assignment for each road section, this study develops a pseudo-random state transition rules based on dynamic route choice optimization method. The traffic flow and impedance on each road section are calculated, and then the indi- vidual traveler’s route choice behaviors on network nodes are simulated by applying the pseudo- random state transition rules, route and section pheromone update rules. It implements the synthesizing of static prior knowledge, dynamic traffic state and the randomness of route choice. Test example shows that the method is capable of reflecting the overlay and delay effect of route choice under different OD demands. In addition, this method can obtain better network equilibrium compared with the equilibrium assignment method, which will also benefit for achieving the route guidance system with time-varying traffic conditions.

Key words: intelligent transportation, dynamic route choice, ant colony algorithm, traffic network, transi- tion probability

中图分类号:

U491.265

安毅生，袁绍欣，赵祥模，岳云. 基于蚁群算法的动态路径选择优化方法[J]. 交通运输系统工程与信息, 2014, 14(3): 97-103.

AN Yi-sheng，YUAN Shao-xin，ZHAO Xiang-mo，YUE Yun. Optimization of Dynamic Route Choice Based on Ant Colony Algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(3): 97-103.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract18788.shtml

http://www.tseit.org.cn/CN/Y2014/V14/I3/97

参考文献

[1] 高自友, 任华玲. 城市动态交通流分配模型与算法 [M]. 北京: 人民交通出版社, 2005. [GAO Z Y, REN H L. Dynamic traffic assignment problems in urban transportation networks: models and methods[M]. Beijing: China Communications Press, 2005.]

[2] 许良, 高自友. 不确定条件下用户路径选择行为研究述评[J]. 燕山大学学报(哲学社会科学版), 2007, 8(1): 139- 144. [XU L, GAO Z Y. Review on user route choice behavior model under uncertainty[J]. Journal of Yanshan University (Philosophy and Social Science Edition). 2007, 8(1):139-144.]
[3] 王谱, 孙会君. 基于自适应规则的择路演化研究[J]. 交通运输系统工程与信息, 2010, 10(4):86-92. [WANG P, SUN H J. Route choice evolving under adaptive rule [J]. Journal of Transportation Systems Engineering and Information Technology, 2010, 10(4): 86-92.]
[4] 肖海燕. 基于马尔科夫的动态交通流演化模型及应用[J]. 武汉大学学报工学版, 2012, 45(2):255- 258.[XIAO H Y. Modeling of dynamic traffic flow evolution based on Markov chain and its application[J]. Engineering Journal of Wuhan University, 2012, 45(2): 255-258.]
[5] 雷东升，诸彤宇.  一种基于实时路况信息的动态路径规划算法[J]. 计算机科学，2008，35(4A)：28-30. [LEI D S, ZHU T Y. A dynamic route planning algorithm based on real-time traffic information[J]. Computer Science, 2008, 35(4A): 28-30.]
[6] 袁绍欣,   赵祥模,   安毅生，等.   交通错峰出行策略仿真模型[J]. 长安大学学报(自然科学版), 2010, 30(5):75-78. [YUAN S X, ZHAO X M, AN Y S, et al. Simulation model of travel strategies for staggered shifts[J]. Journal of Chang’an University (Natural Science Edition), 2010, 30(5): 75-78.]
[7] 何胜学, 范炳全. 多用户动态交通流分配模型及算法研究 [J]. 上海理工大学学报, 2006, 28(5):460- 464.[HE S X, FAN B Q. Multi- user dynamic traffic assignment model and relevant algorithm[J]. Journal of University of Shanghai for Science and Technology, 2006, 28 (5): 460-464.]
[8] Dorigo M, Stutzle T. Ant colony optimization[M]. Cambridge (MA): The MIT Press, 2004.
[9] Mussone L, Matteucci M. An application of Ant Colony Systems for DUE and SUE assignment in congested transportation networks[C]//Proceedings of the 11th World Conference on Transport Research, Berkeley (CA), USA, 2007.
[10] Matteucci M, Mussone L. An ant colony system for transportation user equilibrium analysis in congested networks[J]. Swarm Intelligence, 2013, 7(4):255-277.
[11] D’Acierno L, Gallo M, Montella B. Ant colony optimisation approaches for the transportation assignment problem[J]. WIT Transactions on the Built Environment 111, 2010, 37-48.
[12] Gallo M, D’Acierno L, Montella B. An ant colony optimisation algorithm for solving the asymmetric traffic assignment problem[J]. European Journal of Operational Research, 2012, 217(2): 459-469.
[13]     夏媛媛，马立云，王晓原. 基于混沌蚁群算法的动态用户最优配流方法[J]. 山东理工大学学报(自然科学版), 2011, 25(3):17- 21. [XIA Y Y, MA L Y, WANG X Y. Dynamic users optimum traffic assignment method based on chaos ant colony algorithm[J]. Journal of Shan dong University of Technology (Natural Science Edi? tion), 2011, 25(3):17-21.]
[14]     闻育，吴铁军. 基于蚁群算法的城域交通控制实时滚动优化 [J]. 控制与决策，2004，19(9)：1057- 1063. [WEN Y, WU T J. Real-time rolling horizon optimization of urban traffic control based on ant algorithm[J]. Control and Decision, 2004,19(9):1057-1063.]
[15]       刘经宇，方彦军. 蚁群算法在城市交通路径选择中的应用 [J]. 西南交通大学学报，2009，44(6)：912- 917. [LIU J Y, FANG Y J. Urban vehicle routing based on ant colony algorithm[J]. Journal of southwest jiaotong university. 2009, 44(6):912-917.]
[16]     谷远利，李善梅，邵春福. 基于蚁群算法的交通控制与诱导协同研究 [J]. 系统仿真学报，2008，20(10)： 2754-2761. [GU Y L, LI S M, SHAO C F. Study on cooperation of traffic control and route guidance based on ant algorithm[J]. Journal of System Simulation, 2008, 20 (10):2754-2761.]