IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v47y2013i2p280-293.html
   My bibliography  Save this article

The Stiff Is Moving---Conjugate Direction Frank-Wolfe Methods with Applications to Traffic Assignment

Author

Listed:
  • Maria Mitradjieva

    (Institute of Technology, Linköping University, SE-58183 Linköping, Sweden)

  • Per Olov Lindberg

    (Department of Transport Science, KTH Royal Institute of Technology, SE-100 44 Stockholm, Sweden; and Department of Numerical Analysis, KTH)

Abstract

We present versions of the Frank-Wolfe method for linearly constrained convex programs, in which consecutive search directions are made conjugate. Preliminary computational studies in a MATLAB environment applying pure Frank-Wolfe, conjugate direction Frank-Wolfe (CFW), bi-conjugate Frank-Wolfe (BFW), and “partanized” Frank-Wolfe methods to some classical Traffic Assignment Problems show that CFW and BFW compare favorably to the other methods. This spurred a more detailed study, comparing our methods to an origin-based algorithm. This study indicates that our methods are competitive for accuracy requirements ensuring link flow stability. We also show that CFW is globally convergent. We further point at independent studies by other researchers that show that our methods compare favorably with recent bush-based and gradient projection algorithms on computers with several cores.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:ortrsc:v:47:y:2013:i:2:p:280-293
    DOI: 10.1287/trsc.1120.0409
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1120.0409
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1120.0409?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
    ---><---

    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. A. Ouorou & P. Mahey & J.-Ph. Vial, 2000. "A Survey of Algorithms for Convex Multicommodity Flow Problems," Management Science, INFORMS, vol. 46(1), pages 126-147, January.
    3. Hillel Bar-Gera, 2002. "Origin-Based Algorithm for the Traffic Assignment Problem," Transportation Science, INFORMS, vol. 36(4), pages 398-417, November.
    4. 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.
    5. 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.
    6. 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.
    7. Y. Arezki & D. Van Vliet, 1990. "A Full Analytical Implementation of the PARTAN/Frank–Wolfe Algorithm for Equilibrium Assignment," Transportation Science, INFORMS, vol. 24(1), pages 58-62, February.
    8. Bar-Gera, Hillel, 2010. "Traffic assignment by paired alternative segments," Transportation Research Part B: Methodological, Elsevier, vol. 44(8-9), pages 1022-1046, September.
    9. 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.
    10. 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.
    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. 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.
    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. 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).
    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. Immanuel M. Bomze & Francesco Rinaldi & Damiano Zeffiro, 2021. "Frank–Wolfe and friends: a journey into projection-free first-order optimization methods," 4OR, Springer, vol. 19(3), pages 313-345, September.
    7. Wang, Ting & Li, Yao & Jia, Bin & Long, Jiancheng, 2024. "An autonomous vehicle exclusive lane design problem under the mixed autonomy traffic environment: Model formulation and large-scale algorithm design," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 188(C).
    8. 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).
    9. Sohouenou, Philippe Y.R. & Neves, Luis A.C., 2021. "Assessing the effects of link-repair sequences on road network resilience," International Journal of Critical Infrastructure Protection, Elsevier, vol. 34(C).
    10. Rambha, Tarun & Boyles, Stephen D., 2016. "Dynamic pricing in discrete time stochastic day-to-day route choice models," Transportation Research Part B: Methodological, Elsevier, vol. 92(PA), pages 104-118.
    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.

    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. Taesung Hwang, 2021. "Assignment of Freight Truck Shipment on the U.S. Highway Network," Sustainability, MDPI, vol. 13(11), pages 1-11, June.
    3. 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.
    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. 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).
    6. 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).
    7. 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.
    8. 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).
    9. 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.
    10. 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.
    11. 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.
    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. 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. Jaller, Miguel & Pahwa, Anmol & Zhang, Michael, 2021. "Cargo Routing and Disadvantaged Communities," Institute of Transportation Studies, Working Paper Series qt9qg2318x, Institute of Transportation Studies, UC Davis.
    16. Shen, Wei & Wynter, Laura, 2012. "A new one-level convex optimization approach for estimating origin–destination demand," Transportation Research Part B: Methodological, Elsevier, vol. 46(10), pages 1535-1555.
    17. 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).
    18. Frédéric Babonneau & Jean-Philippe Vial, 2008. "An Efficient Method to Compute Traffic Assignment Problems with Elastic Demands," Transportation Science, INFORMS, vol. 42(2), pages 249-260, May.
    19. Sang Nguyen & Stefano Pallottino & Federico Malucelli, 2001. "A Modeling Framework for Passenger Assignment on a Transport Network with Timetables," Transportation Science, INFORMS, vol. 35(3), pages 238-249, August.
    20. Meruza Kubentayeva & Demyan Yarmoshik & Mikhail Persiianov & Alexey Kroshnin & Ekaterina Kotliarova & Nazarii Tupitsa & Dmitry Pasechnyuk & Alexander Gasnikov & Vladimir Shvetsov & Leonid Baryshev & A, 2024. "Primal-dual gradient methods for searching network equilibria in combined models with nested choice structure and capacity constraints," Computational Management Science, Springer, vol. 21(1), pages 1-33, June.

    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:inm:ortrsc:v:47:y:2013:i:2:p:280-293. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.