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]

[thumbnail of TamerDoyuran.pdf] PDF

Download (391kB)


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
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Manufacturing Systems Eng.
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 05 Jul 2010 17:02
Last Modified: 26 Apr 2022 09:51
URI: https://research.sabanciuniv.edu/id/eprint/14115

Actions (login required)

View Item
View Item