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

A link-node complementarity model and solution algorithm for dynamic user equilibria with exact flow propagations

Author

Listed:
  • Ban, Xuegang (Jeff)
  • Liu, Henry X.
  • Ferris, Michael C.
  • Ran, Bin

Abstract

In this paper, we propose a link-node complementarity model for the basic deterministic dynamic user equilibrium (DUE) problem with single-user-class and fixed demands. The model complements link-path formulations that have been widely studied for dynamic user equilibria. Under various dynamic network constraints, especially the exact flow propagation constraints, we show that the continuous-time dynamic user equilibrium problem can be formulated as an infinite dimensional mixed complementarity model. The continuous-time model can be further discretized as a finite dimensional non-linear complementarity problem (NCP). The proposed discrete-time model captures the exact flow propagation constraints that were usually approximated in previous studies. By associating link inflow at the beginning of a time interval to travel times at the end of the interval, the resulting discrete-time model is predictive rather than reactive. The solution existence and compactness condition for the proposed model is established under mild assumptions. The model is solved by an iterative algorithm with a relaxed NCP solved at each iteration. Numerical examples are provided to illustrate the proposed model and solution approach. We particularly show why predictive DUE is preferable to reactive DUE from an algorithmic perspective.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:transb:v:42:y:2008:i:9:p:823-842
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191-2615(08)00015-5
    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. 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.
    2. Malachy Carey, 1987. "Optimal Time-Varying Flows on Congested Networks," Operations Research, INFORMS, vol. 35(1), pages 58-69, February.
    3. Carey, Malachy & McCartney, Mark, 2002. "Behaviour of a whole-link travel time model used in dynamic traffic assignment," Transportation Research Part B: Methodological, Elsevier, vol. 36(1), pages 83-95, January.
    4. Chen, Huey-Kuo & Hsueh, Che-Fu, 1998. "A model and an algorithm for the dynamic user-optimal route choice problem," Transportation Research Part B: Methodological, Elsevier, vol. 32(3), pages 219-234, April.
    5. Han, S. & Heydecker, B.G., 2006. "Consistent objectives and solution of dynamic user equilibrium models," Transportation Research Part B: Methodological, Elsevier, vol. 40(1), pages 16-34, January.
    6. Smith, M. J., 1979. "The existence, uniqueness and stability of traffic equilibria," Transportation Research Part B: Methodological, Elsevier, vol. 13(4), pages 295-304, December.
    7. Daganzo, Carlos F., 1994. "The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory," Transportation Research Part B: Methodological, Elsevier, vol. 28(4), pages 269-287, August.
    8. 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.
    9. 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.
    10. Han, Sangjin, 2003. "Dynamic traffic modelling and dynamic stochastic user equilibrium assignment for general road networks," Transportation Research Part B: Methodological, Elsevier, vol. 37(3), pages 225-249, March.
    11. 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.
    12. Wie, Byung-Wook & Tobin, Roger L. & Carey, Malachy, 2002. "The existence, uniqueness and computation of an arc-based dynamic network user equilibrium formulation," Transportation Research Part B: Methodological, Elsevier, vol. 36(10), pages 897-918, December.
    13. Nie, Xiaojian & Zhang, H.M., 2005. "Delay-function-based link models: their properties and computational issues," Transportation Research Part B: Methodological, Elsevier, vol. 39(8), pages 729-751, September.
    14. Takashi Akamatsu, 2001. "An Efficient Algorithm for Dynamic Traffic Equilibrium Assignment with Queues," Transportation Science, INFORMS, vol. 35(4), pages 389-404, November.
    15. Daganzo, Carlos F., 1995. "Properties of link travel time functions under dynamic loads," Transportation Research Part B: Methodological, Elsevier, vol. 29(2), pages 95-98, April.
    16. Menglin Cao & Michael C. Ferris, 1996. "A Pivotal Method for Affine Variational Inequalities," Mathematics of Operations Research, INFORMS, vol. 21(1), pages 44-64, February.
    17. 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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    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. 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.
    8. Gentile, Guido & Meschini, Lorenzo & Papola, Natale, 2007. "Spillback congestion in dynamic traffic assignment: A macroscopic flow model with time-varying bottlenecks," Transportation Research Part B: Methodological, Elsevier, vol. 41(10), pages 1114-1138, December.
    9. Blumberg, Michal & Bar-Gera, Hillel, 2009. "Consistent node arrival order in dynamic network loading models," Transportation Research Part B: Methodological, Elsevier, vol. 43(3), pages 285-300, March.
    10. Hong Zheng & Yi-Chang Chiu & Pitu B. Mirchandani, 2015. "On the System Optimum Dynamic Traffic Assignment and Earliest Arrival Flow Problems," Transportation Science, INFORMS, vol. 49(1), pages 13-27, February.
    11. 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.
    12. Laval, Jorge A., 2009. "Graphical solution and continuum approximation for the single destination dynamic user equilibrium problem," Transportation Research Part B: Methodological, Elsevier, vol. 43(1), pages 108-118, January.
    13. 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.
    14. 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.
    15. Rui Ma & Xuegang Ban & Jong-Shi Pang & Henry Liu, 2015. "Submission to the DTA2012 Special Issue: Convergence of Time Discretization Schemes for Continuous-Time Dynamic Network Loading Models," Networks and Spatial Economics, Springer, vol. 15(3), pages 419-441, September.
    16. 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.
    17. 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.
    18. 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.
    19. 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.
    20. Huang, Y.P. & Xiong, J.H. & Sumalee, A. & Zheng, N. & Lam, W.H.K. & He, Z.B. & Zhong, R.X., 2020. "A dynamic user equilibrium model for multi-region macroscopic fundamental diagram systems with time-varying delays," Transportation Research Part B: Methodological, Elsevier, vol. 131(C), pages 1-25.

    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:eee:transb:v:42:y:2008:i:9:p:823-842. 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.