The application of Genetic-tabu Algorithm To Vehicle Routing

The application of Genetic-tabu Algorithm To Vehicle Routing
Problem with Time Window
Xu Xusong , Wei Zhongcheng
Economics & Management School,
Wuhan University, P.R.China, 430072
Abstract
It is well-known that the genetic algorithm has the disadvantage of “premature
convergence”. In this paper we design a hybrid algorithm based on genetic algorithm and Tabu search to
solve the vehicle routing problem with time windows. Our design makes use of the genetic algorithm
based the Tabu search crossover operator and Tabu search mutation operator. We test our hybrid
algorithm in the practical vehicle routing problem ,which shows good empirial agreements.
Key Words Vehicle Routing Problem, Time Windows, Genetic Algorithm (GA), Tabu Search
1 Introduction
The vehicle routing problem (VRP, hereafter) was first introduced by Dantzig and Ramser [1] in
1959. It has been one of leading research areas in the filed of operation research and combinatorial
optimizations. It arises in lots of practical problems such as post problem, computer designing, public
transport time-table problem, electricity flow problems, etc.
VRP is a special traveling salesman problem (TSP, hereafter), in which each node has cargo
demands in the transport network, each vehicle has its capacity limit and each transported cargo has its
own capacity limit. VRP is the basic model for many practical routes planning problem . However, the
actual transport routing planning often introduces some significant constraints to form various variation
problems of VRP, such as VRP problem with time window (VRPTW, hereafter). VRPTW deals with
the situation where clients often have the specific requirements on the time that cargos arrive at the
destination. The goal of VRPTW is to minimize the total travel cost of a vehicle while meeting the
clients’ requirements on cargo and service time.
Because VRPTW is a NP-hard problem, most of its research concentrates on designing and improving the
algorithm of obtaining optimal or approximate optimal solutions. VRPTW was first studied by Solomon [2] and
Desrosiers [3]. There are two main types of algorithms so far. The first type is precise algorithm, which works well
in small size VRPTW, see Kolen [4], Desrochers [5], Fisher [6] and Kohl [7] and the references therein. The other
approach is construction-type, which was first introduced by Solomon [2]. See also parallel interpolation algorithm
of Potvin [8], averaging distributing algorithm of Koskosidis [9], and Greed-stochastic-searching algorithm of George
[10]
. Others constructing-type methods are also used in finding solutions of VRPTW, such as genetic-algorithm (Tan
[11]
, Baker [12], Li [13], Xie[14]), tabu-search algorithm (Taillard [15], Brandao [16]). In this paper, we combine both
genetic algorithm and tabu-search to solve VRPTW.
2 Genetic-tabu Algorithm
In order to solve the precocity problem in Genetic Algorithm (GA, hereafter) and improve its
operation efficiency, many researchers have done a lot of work and put forward several improvement
methods, of which Genetic-tabu Algorithms search ( GATS, hereafter) is an important method. It
modifies the core operator in GA—cross operator and mutation operator according to the ideal of tabu
search algorithm. In this paper we introduce a short-term memory device, that is, Tabu Table whose
380
length is L. Here L represents the number of movements that are recently performed. Because these
movements are forbidden in the current iteration, L is called as the length of tabu. Through this
procedure, the genetic operation operators are re-defined respectively, writing as tabu cross operator
(TSCO, hereafter) and tabu mutation operator (TSMO, hereafter). Because of the introduction of Tabu
search, GA can have memory function and the stronger “climbing” capacity. It can jump out of the
local optimal solution in the search process and go to other areas to perform search. In this way,
it
has a better chance to obtain good optimal solution.
As cross operator, TSCO records the adaptive value of the chromosome in a tabu table whose
length is T and the expectation level is taken the mean value of parent group adaptive value. When
TSCO operation is performed, the child adaptive value is firstly compared with the expectation level. If
it is above the expectation level, the tabu is released, i.e. this child chromosome enters in the next
generation. If it is below the expectation level and the child doesn’t belong to tabu, this child is also
accepted; then select the best parent into the next generation if it belongs to tabu. Because TSCO uses a
tabu table, it limits the occurrence of cycles of the child with the same adaptive value and so the
diversity of the chromosome structure in the group is maintained so as to avoid precocity of algorithm.
On the other hand, Tabu table of TSMO is defined as follows: L information bits are added in each
chromosome to store the number of L information bits in which variety is produced recently. When one
variety occurs, the number of the information bit in which variety occurs is compared with that in tabu
table. If it is in the table, it belongs to the scope of tabu; the adaptive value of the individual after variety
is larger than the expectation level, it will go into the next generation. Firstly, a solution (chromosome)
is taken as input (initial solution). Through action of TSMO, a solution is returned as output. The
difference lies in that TSMO is a search process, therefore it is necessary to call an adaptability function
to determine the movement value and decide which movement (output) is accepted according to the
movement value and tabu table. Similarly, because TSMO is a TS search process, a bad solution may be
accepted in the search process. Thus TSMO has the stronger climbing capacity than other mutation
operators.
3 Model
The model for VRPTW can be described as follows: suppose we have a group of vehicles of same
type, a transport center, a group of clients needing transport service and a transport network connection
between the transport center and clients.
Let Vehicle aggregate V={1,2,…,K}, client aggregate C {0,1,2,… N}and directed graph G. This
directed graph has C + 2 peaks, of which peak 1 2 …,N indicate client nodes, peak 0 indicates the
transport center at departure, peak N+1 indicates the transport center at return. Arcs between the clients
and arcs between the clients and the transport centers are written as aggregate A. In addition, no arc
starts from peak N+1 and no arc ends at peak 0. Each arc (i, j) corresponds to a material consumption
value ci , j and a time value ti , j. Each vehicle has a capacity q and each client i has a demand di and a
time window [ai , bi]. This time window indicates that the vehicle must arrive at client i before bi . If the
vehicle can arrive at client i before ai
the vehicle must wait. The transport center also has a time
window [a0, b0]. This time window indicates the vehicle can’t leave from the transport center before a0
and must return to the transport center on b0 or before b0. Hereafter, we suppose q, ai, bi, di and ci , j are
non-negative integers and ti , j is a positive integer.
Variable xi jk is defined with each arch (i, j) (i≠j, i≠N+1, j≠0) and vehicle k:
0 if vehicle k doesnt arrive at node i from j
xi j k = 
1 if vehicle k arrives at node j from i
For each client i and vehicle k, let Sik indicate vehicle k accesses to client i at starting point of Sik. If
k vehicle doesn’t have access to client i, Sik is 0. If a0=0, for all vehicle k, Sok=0. For each vehicle, a route
，，
，
381
∈
，
with minimum cost is designed, which starts from peak 0 and ends peak N+1. In addition, it is necessary
to guarantee each client is accurately accessed once while the capacity constraint of each time window
and each vehicle must be satisfied.
By the above-mentioned description, model of VRPTW can be expressed as:
N
min
N
K
∑∑∑ c
(1)
ij x ijk
i = 0 j = 0 k =1
K
N
∑∑ x
s.t .
=1
ijk
i
k =1 j = 0
N
N
∑ ∑x
di
i =0
≤q
ijk
k
j =0
N
∑x
0 jk
=1
k
j =0
N
∑
i =0
∑x
hjk
=0
∑x
i , N +1,k
∈{1,2,…,N}
k {1,2,…,K}
ai ≤ sik ≤ bi
xijk ∈ {0,1}
(4)
(6)
∈{1,2,…,K}, ∀i , j∈{1,2,…,N}
k∈{1,2,…,K}, ∀i ∈{1,2,…,N}
k∈{1,2,…,K}, ∀i , j∈{1,2,…,N}
sik + tij − K (1 − xijk ) ≤ s jk
(3)
(4)
∈
=1
i =0
(2)
∈{1,2,…,K}
k {1,2,…,K}, h
j =0
N
∈{1,2,…,K}
∈
N
xihk −
∈{1,2,…,N}
k
(7)
(8)
(9)
In the above formulation, constrained condition (2) indicates that each branch store is only
accessed once; (3) indicates that the transferred vehicles all meet the capacity constrained condition;
equation (4), (5) and (6) guarantee each starts from the center warehouse and finally returns to the center
warehouse after accessing to the branch store; inequality (7) indicates that vehicle k is in the process
traveling to branch store j to branch store i and can’t arrive at branch store j before Sij +tij, of which k is a
larger scalar quantity; constrained condition (8) indicates that constraint of time window shall be met in
the traveling process of a vehicle; condition (9) is the rounding-into-integer constraint.
This model is good on versatility. Through different setting of parameters, it can be converted into
the model of other combinatorial and optimizing problem. If suppose ai=0, bi=M (M is a very large
number), time constraint (7) and (8) can be removed. In this way, VRPTW model becomes an ordinary
VRP model. If only one vehicle is used, this problem becomes TSP. If several vehicles are used and
attached condition c0j=1, j C and cij=0, model of the packing problem is obtained. If capacity
constraint (3) is removed, this model becomes m-TSPTW model; if only one vehicle is used, it becomes
TSPTW model again. If constraint (2) is removed, the model becomes the basic shortest route problem
with time window and capacity constraint. Because all vehicles are same, the short route of each vehicle
is same.
∈
4 Researching Method
After initial solution of VRPTW is found by the sequential interpolation method, we improve the
initial solution with genetic-tabu algorithm. If the optimal value or quasi-optimal value of the target
function can be determined, we generally terminate the program. However, in general the optimal value
382
of the large-scale complicated problem such as VRPTW is difficult to be determined. Here we use the
approximate criterion concerning the algorithm performance and takes account of quality of solution
and algorithm efficiency to determine whether iteration of a program is terminated or not.
4.1 Genetic encoding and decoding
The clients accessed to all routes are successively encoded into a chromosome, i.e. the clients that
are firstly accessed to in route i and route i+1 are connected to form a string that connects all routes. If
there is no bit, it indicates a route is ending and another route is starting in the string. Thus decoding
operation must be performed for the final solution.
At decoding, as the establishment process of routes, a new route is initialized and the genetic
values (client nodes) in the chromosome are interpolated into the current routes in turn. If interpolation
of a genetic value makes the load of this route above the maximum capacity of a vehicle or the returning
time later than the latest returning time of the transport center, a new route will be established. The
above-mentioned operation is repeated until all clients are interpolated into the route.
4.2 Designing adaptive value function
Because VRPTW is a combinatorial and optimizing problem, its object is to make total travel of a
vehicle the shortest, i.e. the smaller the target function value is, the larger the adaptability of the
corresponding individual (solution) is and the better performance of a solution is. In general, the
adaptability function in the minimization problem shall be the reciprocal of the target function. But the
target function value is often large in this paper. So if the reciprocal value is adopted, the adaptability
value will be too small. Therefore, we directly adopt the value of the target function as the standard
evaluating quality of an individual and redesign the selection strategy and group renewal strategy. The
larger the target function value corresponding to the individual is, the smaller the probability selected
into the next generation or into genetic operation is, and vice versa.
4.3 Genetic operation
① Selecting operator
Because we directly adopt the value of the target function as the standard evaluating quality of an
individual, we can’t use the selection mechanism directly relating to the absolute adaptability value of
the individual. Instead, we use a mixing mechanism of elitist model and rank--based mode as the basis
of selecting individual and adopt the roulette wheel selection method when the individual selection
probability is determined.
We arrange the individuals from the small to the large according to their target function values.
That is, the full group scale is N, the serial number of the individual with the minimum target function
value is 1 and the maximum serial number is N. The individuals whose serial number is 1 are directly
kept in the next generation of group. When the probability is selected after the rank is determined, we
use Potvin’s selection probability mechanism which solves Vehicle Routing Problem with Hard Time
Window (VRPHTW, hereafter) by genetic algorithm. After ranking according to the target function
value, a relative adaptability value, fitnessi , for the individual whose serial number is i is:
fitnessi = MAX − [(MAX − MIN ) × (i − 1) ÷ ( N − 1)]
(10)
Here we put MAX=1.6, MIN=0.4. Then the selection probability Pi is chosen according to the
relative size of each individual’s adaptability by the adaptability proportion selection method (roulette
wheel selection):
383
pi =
fitness i
=
N
∑ fitness
fitness i
N
(11)
j
j =1
② Tabu crossover operator
Suppose x is a child chromosome generated by parent through crossover. If the adaptive value x is
larger than the mean value of parent group’s adaptive value, it will be accepted by the next generation. If
x isn’t in tabu table, x will be also accepted, otherwise, the best chromosome in parent generation is
selected to enter the next generation.
Tabu mutation operator
Suppose x is an optimal solution (chromosome) and length of tabu table is L, which is used to store
the numbers of information bits producing variety recently. x is performed variety operation to produce a
new chromosome x’. The number of variety information bit is compared with that in tabu table. If it is in
the table, it belongs to tabu; it isn’t in the table and is smaller than the expectation level, the tabu table is
updated. If adaptive value of x’ is larger than the expectation level, it is accepted.
③
4.4 Algorithm flow solving CVRPTW
The following gives the steps in solving VRPTW with genetic-tabu algorithm. Its flow diagram is
shown in Fig. 1.
Set all control parameters involved in genetic-tabu algorithm, including group scale popsize,
proportion of random individuals in initial group Rand_Init_Popu, cross probability Pcross, variety
probability Pmutation, number of iteration cycles Maxgen and tabu length L.
Initialize each variable in the program, let generation=0.
According to parameter Rand_Init_Popu, part of the individuals in the initial group are generated by
the initial solution obtained with the scanning method. The remained individuals are randomly generated,
generation= generation+1.
Individuals are ranked according to their target function values of each individual in the current group.
The corresponding adaptability function is determined based on serial number of each individual.
Then the probability of all individuals in the group is calculated with the roulette wheel selection
method. In addition, the individual with minimum target function value is stored as the current optimal
solution and directly enters into the next generation.
Choose probability according to the individuals obtained in
and select the individuals that
directly enter the next generation or participate in crossing operation.
Crossing is carried out based on the crossing probability and tabu crossover operator TSCO is
adopted.
All individuals in the new group are changed based on varietion probability and tabu mutation
operator TSMO is adopted.
Determine whether the program termination condition is met or not: If the program termination
condition isn’t met, generation= generation+1, which turns to ; otherwise, evolution is terminated and
an optimal solution is output.
①
②
③
④
⑤
⑥
⑦
⑧
④
④
384
Initial solution generated with
interpolation method
Inputting various
control parameters
Generating initial group
Ranking individuals and computing
individual selecting probalibity base
on target function value
Selection operation
Tabu cross operator
Tabu variaty operator
N
Meeting program
terminating condition
Decoding optimal solution
Y
Outputing results
End
Figure 1 Flow Diagram of Genetic-tabu Algorithm
5 Empirical Test
①～⑧
The above flow is programmed in C++ language based on model
with genetic-tabu
algorithm designed in this paper, and six data sets given by Solomon such as R1,R2,C1,C2,RC1and RC2
are performed as trial calculation. The calculation results, as shown in Table 1, are compared with
those solved with local search algorithm, or tabu search and simulated annealing mixing algorithm, or
improved genetic algorithm (as in [18]). The best result of solving VRPTW problem at present is
shown in Table 2.
It can be seen from the results in Table 1 that our genetic-tabu algorithm performs best in
solving C1, R1 and RC2 problems, and is better than local search algorithm, tabu search and simulated
annealing mixing algorithm and improved genetic algorithm; for C2 problem, the algorithm in this paper
performs better than local search algorithm and improved genetic algorithm, and poorer than tabu search
and simulated annealing mixing algorithm; for solving R2 problem, the algorithm in this paper performs
385
better than improved genetic algorithm, and poorer than local search algorithm, tabu search and
simulated annealing mixing algorithm; for RC1 problem, the algorithm in this paper performs better
than local search, tabu search and simulated annealing mixing algorithm and poorer than improved
genetic algorithm. However it can be seen from Table 2 when VRPTW problem is solved with the
algorithm in this paper, compared with the best result at present, the relative errors are all
between0~4.4% , which indicates the mixing algorithm in this paper is more effective.
Table 1 Comparison between Result of Genetic-tabu Algorithm and Result Solved in Literature [18]
Local
Genetic-tabu
Tabu Search and simulated
Improved GA
Search
Problem
Algorithm in
Annealing Mixing Algorithm [18]
Algorithm [18]
Type
This Paper
[18]
Mean vehicle
10.0
10.0
10.0
10.0
number
C1
Mean traveling
850.71
841.92
851.05
840.16
distance
Mean vehicle
3.1
3.3
3.2
3.2
number
C2
Mean traveling
646.2
612.75
620.12
615.97
distance
Mean vehicle
13.3
13.1
13.2
13.1
number
R1
Mean traveling
1197.27
1213.16
1220.00
1189.58
distance
Mean vehicle
4.5
4.6
4.4
4.5
number
R2
Mean traveling
979.53
952.3
985.69
980.71
distance
Table 2 Comparison between Result of Genetic-tabu Algorithm and Best Solution at Present
Best
Best
Algorithm in Relative
Algorithm in Relative
Problem Solution
Problem
Solution
This Paper
Error (%)
This Paper
Error (%)
Result [18]
Result [18]
C1
827.5
836.44
+1.08
R2
942.0
975.06
+3.51
C2
589.9
607.42
+2.97
1354.1
1377.39
+1.72
RC1
R1
1174.7
1184.80
+0.86
1081.3
1128.23
+4.34
RC2
5 Conclusion
VRPTW is the extension and development of the general VRP which has been widely used now.
But it isn’t always solved effectively. GA obtains the abundant results in the field of combinatorial
optimization. In this paper we have combined tabu search with GA, and designed the computer program
that can smoothly operates and showed that this algorithm has better performances in finding the
optimal solution or the approximate optimal solution .In conclusion,it can be a good algorithm of
solving VRPTW.
386
References
[1] Dantzig G B, Ramser K B. The truck dispatch problem[J]. Operation Research, 1959, 12(1):80
[2] Solomon, M.M.. Algorithms for the Vehicle Routing and Scheduling Problems with Time-Window
ConstrainTS[J]. Operations Research, 1987, 35(2),p254 265
[3] M.Desrochers, J.Lenstra,M.Savelsbergh, and F.Soumis. Time Window Constrained Routing and
Scheduling Problems[J]. Transportation Science, 1988, 22(1),p1 13
[4] Kolen,A.W.,A.H.G.Rinnooy Kan,and H.W.J.M.Trienkens. Vehicle Routing Problem with Time
Windows[J]. Operation Research, 1987, 35(2),p266 273
[5] M.Desrochers,J.Lenstra,M.Savelsbergh, and F.Soumis. Vehicle Routing Problem with Time
Windows:Optimization and Approximation[M]. North-Holland,Amsterdam:Vehicle Routing: Methods
and Studies, 1988
[6]Fisher, M.,K.O.Jornsten and O.B.G..Madsen. Vehicle Routing with Time Windows:Two Optimization
Algorithms[J]. Operation Research, 1997, 45,p488 492
[7]Kohl, N.,and O.B.G.. Madsen. An Optimization Algorithm for the Vehicle Routing with Time
Windows based on Lagrangrian Relaxation[J]. Operation Research, 1997, 45,p395 406
[8] Potvin,J.Y. and J.M. Rousseau. A Parallel Route Building Algorithm for the Vehicle Routing and
Scheduling Problem with Time Windows[J]. European Journal of Operational Research,
1993,66,p331 340
[9] Koskosidis,Y, W.B. Powell, and M.M. Solomon. An Optmization Based Heuristic for Vehicle
Routing and Scheduling with Time Windows ConstrainTS[J]. Transportation Science, 1992,
26(2),p69 85
[10] George, K., and J.F. Bard. A GRASP for the Vehicle Routing Problem with Time Windows[J].
ORSA Journal on Computing, 1995,7(1),p10 23
[11] Tan, K.C.; Lee, L.H.; Ou, K. Artificial intelligence heuristics in solving vehicle routing problems
with time window constrainTS[J]. Engineering Applications of Artificial Intelligence,
2001,14(6),p825 837
[12] Baker, Barrie M.; Ayechew, M.A. A genetic algorithm for the vehicle routing problem[J].
Computers and Operations Research ,2003, 30(5),p787 800
[13] E.D. Taillard. Parallel iterative seareh methods for vehicle routing problems. Networks[J]. 1993,
23,p661 673
[14] Brandão, José; Mercer, Alan. A tabu search algorithm for the multi-trip vehicle routing and
scheduling problem[J]. European Journal of Operational Research,1997,100(1),p180 191
[15] Mantawy AH, Youssef L A bdel-Magid, ShokriZSelim. A new genetic-based tabu search algorithm
for unit commitment problem[J].Electric power systems Research,1999 49,p71 78
[16] Huang Jihong,Lei Zhanbo,Li Xinmiao. Research on Case Retrieval Porcess Based on a Hybrid
Approach Using Genetic Algorithms and Tabu Search [J]. Systems Engineering-Theory Methodology
Applications 2004 13(1),p10 13(in Chinese)
[17] Potvin, J.Y, and Bengio, S. The Vehicle Routing Problem with Time Windows Part 2: Genetic
Search[J]. INFORMS Journal on Computing,1996,8(2),p165 172
[18] K.C. Tan, L.H. Lee, K. Ou. Artificial intelligence heuristics in solving vehicle routing problems
with time window constraints[J]. Engineering Applications of Artificial intelligence, 2001, 14(6),p825
837
～
～
～
～
～
～
～
～
～
～
～
，
， ，
～
～
387
～
～
～