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

Doyuran, Tamer (2008) Enhancements of Clarke-Wright savings heuristics for the capacitated vehicle routing problem. [Thesis]

[img]PDF - Registered users only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: (Table of Contents)


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.

Item Type:Thesis
Uncontrolled Keywords:Vehicle routing problem. -- Clarke-Wright algorithm. -- Heuristics. -- Capacitated vehicle routing problem. -- Clarke-Wright savings heuristic. -- Araç rotalama problemi. -- Clarke-Wright algoritması. -- Sezgisel yöntemler. -- Kapasite kısıtlı araç rotalama problemi. -- Clarke-Wright tasarruf yöntemi.
Subjects:T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
ID Code:14115
Deposited By:IC-Cataloging
Deposited On:05 Jul 2010 17:02
Last Modified:05 Jul 2010 17:02

Repository Staff Only: item control page