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.

Automated summary

In this paper, a hybrid algorithm based on a discrete adaptation of the Differential Evolution metaheuristic combined with local search procedures is proposed to solve the Capacitated Vehicle Routing Problem (CVRP). The proposed algorithm, CDELS, shows significantly better results compared to state-of-the-art methods with a confidence level of 99% based on computational experiments on six classical datasets.