A robust algorithm based on Differential Evolution with local search for the Capacitated Vehicle Routing Problem
Israel Pereira de Souza, Maria Claudia Silva Bóeres, Renato Elias Nunes de Moraes
Abstract
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.