1. INTRODUCTION
In recent, the number of natural disaster occurrence is continuously increasing and the damage scale and intensity of the natural disasters are growing accordingly. This phenomenon is interpreted as a result of the climate change represented by global warming, environmental change due to the urbanization, and other factors. According to the Centre for Research on the Epidemiology of Disasters, there were 346 reported disasters in 2015, 22,773 people dead, 98.6 million people were affected by those disasters and 66.5 billion of economic damages (CRED, 2011; UNISDR, 2016). Besides those natural disasters, the manmade disasters such as Fukushima Daiichi nuclear disaster, fire, terrorism, etc. become more influential on human life (Coleman, 2006).
To respond to the disaster, activities such as organizing disaster response groups, securing access routes and relief resources, distributing relief resources, and recovering damaged areas are needed (Haddow et al., 2007). Among these activities, efficient distribution of relief resources to victims in disaster scene is one of the most essential activities in disaster response (Cheng and Ling, 2008).
A vehicle routing problem for efficient distribution in the disaster scene is the most important part of emergency logistics problem. To build an efficient emergency vehicle route plan, an allocation problem to assign relief demands to vehicles and vehicle routing problem to generate a visiting sequence with considering relief resource usage for various type of vehicle should be solved simultaneously.
In disaster scene, the information uncertainty such as accessibility to roads, the positions, required relief type, and amount of relief demands, etc. is one of the essential factors that should be considered for efficient distribution. To deal with information uncertainty, an agentbased distributed architecture is adopted with an assumption that individual vehicle (an agent) could gather more exact information on its territory or nearby area than a central headquarter could in the disaster scene. Based on the architecture, an algorithm for distributed vehicle routing problem (DVRP) is proposed to solve the transportation problem. In this algorithm, the individual relief vehicle builds its own route plan based on its own information and a headquarter coordinates to refine the build plans. The performance of the suggested algorithm will be verified with a simulation experiment.
The rest of this paper is organized as follows: Section 2 presents a literature review, and Section 3 presents the characteristics of emergency logistics problem and proposed solution procedure. Computational simulations are described in Section 4, and the conclusion is remarked in Section 5
2. LITERATURE REVIEW
There were various studies related to the disaster response and emergency logistics. They may be classified into two categoriesemergency response systems and vehicle routing problems on the disaster scene.
Tovia (2007) analyzed the disaster cases of hurricane and suggested a response model which is specialized to hurricane in North America. Cheng and Ling (2008) suggested emergency response system models based on the analysis of operations on the disaster scene. Their model focuses in macro level operations in disaster response. Ren and Zhang (2010) insisted a design strategy for the emergency logistics system, based on the analysis of the uncertainty in relief goods logistics. They applied fuzzy clustering to build their strategy. Their design strategy focused on the location of facility and area scoring. Dai et al. (2010) analyzed common characteristics between supply chain and emergency logistics. Afterwards, they defined eleven subsystems and defined their relationships in macro level of logistics system. Ahmadi et al. (2015) studied on the logistics system considering network failure in disaster scene. They built logistics model which covers local depots and verify their model by simulation experiment based on the geography of San Francisco. Those studies tried to build the emergency logistics system. However, they are based on the specific category of disaster and applied region, it is hard to expand their model to the general disaster.
The studies on the vehicle routing problem during a disaster deal with an algorithm for vehicle routing. Chang et al. (2007) built a relief distribution center allocation algorithm in the middle stage of logistics. The geographic data of Taiwan is applied to build a threestage relief organization. Their study is based on the demand cover model, and focused on the distribution center allocation. Yi and Özdamar (2007) solved the emergency logistics problem which makes a plan to distribute relief goods and evacuate those with casualties. This study suggested the specialized solution to solve the emergency logistics problem based on the earthquake of Istanbul. Cao et al. (2009) studied the vehicle routing plan in the event of an earthquake. In this study, the objective function contains the safety index from the GIS system. Parragh et al. (2009) focused on developing a fast response to the disaster. To reduce the response time, a twostage heuristic algorithm was suggested. Yue et al. (2012) studied the dispatching problem of ambulances which has similar characteristics with emergency logistics. The suggested algorithm was a heuristic algorithm with a greedy property. Chang et al. (2014) built GSMOGA (greedysearchbased multiobjective genetic algorithm) to build the route plan in disaster scene. The route plan in this study aimed to minimize the delay in the route plan of emergency logistics. Gai et al. (2015) built the heuristic algorithm for route plan in emergency which considers multiobjective function, total travel time and safety of the route. The algorithm in this study examines various weight setting of objectives. Moreno et al. (2016) suggested a heuristic approach which considers reuse of the vehicles in disaster scene. They suggested relaxed mixed integer model to solve allocation problem and expand it to multiperiod problem.
Pervious researches suggest various method to solve route problem in emergency logistics. Because of dynamic environment of disaster scene, the difficulty in information gathering and transferring is unavoidable. However, their consideration of those difficulty was not enough. To overcome this obstacle, this problem suggests the distributed vehicle routing algorithm. In this algorithm, vehicles in disaster scene build its route plan with up to date information, and headquarters gather and coordinate route plan.
3. CHARACTERISTICS AND SOLUTION OF DISTRIBUTED VEHICLE ROUTING PROBLEM IN DISASTER SCENE
3.1. Characteristics of DVRP in Disaster Scene
The emergency logistics problem deals with an efficient dispatch of relief resources to disaster victims. This problem is the logistics problem with various uncertainties. In the aspect of demand, they occur more frequent than demands in the time of peace. Moreover, the amount and deadline of demands have larger deviations. Therefore, it is hard to satisfy all demands with a single visit, and revisiting should be considered. In aspect of environment, the impact of disaster causes various uncertainties to the social infrastructures. Therefore, the routing algorithm in emergency logistics must consider those uncertainties.
The importance of a deadline compliance in the emergency logistics problem is strengthened compared to the time of peace. Because casualties in disaster scene must get first aid within the golden time, and relief goods requests should be delivered as soon as possible. If the medical team arrives beyond the golden time, their efforts will have been in vain. Therefore, deadline compliance is mandatory. The problem with these characteristic is classified as the vehicle routing problem with a time window (VRPWTW). However, the penalty of late arrival in emergency logistics is more severe than the general VRPWTW. Therefore, the vehicle routing algorithm in disaster scene should consider maximizing the number of demands which satisfy its deadline.
In this study, the algorithm to solve the vehicle routing problem with resource usage plan in disaster scene will be suggested. The objective of the suggested algorithm is maximizing the number of demands, which satisfy its deadline. There are some assumptions to model this problem.

The route plan is built upon the traffic network, which is defined as the combination of nodes and arcs.

There are two types of demand according to required relief resource type: urgent demand vs. normal demand

All demands have a specific deadline that represents time limit for the relief resource works valid.

All vehicles are identical.

Vehicles consumes their time while moving, loading, and distributing resources, and it consumes equal time to load and distribute.

Route in this problem allows revisiting.
At first, a mathematical programming method which builds the optimal route plan is reviewed. Table 1 and Formula 2~21 is the mathematical model of suggested problem.(3)(4)(5)(9)(10)(13)(14)(17)(18)
Formula 1 is the objective function to maximize the number of demands which satisfy its deadline. Formula 2~6 are related to the vehicle route. Formula 7 and 8 deals with time in the route plan. Formula 9~11 are related to the resource amount of each vehicle. Formula 12~15 limit the resource usage. Formula 16~19 is the constraints related to deadline. Lastly, Formula 20 and 21 are the positive constraints of variables.
This problem is similar to the VPRWTW. However, it has additional characteristics such as resource usage, allowed revisit, and deadline constraints. Therefore, this problem is expected to be more difficult than original problem, it will take very long time to compute the optimal solution. To solve this problem, a solution with a reasonable computation time will be suggested.
3.2. Solution of DVRP in Disaster Scene
In general, a solution procedure is classified as centralized approach or distributed approach depending on which plays key role among the headquarters and individual members. In a centralized approach, the headquarters must collect information about demands, traffic network, and other surroundings in dynamic situations due to disaster. This process mostly depends on the telecommunications but the communication disruption often occurs in disaster scene. Therefore, the centralized approach is hard to be applied as solution procedure in disaster scene.
To overcome this limitation, an algorithm for DVRP is suggested. In this algorithm, the individual vehicle builds its own route plan, and the headquarter aggregates all individual plans and refine them. Moreover, a vehicle in disaster scene collects information change. In this case, vehicle is close to disaster scene, it is easy to recognize and collect the changes. Therefore, the algorithm might be helpful in overcoming the delay and uncertainty of communication in information collection step and efficient in computational time when compared to the centralized algorithm.
3.2.1. Framework
Figure 1 show the entire stages of the proposed algorithm for DVRP. In the first stage, each individual vehicle builds its own initial route using the suggested algorithm. In the second stage, headquarters collects the route plans. With the collected plans, headquarters coordinate and refine those plans.
3.3. Algorithm for Initial Route
The entire process of the suggested algorithm is the almost same with the process of the general GA.
3.3.1. Chromosome Structure
To apply the genetic algorithm to the VRP, the chromosome should cover the resource usage plan. There are two methods to indicate the resource usage plan in the chromosome. The first method is that the chromosome contains both the vehicle route and the resource usage plan. This method is easy to build the actual plan. However, result of crossover operator and mutation operator often become impossible. Therefore, an adjusting step is needed to correct the chromosome. the second method is that the chromosome contains only the vehicle route. With this method, a problem for resource usage plan should be solved additionally. However, an optimal resource usage plan could be applied for the individual vehicle route. In this study, the chromosome structure is defined base on the second method. In addition, the chromosome does not contain the route of facility node because those routes could be determined by the optimal resource usage plan.
3.3.2. Evaluation
As, mentioned the chromosome do not contain a route to the facility nodes. Therefore, to complete the vehicle plan, facility route and resource plan should be added, and then the completed chromosome is evaluated. A fitness function to evaluate the performance is suggested as shown in Formula 22.

i : Index of chromosome

S(i): # of demands which satisfied their deadline

U(i): # of demands which do not satisfied their deadline
The vehicle visits the nodes according to the node sequence in the chromosome, and use its resource to satisfy the demand located in visited node. The vehicle must visit the facility node to replenish the relief resource before going to the next node when the resources in a vehicle is insufficient. Furthermore, if the demand in the next node exceeds the maximum load of the vehicle, the vehicle should visit the facility node multiple times. Moreover, two types of visiting methods are available in this problem. One is visiting the demand node first and then considering round trip to facility node, which is needed if the vehicle cannot satisfy the demand with a single visit. The other is visiting the facility node in advance and going to the next node.
To add the visiting plan to the facility node, an integer programming method applied. The method of this problem uses the parameters which are calculated with the result of the original route plan. The calculation process is described. in Figure 2 and the formulation for the visiting plan is shown with formulas from 23 to 31 and Table 2.(23)(26)
Variables and parameters in Table 2 are defined to describe the arrival time and available amount of relief resource. Decision variables describe the initial amount and supplying amount of relief resources and the plan for facility nodes. Using variables and parameters, the deadline observance of every demands in the original route plan are verified.
The objective of this problem is maximizing the number of demands that satisfies its deadline as shown in formula 23.
Formula 24 checks the deadline observance of every demands in original route plan. Formula 25~27 are related to the supplying amount of relief resources. Formula 25 calculates the amount of relief resources. 26 limits the amount of supplying resource according to the visit of depots and maximum cargo of a vehicle. At last, 27 limits the total amount of relief resource according to the maximum cargo. The arrival and starting time of vehicles are managed in Formula 28 and 29. Formula 28 calculates the arriving time of node n. 29 sets the starting time of the route plan. Formula 30 and 31 limit the positive condition and multiple visit in even numbered node.
The complexity of this problem is low, and it is easily solved in the short computation time. Therefore, this study can apply the GA with the suggested chromosome structure and performance evaluation method.
3.3.3. Other Parameters for Experiment
The number of the population is initially set to 500. This size is set to get reasonable computation time. To generate the initial population, the heuristic method and randomized generation method are applied. One of them is selected randomly based with the probability of 20% and 80%. In the heuristic method, the next node with the next demand is selected randomly based on the probability which is proportional to the reciprocal number of its deadline.
As crossover operator, an order based crossover is applied. In mutation, two points in the chromosome are selected randomly, and the route between two points are reversed. In the suggested algorithm, mutation is applied with a probability of 20%. These operators work as in processes which are described by Figure 3.
As the generation increases, it becomes more difficult to find a better solution with GA. Therefore, if the suggested algorithm fails to find a better solution in a certain number of consecutive generations, the suggested solution will regard this as the convergence of a solution and terminate. In this study, the maximum number of generations without progress is designated as 50. In addition, the number of generations exceeds 1000, the algorithm terminates. These parameters are set to get the resonable computation time.
3.4. Cordinating Process for FInal Plan
With the route plan of the individual vehicles, the suggested algorithm builds the coordinated final route plan for the vehicle fleet and returns the final plan to the individual vehicles. In this process, two algorithms will be suggested. One is the priority based heuristic rules, and the other is the modified kmeans clustering algorithm.
3.4.1. Priority Based Heuristic Algorithm
The priority based heuristic algorithm follows 3 steps as shown in Figure 4. In the first step, the initial routes are analyzed to find the demand nodes whose deadlines are violated or assigned other vehicles redundantly.
In the second step, the increment of the fitness value when the specific redundant demand node is removed is calculated for each route plan to resolve the redundancy. The route plan shows the smallest increment preserves the redundant demand and for the other route plans the specific redundant demand node is removed. This process is repeated until the redundancy is resolved. And then deadline violation is checked again for each route plans and the demand nodes with deadline violation are removed from each route plans
In the third step, the priority of each pair of unallocated demand and vehicle is calculated. To calculate the priority of the pair, all possible insertion points are evaluated by fitness values for a certain unallocated demand. The point shows the biggest increment in fitness value is selected an inserting point in this route plan, and this value represents the priority of this pair. A route plan shows the biggest increment is selected to allocate this unallocated demand. This process is repeated until unallocated demands are allocated.
3.4.2. Modified KMeans Clustering Algorithm
Modified Kmeans clustering algorithm is based on the kmeans clustering algorithm, but it has some different properties. At first, the process of general kmeans clustering algorithm is described in Figure 5.
Duplicated assigned demands and unallocated demands are target demands in this algorithm, which are reallocated by this algorithm. Other demands are not reallocated, but they are included only in calculating the center of the cluster.
In Initialization stage, the number of clusters is set to the number of vehicles, and the initial center is the starting point of each vehicle.
In cluster calculation stage, target demands are allocated to the closest center. To calculate the distance between demands, the shortest distance in the network is applied. If the center is not on the node, the Euclidean distance to the closest node is added to calculate the total distance between the center and demands. In the result of this stage, the all target demands are allocated to the center of each vehicle.
Next stage is center calculation. In this stage, new center is calculated. New center is the arithmetic average of location in the demands in the cluster. The old center is replaced with new one. With new center, the terminal condition is checked to finish this algorithm. In this stage, change of the cluster after iteration is checked. If there is not a change in the allocation of the demands with pervious iteration, the algorithm is terminated. This condition is same as the general terminal condition in Kmeans clustering. In addition, when the shortest distance between the location of vehicle and the center exceeds the 2 times the initial distance between the vehicles and the center, the algorithm is terminated, too After clustering, each vehicle rebuilds its route plan using the GA based algorithm with the result of clustering.
4. SIMULATION EXPERIMENT
To verify the performance of the suggested algorithm, a simulation experiment was conducted.
4.1. Simulation Environment
Simulation environments are generated by parameters based on the data of major cities and past disasters in South Korea. The parameters are listed in Table 3.
Based on the common parameters in Table 3, disaster scenes are randomly generated and applied to the simulation experiments. In this research, three types of experiments are conducted. The first experiment is to verify the performance of vehicle routing algorithm for the individual vehicle by comparing the solution with optimal solution. Because it takes too long time to compute the optimal solution for realsized problem, three types of smallsized problems which has 10, 30, and 50 demands with 20% of urgent demands are randomly generated 100 times and applied to this experiment.
The second experiment is to observe the performance variation of vehicle routing algorithm for the individual vehicle according to the change in simulation environment, especially in size, derived from the parameters and those values shown in Table 4. There are 3 types of household density and 3 types in urgent demand proportions. Therefore, 9 types of environment are generated 100 times and applied to simulation experiment.
The last experiment is to verify the entire algorithm which covers the coordination process for whole fleet under various environments which is randomly generated based on the parameters in Table 4. In this experiment, the performance of two coordination rules are compared. Same as the experiment for the single vehicle, 9 types of environment are generated, and 2 types of vehicle fleets with three and six vehicles are applied. Therefore, 18 types of simulation experiments are conducted. Each experiment is repeated 100 times.
4.2. Experiment Result
As mentioned above, deadline satisfaction is one of the most critical factors to evaluate performance in the emergency logistics. To compare deadline satisfaction, the number of demand which satisfies its deadline and percentage of satisfied demands are applied. The percentage is calculated based on the total number of demands. At first, the result of experiment is verified by ANOVA test as described in Table 5. Small pvalue shows that all parameter combination makes different experiment result.
4.2.1. Comparison with Optimal Solution
As mentioned previously, the smallsized problems were solved to compare the result with the optimal solution. The performance ratio between optimal solution and genetic algorithm solution are calculated to reveal the difference. The result is described in Table 6.
The result shows that the performance of the suggested algorithm is inferior to the result of optimal solution, but the computation time is short. Therefore, the result states that the suggested algorithm is applicable in the disaster scene, which requires fast decision and short computation time. Moreover, following aggregation algorithm will gather and harmonize the plans of the individual vehicles in fleets. Therefore, the final plan of the whole fleets will be improved further and the difference with the optimal solution will be decreased.
4.2.2. Performance of Algorithm for Individual Vehicle
Table 7 shows the entire experiment result of algorithm for individual vehicle. The result shows that the performance of the suggested algorithm becomes worse as the number of families increases, but the gap between them is not significant. The number of demands which satisfies its deadline doesn’t change a lot. However, the percentage of satisfied demand is between 10% and 30%, which is caused by change of household density. This result is caused by a single vehicle setting. In an actual situation, multiple vehicles may be allocated in the same environment.
In case of urgent demand proportion, the result shows that the performance of the suggested algorithm becomes worse as the number of families increases, but the gap between them is less than that of number of families in disaster scene. Therefore, the suggested algorithm is expected to perform well in extreme situations. The suggested algorithm works well in a single vehicle environment.
4.2.3. Performance of Algorithm for Vehicle Fleet
Table 8 shows the result of experiment for the whole vehicle fleet. The result shows that the percentage of satisfied demands decreases as the number of families increase and the proportion of urgent demands increase.
The tendency of performance variation in the experiment for the vehicle fleet is same with the experiment for the individual vehicle. Moreover, the result shows that the suggested algorithm is applicable in the actual disaster. Also, the result shows that the performance of the suggested algorithms becomes better as the number of vehicles increases, but the computation time becomes worse. Therefore, it is important to find the appropriate size of vehicle fleet to make efficient vehicle route plan of the fleets.
Table 9 shows the performance comparison of the two coordination algorithms. It shows that the performance of the Priority based heuristic algorithm based on integer programming is inferior to the result of Modified kmeans clustering algorithm in the point of satisfied demand, but the computation time of Priority based heuristic algorithm is shorter than Modified kmeans clustering algorithm.
5. CONCLUSION
This study tries to solve the vehicle routing problem for the emergency logistics in disaster scene, and suggests a distributed vehicle routing algorithm. In this algorithm, each vehicle builds its route with GA based algorithm and its information. After that, a headquarters gathers the route plan of all vehicles in fleets and aggregates them to complete the final plans for individual vehicles.
To verify the performance of the suggested algorithm, simulation experiments were conducted based on the real data of Korean urban and the historical data for disasters in Korea. The result of the simulation experiment shows that the performance of the suggested algorithms works well in deadline based performance and short computation time. Moreover, the result shows that the suggested algorithm can work well under extreme environment with massive demand and urgent deadline.
This study made some assumptions to build the model. For example, the model assumed that one vehicle is assigned to fulfill one demand node. Future study will resolve those assumptions for more realistic application. Moreover, future research should try to improve the performance of the algorithm. It will consider additional uncertainties that may be caused by an unstable environment and supplies. Afterwards, the actual damage and demand data of past disaster will be applied to verify the improved algorithm.