Distributed genetic algorithm for disaster relief planning

Kamel Zidi, Fethi Mguis, Pierre Borne, Khaled Ghedira

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.

Keywords


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

Full Text:

PDF

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.




DOI: https://doi.org/10.15837/ijccc.2013.5.401



Copyright (c) 2017 Kamel Zidi, Fethi Mguis, Pierre Borne, Khaled Ghedira

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

CC-BY-NC  License for Website User

Articles published in IJCCC user license are protected by copyright.

Users can access, download, copy, translate the IJCCC articles for non-commercial purposes provided that users, but cannot redistribute, display or adapt:

  • Cite the article using an appropriate bibliographic citation: author(s), article title, journal, volume, issue, page numbers, year of publication, DOI, and the link to the definitive published version on IJCCC website;
  • Maintain the integrity of the IJCCC article;
  • Retain the copyright notices and links to these terms and conditions so it is clear to other users what can and what cannot be done with the  article;
  • Ensure that, for any content in the IJCCC article that is identified as belonging to a third party, any re-use complies with the copyright policies of that third party;
  • Any translations must prominently display the statement: "This is an unofficial translation of an article that appeared in IJCCC. Agora University  has not endorsed this translation."

This is a non commercial license where the use of published articles for commercial purposes is forbiden. 

Commercial purposes include: 

  • Copying or downloading IJCCC articles, or linking to such postings, for further redistribution, sale or licensing, for a fee;
  • Copying, downloading or posting by a site or service that incorporates advertising with such content;
  • The inclusion or incorporation of article content in other works or services (other than normal quotations with an appropriate citation) that is then available for sale or licensing, for a fee;
  • Use of IJCCC articles or article content (other than normal quotations with appropriate citation) by for-profit organizations for promotional purposes, whether for a fee or otherwise;
  • Use for the purposes of monetary reward by means of sale, resale, license, loan, transfer or other form of commercial exploitation;

    The licensor cannot revoke these freedoms as long as you follow the license terms.

[End of CC-BY-NC  License for Website User]


INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL (IJCCC), With Emphasis on the Integration of Three Technologies (C & C & C),  ISSN 1841-9836.

IJCCC was founded in 2006,  at Agora University, by  Ioan DZITAC (Editor-in-Chief),  Florin Gheorghe FILIP (Editor-in-Chief), and  Misu-Jan MANOLESCU (Managing Editor).

Ethics: This journal is a member of, and subscribes to the principles of, the Committee on Publication Ethics (COPE).

Ioan  DZITAC (Editor-in-Chief) at COPE European Seminar, Bruxelles, 2015:

IJCCC is covered/indexed/abstracted in Science Citation Index Expanded (since vol.1(S),  2006); JCR2018: IF=1.585..

IJCCC is indexed in Scopus from 2008 (CiteScore2018 = 1.56):

Nomination by Elsevier for Journal Excellence Award Romania 2015 (SNIP2014 = 1.029): Elsevier/ Scopus

IJCCC was nominated by Elsevier for Journal Excellence Award - "Scopus Awards Romania 2015" (SNIP2014 = 1.029).

IJCCC is in Top 3 of 157 Romanian journals indexed by Scopus (in all fields) and No.1 in Computer Science field by Elsevier/ Scopus.

 

 Impact Factor in JCR2018 (Clarivate Analytics/SCI Expanded/ISI Web of Science): IF=1.585 (Q3). Scopus: CiteScore2018=1.56 (Q2); Editors-in-Chief: Ioan DZITAC & Florin Gheorghe FILIP.