Tabu Search to Draw Evacuation Plans in Emergency Situations

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.

• S. Nasri
• H. Bouziri

• Dynamic network flow
• Load dependent transit time
• Evacuation strategy
• Earliest arrival flow problem.

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