Volume 18 Issue 3
. 
Turn off MathJax
Article Contents
Article Navigation >  Journal of Traffic and Transportation Engineering  > 2018  >  18(3): 189-198
YANG Lin-jian, ZHAO Xiang-mo, HE Bing-hua, WEI Qiu-yue, AN Yi-sheng. An ant colony optimization algorithm of stochastic user equilibrium traffic assignment problem[J]. Journal of Traffic and Transportation Engineering, 2018, 18(3): 189-198. doi: 10.19818/j.cnki.1671-1637.2018.03.019
Citation: YANG Lin-jian, ZHAO Xiang-mo, HE Bing-hua, WEI Qiu-yue, AN Yi-sheng. An ant colony optimization algorithm of stochastic user equilibrium traffic assignment problem[J]. Journal of Traffic and Transportation Engineering, 2018, 18(3): 189-198. doi: 10.19818/j.cnki.1671-1637.2018.03.019
shu

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

doi: 10.19818/j.cnki.1671-1637.2018.03.019
  • 1.

    School of Information Engineering, Chang'an University, Xi'an 710064, Shaanxi, China

  • 2.

    Road Transport Administration of Yunnan Province, Kunming 650031, Yunnan, China

More Information
  • Author Bio:

    YANG Lin-jian(1980-), male, doctoral student, yang2612351@163.com

    ZHAO Xiang-mo(1966-), male, professor, PhD, xmzhao@chd.edu.cn

  • Received Date: 2018-02-15
  • Publish Date: 2018-06-25
    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 familiaritywith 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.

     

    • FullText(HTML)
  • loading
    • References(26)
  • [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. doi: 10.1023/A:1012896228490
    [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. doi: 10.1016/S0191-2615(00)00049-7
    [3]
    CHOW A H F. Dynamic system optimal traffic assignment—a state-dependent control theoretic approach[J]. Transportmetrica, 2009, 5 (2): 85-106. doi: 10.1080/18128600902717483
    [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. doi: 10.1016/j.trb.2011.05.004
    [5]
    DAGANZO C F, SHEFFI Y. On stochastic models of traffic assignment[J]. Transportation Science, 1977, 11 (3): 253-274. doi: 10.1287/trsc.11.3.253
    [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. doi: 10.1016/j.trb.2014.10.009
    [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. doi: 10.1016/j.cor.2013.08.022
    [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. doi: 10.1016/j.trb.2015.03.009
    [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. 2010International 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. doi: 10.1002/atr.5670420403
    [12]
    KUANG A W, HUANG Z X. A research on mixed stochastic user equilibrium model based on generalized travel disutility under ATIS[C]∥IEEE. 2010International 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. doi: 10.1080/18128601003736026
    [14]
    周晶. 随机交通均衡配流模型及其等价的变分不等式问题[J]. 系统科学与数学, 2003, 23 (1): 120-127. doi: 10.3969/j.issn.1000-0577.2003.01.017

    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). doi: 10.3969/j.issn.1000-0577.2003.01.017
    [15]
    况爱武, 王正武, 李炳林. 多用户类弹性需求随机用户均衡模型及其求解[J]. 长沙理工大学学报: 自然科学版, 2007, 4 (2): 16-20. https://www.cnki.com.cn/Article/CJFDTOTAL-HNQG200702002.htm

    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). https://www.cnki.com.cn/Article/CJFDTOTAL-HNQG200702002.htm
    [16]
    陈群, 王艳, 陈维亚, 等. 一种新的概率型随机用户均衡问题表示方法及算法[J]. 中国公路学报, 2014, 27 (8): 82-88. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL201408015.htm

    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). https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL201408015.htm
    [17]
    周博见, 李旭宏, 何杰. 求解基于路径的Logit型随机用户均衡模型的新算法[J]. 中国公路学报, 2014, 27 (3): 100-107. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL201403018.htm

    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). https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL201403018.htm
    [18]
    徐兵, 朱道立. 多用户多准则固定需求随机交通均衡变分模型[J]. 公路交通科技, 2007, 24 (4): 129-133. doi: 10.3969/j.issn.1002-0268.2007.04.030

    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). doi: 10.3969/j.issn.1002-0268.2007.04.030
    [19]
    DORIGO M, BIRATTARI M, STÜTZLE T. Ant colony optimization[J]. IEEE Computational Intelligence Magazine, 2006, 1 (4): 28-39. doi: 10.1109/MCI.2006.329691
    [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. https://www.cnki.com.cn/Article/CJFDTOTAL-GLJK200501029.htm

    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). https://www.cnki.com.cn/Article/CJFDTOTAL-GLJK200501029.htm
    [25]
    安毅生, 袁绍欣, 赵祥模, 等. 基于蚁群算法的动态路径选择优化方法[J]. 交通运输系统工程与信息, 2014, 14 (3): 97-103. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201403015.htm

    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). https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201403015.htm
    [26]
    SHEFFI Y, POWELL W B. An algorithm for the equilibrium assignment problem with random link times[J]. Networks, 1982, 12 (2): 191-207.
    • Relative Articles
    • Supplements(0)
    • Cited By
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索
    Get Citation
    PDF
    XML

    Article Metrics

    Article views (843) PDF downloads(1252) Cited by()
    Proportional views
    Related

    Copyright《Journal of Traffic and Transportation Engineering》编辑部陕ICP备05001904号-1

    Address ：Editorial Department of Journal of Traffic and Transportation Engineering, Chang 'an University, Middle Section of South Second Ring Road, Xi 'an, Shaanxi（710064） Tel：029-82334388 Email：jygc@chd.edu.cn

    All visit:Today's visit:

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return