|Table of Contents|

An ant colony optimization algorithm of stochastic user equilibrium traffic assignment problem(PDF)

《交通运输工程学报》[ISSN:1671-1637/CN:61-1369/U]

Issue:
2018年03期
Page:
189-198
Research Field:
交通运输规划与管理
Publishing date:

Info

Title:
An ant colony optimization algorithm of stochastic user equilibrium traffic assignment problem
Author(s):
YANG Lin-jian1; 2;  ZHAO Xiang-mo1;  HE Bing-hua1;  WEI Qiu-yue1;  AN Yi-sheng1
1. School of Information Engineering, Chang’an University, Xi’an 710064, Shaanxi, China; 2. Road Transport Administration of Yunnan Province, Kunming 650031, Yunnan, China
Keywords:
intelligent transportation;  dynamic traffic assignment;  ant colony optimization;  stochastic user equilibrium problem;  logit model;  sensitivity analysis
PACS:
U491.123
DOI:
-
Abstract:
The relationship between the indicators of the traveler’s familiarity with the road network and the equilibrium of traffic flow assignment was studied. An ant colony optimization algorithm with the pheromone update strategy of exponential form was proposed to solve the stochastic user equilibrium problem. In addition, the dynamic cycle process of traffic assignment was established from the logit model loading to the iterative calculations of traffic demand, path flow, road flow, road impedance and path impedance. The road flows and road impedances of Nguyen-Dupuis road network model were calculated and compared with the result computed by the successive average algorithm. The sensitivities of ant colony optimization algorithm and successive average algorithm were analyzed by adjusting the factors of the traveler’s familiarity with the road network. Analysis result shows that the road flow distributions computed by the successive average algorithm and ant colony optimization algorithm are 20-280 and 40-260 pcu, respectively, and the flow distribution interval computed by the latter decreases by 15.4%, while the maximum road flow decreases by 7.1%. Therefore, the road flow calculated by the ant colony optimization algorithm is more balanced. When using the ant colony optimization algorithm, the standard deviation of each road section flow in Nguyen-Dupuis road network model reduces from 65 to 48 pcu, 88% of the alternative paths’ impedances distribute in 61-64, and 84% of the path impedances are lower than the result computed by the successive average algorithm. Therefore, the ant colony optimization algorithm can reduce the user travel time. When the familiarity of the road network is 0.01, 0.1, 1, 2, 7, and 11, respectively, the standard deviation of each road section calculated by the successive average algorithm is 75, 65, 50, 47, 45, and 45 pcu, respectively, and the standard deviation calculated by the ant colony optimization algorithm is 48, 48, 48, 47, 43, and 43 pcu, respectively. With the increase of road network familiarity, the range of the flow assigned to each road gradually decreases, and the standard deviation tends to be stable. The pheromone update strategy has greater influence on the probability of traveler’s path selection, and the probability selecting the path with smaller impedance is higher. Therefore, the ant colony optimization algorithm gradually outperforms the successive average algorithm for the flow distribution of each road section. 2 tabs, 10 figs, 26 refs.

References:


[1] FRIESZ T L, BERNSTEIN D, SUO Z, et al. Dynamic network user equilibrium with state-dependent time lags[J]. Networks and Spatial Economics, 2001, 1: 319-347.
[2] HUANG Hai-jun, LAM W H K. Modeling and solving the dynamic user equilibrium route and departure time choice problem in network with queues[J]. Transportation Research Part B: Methodological, 2002, 36(3): 253-273.
[3] CHOW A H F. Dynamic system optimal traffic assignment—a state-dependent control theoretic approach[J]. Transportmetrica, 2009, 5(2): 85-106.
[4] ZHONG R X, SUMALEE A, FRIESZ T L, et al. Dynamic user equilibrium with side constraints for a traffic network: theoretical development and numerical solution algorithm[J]. Transportation Research Part B: Methodological, 2011, 45(7): 1035-1061.
[5] DAGANZO C F, SHEFFI Y. On stochastic models of traffic assignment[J]. Transportation Science, 1977, 11(3): 253-274.
[6] LIU Hao-xiang, WANG D Z W. Global optimization method for network design problem with stochastic user equilibrium[J]. Transportation Research Part B: Methodological, 2015, 72: 20-39.
[7] CHEN A, RYU S, XU Xiang-dong, et al. Computation and application of the paired combinatorial logit stochastic user equilibrium problem[J]. Computers and Operations Research, 2014, 43: 68-77.
[8] RASMUSSEN T K, WATLING D P, PRATO C G, et al. Stochastic user equilibrium with equilibrated choice sets: Part Ⅱ—solving the restricted SUE for the logit family[J]. Transportation Research Part B: Methodological, 2015, 77: 146-165.
[9] MAHER M. Stochastic user equilibrium assignment with elastic demand[J]. Traffic Engineering and Control, 2001, 42(5): 163-167.
[10] KUANG A W, HUANG Z X. Stochastic user equilibrium traffic assignment with multiple user classes and elastic demand[C]∥IEEE. 2010 International Conference on Intelligent Computation Technology and Automation. New York: IEEE, 2010: 394-397.
[11] MENG Qiang, LAM W H K, YANG Liu. General stochastic user equilibrium traffic assignment problem with link capacity constraints[J]. Journal of Advanced Transportation, 2008, 42(4): 429-465.
[12] KUANG A W, HUANG Z X. A research on mixed stochastic user equilibrium model based on generalized travel disutility under ATIS[C]∥IEEE. 2010 International Conference on Intelligent Computation Technology and Automation. New York: IEEE, 2010: 324-327.
[13] MENG Qiang, LIU Zhi-yuan. Mathematical models and computational algorithms for probit-based asymmetric stochastic user equilibrium problem with elastic demand[J]. Transportmetrica, 2012, 8(4): 261-290.
[14] 周 晶.随机交通均衡配流模型及其等价的变分不等式问题[J].系统科学与数学,2003,23(1):120-127. ZHOU Jing. Stochastic user equilibrium and its variational inequality problem[J]. Journal of Systems Science and Mathematical Sciences, 2003, 23(1): 120-127.(in Chinese)
[15] 况爱武,王正武,李炳林.多用户类弹性需求随机用户均衡模型及其求解[J].长沙理工大学学报:自然科学版,2007,4(2):16-20. KUANG Ai-wu, WANG Zheng-wu, LI Bing-lin. Model and its solution for stochastic user equilibrium traffic assignment with multiple user classes and variable demand[J]. Journal of Changsha University of Science and Technology: Natural Science, 2007, 4(2): 16-20.(in Chinese)
[16] 陈 群,王 艳,陈维亚,等.一种新的概率型随机用户均衡问题表示方法及算法[J].中国公路学报,2014,27(8):82-88. CHEN Qun, WANG Yan, CHEN Wei-ya, et al. New expression and algorithm for probit-based stochastic user equilibrium[J]. China Journal of Highway and Transport, 2014, 27(8): 82-88.(in Chinese)
[17] 周博见,李旭宏,何 杰.求解基于路径的Logit型随机用户均衡模型的新算法[J].中国公路学报,2014,27(3):100-107. ZHOU Bo-jian, LI Xu-hong, HE Jie. A new algorithm for path-based logit stochastic user equilibrium model[J]. China Journal of Highway and Transport, 2014, 27(3): 100-107.(in Chinese)
[18] 徐 兵,朱道立.多用户多准则固定需求随机交通均衡变分模型[J].公路交通科技,2007,24(4):129-133. XU Bing, ZHU Dao-li. A multiclass and multicriteria stochastic traffic network equilibrium variational inequality model with fixed demand[J]. Journal of Highway and Transportation Research and Development, 2007, 24(4): 129-133.(in Chinese)
[19] DORIGO M, BIRATTARI M, STÜTZLE T. Ant colony optimization[J]. IEEE Computational Intelligence Magazine, 2006, 1(4): 28-39.
[20] LIAO Tian-jun, SOCHA K, MONTES DE OCA M A, et al. Ant colony optimization for mixed-variable optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 503-518.
[21] MATTEUCCI M, MUSSONE L. Ant colony optimization technique for equilibrium assignment in congested transportation networks[C]∥Association for Computing Machinery. 8th Annual Genetic and Evolutionary Computation Conference. New York: Association for Computing Machinery, 2006: 87-88.
[22] D’ACIERNO L, MONTELLA B, DE LUCIA F, et al. A stochastic traffic assignment algorithm based on ant colony optimization[J]. Lecture Notes in Computer Science, 2006, 4150: 25-36.
[23] MATTEUCCI M, MUSSONE L. An ant colony system for transportation user equilibrium analysis in congested networks[J]. Swarm Intelligence, 2013, 7(4): 255-277.
[24] 徐勋倩,黄 卫.蚂蚁算法处理动态交通网络用户均衡配流问题[J].公路交通科技,2005,22(1):111-114. XU Xun-qian, HUANG Wei. Ant algorithm for users equilibrium assignment model of dynamic traffic network[J]. Journal of Highway and Transportation Research and Development, 2005, 22(1): 111-114.(in Chinese)
[25] 安毅生,袁绍欣,赵祥模,等.基于蚁群算法的动态路径选择优化方法[J].交通运输系统工程与信息,2014,14(3):97-103. AN Yi-sheng, YUAN Shao-xin, ZHAO Xiang-mo, et al. Optimization of dynamic route choice based on ant colony algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(3): 97-103.(in Chinese)
[26] SHEFFI Y, POWELL W B. An algorithm for the equilibrium assignment problem with random link times[J]. Networks, 1982, 12(2): 191-207.

Memo

Memo:
-
Last Update: 2018-07-14