Solution of the Capacitated Vehicle Routing Problem using Variable Neighborhood Search with Threshold

The capacitated vehicle routing problem (CVRP) arises in daily logistics problem. Here a set of customers are served by a number of similar vehicles originated from a depot. The aim is to find the shortest routes to serve the customers. An adaptation of the variable neighborhood search (VNS) is used to solve the CVRP. In the algorithm, a threshold is applied in the shaking procedure. A number of neighborhood and local searches are used in the searching process. In the local search, the first improvement search strategy is used. Five instances from literature are used to test the proposed algorithm. The solutions produced are good, as the average deviation obtained by the proposed algorithm is just 0.04% less than the average deviation of the recently published CVRP paper.