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

Abstract

Bu çalışmamızda, Kapasite Kısıtlı Araç Rotalama Problemleri için kullanılan Clarke-Wright (CW) tasarruf algoritmasına değiniyoruz. Geçmişte, Gaskell (1967), Yellow (1970), Paessens (1988) ve Altınel-Öncan (2005) tasarruf formülündeki terimleri parametrize ederek ve bu formüle yeni terimler ekleyerek CW algoritmasına yeni açılımlar getirmişlerdir. Tüm bu yeni açılımların başlıca amacı, hızlı hesaplama süresinde kısa rotalar bulmaktır. Çalışmamızda, CW tasarruf formülünün iki ve üç terimli versiyonlarının performansını arttıran çeşitli yaklaşımlar önerdik. Amacımız, ek bir hesaplama yükü getirmeden çözüm kalitesini arttırmaktır. Algoritmayı, literatürdeki en bilinen örnek setleri üzerinde test ettik. Bu örnek setleri, daha once önerilmiş ve bizim de karşılatırmalı değerlendirme yaptığımız tasarruf formüllerini test etmek için de kullanılmıştır. Algoritmamız, birçok problem için literatürdeki diğer sezgisel yöntemlerden daha iyi sonuçlar vermektedir.

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.