Two enhanced savings functions for the Clark-Wright algorithm

Official URL: http://esv.info/id/350311227/katalog.html

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.