Distributed genetic algorithm for disaster relief planning
Keywords:
Vehicle Routing Problem, multi-agent system, genetic algorithm, emergency, disaster reliefAbstract
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
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
