×

Macroscopic evacuation plans for natural disasters. A lexicographical approach for duration and safety criteria: \(\mathrm{Lex}((Q|S)\mathrm{Flow})\). (English) Zbl 1371.90079

Summary: Since the 1990s, problems regarding the evacuation of persons have been extensively studied in the literature. The proposed models can be classified into two main categories: macroscopic and microscopic models. The DSS\(\_\)Evac\(\_\)Logistic project (2015, http://projets.li.univ-tours.fr/dssvalog/?lang=en) is interested in the evacuation of people in the context of flooding, burning or seismic events for which insecurity, capacity, and time to cross roads vary over time. We consider the problem of large-scale evacuation of medium-sized cities, in situations where the evacuees must change their place of residence for a period ranging from several days to several months. As a part of this project, we assume as solved the problem of selecting a set of starting points and shelter locations. We develop discrete macroscopic models and methods that incorporate the risk and safety that are inherent in the context studied for evacuating persons. The problem that needs to be addressed is to determine the minimum overall evacuation time while minimizing the risk incurred by evacuees (i.e., maximize the amount of unharmed persons). In this context, we first propose a pseudopolynomial method, which is based on the shortest augmenting paths, without using a time-expanded network to tackle the earliest arrival flow and the quickest flow problems no-wait with time-dependent data. Then, we extend this approach to consider the safety criterion.

MSC:

90B80 Discrete location and assignment
90B50 Management decision making, including multiple objectives
91B30 Risk theory, insurance (MSC2010)

Software:

OpenStreetMap
Full Text: DOI

References:

[1] Aronson JE (1989) A survey of dynamic network flows. Ann Oper Res 20(1):1-66 · Zbl 0704.90028 · doi:10.1007/BF02216922
[2] Baumann N (2007) Evacuation by earliest arrival flows. Ph.D. thesis · Zbl 1197.90001
[3] Baumann N, Skutella M (2009) Earliest arrival flows with multiple sources. Math Oper Res 34(2):499-512 · Zbl 1218.90166 · doi:10.1287/moor.1090.0382
[4] Borrmann A, Kneidl A, Köster G, Ruzika S, Thiemann M (2012) Bidirectional coupling of macroscopic and microscopic pedestrian evacuation models. Saf Sci 50(8):1695-1703 (Evacuation and Pedestrian Dynamics)
[5] Bretschneider S (2012) Mathematical models for evacuation planning in urban areas, vol 659. Springer Science & Business Media, Berlin · Zbl 1237.90036
[6] Burkard RE, Dlaska K, Klinz B (1993) The quickest flow problem. Z Oper Res 37(1):31-58 · Zbl 0780.90031
[7] Chalmet LG, Francis RL, Saunders PB (1982) Network models for building evacuation. Fire Technol 18(1):90-113. doi:10.1007/BF02993491 · Zbl 1260.90039
[8] Coutinho-Rodrigues JA, Tralhão L, Alçada-Almeida L (2012) Solving a location-routing problem with a multiobjective approach: the design of urban evacuation plans. J Trans Geogr 22:206-218 · Zbl 1253.90133
[9] Disser Y, Skutella M (2015) The simplex algorithm is np-mighty. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 858-872. SIAM · Zbl 1371.90081
[10] DSS_Evac_Logistic: Decision support system for large-scale evacuation logistics. http://projets.li.univ-tours.fr/dssvalog/?lang=en. Accessed 16 Nov 2015 · Zbl 1146.90014
[11] Fleischer L, Skutella M (2007) Quickest flows over time. SIAM J Comput 36(6):1600-1630 · Zbl 1146.90014 · doi:10.1137/S0097539703427215
[12] Ford L, Fulkerson DR (1962) Flows in networks, vol 1962. Princeton University Press, Princeton · Zbl 0106.34802
[13] Göttlich S, Kühn S, Ohst JP, Ruzika S, Thiemann M (2011) Evacuation dynamics influenced by spreading hazardous material. NHM 6(3):443-464 · Zbl 1260.90039 · doi:10.3934/nhm.2011.6.443
[14] Groß M, Skutella M (2015) A tight bound on the speed-up through storage for quickest multi-commodity flows. Oper Res Lett 43(1):93-95 · Zbl 1408.90049 · doi:10.1016/j.orl.2014.12.008
[15] Hamacher, H.; Heller, S.; Klein, W.; Köster, G.; Ruzika, S.; Peacock, RD (ed.); Kuligowski, ED (ed.); Averill, JD (ed.), A sandwich approach for evacuation time bounds, 503-513 (2011), US · doi:10.1007/978-1-4419-9725-8_45
[16] Hamacher HW, Tjandra SA (2002) Mathematical modeling of evacuation problems: a state of the art. In: Schreckenberg, M, Sharma SD (eds) Pedestrian and Evacuation Dynamics, pp 227-266. Springer, Berlin · Zbl 1048.90041
[17] Hamacher HW, Tjandra SA (2003) Earliest arrival flows with time-dependent data. Tech. Rep. 88, Fachbereich Mathematik—TU Kaiserslautern. https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1449. Accessed 16 Nov 2015
[18] Hoppe B, Tardos E (2000) The quickest transshipment problem. Math Oper Res 25(1):36-62 · Zbl 0977.90002 · doi:10.1287/moor.25.1.36.15211
[19] INSEE: Population data. http://www.insee.fr. Accessed 16 Nov 2015
[20] Jarvis JJ, Ratliff HD (1982) Notesome equivalent objectives for dynamic network flow problems. Manag Sci 28(1):106-109 · Zbl 0486.90042 · doi:10.1287/mnsc.28.1.106
[21] Klüpfel, H.; Meyer-König, T.; Wahle, J.; Schreckenberg, M.; Bandini, S. (ed.); Worsch, T. (ed.), Microscopic simulation of evacuation processes on passenger ships, 63-71 (2001), London · doi:10.1007/978-1-4471-0709-5_8
[22] Köhler E, Möhring RH, Spenke I (2008) Quickest flows: a practical model. Technische Universität, Berlin · Zbl 1196.90031
[23] Lämmel, G.; Klüpfel, H.; Nagel, K.; Peacock, RD (ed.); Kuligowski, ED (ed.); Averill, JD (ed.), Risk minimizing evacuation strategies under uncertainty, 287-296 (2011), US · doi:10.1007/978-1-4419-9725-8_26
[24] Lemoine A, Bernardie S, Brivois O, De Martin F, Desramaut N, Le Roy S, Monfort Climent D, Negulescu C, Pedreros R, Sedan O, Chan Vong Q, Vagner A, Foerster E (2014) Ligurian earthquake: Seismic and tsunami scenario modeling, from hazard to risk assessment towards evacuation planning. In: 2nd European conference on earthquake engineering and seismology : 2ECEES 2014. Istanbul, Turkey
[25] Miller-Hooks E, Patterson SS (2004) On solving quickest time problems in time-dependent, dynamic networks. J Math Modell Algorithms 3(1):39-71 · Zbl 1048.90048 · doi:10.1023/B:JMMA.0000026708.57419.6d
[26] Opasanon S, Miller-Hooks E (2009) The safest escape problem. J Oper Res Soc 60(12):1749-1758 · Zbl 1196.90031 · doi:10.1057/jors.2008.122
[27] OpenStreetMap: Openstreetmap data for provence alpes-cote-d’azur (including nice city). http://download.geofabrik.de/europe/france/provence-alpes-cote-d-azur.html. Accessed 16 Nov 2015 · Zbl 1218.90166
[28] OpenStreetMap: Openstreetmap website. http://openstreetmap.fr. Accessed 16 Nov 2015 · Zbl 0747.90104
[29] Powell WB, Jaillet P, Odoni A (1995) Stochastic and dynamic networks and routing. Handb Oper Res Manag Sci 8:141-295 · Zbl 0870.90059 · doi:10.1016/S0927-0507(05)80107-0
[30] Rosen JB, Sun SZ, Xue GL (1991) Algorithms for the quickest path problem and the enumeration of quickest paths. Comput Oper Res 18(6):579-584 · Zbl 0747.90104 · doi:10.1016/0305-0548(91)90063-W
[31] Schmidt M, Skutella M (2014) Earliest arrival flows in networks with multiple sinks. Discrete Appl Math 164:320-327 · Zbl 1326.90014 · doi:10.1016/j.dam.2011.09.023
[32] Tjandra SA (2003) Dynamic network optimisation with application to the evacuation problem. Ph.D. thesis
[33] Wayne KD (1999) Generalized maximum flow algorithms. Ph.D. thesis, Citeseer
[34] Yuan F, Han LD (2010) A multi-objective optimization approach for evacuation planning. Proc Eng 3:217-227 · doi:10.1016/j.proeng.2010.07.020
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.