IDEAS home Printed from https://ideas.repec.org/p/cdl/uctcwp/qt2hf4541x.html

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. 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.
    2. 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.
    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. 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.
    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. 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.
    2. Bingfeng Si & Xuedong Yan & Hunjun Sun & Xiaobao Yang & Ziyou Gao, 2012. "Travel Demand‐Based Assignment Model for Multimodal and Multiuser Transportation System," Journal of Applied Mathematics, John Wiley & Sons, vol. 2012(1).
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Max Klimm & Andreas Schütz, 2022. "Equilibria in Multiclass and Multidimensional Atomic Congestion Games," Mathematics of Operations Research, INFORMS, vol. 47(4), pages 2743-2764, November.
    10. Elnaz Miandoabchi & Reza Farahani & W. Szeto, 2012. "Bi-objective bimodal urban road network design using hybrid metaheuristics," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 20(4), pages 583-621, December.
    11. Li, Guoyuan & Chen, Anthony, 2022. "Frequency-based path flow estimator for transit origin-destination trip matrices incorporating automatic passenger count and automatic fare collection data," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 163(C).
    12. Jiancheng Long & Hai-Jun Huang & Ziyou Gao & W. Y. Szeto, 2013. "An Intersection-Movement-Based Dynamic User Optimal Route Choice Problem," Operations Research, INFORMS, vol. 61(5), pages 1134-1147, October.
    13. Sheu, Jiuh-Biing, 2006. "A composite traffic flow modeling approach for incident-responsive network traffic assignment," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 367(C), pages 461-478.
    14. Lam, William H. K. & Huang, Hai-Jun, 1995. "Dynamic user optimal traffic assignment model for many to one travel demand," Transportation Research Part B: Methodological, Elsevier, vol. 29(4), pages 243-259, August.
    15. 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.
    16. Xiang Zhang & David Rey & S. Travis Waller & Nathan Chen, 2019. "Range-Constrained Traffic Assignment with Multi-Modal Recharge for Electric Vehicles," Networks and Spatial Economics, Springer, vol. 19(2), pages 633-668, June.
    17. Lam, William H. K. & Tam, M. L., 1997. "Why standard modelling and evaluation procedures are inadequate for assessing traffic congestion measures," Transport Policy, Elsevier, vol. 4(4), pages 217-223, October.
    18. Ran, Bin & Hall, Randolph W. & Boyce, David E., 1996. "A link-based variational inequality model for dynamic departure time/route choice," Transportation Research Part B: Methodological, Elsevier, vol. 30(1), pages 31-46, February.
    19. 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.
    20. Lukas Graf & Tobias Harks, 2024. "Side-Constrained Dynamic Traffic Equilibria," Operations Research, INFORMS, vol. 72(6), pages 2279-2301, November.

    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: eScholarship, California Digital Library (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.