Distributed genetic algorithm for disaster relief planning

  • Kamel Zidi Science Faculty of Gafsa, university of Gafsa Campus Universitaire Sidi Ahmed Zarrouk 2112 Gafsa, Tunisia
  • Fethi Mguis Higher Management School of Tunis, University of Tunis
  • Pierre Borne Ecole Centrale de Lille
  • Khaled Ghedira SOIE, University of Tunis


The problem studied in this paper is the management of vehicle routing in case of emergency. It is decomposed into two parts. The first one deals with the emergency planning in the event of receiving a set of requests for help after a major disaster such as in the case of an earthquake, hurricane, flood, etc. The second part concerns the treatment of contingency as the arrival of a new request or the appearance of a disturbance such as breakdowns of vehicles, the malfunction of roads, availability of airports, etc. To solve this problem we proposed a multi-agents approach using a guided genetic algorithm for scheduling vehicle routing and local search for the management of contingencies. The main objectif of our approach was to maximizing the number of saved people and minimizing the costs of the rescue operation. This approach was tested with the modified Solomon benchmarks and gave good results.


Adinolfi, C. et al (2005); Humanitarian response review, An independent report commissioned by the United Nations Emergency Relief Coordinator \& Under-Secretary-General for Humanitarian Affairs, Office for the Coordination of Humanitarian Affairs (OCHA), New York and Geneva.

Afshar, A.; Haghani, A. (2012); Modeling integrated supply chain logistics in real-time large-scale disaster relief operations, Socio-Economic Planning Sciences, 46(4): 327-338.

Baer, M. et al (2005); Safe: the race to protect ourselves in a newly dangerous world, New York: HarperCollins.

Balcik, B. et al (2008); Last mile distribution in humanitarian relief, Journal of Intelligent Transportation Systems, 12(2): 51-63.

Bent, R.; Hentenryck, P.V.(2004); Scenario-based planning for partially dynamic vehicle routing with stochastic customers, Operations Research

Beresford, A.; Rugamba, A. (1996); Evaluation of the transport Sector in Rwanda, Geneva: UNCTAD.

Boudali, I. et al (2005); An Interactive Distributed Approach for the VRP with Time Windows, Journal of Simulation Systems, Science and Technology.

Burg, S.; Shoup, P. (1999); The war in BosniaeHerzegovina: ethnic conflict and international intervention, Armonk, NY: M.E Sharpe.

Campbell, A.M.; Savelsbergh M.W.P. (2004); A decomposition approach for the inventory-routing problem, Transportation Science, 38: 488-502.

Cheng, C.B.; Wang, K.P. (2009); Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm, Expert Systems with Applications 36: 7758-7763

Coello, C. (2001); A short tutorial on evolutionary multi-objective optimization, Computer Science, 1993: 21-40.

Fritz Institute (2005); Lessons learned: recipient perceptions of aid effectiveness: rescue, relief and rehabilitation in tsunami affected Indonesia, India and SriLanka, San Francisco, CA: Fritz Institute.

Goldberg, D. (1989); Genetic algorithms in search, optimization, and machine learning, Advison-Wesley.

Harbaoui, D.I. et al (2011), Multi-Objective Optimization for the m-PDPTW: Aggregation Method With Use of Genetic Algorithm and Lower Bounds, International Journal of Computers Communications \& Control, ISSN 1841-9836, 6(2):246-257.

Holland, J. (1975); Adaptation in natural and artificial systems, Tech. rep., University of Michigan Press, Ann Arbor, Canberra ACT 2601, Australia.

Hong, L.(2011); An improved LNS algorithm for real-time vehicle routing problem with time windows, Computers and Operations Research.

Kefi, G.M.; Ghedira, K.; (2004); A Multi-Agent Model for a Vehicle Routing Problem with Time Windows, Urban Transport Conference, Dresden-Allemagne.

Kovacs, G.; Spens, K. (2007); Humanitarian logistics in disaster relief operations, International Journal of Physical Distribution and Logistics Management, 36(2): 99-114.

Long, D.; Wood, D. (1995); The logistics of famine relief, Journal of Business Logistics, 16(1): 213-229.

Ma, X. et al (2010); Min-max robust optimization for the wounded transfer problem in large-scale emergencies, Control and Design Conference, China.

McClintock, A. (2009); The logistics of humanitarian emergencies: notes from the field, Journal of Contingencies and Crisis Management, 17(4): 295-302.

McEntire, D. (1999); Issues in disaster relief: progress, perpetual problems and prospective solutions, Disaster Prevention and Management, 8(5): 351-361.

McGuire, G.(2000); Supply chain management in the context of international humanitarian assistance in complex emergencies, Supply Chain Practice, 2(4): 30-43.

Mguis, F. et al (2012); Modlisation dun systme multi-agent pour la rsolution dun problme de tournes de vhicules dans une situation durgence, in: 9me Confrence Internationale de Modlisation, Optimisation et SIMulation MOSIM12, Bordeaux, France.

Mguis, F. et al (2012); Distributed approach for vehicle routing problem in disaster case, 13th IFAC Symposium on Control in Transportation Systems, Sofia-Bulgaria.

Mguis, F. et al (2013); Guided genetic algorithm for the dynamic management of emergency planning for disaster, Internationnal conference of Information Technology and Quantitative Management, Suzhou-China.

Oh, S.; Haghani, A.; (1997); Testing and evaluation of a multi-commodity multi-modal network flow model for disaster relief management, Journal of Advanced Transportation 31: 249–282.

Oloruntoba, R.; Gray, R. (2009); Customer service in emergency relief chains, International Journal of Physical Distribution and Logistics Management, 39(6): 486-505.

Oloruntoba, R.A. (2010); Documentary analysis of the cyclone Larry emergency relief chain: some key success factors, International Journal of Production Economics, 126(1): 85-101.

Ozdamar, L. (2011); Planning helicopter logistics in disaster relief, OR Spectrum 33: 655-672.

Ozdamar, L.; Demir, O. (2012); A hierarchical clustering and routing procedure for large scale disaster relief logistics planning. Transportation Research Part E; Logistics and Transportation Review 48: 591-602.

Perry, M. (2007); Natural disaster management planning: a study of logistics managers responding to the tsunami, International Journal of Physical Distribution \& Logistics Management, 37(5): 409-433.

Petitt, S.; Beresford, A. (2005); Emergency relief logistics: an evaluation of military, nonmilitary and composite response models, International Journal of Logistics: Research and Applications, 8: 313-331.

Psaraftis, H.N. (1988); Dynamic vehicle routing problems, Vehicle routing: methods and studies, Elsevier Science Publishers B.V.: 293-318.

Psaraftis, H.N. (1995); Dynamic vehicle routing: Status and prospects, Annals of Operations Research: 143-164.

Quarantelli, E. (1982); Ten research derived principles of disaster planning, Disaster Management, 2: 23-26.

Quarantelli, E. (1998); What is a disaster, London: Routledge.

Rosenthal, U. et al (1989); Coping with crises: the management of disasters, riots and terrorism. Springfield, IL: Charles C. Thomas Publishers.

Savvaidis, P.et al (2002); Organization of emergency response after a major disaster event in an urban area with the help of an automatic vehicle location and control system, GPS Solutions, 5(4): 70-79.

Solomon, M. (1987); Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research 35(2): 254-265.

Tzeng, G.H.et al (2007); Multi-objective optimal planning for designing relief delivery systems, Transportation Research Part E: Logistics and Transportation Review 43: 673-686.

Yi, W.; Kumar, A. (2007); Ant colony optimization for disaster relief, operations, Transportation Research Part E: Logistics and Transportation Review 43 (6): 660-672.

Zeddini, B.; Zargayouna M. (2009); Auto-organisation spatio-temporelle pour le VRPTW dynamique, RJCIA.

Zhang, J.H.et al (2012); Multiple-resource and multiple-depot emergency response problem considering secondary disasters, Expert Systems with Applications 39, 11066-11071.

Zidi, I. et al (2011); A Multi-Agent System based on the Multi-Objective Simulated Annealing Algorithm for the Static Dial a Ride Problem, 18th World Congress of the International Federation of Automatic Control (IFAC), Milan (Italy).

Zidi, K. (2006); Système Interactif d'Aide au Déplacement Multimodal, Thèse de doctorat Ecole centrale de Lille France.
How to Cite
ZIDI, Kamel et al. Distributed genetic algorithm for disaster relief planning. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 8, n. 5, p. 769-783, sep. 2013. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/401>. Date accessed: 25 nov. 2020. doi: https://doi.org/10.15837/ijccc.2013.5.401.


Vehicle Routing Problem; multi-agent system; genetic algorithm; emergency; disaster relief