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_{ij}}$ obtained by merging routes ${p}$ and ${q}$ is computed as ${s_{ij}=t(S_{i})+t(S_{j})-t(S_{i} \bigcup S_{j})}$, where ${S_{k}}$ is the vertex set of route ${k}$, and ${t(S_{k})}$ is the length of an optimal TSP solution on ${S_{k}}$.

A matching problem over the sets ${S_{k}}$ is solved using the ${s_{ij}}$ 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 on approximating the ${t(S_{k})}$ values instead of computing them exactly.