Distributed genetic algorithm for disaster relief planning

Authors

  • 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

Keywords:

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

Abstract

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.

References

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. http://dx.doi.org/10.1016/j.seps.2011.12.003

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. http://dx.doi.org/10.1080/15472450802023329

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. http://dx.doi.org/10.1287/trsc.1030.0054

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 http://dx.doi.org/10.1016/j.eswa.2008.09.001

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. http://dx.doi.org/10.1111/j.1468-5973.2009.00587.x

McEntire, D. (1999); Issues in disaster relief: progress, perpetual problems and prospective solutions, Disaster Prevention and Management, 8(5): 351-361. http://dx.doi.org/10.1108/09653569910298279

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. http://dx.doi.org/10.1002/atr.5670310304

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

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. http://dx.doi.org/10.1016/j.ijpe.2009.10.013

Ozdamar, L. (2011); Planning helicopter logistics in disaster relief, OR Spectrum 33: 655-672. http://dx.doi.org/10.1007/s00291-011-0259-y

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. http://dx.doi.org/10.1016/j.tre.2011.11.003

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. http://dx.doi.org/10.1007/BF02098286

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. http://dx.doi.org/10.1007/PL00012913

Solomon, M. (1987); Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research 35(2): 254-265. http://dx.doi.org/10.1287/opre.35.2.254

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. http://dx.doi.org/10.1016/j.tre.2006.10.012

Yi, W.; Kumar, A. (2007); Ant colony optimization for disaster relief, operations, Transportation Research Part E: Logistics and Transportation Review 43 (6): 660-672. http://dx.doi.org/10.1016/j.tre.2006.05.004

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. http://dx.doi.org/10.1016/j.eswa.2012.03.016

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.

Published

2013-09-17

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.