IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v168y2023icp170-205.html
   My bibliography  Save this article

Robust and resilient equilibrium routing mechanism for traffic congestion mitigation built upon correlated equilibrium and distributed optimization

Author

Listed:
  • Ning, Yuqiang
  • Du, Lili

Abstract

With the rapid development of wireless communication, mobile computing, and GPS technologies, drivers’ route decisions nowadays rely more on navigation services, such as Google or Waze. However, these navigation services don't always come with improved traffic conditions. Individual drivers often make independent and selfish route decisions that are not systematically favorable and thus often result in severe congestions. This study aims to alleviate such problems by exploiting the information gaps between individuals and the central planner (CP). Specifically, we develop a correlated equilibrium routing mechanism (CeRM) for the CP, which drives a group of vehicles’ route choices to an equilibrium with a systematically optimal traffic condition while still satisfying individuals’ selfish nature. Participating drivers would only be better off by following the suggested routing guidance than navigating on their best responses to real-time traffic information. The CeRM is modeled as a nonconvex and nonlinear program involving a large-scale of users. A distributed Augmented Lagrangian algorithm (D-AL) is developed to efficiently solve the CeRM to provide online real-time navigation service, taking advantage of the on-board computation resources of individual vehicles. Considering the D-AL relies on the wireless communications between vehicles and the CP, we proved the convergence robustness of the D-AL against random communication failures and derived the convergence rate upper bound as a function of the communication failure probability. It is noticed that the convergence rate of the D-AL degrades dramatically as the communication failure probability increases, which hampers the applicability of implementing the CeRM in practice. To improve the solution algorithm's resilience in the computation performance, we further designed and proved an acceleration scheme aided D-AL (aD-AL) to expedite the convergence rate under the high likelihood of communication failures. Numerical experiments conducted on the Sioux Falls city network confirmed the D-AL's convergence properties, robustness against random communication failures, and the resilience of the aD-AL to solve the CeRM. The experiments also show that the CeRM results in better system performance (have less system cost) compared with the existing Independent Routing (IR) mechanism and user-oriented Equilibrium Routing (uoER) mechanism.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:transb:v:168:y:2023:i:c:p:170-205
    DOI: 10.1016/j.trb.2022.12.006
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261522002089
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2022.12.006?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. Herbert A. Simon, 1955. "A Behavioral Model of Rational Choice," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 69(1), pages 99-118.
    2. Small, Kenneth A & Rosen, Harvey S, 1981. "Applied Welfare Economics with Discrete Choice Models," Econometrica, Econometric Society, vol. 49(1), pages 105-130, January.
    3. Mariska van Essen & Tom Thomas & Eric van Berkum & Caspar Chorus, 2016. "From user equilibrium to system optimum: a literature review on the role of travel information, bounded rationality and non-selfish behaviour at the network and individual levels," Transport Reviews, Taylor & Francis Journals, vol. 36(4), pages 527-548, July.
    4. Dirk Van Amelsfort & Michiel Bliemer, 2005. "Valuation of uncertainty in travel time and arrival time - some findings from a choice experiment," ERSA conference papers ersa05p721, European Regional Science Association.
    5. Guo, Xiaolei & Yang, Hai, 2010. "Pareto-improving congestion pricing and revenue refunding with multiple user classes," Transportation Research Part B: Methodological, Elsevier, vol. 44(8-9), pages 972-982, September.
    6. Rey, David & Dixit, Vinayak V. & Ygnace, Jean-Luc & Waller, S. Travis, 2016. "An endogenous lottery-based incentive mechanism to promote off-peak usage in congested transit systems," Transport Policy, Elsevier, vol. 46(C), pages 46-55.
    7. Liu, Yixuan & Whinston, Andrew B., 2019. "Efficient real-time routing for autonomous vehicles through Bayes correlated equilibrium: An information design framework," Information Economics and Policy, Elsevier, vol. 47(C), pages 14-26.
    8. 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).
    9. Jin Y. Yen, 1971. "Finding the K Shortest Loopless Paths in a Network," Management Science, INFORMS, vol. 17(11), pages 712-716, July.
    10. 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.
    11. 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.
    12. Wu, Di & Yin, Yafeng & Lawphongpanich, Siriphong, 2011. "Pareto-improving congestion pricing on multimodal transportation networks," European Journal of Operational Research, Elsevier, vol. 210(3), pages 660-669, May.
    13. Small, Kenneth A., 2001. "The Value of Pricing," University of California Transportation Center, Working Papers qt0rm449sx, University of California Transportation Center.
    14. Hai Yang, 1999. "System Optimum, Stochastic User Equilibrium, and Optimal Link Tolls," Transportation Science, INFORMS, vol. 33(4), pages 354-360, November.
    Full references (including those not matched with items on IDEAS)

    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. Yang Liu & Yu (Marco) Nie, 2017. "A Credit-Based Congestion Management Scheme in General Two-Mode Networks with Multiclass Users," Networks and Spatial Economics, Springer, vol. 17(3), pages 681-711, September.
    2. Paul Koster & Erik T. Verhoef & Simon Shepherd & David Watling, 2014. "Probabilistic Choice and Congestion Pricing with Heterogeneous Travellers and Price-Sensitive Demand," Tinbergen Institute Discussion Papers 14-078/VIII, Tinbergen Institute, revised 13 Nov 2014.
    3. Koster, Paul & Verhoef, Erik & Shepherd, Simon & Watling, David, 2018. "Preference heterogeneity and congestion pricing: The two route case revisited," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 137-157.
    4. 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.
    5. Levy, Nadav & Klein, Ido & Ben-Elia, Eran, 2018. "Emergence of cooperation and a fair system optimum in road networks: A game-theoretic and agent-based modelling approach," Research in Transportation Economics, Elsevier, vol. 68(C), pages 46-55.
    6. Wu, Di & Yin, Yafeng & Lawphongpanich, Siriphong, 2011. "Pareto-improving congestion pricing on multimodal transportation networks," European Journal of Operational Research, Elsevier, vol. 210(3), pages 660-669, May.
    7. Baiocchi, Andrea, 2016. "Analysis of timer-based message dissemination protocols for inter-vehicle communications," Transportation Research Part B: Methodological, Elsevier, vol. 90(C), pages 105-134.
    8. Mercure, Jean-François, 2018. "Fashion, fads and the popularity of choices: Micro-foundations for diffusion consumer theory," Structural Change and Economic Dynamics, Elsevier, vol. 46(C), pages 194-207.
    9. Viauroux, Christelle, 2007. "Structural estimation of congestion costs," European Economic Review, Elsevier, vol. 51(1), pages 1-25, January.
    10. Pi, Xidong & Qian, Zhen (Sean), 2017. "A stochastic optimal control approach for real-time traffic routing considering demand uncertainties and travelers’ choice heterogeneity," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 710-732.
    11. Li, Yuanyuan & Liu, Yang, 2021. "Optimizing flexible one-to-two matching in ride-hailing systems with boundedly rational users," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 150(C).
    12. Ma, Jie & Meng, Qiang & Cheng, Lin & Liu, Zhiyuan, 2022. "General stochastic ridesharing user equilibrium problem with elastic demand," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 162-194.
    13. Kasun P Wijayaratna & Vinayak V Dixit & Laurent Denant-Boemont & S Travis Waller, 2017. "An experimental study of the Online Information Paradox: Does en-route information improve road network performance?," PLOS ONE, Public Library of Science, vol. 12(9), pages 1-17, September.
    14. Wang, Shuaian & Zhang, Wei & Qu, Xiaobo, 2018. "Trial-and-error train fare design scheme for addressing boarding/alighting congestion at CBD stations," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 318-335.
    15. Swait, J. & de Bekker-Grob, E.W., 2022. "A discrete choice model implementing gist-based categorization of alternatives, with applications to patient preferences for cancer screening and treatment," Journal of Health Economics, Elsevier, vol. 85(C).
    16. M. Rouhani, Omid, 2015. "Impact of Value of Time (VOT) on toll roads," MPRA Paper 65087, University Library of Munich, Germany.
    17. Mariska van Essen & Tom Thomas & Eric van Berkum & Caspar Chorus, 2020. "Travelers’ compliance with social routing advice: evidence from SP and RP experiments," Transportation, Springer, vol. 47(3), pages 1047-1070, June.
    18. Thomas, Tom & Tutert, Bas, 2015. "Route choice behavior in a radial structured urban network: Do people choose the orbital or the route through the city center?," Journal of Transport Geography, Elsevier, vol. 48(C), pages 85-95.
    19. Meng, Qiang & Liu, Zhiyuan & Wang, Shuaian, 2012. "Optimal distance tolls under congestion pricing and continuously distributed value of time," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(5), pages 937-957.
    20. M. Rouhani, Omid, 2014. "Road pricing: An overview," MPRA Paper 59662, University Library of Munich, Germany.

    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:transb:v:168:y:2023:i:c:p:170-205. 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: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    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.