A robust algorithm based on Differential Evolution with local search for the Capacitated Vehicle Routing Problem

The Capacitated Vehicle Routing Problem is a well-known combinatorial problem . In this paper, we propose a hybrid algorithm based on a discrete adaptation of the Differential Evolution metaheuristic , which is designed for continuous problems, combined with local search procedures to solve CVRP. An individual in the algorithm represents a CVRP solution. The algorithm presents a discrete adaptation for DE that consists on exchanging customers considering their routes positions, instead of arithmetically modifying the individuals. The proposed algorithm, called CDELS, is compared with three state-of-the-art algorithms. The computational experiments are performed on six classical datasets, with an extensive study for parameter tuning. A statistical analysis of the results was also conducted. It showed that the CDELS algorithm is highly significantly better than state-of-the-art methods with a confidence level of 99%. CDELS is open-source.