Tabu Search to Draw Evacuation Plans in Emergency Situations

Authors: S. Nasri, H. Bouziri

Abstract:

Disasters are quite experienced in our days. They are caused by floods, landslides, and building fires that is the main objective of this study. To cope with these unexpected events, precautions must be taken to protect human lives. The emphasis on disposal work focuses on the resolution of the evacuation problem in case of no-notice disaster. The problem of evacuation is listed as a dynamic network flow problem. Particularly, we model the evacuation problem as an earliest arrival flow problem with load dependent transit time. This problem is classified as NP-Hard. Our challenge here is to propose a metaheuristic solution for solving the evacuation problem. We define our objective as the maximization of evacuees during earliest periods of a time horizon T. The objective provides the evacuation of persons as soon as possible. We performed an experimental study on emergency evacuation from the tunisian children’s hospital. This work prompts us to look for evacuation plans corresponding to several situations where the network dynamically changes.

Keywords: Dynamic network flow, Load dependent transit time, Evacuation strategy, Earliest arrival flow problem.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1096233

References:

[1] M. Anisuddin Nasir, L. Severien, and E. Dimogerontakis. (2014).Tabu Search Optimization of Data Distribution in P2P Networks (Online). Available: http://web.ict.kth.se/ emmdim/docs/tabu.pdf
[2] N. Baumann, and E. Kohler, ”Approximating earliest arrival flows with flow dependent transit times,” Elsevier. Discrete Applied Mathematics,vol. 155, pp. 161–171, Jan. 2007.
[3] N. Baumann, ”Evacuation by Earliest Arrival Flows,” Ph.D. dissertation, Fachb.Math.,Dortumund Univ., Aus Potsdam, 2007.
[4] N. Baumann, and M. Skutella, ”Solving Evacuation Problems Efficiently: Earliest Arrival Flows with Multiple Sources,” 47th Annual IEEE Symposiumon Foundations of Computer Science, FOCS 2006, Berkeley, CA,pp. 399–410, Oct. 2006.
[5] R.E. Burkard, K. Dlaska, and B. Klinz.(2007, Feb.).Quickest Flow over time. SIAM Journal on Computing (Online). 36(6), pp. 1600-1630. Available:http://researchweb.watson.ibm.com/people/l/lkf/papers/FS2.p df
[6] K. Bettina, and J. Gerhard, ”Minimum-cost dynamic flows: The series parallel case,” Wiley Periodicals. Networks, vol. 43, pp. 153-162, May.2004.
[7] R. Challenger, C.W. Clegg, and M.A. Robinson, Understanding Crowd Behaviours, Practical Guidance and Lessons Identied. Researcher in Organisational Psychology., London, TSO Rep. 1161–CB, 2010.
[8] L.R. Ford, D.R. Fulkerson, and D.R, ”Constructing maximal dynamic flows from static flows”, Springer. Operations Research, vol. 6, pp. 419- 433, May. 1958.
[9] F. Glover. (1989, Summer.). Tabu Search Part I. Informs Journal on computing (Online). 1(3),pp. 190–206. Available: http://www.pubsonline.informs.org
[10] D. Gale. (1959). Transient flows in networks. The Michigan Mathematical Journal (Online). 6(1), pp. 59–63.Available: http://projecteuclid.org/euclid.mmj/1028998140
[11] M. Gendreau, A. Hertz, G. Laporte. (1994, Oct.). A tabu search heuristic for the vehicle routing problem. Management Science (Online). 40(10), pp. 1276–1290. Available: http://www.jstor.org/stable/2661622
[12] B. Hoppe, and E. Tardos. (2000, Feb.).The quickest transshipment problem. Mathematics of Operations Research (Online). 25(1), pp. 36- 62.Available: http://hdl.handle.net/1813/9000
[13] H.W. Hamacher, and S.A. Tjandra. (2000). Mathematical modeling of evacuation problems: A state of the art. Pedestrian and Evacuation Dynamics (Online). pp. 227–266. Available: https://kluedo.ub.unikl.de/files/1477/bericht24.pdf
[14] E. Minieka, ”Maximal lexicographic and dynamic network flows,”Informs. Operations Research, vol. 21, pp. 517-527, Apr. 1973.
[15] F. Rita, ”An Evacuation Model for High Rise Buildings,” in Proc. 3thInter. Symposium in Fire Safety Science Conf. Scotland, 1991, pp. 815–823.
[16] Y. Shengxiang, J. Yong, and N. Trung.(2012, Oct.).Metaheuristics for Dynamic Combinatorial Optimization Problems. Journal of Management Mathematics (Online). 24, pp. 1–29. Available: http://www.tech.dmu.ac.uk/ syang/ECiDUE/Yang-IMAMAN13.pdf
[17] P. Stefano, and M. Skutella, ”Shortest Path algorithms in transportation models: Classical and innovative aspects,” C.N.R. Res. Lab., Pisa Italia.TR-97-06 (II), 1997.
[18] S. Jayaswal, ”A Comparative Study of Tabu Search and Simulated Annealing for Traveling Salesman Problem,” Proj. Rep. Appl. Opt. Univ.Water., Canada. MSCI-703, (2008).
[19] Y. Sheffi, Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice-Hall, Englewood Cliffs,New Jersey, 1985.
[20] S.A. Tjandra, ”Dynamic network optimization with application to the evacuation problem,” Ph.D. dissertation, Dept. Fach. Math., Kaiserslautern Univ.,Genehmigte, 2003.
[21] R. Stefan, S. Heika, and S. Mechthid, ”Earliest arrival flows on series parallel graphs” Wiley Online Library. Networks, vol. 57, pp. 169-173, Mar. 2011.
[22] W. Bein, and P. Brucker, ”Minimum cost flow algorithms for series parallel networks” Elsevier. Discrete Applied Mathematics, vol. 10, pp.117-124, Feb. 1985.