An Effective Local Search Algorithm for the Multidepot Cumulative Capacitated Vehicle Routing Problem

The cumulative capacitated vehicle routing problem (CCVRP) focuses on minimizing the sum of arrival times at the customers. An important application of the CCVRP arises in the procurement of humanitarian aid when natural disasters occur. In this article, the multidepot CCVRP (MDCCVRP) is investigated, and its mathematical model is developed. Moreover, an effective perturb-based local search (PLS) algorithm is proposed to solve the problem. The proposed PLS algorithm starts from having a feasible solution. Regarding the PLS, the perturbing operators help to explore the searching space, while the six local search operators help to exploit the best solution within each searching basin. To test the performance, the proposed PLS is applied to a set of standard benchmark instances and compared with the recently published algorithms. Extensive computational studies reveal that the proposed PLS algorithm is able to attain better solutions with less computational time for most testing instances, and thus competes very favorably with the previously proposed approaches. A stability analysis is also presented to shed light on the robust behavior of the proposed algorithm. The results of the two-sided Wilcoxon rank sum tests clearly show that the algorithms (our PLS and other published methods) have performed with statistically significant differences.