CHAPTER 3. THE INSERTION HEURISTIC
88888 88888
99999 99999
::::::;;;;;
<<<<<<
<<<<<<
=====
=====
>>>>>>
>>>>>>
?????
?????
@@@@@@AAAAA BBBBB
BBBBB BBBBB BBBBB BBBBB
CCCCC CCCCC CCCCC CCCCC CCCCC DDDDD DDDDD DDDDD DDDDD DDDDD
EEEEE EEEEE EEEEE EEEEE EEEEE
FGHI
JJJJJ KKKKK
L MMMMMM
MMMMMM MMMMMM MMMMMM MMMMMM MMMMMM MMMMMM MMMMMM MMMMMM MMMMMM MMMMMM MMMMMM MMMMMM MMMMMM MMMMMM MMMMMM
NNNNN NNNNN NNNNN NNNNN NNNNN NNNNN NNNNN NNNNN NNNNN NNNNN NNNNN NNNNN NNNNN NNNNN NNNNN NNNNN
OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO
PPPPP PPPPP PPPPP PPPPP PPPPP QQQQQQ QQQQQQ QQQQQQ QQQQQQ QQQQQQ QQQQQQ QQQQQQ QQQQQQ QQQQQQ QQQQQQ QQQQQQ QQQQQQ QQQQQQ QQQQQQ QQQQQQ QQQQQQ
RRRRR RRRRR RRRRR RRRRR RRRRR RRRRR RRRRR RRRRR RRRRR RRRRR RRRRR RRRRR RRRRR RRRRR RRRRR RRRRR
SSSSS SSSSS
TTTTT TTTTT
100 200 300 400
0 1 2
time
480 480 480
waiting time
caretakers transport time
working time as regular caretaker working time as not regular caretaker
94
4 1 99 159 164 180 245 270
2 5 300 6
6 3
390 395
300
240 420
7 57 6696 100 180 240 244 330 390 396
7 9 11 10
12 13
160 160
7 100 160 167
Figure 3.12: The schedule for the 3 caretakers with the shared visit consisting of visit 12 and 13
UUUUU UUUUU UUUUU
VVVVV VVVVV VVVVV
WWWWWW
XXXXX YYYYYY YYYYYY YYYYYY
ZZZZZ ZZZZZ ZZZZZ [[[[[[ [[[[[[ [[[[[[
\\\\\
\\\\\
\\\\\ ]]]]]]
^^^^^ _____
_____ _____ _____ _____
`````
`````
`````
`````
`````
abbcdd
eeeee
fffff
g hhhhhh
hhhhhh hhhhhh hhhhhh hhhhhh hhhhhh hhhhhh hhhhhh hhhhhh hhhhhh hhhhhh hhhhhh hhhhhh hhhhhh hhhhhh hhhhhh
iiiii iiiii iiiii iiiii iiiii iiiii iiiii iiiii iiiii iiiii iiiii iiiii iiiii iiiii iiiii iiiii
jjjjjj jjjjjj jjjjjj jjjjjj jjjjjj
kkkkk kkkkk kkkkk kkkkk kkkkk llllll llllll llllll llllll llllll llllll llllll llllll llllll llllll llllll llllll llllll llllll llllll llllll
mmmmm mmmmm mmmmm mmmmm mmmmm mmmmm mmmmm mmmmm mmmmm mmmmm mmmmm mmmmm mmmmm mmmmm mmmmm mmmmm
nnnnn nnnnn
ooooo ooooo ppppp ppppp ppppp ppppp
qqqqq qqqqq qqqqq qqqqq
r
100 200 300 400
0 1 2
time
480 480 480
waiting time
caretakers transport time
working time as regular caretaker working time as not regular caretaker
94
4 1 99 159 164 180 245 270
2 5 300 6
6 3
390 395
300
240 420
7 57 6696 100 180 240 330 390 396
7 9 11 10
12 13
160 160
7 100 160 167 247 277 286 8
Figure 3.13: The schedule for the 3 caretakers with all visits
Chapter 4
Tabu Search
Tabu search is based on the concept of performing changes to a solution in the attempt to obtain an improved solution. The change of a solution is called a move from one solution to another. The solutions that can be reached from a solutionxby making moves is called aneighbourhood. More formally a neighbourhood functionN can be described as a mapping from the solution spaceS to the same solution spaceS
N : S → S
The argument for the neighbourhood is a solutionx∈ S and the output is a subset ofS. The neighbourhood ofxis denotedN(x), where each ˆx∈N(x) is a neighbour tox.
The slides [Sti05] give a set of useful tools for evaluating neighbourhoods and how they are used. The special issues to consider when using neigh-bourhoods are.
Coverage: Whether the neighbourhood is able to cover the whole solution space by one type of move, or if several types of moves are required.
It is not necessarily bad when the whole solution space can not be reached, if the good solutions can be reached
Guidance: Should the best solutions in the neighbourhood be chosen? It could have both advantages and disadvantages. An advantage would be obtaining good solutions faster, but the disadvantages are more computation time or maybe misleading the search.
CHAPTER 4. TABU SEARCH
Continuity: Neighbourhood solutions should be related, otherwise the search becomes random. A relationship could be that a good solu-tionx implies a good neighbour ˆx.
Size: The size of the neighbourhood is of importance, because it can both be too small or too big. A neighbourhood too small can not perform a good search and the risk of ending up in a locale optimum arises.
Neighbourhoods too large demand too much computational effort.
Feasibility: It should be considered whether the good solutions are on the border to infeasibility, and if it should be avoided to obtain infeasible solutions. In the case, where infeasible solutions are obtained, how should they be handled?
Local search is based on the idea to find better solutions by making moves and looking in the neighborhood for better solutions. There is a problem of guidanceif one always go from worse to better solution, because it is possible to get stuck in a locale optimum. Figure 4.1 illustrates this situation, where the local search is stuck in a valley.
Objective value
PSfrag replacements
x
Figure 4.1: A locale minimum
To avoid ending up in a locale optimum, it is allowed to go to worse solutions.
This may cause a new problem;cycling, which means that the search revisits solutions, that have been visited before. This can be avoided by having a tabu strategy. The tabu search has a tabu strategy, which for instance can forbid the solutions in the last iterations or the last moves to be used again.
Which tabu strategy is best depends on the type of the problem.
Tabu search is a metaheuristic. A metaheuristic a heuristic, which can be adapted to different problems. As other heuristics a metaheuristic does not
CHAPTER 4. TABU SEARCH
necessarily find the optimal solution. The tabu search has showed to be very efficient for many kinds of problems, and is therefore one of the most used metaheuristics.
In the VRPTWSV, it is difficult to perform a move without violating any of the constraints, hence it would be a good idea to allow infeasible solutions.
One might also expect the good solutions to lie on the border offeasibility.
The question is how to treat the infeasible solutions? The article [CLA01]
gives an answer to this question, where unified tabu search is introduced on the VRPTW. The main feature of this method is that the problem is relaxed in the same way as Lagrangean relaxation, where it is possible to violate certain constraints, and the violation is penalized. The penalties varies dependent on the number of times a certain constraint is violated.
In this case with VRPTWSV it is possible to violate the constraints (2.22), (2.24) and (2.27).
Relaxing the constraint (2.27) involve accepting starting a visit later than the latest starting time bi for every visit i∈ V. The cost for every minute of violation isα. The total violation is given in (4.1).
A(x) =X
i∈V
max{si−bi,0} (4.1)
Relaxing the constraint (2.22) is the same as allowing the two separate visits in a shared visit to start at different times. The price for this violation is β per minute. The total violation is given in (4.2). Notice that the multiplication by 1/2, which is applied, because every pair of visits (i,j) is included twice in the summation.
B(x) = 1 2
X
i,j∈V
ωij|si−sj| (4.2)
Relaxing the last constraint (2.24) is equivalent to allowing caretakers to work later than the latest finishing timehr for every r ∈ R. The price per minute for this violation is γ. The total violation is given in (4.3), where fr= max{fi|i∈r}.
G(x) =X
r∈R
max{fr−hr,0} (4.3)
CHAPTER 4. TABU SEARCH
The pricesα, βandγ are positive and they are modified after each iteration in the search. The positive factorδis the modification factor. If a constraint among (2.27), (2.22) or (2.24) is violated, it implies that the corresponding price α, β or γ is multiplied by (1 +δ). If the constraint is not violated, it implies that the price will be divided by (1 +δ).
The already known cost function C(x) is given as T +µΨ in the objective function (2.16) in the mathematical model for the VRPTWSV. The cost C(x) forms together with A(x), B(x) and G(x) the new cost F(x) as in (4.4). The use of F(x) is explained in section 4.4.
F(x) =C(x) +αA(x) +βB(x) +γG(x) (4.4) Notice that the prices α, β and γ in the article [CLA01] correspond to violations, that are different from the violations in this project, namely the violation of the maximum load capacity at the vehicles, the violation of the routes’ durations and the violation of the latest starting times at customers.
Algorithm 7 shows the pseudo code for the tabu search, where the method starts in an initial solutionx. In this project the initial solution is a feasible solution found by the insertion heuristic described in chapter 3. The moves and neighbourhood functions used in this project are introduced in section 4.1 and 4.2.
Algorithm 7 Tabu Search
1: xis a initial solution
2: x∗is the best feasible solution currently 3: if xis feasiblethen
4: x∗:=x 5: C(x∗) :=C(x) 6: else
7: C(x∗) :=∞ 8: end if
9: whilestop criterion not reacheddo
10: choose the best solution ˆx∈N(x), which is not tabu or satisfies the aspiration criteria 11: if ˆxis feasible andC(ˆx)< C(x∗)then
12: x∗:= ˆx 13: C(x∗) :=C(ˆx) 14: end if
15: Updateα,βandγ 16: x:= ˆx
17: end while
For every iteration is the best non-tabu solution in the neighbourhood cho-sen. The section 4.3 describes what characterizes a non-tabu solution. The evaluation used for finding the best solution includes a factor for diversifying the search, which will be introduced in the section 4.4. If the best solution turns out to be tabu, it can still be chosen, if it satisfies the aspiration
cri-CHAPTER 4. TABU SEARCH
terion described in section 4.5. The stopping criterion for the method is introduced in section 4.6.
In the article [CLA01], they suggest violating the latest starting times for visits, but not the earliest starting times, and this is discussed in section 4.7.
The section 4.8 contains a discussion on how the starting times of the visits in a route are updated, when removing a visit from a route or inserting a visit in a route.