Optimal scenario for road evacuation in an urban environment. (English) Zbl 07905872
Summary: How to free a road from vehicle traffic as efficiently as possible and in a given time, in order to allow for example the passage of emergency vehicles? We are interested in this question which we reformulate as an optimal control problem. We consider a macroscopic road traffic model on networks, semi-discretized in space and decide to give ourselves the possibility to control the flow at junctions. Our target is to smooth the traffic along a given path within a fixed time. A parsimony constraint is imposed on the controls, in order to ensure that the optimal strategies are feasible in practice. We perform an analysis of the resulting optimal control problem, proving the existence of an optimal control and deriving optimality conditions, which we rewrite as a single functional equation. We then use this formulation to derive a new mixed algorithm interpreting it as a mix between two methods: a descent method combined with a fixed point method allowing global perturbations. We verify with numerical experiments the efficiency of this method on examples of graphs, first simple, then more complex. We highlight the efficiency of our approach by comparing it to standard methods. We propose an open source code implementing this approach in the Julia language.
MSC:
| 35Q49 | Transport equations |
| 76A30 | Traffic and pedestrian flow models |
| 49K15 | Optimality conditions for problems involving ordinary differential equations |
| 49K30 | Optimality conditions for solutions belonging to restricted classes (Lipschitz controls, bang-bang controls, etc.) |
| 49J30 | Existence of optimal solutions belonging to restricted classes (Lipschitz controls, bang-bang controls, etc.) |
| 49M41 | PDE constrained optimization (numerical aspects) |
| 65M08 | Finite volume methods for initial value and initial-boundary value problems involving PDEs |
| 65M06 | Finite difference methods for initial value and initial-boundary value problems involving PDEs |
| 65L06 | Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations |
| 65K05 | Numerical mathematical programming methods |
| 90C05 | Linear programming |
| 47J26 | Fixed-point iterations |
| 41A60 | Asymptotic approximations, asymptotic expansions (steepest descent, etc.) |
| 35B20 | Perturbations in context of PDEs |
References:
| [1] | Ancona, F.; Caravenna, L.; Cesaroni, A.; Coclite, GM; Marchi, C.; Marson, A., Analysis and control on networks: trends and perspectives, Netw. Heterog. Media, 12, 3, 1-2, 2017 · Zbl 1516.35003 · doi:10.3934/nhm.201703i |
| [2] | Ancona, F.; Cesaroni, A.; Coclite, GM; Garavello, M., On the optimization of conservation law models at a junction with inflow and flow distribution controls, SIAM J. Control. Optim., 56, 5, 3370-3403, 2018 · Zbl 1403.35166 · doi:10.1137/18M1176233 |
| [3] | Aw, A.; Rascle, M., Resurrection of “second order” models of traffic flow, SIAM J. Appl. Math., 60, 916-938, 2000 · Zbl 0957.35086 · doi:10.1137/S0036139997332099 |
| [4] | Baumgart, U.; Burger, M.; Klein, C.; Jarke, M.; Helfert, M.; Berns, K.; Gusikhin, O., Optimal control of traffic flow based on reinforcement learning, Smart Cities. Green Technologies, and Intelligent Transport Systems, 313-329, 2022, Cham: Springer, Cham · doi:10.1007/978-3-031-17098-0_16 |
| [5] | Bayen, A.; Delle Monache, M-L; Garavello, M.; Goatin, P.; Piccoli, B., Control Problems for Conservation Laws with Traffic Applications: Modeling, Analysis, and Numerical Methods, Progress in Nonlinear Differential Equations and Their Applications, 2022, Cham: Springer, Cham · Zbl 1501.35001 |
| [6] | Bayen, A.; Raffard, R.; Tomlin, C., Adjoint-based control of a new Eulerian network model of air traffic flow, IEEE Trans. Control Syst. Technol., 14, 5, 804-818, 2006 · doi:10.1109/TCST.2006.876904 |
| [7] | Biham, O.; Middleton, AA; Levine, D., Self-organization and a dynamical transition in traffic-flow models, Phys. Rev. A, 46, R6124-R6127, 1992 · doi:10.1103/PhysRevA.46.R6124 |
| [8] | Bretti, G.; Natalini, R.; Piccoli, B., Numerical approximations of a traffic flow model on networks, Netw. Heterog. Media, 1, 1, 57, 2006 · Zbl 1124.90005 · doi:10.3934/nhm.2006.1.57 |
| [9] | Canic, S., Piccoli, B., Qiu, J.-M., Ren, T.: Runge-Kutta discontinuous Galerkin method for traffic flow model on networks. J. Sci. Comput. (2015) · Zbl 1321.90034 |
| [10] | Chambolle, A., An algorithm for total variation minimization and applications, J. Math. Imaging Vis., 20, 89-97, 2004 · Zbl 1366.94048 · doi:10.1023/B:JMIV.0000011321.19549.88 |
| [11] | Chambolle, A., Mazari-Fouquer, I., Privat, Y.: (2023) Stability of optimal shapes and convergence of thresholding algorithms in linear and spectral optimal control problems. arXiv preprint arXiv:2306.14577 |
| [12] | Chitour, Y.; Piccoli, B., Traffic circles and timing of traffic lights for cars flow, Discrete Contin. Dyn. Syst. Ser. B, 5, 599-630, 2005 · Zbl 1086.35066 |
| [13] | Coclite, GM; Garavello, M.; Piccoli, B., Traffic flow on a road network, SIAM J. Math. Anal., 36, 6, 1862-1886, 2005 · Zbl 1114.90010 · doi:10.1137/S0036141004402683 |
| [14] | Coscia, V.; Delitala, M.; Frasca, P., On the mathematical theory of vehicular traffic flow II: discrete velocity kinetic models, Int. J. Nonlinear Mech., 42, 3, 411-421, 2007 · Zbl 1200.76163 · doi:10.1016/j.ijnonlinmec.2006.02.008 |
| [15] | Courtès, C.; Franck, E.; Lutz, K.; Navoret, L.; Privat, Y., Reduced modelling and optimal control of epidemiological individual-based models with contact heterogeneity, Optim. Control Appl. Methods, 45, 459-493, 2023 · Zbl 07831201 · doi:10.1002/oca.2970 |
| [16] | Delitala, M.; Tosin, A., Mathematical modeling of vehicular traffic: a discrete kinetic theory approach, Math. Models Methods Appl. Sci., 17, 6, 901-932, 2007 · Zbl 1117.35320 · doi:10.1142/S0218202507002157 |
| [17] | Ekeland, I., Témam, R.: Convex Analysis and Variational Problems, Classics in Applied Mathematics, vol. 28. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, English edition, 1999. Translated from the French · Zbl 0939.49002 |
| [18] | Fermo, L.; Tosin, A., Fundamental diagrams for kinetic equations of traffic flow, Discrete Contin. Dyn. Syst. Ser. S, 7, 449-462, 2014 · Zbl 1292.90079 |
| [19] | Fügenschuh, A.; Herty, M.; Klar, A.; Martin, A., Combinatorial and continuous models for the optimization of traffic flows on networks, SIAM J. Optim., 16, 4, 1155-1176, 2006 · Zbl 1131.90015 · doi:10.1137/040605503 |
| [20] | Bretti, G.; Natalini, R.; Piccoli, B., A fluid-dynamic traffic model on road networks, Arch. Comput. Methods Eng., 14, 139-172, 2007 · Zbl 1127.76004 · doi:10.1007/s11831-007-9004-8 |
| [21] | Garavello, M.; Piccoli, B., Traffic Flow on Networks, 2006, American Institute of Mathematical Sciences · Zbl 1136.90012 |
| [22] | Gipps, P., A behavioural car-following model for computer simulation, Transp. Res. Part B: Methodol., 15, 105-111, 1981 · doi:10.1016/0191-2615(81)90037-0 |
| [23] | Goatin, P.; Göttlich, S.; Kolb, O., Speed limit and ramp meter control for traffic flow networks, Eng. Optim., 48, 7, 1121-1144, 2016 · doi:10.1080/0305215X.2015.1097099 |
| [24] | Gugat, M.; Herty, M.; Klar, A.; Leugering, G., Optimal control for traffic flow networks, J. Optim. Theory Appl., 126, 3, 589-616, 2005 · Zbl 1079.49024 · doi:10.1007/s10957-005-5499-z |
| [25] | Göttlich, S.; Herty, M.; Ziegler, U., Modeling and optimizing traffic light settings in road networks, Comput. Oper. Res., 55, 36-51, 2015 · Zbl 1348.90186 · doi:10.1016/j.cor.2014.10.001 |
| [26] | Jayakrishnan, R.; Mahmassani, HS; Hu, T-Y, An evaluation tool for advanced traffic information and management systems in urban networks, Transp. Res. Part C Emerg. Technol., 2, 129-147, 1994 · doi:10.1016/0968-090X(94)90005-1 |
| [27] | Krug, J.; Spohn, H., Universality classes for deterministic surface growth, Phys. Rev. A, 38, 4271, 1988 · doi:10.1103/PhysRevA.38.4271 |
| [28] | Kurzhanskiy, AA; Varaiya, P., Active traffic management on road networks: a macroscopic approach, Philos. Trans. R. Soc. A Math. Phys. Eng. Sci., 368, 1928, 4607-4626, 2010 · Zbl 1202.93010 · doi:10.1098/rsta.2010.0185 |
| [29] | Lebacque, J.: The Godunov scheme and what it means for first order traffic flow models. In: Proceedings of the 13th International Symposium on Transportation and Traffic Theory, Lyon, France, July, vol. 2426 (1996) |
| [30] | Lee, EB; Markus, L., Foundations of Optimal Control Theory, 1967, New York: Wiley, New York · Zbl 0159.13201 |
| [31] | Leonard, D., Gower, P., Taylor, N.: Contram: Structure of the Model. Transport and Road Research Laboratory (TRRL) Research Report 178, Department of Transport, Crowthorne (1989) |
| [32] | LeVeque, R.J.: Numerical Methods for Conservation Laws. Lectures in Mathematics ETH ZüRich, 2nd edn. Birkhäuser Verlag, Basel, Boston (1992) · Zbl 0847.65053 |
| [33] | Lighthill, M., Whitham, G.: On kinematic waves II. A theory of traffic flow on long crowded roads. In: Proceedings of Royal Society London (1955) · Zbl 0064.20906 |
| [34] | Malena, K.; Link, C.; Bußemas, L.; Gausemeier, S.; Trächtler, A.; Klein, C.; Jarke, M.; Helfert, M.; Berns, K.; Gusikhin, O., Traffic estimation and MPC-based traffic light system control in realistic real-time traffic environments, Smart Cities. Green Technologies, and Intelligent Transport Systems, 232-254, 2022, Cham: Springer, Cham · doi:10.1007/978-3-031-17098-0_12 |
| [35] | Manzo, R.; Piccoli, B.; Rarita, L., Optimal distribution of traffic flows in emergency cases, Eur. J. Appl. Math., 23, 4, 515-535, 2012 · Zbl 1460.90064 · doi:10.1017/S0956792512000071 |
| [36] | Materne, T.; Klar, A.; Günther, M.; Wegener, R.; Anile, AM; Capasso, V.; Greco, A., An explicit kinetic model for traffic flow, Progress in Industrial Mathematics at ECMI 2000, 597-601, 2002, Berlin: Springer, Berlin · doi:10.1007/978-3-662-04784-2_82 |
| [37] | Nagel, K.; Schreckenberg, M., A cellular automaton model for freeway traffic, J. Phys. I, 2, 12, 2221-2229, 1992 |
| [38] | Paveri-Fontana, SL, On Boltzmann-like treatments for traffic flow: a critical review of the basic model and an alternative proposal for dilute traffic analysis, Transp. Res., 9, 225-235, 1975 · doi:10.1016/0041-1647(75)90063-5 |
| [39] | Payne, H.J.: Model of freeway traffic and control. In: Mathematical Model of Public System, pp. 51-61 (1971) |
| [40] | Prigogine, I.; Resibois, P.; Herman, R.; Anderson, R., On a generalized Boltzmann-like approach for traffic flow, Bulletin de la Classe des Sciences. Académie royale de Belgique, 48, 9, 805-814, 1962 · Zbl 0272.90026 |
| [41] | Reilly, J.; Krichene, W.; Monache, MLD; Samaranayake, S.; Goatin, P.; Bayen, A., Adjoint-based optimization on a network of discretized scalar conservation law PDEs with applications to coordinated ramp metering, J. Optim. Theory Appl., 167, 733-760, 2015 · Zbl 1337.35161 · doi:10.1007/s10957-015-0749-1 |
| [42] | Richards, PI, Shock waves on the highway, Oper. Res., 4, 1, 42-51, 1956 · Zbl 1414.90094 · doi:10.1287/opre.4.1.42 |
| [43] | Shi, YF; Guo, Y., A maximum-principle-satisfying finite volume compact-WENO scheme for traffic flow model on networks, Appl. Numer. Math., 108, 21-36, 2016 · Zbl 1346.65043 · doi:10.1016/j.apnum.2016.05.001 |
| [44] | Treiber, M.; Hennecke, A.; Helbing, D., Congested traffic states in empirical observations and microscopic simulations, Phys. Rev. E, 62, 2, 1805, 2000 · doi:10.1103/PhysRevE.62.1805 |
| [45] | Treiber, M.; Kesting, A., Traffic Flow Dynamics, 2013, Berlin: Springer, Berlin · doi:10.1007/978-3-642-32460-4 |
| [46] | Wegener, R.; Klar, A., A kinetic model for vehicular traffic derived from a stochastic microscopic model, Transp. Theory Stat. Phys., 25, 7, 785-798, 1996 · Zbl 1467.82077 · doi:10.1080/00411459608203547 |
| [47] | Whitham, GB, Linear and Nonlinear Waves, 2011, Wiley |
| [48] | Wiedemann, R.: Simulation des strassenverkehrsflusses. Institute for Traffic Engineering, University of Karlsruhe, Technical Report (1974) |
| [49] | Wu, Y., Liu, L., Bae, J., Chow, K.-H., Iyengar, A., Pu, C., Wei, W., Yu, L., Zhang, Q.: Demystifying learning rate policies for high accuracy training of deep neural networks. In: 2019 IEEE International Conference on Big Data (Big Data), pp. 1971-1980. IEEE (2019) |
| [50] | Zhang, H., A non-equilibrium traffic model devoid of gas-like behavior, Transp. Res. Part B Methodol., 36, 3, 275-290, 2002 · doi:10.1016/S0191-2615(00)00050-3 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
