INT J COMPUT COMMUN, ISSN 1841-9836 8(5):769-783, October, 2013. Distributed Genetic Algorithm for Disaster Relief Planning K. Zidi, F. Mguis, P. Borne, K. Ghedira Kamel Zidi Science Faculty of Gafsa, university of Gafsa Campus Universitaire Sidi Ahmed Zarrouk 2112 Gafsa, Tunisia kamel_zidi@yahoo.fr Fethi Mguis*, Khaled Ghedira Higher Management School of Tunis, University of Tunis 41, Rue de la liberté Bouchoucha le Bardo 2000, Tunisia *Corresponding author: fethi.mguis@fsg.rnu.tn khaled.ghedira@isg.rnu.tn Pierre Borne Ecole Centrale de Lille Villeneuve d’ascq 59650, France pierre.borne@ec-lille.fr 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, emer- gency, disaster relief. 1 Introduction Although there were several studies in the field of vehicle dynamics deals with the problem of the distribution (eg, [9]- [34]- [35]- [39]). However, most of the available research has focused on commercial transport, logistics planning in supply chain repetitive, and routine treatments and environments orders [4]. Studies dealing with vehicle routing problems as the dynamic response planning and logistics of disaster relief were few. The objective of this work was to propose a distributed approach based on a genetic algorithm for modeling and solving the problem of contingency planning in case of disaster. Our approach enables a planning disaster relief distribution by maximizing the number of people saved, avoiding delays in the relief distribution and maximizing the useful equipment life which saves costs. In section 2, we have presented the problems and the aims of this work; while section 3 presented a literature overview dealing with the problem of emergency planning for disaster. In the section four highlighted and described the proposed approach. In the last tow sections, we have discussed tests of calculation and managerial implications arising from the study, and we have summarized the work, by presenting findings and suggesting further alternatives. Copyright c⃝ 2006-2013 by CCC Publications 770 K. Zidi, F. Mguis, P. Borne, K. Ghedira 2 Problematic and Aims As the world continue to witness the vulnerability of natural and artificial disasters on hu- man well-being is constantly under threat (eg, [3] [22] [36] [37]). For example, about two million people were affected by the Haitian earthquake of January 2010, the Haitian government have reported that an entire nation of 230,000 people had died, 300,000 were injured and 1,000,000 made homeless [47]. Furthermore about 250,000 homes and 30,000 commercial buildings were collapsed or were severely damaged [47]. Similarly, the earthquake of 2008 in China killed more than 67,000 people. In 2008 Cyclone Nargis killed more than 78,000 in Myanmar [28], the Kash- mir earthquake in Pakistan in 2005 killed more than 86,000 people and Katrina Hurricane killed more than 1,000 person with damages of billions of dollars [21]. In fact, Disasters and crises are often characterized by massive displacement of people, lack of food and water, degradation of essential services, damage to infrastructure, unsatisfactory ware- housing capacity, inadequate transportation and inaccessibility to remote areas [28] [29]. Add to this, other challenges include the difficulty in assessing the needs and expectations of victims (human resources management), insufficient relief or quantity transported and delivered as well as issues of inter-agency coordination. Often, disaster response was characterized by excessive centralization and short-term nature of the emergency chain coupled with a lack of reliable information [1] [18] [28]. In addition, sources the supply distribution nodes, and extended distribution points must be quickly putted in place, sometimes because of the topographical difficult situations of pickups and deliveries [6] [19]. In several times, organizations and agencies have negotiated with governments and administrations, military access, municipal authorities and organizations [4] [33], therefore, it appeared that crises and disasters create circumstances and extraordinary conditions for those who seek to manage relief and rescue operations. These actors must take urgent decisions while essential information on the causes. Thus, consequences remain unavailable and the degree of uncertainty is high [38]. Despite this difficult environment disaster with rapid change, and the efforts of charities, aid agencies and governments, stakeholders such as emergency beneficiaries [12] [23] [32] as well as the media [8] [48] have criticized how the relief was distributed and the disaster relief chains were managed. It’s the case of inefficiency, waste, and lack of planning and logistical capacity limited disaster were cited. These criticisms, were also applied to the disaster relief operations, for example, in the aftermath of Hurricane Katrina in 2005. Such an investigation was crucial for improving real-time response and effectively to the conse- quences of disasters as well. Other crises where relief goods such as water, food, first aid and so must be rapidly distributed to reduce human suffering and save lives. In others words, the nature of a disaster, especially with regard to the availability of infrastructure logistics, warning, scale, location, topography and resources have an impact on the design plans and emergency response, as well as the mixture of the allocation of resources [33]. It appeared that, some parameters must be taken into consideration to better understand the situation of the typical distribution of disaster relief. Resources of the fleet of vehicles and emergency equipment were generally insufficient; the affected area was often a poor logistics infrastructure (eg, bad and damaged roads , warehouses, ports, etc.) and desperate people who may be dispersed to different nodes (feeding sites and/or distribution) over a large area. There- fore, it is difficult for both relief workers and logisticians to rapidly develop effective and efficient distribution plans [4] [34] [35]. Second, fleet management with interest on routing, planning, pickup and delivery are often the main decisions to be taken by the logisticians and the relief’s effective allocation and satisfac- tion of requests place were also to be taken in consideration. These decisions are important for the distribution of relief because of "life or death." This requires fast delivery with strict limits Distributed Genetic Algorithm for Disaster Relief Planning 771 required by donors and financial accountability reports. Hence the need for an efficient routing and planning essential to the effectiveness of relief programs. 3 Literature Review In recent years, the problems of disaster emergency management have attracted more and more the researchers’s attention. This was due to their importance for human, economy and society. Indeed, some approaches have been proposed for modeling and solving this problem. Oh and Haghani [27] modeled the problem as a linear program by considering only how minimizing the cost. However, Tzeng [41] developed a heuristic based on linear program in which they took into account the human and the cost; while Yi [42] proposed an approach based on ACO meta- heuristic modeling with linear program witch consider only the human side of the problem. in same way Ozdamar [30] proposed a modeling of the problem as a linear program. Furthermore, he also proposed a modeling of the problem as a linear program in which they took into account the human side and they have developed a heuristic to solve the problem [31]. In contrast, Ma [20] proposed an exact method using a nonlinear program by considering the human goal only. This was similar to some extend, Afshar [2] is based on an exact method to solve the problem by modeling as a linear program that takes into account the human side. Zhang [44] developed a heuristic which considers the minimization of cost. To conclude, we can say that: • Most approaches do not take into account the aspect of multi-objective problem. • The majority of available studies dealing with static problems ignore the dynamic aspect of the problem. • The meta-heuristics were less used despite they were more efficient especially with this kind of problem since they require a short response time with a number of exponential data. • All the approaches developed did not include forecasts to predict future requests for help. In fact, in the disaster case, forecasting future demands have allowed to avoid certain circumstances and reduce the damage to human and material. • Distributed approaches were almost absent despite their great performance for modeling and solving problems similar to the problem addressed herein(eg, [25]- [24]- [45]- [43]- [7]- [17]- [10]- [14]). 4 Proposed Approach In order to solve the above described problem, we propose a multi-agent model as developed by Zidi [46] to which we were add some features that we suspect necessary for the proper func- tioning of the system to adequately address the problem. Our model as described in Figure 1 was composed by a "System Agent" and a set of "Zone Subsystems". The "System Agent" has to create and supervise all other agents. Each "Zone Subsystems" was composed of a "Plan- ning Subsystem", an "Area Manager Agent", "Information Manager Agent", "Forecast Agent", "Disturbance Agent", and a local database. The "Zone Subsystem" was managed by the "Area Manager Agent" which provides communication with the "System Agent" and other "Zone Sub- systems". The "Information Manager Agent" was responsible for the management of information 772 K. Zidi, F. Mguis, P. Borne, K. Ghedira necessary for the proper conduct of the rescue operation. In fact it provides information collec- tion, their filtration, and updates the local database. The "Forecast Agent" allowed forecasting of emergency calls based on the information received and based on historical relief interventions. The "Disturbance Agent" will be used to detect disturbances that can occur, transmit "Planning Subsystem" to be processed. The "Planning Subsystem" was responsible for emergency planning, integration of new applications and correction planning in case of a disturbance. The "Planning Subsystem" was composed of three types of agents namely "Supervisor Agent" who supervises the other components in addition to its roles in the "Planning Subsystem". The role of "Vehicle Agent" is finding a path for a vehicle. The "Interface Agent" handles communication with the external environment. The local database of "Zone Subsystem" will be used to store all data in the backup area. Each "Zone Subsystem" can communicate with the external environment mainly composed by: applicants emergency disaster, relief agencies, the geographic information system GIS, news and weather agencies. Figure 1: Overview of the system 4.1 The Planning Subsystem The subsystem of planning presented in Figure 2 was composed of three types of agents: Supervisor, Interface and Vehicle. Supervisor Agent This agent ensures the consolidation of emergency calls, the creation of tenders for the in- sertion of a new application, choose the best solution and update planning after any changes generated by the insertion of a new application or by the occurrence of a disturbance. Interface Agent This agent was responsible for all information exchanged between the "Planning Subsystem" and its external environment. It was responsible for receiving requests for help formatting, negotiating with transport operators and information from stakeholders. Distributed Genetic Algorithm for Disaster Relief Planning 773 Vehicle Agent Each vehicle agent was responsible for a vehicle. It has to ensure that the search path will be followed by the vehicle. In addition to receiving a bid for the insertion of a new request, the agent "Vehicle" checks can add this request and sets its offer, which sends it to the "Supervisor Agent". Figure 2: Subsystem of planning Agents Communications We identify ten types of communication messages between agents of "Planning Subsystem". These messages were: "Request" was sent by the "Interface Agent" to the agent "Supervisor" upon receipt of a new request for help. After processing a new application, a "Request Response" was sent by the "Supervisor Agent" to the "Interface Agent". When receiving an announcement of a disturbance, a message "Disturbance" has to be sent by the "Interface Agent" to the "Su- pervisor Agent". After treatment of the disturbance, a message "Solution of disturbance" which was sent by the "Supervisor Agent" to "Interface Agent". After the consolidation of emergency requests, messages "Group requests" were sent by the "Supervisor Agent" to "Vehicle Agents". After searching for a path, a message "Path" was sent by the "Vehicle Agent" to the "Supervisor Agent". Following the receipt of a new request messages "Tender" were sent by the "Supervi- sor Agent" to "Vehicle Agents". After the establishment of an offer to insert a new request, a message "Offer" was sent by a "Vehicle Agent" to "Supervisor Agent". In order to improve the quality of its way, a "Vehicle Agent" can send a message "Negotiation" to the other "Vehicle Agent". Communications between the different agents were presented in Figure 3. Emergency Planning Emergency planning starts by grouping the applications according to their types, their loca- tions, their degrees of urgency, their quantities, and their time windows. Then each group will be assigned to an "Vehicle Agent" which was responsible for finding the right path according to a heuristic which sort the requests in ascending order according to their service termination dates. In the of equality case the customer closest to the preceding customer has to be selected. This creates an initial population for a genetic algorithm executed by the "Supervisor Agent" altogether with the "vehicle Agent". At the end a we got the final population of the solutions 774 K. Zidi, F. Mguis, P. Borne, K. Ghedira Figure 3: Protocols diagram for planning from which the "Supervisor Agent" have to chose one of them to be followed for the planning of the rescue operation. Genetic Algorithm The real universal problems, including disaster cases has inevitably some unknown and un- certain parameters. Stochastic programming seems to be the most appropriate to solve this problems, while it requires probability distributions for the estimate data. The solution com- puted should be valid for the majority of possible realities and the expected value of the objective function was optimized. Our challenge was to propose an alternative approach to provide prob- ability distributions. If the deviations were within certain limits, our idea was to find the valid solution, even if small changes may occurs. Therefore, the desired visits should be robust and flexible. However, these terms were often used with different meanings; hence we will define this terms to be used later in this document: • Robustness: if a change in travel time or a new customer request arrives, only minor changes were needed in the planning. • Flexibility: it will keep the schedule, because the generated plan has several options. Therefore, a right option was to solve a stochastic model that was particularly difficult to solve in a certain period. Alternatively, it is possible to solve a deterministic model with additional constraints to create a robust and similar flexibility. Therefore, a similar performance with less efforts calculation can be performed. So with such problem, the approximate methods have proved more effective resolution. In fact, they allow to obtain acceptable solutions in a reasonable time. Among the approximate methods the most used wre the genetic algorithms that provide solutions which guaranteed robustness and flexibility. The fundamental principles of these algorithms have been incurred by Holland [15]. These algorithms are based on the functioning of the natural evolution of species, including the selection of Darwin and Mendel procreation. They have been successfully used to solve several problems of multi-criteria optimization [11]. In genetic algorithms, we simulate the process of evolution of a population. One starts with an initial population composed of N solutions (individuals) of the problem. The degree of adaptation of an individual to the environment is expressed by the value of the cost function f (x), where x is the solution that is the individual. It is said that a person is much better adapted to its environment, the cost of the solution is lower or larger depending on test selected optimization. Distributed Genetic Algorithm for Disaster Relief Planning 775 Within this population, occurs when the random selection of one or both parents, producing a new solution, through genetic operators such as crossover and mutation. The new population is obtained by the choice of N individuals among populations (parents and children) is called next generation. By iterating the process, we produce population richer individuals best suited. The process of the genetic algorithm is presented in Figure 4. For success and the convergence of the Figure 4: Functioning of the genetic algorithm genetic algorithm requires: • Make a good representation (encoding) of a solution (chromosome) • choose the manufacturer of the original solution, • clearly define the evaluation function to determine the fitness of each individual • choose the methods of selection, crossover and mutation are best suited to the problem and • carefully choose the parameter values: population size, probabilities, etc.. Coding: Because the chromosomes are not binary adopted for sequencing problems, it has adopted an actual coding where the chromosome is a sequence of nodes (excluding the deposit). Figure 5 shows a chromosome of a problem consists of 10 clients. Creation of the initial population: To build the initial population, we have developed a heuristic which builds the first half of the population randomly and the second half in a guided manner based on the method of insertion of Solomon [40]. Selection: To select the chromosomes (solutions) that will be able to contribute to the creation of the new population, we adopted the method of selection of Wheel [15] [13] which consists in assigning to each individual a probability of selection proportional to its evaluation (fitness) and the sum of the evaluations of individuals. The selection process is shown by the following algorithm: 1. Calculating the fitness fi for each individual of the population 776 K. Zidi, F. Mguis, P. Borne, K. Ghedira Figure 5: Example of an individual 2. Calculating the probability Pi of selection of each individual Pi = fi/ ∑i=n i=1 fi 3. Calculation of cumulative probability qi of each individual qi = ∑i j=1 pj 4. Generate a random value r ∈ [0,1] 5. If r < q1 then select the first individual else choose individual i as: qi−1 < r ≤ qi 6. Repeat steps 4 and 5 to create the desired number of individual Crossover: From both parents (solutions), we try to generate one or two son. There are several breeding techniques. For each type of problem, there are a set of breeding methods that are more suitable. For the vehicle routing problem, according to the literature, the most commonly used methods are: a crossing point, dual point crossover and uniform crossover. In our case we used the Uniform crossover. This method consists in determining the cost, the number of customers and the ratio of these last two for each round of two parents chosen at random. Then, each parent towers are sorted in ascending order according to the quotient: Cost/Number of customers. The third step is to establish a conflict matrix to describe the conflicts between the towers of both parents. The construction of the individual descending begins by inserting the first turn of one of the parents. The second step in the construction of the son is to exclude all rounds of the other parent are in conflict with the tour recently added. The same process is then repeated with the first round of the other parent and so on until there are more towers to insert. At this stage it is possible to customers not served. These customers are inserted into the shot so that the overall cost is minimal. Figure 6 illustrate an example of a crossover operation. Mutation: In the process of evolution, mutation performs a broader exploration of the search space, to avoid premature convergence and diversity loss by bringing innovation in the population. In our approach we have adopted the method of simple random mutation. The principle of this method is to choose two nodes randomly. Result in generating a random value between 0 and 1. If this value is less than the mutation probability, then swap the two nodes, otherwise do nothing. Figure 7 shows an example of a mutation operation. Distributed Genetic Algorithm for Disaster Relief Planning 777 Figure 6: Example of a crossover operation Figure 7: Example of a mutation operation 778 K. Zidi, F. Mguis, P. Borne, K. Ghedira Replacement: After each iteration, individuals created (children) will be added to the popu- lation. To keep the same population size, we proceed to an alternative transaction elitist is to sort individuals according to their overall costs and keeps only the first N individuals to form the next generation. 4.2 Treatment of a New Request Upon the arrival of a new request for assistance to the agent "Interface", it begins with collecting the necessary information that can help the agent "Supervisor" to make the right decision, then it sends the request to the "Supervisor Agent". This establishes a tender which will be sent to "Vehicle Agents" which will be able to meet this demand. Each "Vehicle Agent" receiving the tender should calculate its area of action [43][60] which is equal to the number of customers(t,x,y) that can be served by this vehicle (t0,x0,y0). Then this agent should calculate also the insertion cost which equals to the difference between the old and the new zone area. Finally, the "Vehicle Agent" sends its offer to the "Supervisor Agent" who is in charge of choosing the best offer and sends the response to the "Interface Agent" which should inform stakeholders involved in this new application. If the "Supervisor Agent" could not insert the new request in any tour, there will be creation of a new tour to meet request. The above process of a new request treatment was described in Figure 8. Figure 8: Treatment of a new request 4.3 Treatment of a Disturbance A good management of disaster relief should take into account the occurrence of disturbances at any time during the rescue. In fact in the case of disasters road and emergency equipment were very delicate and it may cause a malfunction of the system. For these reasons, we have provided a module for the treatment of disturbances. When receiving an announcement of a disturbance, the "Interface Agent" was responsible for the collection of information relating to the obstruction. Then it sends all this information to the "Supervisor Agent" who takes care of looking for a solution to the disturbance. Disturbances treated herein were two types. Disturbance may be caused by a vehicle breakdown or unavailability of a road. In the vehicle breakdown case, the "Supervisor Agent" checks the possibility of replacing the vehicle. if not he have to try to fit the request of the disabled vehicle in the other tour, without interfering any constraints. In case of unavailability of a road, we proposed two alternatives. The first one Distributed Genetic Algorithm for Disaster Relief Planning 779 consist of changing the vehicle way by avoiding the disrupted roads. The second alternative consist of inserting customers in other tours. The treatment process of a disturbance was shown in Figure 9. Figure 9: Treatment of a disturbance 5 Experiments and Results In this section, we report our approach results in comparison with other algorithms. The tests data were described in the section 5.1; while the experimental results of the different problems were summarized in the section 5.2. 5.1 Experimental test data The basic data of our testing problems adopt Solomon’s 100-customer benchmark problems [40] for the static vehicle routing problem with time windows (VRPTW). In these benchmark problems, 100 nodes are distributed in a Euclidean plane of 100*100 squares, and the travel times between nodes are equal to the corresponding Euclidean distances. There are six types of problems, named C1, C2, R1, R2, RC1 and RC2, each with 8-12 problems. Different types of problems differ in the distribution of the nodes, the service time of each node, and the width of time windows, described in detail as follows: • The locations of the nodes are clustered distribution in the problems of types C1 and C2, are random distribution in the problems of types R1 and R2, and are mixture distribution in the problems of Types RC1 and RC2. • The service time at each node is 90 time units in the problems of Types C1 and C2 and 10 time units in the problems of types R1, R2, RC1, and RC2. • The problems of types C1, R1 and RC1 have the vehicles of relatively small capacity; the capacity of each vehicle is 200 units. The ratios of the average demand of the nodes to vehicles capacities are 7.29%, 9.05% and 8.62%, respectively. And the problems of types C2, R2 and RC2 provide more capacity vehicles; the capacity of each vehicle is 700 units in Type C2, 1000 units in types R2 and RC2. The ratios of the average demands of the nodes to vehicles capacities are 1.469%, 2.59% and 1.72%, respectively. • In each problem, there is a time window [e0, l0] associated with the depot with in which a vehicle must return to the depot after serving some customers. The problems of Types 780 K. Zidi, F. Mguis, P. Borne, K. Ghedira C1, R1 and RC1 have an arrow time window of the depots, such that only few customers can be covered in each trip, while problems of Types C2, R2 and RC2 have a wider time window of the depots. 5.2 Experimental Results The test results were shown in Tables 1 for all the six type problems described in the section 4.1. For description convenience, we call the column (1) C1, column (2) C2, etc. NOV were the average of the used vehicles number. TD were the average of travel distance. C1, C2 were the computational results for the improved LNS algorithm (ILNS for short) which was proposed by Hong [16]. The C3 was the relative error between C2 and C8 (i.e.C3=(C8-C2)/C2*100%). C4 and C5 are the computational results for the Two-stage hybrid local search approach (HLS for short) which was proposed by Bent and Van Hentenryck [5]. the C6 was the relative error between C5 and C8 (i.e.C6=(C8-C5)/C5*100%). C7 and C8 were the computational results for our approach Guided Genetic Algorithm(GGA) [26]. C9 represents the percentage gain in execution time obtained by the use of our distributed approach. Based on these results, we can make the following conclusions on the effectiveness of the proposed approach to solve the problem studied: • The solution quality generated by our approach can approximate to the best known solu- tions, the ILNS approach and the HLS approach. If the travel distances are only observed and the number of used vehicles were ignored, the average relative error of each type was less than 10%. • Our approach provided an effective result within a reasonable time, which is very important in the disaster case. In fact, in the emergencies case, the solution should be provided quickly and efficiently. In addition our approach allowed at any time to provide an acceptable solution to stopping the execution of the algorithm after a given generation if necessary. • Using multi-agent systems has allowed us to reduce the execution time which was very important for emergency planning in disaster case. Table 1: Experimental results. ILNS approach HLS approach GGA Our aproach Problem NOV TD ER(%) NOV TD ER(%) NOV TD ∆Time(%) type (1) (2) (3) (4) (5) (6) (7) (8) (9) C1 10 833,1 -0,53 10 828,82 -0,02 10 828,65 -25,46 C2 3 590,31 9,09 3 589,86 9,17 3 643,94 -22,03 R1 12,25 1218,28 -1,28 11,92 1244,52 -3,36 11,9 1202,74 -14,67 R2 3,27 964,11 -5,24 4 954,27 -4,26 2,9 913,6 -16,53 RC1 12,13 1369,57 0,46 11,5 1384,17 -0,60 11,9 1375,89 -17,89 RC2 3,75 1131,18 7,69 3,25 1124,46 8,34 3,9 1218,2 -28,91 6 Conclusions and Future Works In this paper, we have developed a solution to the problem of emergency planning for disaster. We have illustrated some of the complexities practices for emergency in disaster case. Despite the importance of emergency planning in several disaster cases, they have received few attention Distributed Genetic Algorithm for Disaster Relief Planning 781 in the literature of the disaster and operations research. Thus, it appears that the extension of our approach to disaster relief, as described looks promising and with considerable value. Even if we know the boundaries explicitly construct models of reality and the unique nature of disasters, we suggest that operations research systems decision support can be beneficial in the disaster. Although several emergency relief organizations often hide their distribution planning for security reasons. finally we conclude that the adaptation and the use of the approach described above can contribute to the improvement of the use of the vehicle fleet management as well as the routing and delivery of relief goods in disaster cases. Bibliography [1] Adinolfi, C. et al.; 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, 2005. [2] Afshar, A.; Haghani, A.; Modeling integrated supply chain logistics in real-time large-scale disaster relief operations, Socio-Economic Planning Sciences, 46(4): 327-338, 2012. [3] Baer, M. et al.; Safe: the race to protect ourselves in a newly dangerous world, New York: HarperCollins, 2005. [4] Balcik, B. et al.; Last mile distribution in humanitarian relief, Journal of Intelligent Trans- portation Systems, 12(2): 51-63, 2008. [5] Bent, R.; Hentenryck, P.V.; Scenario-based planning for partially dynamic vehicle routing with stochastic customers, Operations Research, 52(6): 977-987, 2004. [6] Beresford, A.; Rugamba, A.; Evaluation of the transport Sector in Rwanda, Geneva: UNC- TAD, 1996. [7] Boudali, I. et al.; An Interactive Distributed Approach for the VRP with Time Windows, Journal of Simulation Systems, Science and Technology, 2005. [8] Burg, S.; Shoup, P. (1999); The war in BosniaeHerzegovina: ethnic conflict and international intervention, Armonk, NY: M.E Sharpe, 1999. [9] Campbell, A.M.; Savelsbergh M.W.P.; A decomposition approach for the inventory-routing problem, Transportation Science, 38: 488-502, 2004. [10] Cheng, C.B.; Wang, K.P.; Solving a vehicle routing problem with time windows by a decom- position technique and a genetic algorithm, Expert Systems with Applications, 36: 7758-7763, 2009. [11] Coello, C.; A short tutorial on evolutionary multi-objective optimization, Computer Science, 1993: 21-40, 2001. [12] Fritz Institute; Lessons learned: recipient perceptions of aid effectiveness: rescue, relief and rehabilitation in tsunami affected Indonesia, India and SriLanka, San Francisco, CA: Fritz Institute, 2005. [13] Goldberg, D.; Genetic algorithms in search, optimization, and machine learning, Advison- Wesley, 1989. 782 K. Zidi, F. Mguis, P. Borne, K. Ghedira [14] Harbaoui, D.I. et al.; Multi-Objective Optimization for the m-PDPTW: Aggregation Method With Use of Genetic Algorithm and Lower Bounds, Int J Comput Commun, ISSN 1841-9836, 6(2):246-257, 2001. [15] Holland, J.; Adaptation in natural and artificial systems, Tech. rep., University of Michigan Press, Ann Arbor, Canberra ACT 2601, Australia, 1975. [16] Hong, L.; An improved LNS algorithm for real-time vehicle routing problem with time windows, Computers and Operations Research, 39(2):151-163, February, 2012. [17] Kefi, G.M.; Ghedira, K.; A Multi-Agent Model for a Vehicle Routing Problem with Time Windows, Urban Transport Conference, Dresden-Allemagne, 2004. [18] Kovacs, G.; Spens, K.; Humanitarian logistics in disaster relief operations, International Journal of Physical Distribution and Logistics Management, 36(2): 99-114, 2007. [19] Long, D.; Wood, D.; The logistics of famine relief, Journal of Business Logistics, 16(1): 213-229, 1995. [20] Ma, X. et al.; Min-max robust optimization for the wounded transfer problem in large-scale emergencies, Control and Design Conference, China, 2010. [21] McClintock, A.; The logistics of humanitarian emergencies: notes from the field, Journal of Contingencies and Crisis Management, 17(4): 295-302, 2009. [22] McEntire, D.; Issues in disaster relief: progress, perpetual problems and prospective solu- tions, Disaster Prevention and Management, 8(5): 351-361, 1999. [23] McGuire, G.; Supply chain management in the context of international humanitarian assis- tance in complex emergencies, Supply Chain Practice, 2(4): 30-43, 2000. [24] Mguis, F. et al.; Modlisation dun systme multi-agent pour la rsolution dun problme de tournes de vhicules dans une situation durgence, in: 9me Confrence Internationale de Mod- lisation, Optimisation et SIMulation MOSIM12, Bordeaux, France, 2012. [25] Mguis, F. et al.; Distributed approach for vehicle routing problem in disaster case, 13th IFAC Symposium on Control in Transportation Systems, Sofia-Bulgaria, 2012. [26] Mguis, F. et al.; Guided genetic algorithm for the dynamic management of emergency planning for disaster, Internationnal conference of Information Technology and Quantitative Management, Suzhou-China, 2013. [27] Oh, S.; Haghani, A.; Testing and evaluation of a multi-commodity multi-modal network flow model for disaster relief management, Journal of Advanced Transportation, 31: 249-282, 1997. [28] Oloruntoba, R.; Gray, R.; Customer service in emergency relief chains, International Journal of Physical Distribution and Logistics Management, 39(6): 486-505, 2009. [29] Oloruntoba, R.A.; Documentary analysis of the cyclone Larry emergency relief chain: some key success factors, International Journal of Production Economics, 126(1): 85-101, 2010. [30] Ozdamar, L.; Planning helicopter logistics in disaster relief, OR Spectrum, 33: 655-672, 2011. Distributed Genetic Algorithm for Disaster Relief Planning 783 [31] Ozdamar, L.; Demir, O.; A hierarchical clustering and routing procedure for large scale dis- aster relief logistics planning. Transportation Research Part E: Logistics and Transportation Review, 48: 591-602, 2012. [32] Perry, M. ; Natural disaster management planning: a study of logistics managers respond- ing to the tsunami, International Journal of Physical Distribution & Logistics Management, 37(5): 409-433, 2007. [33] Petitt, S.; Beresford, A.; Emergency relief logistics: an evaluation of military, nonmilitary and composite response models, International Journal of Logistics: Research and Applica- tions, 8: 313-331, 2005. [34] Psaraftis, H.N.; Dynamic vehicle routing problems, Vehicle routing: methods and studies, Elsevier Science Publishers B.V.: 293-318, 1988. [35] Psaraftis, H.N.; Dynamic vehicle routing: Status and prospects, Annals of Operations Re- search, 143-164, 1995. [36] Quarantelli, E.; Ten research derived principles of disaster planning, Disaster Management, 2: 23-26, 1982. [37] Quarantelli, E.; What is a disaster, London: Routledge, 1998. [38] Rosenthal, U. et al.; Coping with crises: the management of disasters, riots and terrorism, Springfield, IL: Charles C. Thomas Publishers, 1989. [39] Savvaidis, P.et al); 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, 2002. [40] Solomon, M.; Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, 35(2): 254-265, 1987. [41] Tzeng, G.H.et al.; Multi-objective optimal planning for designing relief delivery systems, Transportation Research Part E: Logistics and Transportation Review, 43: 673-686, 2007. [42] Yi, W.; Kumar, A. (2007); Ant colony optimization for disaster relief, operations, Trans- portation Research Part E: Logistics and Transportation Review, 43 (6): 660-672, 2007. [43] Zeddini, B.; Zargayouna M.; Auto-organisation spatio-temporelle pour le VRPTW dy- namique, RJCIA, 2009. [44] Zhang, J.H.et al.; Multiple-resource and multiple-depot emergency response problem con- sidering secondary disasters, Expert Systems with Applications ,39, 11066-11071, 2012. [45] Zidi, I. et al.; 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), Milano (Italy), 2011. [46] Zidi, K.; Systčme Interactif d’Aide au Déplacement Multimodal, Thčse de doctorat Ecole centrale de Lille France, 2006. [47] http://www.cbsnews.com/stories/2010/01/13/world/main6090601.shtml [48] http://www.reliefweb.int