A genetic local search algorithm for the capacitated vehicle routing problem

摘要

This paper aims to examine the capacitated vehicle routing problem (CVRP). It is a major logistics problem encountered by any company that must organize the distribution of its products. The CVRP is an NP-hard problem. This problem involves planning vehicle routes that are to serve a number of customers from a depot. The capacity of each vehicle is limited and each customer has demanded who must be satisfied. The objective of this problem is to minimize the total distance travelled by vehicles. It is a very broad class of problems, including the famous traveling salesman problem (TSP). The goal of this paper is to find a solution for CVRP using a hybrid heuristic. This heuristic, called, genetic local search algorithm (GA-LS). We propose a genetic algorithm with a new procedure crossover operator to minimize the total travelled distance. To simplify the problem, a natural number coding is used and to assure enough diversification into the algorithm the best selection is retained. Local search uses performance indicators in order to maintain a balance between convergence and the diversity of the solutions obtained. Large numerical experiments are made to prove the efficiency of the proposed algorithm. Our approach is compared to the different existing approaches. The results show that our approach is very competitive in terms of the solutions obtained. Based on five reference data sets our approach obtains a total of 45 values equal to the best- known solution for 57 instances.