Moves

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.

CHAPTER 4. TABU SEARCH

windows and the opportunity of exploring more different new solutions. By performing the relocation between routes, one can also end up having made a relocation within a route. Or considered a new variant of relocating in [Or76], which introduced relocating a chain of consecutive vertices instead of only moving one vertex.

Exchanging vertices are illustrated at figure 4.3, where the two verticesiand j are exchanged. This correspond to performing a relocating twice, where the vertex iis relocated in one move and the other vertex j is relocated in the other move.

PSfrag replacements

i i

i+ 1

i+ 1 i−1

i−1

j−1 j−1

j j

j+ 1 j+ 1

Figure 4.3: Exchanging vertices

An extension of exchanging vertices could start in the idea of relocating chains of vertices from one route to another, where a chain of the last visits in one route is exchanged with another chain of the last visits in another.

This exchange corresponds to an exchange of edges also called a cross as seen in figure 4.4, where the edges (i, i+ 1) and (j, j+ 1) are exchanged with the edges (j, i+ 1) and (i, j + 1).

PSfrag replacements i i

i+ 1

i+ 1 j

j

j+ 1 j+ 1

Figure 4.4: Exchanging edges

Exchanging two edges is also named a2-opt exchange. This procedure can also be expanded to for instance a 3-opt exchange and so on. These ex-changes were introduced by Lin in [Lin65] For each move there are two op-portunities for how to perform the move: within a route or between routes.

There first opportunity will only perform well in problems, where the time windows of the visits are very wide. This opportunity will not be used, because the VRPTWSV does not necessarily have wide time windows. The other opportunity fits well the VRPTWSV, when the cost ψ is large, be-cause one has the opportunity of moving visits from routes with non-regular caretakers to routes with regular caretakers.

CHAPTER 4. TABU SEARCH

All the moves presented here are all simple and quick moves, but the relo-cating is the most simple, because the other two moves can be performed by doing more than one relocation. The thesis [Br¨a01] compares different between-routes improvement heuristics. The results of the comparison is listed in table 9, page 116 in the thesis [Br¨a01]. The results for relocation, exchanging of nodes or edges show that the relocation move seems to per-form better than the other quick moves. Based on these good results, the relocation move is chosen to be applied in the tabu search in this project.

4.1.1 The Implementation of a Move

In the VRPTWSV only the unlocked visits can be moved. The locked visits e.g. start visits and breaks are locked to a caretaker, and can therefore not be moved.

Performing a move involves two functions. One for removing a visit v from a route ¯r and one for inserting the visit in another route r^∗. The insertion function in algorithm 4 in chapter 3 is used again without the setsV and ¯V. The push forward function in algorithm 6 is also used again with the change that it only performs the push forward within one route. The push forward does not pay attention to the starting time of the shared visits, because the starting times do not need to be synchronous, when constraint (2.22) is relaxed. The starting time of a inserted visit i is set to max{l_i, a_i}, where the arrival timel_i is given by (3.1). The insertion and push forward function is changed to calculate the new total violations of latest starting times given in (4.1), the new total violation of same starting times for shared visits given in (4.2) and the new total violation of latest finishing times for the workers given in (4.3).

The new total violation of latest starting timeA(ˆx) is calculated by adding the differences between the old and the new violations for all visits in router^∗ succeeding the inserted visit, including the inserted visitvand the previously succeeding visits in ¯r. The calculation is

A(ˆx) =A(x) +X

k

(max{ˆs_k−b_k,0} −max{s_k−b_k,0}),

wherek belongs to the set of visits includingv and the succeeding visits in route r^∗ or the previously succeeding visits in route ¯r.

The new total violation of the synchronous starting times for a shared visit B(ˆx) is only calculated if the inserted visitvor if one of the succeeding visits iin the router^∗ or ¯r is shared. In such case the difference between the old

CHAPTER 4. TABU SEARCH

and new violation of synchronous starting times for those eventually shared visits is added to the total violation of the synchronous starting time for the shared visits in this manner

B(ˆx) =B(x) +X

k,j

(|sˆ_k−sˆ_j| − |s_k−s_j|)

wherek is a visit in the set of the shared visits which may includevand the succeeding visits in router^∗ or the previously succeeding visits in route ¯r if they are shared andj is the other half of each eventually shared visitk.

The new total violation of the latest finishing time is calculated by finding the old and new latest finishing times in the router^∗ and ¯r. The difference is added to the total violation of the latest finishing times

G(ˆx) = G(x) + max{fˆ_r^∗−h_r^∗,0} −max{f_r^∗−h_r^∗,0}+ max{fˆr¯−hr¯,0} −max{f¯r−h¯r,0}

wherefr^∗is the finishing time of the last visit in router^∗ in the old solution x and the ˆf_r^∗ is the finishing time of the last visit in the route r^∗ in the solution ˆx, which could be a new visit, if v is inserted at the last position.

The notation is similar for route ¯r.

When removing the visitv, a push-back function is defined. It is very simple.

The visit after v has defined a new starting time, which is the maximum of the new arrival time and the earliest starting time. The difference of the old and the new starting time is the push backward for all the succeeding arrival times in the route considered. The new starting times of the succeeding visits k is max{l_k, a_k}. This push backward function does again not pay any special attention to the shared visits, because the starting times do not need to be synchronous, when constraint (2.22) is relaxed.

The push functions used in the implementation of a move do only pay atten-tion to those times, that are delayed e.g. the starting times greater than the latest starting times and the finishing times greater than the latest finishing times. The push functions can not pay attention to the starting times, that can be too early e.g. a part of a shared visit starts before the other. In sec-tion 4.7 it is suggested how to avoid this problem by solving a LP-problem.

A comparison of the strategies is in section 4.8, where the problem with the push functions is illustrated by an example in subsection 4.8.1.

CHAPTER 4. TABU SEARCH