IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v45y2011i1p176-207.html
   My bibliography  Save this article

Approximate network loading and dual-time-scale dynamic user equilibrium

Author

Listed:
  • Friesz, Terry L.
  • Kim, Taeil
  • Kwon, Changhyun
  • Rigdon, Matthew A.

Abstract

In this paper we present a dual-time-scale formulation of dynamic user equilibrium (DUE) with demand evolution. Our formulation belongs to the problem class that Pang and Stewart (2008) refer to as differential variational inequalities. It combines the within-day time scale for which route and departure time choices fluctuate in continuous time with the day-to-day time scale for which demand evolves in discrete time steps. Our formulation is consistent with the often told story that drivers adjust their travel demands at the end of every day based on their congestion experience during one or more previous days. We show that analysis of the within-day assignment model is tremendously simplified by expressing dynamic user equilibrium as a differential variational inequality. We also show there is a class of day-to-day demand growth models that allow the dual-time-scale formulation to be decomposed by time-stepping to yield a sequence of continuous time, single-day, dynamic user equilibrium problems. To solve the single-day DUE problems arising during time-stepping, it is necessary to repeatedly solve a dynamic network loading problem. We observe that the network loading phase of DUE computation generally constitutes a differential algebraic equation (DAE) system, and we show that the DAE system for network loading based on the link delay model (LDM) of Friesz et al. (1993) may be approximated by a system of ordinary differential equations (ODEs). That system of ODEs, as we demonstrate, may be efficiently solved using traditional numerical methods for such problems. To compute an actual dynamic user equilibrium, we introduce a continuous time fixed-point algorithm and prove its convergence for effective path delay operators that allow a limited type of nonmonotone path delay. We show that our DUE algorithm is compatible with network loading based on the LDM and the cell transmission model (CTM) due to Daganzo (1995). We provide a numerical example based on the much studied Sioux Falls network.

Suggested Citation

  • Friesz, Terry L. & Kim, Taeil & Kwon, Changhyun & Rigdon, Matthew A., 2011. "Approximate network loading and dual-time-scale dynamic user equilibrium," Transportation Research Part B: Methodological, Elsevier, vol. 45(1), pages 176-207, January.
    • Handle: RePEc:eee:transb:v:45:y:2011:i:1:p:176-207
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191-2615(10)00071-8
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Li, Jun & Fujiwara, Okitsugu & Kawakami, Shogo, 2000. "A reactive dynamic user equilibrium model in network with queues," Transportation Research Part B: Methodological, Elsevier, vol. 34(8), pages 605-624, November.
    2. 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.
    3. Friesz, Terry L. & Mookherjee, Reetabrata, 2006. "Solving the dynamic network user equilibrium problem with state-dependent time shifts," Transportation Research Part B: Methodological, Elsevier, vol. 40(3), pages 207-229, March.
    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. Malachy Carey, 1987. "Optimal Time-Varying Flows on Congested Networks," Operations Research, INFORMS, vol. 35(1), pages 58-69, February.
    6. Yu (Marco) Nie & H. Michael Zhang, 2008. "Oscillatory Traffic Flow Patterns Induced by Queue Spillback in a Simple Road Network," Transportation Science, INFORMS, vol. 42(2), pages 236-248, May.
    7. Terry L. Friesz, 2010. "Dynamic Optimization and Differential Games," International Series in Operations Research and Management Science, Springer, number 978-0-387-72778-3, September.
    8. Terry L. Friesz & Javier Luque & Roger L. Tobin & Byung-Wook Wie, 1989. "Dynamic Network Traffic Assignment Considered as a Continuous Time Optimal Control Problem," Operations Research, INFORMS, vol. 37(6), pages 893-901, December.
    9. 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.
    10. Carey, Malachy, 1992. "Nonconvexity of the dynamic traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 26(2), pages 127-133, April.
    11. Paul I. Richards, 1956. "Shock Waves on the Highway," Operations Research, INFORMS, vol. 4(1), pages 42-51, February.
    12. Nie, Yu (Marco) & Zhang, H.M., 2008. "A variational inequality formulation for inferring dynamic origin-destination travel demands," Transportation Research Part B: Methodological, Elsevier, vol. 42(7-8), pages 635-662, August.
    13. Terry L. Friesz & David Bernstein & Tony E. Smith & Roger L. Tobin & B. W. Wie, 1993. "A Variational Inequality Formulation of the Dynamic Network User Equilibrium Problem," Operations Research, INFORMS, vol. 41(1), pages 179-191, February.
    14. MERCHANT, Deepak K. & NEMHAUSER, George L., 1978. "A model and an algorithm for the dynamic traffic assignment problems," LIDAM Reprints CORE 346, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    15. 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.
    16. Yu Nie & H. Zhang, 2010. "Solving the Dynamic User Optimal Assignment Problem Considering Queue Spillback," Networks and Spatial Economics, Springer, vol. 10(1), pages 49-71, March.
    17. MERCHANT, Deepak K. & NEMHAUSER, George L., 1978. "Optimality conditions for a dynamic traffic assignment model," LIDAM Reprints CORE 345, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    18. Georgia Perakis & Guillaume Roels, 2006. "An Analytical Model for Traffic Delays and the Dynamic User Equilibrium Problem," Operations Research, INFORMS, vol. 54(6), pages 1151-1171, December.
    19. Deepak K. Merchant & George L. Nemhauser, 1978. "Optimality Conditions for a Dynamic Traffic Assignment Model," Transportation Science, INFORMS, vol. 12(3), pages 200-207, August.
    20. Bliemer, Michiel C. J. & Bovy, Piet H. L., 2003. "Quasi-variational inequality formulation of the multiclass dynamic traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 37(6), pages 501-519, July.
    21. Lo, Hong K. & Szeto, W. Y., 2002. "A cell-based variational inequality formulation of the dynamic user optimal assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 36(5), pages 421-443, June.
    22. Tong, C. O. & Wong, S. C., 2000. "A predictive dynamic traffic assignment model in congested capacity-constrained road networks," Transportation Research Part B: Methodological, Elsevier, vol. 34(8), pages 625-644, November.
    23. Daganzo, Carlos F., 1995. "The cell transmission model, part II: Network traffic," Transportation Research Part B: Methodological, Elsevier, vol. 29(2), pages 79-93, April.
    24. Nie, Yu (Marco), 2010. "Equilibrium analysis of macroscopic traffic oscillations," Transportation Research Part B: Methodological, Elsevier, vol. 44(1), pages 62-72, January.
    25. 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.
    26. Larry Samuelson, 1998. "Evolutionary Games and Equilibrium Selection," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262692198, December.
    27. N. El Farouq, 2001. "Pseudomonotone Variational Inequalities: Convergence of Proximal Methods," Journal of Optimization Theory and Applications, Springer, vol. 109(2), pages 311-326, May.
    28. Szeto, W. Y. & Lo, Hong K., 2004. "A cell-based simultaneous route and departure time choice model with elastic demand," Transportation Research Part B: Methodological, Elsevier, vol. 38(7), pages 593-612, August.
    29. Deepak K. Merchant & George L. Nemhauser, 1978. "A Model and an Algorithm for the Dynamic Traffic Assignment Problems," Transportation Science, INFORMS, vol. 12(3), pages 183-199, August.
    30. 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.
    31. Y. W. Xu & J. H. Wu & M. Florian & P. Marcotte & D. L. Zhu, 1999. "Advances in the Continuous Dynamic Network Loading Problem," Transportation Science, INFORMS, vol. 33(4), pages 341-353, November.
    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. Ke Han & Gabriel Eve & Terry L. Friesz, 2019. "Computing Dynamic User Equilibria on Large-Scale Networks with Software Implementation," Networks and Spatial Economics, Springer, vol. 19(3), pages 869-902, September.
    2. Friesz, Terry L. & Han, Ke & Neto, Pedro A. & Meimand, Amir & Yao, Tao, 2013. "Dynamic user equilibrium based on a hydrodynamic model," Transportation Research Part B: Methodological, Elsevier, vol. 47(C), pages 102-126.
    3. 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.
    4. Long, Jiancheng & Szeto, W.Y. & Gao, Ziyou & Huang, Hai-Jun & Shi, Qin, 2016. "The nonlinear equation system approach to solving dynamic user optimal simultaneous route and departure time choice problems," Transportation Research Part B: Methodological, Elsevier, vol. 83(C), pages 179-206.
    5. Long, Jiancheng & Szeto, W.Y. & Huang, Hai-Jun & Gao, Ziyou, 2015. "An intersection-movement-based stochastic dynamic user optimal route choice model for assessing network performance," Transportation Research Part B: Methodological, Elsevier, vol. 74(C), pages 182-217.
    6. 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.
    7. Han, Ke & Friesz, Terry L. & Szeto, W.Y. & Liu, Hongcheng, 2015. "Elastic demand dynamic network user equilibrium: Formulation, existence and computation," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 183-209.
    8. Ukkusuri, Satish V. & Han, Lanshan & Doan, Kien, 2012. "Dynamic user equilibrium with a path based cell transmission model for general traffic networks," Transportation Research Part B: Methodological, Elsevier, vol. 46(10), pages 1657-1684.
    9. Malachy Carey & Y. Ge, 2012. "Comparison of Methods for Path Flow Reassignment for Dynamic User Equilibrium," Networks and Spatial Economics, Springer, vol. 12(3), pages 337-376, September.
    10. Zhu, Feng & Ukkusuri, Satish V., 2017. "Efficient and fair system states in dynamic transportation networks," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 272-289.
    11. Long, Jiancheng & Wang, Chao & Szeto, W.Y., 2018. "Dynamic system optimum simultaneous route and departure time choice problems: Intersection-movement-based formulations and comparisons," Transportation Research Part B: Methodological, Elsevier, vol. 115(C), pages 166-206.
    12. Rui Ma & Xuegang (Jeff) Ban & Jong-Shi Pang, 2018. "A Link-Based Differential Complementarity System Formulation for Continuous-Time Dynamic User Equilibria with Queue Spillbacks," Transportation Science, INFORMS, vol. 52(3), pages 564-592, June.
    13. Ban, Xuegang (Jeff) & Pang, Jong-Shi & Liu, Henry X. & Ma, Rui, 2012. "Modeling and solving continuous-time instantaneous dynamic user equilibria: A differential complementarity systems approach," Transportation Research Part B: Methodological, Elsevier, vol. 46(3), pages 389-408.
    14. Tong, C. O. & Wong, S. C., 2000. "A predictive dynamic traffic assignment model in congested capacity-constrained road networks," Transportation Research Part B: Methodological, Elsevier, vol. 34(8), pages 625-644, November.
    15. Friesz, Terry L. & Han, Ke, 2019. "The mathematical foundations of dynamic user equilibrium," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 309-328.
    16. Long, Jiancheng & Szeto, W.Y. & Du, Jie & Wong, R.C.P., 2017. "A dynamic taxi traffic assignment model: A two-level continuum transportation system approach," Transportation Research Part B: Methodological, Elsevier, vol. 100(C), pages 222-254.
    17. S. Waller & Athanasios Ziliaskopoulos, 2006. "A Combinatorial user optimal dynamic traffic assignment algorithm," Annals of Operations Research, Springer, vol. 144(1), pages 249-261, April.
    18. 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.
    19. Zhang, Pinchao & Qian, Sean, 2020. "Path-based system optimal dynamic traffic assignment: A subgradient approach," Transportation Research Part B: Methodological, Elsevier, vol. 134(C), pages 41-63.
    20. Zhong, R.X. & Sumalee, A. & Friesz, T.L. & Lam, William H.K., 2011. "Dynamic user equilibrium with side constraints for a traffic network: Theoretical development and numerical solution algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 45(7), pages 1035-1061, August.

    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:eee:transb:v:45:y:2011:i:1:p:176-207. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    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.