Solution Techniques

Multi-Route Improvement Algorithms

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 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 $r(j)$ to route $r(σ(j))$ for each j and fixed integer k. The set of routes $r(1..m)$ , with $m ≥ 2$ , constitutes a feasible solution and $σ$ is a cyclic permutation of a subset of ${1, …, m}$ . In particular, when $σ$ 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.

The 3-cyclic 2-transfer operator — The cyclic transfer operator. The basic idea is to transfer simultaneously the customers denoted by white circles in a cyclical manner between the routes. More precisely, here customers a and c in route 1, f and j in route 2 and o and p in route 4 are simultaneously transferred to routes 2, 4, and 1 respectively, and route 3 remains untouched.

Van Breedam's Analysis

We now summarize Van Breedam's analysis. Four operations are considered:

String Cross (SC): Two strings (or chains) of vertices are exchanged by crossing two edges of two different routes.

String cross operation — String Cross (SC).

String Exchange (SE): Two strings of at most k vertices are exchanged between two routes.

String exchange operation — String Exchange (SE).

String Relocation (SR): A string of at most k vertices is moved from one route to another, typically with k = 1 or 2.

String relocation operation — String Relocation (SR).

String Mix (SM): The best move between SE and SR is selected.

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

First Improvement (FI): Consists of implementing the first move that improves the objective function.
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 the 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:

Customer Relocation: A customer located on one route is moved to another one.

Customer relocation operation — Customer Relocation.

Crossover: Two routes are mixed at one point.

Customer Exchange: Two customers of two different routes are interchanged between the two routes.

Customer exchange operation — Customer Exchange.

In the following pictures we can see slightly more complex examples:

More complex Kinderwater and Savelsbergh move examples — More complex exchange examples.