June  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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[27]

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

[28]

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

[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.  Google Scholar

[30]

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

[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.  Google Scholar

[32]

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

[33]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[37]

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

[38]

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

[39]

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

[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.  Google Scholar

[41]

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

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[27]

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

[28]

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

[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.  Google Scholar

[30]

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

[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.  Google Scholar

[32]

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

[33]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[37]

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

[38]

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

[39]

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

[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.  Google Scholar

[41]

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

[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.  Google Scholar

[1]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[2]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[3]

Thabet Abdeljawad, Mohammad Esmael Samei. Applying quantum calculus for the existence of solution of $ q $-integro-differential equations with three criteria. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020440

[4]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046

[5]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444

[6]

Youming Guo, Tingting Li. Optimal control strategies for an online game addiction model with low and high risk exposure. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020347

[7]

Bernard Bonnard, Jérémy Rouot. Geometric optimal techniques to control the muscular force response to functional electrical stimulation using a non-isometric force-fatigue model. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2020032

[8]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

2019 Impact Factor: 1.053

Metrics

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

Other articles
by authors

[Back to Top]