2014, 9(2): 315-334. doi: 10.3934/nhm.2014.9.315

Optimization for a special class of traffic flow models: Combinatorial and continuous approaches

1. 

Department of Mathematics, University of Mannheim, D-68131 Mannheim

2. 

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

3. 

Department of Mathematics, University of Kaiserslautern, D-67663 Kaiserslautern, Germany

Received  November 2013 Revised  March 2014 Published  July 2014

In this article, we discuss the optimization of a linearized traffic flow network model based on conservation laws. We present two solution approaches. One relies on the classical Lagrangian formalism (or adjoint calculus), whereas another one uses a discrete mixed-integer framework. We show how both approaches are related to each other. Numerical experiments are accompanied to show the quality of solutions.
Citation: Simone Göttlich, Oliver Kolb, Sebastian Kühn. Optimization for a special class of traffic flow models: Combinatorial and continuous approaches. Networks & Heterogeneous Media, 2014, 9 (2) : 315-334. doi: 10.3934/nhm.2014.9.315
References:
[1]

A. M. Bayen, R. L. Raffard and C. Tomlin, Adjoint-based control of a new Eulerian network model of air traffic flow,, IEEE Transactions on Control Systems Technology, 14 (2006), 804. doi: 10.1109/TCST.2006.876904.

[2]

A. Bressan and K. Han, Optima and equilibria for a model of traffic flow,, SIAM Journal on Mathematical Analysis, 43 (2011), 2384. doi: 10.1137/110825145.

[3]

M. Carey and E. Subrahmanian, An approach to modelling time-varying flows on congested networks,, Transportation Research Part B: Methodological, 34 (2000), 157. doi: 10.1016/S0191-2615(99)00019-3.

[4]

A. Cascone, B. Piccoli and L. Rarita, Circulation of car traffic in congested urban areas,, Communications in Mathematical Sciences, 6 (2008), 765. doi: 10.4310/CMS.2008.v6.n3.a12.

[5]

G. M. Coclite, M. Garavello and B. Piccoli, Traffic flow on a road network,, SIAM Journal on Mathematical Analysis, 36 (2005), 1862. doi: 10.1137/S0036141004402683.

[6]

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

[7]

C. F. Daganzo, Fundamentals of Transportation and Traffic Operations,, Pergamon-Elsevier, (1997).

[8]

C. D'Apice, S. Göttlich, M. Herty and B. Piccoli, Modeling, Simulation and Optimization of Supply Chains: A Continuous Approach,, SIAM Book Series on Mathematical Modeling and Computation, (2010). doi: 10.1137/1.9780898717600.

[9]

C. D'Apice, R. Manzo and B. Piccoli, Packet flow on telecommunication networks,, SIAM Journal on Mathematical Analysis, 38 (2006), 717. doi: 10.1137/050631628.

[10]

C. D'Apice, R. Manzo and B. Piccoli, A fluid dynamic model for telecommunication networks with sources and destinations,, SIAM Journal on Applied Mathematics, 68 (2008), 981. doi: 10.1137/060674132.

[11]

C. D'Apice, R. Manzo and B. Piccoli, Modelling supply networks with partial differential equations,, Quarterly of Applied Mathematics, 67 (2009), 419.

[12]

C. D'Apice, R. Manzo and B. Piccoli, Existence of solutions to Cauchy problems for a mixed continuum-discrete model for supply chains and networks,, Journal of Mathematical Analysis and Applications, 362 (2010), 374. doi: 10.1016/j.jmaa.2009.07.058.

[13]

C. D'Apice, R. Manzo and B. Piccoli, Optimal input flows for a PDE-ODE model of supply chains,, Communications in Mathematical Sciences, 10 (2012), 1225. doi: 10.4310/CMS.2012.v10.n4.a10.

[14]

P. Domschke, B. Geißler, O. Kolb, J. Lang, A. Martin and A. Morsi, Combination of nonlinear and linear optimization of transient gas networks,, INFORMS Journal on Computing, 23 (2011), 605. doi: 10.1287/ijoc.1100.0429.

[15]

A. Fügenschuh, B. Geißler, A. Martin and A. Morsi, The Transport PDE and Mixed-Integer Linear Programming,, in Models and Algorithms for Optimization in Logistics (eds. C. Barnhart, (2009).

[16]

A. Fügenschuh, S. Göttlich, M. Herty, A. Klar and A. Martin, A discrete optimization approach to large scale supply networks based on partial differential equations,, SIAM Journal on Scientific Computing, 30 (2008), 1490. doi: 10.1137/060663799.

[17]

A. Fügenschuh, M. Herty, A. Klar and A. Martin, Combinatorial and continuous models for the optimization of traffic flows on networks,, SIAM Journal on Optimization, 16 (2006), 1155. doi: 10.1137/040605503.

[18]

S. Göttlich, M. Herty, C. Ringhofer and U. Ziegler, Production systems with limited repair capacity,, Optimization, 61 (2012), 915. doi: 10.1080/02331934.2011.615395.

[19]

S. Göttlich, M. Herty and U. Ziegler, Numerical discretization of Hamilton - Jacobi equations on networks,, Networks and Heterogeneous Networks, 8 (2013), 685. doi: 10.3934/nhm.2013.8.685.

[20]

S. Göttlich, S. Kühn, J.P. Ohst, S. Ruzika and M. Thiemann, Evacuation dynamics influenced by spreading hazardous material,, Networks and Heterogeneous Media, 6 (2011), 443. doi: 10.3934/nhm.2011.6.443.

[21]

S. Göttlich and U. Ziegler, Traffic light control: A case study,, Discrete and Continuous Dynamical Systems Series S, 7 (2014), 483. doi: 10.3934/dcdss.2014.7.483.

[22]

M. Gugat, M. Herty, A. Klar and G. Leugering, Optimal control for traffic flow networks,, J. Optimization Theory Appl., 126 (2005), 589. doi: 10.1007/s10957-005-5499-z.

[23]

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.

[24]

M. Herty and A. Klar, Simplified dynamics and optimization of large scale traffic networks,, Mathematical Models and Methods in Applied Sciences (M3AS), 14 (2004), 579. doi: 10.1142/S0218202504003362.

[25]

M. Herty and V. Sachers, Adjoint calculus for optimization of gas networks,, Networks and Heterogeneous Media, 2 (2007), 733. doi: 10.3934/nhm.2007.2.733.

[26]

H. Holden and N. H. Risebro, A mathematical model of traffic flow on a network of unidirectional roads,, SIAM Journal on Mathematical Analysis, 26 (1995), 999. doi: 10.1137/S0036141093243289.

[27]

H. Holden and N. H. Risebro, Front Tracking for Hyperbolic Conservation Laws,, 2nd edition, (2002). doi: 10.1007/978-3-642-56139-9.

[28]

IBM ILOG CPLEX Optimization Studio, Cplex version 12,, 2010., ().

[29]

G. S. Jiang, D. Levy, C. T. Lin, S. Osher and E. Tadmor, High-Resolution nonoscillatory central schemes with nonstaggered grids for hyperbolic conservation laws,, SIAM Journal on Numerical Analysis, 35 (1998), 2147. doi: 10.1137/S0036142997317560.

[30]

C. T. Kelley, Iterative Methods for Optimization,, Society for Industrial and Applied Mathematics, (1999). doi: 10.1137/1.9781611970920.

[31]

C. Kirchner, M. Herty, S. Göttlich and A. Klar, Optimal control for continuous supply network models,, Networks Heterogenous Media, 1 (2006), 675. doi: 10.3934/nhm.2006.1.675.

[32]

A. Klar, R. D. Kühne and R. Wegener, Mathematical models for vehicular traffic,, Surveys on Mathematics for Industry, 6 (1996), 215.

[33]

O. Kolb, Simulation and Optimization of Gas and Water Supply Networks,, Ph.D thesis, (2011).

[34]

O. Kolb and J. Lang, Simulation and continuous optimization,, in Mathematical Optimization of Water Networks (eds. A. Martin, (2012), 17. doi: 10.1007/978-3-0348-0436-3.

[35]

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

[36]

R. Manzo, B. Piccoli and L. Rarita, Optimal distribution of traffic flows at junctions in emergency cases,, European Journal of Applied Mathematics, 23 (2012), 515. doi: 10.1017/S0956792512000071.

[37]

G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization,, Wiley-Interscience Series in Discrete Mathematics and Optimization, (1988).

[38]

G. F. Newell, Traffic Flow on Transportation Networks,, MIT Press Series in Transportation Studies, (1980).

[39]

P. Spellucci, Numerische Verfahren der Nichtlinearen Optimierung,, Birkhäuser-Verlag, (1993). doi: 10.1007/978-3-0348-7214-0.

[40]

P. Spellucci, A new technique for inconsistent QP problems in the SQP method,, Mathematical Methods of Operations Research, 47 (1998), 355. doi: 10.1007/BF01198402.

[41]

P. Spellucci, An SQP method for general nonlinear programs using only equality constrained subproblems,, Mathematical programming, 82 (1998), 413. doi: 10.1007/BF01580078.

[42]

D. Sun, I. S. Strub and A. M. Bayen, Comparison of the performance of four Eulerian network flow models for strategic air traffic management,, Networks and Heterogeneous Media, 2 (2007), 569. doi: 10.3934/nhm.2007.2.569.

show all references

References:
[1]

A. M. Bayen, R. L. Raffard and C. Tomlin, Adjoint-based control of a new Eulerian network model of air traffic flow,, IEEE Transactions on Control Systems Technology, 14 (2006), 804. doi: 10.1109/TCST.2006.876904.

[2]

A. Bressan and K. Han, Optima and equilibria for a model of traffic flow,, SIAM Journal on Mathematical Analysis, 43 (2011), 2384. doi: 10.1137/110825145.

[3]

M. Carey and E. Subrahmanian, An approach to modelling time-varying flows on congested networks,, Transportation Research Part B: Methodological, 34 (2000), 157. doi: 10.1016/S0191-2615(99)00019-3.

[4]

A. Cascone, B. Piccoli and L. Rarita, Circulation of car traffic in congested urban areas,, Communications in Mathematical Sciences, 6 (2008), 765. doi: 10.4310/CMS.2008.v6.n3.a12.

[5]

G. M. Coclite, M. Garavello and B. Piccoli, Traffic flow on a road network,, SIAM Journal on Mathematical Analysis, 36 (2005), 1862. doi: 10.1137/S0036141004402683.

[6]

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

[7]

C. F. Daganzo, Fundamentals of Transportation and Traffic Operations,, Pergamon-Elsevier, (1997).

[8]

C. D'Apice, S. Göttlich, M. Herty and B. Piccoli, Modeling, Simulation and Optimization of Supply Chains: A Continuous Approach,, SIAM Book Series on Mathematical Modeling and Computation, (2010). doi: 10.1137/1.9780898717600.

[9]

C. D'Apice, R. Manzo and B. Piccoli, Packet flow on telecommunication networks,, SIAM Journal on Mathematical Analysis, 38 (2006), 717. doi: 10.1137/050631628.

[10]

C. D'Apice, R. Manzo and B. Piccoli, A fluid dynamic model for telecommunication networks with sources and destinations,, SIAM Journal on Applied Mathematics, 68 (2008), 981. doi: 10.1137/060674132.

[11]

C. D'Apice, R. Manzo and B. Piccoli, Modelling supply networks with partial differential equations,, Quarterly of Applied Mathematics, 67 (2009), 419.

[12]

C. D'Apice, R. Manzo and B. Piccoli, Existence of solutions to Cauchy problems for a mixed continuum-discrete model for supply chains and networks,, Journal of Mathematical Analysis and Applications, 362 (2010), 374. doi: 10.1016/j.jmaa.2009.07.058.

[13]

C. D'Apice, R. Manzo and B. Piccoli, Optimal input flows for a PDE-ODE model of supply chains,, Communications in Mathematical Sciences, 10 (2012), 1225. doi: 10.4310/CMS.2012.v10.n4.a10.

[14]

P. Domschke, B. Geißler, O. Kolb, J. Lang, A. Martin and A. Morsi, Combination of nonlinear and linear optimization of transient gas networks,, INFORMS Journal on Computing, 23 (2011), 605. doi: 10.1287/ijoc.1100.0429.

[15]

A. Fügenschuh, B. Geißler, A. Martin and A. Morsi, The Transport PDE and Mixed-Integer Linear Programming,, in Models and Algorithms for Optimization in Logistics (eds. C. Barnhart, (2009).

[16]

A. Fügenschuh, S. Göttlich, M. Herty, A. Klar and A. Martin, A discrete optimization approach to large scale supply networks based on partial differential equations,, SIAM Journal on Scientific Computing, 30 (2008), 1490. doi: 10.1137/060663799.

[17]

A. Fügenschuh, M. Herty, A. Klar and A. Martin, Combinatorial and continuous models for the optimization of traffic flows on networks,, SIAM Journal on Optimization, 16 (2006), 1155. doi: 10.1137/040605503.

[18]

S. Göttlich, M. Herty, C. Ringhofer and U. Ziegler, Production systems with limited repair capacity,, Optimization, 61 (2012), 915. doi: 10.1080/02331934.2011.615395.

[19]

S. Göttlich, M. Herty and U. Ziegler, Numerical discretization of Hamilton - Jacobi equations on networks,, Networks and Heterogeneous Networks, 8 (2013), 685. doi: 10.3934/nhm.2013.8.685.

[20]

S. Göttlich, S. Kühn, J.P. Ohst, S. Ruzika and M. Thiemann, Evacuation dynamics influenced by spreading hazardous material,, Networks and Heterogeneous Media, 6 (2011), 443. doi: 10.3934/nhm.2011.6.443.

[21]

S. Göttlich and U. Ziegler, Traffic light control: A case study,, Discrete and Continuous Dynamical Systems Series S, 7 (2014), 483. doi: 10.3934/dcdss.2014.7.483.

[22]

M. Gugat, M. Herty, A. Klar and G. Leugering, Optimal control for traffic flow networks,, J. Optimization Theory Appl., 126 (2005), 589. doi: 10.1007/s10957-005-5499-z.

[23]

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.

[24]

M. Herty and A. Klar, Simplified dynamics and optimization of large scale traffic networks,, Mathematical Models and Methods in Applied Sciences (M3AS), 14 (2004), 579. doi: 10.1142/S0218202504003362.

[25]

M. Herty and V. Sachers, Adjoint calculus for optimization of gas networks,, Networks and Heterogeneous Media, 2 (2007), 733. doi: 10.3934/nhm.2007.2.733.

[26]

H. Holden and N. H. Risebro, A mathematical model of traffic flow on a network of unidirectional roads,, SIAM Journal on Mathematical Analysis, 26 (1995), 999. doi: 10.1137/S0036141093243289.

[27]

H. Holden and N. H. Risebro, Front Tracking for Hyperbolic Conservation Laws,, 2nd edition, (2002). doi: 10.1007/978-3-642-56139-9.

[28]

IBM ILOG CPLEX Optimization Studio, Cplex version 12,, 2010., ().

[29]

G. S. Jiang, D. Levy, C. T. Lin, S. Osher and E. Tadmor, High-Resolution nonoscillatory central schemes with nonstaggered grids for hyperbolic conservation laws,, SIAM Journal on Numerical Analysis, 35 (1998), 2147. doi: 10.1137/S0036142997317560.

[30]

C. T. Kelley, Iterative Methods for Optimization,, Society for Industrial and Applied Mathematics, (1999). doi: 10.1137/1.9781611970920.

[31]

C. Kirchner, M. Herty, S. Göttlich and A. Klar, Optimal control for continuous supply network models,, Networks Heterogenous Media, 1 (2006), 675. doi: 10.3934/nhm.2006.1.675.

[32]

A. Klar, R. D. Kühne and R. Wegener, Mathematical models for vehicular traffic,, Surveys on Mathematics for Industry, 6 (1996), 215.

[33]

O. Kolb, Simulation and Optimization of Gas and Water Supply Networks,, Ph.D thesis, (2011).

[34]

O. Kolb and J. Lang, Simulation and continuous optimization,, in Mathematical Optimization of Water Networks (eds. A. Martin, (2012), 17. doi: 10.1007/978-3-0348-0436-3.

[35]

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

[36]

R. Manzo, B. Piccoli and L. Rarita, Optimal distribution of traffic flows at junctions in emergency cases,, European Journal of Applied Mathematics, 23 (2012), 515. doi: 10.1017/S0956792512000071.

[37]

G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization,, Wiley-Interscience Series in Discrete Mathematics and Optimization, (1988).

[38]

G. F. Newell, Traffic Flow on Transportation Networks,, MIT Press Series in Transportation Studies, (1980).

[39]

P. Spellucci, Numerische Verfahren der Nichtlinearen Optimierung,, Birkhäuser-Verlag, (1993). doi: 10.1007/978-3-0348-7214-0.

[40]

P. Spellucci, A new technique for inconsistent QP problems in the SQP method,, Mathematical Methods of Operations Research, 47 (1998), 355. doi: 10.1007/BF01198402.

[41]

P. Spellucci, An SQP method for general nonlinear programs using only equality constrained subproblems,, Mathematical programming, 82 (1998), 413. doi: 10.1007/BF01580078.

[42]

D. Sun, I. S. Strub and A. M. Bayen, Comparison of the performance of four Eulerian network flow models for strategic air traffic management,, Networks and Heterogeneous Media, 2 (2007), 569. doi: 10.3934/nhm.2007.2.569.

[1]

Michael Herty, Veronika Sachers. Adjoint calculus for optimization of gas networks. Networks & Heterogeneous Media, 2007, 2 (4) : 733-750. doi: 10.3934/nhm.2007.2.733

[2]

Wen-Xiu Ma. Conservation laws by symmetries and adjoint symmetries. Discrete & Continuous Dynamical Systems - S, 2018, 11 (4) : 707-721. doi: 10.3934/dcdss.2018044

[3]

Mauro Garavello. A review of conservation laws on networks. Networks & Heterogeneous Media, 2010, 5 (3) : 565-581. doi: 10.3934/nhm.2010.5.565

[4]

Georges Bastin, B. Haut, Jean-Michel Coron, Brigitte d'Andréa-Novel. Lyapunov stability analysis of networks of scalar conservation laws. Networks & Heterogeneous Media, 2007, 2 (4) : 751-759. doi: 10.3934/nhm.2007.2.751

[5]

Christophe Prieur. Control of systems of conservation laws with boundary errors. Networks & Heterogeneous Media, 2009, 4 (2) : 393-407. doi: 10.3934/nhm.2009.4.393

[6]

Xavier Litrico, Vincent Fromion, Gérard Scorletti. Robust feedforward boundary control of hyperbolic conservation laws. Networks & Heterogeneous Media, 2007, 2 (4) : 717-731. doi: 10.3934/nhm.2007.2.717

[7]

Martin Gugat, Alexander Keimer, Günter Leugering, Zhiqiang Wang. Analysis of a system of nonlocal conservation laws for multi-commodity flow on networks. Networks & Heterogeneous Media, 2015, 10 (4) : 749-785. doi: 10.3934/nhm.2015.10.749

[8]

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

[9]

Lino J. Alvarez-Vázquez, Néstor García-Chan, Aurea Martínez, Miguel E. Vázquez-Méndez. Optimal control of urban air pollution related to traffic flow in road networks. Mathematical Control & Related Fields, 2018, 8 (1) : 177-193. doi: 10.3934/mcrf.2018008

[10]

Avner Friedman. Conservation laws in mathematical biology. Discrete & Continuous Dynamical Systems - A, 2012, 32 (9) : 3081-3097. doi: 10.3934/dcds.2012.32.3081

[11]

Mauro Garavello, Roberto Natalini, Benedetto Piccoli, Andrea Terracina. Conservation laws with discontinuous flux. Networks & Heterogeneous Media, 2007, 2 (1) : 159-179. doi: 10.3934/nhm.2007.2.159

[12]

Yanning Li, Edward Canepa, Christian Claudel. Efficient robust control of first order scalar conservation laws using semi-analytical solutions. Discrete & Continuous Dynamical Systems - S, 2014, 7 (3) : 525-542. doi: 10.3934/dcdss.2014.7.525

[13]

Yuan Zhao, Shunfu Jin, Wuyi Yue. Adjustable admission control with threshold in centralized CR networks: Analysis and optimization. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1393-1408. doi: 10.3934/jimo.2015.11.1393

[14]

Tai-Ping Liu, Shih-Hsien Yu. Hyperbolic conservation laws and dynamic systems. Discrete & Continuous Dynamical Systems - A, 2000, 6 (1) : 143-145. doi: 10.3934/dcds.2000.6.143

[15]

Yanbo Hu, Wancheng Sheng. The Riemann problem of conservation laws in magnetogasdynamics. Communications on Pure & Applied Analysis, 2013, 12 (2) : 755-769. doi: 10.3934/cpaa.2013.12.755

[16]

Stefano Bianchini, Elio Marconi. On the concentration of entropy for scalar conservation laws. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 73-88. doi: 10.3934/dcdss.2016.9.73

[17]

Renato Bruni, Gianpiero Bianchi, Alessandra Reale. A combinatorial optimization approach to the selection of statistical units. Journal of Industrial & Management Optimization, 2016, 12 (2) : 515-527. doi: 10.3934/jimo.2016.12.515

[18]

Alberto Bressan, Marta Lewicka. A uniqueness condition for hyperbolic systems of conservation laws. Discrete & Continuous Dynamical Systems - A, 2000, 6 (3) : 673-682. doi: 10.3934/dcds.2000.6.673

[19]

Rinaldo M. Colombo, Kenneth H. Karlsen, Frédéric Lagoutière, Andrea Marson. Special issue on contemporary topics in conservation laws. Networks & Heterogeneous Media, 2016, 11 (2) : i-ii. doi: 10.3934/nhm.2016.11.2i

[20]

Laurent Lévi, Julien Jimenez. Coupling of scalar conservation laws in stratified porous media. Conference Publications, 2007, 2007 (Special) : 644-654. doi: 10.3934/proc.2007.2007.644

2017 Impact Factor: 1.187

Metrics

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

Other articles
by authors

[Back to Top]