September  2013, 8(3): 685-705. doi: 10.3934/nhm.2013.8.685

Numerical discretization of Hamilton--Jacobi equations on networks

1. 

University of Mannheim, School of Business Informatics and Mathematics, A5-6, 68131 Mannheim, Germany, Germany

2. 

RWTH Aachen University, IGPM, Templergraben 55, 52056 Aachen

Received  November 2012 Revised  June 2013 Published  October 2013

We discuss a numerical discretization of Hamilton--Jacobi equations on networks. The latter arise for example as reformulation of the Lighthill--Whitham--Richards traffic flow model. We present coupling conditions for the Hamilton--Jacobi equations and derive a suitable numerical algorithm. Numerical computations of travel times in a round-about are given.
Citation: Simone Göttlich, Ute Ziegler, Michael Herty. Numerical discretization of Hamilton--Jacobi equations on networks. Networks & Heterogeneous Media, 2013, 8 (3) : 685-705. doi: 10.3934/nhm.2013.8.685
References:
[1]

A. M. Bayen and C. G. Claudel, Convex formulations of data assimilation problems for a class of Hamilton-Jacobi equations,, SIAM J. Control Optim., 49 (2011), 383.  doi: 10.1137/090778754.  Google Scholar

[2]

A. Bressan and K. Han, Optima and equilibria for a model of traffic flow,, SIAM J. Math. Anal., 43 (2011), 2384.  doi: 10.1137/110825145.  Google Scholar

[3]

G. Bretti, R. Natalini and B. Piccoli, Numerical approximations of a traffic flow model on networks,, Netw. Heterog. Media, 1 (2006), 57.  doi: 10.3934/nhm.2006.1.57.  Google Scholar

[4]

G. Bretti and B. Piccoli, A tracking algorithm for car paths on road networks,, SIAM J. Appl. Dyn. Syst., 7 (2008), 510.  doi: 10.1137/070697768.  Google Scholar

[5]

Y. Chitour and B. Piccoli, Traffic circles and timing of traffic lights for cars flow,, Discrete Contin. Dyn. Syst. Ser. B, 5 (2005), 599.  doi: 10.3934/dcdsb.2005.5.599.  Google Scholar

[6]

G. M. Coclite, M. Garavello and B. Piccoli, Traffic flow on a road network,, SIAM J. Math. Anal., 36 (2005), 1862.  doi: 10.1137/S0036141004402683.  Google Scholar

[7]

R. Corthout, G. Flötteröd, F. Viti and C. M. J. Tampère, Non-unique flows in macroscopic first-order intersection models,, Transportation Res. Part B, 46 (2012), 343.  doi: 10.1016/j.trb.2011.10.011.  Google Scholar

[8]

C. F. Daganzo, A variational formulation of kinematic waves: Basic theory and complex boundary conditions,, Transportation Res. Part B, 39 (2005), 187.  doi: 10.1016/j.trb.2004.04.003.  Google Scholar

[9]

C. F. Daganzo, The cell transmission model, part II: Network traffic,, Transportation Res. Part B, 29 (1995), 79.  doi: 10.1016/0191-2615(94)00022-R.  Google Scholar

[10]

C. F. Daganzo, On the variational theory of traffic flow: Well-posedness, duality and applications,, Networks and Heterogeneous Media, 1 (2006), 601.  doi: 10.3934/nhm.2006.1.601.  Google Scholar

[11]

G. B. Dantzig, "Linear Programming and Extensions,", Princeton University Press, (1963).   Google Scholar

[12]

C. D'Apice, R. Manzo and B. Piccoli, A fluid dynamic model for telecommunication networks with sources and destinations,, SIAM J. Appl. Math., 68 (2008), 981.  doi: 10.1137/060674132.  Google Scholar

[13]

C. D'Apice, R. Manzo and L. Rarità, Splitting of traffic flows to control congestion in special events,, Int. J. Math. Math. Sci., (2011).  doi: 10.1155/2011/563171.  Google Scholar

[14]

G. Flötteröd and J. Rohde, Operational macroscopic modeling of complex urban intersections,, Transportation Res. Part B: Methodological, 45 (2011), 903.   Google Scholar

[15]

M. Garavello and B. Piccoli, "Traffic Flow on Networks,", AIMS Series on Applied Mathematics, (2006).   Google Scholar

[16]

M. Garavello and B. Piccoli, Source-destination flow on a road network,, Commun. Math. Sci., 3 (2005), 261.   Google Scholar

[17]

S. K. Godunov, A difference method for numerical calculation of discontinuous solutions of the equations of hydrodynamics,, (Russian) Mat. Sb. (N. S.), 47 (1959), 271.   Google Scholar

[18]

B. Haut and G. Bastin, A second order model of road junctions in fluid models of traffic networks,, Netw. Heterog. Media, 2 (2007), 227.  doi: 10.3934/nhm.2007.2.227.  Google Scholar

[19]

M. Herty and A. Klar, Modeling, simulation, and optimization of traffic flow networks,, SIAM Journal on Scientific Computing, 25 (2003), 1066.  doi: 10.1137/S106482750241459X.  Google Scholar

[20]

M. Herty and M. Rascle, Coupling conditions for a class of "second-order'' models for traffic flow,, SIAM J. Math. Anal., 38 (2006), 595.  doi: 10.1137/05062617X.  Google Scholar

[21]

H. Holden and N. H. Risebro, A mathematical model of traffic flow on a network of unidirectional roads,, SIAM J. Math. Anal., 26 (1995), 999.  doi: 10.1137/S0036141093243289.  Google Scholar

[22]

C. Imbert, R. Monneau and H. Zidnani, A Hamilton-Jacobi approach to junction problems and application to traffic flow,, ESAIM Control Optim. Calc. Var., 19 (2013), 129.  doi: 10.1051/cocv/2012002.  Google Scholar

[23]

A. Kurganov and E. Tadmor, New high-resolution semi-discrete central schemes for Hamilton-Jacobi equations,, J. Comput. Phys., 160 (2000), 720.  doi: 10.1006/jcph.2000.6485.  Google Scholar

[24]

J.-P. Lebacque and M. Khoshyaran, First order macroscopic traffic flow models for networks in the context of dynamic assignment,, Transportation Planning Applied Optimization, 64 (2004), 119.  doi: 10.1007/0-306-48220-7_8.  Google Scholar

[25]

R. J. LeVeque, "Numerical Methods for Conservation Laws,", Second edition. Lectures in Mathematics ETH Zürich, (1992).  doi: 10.1007/978-3-0348-8629-1.  Google Scholar

[26]

M. J. Lighthill and G. B. Whitham, On kinematic waves II. A theory of traffic flow on long crowded roads,, Proc. Royal Society London. Ser. A., 229 (1955), 317.  doi: 10.1098/rspa.1955.0089.  Google Scholar

[27]

Y. Makigami, G. F. Newell and R. Rothery, Three-dimensional representation of traffic flow,, Transportation Science, 5 (1971), 302.  doi: 10.1287/trsc.5.3.302.  Google Scholar

[28]

P. Mazarè, A. Dehwah, C. Claudel and A. Bayen, Analytical and grid-free solutions to the lighthill-whitham-richards traffic flow model,, Transportation Res. Part B: Methodological, 45 (2011), 1727.   Google Scholar

[29]

K. Moskowitz, Discussion of freeway level of service as influenced by volume and capacity characteristics,, Highway Research Record, 99 (1965), 43.   Google Scholar

[30]

G. F. Newell, A simplified theory of kinematic waves in highway traffic: (I) general theory; (ii) queuing at freeway bottlenecks; (iii) multi-destination flow,, Transportation Res. Part B, 27 (1993), 281.   Google Scholar

[31]

P. I. Richards, Shock waves on the highway,, Operations Res., 4 (1956), 42.  doi: 10.1287/opre.4.1.42.  Google Scholar

show all references

References:
[1]

A. M. Bayen and C. G. Claudel, Convex formulations of data assimilation problems for a class of Hamilton-Jacobi equations,, SIAM J. Control Optim., 49 (2011), 383.  doi: 10.1137/090778754.  Google Scholar

[2]

A. Bressan and K. Han, Optima and equilibria for a model of traffic flow,, SIAM J. Math. Anal., 43 (2011), 2384.  doi: 10.1137/110825145.  Google Scholar

[3]

G. Bretti, R. Natalini and B. Piccoli, Numerical approximations of a traffic flow model on networks,, Netw. Heterog. Media, 1 (2006), 57.  doi: 10.3934/nhm.2006.1.57.  Google Scholar

[4]

G. Bretti and B. Piccoli, A tracking algorithm for car paths on road networks,, SIAM J. Appl. Dyn. Syst., 7 (2008), 510.  doi: 10.1137/070697768.  Google Scholar

[5]

Y. Chitour and B. Piccoli, Traffic circles and timing of traffic lights for cars flow,, Discrete Contin. Dyn. Syst. Ser. B, 5 (2005), 599.  doi: 10.3934/dcdsb.2005.5.599.  Google Scholar

[6]

G. M. Coclite, M. Garavello and B. Piccoli, Traffic flow on a road network,, SIAM J. Math. Anal., 36 (2005), 1862.  doi: 10.1137/S0036141004402683.  Google Scholar

[7]

R. Corthout, G. Flötteröd, F. Viti and C. M. J. Tampère, Non-unique flows in macroscopic first-order intersection models,, Transportation Res. Part B, 46 (2012), 343.  doi: 10.1016/j.trb.2011.10.011.  Google Scholar

[8]

C. F. Daganzo, A variational formulation of kinematic waves: Basic theory and complex boundary conditions,, Transportation Res. Part B, 39 (2005), 187.  doi: 10.1016/j.trb.2004.04.003.  Google Scholar

[9]

C. F. Daganzo, The cell transmission model, part II: Network traffic,, Transportation Res. Part B, 29 (1995), 79.  doi: 10.1016/0191-2615(94)00022-R.  Google Scholar

[10]

C. F. Daganzo, On the variational theory of traffic flow: Well-posedness, duality and applications,, Networks and Heterogeneous Media, 1 (2006), 601.  doi: 10.3934/nhm.2006.1.601.  Google Scholar

[11]

G. B. Dantzig, "Linear Programming and Extensions,", Princeton University Press, (1963).   Google Scholar

[12]

C. D'Apice, R. Manzo and B. Piccoli, A fluid dynamic model for telecommunication networks with sources and destinations,, SIAM J. Appl. Math., 68 (2008), 981.  doi: 10.1137/060674132.  Google Scholar

[13]

C. D'Apice, R. Manzo and L. Rarità, Splitting of traffic flows to control congestion in special events,, Int. J. Math. Math. Sci., (2011).  doi: 10.1155/2011/563171.  Google Scholar

[14]

G. Flötteröd and J. Rohde, Operational macroscopic modeling of complex urban intersections,, Transportation Res. Part B: Methodological, 45 (2011), 903.   Google Scholar

[15]

M. Garavello and B. Piccoli, "Traffic Flow on Networks,", AIMS Series on Applied Mathematics, (2006).   Google Scholar

[16]

M. Garavello and B. Piccoli, Source-destination flow on a road network,, Commun. Math. Sci., 3 (2005), 261.   Google Scholar

[17]

S. K. Godunov, A difference method for numerical calculation of discontinuous solutions of the equations of hydrodynamics,, (Russian) Mat. Sb. (N. S.), 47 (1959), 271.   Google Scholar

[18]

B. Haut and G. Bastin, A second order model of road junctions in fluid models of traffic networks,, Netw. Heterog. Media, 2 (2007), 227.  doi: 10.3934/nhm.2007.2.227.  Google Scholar

[19]

M. Herty and A. Klar, Modeling, simulation, and optimization of traffic flow networks,, SIAM Journal on Scientific Computing, 25 (2003), 1066.  doi: 10.1137/S106482750241459X.  Google Scholar

[20]

M. Herty and M. Rascle, Coupling conditions for a class of "second-order'' models for traffic flow,, SIAM J. Math. Anal., 38 (2006), 595.  doi: 10.1137/05062617X.  Google Scholar

[21]

H. Holden and N. H. Risebro, A mathematical model of traffic flow on a network of unidirectional roads,, SIAM J. Math. Anal., 26 (1995), 999.  doi: 10.1137/S0036141093243289.  Google Scholar

[22]

C. Imbert, R. Monneau and H. Zidnani, A Hamilton-Jacobi approach to junction problems and application to traffic flow,, ESAIM Control Optim. Calc. Var., 19 (2013), 129.  doi: 10.1051/cocv/2012002.  Google Scholar

[23]

A. Kurganov and E. Tadmor, New high-resolution semi-discrete central schemes for Hamilton-Jacobi equations,, J. Comput. Phys., 160 (2000), 720.  doi: 10.1006/jcph.2000.6485.  Google Scholar

[24]

J.-P. Lebacque and M. Khoshyaran, First order macroscopic traffic flow models for networks in the context of dynamic assignment,, Transportation Planning Applied Optimization, 64 (2004), 119.  doi: 10.1007/0-306-48220-7_8.  Google Scholar

[25]

R. J. LeVeque, "Numerical Methods for Conservation Laws,", Second edition. Lectures in Mathematics ETH Zürich, (1992).  doi: 10.1007/978-3-0348-8629-1.  Google Scholar

[26]

M. J. Lighthill and G. B. Whitham, On kinematic waves II. A theory of traffic flow on long crowded roads,, Proc. Royal Society London. Ser. A., 229 (1955), 317.  doi: 10.1098/rspa.1955.0089.  Google Scholar

[27]

Y. Makigami, G. F. Newell and R. Rothery, Three-dimensional representation of traffic flow,, Transportation Science, 5 (1971), 302.  doi: 10.1287/trsc.5.3.302.  Google Scholar

[28]

P. Mazarè, A. Dehwah, C. Claudel and A. Bayen, Analytical and grid-free solutions to the lighthill-whitham-richards traffic flow model,, Transportation Res. Part B: Methodological, 45 (2011), 1727.   Google Scholar

[29]

K. Moskowitz, Discussion of freeway level of service as influenced by volume and capacity characteristics,, Highway Research Record, 99 (1965), 43.   Google Scholar

[30]

G. F. Newell, A simplified theory of kinematic waves in highway traffic: (I) general theory; (ii) queuing at freeway bottlenecks; (iii) multi-destination flow,, Transportation Res. Part B, 27 (1993), 281.   Google Scholar

[31]

P. I. Richards, Shock waves on the highway,, Operations Res., 4 (1956), 42.  doi: 10.1287/opre.4.1.42.  Google Scholar

[1]

Olivier Ley, Erwin Topp, Miguel Yangari. Some results for the large time behavior of Hamilton-Jacobi equations with Caputo time derivative. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021007

[2]

Sergey Rashkovskiy. Hamilton-Jacobi theory for Hamiltonian and non-Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 563-583. doi: 10.3934/jgm.2020024

[3]

Ahmad El Hajj, Hassan Ibrahim, Vivian Rizik. $ BV $ solution for a non-linear Hamilton-Jacobi system. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020405

[4]

Caterina Balzotti, Simone Göttlich. A two-dimensional multi-class traffic flow model. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020034

[5]

Ling-Bing He, Li Xu. On the compressible Navier-Stokes equations in the whole space: From non-isentropic flow to isentropic flow. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021005

[6]

Ágota P. Horváth. Discrete diffusion semigroups associated with Jacobi-Dunkl and exceptional Jacobi polynomials. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021002

[7]

Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170

[8]

Giuseppe Capobianco, Tom Winandy, Simon R. Eugster. The principle of virtual work and Hamilton's principle on Galilean manifolds. Journal of Geometric Mechanics, 2021  doi: 10.3934/jgm.2021002

[9]

Raimund Bürger, Christophe Chalons, Rafael Ordoñez, Luis Miguel Villada. A multiclass Lighthill-Whitham-Richards traffic model with a discontinuous velocity function. Networks & Heterogeneous Media, 2021  doi: 10.3934/nhm.2021004

[10]

Jing Zhang, Jianquan Lu, Jinde Cao, Wei Huang, Jianhua Guo, Yun Wei. Traffic congestion pricing via network congestion game approach. Discrete & Continuous Dynamical Systems - S, 2021, 14 (4) : 1553-1567. doi: 10.3934/dcdss.2020378

[11]

Xiaoxian Tang, Jie Wang. Bistability of sequestration networks. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1337-1357. doi: 10.3934/dcdsb.2020165

[12]

Shuxing Chen, Jianzhong Min, Yongqian Zhang. Weak shock solution in supersonic flow past a wedge. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 115-132. doi: 10.3934/dcds.2009.23.115

[13]

Wenmeng Geng, Kai Tao. Large deviation theorems for dirichlet determinants of analytic quasi-periodic jacobi operators with Brjuno-Rüssmann frequency. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5305-5335. doi: 10.3934/cpaa.2020240

[14]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375

[15]

D. R. Michiel Renger, Johannes Zimmer. Orthogonality of fluxes in general nonlinear reaction networks. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 205-217. doi: 10.3934/dcdss.2020346

[16]

Bernold Fiedler. Global Hopf bifurcation in networks with fast feedback cycles. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 177-203. doi: 10.3934/dcdss.2020344

[17]

Lars Grüne. Computing Lyapunov functions using deep neural networks. Journal of Computational Dynamics, 2020  doi: 10.3934/jcd.2021006

[18]

Pedro Aceves-Sanchez, Benjamin Aymard, Diane Peurichard, Pol Kennel, Anne Lorsignol, Franck Plouraboué, Louis Casteilla, Pierre Degond. A new model for the emergence of blood capillary networks. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2021001

[19]

Leslaw Skrzypek, Yuncheng You. Feedback synchronization of FHN cellular neural networks. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021001

[20]

Shirin Panahi, Sajad Jafari. New synchronization index of non-identical networks. Discrete & Continuous Dynamical Systems - S, 2021, 14 (4) : 1359-1373. doi: 10.3934/dcdss.2020371

2019 Impact Factor: 1.053

Metrics

  • PDF downloads (145)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]