Solution Techniques

Clarke and Wright Savings Algorithm

The Clarke and Wright savings algorithm is one of the best-known heuristics for the VRP. It was developed in [Clarke and Wright 1964] and it applies to problems for which the number of vehicles is not fixed (it is a decision variable), and it works equally well for both directed and undirected problems. When two routes (0,…,i,0) and (0,j,…,0) can feasibly be merged into a single route (0,…,i,j,…,0), a distance saving $s(i, j)$ is generated. The algorithm works as follows (the first step is the same in both the parallel and sequential versions):

Step 1. Savings Computation

Compute the savings $s(i, j)$ for $i, j = 1, …, n$ and i $≠$ j.
Create n vehicle routes $(0, i, 0)$ for $i = 1, …, n$ .
Order the savings in a non-increasing fashion.

Parallel Version

Step 2. Best Feasible Merge

Starting from the top of the savings list, execute the following:

Given a saving $s(i, j)$ , determine whether there exist two routes that can feasibly be merged:

One starting with $(0, j)$
One ending with $(i, 0)$

Combine these two routes by deleting $(0, j)$ and $(i, 0)$ and introducing $(i, j)$ .

Sequential Version

Step 2. Route Extension

Consider in turn each route $(0, …, i, 0)$ .
Determine the first saving $s(k, i)$ or $s(j, l)$ that can feasibly be used to merge the current route with another route ending with $(k, 0)$ or starting with $(0, l)$ .
Implement the merge and repeat this operation on the current route.
If no feasible merge exists, consider the next route and reapply the same operations.
Stop when no route merge is feasible.