A variable neighborhood search algorithm for the capacitated vehicle routing problem

This paper studies the capacitated vehicle routing problem (CVRP). Since the problem is NP-hard, a variable neighborhood search (VNS) algorithm is proposed for the CVRP with the objective to minimize the total traveled distance. The proposed algorithm includes a variable neighborhood descent (VND) algorithm based on several different neighborhood structures to intensify the search effort. Various benchmark problems including the number of customers, the capacity of vehicles are tested to evaluate the performance of proposed methodology. The experimental results indicate that the proposed algorithm provides superior solutions for well-known benchmark problems compared to those reported in the literature.