IDEAS home Printed from https://ideas.repec.org/a/eee/apmaco/v371y2020ics0096300319308872.html
   My bibliography  Save this article

A reinforcement learning scheme for the equilibrium of the in-vehicle route choice problem based on congestion game

Author

Listed:
  • Zhou, Bo
  • Song, Qiankun
  • Zhao, Zhenjiang
  • Liu, Tangzhi

Abstract

In this paper, the Bush–Mosteller (B-M) reinforcement learning (RL) scheme is introduced to model the route choice behaviors of the travelers in traffic networks, who aim to seek the optimal travel routes that minimize their individual travel time. The optimal route choice strategy is presented by the Nash equilibrium of the congestion game. By constructing a novel potential function, the congestion game is transformed into the traffic assignment problem (TAP). Then, a distributed algorithm based on B-M RL scheme is devised to solve the TAP. Under some mild conditions, the B-M RL solution method is proven to converge almost surely to the optimal solution of the TAP. A numerical experiment is conducted based on the Nguyen–Dupuis network, the experimental results not only demonstrate the effectiveness of the theoretical analysis, but also show that the B-M RL-based solution method outperforms several existing solution methods.

Suggested Citation

  • Zhou, Bo & Song, Qiankun & Zhao, Zhenjiang & Liu, Tangzhi, 2020. "A reinforcement learning scheme for the equilibrium of the in-vehicle route choice problem based on congestion game," Applied Mathematics and Computation, Elsevier, vol. 371(C).
    • Handle: RePEc:eee:apmaco:v:371:y:2020:i:c:s0096300319308872
    DOI: 10.1016/j.amc.2019.124895
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0096300319308872
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.amc.2019.124895?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Fisk, Caroline, 1980. "Some developments in equilibrium traffic assignment," Transportation Research Part B: Methodological, Elsevier, vol. 14(3), pages 243-255, September.
    2. Li, Zhibin & Jia, Danyang & Guo, Hao & Geng, Yini & Shen, Chen & Wang, Zhen & Li, Xuelong, 2019. "The effect of multigame on cooperation in spatial network," Applied Mathematics and Computation, Elsevier, vol. 351(C), pages 162-167.
    3. Xu, Hongli & Lou, Yingyan & Yin, Yafeng & Zhou, Jing, 2011. "A prospect-based user equilibrium model with endogenous reference points and its application in congestion pricing," Transportation Research Part B: Methodological, Elsevier, vol. 45(2), pages 311-328, February.
    4. Tanimoto, Jun & Nakamura, Kousuke, 2016. "Social dilemma structure hidden behind traffic flow with route selection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 459(C), pages 92-99.
    5. Du, Lili & Han, Lanshan & Li, Xiang-Yang, 2014. "Distributed coordinated in-vehicle online routing using mixed-strategy congestion game," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 1-17.
    6. Sang Nguyen & Clermont Dupuis, 1984. "An Efficient Method for Computing Traffic Equilibria in Networks with Asymmetric Transportation Costs," Transportation Science, INFORMS, vol. 18(2), pages 185-202, May.
    7. Kang, Zengxin & Zhang, Lei & Li, Kun, 2019. "An improved social force model for pedestrian dynamics in shipwrecks," Applied Mathematics and Computation, Elsevier, vol. 348(C), pages 355-362.
    8. Agryzkov, Taras & Tortosa, Leandro & Vicent, Jose F., 2019. "A variant of the current flow betweenness centrality and its application in urban networks," Applied Mathematics and Computation, Elsevier, vol. 347(C), pages 600-615.
    9. Cheng, Yuan & Zheng, Xiaoping, 2018. "Emergence of cooperation during an emergency evacuation," Applied Mathematics and Computation, Elsevier, vol. 320(C), pages 485-494.
    10. Angelelli, E. & Arsik, I. & Morandi, V. & Savelsbergh, M. & Speranza, M.G., 2016. "Proactive route guidance to avoid congestion," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 1-21.
    11. Xu, Hedong & Fan, Suohai & Tian, Cunzhi & Xiao, Xinrong, 2019. "Evolutionary investor sharing game on networks," Applied Mathematics and Computation, Elsevier, vol. 340(C), pages 138-145.
    12. Papageorgiou, Markos, 1990. "Dynamic modeling, assignment, and route guidance in traffic networks," Transportation Research Part B: Methodological, Elsevier, vol. 24(6), pages 471-495, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Wang, Yi & Qiu, Dawei & Strbac, Goran, 2022. "Multi-agent deep reinforcement learning for resilience-driven routing and scheduling of mobile energy storage systems," Applied Energy, Elsevier, vol. 310(C).
    2. Sun, Wenjun & Zhu, Changfeng & Li, Hui, 2022. "Evolutionary game of emergency logistics path selection under bounded rationality," Socio-Economic Planning Sciences, Elsevier, vol. 82(PB).
    3. Ning, Yuqiang & Du, Lili, 2023. "Robust and resilient equilibrium routing mechanism for traffic congestion mitigation built upon correlated equilibrium and distributed optimization," Transportation Research Part B: Methodological, Elsevier, vol. 168(C), pages 170-205.
    4. Tan, Lihua & Li, Chuandong & Huang, Junjian & Huang, Tingwen, 2021. "Output feedback leader-following consensus for nonlinear stochastic multiagent systems: The event-triggered method," Applied Mathematics and Computation, Elsevier, vol. 395(C).
    5. Le Zhang & Lijing Lyu & Shanshui Zheng & Li Ding & Lang Xu, 2022. "A Q-Learning-Based Approximate Solving Algorithm for Vehicular Route Game," Sustainability, MDPI, vol. 14(19), pages 1-14, September.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Claudia Castaldi & Paolo Delle Site & Francesco Filippi, 2019. "Stochastic user equilibrium in the presence of state dependence," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 535-559, December.
    2. Chen, Anthony & Zhou, Zhong & Lam, William H.K., 2011. "Modeling stochastic perception error in the mean-excess traffic equilibrium model," Transportation Research Part B: Methodological, Elsevier, vol. 45(10), pages 1619-1640.
    3. Ji, Xiangfeng & Chu, Yanyu, 2020. "A target-oriented bi-attribute user equilibrium model with travelers’ perception errors on the tolled traffic network," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 144(C).
    4. Li, Tongfei & Xu, Min & Sun, Huijun & Xiong, Jie & Dou, Xueping, 2023. "Stochastic ridesharing equilibrium problem with compensation optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 170(C).
    5. Li, Xue-yan & Li, Xue-mei & Yang, Lingrun & Li, Jing, 2018. "Dynamic route and departure time choice model based on self-adaptive reference point and reinforcement learning," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 502(C), pages 77-92.
    6. Alireza Ermagun & David M Levinson, 2019. "Development and application of the network weight matrix to predict traffic flow for congested and uncongested conditions," Environment and Planning B, , vol. 46(9), pages 1684-1705, November.
    7. Prakash, A. Arun & Seshadri, Ravi & Srinivasan, Karthik K., 2018. "A consistent reliability-based user-equilibrium problem with risk-averse users and endogenous travel time correlations: Formulation and solution algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 114(C), pages 171-198.
    8. Hamid Reza Eftekhari & Mehdi Ghatee, 2017. "The lower bound for dynamic parking prices to decrease congestion through CBD," Operational Research, Springer, vol. 17(3), pages 761-787, October.
    9. Zhaoqi Zang & Xiangdong Xu & Kai Qu & Ruiya Chen & Anthony Chen, 2022. "Travel time reliability in transportation networks: A review of methodological developments," Papers 2206.12696, arXiv.org, revised Jul 2022.
    10. Angelelli, E. & Morandi, V. & Savelsbergh, M. & Speranza, M.G., 2021. "System optimal routing of traffic flows with user constraints using linear programming," European Journal of Operational Research, Elsevier, vol. 293(3), pages 863-879.
    11. Huijun Sun & Si Zhang & Linghui Han & Xiaomei Zhao & Lu Lou, 2020. "Day-to-Day Evolution Model Based on Dynamic Reference Point with Heterogeneous Travelers," Networks and Spatial Economics, Springer, vol. 20(4), pages 935-961, December.
    12. Almotahari, Amirmasoud & Yazici, Anil, 2021. "A computationally efficient metric for identification of critical links in large transportation networks," Reliability Engineering and System Safety, Elsevier, vol. 209(C).
    13. Clark, Stephen D. & Watling, David P., 2006. "Applications of sensitivity analysis for probit stochastic network equilibrium," European Journal of Operational Research, Elsevier, vol. 175(2), pages 894-911, December.
    14. Li, Xue-yan & Li, Xue-mei & Li, Xue-wei & Qiu, He-ting, 2017. "Multi-agent fare optimization model of two modes problem and its analysis based on edge of chaos," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 469(C), pages 405-419.
    15. Eikenbroek, Oskar A.L. & Still, Georg J. & van Berkum, Eric C., 2022. "Improving the performance of a traffic system by fair rerouting of travelers," European Journal of Operational Research, Elsevier, vol. 299(1), pages 195-207.
    16. Li, Tongfei & Sun, Huijun & Wu, Jianjun & Ge, Ying-en, 2017. "Optimal toll of new highway in the equilibrium framework of heterogeneous households' residential location choice," Transportation Research Part A: Policy and Practice, Elsevier, vol. 105(C), pages 123-137.
    17. Du, Lili & Han, Lanshan & Li, Xiang-Yang, 2014. "Distributed coordinated in-vehicle online routing using mixed-strategy congestion game," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 1-17.
    18. Xinming Zang & Zhenqi Guo & Jingai Ma & Yongguang Zhong & Xiangfeng Ji, 2021. "Target-Oriented User Equilibrium Considering Travel Time, Late Arrival Penalty, and Travel Cost on the Stochastic Tolled Traffic Network," Sustainability, MDPI, vol. 13(17), pages 1-22, September.
    19. Du, Lili & Han, Lanshan & Chen, Shuwei, 2015. "Coordinated online in-vehicle routing balancing user optimality and system optimality through information perturbation," Transportation Research Part B: Methodological, Elsevier, vol. 79(C), pages 121-133.
    20. Gentile, Guido & Meschini, Lorenzo & Papola, Natale, 2007. "Spillback congestion in dynamic traffic assignment: A macroscopic flow model with time-varying bottlenecks," Transportation Research Part B: Methodological, Elsevier, vol. 41(10), pages 1114-1138, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:apmaco:v:371:y:2020:i:c:s0096300319308872. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/applied-mathematics-and-computation .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.