Dynamic Real-Time Algorithm for Multi-Intersection Route Selection in Urban Traffic Networks
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61572369, 61471274, 70901060); Hubei Province Natural Science Foundation (2011CDB461, 2014CFB193, 2015CFB423); State Key Laboratory of Software Engineering Open Foundation (SKLSE 2010-08-15); Youth Plan Found of Wuhan City (2011-50431101); Key Science and Technology Project of Wuhan City (20150101010 10023); Jiangxi Province Youth Science Foundation (20151BAB217017)

  • Article
  • | |
  • Metrics
  • |
  • Reference [44]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    In order to alleviate traffic congestion for vehicles in urban traffic networks, many researchers have studied how to utilize the traffic resources such as roads effectively to supply effective route selection strategies for vehicles. Most of the current researches mainly focus on optimizing the signal cycle of traffic lights, supplying the optimized route selection for individual vehicles, and dispersing vehicles on the alternative routes based on their historical driving data or through the traffic game between the information center and the vehicles. However, the above methods have not considered the personalized traffic demands of each vehicle, the route selection conflicts between vehicles, or even the dynamic and uncertain traffic conditions in urban road networks. To solve these problems, this paper proposes a dynamic and real-time route selection model in urban traffic networks (DR2SM), which incorporates the preference for the alternative routes and the real-time traffic conditions. Through mutual information exchange, each vehicle uses a self-adaptive learning algorithm (SALA) to play the congestion game with each other to reach Nash equilibrium.

    Reference
    [1] Schrank D,Eisele B,Lomax T.2012 Urban mobility report.Texas Transportation Institute,Texas A&M University,2012.
    [2] Sims AG,Dobinson KW.The Sydney coordinated adaptive traffic (SCAT) system philosophy and benefits.IEEE Trans.on Vehicular Technology,1980,29(2):130-137.[doi:10.1109/T-VT.1980.23833]
    [3] Hunt PB,Robertson DI,Bretherton RD,Royle MC.The SCOOT on-line traffic signal optimisation technique.Traffic Engineering&Control,1982,23(4):190-192.
    [4] Kala R,Shukla A,Tiwari R.Fusion of probabilistic A* algorithm and fuzzy inference system for robotic path planning.Artificial Intelligence Review,2010,33(4):307-327.[doi:10.1007/s10462-010-9157-y]
    [5] Arokhlo MZ,Selamat A,Hashim SZM,Selamat MH.Route guidance system using multi-agent reinforcement learning.In:Proc.of the 7th Int'l Conf.on Information Technology in Asia.2011.1-5.[doi:10.1109/CITA.2011.5999388]
    [6] Yu S,Shingo M,Kanta MM,Kaoru S,Kotaro H.An application of Q-value-based dynamic programming with Boltzmann distribution to real-world road networks.IEEE Trans.on Electrical&Electronic Engineering,2013,8(2):139-145.[doi:10.1002/tee.21833]
    [7] Li T,Zhang J,Wang S,Lv Z.Research on route planning based on quantum-behaved particle swam optimization algorithm.In:Proc.of 2014 IEEE Chinese Guidance,Navigation and Control Conf.2014.335-339.[doi:10.1109/CGNCC.2014.7007253]
    [8] Huang SC,Jiau MK,Lin CH.A genetic-algorithm-based approach to solve carpool service problems in cloud computing.IEEE Trans.on Intelligent Transportation Systems,2015,16(1):352-364.[doi:10.1109/TITS.2014.2334597]
    [9] Negulescu SC,Kifor CV,Oprean C.Ant colony solving multiple constraints problem:Vehicle route allocation.Int'l Journal of Computers Communications&Control,2008,Ⅲ (4):366-373.[doi:10.15837/ijccc.2008.4.2404]
    [10] Han Z,Wu C,Ma B,Li J,Xu K.Restricted searching area route guidance based on neural network and EA.In:Proc.of the IEEE Int'l Conf.on Automation and Logistics.2007.2477-2480.[doi:10.1109/ICAL.2007.4338994]
    [11] Tomtom.2016.https://mydrive.tomtom.com/en_gb/
    [12] Google maps.2014.https://www.google.com/mobile/maps/
    [13] Yamada K,Ma J,Fukuda D.Simulation analysis of the market diffusion effects of risk-averse route guidance on network traffic.Procedia Computer Science,2013,19:874-881.[doi:10.1016/j.procs.2013.06.117]
    [14] Wang L,Jiang P,Zhong J,Li L,Zhang J,Wei X,Li E.Intelligent traffic guidance system based on dynamic toll collection policy.In:Proc.of the 4th Int'l IEEE Conf.on Communication Systems and Network Technologies.2014.1172-1176.[doi:10.1109/CSNT.2014.238]
    [15] Groot N,De Schutter BD,Hellendoorn H.Toward system-optimal routing in traffic networks:A reverse stackelberg game approach.IEEE Trans.on Intelligent Transportation Systems,2015,16(1):29-40.[doi:10.1109/TITS.2014.2322312]
    [16] Desai P,Loke SW,Desai A,Singh J.CARAVAN:Congestion avoidance and route allocation using virtual agent negotiation.IEEE Trans.on Intelligent Transportation Systems,2013,14(3):1197-1207.[doi:10.1109/TITS.2013.2256420]
    [17] Li LJ,Liu HF,Yang ZY,Ge LJ,Huang XY.Broadcasting methods in vehicular ad hoc networks.Ruan Jian Xue Bao/Journal of Software,2010,21(7):1620-1634(in Chinese with English abstract).http://www.jos.org.cn/1000-9825/3845.htm[doi:10.3724/SP.J.1001.2010.03845]
    [18] Hu WB,Yan LP,Wang H,Du B.On exploring a virtual agent negotiation inspired approach for route guidance in urban traffic networks.In:Proc.of Int'l Conf.on Algorithms and Architectures for Parallel Processing.Springer Int'l Publishing,2015.3-16.[doi:10.1007/978-3-319-27137-8_1]
    [19] Li MC,Xu L,Sun WF,Lu K,Guo C.Grid resource allocation model based on incomplete information game.Ruan Jian Xue Bao/Journal of Software,2012,23(2):428-438(in Chinese with English abstract).http://www.jos.org.cn/1000-9825/3972.htm[doi:10.3724/SP.J.1001.2012.03972]
    [20] Shamma JS.Learning in games.Encyclopedia of Systems&Control,2015,133(1):177-198.[doi:10.1007/978-1-4471-5058-9_34]
    [21] Hui F,Adam JP,Serge PH.Optimization of evacuation traffic management with intersection control constraints.IEEE Trans.on Intelligent Transportation Systems,2015,16(1):376-386.[doi:10.1109/TITS.2014.2336266]
    [22] Hajiahmadi M,Knoop VL,Schutter BD,Hellendoorn H.Optimal dynamic route guidance:A model predictive approach using the macroscopic fundamental diagram.In:Proc.of the 16th Int'l IEEE Conf.on Intelligent Transportation Systems.2013.1022-1028.[doi:10.1109/ITSC.2013.6728366]
    [23] El-Tantawy S,Abdulhai B,Abdelgawad H.Multiagent reinforcement learning for integrated network of adaptive traffic signal controllers (MARLIN-ATSC):Methodology and large-scale application on downtown toronto.IEEE Trans.on Intelligent Transportation Systems,2013,14(3):1140-1150.[doi:10.1109/TITS.2013.2255286]
    [24] Xu Y,Zhang YL,Sun TT,Su YF.Agent-Based decentralized cooperative traffic control toward green-waved effects.Ruan Jian Xue Bao/Journal of Software,2012,23(11):2937-2945(in Chinese with English abstract).http://www.jos.org.cn/1000-9825/4307.htm[doi:10.3724/SP.J.1001.2012.04307]
    [25] Li C,Anavatti SG,Ray T.Analytical hierarchy process using fuzzy inference technique for real-time route guidance system.IEEE Trans.on Intelligent Transportation Systems,2014,15(1):84-93.[doi:10.1109/TITS.2013.2272579]
    [26] Zolfpour-Arokhlo M,Selamat A,Hashim SZM,Afkhami H.Modeling of route planning system based on Q value-based dynamic programming with multi-agent reinforcement learning algorithms.Engineering Applications of Artificial Intelligence,2014,29(3):163-177.[doi:10.1016/j.engappai.2014.01.001]
    [27] Zafar K,Baig R,Bukhari N,Halim Z.Route planning and optimization of route using simulated ant agent system.Journal of Circuits Systems&Computers,2011,20(3):457-478.[doi:10.1142/S0218126611007396]
    [28] Cao ZC,Han DF,Wang YJ.A novel dynamic path optimization method for urban traffic networks.Acta Electronica Sinica,2012,40(10):2062-2067(in Chinese with English abstract).[doi:10.3969/j.issn.0372-2112.2012.10.026]
    [29] Pan J,Popa IS,Zeitouni K,Borcea C.Proactive vehicular traffic rerouting for lower travel time.IEEE Trans.on Vehicular Technology,2013,62(8):3551-3568.[doi:10.1109/TVT.2013.2260422]
    [30] Wang S,Djahel S,Mcmanis J.A multi-agent based vehicles re-routing system for unexpected traffic congestion avoidance.In:Proc.of the 17th Int'l IEEE Conf.on Intelligent Transportation Systems.2014.2541-2548.[doi:10.1109/ITSC.2014.6958097]
    [31] Liang Z,Wakahara Y.A route guidance system with personalized rerouting for reducing traveling time of vehicles in urban areas.In:Proc.of the 17th Int'l IEEE Conf.on Intelligent Transportation Systems.2014.1541-1548.[doi:10.1109/ITSC.2014.6957652]
    [32] Zhu GQ,Tong GJ,Dai LL.Analysis of urban road congestion pricing based on game theory.In:Proc.of the 15th Annual Conf.on Management Science and Engineering.2008.1693-1697.[doi:10.1109/ICMSE.2008.4669133]
    [33] Adler JL,Satapathy G,Manikonda V,Bowles B,Blue VJ.A multi-agent approach to cooperative traffic management and route guidance.Transportation Research Part B Methodological,2005,39(4):297-318.[doi:10.1016/j.trb.2004.03.005]
    [34] Fudenberg D,Levine DK.The Theory of Learning in Games.The MIT Press,1996.177-198.
    [35] Tsitsiklis JN.Asynchronous stochastic approximation and Q-learning.Machine Learning,1994,16(3):185-202.[doi:10.1007/BF00993306]
    [36] Kushner HJ,Clark DS.Stochastic approximation methods for constrained and unconstrained systems.In:Proc.of the Applied Mathematical Sciences.1978.26.[doi:10.1007/978-1-4684-9352-8]
    [37] Leslie DS,Collins EJ.Individual Q-learning in normal form games.Siam Journal on Control&Optimization,2005,44(2):495-514.[doi:10.1137/S0363012903437976]
    [38] Benaïm M.Dynamics of stochastic approximation algorithms.In:Proc.of the Séminaire De Probabilités XXXⅢ.Heidelberg,Berlin:Springer-Verlag,1999.1-68.[doi:10.1007/BF60096509]
    [39] Jackson MO.The evolution of social and economic networks.Journal of Economic Theory,2002,106(2):265-295.[doi:10.1006/jeth.2001.2903]
    附中文参考文献:
    [17] 李丽君,刘鸿飞,杨祖元,葛利嘉,黄席樾.车用自组网信息广播.软件学报,2010,21(7):1620-1634.http://www.jos.org.cn/1000-9825/3845.htm[doi:10.3724/SP.J.1001.2010.03845]
    [19] 李明楚,许雷,孙伟峰,陆坤,郭成.基于非完全信息博弈的网格资源分配模型.软件学报,2012,23(2):428-438.http://www.jos.org.cn/1000-9825/3972.htm[doi:10.3724/SP.J.1001.2012.03972]
    [24] 徐杨,张玉林,孙婷婷,苏艳芳.基于多智能体交通绿波效应分布式协同控制算法.软件学报,2012,23(11):2937-2945.http://www.jos.org.cn/1000-9825/4307.htm[doi:10.3724/SP.J.1001.2012.04307]
    [28] 曹政才,韩丁富,王永吉.面向城市交通网络的一种新型动态路径寻优方法.电子学报,2012,10(10):2062-2067.[doi:10.3969/j.issn.0372-2112.2012.10.026]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

严丽平,胡文斌,王欢,邱振宇,杜博.城市路网多路口路径动态实时选择方法.软件学报,2016,27(9):2199-2217

Copy
Share
Article Metrics
  • Abstract:2672
  • PDF: 5213
  • HTML: 1646
  • Cited by: 0
History
  • Received:November 13,2015
  • Revised:March 30,2016
  • Online: September 02,2016
You are the first2038030Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063