Journal of Industrial Engineering and Management

 
Research on multi-objective emergency logistics vehicle routing problem under constraint conditions

Miaomiao Du¹, Hua Yi²

School of Economics and Management Beijing Jiaotong University (China)

Received June 2012

Accepted February 2013

 

Du, M., & Yi, H. (2013). Research on Multi-objective Emergency Logistics Vehicle Routing Problem under Constraint Conditions. Journal of Industrial Engineering and Management, 6(1), 258-266. http://dx.doi.org/10.3926/jiem.670

---------------------

Abstract:

Purpose: Aim at choosing a relative good vehicle routing in emergency conditions under constraint conditions when disaster happens. Rapid response and rescue can save a lot of people.

Design/methodology/approach: Modeling analysis: establishing a mathematical model of multi-objective emergency logistics vehicle routing problem. And in end of the paper, we intend to use genetic algorithms to solve the problem.

Findings: Considering time requirement and cost limit both while choosing vehicle routing when the disasters happens is meaningful. We can get a relative good result and give a guidance to rescue teams.

Originality/value: Consider cost and time objectives and kinds of realistic conditions (such as the road congestion) in the model when solving the problem, having expanded the theory scope.

Keywords: emergency logistics, road congestion, unilateralism time window, vehicle routing problem, genetic algorithms

---------------------

1. Introduction

With the rapid development of China's economic and the modernization process, no matter the natural disasters or public safety disasters, the occurrence and size are significantly larger than usual. It brings more and more serious affect on people's daily lives and work. This has an ever-increasing impact on people's daily life and work. And this also hinders the pace of China's sustained and healthy economic development. With the current level of technology, the occurrence of these natural disasters and public health events is inevitable and the loss it caused is immeasurable. Emergency logistics system should achieve the time benefits to maximization and the disaster to the minimization and meet the emergency logistics needs in condition of limited time, space and resource constraints. Under the impact of the incident, the original vehicle path may no longer fit the new situation. So how to elect a best path from each path program is an important work. And it is worth studying.

Emergency Logistics is a special logistics activity which supplies materials, personnel and funding for the emergency support, responding to the incident of serious natural disasters or unexpected public health events. Its aim is to pursuit the time benefits to maximization and losses caused by disasters to minimization. Emergency Logistics has some special features, such as uncertainty, unconventional, the urgency of time constraints, diversity of needs, government and market participation and so on (Zhao, Zhang & Huang, 2009).

2. Research of Emergency Logistics Vehicle Routing Problem

In the foreign literature, there exists a study about material transportation planning with helicopter (Barbarosogu, Ozdamar & Cevik, 2002). In this paper, they divided the problem into two sub-problems. One is the composition of the helicopter. Another is the transport route choice of helicopter. There exists a study about multi-objective programming of routing problem (Viswanath & Peeta, 2003). One of the objectives is that the total fee of material transportation is the least. The other objective is the critical path can cover most of the affected people in disaster. A study puts forward an emergency material transportation model based on mixed integer programming (Ozdamar, Ediz & Kocokyazici, 2004). The objective function of the model is to minimize the time delay of demand materials. The authors put forward the solving algorithm of the model and Verify the effectiveness of the algorithm using an example in the end.

In domestic literature, there also exist some related researches. In a paper, the author established a model by using operations research methods (Zhou, 2009). This model solved the problem of how to choose the path of the delivery vehicles. It had some practical significance. There exists study about emergency materials vehicle scheduling (Chou & Feng, 2010). The author established a model and used Genetic Algorithm to achieve it, having some certain reference significance. There also exists research about road congestion and window time (Zhao & Ji, 2011). In this paper, the author established a model. The aim of this model was the maximum degree of satisfaction. And this achieved good results.

3. Description of Problem and Mathematical Model

3.1. Description of Problem

The roads may be destroyed which making the total capacity of the road network fell in some region after the occurrence of natural disasters and public emergencies. Before the road network being repaired, traffic will be concentrated to the other sections. The traffic load will increase on this sections and even lead to certain traffic congestion (Zhao & Ji, 2011). In addition, the disaster itself will produce a series of traffic load, including transport and distribution of relief materials, the transfer of the wounds, visiting friends or family security and so on, which is bound to have a major impact on the entire road network. Therefore, the congestion constraints should be taken into account when researching the emergency vehicle routing problem. We also need consider the time window for each demand point in emergency logistics. According to the characteristics of emergency logistics, we just consider the unilateral time window, meeting the latest arrival time. The upper limit of the time windows is zero. It should consider the cost because of the limiting of human, material and financial. The model’s main aim is that the sum of the time is the least. And the second aim is total system cost minimization. All requirements can be met according to this model.

We assume that the road is blockage. We regard d as the congestion level. And d is bigger, the congestion level is more serious. Road traffic only has a relation with d, d=kQ_{flow capacity} (k>0) (Xu, Ma & Li, 2008). When Link flow is less than the rated capacity of the vehicle, that is Q_{flow capacity}<Q_{rated flow capacity}, d equals to 1.

3.2. Assumption of Model

- There is only an emergency logistics distribution center and several emergency supplies demand points which the demand and location are known.

- Emergency logistics centers have the same model transport vehicles and the vehicle's load capacity is known and determined. The demand for each demand point is less than the capacity of a vehicle.

- Emergency logistics center supplies (including emergency vehicles) are adequate. There are no out of stock.

- Each emergency logistics points need only one vehicle. One vehicle could be responsible for a number of demand points. Each vehicle starts from the emergency logistics center and returns to the emergency logistics when it completes the task.

- We don’t consider the service time of vehicles in each demand point, supposing that the loading and unloading time is 0, and only consider the travel time between the emergency demand points.

- There is design speed limit of various sections. That is the maximum safe speed when the road conditions and environmental climatic conditions are in good case.

3.3. Establishment of Model

In the model, Drepresents emergency logistics center. Letter M represents the collection of demand point. Letter V represents collection of emergency vehicles. Letter A represents collection of all nodes. Parameter c_n^f represents the fixed costs of emergency vehicle n. Parameter c_n^t_ijn represents unit cost of the vehicle n from node i to node j. Parameter T_in represents the time of vehicle n arriving at the emergency demand point i. Parameter L_i represents the latest time vehicle arriving at emergency demand point. Parameter d_ij represents the distance between node i and node j. Parameter d_ij represents the congestion level between node i and node j. Parameter v_ij represents design speed between node i and node j. Parameter Q_n represents the capacity of the emergency vehicle. Parameter q_i represents demand of emergency demand. Integer variable x_in, x_in=1 when the task of demand point is completed by the vehicle j, otherwise x_in =0. Integer variable y_ijn, y_ijn=1 when vehicle n is from node i to node j, otherwise y_ijn =0.

Objective function (1) makes sure that the total time is the least. Objective function (2) is the total cost, including the fixed grid costs (gasoline consumption, vehicle depreciation, etc.) and the travel costs. Objective function (1) is the main goal. Objective function (2) is a secondary objective.

Constraint (3) refers that an emergency demand point can be serviced only by one vehicle and only service once. Constraint (4) and (5) refers that the vehicle must leave the demand points at last, to ensure the continuity of the vehicle. Constraint (6) is the capacity constraint of vehicle. Constraint (7) refers that the time which vehicles arrived at the emergency demand point must meet the requirements of the unilateral time window. Constraint (8) indicates the actual time that the vehicle n arrives at demand points i. Constraint (9) and (10) represent the integer variable constraints.

4. Solution of Model

4.1. Description of Genetic Algorithm

In this paper, the vehicle routing problem is described as a multi-objective optimization problem and the solution to solve it is the Genetic Algorithm (Barrie & Ayechew, 2003). Solving optimization problem with multi-objective and multi-constrain is regarded as the multi-objective optimization problem. Model in the paper makes sure not only time limit but also the minimum of the total cost of the system. And these two goals are in fact conflict with each other. It is a typical multi-objective optimization problem. The essential difference between multi-objective optimization problem and single objective optimization problem is that the solution of former question an optimal solution set, while the solution of latter question is the only one solution.

We have done some processing on the target function when solving the multi-objective optimization. We use the weight coefficient transformation method and give a weight to each objective function. The overall objective function is the linear weighted sum. Because of the special application background, in order to highlight the importance of time to emergency vehicle routing problem, we give relatively large weights to the time limit function. Then the model can be seen as a general single-objective model. We can use Genetic Algorithm to solve it.

4.2. Specific Operation

Coding: In the article, a chromosome represents a feasible solution of the vehicle routing problem in the context of emergency. Each chromosome consists of two sub-strings. The first sub-string has M genes (M is the number of emergency demand points). Each gene uses natural number-coded, randomly selected in the natural number between 1 and n (n is the number of emergency vehicles). The second sub-string represents the sequence of visiting to the emergency demand points in a sub-path. The value ​​of the genes is randomly arranged by natural number between 1 and n. Adjustment of the internal order of sub-path will lead to change in the objective function value. Adjustment between the sub-paths does not change the objective function value. The first sub-string is correspondence to the second sub-string. This refers that the encoding of each vehicle of every emergency demand points.

Fitness function: We can use the fitness function value to judge the level that Genetic Algorithm does on a body. The greater the fitness function value, the better the quality of the solution. The result must be non-negative function. The fitness function must be converted to maximized-problem because the function in the model is a minimization problem.

Selection mechanism: In this paper, we use the election strategy of combination of roulette wheel selection and elitist selection to select the individuals which have the higher fitness level to next-generation groups according to some certain rules. First divide the wheel according to the fitness function value of each chromosome. The larger the area of each chromosome in the wheel, the higher the probability of selected. This also can make sure that chromosomes which the fitness function value is low may be selected, increasing the variability of the evolution process. And at the same time, we use an elite population to save the optimal solution. The best concept should be given when a new multi-target species generation generates. This makes sure that we can timely update the individuals in the elite population and exclude the inferior solution.

Cross-process: In Genetic Algorithm, the basic operation to generate a new chromosome is chromosome cross. The new individual has a part of both parents' genetic material like the natural evolution. The ways of cross include single-point crossover, two crossover, partial matching crossover and order crossover and so on. This article uses single-point crossover in the first sub-string and partial matching crossover and order crossover in the second sub-string.

Variation of the process: This article uses swap mutation operation in the first sub-string and reverse mutation operation in the second sub-string. Swap mutation operation is to select two genes in sub-string randomly and then swap their value. Reversal mutation operation is to set two reversal points in Individual code strings and then reverse and arrange genes between the two reversal points with reversal probability P_i.

Termination condition: Termination condition of this article is to meet the maximum number of iterations. And then we can stop the cycle. The genetic algorithm obtains the corresponding solution after iterations terminating. Then we can use cross exchange for the areas operation of the sub-way. Then use a random search algorithm to find better solution of the target.

4.3. Steps of Genetic Algorithm

- Code and construct chromosome structure and Set the crossover rate, mutation rate and the number of iterations and other parameters needed.

- Determine the fitness function and compute the objective function value and the fitness function value.

- Copy the next generation of chromosomes based on a combination of the roulette wheel selection and elitist selection.

- Crossover and mutation operations of the individual.

- Produce a new individual. Detection and evaluation to individual’s fitness level and then returning to Step 3.

- The iterations terminate when the number of iterations meet the maximum number of iterations. The appropriate solution is gained.

- Use cross exchange for the areas operation of the sub-way and then use a random search algorithm to find a better solution of the target.

- Decode and describe the best individual.

Finally, we can reach concrete results by using the simulation experiments and computer program. Then we can achieve the above-mentioned Genetic Algorithm.

5. Conclusion

There are a lot of researches on vehicle routing problem of emergency logistics now. They are generally establishing a mathematical model according to the description of the problem. And then construct heuristic algorithm for its solution. This paper takes congestion into account and uses time and cost these two factors to build a model. The model is rather good. And in the end of the paper, the using of Genetic Algorithms is a good way to this kind problem. Generally speaking, this article has some reference significance.

References

Barbarosogu, G., Ozdamar, L., & Cevik, A. (2002). An interactive approach or hierarchical analysis of helicopter logistics in relief operation. European Journal of Operational Research, 140, 118-133. http://dx.doi.org/10.1016/S0377-2217(01)00222-3  

Barrie, M.B., & Ayechew, M.A. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30, 787-800. http://dx.doi.org/10.1016/S0305-0548(02)00051-5

Chou, G., & Feng, C. (2010). Research on VRP under emergency logistics management. Southwest Jiaotong University.

Ozdamar, L., Ediz, E., & Kocokyazici, B. (2004). Emergency logistics planning in natural disasters. Annals of Operations Research, 129, 217-245. http://dx.doi.org/10.1023/B:ANOR.0000030690.27939.39

Viswanath, K., & Peeta, S. (2003). Multi-commodity maximal covering network design problem for planning critical routes for earthquake response. Transportation Research Board, 18, 11-14.

Xu, Q., Ma, Z.Y., & Li, H.J. (2008). Research on LRP of urban public emergencies in emergency logistics. Huazhong Science and Technology University.

Zhao, S.M., & Ji, S.Y. (2011). The network construction and routing optimization of grain emergency logistics system. Wuhan Technology University.

Zhao, Z.Y., Zhang, Y.Y, & Huang, X.K. (2009). Particularity and counter measures of emergency logistics. Research on Logistic Economic, 3, 58-61.

Zhou, P. (2009).Research on distribution vehicle routing problem of emergency material. Harbin Industrial University.