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

The nonlinear equation system approach to solving dynamic user optimal simultaneous route and departure time choice problems

Author

Listed:
  • Long, Jiancheng
  • Szeto, W.Y.
  • Gao, Ziyou
  • Huang, Hai-Jun
  • Shi, Qin

Abstract

Dynamic user optimal simultaneous route and departure time choice (DUO-SRDTC) problems are usually formulated as variational inequality (VI) problems whose solution algorithms generally require continuous and monotone route travel cost functions to guarantee convergence. However, the monotonicity of the route travel cost functions cannot be ensured even if the route travel time functions are monotone. In contrast to traditional formulations, this paper formulates a DUO-SRDTC problem (that can have fixed or elastic demand) as a system of nonlinear equations. The system of nonlinear equations is a function of generalized origin-destination (OD) travel costs rather than route flows and includes a dynamic user optimal (DUO) route choice subproblem with perfectly elastic demand and a quadratic programming (QP) subproblem under certain assumptions. This study also proposes a solution method based on the backtracking inexact Broyden–Fletcher–Goldfarb–Shanno (BFGS) method, the extragradient algorithm, and the Frank-Wolfe algorithm. The BFGS method, the extragradient algorithm, and the Frank-Wolfe algorithm are used to solve the system of nonlinear equations, the DUO route choice subproblem, and the QP subproblem, respectively. The proposed formulation and solution method can avoid the requirement of monotonicity of the route travel cost functions to obtain a convergent solution and provide a new approach with which to solve DUO-SRDTC problems. Finally, numeric examples are used to demonstrate the performance of the proposed solution method.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:transb:v:83:y:2016:i:c:p:179-206
    DOI: 10.1016/j.trb.2015.11.005
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261515002362
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2015.11.005?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
    ---><---

    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. Fukushima, Masao, 1984. "On the dual approach to the traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 18(3), pages 235-245, June.
    2. 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.
    3. Salop, Steven C & Scheffman, David T, 1983. "Raising Rivals' Costs," American Economic Review, American Economic Association, vol. 73(2), pages 267-271, May.
    4. Li-Jun Tian & Hai-Jun Huang & Zi-You Gao, 2012. "A Cumulative Perceived Value-Based Dynamic User Equilibrium Model Considering the Travelers’ Risk Evaluation on Arrival Time," Networks and Spatial Economics, Springer, vol. 12(4), pages 589-608, December.
    5. 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.
    6. Newell, G. F., 1993. "A simplified theory of kinematic waves in highway traffic, part III: Multi-destination flows," Transportation Research Part B: Methodological, Elsevier, vol. 27(4), pages 305-313, August.
    7. Han, Ke & Friesz, Terry L. & Yao, Tao, 2013. "A partial differential equation formulation of Vickrey’s bottleneck model, part I: Methodology and theoretical analysis," Transportation Research Part B: Methodological, Elsevier, vol. 49(C), pages 55-74.
    8. Carlos F. Daganzo, 1998. "Queue Spillovers in Transportation Networks with a Route Choice," Transportation Science, INFORMS, vol. 32(1), pages 3-11, February.
    9. 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.
    10. 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.
    11. 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.
    12. Nie, Yu (Marco), 2011. "A cell-based Merchant-Nemhauser model for the system optimum dynamic traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 45(2), pages 329-342, February.
    13. Malachy Carey, 1987. "Optimal Time-Varying Flows on Congested Networks," Operations Research, INFORMS, vol. 35(1), pages 58-69, February.
    14. Han, Ke & Szeto, W.Y. & Friesz, Terry L., 2015. "Formulation, existence, and computation of boundedly rational dynamic user equilibrium with fixed or endogenous user tolerance," Transportation Research Part B: Methodological, Elsevier, vol. 79(C), pages 16-49.
    15. Arnott, R. & de Palma, A. & Lindsey, R., 1990. "Departure time and route choice for the morning commute," Transportation Research Part B: Methodological, Elsevier, vol. 24(3), pages 209-228, June.
    16. Chow, Andy H.F., 2009. "Properties of system optimal traffic assignment with departure time choice and its solution method," Transportation Research Part B: Methodological, Elsevier, vol. 43(3), pages 325-344, March.
    17. 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.
    18. Chris Hendrickson & George Kocur, 1981. "Schedule Delay and Departure Time Decisions in a Deterministic Model," Transportation Science, INFORMS, vol. 15(1), pages 62-77, February.
    19. Long, Jiancheng & Gao, Ziyou & Szeto, W.Y., 2011. "Discretised link travel time models based on cumulative flows: Formulations and properties," Transportation Research Part B: Methodological, Elsevier, vol. 45(1), pages 232-254, January.
    20. Doan, Kien & Ukkusuri, Satish V., 2012. "On the holding-back problem in the cell transmission based dynamic traffic assignment models," Transportation Research Part B: Methodological, Elsevier, vol. 46(9), pages 1218-1238.
    21. 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.
    22. 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.
    23. Carey, Malachy & Watling, David, 2012. "Dynamic traffic assignment approximating the kinematic wave model: System optimum, marginal costs, externalities and tolls," Transportation Research Part B: Methodological, Elsevier, vol. 46(5), pages 634-648.
    24. 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.
    25. 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.
    26. Vickrey, William S, 1969. "Congestion Theory and Transport Investment," American Economic Review, American Economic Association, vol. 59(2), pages 251-260, May.
    27. Carey, Malachy & Subrahmanian, Eswaran, 2000. "An approach to modelling time-varying flows on congested networks," Transportation Research Part B: Methodological, Elsevier, vol. 34(3), pages 157-183, April.
    28. Small, Kenneth A, 1982. "The Scheduling of Consumer Activities: Work Trips," American Economic Review, American Economic Association, vol. 72(3), pages 467-479, June.
    29. 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.
    30. Yang, Hai & Meng, Qiang, 1998. "Departure time, route choice and congestion toll in a queuing network with elastic demand," Transportation Research Part B: Methodological, Elsevier, vol. 32(4), pages 247-260, May.
    31. Carey, Malachy & Subrahmanian, Eswaran, 2000. "Erratum to "An approach to modelling time-varying flows on congested networks" [Transportation Research Part B 34(3) 157-183]," Transportation Research Part B: Methodological, Elsevier, vol. 34(6), pages 547-547, August.
    32. Nie, Yu (Marco), 2010. "Equilibrium analysis of macroscopic traffic oscillations," Transportation Research Part B: Methodological, Elsevier, vol. 44(1), pages 62-72, January.
    33. Robin Lindsey, C. & van den Berg, Vincent A.C. & Verhoef, Erik T., 2012. "Step tolling with bottleneck queuing congestion," Journal of Urban Economics, Elsevier, vol. 72(1), pages 46-59.
    34. Athanasios K. Ziliaskopoulos, 2000. "A Linear Programming Model for the Single Destination System Optimum Dynamic Traffic Assignment Problem," Transportation Science, INFORMS, vol. 34(1), pages 37-49, February.
    35. Mounce, Richard & Carey, Malachy, 2011. "Route swapping in dynamic traffic networks," Transportation Research Part B: Methodological, Elsevier, vol. 45(1), pages 102-111, January.
    36. 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.
    37. Han, Ke & Friesz, Terry L. & Yao, Tao, 2013. "A partial differential equation formulation of Vickrey’s bottleneck model, part II: Numerical analysis and computation," Transportation Research Part B: Methodological, Elsevier, vol. 49(C), pages 75-93.
    38. Papageorgiou, Markos, 1990. "Dynamic modeling, assignment, and route guidance in traffic networks," Transportation Research Part B: Methodological, Elsevier, vol. 24(6), pages 471-495, December.
    39. Chen, H. K. & Chang, M. S. & Wang, C. Y., 2001. "Dynamic capacitated user-optimal departure time/route choice problem with time-window," European Journal of Operational Research, Elsevier, vol. 132(3), pages 603-618, August.
    40. Ng, ManWo & Waller, S. Travis, 2010. "Reliable evacuation planning via demand inflation and supply deflation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(6), pages 1086-1094, November.
    41. 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.
    42. 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.
    43. 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.
    44. Jin-Su Mun, 2011. "A solution algorithm for a dynamic deterministic user equilibrium assignment model with departure time choice," Transportation Planning and Technology, Taylor & Francis Journals, vol. 34(5), pages 443-466, July.
    45. Han, Ke & Friesz, Terry L. & Yao, Tao, 2013. "Existence of simultaneous route and departure choice dynamic user equilibrium," Transportation Research Part B: Methodological, Elsevier, vol. 53(C), pages 17-30.
    46. 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.
    47. 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.
    48. 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).
    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. Crawford, F. & Watling, D.P. & Connors, R.D., 2017. "A statistical method for estimating predictable differences between daily traffic flow profiles," Transportation Research Part B: Methodological, Elsevier, vol. 95(C), pages 196-213.
    2. Qixiu Cheng & Zhiyuan Liu & Feifei Liu & Ruo Jia, 2017. "Urban dynamic congestion pricing: an overview and emerging research needs," International Journal of Urban Sciences, Taylor & Francis Journals, vol. 21(0), pages 3-18, August.
    3. Jiancheng Long & Wai Yuen Szeto, 2019. "Link-Based System Optimum Dynamic Traffic Assignment Problems in General Networks," Operations Research, INFORMS, vol. 67(1), pages 167-182, January.
    4. 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.
    5. Ren-Yong Guo & Hai Yang & Hai-Jun Huang, 2018. "Are We Really Solving the Dynamic Traffic Equilibrium Problem with a Departure Time Choice?," Transportation Science, INFORMS, vol. 52(3), pages 603-620, June.
    6. Wang, Dong & Liao, Feixiong & Gao, Ziyou & Rasouli, Soora & Huang, Hai-Jun, 2020. "Tolerance-based column generation for boundedly rational dynamic activity-travel assignment in large-scale networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 141(C).
    7. Wang, Dong & Liao, Feixiong & Gao, Ziyou & Timmermans, Harry, 2019. "Tolerance-based strategies for extending the column generation algorithm to the bounded rational dynamic user equilibrium problem," Transportation Research Part B: Methodological, Elsevier, vol. 119(C), pages 102-121.
    8. Zhi-Yang Lin & S. C. Wong & Peng Zhang & Keechoo Choi, 2018. "A Predictive Continuum Dynamic User-Optimal Model for the Simultaneous Departure Time and Route Choice Problem in a Polycentric City," Service Science, INFORMS, vol. 52(6), pages 1496-1508, December.
    9. Long, Jiancheng & Szeto, W.Y., 2019. "Congestion and environmental toll schemes for the morning commute with heterogeneous users and parallel routes," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 305-333.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Jiancheng Long & Wai Yuen Szeto, 2019. "Link-Based System Optimum Dynamic Traffic Assignment Problems in General Networks," Operations Research, INFORMS, vol. 67(1), pages 167-182, January.
    9. 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.
    10. Han, Ke & Szeto, W.Y. & Friesz, Terry L., 2015. "Formulation, existence, and computation of boundedly rational dynamic user equilibrium with fixed or endogenous user tolerance," Transportation Research Part B: Methodological, Elsevier, vol. 79(C), pages 16-49.
    11. 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.
    12. Song, Wenjing & Han, Ke & Wang, Yiou & Friesz, Terry L. & del Castillo, Enrique, 2018. "Statistical metamodeling of dynamic network loading," Transportation Research Part B: Methodological, Elsevier, vol. 117(PB), pages 740-756.
    13. 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.
    14. Qixiu Cheng & Zhiyuan Liu & Feifei Liu & Ruo Jia, 2017. "Urban dynamic congestion pricing: an overview and emerging research needs," International Journal of Urban Sciences, Taylor & Francis Journals, vol. 21(0), pages 3-18, August.
    15. Zhi-Yang Lin & S. C. Wong & Peng Zhang & Keechoo Choi, 2018. "A Predictive Continuum Dynamic User-Optimal Model for the Simultaneous Departure Time and Route Choice Problem in a Polycentric City," Service Science, INFORMS, vol. 52(6), pages 1496-1508, December.
    16. Ren-Yong Guo & Hai Yang & Hai-Jun Huang, 2018. "Are We Really Solving the Dynamic Traffic Equilibrium Problem with a Departure Time Choice?," Transportation Science, INFORMS, vol. 52(3), pages 603-620, June.
    17. Nie, Yu (Marco), 2011. "A cell-based Merchant-Nemhauser model for the system optimum dynamic traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 45(2), pages 329-342, February.
    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. Friesz, Terry L. & Han, Ke & Bagherzadeh, Amir, 2021. "Convergence of fixed-point algorithms for elastic demand dynamic user equilibrium," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 336-352.
    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:83:y:2016:i:c:p:179-206. 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.