IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v60y2015i1p151-170.html
   My bibliography  Save this article

A convergent and efficient decomposition method for the traffic assignment problem

Author

Listed:
  • David Di Lorenzo
  • Alessandro Galligari
  • Marco Sciandrone

Abstract

In this work we consider the network equilibrium problem formulated as convex minimization problem whose variables are the path flows. In order to take into account the difficulties related to the large dimension of real network problems we adopt a decomposition-based approach suitably combined with a column generation strategy. We present an inexact block-coordinate descent method and we prove the global convergence of the algorithm. The results of computational experiments performed on medium-large dimensional problems show that the proposed algorithm is at least competitive with state of the art algorithms. Copyright Springer Science+Business Media New York 2015

Suggested Citation

  • 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.
    • Handle: RePEc:spr:coopap:v:60:y:2015:i:1:p:151-170
    DOI: 10.1007/s10589-014-9668-6
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10589-014-9668-6
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10589-014-9668-6?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. Bar-Gera, Hillel & Hellman, Fredrik & Patriksson, Michael, 2013. "Computational precision of traffic equilibria sensitivities in automatic network design and road pricing," Transportation Research Part B: Methodological, Elsevier, vol. 57(C), pages 485-500.
    2. 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.
    3. C. J. Lin & S. Lucidi & L. Palagi & A. Risi & M. Sciandrone, 2009. "Decomposition Algorithm Model for Singly Linearly-Constrained Problems Subject to Lower and Upper Bounds," Journal of Optimization Theory and Applications, Springer, vol. 141(1), pages 107-126, April.
    4. 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.
    5. Bar-Gera, Hillel, 2010. "Traffic assignment by paired alternative segments," Transportation Research Part B: Methodological, Elsevier, vol. 44(8-9), pages 1022-1046, September.
    6. 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.
    7. Hillel Bar-Gera, 2002. "Origin-Based Algorithm for the Traffic Assignment Problem," Transportation Science, INFORMS, vol. 36(4), pages 398-417, November.
    8. Larry J. LeBlanc & Richard V. Helgason & David E. Boyce, 1985. "Improved Efficiency of the Frank-Wolfe Algorithm for Convex Network Programs," Transportation Science, INFORMS, vol. 19(4), pages 445-462, November.
    9. 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.
    10. 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. Leonardo Galli & Alessandro Galligari & Marco Sciandrone, 2020. "A unified convergence framework for nonmonotone inexact decomposition methods," Computational Optimization and Applications, Springer, vol. 75(1), pages 113-144, January.

    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 & 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.
    2. 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).
    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. 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.
    5. 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).
    6. 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.
    7. 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.
    8. 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.
    9. Jafari, Ehsan & Boyles, Stephen D., 2016. "Improved bush-based methods for network contraction," Transportation Research Part B: Methodological, Elsevier, vol. 83(C), pages 298-313.
    10. 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.
    11. 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.
    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. Meng Li & Guowei Hua & Haijun Huang, 2018. "A Multi-Modal Route Choice Model with Ridesharing and Public Transit," Sustainability, MDPI, vol. 10(11), pages 1-14, November.
    14. 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).
    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. Hong Zheng, 2015. "Adaptation of Network Simplex for the Traffic Assignment Problem," Transportation Science, INFORMS, vol. 49(3), pages 543-558, August.
    17. 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.
    18. Rinaldi, Marco & Tampère, Chris M.J. & Viti, Francesco, 2018. "On characterizing the relationship between route choice behaviour and optimal traffic control solution space," Transportation Research Part B: Methodological, Elsevier, vol. 117(PB), pages 892-906.
    19. Bar-Gera, Hillel, 2010. "Traffic assignment by paired alternative segments," Transportation Research Part B: Methodological, Elsevier, vol. 44(8-9), pages 1022-1046, September.
    20. Liu, Ronghui & Smith, Mike, 2015. "Route choice and traffic signal control: A study of the stability and instability of a new dynamical model of route choice and traffic signal control," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 123-145.

    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:spr:coopap:v:60:y:2015:i:1:p:151-170. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.