The Clarke and Wright savings algorithm is one of the most known heuristic for VRP. It was developed on [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_{ij}=c_{i0}+c_{0j}c_{ij}}$ is generated. The algorithm works at follows (the first step is equal in both parallel and sequential versions):
 Step 1. Savings computation

 Compute the savings ${s_{ij}=c_{i0}+c_{0j}c_{ij}}$ for ${i,j=1,…,n}$ and ${i \neq j}$.
 Create ${n}$ vehicle routes ${(0,i,0)}$ for ${i=1,…,n}$.
 Order the savings in a non increasing fashion.
 Step 2. Best feasible merge (Parallel version)

Starting from the top of the savings list, execute the following:
 Given a saving ${s_{ij}}$, determine whether there exist two routes that can feasibility 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)}$.
 Given a saving ${s_{ij}}$, determine whether there exist two routes that can feasibility be merged:
 Step 2. Route Extension (Sequential version)

 Consider in turn each route ${(0,i,…,j,0)}$.
 Determine the first saving ${s_{ki}}$ or ${s_{jl}}$ 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 to the current route.
 If not feasible merge exists, consider the next route and reapply the same operations.
 Stop when not route merge is feasible.