IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v310y2023i3p1072-1084.html
   My bibliography  Save this article

An alternating direction method of multipliers for solving user equilibrium problem

Author

Listed:
  • Liu, Zhiyuan
  • Chen, Xinyuan
  • Hu, Jintao
  • Wang, Shuaian
  • Zhang, Kai
  • Zhang, Honggang

Abstract

This paper introduces a new parallel computing algorithm to address the user equilibrium (UE) problem. Searching for efficient solution algorithms for UE has been a recurring study subject in transportation research and has attracted much attention in past decades. Existing solution algorithms can be classified into three categories: link-based, path-based, and origin-based. This paper introduces an alternating direction method of multipliers (ADMM) algorithm that is different from these categories. Based on the origin-based formulation of UE problem, an equivalent problem is proposed which eliminates the flow conservation conditions through the augmented Lagrangian function. In order to make use of the ADMM, the network links should be grouped into different blocks, where the links in the same block are disconnected. This link grouping problem falls into the category of edge-coloring problem in graph theory, and it follows the Vizing theorem. A novel approach is developed for the link grouping problem. For links in the same block, we have a separable subproblem, which is solved in parallel by the gradient projection algorithm. Numerical experiments are conducted to validate the proposed algorithm, which shows its computation efficiency.

Suggested Citation

  • Liu, Zhiyuan & Chen, Xinyuan & Hu, Jintao & Wang, Shuaian & Zhang, Kai & Zhang, Honggang, 2023. "An alternating direction method of multipliers for solving user equilibrium problem," European Journal of Operational Research, Elsevier, vol. 310(3), pages 1072-1084.
    • Handle: RePEc:eee:ejores:v:310:y:2023:i:3:p:1072-1084
    DOI: 10.1016/j.ejor.2023.04.008
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722172300276X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2023.04.008?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. Warren B. Powell & Yosef Sheffi, 1982. "The Convergence of Equilibrium Algorithms with Predetermined Step Sizes," Transportation Science, INFORMS, vol. 16(1), pages 45-55, February.
    2. 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.
    3. Weintraub, Andrés & Ortiz, Carmen & González, Jaime, 1985. "Accelerating convergence of the Frank-Wolfe algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 19(2), pages 113-122, April.
    4. Xie, Chi, 2016. "New insights and improvements of using paired alternative segments for traffic assignmentAuthor-Name: Xie, Jun," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 406-424.
    5. Fukushima, Masao, 1984. "A modified Frank-Wolfe algorithm for solving the traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 18(2), pages 169-177, April.
    6. Zheng, Hong & Peeta, Srinivas, 2014. "Cost scaling based successive approximation algorithm for the traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 68(C), pages 17-30.
    7. Fukushima, Masao, 1984. "On the dual approach to the traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 18(3), pages 235-245, June.
    8. Sang Nguyen, 1974. "An Algorithm for the Traffic Assignment Problem," Transportation Science, INFORMS, vol. 8(3), pages 203-216, August.
    9. 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.
    10. Bar-Gera, Hillel, 2010. "Traffic assignment by paired alternative segments," Transportation Research Part B: Methodological, Elsevier, vol. 44(8-9), pages 1022-1046, September.
    11. Yu (Marco) Nie, 2012. "A Note on Bar-Gera's Algorithm for the Origin-Based Traffic Assignment Problem," Transportation Science, INFORMS, vol. 46(1), pages 27-38, February.
    12. Xie, Jun & Nie, Yu (Marco) & Yang, Xiaoguang, 2013. "Quadratic approximation and convergence of some bush-based algorithms for the traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 56(C), pages 15-30.
    13. B. Feijoo & R. R. Meyer, 1988. "Piecewise-Linear Approximation Methods for Nonseparable Convex Optimization," Management Science, INFORMS, vol. 34(3), pages 411-419, March.
    14. Nie, Yu (Marco), 2010. "A class of bush-based algorithms for the traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 44(1), pages 73-89, January.
    15. Jun Xie & Yu (Marco) Nie, 2019. "A New Algorithm for Achieving Proportionality in User Equilibrium Traffic Assignment," Transportation Science, INFORMS, vol. 53(2), pages 566-584, March.
    16. Hillel Bar-Gera, 2002. "Origin-Based Algorithm for the Traffic Assignment Problem," Transportation Science, INFORMS, vol. 36(4), pages 398-417, November.
    17. Maria Mitradjieva & Per Olov Lindberg, 2013. "The Stiff Is Moving---Conjugate Direction Frank-Wolfe Methods with Applications to Traffic Assignment ," Transportation Science, INFORMS, vol. 47(2), pages 280-293, May.
    18. Dial, Robert B., 2006. "A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration," Transportation Research Part B: Methodological, Elsevier, vol. 40(10), pages 917-936, 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. Liu, Zhiyuan & Zhang, Honggang & Zhang, Kai & Zhou, Zihan, 2023. "Integrating alternating direction method of multipliers and bush for solving the traffic assignment problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    2. Zhang, Honggang & Liu, Zhiyuan & Dong, Yu & Zhou, Hongyue & Liu, Pan & Chen, Jun, 2024. "A novel network equilibrium model integrating urban aerial mobility," Transportation Research Part A: Policy and Practice, Elsevier, vol. 187(C).
    3. Liu, Zhiyuan & Dong, Yu & Zhang, Honggang & Zheng, Nan & Huang, Kai, 2024. "A novel parallel computing framework for traffic assignment problem: Integrating alternating direction method of multipliers with Jacobi over relaxation method," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 189(C).
    4. Zhao, Wei & Liao, Qi & Qiu, Rui & Liu, Chunying & Xu, Ning & Yu, Xiao & Liang, Yongtu, 2024. "Pipe sharing: A bilevel optimization model for the optimal capacity allocation of natural gas network," Applied Energy, Elsevier, vol. 359(C).
    5. 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.
    6. Liu, Zhiyuan & Xie, Shen & Zhang, Honggang & Zhou, Dinghao & Yang, Yuwei, 2024. "A parallel computing framework for large-scale microscopic traffic simulation based on spectral partitioning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 181(C).
    7. Cheng, Qixiu & Lin, Yuqian & Zhou, Xuesong (Simon) & Liu, Zhiyuan, 2024. "Analytical formulation for explaining the variations in traffic states: A fundamental diagram modeling perspective with stochastic parameters," European Journal of Operational Research, Elsevier, vol. 312(1), pages 182-197.

    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. Liu, Zhiyuan & Zhang, Honggang & Zhang, Kai & Zhou, Zihan, 2023. "Integrating alternating direction method of multipliers and bush for solving the traffic assignment problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    2. Xie, Chi, 2016. "New insights and improvements of using paired alternative segments for traffic assignmentAuthor-Name: Xie, Jun," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 406-424.
    3. Xu, Zhandong & Xie, Jun & Liu, Xiaobo & Nie, Yu (Marco), 2020. "Hyperpath-based algorithms for the transit equilibrium assignment problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(C).
    4. Zhang, Honggang & Liu, Zhiyuan & Wang, Jian & Wu, Yunchi, 2023. "A novel flow update policy in solving traffic assignment problems: Successive over relaxation iteration method," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 174(C).
    5. Jafari, Ehsan & Pandey, Venktesh & Boyles, Stephen D., 2017. "A decomposition approach to the static traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 270-296.
    6. Liu, Zhiyuan & Dong, Yu & Zhang, Honggang & Zheng, Nan & Huang, Kai, 2024. "A novel parallel computing framework for traffic assignment problem: Integrating alternating direction method of multipliers with Jacobi over relaxation method," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 189(C).
    7. Taesung Hwang, 2021. "Assignment of Freight Truck Shipment on the U.S. Highway Network," Sustainability, MDPI, vol. 13(11), pages 1-11, June.
    8. Maria Mitradjieva & Per Olov Lindberg, 2013. "The Stiff Is Moving---Conjugate Direction Frank-Wolfe Methods with Applications to Traffic Assignment ," Transportation Science, INFORMS, vol. 47(2), pages 280-293, May.
    9. Zheng, Hong & Peeta, Srinivas, 2014. "Cost scaling based successive approximation algorithm for the traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 68(C), pages 17-30.
    10. Feng, Liyang & Xie, Jun & Liu, Xiaobo & Tang, Youhua & Wang, David Z.W. & Nie, Yu (Marco), 2024. "Is order-2 proportionality good enough for approximating the most likely path flow in user equilibrium traffic assignment?," Transportation Research Part B: Methodological, Elsevier, vol. 186(C).
    11. David Di Lorenzo & Alessandro Galligari & Marco Sciandrone, 2015. "A convergent and efficient decomposition method for the traffic assignment problem," Computational Optimization and Applications, Springer, vol. 60(1), pages 151-170, January.
    12. Hong Zheng, 2015. "Adaptation of Network Simplex for the Traffic Assignment Problem," Transportation Science, INFORMS, vol. 49(3), pages 543-558, August.
    13. Wang, Xiaolei & Wang, Jun & Guo, Lei & Liu, Wei & Zhang, Xiaoning, 2021. "A convex programming approach for ridesharing user equilibrium under fixed driver/rider demand," Transportation Research Part B: Methodological, Elsevier, vol. 149(C), pages 33-51.
    14. Xie, Jun & Nie, Yu (Marco) & Yang, Xiaoguang, 2013. "Quadratic approximation and convergence of some bush-based algorithms for the traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 56(C), pages 15-30.
    15. Yu (Marco) Nie, 2012. "A Note on Bar-Gera's Algorithm for the Origin-Based Traffic Assignment Problem," Transportation Science, INFORMS, vol. 46(1), pages 27-38, February.
    16. Jun Xie & Yu (Marco) Nie, 2019. "A New Algorithm for Achieving Proportionality in User Equilibrium Traffic Assignment," Transportation Science, INFORMS, vol. 53(2), pages 566-584, March.
    17. Bar-Gera, Hillel & Boyce, David & Nie, Yu (Marco), 2012. "User-equilibrium route flows and the condition of proportionality," Transportation Research Part B: Methodological, Elsevier, vol. 46(3), pages 440-462.
    18. Smith, Mike & Mounce, Richard, 2011. "A splitting rate model of traffic re-routeing and traffic control," Transportation Research Part B: Methodological, Elsevier, vol. 45(9), pages 1389-1409.
    19. 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.
    20. Bar-Gera, Hillel, 2010. "Traffic assignment by paired alternative segments," Transportation Research Part B: Methodological, Elsevier, vol. 44(8-9), pages 1022-1046, September.

    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:ejores:v:310:y:2023:i:3:p:1072-1084. 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/locate/eor .

    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.