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

An Efficient Algorithm for Dynamic Traffic Equilibrium Assignment with Queues

Author

Listed:
  • Takashi Akamatsu

    (Graduate School of Information Sciences, Tohoku University, Sendai, Miyagi 980-8579, Japan)

Abstract

This paper presents an efficient algorithm for solving the dynamic user equilibrium (DUE) traffic assignment with a one-to-many origin-destination (OD) pattern. To achieve the efficiency of the algorithm, we employ the following three strategies. First, we exploit the decomposition property of the DUE assignment with respect to the departure time from an origin; we consider the algorithm that solves each of the decomposed DUE assignments sequentially. Second, we represent the decomposed DUE assignment by an arc-node formulation, not by using path variables. Third, we take advantage of the fact that the decomposed DUE assignment reduces to (finite dimensional) nonlinear complementarity problems (NCPs); we develop the algorithm based on the globally convergent Newton's method for general NCPs. These strategies, together with graph theoretic devices, enable us to design a new algorithm which does not require path enumeration and is capable of dealing with very large-scale networks. Numerical experiments disclose that the proposed algorithm solves the DUE assignment very rapidly, even in large-scale networks with some thousands of links and nodes where conventional heuristic algorithms do not converge to the accurate equilibrium solution.

Suggested Citation

  • Takashi Akamatsu, 2001. "An Efficient Algorithm for Dynamic Traffic Equilibrium Assignment with Queues," Transportation Science, INFORMS, vol. 35(4), pages 389-404, November.
    • Handle: RePEc:inm:ortrsc:v:35:y:2001:i:4:p:389-404
    DOI: 10.1287/trsc.35.4.389.10435
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.35.4.389.10435
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.35.4.389.10435?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. Lawphongpanich, Siriphong & Hearn, Donald W., 1984. "Simplical decomposition of the asymmetric traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 18(2), pages 123-133, April.
    2. Stephen M. Robinson, 1980. "Strongly Regular Generalized Equations," Mathematics of Operations Research, INFORMS, vol. 5(1), pages 43-62, February.
    3. Akamatsu, Takashi, 2000. "A dynamic traffic equilibrium assignment paradox," Transportation Research Part B: Methodological, Elsevier, vol. 34(6), pages 515-531, August.
    4. Smith, M. J., 1993. "A new dynamic traffic model and the existence and calculation of dynamic user equilibria on congested capacity-constrained road networks," Transportation Research Part B: Methodological, Elsevier, vol. 27(1), pages 49-63, February.
    5. Kuwahara, Masao & Akamatsu, Takashi, 2001. "Dynamic user optimal assignment with physical queues for a many-to-many OD pattern," Transportation Research Part B: Methodological, Elsevier, vol. 35(5), pages 461-479, June.
    6. 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.
    7. 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.
    8. Byung-Wook Wie & Roger L. Tobin & Terry L. Friesz & David Bernstein, 1995. "A Discrete Time, Nested Cost Operator Approach to the Dynamic Network User Equilibrium Problem," Transportation Science, INFORMS, vol. 29(1), pages 79-92, February.
    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. Akamatsu, Takashi & Wada, Kentaro & Hayashi, Shunsuke, 2015. "The corridor problem with discrete multiple bottlenecks," Transportation Research Part B: Methodological, Elsevier, vol. 81(P3), pages 808-829.
    2. Iryo, Takamasa, 2011. "Multiple equilibria in a dynamic traffic network," Transportation Research Part B: Methodological, Elsevier, vol. 45(6), pages 867-879, July.
    3. Ban, Xuegang (Jeff) & Pang, Jong-Shi & Liu, Henry X. & Ma, Rui, 2012. "Continuous-time point-queue models in dynamic network loading," Transportation Research Part B: Methodological, Elsevier, vol. 46(3), pages 360-380.
    4. Satsukawa, Koki & Wada, Kentaro & Iryo, Takamasa, 2020. "Reprint of “Stochastic stability of dynamic user equilibrium in unidirectional networks: Weakly acyclic game approach”," Transportation Research Part B: Methodological, Elsevier, vol. 132(C), pages 117-135.
    5. Wada, Kentaro & Satsukawa, Koki & Smith, Mike & Akamatsu, Takashi, 2019. "Network throughput under dynamic user equilibrium: Queue spillback, paradox and traffic control," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 391-413.
    6. Satsukawa, Koki & Wada, Kentaro & Iryo, Takamasa, 2019. "Stochastic stability of dynamic user equilibrium in unidirectional networks: Weakly acyclic game approach," Transportation Research Part B: Methodological, Elsevier, vol. 125(C), pages 229-247.
    7. Iryo, Takamasa & Smith, Michael J., 2018. "On the uniqueness of equilibrated dynamic traffic flow patterns in unidirectional networks," Transportation Research Part B: Methodological, Elsevier, vol. 117(PB), pages 757-773.
    8. Wada, Kentaro & Akamatsu, Takashi, 2013. "A hybrid implementation mechanism of tradable network permits system which obviates path enumeration: An auction mechanism with day-to-day capacity control," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 60(C), pages 94-112.
    9. Takashi Akamatsu & Benjamin Heydecker, 2003. "Detecting Dynamic Traffic Assignment Capacity Paradoxes in Saturated Networks," Transportation Science, INFORMS, vol. 37(2), pages 123-138, May.
    10. Ban, Xuegang (Jeff) & Liu, Henry X. & Ferris, Michael C. & Ran, Bin, 2008. "A link-node complementarity model and solution algorithm for dynamic user equilibria with exact flow propagations," Transportation Research Part B: Methodological, Elsevier, vol. 42(9), pages 823-842, November.

    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. Yuan, Yun & Yu, Jie, 2018. "Locating transit hubs in a multi-modal transportation network: A cluster-based optimization approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 85-103.
    2. 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.
    3. Jang, Wonjae & Ran, Bin & Choi, Keechoo, 2005. "A discrete time dynamic flow model and a formulation and solution method for dynamic route choice," Transportation Research Part B: Methodological, Elsevier, vol. 39(7), pages 593-620, August.
    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. 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.
    6. Wada, Kentaro & Satsukawa, Koki & Smith, Mike & Akamatsu, Takashi, 2019. "Network throughput under dynamic user equilibrium: Queue spillback, paradox and traffic control," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 391-413.
    7. Lu, Gongyuan & Nie, Yu(Marco) & Liu, Xiaobo & Li, Denghui, 2019. "Trajectory-based traffic management inside an autonomous vehicle zone," Transportation Research Part B: Methodological, Elsevier, vol. 120(C), pages 76-98.
    8. Zhen Qian & H. Zhang, 2013. "A Hybrid Route Choice Model for Dynamic Traffic Assignment," Networks and Spatial Economics, Springer, vol. 13(2), pages 183-203, June.
    9. 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.
    10. Lu, Chung-Cheng & Mahmassani, Hani S. & Zhou, Xuesong, 2009. "Equivalent gap function-based reformulation and solution algorithm for the dynamic user equilibrium problem," Transportation Research Part B: Methodological, Elsevier, vol. 43(3), pages 345-364, March.
    11. 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.
    12. Daoli Zhu & Patrice Marcotte, 2000. "On the Existence of Solutions to the Dynamic User Equilibrium Problem," Transportation Science, INFORMS, vol. 34(4), pages 402-414, November.
    13. Takashi Akamatsu & Benjamin Heydecker, 2003. "Detecting Dynamic Traffic Assignment Capacity Paradoxes in Saturated Networks," Transportation Science, INFORMS, vol. 37(2), pages 123-138, May.
    14. Xie, Chi & Liu, Zugang, 2014. "On the stochastic network equilibrium with heterogeneous choice inertia," Transportation Research Part B: Methodological, Elsevier, vol. 66(C), pages 90-109.
    15. Han, Sangjin, 2007. "A route-based solution algorithm for dynamic user equilibrium assignments," Transportation Research Part B: Methodological, Elsevier, vol. 41(10), pages 1094-1113, December.
    16. Damberg, Olof & Lundgren, Jan T. & Patriksson, Michael, 1996. "An algorithm for the stochastic user equilibrium problem," Transportation Research Part B: Methodological, Elsevier, vol. 30(2), pages 115-131, April.
    17. Hillel Bar-Gera, 2002. "Origin-Based Algorithm for the Traffic Assignment Problem," Transportation Science, INFORMS, vol. 36(4), pages 398-417, November.
    18. Michael Patriksson & R. Tyrrell Rockafellar, 2002. "A Mathematical Model and Descent Algorithm for Bilevel Traffic Management," Transportation Science, INFORMS, vol. 36(3), pages 271-291, August.
    19. A. Karakitsiou & A. Migdalas, 2016. "Convex optimization problems in supply chain planning and their solution by a column generation method based on the Frank Wolfe method," Operational Research, Springer, vol. 16(3), pages 401-421, October.
    20. Iryo, Takamasa, 2011. "Multiple equilibria in a dynamic traffic network," Transportation Research Part B: Methodological, Elsevier, vol. 45(6), pages 867-879, July.

    More about this item

    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:inm:ortrsc:v:35:y:2001:i:4:p:389-404. 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.