Numerical discretization of Hamilton--Jacobi equations on networks

Previous Article
A dynamical two-dimensional traffic model in an anisotropic network
NHM Home
This Issue
Next Article
Viability approach to Hamilton-Jacobi-Moskowitz problem involving variable regulation parameters

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

Numerical discretization of Hamilton--Jacobi equations on networks

Simone Göttlich ^1, , Ute Ziegler ^1, and Michael Herty ^2,

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

Abstract
Related Papers

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.

Keywords: Networks, traffic flow, Hamilton-Jacobi Equations..

Mathematics Subject Classification: Primary: 90B20, 35L50; Secondary: 35F2.

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]	Guillaume Costeseque, Jean-Patrick Lebacque. Discussion about traffic junction modelling: Conservation laws VS Hamilton-Jacobi equations. Discrete & Continuous Dynamical Systems - S, 2014, 7 (3) : 411-433. doi: 10.3934/dcdss.2014.7.411
[2]	Claudio Marchi. On the convergence of singular perturbations of Hamilton-Jacobi equations. Communications on Pure & Applied Analysis, 2010, 9 (5) : 1363-1377. doi: 10.3934/cpaa.2010.9.1363
[3]	Isabeau Birindelli, J. Wigniolle. Homogenization of Hamilton-Jacobi equations in the Heisenberg group. Communications on Pure & Applied Analysis, 2003, 2 (4) : 461-479. doi: 10.3934/cpaa.2003.2.461
[4]	Laura Caravenna, Annalisa Cesaroni, Hung Vinh Tran. Preface: Recent developments related to conservation laws and Hamilton-Jacobi equations. Discrete & Continuous Dynamical Systems - S, 2018, 11 (5) : ⅰ-ⅲ. doi: 10.3934/dcdss.201805i
[5]	Fabio Camilli, Paola Loreti, Naoki Yamada. Systems of convex Hamilton-Jacobi equations with implicit obstacles and the obstacle problem. Communications on Pure & Applied Analysis, 2009, 8 (4) : 1291-1302. doi: 10.3934/cpaa.2009.8.1291
[6]	Yasuhiro Fujita, Katsushi Ohmori. Inequalities and the Aubry-Mather theory of Hamilton-Jacobi equations. Communications on Pure & Applied Analysis, 2009, 8 (2) : 683-688. doi: 10.3934/cpaa.2009.8.683
[7]	Olga Bernardi, Franco Cardin. On $C^0$-variational solutions for Hamilton-Jacobi equations. Discrete & Continuous Dynamical Systems - A, 2011, 31 (2) : 385-406. doi: 10.3934/dcds.2011.31.385
[8]	Emeric Bouin. A Hamilton-Jacobi approach for front propagation in kinetic equations. Kinetic & Related Models, 2015, 8 (2) : 255-280. doi: 10.3934/krm.2015.8.255
[9]	Gawtum Namah, Mohammed Sbihi. A notion of extremal solutions for time periodic Hamilton-Jacobi equations. Discrete & Continuous Dynamical Systems - B, 2010, 13 (3) : 647-664. doi: 10.3934/dcdsb.2010.13.647
[10]	Antonio Avantaggiati, Paola Loreti, Cristina Pocci. Mixed norms, functional Inequalities, and Hamilton-Jacobi equations. Discrete & Continuous Dynamical Systems - B, 2014, 19 (7) : 1855-1867. doi: 10.3934/dcdsb.2014.19.1855
[11]	Gui-Qiang Chen, Bo Su. Discontinuous solutions for Hamilton-Jacobi equations: Uniqueness and regularity. Discrete & Continuous Dynamical Systems - A, 2003, 9 (1) : 167-192. doi: 10.3934/dcds.2003.9.167
[12]	Martino Bardi, Yoshikazu Giga. Right accessibility of semicontinuous initial data for Hamilton-Jacobi equations. Communications on Pure & Applied Analysis, 2003, 2 (4) : 447-459. doi: 10.3934/cpaa.2003.2.447
[13]	Xifeng Su, Lin Wang, Jun Yan. Weak KAM theory for HAMILTON-JACOBI equations depending on unknown functions. Discrete & Continuous Dynamical Systems - A, 2016, 36 (11) : 6487-6522. doi: 10.3934/dcds.2016080
[14]	David McCaffrey. A representational formula for variational solutions to Hamilton-Jacobi equations. Communications on Pure & Applied Analysis, 2012, 11 (3) : 1205-1215. doi: 10.3934/cpaa.2012.11.1205
[15]	Mihai Bostan, Gawtum Namah. Time periodic viscosity solutions of Hamilton-Jacobi equations. Communications on Pure & Applied Analysis, 2007, 6 (2) : 389-410. doi: 10.3934/cpaa.2007.6.389
[16]	Piermarco Cannarsa, Marco Mazzola, Carlo Sinestrari. Global propagation of singularities for time dependent Hamilton-Jacobi equations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4225-4239. doi: 10.3934/dcds.2015.35.4225
[17]	Olga Bernardi, Franco Cardin. Minimax and viscosity solutions of Hamilton-Jacobi equations in the convex case. Communications on Pure & Applied Analysis, 2006, 5 (4) : 793-812. doi: 10.3934/cpaa.2006.5.793
[18]	Kaizhi Wang, Jun Yan. Lipschitz dependence of viscosity solutions of Hamilton-Jacobi equations with respect to the parameter. Discrete & Continuous Dynamical Systems - A, 2016, 36 (3) : 1649-1659. doi: 10.3934/dcds.2016.36.1649
[19]	Qing Liu, Atsushi Nakayasu. Convexity preserving properties for Hamilton-Jacobi equations in geodesic spaces. Discrete & Continuous Dynamical Systems - A, 2019, 39 (1) : 157-183. doi: 10.3934/dcds.2019007
[20]	Joan-Andreu Lázaro-Camí, Juan-Pablo Ortega. The stochastic Hamilton-Jacobi equation. Journal of Geometric Mechanics, 2009, 1 (3) : 295-315. doi: 10.3934/jgm.2009.1.295

2018 Impact Factor: 0.871

American Institute of Mathematical Sciences