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

Investigating path-based solution algorithms to the stochastic user equilibrium problem

Author

Listed:
  • Bekhor, Shlomo
  • Toledo, Tomer

Abstract

This paper focuses on path-based solution algorithms to the stochastic user equilibrium (SUE) and investigates their convergence properties. Two general optimization methods are adapted to solve the logit SUE problem. First, a method that closely follows the Gradient Projection (GP) algorithm developed for the deterministic problem is derived. While this method is very efficient for the deterministic user equilibrium problem, we use a simple example to illustrate why it is not suitable for the SUE problem. Next, a different variant of gradient projection, which exploits special characteristics of the SUE solution, is presented. In this method the projection is on the linear manifold of active constraints. The algorithms are applied to solve simple networks. The examples are used to compare the convergence properties of the algorithms with a path-based variant of the Method of Successive Averages (MSA) and with the Disaggregate Simplicial Decomposition (DSD) algorithm.

Suggested Citation

  • Bekhor, Shlomo & Toledo, Tomer, 2005. "Investigating path-based solution algorithms to the stochastic user equilibrium problem," Transportation Research Part B: Methodological, Elsevier, vol. 39(3), pages 279-295, March.
    • Handle: RePEc:eee:transb:v:39:y:2005:i:3:p:279-295
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191-2615(04)00049-9
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Mingyuan Chen & Attahiru Sule Alfa, 1991. "Algorithms for solving fisk's stochastic traffic assignment model," Transportation Research Part B: Methodological, Elsevier, vol. 25(6), pages 405-412, December.
    3. Jayakrishnan, R. & Tsai, Wei T. & Prashker, Joseph N. & Rajadhyaksha, Subodh, 1994. "A Faster Path-Based Algorithm for Traffic Assignment," University of California Transportation Center, Working Papers qt2hf4541x, University of California Transportation Center.
    4. Leurent, Fabien M., 1997. "Curbing the computational difficulty of the logit equilibrium assignment model," Transportation Research Part B: Methodological, Elsevier, vol. 31(4), pages 315-326, August.
    5. Prashker, Joseph N. & Bekhor, Shlomo, 2000. "Some observations on stochastic user equilibrium and system optimum of traffic assignment," Transportation Research Part B: Methodological, Elsevier, vol. 34(4), pages 277-291, May.
    6. Torbjörn Larsson & Michael Patriksson, 1992. "Simplicial Decomposition with Disaggregated Representation for the Traffic Assignment Problem," Transportation Science, INFORMS, vol. 26(1), pages 4-17, February.
    7. Chen, Anthony & Lee, Der-Horng & Jayakrishnan, R., 2002. "Computational study of state-of-the-art path-based traffic assignment algorithms," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 59(6), pages 509-518.
    8. Akamatsu, Takashi, 1996. "Cyclic flows, Markov process and stochastic traffic assignment," Transportation Research Part B: Methodological, Elsevier, vol. 30(5), pages 369-386, October.
    9. Carlos F. Daganzo & Yosef Sheffi, 1977. "On Stochastic Models of Traffic Assignment," Transportation Science, INFORMS, vol. 11(3), pages 253-274, August.
    10. Damberg, Olof & Lundgren, Jan T. & Patriksson, Michael, 1996. "An algorithm for the stochastic user equilibrium problem," Transportation Research Part B: Methodological, Elsevier, vol. 30(2), pages 115-131, April.
    11. Maher, Mike, 1998. "Algorithms for logit-based stochastic user equilibrium assignment," Transportation Research Part B: Methodological, Elsevier, vol. 32(8), pages 539-549, November.
    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. Les Foulds & Daniel Duarte & Hugo Nascimento & Humberto Longo & Bryon Hall, 2014. "Turning restriction design in traffic networks with a budget constraint," Journal of Global Optimization, Springer, vol. 60(2), pages 351-371, October.
    2. Zhao, Taiyi & Tang, Yuchun & Li, Qiming & Wang, Jingquan, 2023. "Resilience-oriented network reconfiguration strategies for community emergency medical services," Reliability Engineering and System Safety, Elsevier, vol. 231(C).
    3. Ye, Jiao & Jiang, Yu & Chen, Jun & Liu, Zhiyuan & Guo, Renzhong, 2021. "Joint optimisation of transfer location and capacity for a capacitated multimodal transport network with elastic demand: a bi-level programming model and paradoxes," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 156(C).
    4. 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.
    5. Guido Gentile, 2018. "New Formulations of the Stochastic User Equilibrium with Logit Route Choice as an Extension of the Deterministic Model," Service Science, INFORMS, vol. 52(6), pages 1531-1547, December.
    6. Seungkyu Ryu, 2021. "Mode Choice Change under Environmental Constraints in the Combined Modal Split and Traffic Assignment Model," Sustainability, MDPI, vol. 13(7), pages 1-16, March.
    7. Ahipaşaoğlu, Selin Damla & Meskarian, Rudabeh & Magnanti, Thomas L. & Natarajan, Karthik, 2015. "Beyond normality: A cross moment-stochastic user equilibrium model," Transportation Research Part B: Methodological, Elsevier, vol. 81(P2), pages 333-354.
    8. Liu, Haoxiang & Zou, Yuncheng & Chen, Ya & Long, Jiancheng, 2021. "Optimal locations and electricity prices for dynamic wireless charging links of electric vehicles for sustainable transportation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    9. Long, Jiancheng & Gao, Ziyou & Zhang, Haozhi & Szeto, W.Y., 2010. "A turning restriction design problem in urban road networks," European Journal of Operational Research, Elsevier, vol. 206(3), pages 569-578, November.
    10. Tan, Heqing & Xu, Xiangdong & Chen, Anthony, 2024. "On endogenously distinguishing inactive paths in stochastic user equilibrium: A convex programming approach with a truncated path choice model," Transportation Research Part B: Methodological, Elsevier, vol. 183(C).
    11. Chen, Anthony & Pravinvongvuth, Surachet & Xu, Xiangdong & Ryu, Seungkyu & Chootinan, Piya, 2012. "Examining the scaling effect and overlapping problem in logit-based stochastic user equilibrium models," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(8), pages 1343-1358.
    12. Chen, Anthony & Choi, Keechoo, 2017. "Solving the combined modal split and traffic assignment problem with two types of transit impedance functionAuthor-Name: Ryu, Seungkyu," European Journal of Operational Research, Elsevier, vol. 257(3), pages 870-880.
    13. Honggang Zhang & Zhiyuan Liu & Yicheng Zhang & Weijie Chen & Chenyang Zhang, 2024. "A Distributed Computing Method Integrating Improved Gradient Projection for Solving Stochastic Traffic Equilibrium Problem," Networks and Spatial Economics, Springer, vol. 24(2), pages 361-381, June.
    14. Oyama, Yuki & Hara, Yusuke & Akamatsu, Takashi, 2022. "Markovian traffic equilibrium assignment based on network generalized extreme value model," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 135-159.
    15. Bliemer, Michiel C.J. & Raadsen, Mark P.H. & Smits, Erik-Sander & Zhou, Bojian & Bell, Michael G.H., 2014. "Quasi-dynamic traffic assignment with residual point queues incorporating a first order node model," Transportation Research Part B: Methodological, Elsevier, vol. 68(C), pages 363-384.
    16. Long, Jiancheng & Szeto, W.Y. & Huang, Hai-Jun, 2014. "A bi-objective turning restriction design problem in urban road networks," European Journal of Operational Research, Elsevier, vol. 237(2), pages 426-439.
    17. 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.
    18. Rasmussen, Thomas Kjær & Watling, David Paul & Prato, Carlo Giacomo & Nielsen, Otto Anker, 2015. "Stochastic user equilibrium with equilibrated choice sets: Part II – Solving the restricted SUE for the logit family," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 146-165.
    19. Liu, Haoxiang & Szeto, W.Y. & Long, Jiancheng, 2019. "Bike network design problem with a path-size logit-based equilibrium constraint: Formulation, global optimization, and matheuristic," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 127(C), pages 284-307.
    20. Du, Muqing & Tan, Heqing & Chen, Anthony, 2021. "A faster path-based algorithm with Barzilai-Borwein step size for solving stochastic traffic equilibrium models," European Journal of Operational Research, Elsevier, vol. 290(3), pages 982-999.
    21. Wang, Dong & Liao, Feixiong & Gao, Ziyou & Rasouli, Soora & Huang, Hai-Jun, 2020. "Tolerance-based column generation for boundedly rational dynamic activity-travel assignment in large-scale networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 141(C).
    22. Zhou, Bojian & Li, Xuhong & He, Jie, 2014. "Exploring trust region method for the solution of logit-based stochastic user equilibrium problem," European Journal of Operational Research, Elsevier, vol. 239(1), pages 46-57.
    23. Liu, Ke & Liu, Yanli, 2023. "Stochastic user equilibrium based spatial-temporal distribution prediction of electric vehicle charging load," Applied Energy, Elsevier, vol. 339(C).
    24. Li, Xinyan & Xie, Chi & Bao, Zhaoyao, 2022. "A multimodal multicommodity network equilibrium model with service capacity and bottleneck congestion for China-Europe containerized freight flows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    25. Heqing Tan & Muqing Du & Xiaowei Jiang & Zhaoming Chu, 2019. "The Combined Distribution and Assignment Model: A New Solution Algorithm and Its Applications in Travel Demand Forecasting for Modern Urban Transportation," Sustainability, MDPI, vol. 11(7), pages 1-18, April.

    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. Tan, Heqing & Xu, Xiangdong & Chen, Anthony, 2024. "On endogenously distinguishing inactive paths in stochastic user equilibrium: A convex programming approach with a truncated path choice model," Transportation Research Part B: Methodological, Elsevier, vol. 183(C).
    2. Ahipaşaoğlu, Selin Damla & Meskarian, Rudabeh & Magnanti, Thomas L. & Natarajan, Karthik, 2015. "Beyond normality: A cross moment-stochastic user equilibrium model," Transportation Research Part B: Methodological, Elsevier, vol. 81(P2), pages 333-354.
    3. Honggang Zhang & Zhiyuan Liu & Yicheng Zhang & Weijie Chen & Chenyang Zhang, 2024. "A Distributed Computing Method Integrating Improved Gradient Projection for Solving Stochastic Traffic Equilibrium Problem," Networks and Spatial Economics, Springer, vol. 24(2), pages 361-381, June.
    4. Oyama, Yuki & Hara, Yusuke & Akamatsu, Takashi, 2022. "Markovian traffic equilibrium assignment based on network generalized extreme value model," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 135-159.
    5. Guido Gentile, 2018. "New Formulations of the Stochastic User Equilibrium with Logit Route Choice as an Extension of the Deterministic Model," Service Science, INFORMS, vol. 52(6), pages 1531-1547, December.
    6. Watling, David Paul & Rasmussen, Thomas Kjær & Prato, Carlo Giacomo & Nielsen, Otto Anker, 2015. "Stochastic user equilibrium with equilibrated choice sets: Part I – Model formulations under alternative distributions and restrictions," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 166-181.
    7. Rasmussen, Thomas Kjær & Watling, David Paul & Prato, Carlo Giacomo & Nielsen, Otto Anker, 2015. "Stochastic user equilibrium with equilibrated choice sets: Part II – Solving the restricted SUE for the logit family," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 146-165.
    8. Zhou, Bojian & Li, Xuhong & He, Jie, 2014. "Exploring trust region method for the solution of logit-based stochastic user equilibrium problem," European Journal of Operational Research, Elsevier, vol. 239(1), pages 46-57.
    9. Du, Muqing & Tan, Heqing & Chen, Anthony, 2021. "A faster path-based algorithm with Barzilai-Borwein step size for solving stochastic traffic equilibrium models," European Journal of Operational Research, Elsevier, vol. 290(3), pages 982-999.
    10. Chen, Anthony & Pravinvongvuth, Surachet & Xu, Xiangdong & Ryu, Seungkyu & Chootinan, Piya, 2012. "Examining the scaling effect and overlapping problem in logit-based stochastic user equilibrium models," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(8), pages 1343-1358.
    11. Kitthamkesorn, Songyot & Chen, Anthony, 2014. "Unconstrained weibit stochastic user equilibrium model with extensions," Transportation Research Part B: Methodological, Elsevier, vol. 59(C), pages 1-21.
    12. Xie, Chi & Travis Waller, S., 2012. "Stochastic traffic assignment, Lagrangian dual, and unconstrained convex optimization," Transportation Research Part B: Methodological, Elsevier, vol. 46(8), pages 1023-1042.
    13. E. Nikolova & N. E. Stier-Moses, 2014. "A Mean-Risk Model for the Traffic Assignment Problem with Stochastic Travel Times," Operations Research, INFORMS, vol. 62(2), pages 366-382, April.
    14. Maher, Mike, 1998. "Algorithms for logit-based stochastic user equilibrium assignment," Transportation Research Part B: Methodological, Elsevier, vol. 32(8), pages 539-549, November.
    15. Ampol Karoonsoontawong & Dung-Ying Lin, 2015. "Combined Gravity Model Trip Distribution and Paired Combinatorial Logit Stochastic User Equilibrium Problem," Networks and Spatial Economics, Springer, vol. 15(4), pages 1011-1048, December.
    16. Long, Jiancheng & Szeto, W.Y. & Huang, Hai-Jun, 2014. "A bi-objective turning restriction design problem in urban road networks," European Journal of Operational Research, Elsevier, vol. 237(2), pages 426-439.
    17. Nie, Yu (Marco), 2011. "Multi-class percentile user equilibrium with flow-dependent stochasticity," Transportation Research Part B: Methodological, Elsevier, vol. 45(10), pages 1641-1659.
    18. Huang, Hai-Jun & Bell, Michael G. H., 1998. "A study on logit assignment which excludes all cyclic flows," Transportation Research Part B: Methodological, Elsevier, vol. 32(6), pages 401-412, August.
    19. 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.
    20. Damberg, Olof & Lundgren, Jan T. & Patriksson, Michael, 1996. "An algorithm for the stochastic user equilibrium problem," Transportation Research Part B: Methodological, Elsevier, vol. 30(2), pages 115-131, April.

    More about this item

    Statistics

    Access and download statistics

    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:39:y:2005:i:3:p:279-295. 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.