1932
0
  1. Home
  2. A-Z Publications
  3. Annual Review of Control, Robotics, and Autonomous Systems
  4. Volume 3, 2020
  5. Article

Annual Review of Control, Robotics, and Autonomous Systems

Volume 3, 2020

Routing on Traffic Networks Incorporating Past Memory up to Real-Time Information on the Network State

Abstract

In this review, we discuss routing algorithms for the dynamic traffic assignment (DTA) problem that assigns traffic flow in a given road network as realistically as possible. We present a new class of so-called routing operators that route traffic flow at intersections based on either real-time information about the status of the network or historical data. These routing operators thus cover the distribution of traffic flow at all possible intersections. To model traffic flow on the links, we use a well-known macroscopic ordinary delay differential equation. We prove the existence and uniqueness of the solutions of the resulting DTA for a broad class of routing operators. This new routing approach is required and justified by the increased usage of real-time information on the network provided by map services, changing the laws of routing significantly. Because these map and routing services have a huge impact on the infrastructure of cities, a more precise mathematical description of the emerging new traffic patterns and effects becomes crucial for understanding and improving road and city conditions.

Keyword(s): dynamic traffic assignment, existence of solutions, ordinary delay differential equations, real-time information, routing in real time, traffic flow, uniqueness of solutions
Loading

Article metrics loading...

/content/journals/10.1146/annurev-control-091319-125444
2020-05-03
2024-05-14
Loading full text...

Full text loading...

/deliver/fulltext/control/3/1/annurev-control-091319-125444.html?itemId=/content/journals/10.1146/annurev-control-091319-125444&mimeType=html&fmt=ahah

Literature Cited

  1. 1. 
    Thai J, Laurent-Brouty N, Bayen AM 2016. Negative externalities of GPS-enabled routing applications: a game theoretical approach. IEEE International Conference on Intelligent Transportation Systems595–601 Piscataway, NJ: IEEE
     [Google Scholar]
  2. 2. 
    Keimer A, Laurent-Brouty N, Farokhi F, Signargout H, Cvetkovic V et al. 2018. Information patterns in the modeling and design of mobility management services. Proc. IEEE 106:554–76
     [Google Scholar]
  3. 3. 
    Cabannes T, Sangiovanni M, Keimer A, Bayen AM 2019. Regrets in routing networks: measuring the impact of routing apps in traffic. ACM Trans. Spat. Algorithms Syst. 5:9
     [Google Scholar]
  4. 4. 
    Cabannes T, Shyu F, Porter E, Yao S, Wang Y et al. 2018. Measuring regret in routing: assessing the impact of increased app usage. 2018 21st International Conference on Intelligent Transportation Systems2589–94 Piscataway, NJ: IEEE
     [Google Scholar]
  5. 5. 
    Cabannes T, Sangiovanni Vincentelli MA, Sundt A, Signargout H, Porter E et al. 2018. The impact of GPS-enabled shortest path routing on mobility: a game theoretic approach Paper presented at the 97th Transportation Research Board Annual Meeting Washington, DC: Jan 7–11
  6. 6. 
    Nash J. 1951. Non-cooperative games. Ann. Math. 54:286–95
     [Google Scholar]
  7. 7. 
    Patriksson M. 2015. The Traffic Assignment Problem: Models and Methods Mineola, NY: Dover
  8. 8. 
    Nie X, Zhang HM. 2005. A comparative study of some macroscopic link models used in dynamic traffic assignment. Netw. Spat. Econ. 5:89–115
     [Google Scholar]
  9. 9. 
    Zhang H. 2001. New perspectives on continuum traffic flow models. Netw. Spat. Econ. 1:9–33
     [Google Scholar]
  10. 10. 
    Hoogendoorn SP, Bovy PHL. 2000. Continuum modeling of multiclass traffic flow. Transp. Res. B 34:123–46
     [Google Scholar]
  11. 11. 
    Merchant D, Nemhauser G. 1978. Optimality conditions for a dynamic traffic assignment model. Transp. Sci. 12:200–7
     [Google Scholar]
  12. 12. 
    Merchant D, Nemhauser G. 1978. A model and an algorithm for the dynamic traffic assignment problems. Transp. Sci. 12:183–99
     [Google Scholar]
  13. 13. 
    Ran B, Boyce D. 1996. Modeling Dynamic Transportation Networks: An Intelligent Transportation System Oriented Approach Berlin: Springer
  14. 14. 
    Jayakrishnan R, Tsai WK, Chen A 1995. A dynamic traffic assignment model with traffic-flow relationships. Transp. Res. C 3:51–72
     [Google Scholar]
  15. 15. 
    Jin WL. 2015. Point queue models: a unified approach. Transp. Res. B 77:1–16
     [Google Scholar]
  16. 16. 
    Ban XJ, Pang JS, Liu HX, Ma R 2012. Continuous-time point-queue models in dynamic network loading. Transp. Res. B 46:360–80
     [Google Scholar]
  17. 17. 
    Ban XJ, Pang JS, Liu HX, Ma R 2012. Modeling and solving continuous-time instantaneous dynamic user equilibria: a differential complementarity systems approach. Transp. Res. B 46:389–408
     [Google Scholar]
  18. 18. 
    Ma R, Ban X, Pang JS 2018. A link-based differential complementarity system formulation for continuous-time dynamic user equilibria with queue spillbacks. Transp. Sci. 52:564–92
     [Google Scholar]
  19. 19. 
    Pang JS, Stewart DE. 2008. Differential variational inequalities. Math. Program. 113:345–424
     [Google Scholar]
  20. 20. 
    Han K, Friesz T, Yao T 2013. A partial differential equation formulation of Vickrey's bottleneck model, part I: methodology and theoretical analysis. Transp. Res. B 49:55–74
     [Google Scholar]
  21. 21. 
    Han K, Friesz T, Yao T 2013. A partial differential equation formulation of Vickrey's bottleneck model, part II: numerical analysis and computation. Transp. Res. B 49:75–93
     [Google Scholar]
  22. 22. 
    Vickrey WS. 1969. Congestion theory and transport investment. Am. Econ. Rev. 59:251–60
     [Google Scholar]
  23. 23. 
    Friesz T, Bernstein D, Smith T, Tobin R, Wie BW 1993. A variational inequality formulation of the dynamic network user equilibrium problem. Oper. Res. 41:179–91
     [Google Scholar]
  24. 24. 
    Ran B, Boyce D, LeBlanc L 1993. A new class of instantaneous dynamic user-optimal traffic assignment models. Oper. Res. 41:192–202
     [Google Scholar]
  25. 25. 
    Nie X, Zhang H. 2005. Delay-function-based link models: their properties and computational issues. Transp. Res. B 39:729–51
     [Google Scholar]
  26. 26. 
    Xu Y, Wu J, Florian M, Marcotte P, Zhu D 1999. Advances in the continuous dynamic network loading problem. Transp. Sci. 33:341–53
     [Google Scholar]
  27. 27. 
    Garavello M, Piccoli B. 2006. Traffic Flow on Networks Springfield, MO: Am. Inst. Math. Sci.
  28. 28. 
    Lighthill MJ, Whitham GB. 1955. On kinematic waves. I. Flood movement in long rivers. Proc. R. Soc. Lond. A 229:281–316
     [Google Scholar]
  29. 29. 
    Richards PI. 1956. Shock waves on the highway. Oper. Res. 4:42–51
     [Google Scholar]
  30. 30. 
    Greenshields BD, Channing W, Miller H 1935. A study of traffic capacity. Highway Research Board Proceedings 14448–77 Washington, DC: Highw. Res. Board
     [Google Scholar]
  31. 31. 
    Lax PD. 1957. Hyperbolic systems of conservation laws II. Commun. Pure Appl. Math. 10:537–66
     [Google Scholar]
  32. 32. 
    Lax PD, Wendroff B. 1960. Systems of conservation laws. Commun. Pure Appl. Math. 13:217–37
     [Google Scholar]
  33. 33. 
    Oleinik O. 1957. Discontinuous solutions of non-linear differential equations. Uspekhi Mat. Nauk 12:3–73
     [Google Scholar]
  34. 34. 
    Azerman M, Bredihina E, Černikov S, Gantmaher F, Gelfand I et al. 1963. Seventeen Papers on Analysis Providence, RI: Am. Math. Soc.
  35. 35. 
    Kružkov SN. 1970. First order quasilinear equations in several independent variables. Math. USSR Sbornik 10:217–43
     [Google Scholar]
  36. 36. 
    Rossi E. 2014. A justification of a LWR model based on a follow the leader description. Discrete Contin. Dyn. Syst. S 7:579–91
     [Google Scholar]
  37. 37. 
    Laval JA, Leclercq L. 2013. The Hamilton–Jacobi partial differential equation and the three representations of traffic flow. Transp. Res. B 52:17–30
     [Google Scholar]
  38. 38. 
    Claudel CG, Bayen AM. 2010. Lax–Hopf based incorporation of internal boundary conditions into Hamilton–Jacobi equation. Part I: theory. IEEE Trans. Autom. Control 55:1142–57
     [Google Scholar]
  39. 39. 
    Joseph KT, Gowda GDV. 1991. Explicit formula for the solution of convex conservation laws with boundary condition. Duke Math. J. 62:401–16
     [Google Scholar]
  40. 40. 
    Joseph KT, Gowda GDV. 1992. Solution of convex conservation laws in a strip. Proc. Indian Acad. Sci. Math. Sci. 102:29–47
     [Google Scholar]
  41. 41. 
    Evans LC. 1997. Partial differential equations and Monge-Kantorovich mass transfer. Curr. Dev. Math. 1997:65–126
     [Google Scholar]
  42. 42. 
    Keimer A, Pflug L. 2017. Existence, uniqueness and regularity results on nonlocal balance laws. J. Differ. Equ. 263:4023–69
     [Google Scholar]
  43. 43. 
    Keimer A, Pflug L, Spinola M 2018. Nonlocal scalar conservation laws on bounded domains and applications in traffic flow. SIAM J. Math. Anal. 50:6271–306
     [Google Scholar]
  44. 44. 
    Blandin S, Goatin P. 2016. Well-posedness of a conservation law with non-local flux arising in traffic flow modeling. Numer. Math. 132:217–41
     [Google Scholar]
  45. 45. 
    Aw A, Rascle M. 2000. Resurrection of “second order” models of traffic flow. SIAM J. Appl. Math. 60:916–38
     [Google Scholar]
  46. 46. 
    Zhang H. 2002. A non-equilibrium traffic model devoid of gas-like behavior. Transp. Res. B 36:275–90
     [Google Scholar]
  47. 47. 
    Fan S, Herty M, Seibold B 2014. Comparative model accuracy of a data-fitted generalized Aw-Rascle-Zhang model. Netw. Heterog. Media 9:239–68
     [Google Scholar]
  48. 48. 
    Lebacque JP, Mammar S, Haj-Salem H 2007. The Aw–Rascle and Zhang's model: vacuum problems, existence and regularity of the solutions of the Riemann problem. Transp. Res. B 41:710–21
     [Google Scholar]
  49. 49. 
    Godvik M, Hanche-Olsen H. 2008. Existence of solutions for the Aw–Rascle traffic flow model with vacuum. J. Hyperbolic Differ. Equ. 05:45–63
     [Google Scholar]
  50. 50. 
    Aw A. 2014. Existence of a global entropic weak solution for the Aw-Rascle model. Int. J. Evol. Equ. 9:53–70
     [Google Scholar]
  51. 51. 
    Ou Z, Dai S, Zhang P, Dong L 2007. Nonlinear analysis in the Aw–Rascle anticipation model of traffic flow. SIAM J. Appl. Math. 67:605–18
     [Google Scholar]
  52. 52. 
    Garavello M, Villa S. 2017. The Cauchy problem for the Aw–Rascle–Zhang traffic model with locally constrained flow. J. Hyperbolic Differ. Equ. 14:393–414
     [Google Scholar]
  53. 53. 
    Garavello M, Goatin P. 2011. The Aw–Rascle traffic model with locally constrained flow. J. Math. Anal. Appl. 378:634–48
     [Google Scholar]
  54. 54. 
    Goatin P. 2006. The Aw–Rascle vehicular traffic flow model with phase transitions. Math. Comput. Model. 44:287–303
     [Google Scholar]
  55. 55. 
    Gupta AK, Katiyar VK. 2007. A new multi-class continuum model for traffic flow. Transportmetrica 3:73–85
     [Google Scholar]
  56. 56. 
    Fan S, Work D. 2015. A heterogeneous multiclass traffic flow model with creeping. SIAM J. Appl. Math. 75:813–35
     [Google Scholar]
  57. 57. 
    Bressan A. 2000. Hyperbolic Systems of Conservation Laws: The One-Dimensional Cauchy Problem Oxford, UK: Oxford Univ. Press
  58. 58. 
    Bardos C, Leroux AY, Nédélec JC 1979. First order quasilinear equations with boundary conditions. Commun. Part. Differ. Equ. 4:1017–34
     [Google Scholar]
  59. 59. 
    Frankowska H. 2010. On LeFloch's solutions to the initial-boundary value problem for scalar conservation laws. J. Hyperbolic Differ. Equ. 7:503–43
     [Google Scholar]
  60. 60. 
    Colombo RM, Rossi E. 2019. Stability of the 1D IBVP for a non autonomous scalar conservation law. Proc. R. Soc. Edinb. A 149:561–92
     [Google Scholar]
  61. 61. 
    Rossi E. 2019. Well-posedness of general 1D initial boundary value problems for scalar balance laws. Discrete Contin. Dyn. Syst. A 39:3577–608
     [Google Scholar]
  62. 62. 
    Armbruster D, Göttlich S, Herty M 2011. A scalar conservation law with discontinuous flux for supply chains with finite buffers. SIAM J. Appl. Math. 71:1070–87
     [Google Scholar]
  63. 63. 
    Bressan A, Nguyen K. 2015. Optima and equilibria for traffic flow on networks with backward propagating queues. Netw. Heterog. Media 10:717–48
     [Google Scholar]
  64. 64. 
    Laurent-Brouty N, Keimer A, Goatin P, Bayen A 2019. A macroscopic traffic flow model with finite buffers on networks: well-posedness by means of Hamilton-Jacobi equations. Commun. Math. Sci. In review
    [Google Scholar]
  65. 65. 
    Garavello M, Goatin P. 2012. The Cauchy problem at a node with buffer. Discrete Contin. Dyn. Syst. A 32:1915–38
     [Google Scholar]
  66. 66. 
    Garavello M, Piccoli B. 2013. A multibuffer model for LWR road networks. Advances in Dynamic Network Modeling in Complex Transportation Systems SV Ukkusuri, KMA Özbay 143–61 New York: Springer
     [Google Scholar]
  67. 67. 
    Bressan A, Nordli A. 2017. The Riemann solver for traffic flow at an intersection with buffer of vanishing size. Netw. Heterog. Media 12:173–89
     [Google Scholar]
  68. 68. 
    Garavello M, Han K, Piccoli B 2016. Models for Vehicular Traffic on Networks Springfield, MO: Am. Inst. Math. Sci.
  69. 69. 
    Garavello M, Piccoli B. 2005. Source-destination flow on a road network. Commun. Math. Sci. 3:261–83
     [Google Scholar]
  70. 70. 
    Garavello M, Piccoli B. 2006. Traffic flow on a road network using the Aw–Rascle model. Commun. Partial Differ. Equ. 31:243–75
     [Google Scholar]
  71. 71. 
    Holden H, Risebro N. 1995. A mathematical model of traffic flow on a network of unidirectional roads. SIAM J. Math. Anal. 26:999–1017
     [Google Scholar]
  72. 72. 
    Herty M, Kirchner C, Moutari S, Rascle M 2008. Multicommodity flows on road networks. Commun. Math. Sci. 6:171–87
     [Google Scholar]
  73. 73. 
    Bayen A, Keimer A, Porter E, Spinola M 2019. Time-continuous instantaneous and on past memory routing on traffic networks: a mathematical analysis on the basis of the link-delay model. SIAM J. Appl. Dyn. Syst 18:2143–80
     [Google Scholar]
  74. 74. 
    Tang S, Keimer A, Bayen A 2019. PDE-modeled traffic systems subject to instantaneous and memory-based routing. IEEE Trans. Control Netw. Syst. In review
    [Google Scholar]
  75. 75. 
    Prato CG. 2009. Route choice modeling: past, present and future research directions. J. Choice Model. 2:65–100
     [Google Scholar]
  76. 76. 
    Henn V. 2000. Fuzzy route choice model for traffic assignment. Fuzzy Sets Syst 116:77–101
     [Google Scholar]
  77. 77. 
    Li J, Huang L. 2012. Stochastic traffic assignment considering road guidance information. J. Transp. Syst. Eng. Inf. Technol. 12:31–35
     [Google Scholar]
  78. 78. 
    Fosgerau M, Frejinger E, Karlstrom A 2013. A link based network route choice model with unrestricted choice set. Transp. Res. B 56:70–80
     [Google Scholar]
  79. 79. 
    Vovsha P, Bekhor S. 1998. Link-nested logit model of route choice: overcoming route overlapping problem. Transp. Res. Rec. 1645:133–42
     [Google Scholar]
  80. 80. 
    Prashker J, Bekhor S. 2004. Route choice models used in the stochastic user equilibrium problem: a review. Transp. Rev. 24:437–63
     [Google Scholar]
  81. 81. 
    Bovy PHL. 2009. On modelling route choice sets in transportation networks: a synthesis. Transp. Rev. 29:43–68
     [Google Scholar]
  82. 82. 
    Ben-Akiva M, Bergman MJ, Daly A, Ramaswamy R 1984. Modeling inter-urban route choice behaviour. Proceedings of the 9th International Symposium on Transportation and Traffic Theory299–330 Utrecht, Neth: VNU
     [Google Scholar]
  83. 83. 
    Gao S, Frejinger E, Ben-Akiva M 2011. Cognitive cost in route choice with real-time information: an exploratory analysis. Procedia Soc. Behav. Sci. 17:136–49
     [Google Scholar]
  84. 84. 
    Hu TY, Mahmassani HS. 1997. Day-to-day evolution of network flows under real-time information and reactive signal control. Transp. Res. C 5:51–69
     [Google Scholar]
  85. 85. 
    Dia H. 2002. An agent-based approach to modelling driver route choice behaviour under the influence of real-time information. Transp. Res. C 10:331–49
     [Google Scholar]
  86. 86. 
    Dia H, Panwai S. 2007. Modelling drivers' compliance and route choice behaviour in response to travel information. Nonlinear Dyn 49:493–509
     [Google Scholar]
  87. 87. 
    Selten R, Schreckenberg M, Pitz T, Chmura T, Kube S 2003. Experiments and simulations on day-to-day route choice-behaviour CESifo Work. Pap. Ser. 900, CESifo Group Munich, Ger: https://ideas.repec.org/p/ces/ceswps/_900.html
  88. 88. 
    Jou RC, Hensher D, Chen KH 2007. Route choice behaviour of freeway travellers under real-time traffic information provision – application of the best route and the habitual route choice mechanisms. Transp. Plan. Technol. 30:545–70
     [Google Scholar]
  89. 89. 
    Nakayama S, Kitamura R, Fujii S 2001. Drivers' route choice rules and network behavior: Do drivers become rational and homogeneous through learning. Transp. Res. Rec. 1752:62–68
     [Google Scholar]
  90. 90. 
    Meneguzzer C. 1995. An equilibrium route choice model with explicit treatment of the effect of intersections. Transp. Res. B 29:329–56
     [Google Scholar]
  91. 91. 
    Bekhor S, Toledo T, Prashker J 2008. Effects of choice set size and route choice models on path-based traffic assignment. Transportmetrica 4:117–33
     [Google Scholar]
  92. 92. 
    Chorus CG. 2012. Regret theory-based route choices and traffic equilibria. Transportmetrica 8:291–305
     [Google Scholar]
  93. 93. 
    Wardrop J. 1952. Some theoretical aspects of road traffic research. Proc. Inst. Civil Eng. 1:325–62
     [Google Scholar]
  94. 94. 
    Nash J. 1950. Equilibrium points in n-person games. PNAS 36:48–49
     [Google Scholar]
  95. 95. 
    Boyce D, Lee DH, Ran B 2001. Analytical models of the dynamic traffic assignment problem. Netw. Spat. Econ. 1:377–90
     [Google Scholar]
  96. 96. 
    Lu CC, Mahmassani HS. 2008. Modeling user responses to pricing: simultaneous route and departure time network equilibrium with heterogeneous users. Transp. Res. Rec. 2085:124–35
     [Google Scholar]
  97. 97. 
    Mahmassani HS, Chang GL. 1987. On boundedly rational user equilibrium in transportation systems. Transp. Sci. 21:89–99
     [Google Scholar]
  98. 98. 
    Chen HK, Hsueh CF. 1998. A model and an algorithm for the dynamic user-optimal route choice problem. Transp. Res. B 32:219–34
     [Google Scholar]
  99. 99. 
    Ran B, Boyce D. 1996. A link-based variational inequality formulation of ideal dynamic user-optimal route choice problem. Transp. Res. C 4:1–12
     [Google Scholar]
  100. 100. 
    Ran B, Hall RW, Boyce DE 1996. A link-based variational inequality model for dynamic departure time/route choice. Transp. Res. B 30:31–46
     [Google Scholar]
  101. 101. 
    Friesz T, Kim T, Kwon C, Rigdon M 2011. Approximate network loading and dual-time-scale dynamic user equilibrium. Transp. Res. B 45:176–207
     [Google Scholar]
  102. 102. 
    Lu C-C, Mahmassani HS, Zhou X 2009. Equivalent gap function-based reformulation and solution algorithm for the dynamic user equilibrium problem. Transp. Res. B 43:345–64
     [Google Scholar]
  103. 103. 
    Wie BW, Friesz TL, Tobin RL 1990. Dynamic user optimal traffic assignment on congested multidestination networks. Transp. Res. B 24:431–42
     [Google Scholar]
  104. 104. 
    Friesz T, Luque J, Tobin R, Wie BW 1989. Dynamic network traffic assignment considered as a continuous time optimal control problem. Oper. Res. 37:893–901
     [Google Scholar]
  105. 105. 
    Gugat M, Herty M, Klar A, Leugering G 2005. Optimal control for traffic flow networks. J. Optim. Theory Appl. 126:589–616
     [Google Scholar]
  106. 106. 
    Herty M, Kirchner C, Klar A 2007. Instantaneous control for traffic flow. Math. Methods Appl. Sci. 30:153–69
     [Google Scholar]
  107. 107. 
    Fügenschuh A, Herty M, Klar A, Martin A 2006. Combinatorial and continuous models for the optimization of traffic flows on networks. SIAM J. Optim. 16:1155–76
     [Google Scholar]
  108. 108. 
    Gugat M, Keimer A, Leugering G, Wang Z 2015. Analysis of a system of nonlocal conservation laws for multi-commodity flow on networks. Netw. Heterog. Media 10:749–85
     [Google Scholar]
  109. 109. 
    Zeidler E. 1986. Nonlinear Functional Analysis and Its Applications: I: Fixed-Point Theorems New York: Springer
/content/journals/10.1146/annurev-control-091319-125444
Loading
Routing on Traffic Networks Incorporating Past Memory up to Real-Time Information on the Network State
Annual Review of Control, Robotics, and Autonomous Systems 3, 151 (2020); https://doi.org/10.1146/annurev-control-091319-125444
/content/journals/10.1146/annurev-control-091319-125444
/content/journals/10.1146/annurev-control-091319-125444
Loading

Data & Media loading...

  • Article Type: Review Article

Most Cited Most Cited RSS feed

This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error