Solution Techniques

Matching Based Savings Algorithm

This is an interesting modification to the standard Savings algorithm (similar descriptions are made by [Desrochers and Verhoog 1989] and [Altinkemer and Gavish 1991]) wherein at each iteration the saving $s(pq)$ obtained by merging routes p and q is computed as $s(pq) = t(p) + t(q) − t(pq)$ , where $V(k)$ is the vertex set of route k, and $t(V(k))$ is the length of an optimal TSP solution on $V(k)$ .

A matching problem over the sets $V(k)$ is solved using the $s(pq)$ values as matching costs, and the routes corresponding to optimal matchings are merged, providing feasibility is maintained. One possible variant of this basic algorithm consists of approximating the $t(V(k))$ values instead of computing them exactly.