IDEAS home Printed from https://ideas.repec.org/p/cdl/uctcwp/qt2hf4541x.html
   My bibliography  Save this paper

A Faster Path-Based Algorithm for Traffic Assignment

Author

Listed:
  • Jayakrishnan, R.
  • Tsai, Wei T.
  • Prashker, Joseph N.
  • Rajadhyaksha, Subodh

Abstract

This paper takes a fresh look at the arguments against path-enumeration algorithms for the traffic assignment problem and provides the results of a gradient projection method. The motivation behind the research is the orders of magnitude improvement in the availability of computer storage over the last decade. Faster assignment algorithms are necessary for real-time traffic assignment under several of the proposed Advanced Traffic Management System (ATMS) strategies, and path-based solutions are preferred. Our results show that gradient projection converges in 1/10 iterations than the conventional Frank-Wolfe algorithm. The computation time improvement is of the same order for small networks, but reduces as the network size increases. We discuss the computer implementation issues carefully, and provide schemes to achieve a 10-fold speed-up for larger networks also. We have used the algorithm for networks of up to 2000 nodes on a typical computer work station, and we discuss certain data structures to save storage and solve the assignment problem for even a 5000 node network.

Suggested Citation

  • 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.
    • Handle: RePEc:cdl:uctcwp:qt2hf4541x
    as

    Download full text from publisher

    File URL: https://www.escholarship.org/uc/item/2hf4541x.pdf;origin=repeccitec
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Barton, Russell R. & Hearn, Donald W. & Lawphongpanich, Siriphong, 1989. "The equivalence of transfer and generalized benders decomposition methods for traffic assignment," Transportation Research Part B: Methodological, Elsevier, vol. 23(1), pages 61-73, February.
    2. Michael Florian, 1977. "A Traffic Equilibrium Model of Travel by Car and Public Transit Modes," Transportation Science, INFORMS, vol. 11(2), pages 166-179, May.
    3. Nagurney, Anna B., 1984. "Comparative tests of multimodal traffic equilibrium methods," Transportation Research Part B: Methodological, Elsevier, vol. 18(6), pages 469-485, December.
    4. Bin Ran & David E. Boyce & Larry J. LeBlanc, 1993. "A New Class of Instantaneous Dynamic User-Optimal Traffic Assignment Models," Operations Research, INFORMS, vol. 41(1), pages 192-202, February.
    5. 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.
    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. García, Ricardo & Marín, Angel, 2005. "Network equilibrium with combined modes: models and solution algorithms," Transportation Research Part B: Methodological, Elsevier, vol. 39(3), pages 223-254, March.
    2. Cantarella, Giulio Erberto & Cartenì, Armando & de Luca, Stefano, 2015. "Stochastic equilibrium assignment with variable demand: Theoretical and implementation issues," European Journal of Operational Research, Elsevier, vol. 241(2), pages 330-347.
    3. Liu, Tian-Liang & Huang, Hai-Jun & Yang, Hai & Zhang, Xiaoning, 2009. "Continuum modeling of park-and-ride services in a linear monocentric city with deterministic mode choice," Transportation Research Part B: Methodological, Elsevier, vol. 43(6), pages 692-707, July.
    4. Tao Zhang & Yang Yang & Gang Cheng & Minjie Jin, 2020. "A Practical Traffic Assignment Model for Multimodal Transport System Considering Low-Mobility Groups," Mathematics, MDPI, vol. 8(3), pages 1-19, March.
    5. 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).
    6. Moore, II, James E. & Kim, Geunyoung & Cho, Seongdil & Hu, Hsi-hwa & Xu, Rong, 1997. "Evaluating System ATMIS Technologies Via Rapid Estimation Of Network Flows: Final Report," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt5c70f3d9, Institute of Transportation Studies, UC Berkeley.
    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. Ziliaskopoulos, Athanasios & Wardell, Whitney, 2000. "An intermodal optimum path algorithm for multimodal networks with dynamic arc travel times and switching delays," European Journal of Operational Research, Elsevier, vol. 125(3), pages 486-502, September.
    9. 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.
    10. Zhao, Chunxue & Fu, Baibai & Wang, Tianming, 2014. "Braess paradox and robustness of traffic networks under stochastic user equilibrium," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 61(C), pages 135-141.
    11. Ran, Bin & Hall, Randolph & Boyce, David E., 1995. "A Link-Based Variational Inequality Model for Dynamic Departure Time/Route Choice," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt84t190b3, Institute of Transportation Studies, UC Berkeley.
    12. Y. Ge & B. Sun & H. Zhang & W. Szeto & Xizhao Zhou, 2015. "A Comparison of Dynamic User Optimal States with Zero, Fixed and Variable Tolerances," Networks and Spatial Economics, Springer, vol. 15(3), pages 583-598, September.
    13. W. Chung & J. Fuller & Y. Wu, 2003. "A New Demand-Supply Decomposition Method for a Class of Economic Equilibrium Models," Computational Economics, Springer;Society for Computational Economics, vol. 21(3), pages 231-243, June.
    14. Xinhua Mao & Jianwei Wang & Changwei Yuan & Wei Yu & Jiahua Gan, 2018. "A Dynamic Traffic Assignment Model for the Sustainability of Pavement Performance," Sustainability, MDPI, vol. 11(1), pages 1-19, December.
    15. Arash Kaviani & Russell G. Thompson & Abbas Rajabifard & Majid Sarvi, 2020. "A model for multi-class road network recovery scheduling of regional road networks," Transportation, Springer, vol. 47(1), pages 109-143, February.
    16. Bellei, Giuseppe & Gentile, Guido & Papola, Natale, 2005. "A within-day dynamic traffic assignment model for urban road networks," Transportation Research Part B: Methodological, Elsevier, vol. 39(1), pages 1-29, January.
    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. Paipuri, Mahendra & Leclercq, Ludovic, 2020. "Bi-modal macroscopic traffic dynamics in a single region," Transportation Research Part B: Methodological, Elsevier, vol. 133(C), pages 257-290.
    19. Huang, Hai-Jun & Lam, William H. K., 2002. "Modeling and solving the dynamic user equilibrium route and departure time choice problem in network with queues," Transportation Research Part B: Methodological, Elsevier, vol. 36(3), pages 253-273, March.
    20. Meneguzzer, Claudio, 1995. "An equilibrium route choice model with explicit treatment of the effect of intersections," Transportation Research Part B: Methodological, Elsevier, vol. 29(5), pages 329-356, October.

    More about this item

    Keywords

    ;

    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:cdl:uctcwp:qt2hf4541x. 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: Lisa Schiff (email available below). General contact details of provider: https://edirc.repec.org/data/itucbus.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.