A robust enhancement to the Clarke–Wright savings algorithm

Abstract

We address the Clarke and Wright (CW) savings algorithm proposed for the Capacitated Vehicle Routing Problem. We first consider a recent enhancement that uses the put first larger items idea originally proposed for the bin packing problem and show that the conflicting idea of putting smaller items first has a comparable performance. Next, we propose a robust enhancement to the CW savings formulation. The proposed formulation is normalized to efficiently solve different problems, independent from the measurement units and parameter intervals. To test the performance of the proposed savings function, we conduct an extensive computational study on a large set of well-known instances from the literature. Our results show that the proposed savings function provides shorter distances in the majority of the instances and the average performance is significantly better than previously presented enhancements.

Appendix

Tables A1, A2, A3, A4 and A5 consist of only capacity-restricted instances whereas the instances in Table A6 include a unique data set CD of Christofides et al's with maximum route length constraint (referred to as Chr CD). This data set was not reported in Altınel and Öncan (2005), but we prefer to test it to observe the performance of our algorithm when a maximum route length is imposed. In all the tables, the instances are represented in the first column and best-known results and the results given by classical CW method are included in the second and third column, respectively. The results obtained using Paessens’ and Altınel and Öncan's savings function are denoted as P and AÖ, respectively, and reported with the corresponding parameter values (λ,μ,) and (λ,μ,v), respectively. ROBUST column shows the results obtained using the proposed savings function (7) along with the corresponding parameter values as well. Our experiments revealed that the parameter v changing within the interval [−0.1,0.1] with an increment of 0.01 works well. The ‘%Imp’ column gives the improvements in the distances obtained by P, AÖ, and ROBUST, respectively, in comparison with CW and is calculated as (CW–P)/CW, (CW–AÖ)/CW, and (CW–ROBUST)/CW, respectively.

Table 3 Relative deviations on Augerat et al's test set P.

Table 4 Relative deviations on Augerat et al's test set A.

Table 5 Relative deviations on Augerat et al's test set B.

Table 6 Relative deviations on Christofides and Eilon's test set.

Table 7 Relative deviations on Christofides et al's test set.

Table 8 Relative deviations on Christofides et al's distance restricted test set.