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

Miaomiao Du^{1}, Hua Yi^{2}

*School of
Economics and
Management Beijing Jiaotong University** (**China**)*

*Received **June** 201**2*

*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*, d equals to 1.

_{flow capacity}__<__Q_{rated flow capacity}**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*represents unit cost of the vehicle n from node

_{n}^{t}_{ijn}*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*represents the distance between node

_{ij}*i*and node j. Parameter d

_{ij}represents the congestion level between node

*i*and node j. Parameter

*v*represents design speed between node

_{ij}*i*and node j. Parameter

*Q*represents the capacity of the emergency vehicle. Parameter

_{n}*q*represents demand of emergency demand. Integer variable

_{i}*x*=1 when the task of demand point is completed by the vehicle j, otherwise

_{in}, x_{in}*x*=0. Integer variable

_{in}*y*=1 when vehicle n is from node

_{ijn}, y_{ijn}*i*to node j, otherwise

*y*=0.

_{ijn}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*.
Com**puters** &** Operations Resear**ch**,
*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
Boar**d,*
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 Universit**y*.

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.*

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

Journal of Industrial Engineering and Management, 2008-2020

Online ISSN: 2013-0953; Print ISSN: 2013-8423; Online DL: B-28744-2008

Publisher: OmniaScience