Two enhanced savings functions for the Clark-Wright algorithm

Doyuran, Tamer and Çatay, Bülent (2008) Two enhanced savings functions for the Clark-Wright algorithm. In: Blecker, Thorsten and Kersten, Wolfgang and Gertz, Carsten, (eds.) Management in Logistics Networks and Nodes: Concepts, Technology and Applications. Operations and Technology Management (8). Erich Schmidt Verlag, Berlin, Germany, pp. 245-258. ISBN 9783503112272

Full text not available from this repository. (Request a copy)

Abstract

We address the Clark-Wright (CW) savings algorithm proposed for the Capacitated Vehicle Routing Problem (CVRP). CVRP is a well-known NP-hard problem with many real-world applications. Thus, it has attracted a lot of attention in the litera-ture and numerous heuristics have been proposed in an effort to obtain good solu-tions fast. The CW savings algorithm is one such classical heuristic which is fre-quently used due to its speed and simplicity. In the literature, Gaskell (1967), Yellow (1970), and Paessens (1988) proposed modifications on the CW function by parameterizing it and adding new terms. In this study, we consider Paessens’ (1988) two-term savings algorithm and present two further enhancements. Unlike the previous ones, our first enhancement “pro-motes” or “penalizes” the savings value between two customers by considering the cosine value of the angle formed by the two rays originating from the depot and crossing two customers. The latter enhancement enforces the customers near the depot to be placed into routes first. To test the performance of the proposed func-tions, we conducted an extensive computational study on a large set of well-known instances from the literature. Our results show that the proposed approaches provide shorter distances in many instances and the average performance is better than that of Paessens.
Item Type: Book Section / Chapter
Subjects: T Technology > TS Manufactures
T Technology > TS Manufactures > TS0155-194 Production management. Operations management
Divisions: Faculty of Engineering and Natural Sciences
Faculty of Engineering and Natural Sciences > Academic programs > Manufacturing Systems Eng.
Depositing User: Bülent Çatay
Date Deposited: 23 Oct 2008 00:30
Last Modified: 19 Jul 2019 12:03
URI: https://research.sabanciuniv.edu/id/eprint/9445

Actions (login required)

View Item
View Item