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. 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.
    3. 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.
    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. Wu, J. H. & Chen, Y. & Florian, M., 1998. "The continuous dynamic network loading problem: a mathematical formulation and solution method," Transportation Research Part B: Methodological, Elsevier, vol. 32(3), pages 173-187, April.
    9. Andrew Ensor & Felipe Lillo, 2016. "Colored-Edge Graph Approach for the Modeling of Multimodal Transportation Systems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(01), pages 1-21, February.
    10. 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.
    11. Gemma, A. & Mannini, L. & Busillo, V. & Cipriani, E. & Crisalli, U., 2022. "Case studies of integration between activity-based demand models and multimodal assignment," Research in Transportation Economics, Elsevier, vol. 92(C).
    12. 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.
    13. Tampère, Chris M.J. & Corthout, Ruben & Cattrysse, Dirk & Immers, Lambertus H., 2011. "A generic class of first order node models for dynamic macroscopic simulation of traffic flows," Transportation Research Part B: Methodological, Elsevier, vol. 45(1), pages 289-309, January.
    14. 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.
    15. 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.
    16. 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.
    17. Chen, Yuh-Wen & Tzeng, Gwo-Hshiung, 2001. "Using fuzzy integral for evaluating subjectively perceived travel costs in a traffic assignment model," European Journal of Operational Research, Elsevier, vol. 130(3), pages 653-664, May.
    18. 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.
    19. Liu, Yang & Nie, Yu (Marco) & Hall, Jonathan, 2015. "A semi-analytical approach for solving the bottleneck model with general user heterogeneity," Transportation Research Part B: Methodological, Elsevier, vol. 71(C), pages 56-70.
    20. Carey, Malachy & Humphreys, Paul & McHugh, Marie & McIvor, Ronan, 2014. "Extending travel-time based models for dynamic network loading and assignment, to achieve adherence to first-in-first-out and link capacities," Transportation Research Part B: Methodological, Elsevier, vol. 65(C), pages 90-104.

    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.