Improvement algorithms attempt to upgrade any feasible solution by performing a sequence of edge or vertex exchanges within or between vehicle routes. Multi-route improvement heuristics for the VRP operate on each vehicle route taken on several routes at a time. We can find descriptions of multi-route edge exchanges for the VRP in these three references:

• [Thompson and Psaraftis 1993]: Describes a general “b-cyclic, k-transfer” scheme in which a circular permutation of b routes is considered and k customers from each route are shifted to the next route of the cyclic permutation. The authors show that applying specific sequences of b-cyclic, k-transfer exchanges (with b = 2 or b variable, and k = 1 or 2) yields interesting results.
• [Van Breedam 1994]: Van Breedam classifies the improvement operations as “string cross”, “string exchange”, “string relocation”, and “string mix”, which can all be viewed as special cases of 2-cyclic exchanges, and provides a computational analysis on a restricted number of test problems.
• [Kinderwater and Savelsbergh 1997]: Define similar operations and perform experiments mostly in the context of the VRP with time windows.

Thompson and Psaraftis

Thompson and Psaraftis (1993) propose a method based on the concept of cyclic k-transfers that involves transferring simultaneously k demands from route ${I^{j}}$ to route ${I^{\delta(j)}}$ for each ${j}$ and fixed integer ${k}$. The set of routes ${\left \lbrace I^{r} \right \rbrace}$, with ${r = 1, \ldots, m}$, constitutes a feasible solution and ${\delta}$ is a cyclic permutation of a subset of ${\left \lbrace 1, \ldots, m \right \rbrace}$. In particular, when ${\delta}$ has fixed cardinality C, we obtain a C-cyclic k-transfer. By allowing k dummy demands on each route, demand transfers can be performed among permutations rather than cyclic permutations of routes. Due to the complexity of the cyclic transfer neighborhood search, it is performed heuristically. The 3-cyclic 2-transfer operator is illustrated in the figure below.

Van Breedam’s Analysis

We now summarize Van Breedam’s analysis. There are considered four operations, which are:

1. String Cross (SC): Two strings (or chains) of vertices are exchanged by crossing two edges of two different routes.
   
2. String Exchange (SE): Two strings of at most k vertices are exchanged between two routes.
   
3. String Relocation (SR): A string of at most k vertices is moved from one route to another, typically with k = 1 or 2.
   
4. String Mix (SM): The best move between SE and SR is selected.

   To evaluate these moves, Van Breedam considers two local improvement strategies:

   1. First Improvement (FI): Consists of implementing the first move that improves the objective function.
   2. Best Improvement (BI): Evaluates all the possible moves and implements the best one.

   Van Breedam then defines a set of parameters that can influence the behavior of the local improvement procedure:

   • The initial solution (poor, good)
   • The string length (k) for moves of type SE, SR, SM (k = 1 or 2)
   • The selection strategy (FI, BI)
   • The evaluation procedure for a string length k > 1 (evaluate all possible string lengths between a pair of routes, increase k when a whole evaluation cycle has been completed without identifying an improvement move).

Kinderwater and Savelsbergh

In Kinderwater and Savelsbergh Heuristic tours are not considered in isolation, so paths and customers are exchanged between different tours. The operations that make these changes are:

1. Customer Relocation: A customer located at one route is changed to another one
   
2. Crossover: Two routes are mixed at one point
   
3. Customer Exchange: Two customers of two different routes are interchanged between the two routes
   

In the following picture we can see a little bit more complex example: