The Piecewise Constant/Linear Solution for Dynamic User Equilibrium

Bliemer MCJ, Raadsen MPH (2019) Continuous-time general link transmission model with simplified fanning, Part I: Theory and link model formulation. Trans Res Part B-Meth 126:442–470. https://doi.org/10.1016/j.trb.2018.01.001, http://www.sciencedirect.com/science/article/pii/S0191261517301479 Corthout R, Himpe W, Viti F, Frederix R, Tampère CM (2014) Improving the efficiency of repeated dynamic network loading through marginal simulation. Transp Res Part C Emerg Technol 41:90–109. https://doi.org/10.1016/j.trc.2013.12.009, https://linkinghub.elsevier.com/retrieve/pii/S0968090X1300274X Daganzo CF (1994) The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory. Transp Res Part B-Meth 28(4):269–287. https://doi.org/10.1016/0191-2615(94)90002-7, http://linkinghub.elsevier.com/retrieve/pii/0191261594900027 Daganzo CF (1995) The cell transmission model, part II: Network traffic. Transp Res Part B-Meth 29(2):79–93. https://doi.org/10.1016/0191-2615(94)00022-R, http://linkinghub.elsevier.com/retrieve/pii/019126159400022R Dean BC (2004) Shortest paths in FIFO time-dependent networks: Theory and algorithms. Rapport technique, Massachusetts Institute of Technology Dehne F, Omran MT, Sack JR (2012) Shortest paths in time-dependent FIFO networks. Algorithmica 62(1-2):416–435. https://doi.org/10.1007/s00453-010-9461-6, http://link.springer.com/10.1007/s00453-010-9461-6 Ding B, Yu JX, Qin L (2008) Finding time-dependent shortest paths over large graphs. In: Proceedings of the 11th international conference on Extending database technology: Advances in database technology, ACM Press, p 205, https://doi.org/10.1145/1353343.1353371, http://portal.acm.org/citation.cfm?doid=1353343.1353371 Facchinei F, Pang JS (eds) (2004) Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer Series in Operations Research and Financial Engineering, Springer New York, New York, NY. https://doi.org/10.1007/b97543, http://link.springer.com/10.1007/b97543 Foschini L, Hershberger J, Suri S (2014) On the Complexity of Time-Dependent Shortest Paths. Algorithmica 68(4):1075–1097. https://doi.org/10.1007/s00453-012-9714-7, https://link.springer.com/article/10.1007/s00453-012-9714-7 Friesz TL, Han K (2019) The mathematical foundations of dynamic user equilibrium. Transp Res Part B-Meth 126:309–328. https://doi.org/10.1016/j.trb.2018.08.015, https://www.sciencedirect.com/science/article/pii/S0191261517301960 Friesz TL, Bernstein D, Smith TE, Tobin RL, Wie BW (1993) A variational inequality formulation of the dynamic network user equilibrium problem. Oper Res 41(1):179–191 Friesz TL, Kim T, Kwon C, Rigdon MA (2011) Approximate network loading and dual-time-scale dynamic user equilibrium. Trans Res Part B-Meth 45(1):176–207 Geisberger R (2010) Engineering Time-dependent One-To-All Computation. http://arxiv.org/abs/1010.0809 Geisberger R, Sanders P (2010) Engineering time-dependent many-to-many shortest paths computation. In: OASIcs-OpenAccess Series in Informatics, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, vol 14 Gentile G (2015) Using the general link transmission model in a dynamic traffic assignment to simulate congestion on urban networks. Trans Res Procedia 5:66–81. https://doi.org/10.1016/j.trpro.2015.01.011, http://linkinghub.elsevier.com/retrieve/pii/S2352146515000125 Gentile G (2016) Solving a dynamic user equilibrium model based on splitting rates with gradient projection algorithms. Transp Res Part B-Meth 92:120–147. https://doi.org/10.1016/j.trb.2016.02.005, http://linkinghub.elsevier.com/retrieve/pii/S0191261516000370 Han D, Lo HK (2004) Solving non-additive traffic assignment problems: A descent method for co-coercive variational inequalities. Eur J Oper Res 159(3):529–544. https://doi.org/10.1016/S0377-2217(03)00423-5, https://linkinghub.elsevier.com/retrieve/pii/S0377221703004235 Han K, Friesz TL, Szeto WY, Liu H (2015a) Elastic demand dynamic network user equilibrium: Formulation, existence and computation. Transp Res Part B-Meth 81:183–209 Han K, Szeto W, Friesz TL (2015b) Formulation, existence, and computation of boundedly rational dynamic user equilibrium with fixed or endogenous user tolerance. Transp Res Part B-Meth 79:16–49 Han K, Piccoli B, Friesz TL (2016) Continuity of the path delay operator for dynamic network loading with spillback. Transp Res Part B-Meth 92:211–233. https://doi.org/10.1016/j.trb.2015.09.009, http://linkinghub.elsevier.com/retrieve/pii/S0191261515002039 Han K, Eve G, Friesz TL (2019) Computing dynamic user equilibria on large-scale networks with software implementation. Netw Spatial Econ 19(3):869–902 Himpe W (2016) Integrated algorithms for repeated dynamic traffic assignments. PhD thesis, KU Leuven, Leuven. https://www.mech.kuleuven.be/en/cib/traffic/downloads/PhDtextWilemHimpe Himpe W, Corthout R, Tampére MC (2016) An efficient iterative link transmission model. Transp Res Part B-Meth 92:170–190. https://doi.org/10.1016/j.trb.2015.12.013, https://linkinghub.elsevier.com/retrieve/pii/S0191261515002805 Hoogendoorn SP, Bovy PHL (2001) State-of-the-art of vehicular traffic flow modelling 215:21 Huang HJ, Lam WH (2002) Modeling and solving the dynamic user equilibrium route and departure time choice problem in network with queues. Transp Res Part B-Meth 36(3), 253–273 Jang W, Ran B, Choi K (2005) A discrete time dynamic flow model and a formulation and solution method for dynamic route choice. Transp Res Part B-Meth 39(7):593–620. https://doi.org/10.1016/j.trb.2004.07.005, http://linkinghub.elsevier.com/retrieve/pii/S0191261504001043 Kolovský F, Ježek J, Kolingerová I (2019a) The e-approximation of the time-dependent shortest path problem solution for all departure times. ISPRS Int J Geo-Inform 8(12):538. https://doi.org/10.3390/ijgi8120538, https://www.mdpi.com/2220-9964/8/12/538, number: 12 Publisher: Multidisciplinary Digital Publishing Institute Kolovský F, Kolingerová I, Ježek J (2019b) Algorithms in transportation: The State of the Art and Concept of PhD Thesis. https://kolovsky.cz/static/teze_final_web.pdf Konno H, Kuno T (1988) Best piecewise constant approximation of a function of single variable. Oper Res Lett 7(4):205–210. https://doi.org/10.1016/0167-6377(88)90030-2 http://www.sciencedirect.com/science/article/pii/0167637788900302 Lighthill MJ, Whitham GB (1955) On kinematic waves II. A theory of traffic flow on long crowded roads. Proc R Soc A: Math Phys Eng Sci 229(1178):317–345 Lo HK, Szeto WY (2002) A cell-based variational inequality formulation of the dynamic user optimal assignment problem. Transp Res Part B:Meth 36(5):421–443 Long J, Huang HJ, Gao Z, Szeto WY (2013) An Intersection-Movement-Based Dynamic User Optimal Route Choice Problem. Oper Res 61(5):1134–1147. https://doi.org/10.1287/opre.2013.1202, http://pubsonline.informs.org/doi/abs/10.1287/opre.2013.1202 Nezamuddin N, Boyles SD (2015) A continuous DUE algorithm using the link transmission model. Netw Spatial Econ15(3):465–483. https://doi.org/10.1007/s11067-014-9234-x, https://doi.org/10.1007/s11067-014-9234-x Omran M, Sack JR (2014) Improved approximation for time-dependent shortest paths. In: International Computing and Combinatorics Conference, Springer, pp 453–464 Orda A, Rom R (1990) Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. Journal of the ACM (JACM) 37(3):607–625 Raadsen MPH, Bliemer MCJ (2019) Continuous-time general link transmission model with simplified fanning, Part II: Event-based algorithm for networks. Transp Res Part B-Meth 126:471–501. https://doi.org/10.1016/j.trb.2018.01.003, http://www.sciencedirect.com/science/article/pii/S0191261517301492 Raadsen MPH, Bliemer MCJ, Bell MGH (2016) An efficient and exact event-based algorithm for solving simplified first order dynamic network loading problems in continuous time. Transp Res Part B-Meth 92:191–210. https://doi.org/10.1016/j.trb.2015.08.004, http://www.sciencedirect.com/science/article/pii/S0191261515001794 Ran B, Hall RW, Boyce DE (1996) A link-based variational inequality model for dynamic departure time/route choice. Transp Res Part B-Meth 30(1):31–463. https://doi.org/10.1016/0191-2615(95)00010-0, http://linkinghub.elsevier.com/retrieve/pii/0191261595000100 Richards PI (1956) Shock waves on the highway. Oper Res 4(1):42–51 Song W, Han K, Wang Y, Friesz T, del Castillo E (2017) Statistical metamodeling of dynamic network loading. Transportation Research Procedia 23:263–282. https://doi.org/10.1016/j.trpro.2017.05.016, https://linkinghub.elsevier.com/retrieve/pii/S2352146517302934 Szeto W, Lo HK (2004) A cell-based simultaneous route and departure time choice model with elastic demand. Transp Res Part B-Meth 38(7):593–612. https://doi.org/10.1016/j.trb.2003.05.001, http://linkinghub.elsevier.com/retrieve/pii/S0191261503000924 Szeto WY, Lo HK (2006) Dynamic traffic assignment: properties and extensions. Transportmetrica 2(1):31–52. https://doi.org/10.1080/18128600608685654, http://www.tandfonline.com/doi/abs/10.1080/18128600608685654 Tian LJ, Huang HJ, Gao ZY (2012) A cumulative perceived value-based dynamic user equilibrium model considering the travelers’ risk evaluation on arrival time. Netw Spatial Econ 12(4):589–608. https://doi.org/10.1007/s11067-011-9168-5 , http://link.springer.com/10.1007/s11067-011-9168-5 Transportation Networks for Research Core Team (2021) Transportation networks for research. https://github.com/bstabler/TransportationNetworks, https://github.com/bstabler/TransportationNetworks Ukkusuri SV, Han L, Doan K (2012) Dynamic user equilibrium with a path based cell transmission model for general traffic networks. Transp Res Part B-Meth 46(10):1657–1684. https://doi.org/10.1016/j.trb.2012.07.010, http://linkinghub.elsevier.com/retrieve/pii/S0191261512001038 van der Gun JPT, Pel AJ, van Arem B (2017) Extending the Link Transmission Model with non-triangular fundamental diagrams and capacity drops. Transp Res Part B-Meth 98:154–178. https://doi.org/10.1016/j.trb.2016.12.011, http://www.sciencedirect.com/science/article/pii/S0191261516309572 Wardrop JG (1952) Road paper. some theoretical aspects of road traffic research. Proceed Ins Civil Eng 1(3):325–362 Wu X, Liu HX (2011) A shockwave profile model for traffic flow on congested urban arterials. Transp Res Part B-Meth 45(10):1768–1786. https://doi.org/10.1016/j.trb.2011.07.013, http://www.sciencedirect.com/science/article/pii/S0191261511001135 Yperman I (2007) The Link Transmission Model for Dynamic Network Loading. Katholieke Universiteit Leuven, Belgium