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

Simone Göttlich; Oliver Kolb; Sebastian Kühn; Simone Göttlich; Oliver Kolb; Sebastian Kühn

doi:10.3934/nhm.2014.9.315

Networks and Heterogeneous Media

2014, Volume 9, Issue 2: 315-334. doi: 10.3934/nhm.2014.9.315

Previous Article Next Article

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
3.
Department of Mathematics, University of Kaiserslautern, D-67663 Kaiserslautern

Received: 01 November 2013 Revised: 01 March 2014
90B20, 49K20, 90C11.

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.
- Traffic networks,
- conservation laws,
- control of discretized PDEs,
- adjoint calculus,
- combinatorial optimization
Citation: Simone Göttlich, Oliver Kolb, Sebastian Kühn. Optimization for a special class of traffic flow models: Combinatorial and continuous approaches[J]. Networks and Heterogeneous Media, 2014, 9(2): 315-334. doi: 10.3934/nhm.2014.9.315

Related Papers:

Abstract

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.

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-818. 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-2417. 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-183. 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-784. 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-1886. doi: 10.1137/S0036141004402683
[6]	C. F. Daganzo, The cell transmission model, part II: Network traffic, Transportation Research Part B: Methodological, 29 (1995), 79-93. doi: 10.1016/0191-2615(94)00022-R
[7]	C. F. Daganzo, Fundamentals of Transportation and Traffic Operations, Pergamon-Elsevier, Oxford, U.K., 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-740. 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-1003. 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-440.
[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-386. 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-1240. 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-617. 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, U. Clausen, U. Lauther and R. H. Möhring), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 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-1507. 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-1176. 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-948. 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-705. 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-464. 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-501. 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-616. 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-1087. 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-601. doi: 10.1142/S0218202504003362
[25]	M. Herty and V. Sachers, Adjoint calculus for optimization of gas networks, Networks and Heterogeneous Media, 2 (2007), 733-750. 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-1017. doi: 10.1137/S0036141093243289
[27]	H. Holden and N. H. Risebro, Front Tracking for Hyperbolic Conservation Laws, 2nd edition, Springer, New York, Berlin, Heidelberg, 2002. doi: 10.1007/978-3-642-56139-9
[28]	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-2168. doi: 10.1137/S0036142997317560
[30]	C. T. Kelley, Iterative Methods for Optimization, Society for Industrial and Applied Mathematics, Philadelphia, 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-688. 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-239.
[33]	O. Kolb, Simulation and Optimization of Gas and Water Supply Networks, Ph.D thesis, Technische Universität Darmstadt, 2011.
[34]	O. Kolb and J. Lang, Simulation and continuous optimization, in Mathematical Optimization of Water Networks (eds. A. Martin, K. Klamroth, J. Lang, G. Leugering, A. Morsi, M. Oberlack, M. Ostrowski and R. Rosen), Internat. Ser. Numer. Math., 162, Birkhäuser/Springer Basel AG, Basel, 2012, 17-33. 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-345. 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-535. doi: 10.1017/S0956792512000071
[37]	G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, 1988.
[38]	G. F. Newell, Traffic Flow on Transportation Networks, MIT Press Series in Transportation Studies, MIT Press, Cambridge, MA, USA, 1980.
[39]	P. Spellucci, Numerische Verfahren der Nichtlinearen Optimierung, Birkhäuser-Verlag, Basel, 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-400. doi: 10.1007/BF01198402
[41]	P. Spellucci, An SQP method for general nonlinear programs using only equality constrained subproblems, Mathematical programming, 82 (1998), 413-448. 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-595. doi: 10.3934/nhm.2007.2.569

Reader Comments

Your name:*

Email:*
© 2014 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)