Enhancements of Clarke-Wright savings heuristics for the capacitated vehicle routing problem

Abstract

We address the Clarke-Wright (CW) savings algorithm proposed for the Capacitated Vehicle Routing Problem (CVRP). In the past, Gaskell (1967), Yellow (1970), Paessens (1988), and Altınel and Öncan (2005) proposed modifications on the CW function by either parameterizing it or by adding new parameterized terms. The primary objective of all these approaches is to obtain short tours with least computational effort. In this study, we propose several enhancements to the two- and three-term versions of CW savings function. Our aim is to further improve the solution quality without bringing additional computational burden to the existing approaches. To test the performance of our savings functions, we conduct an extensive computational study on a large set of well-known instances from the literature. These instances were also used by the earlier savings algorithms that we benchmark our approach with. The results show that the proposed savings functions provide shorter distances in many instances and the average performance is better than those of the previous approaches reported in the literature.