Solving the Capacitated Vehicle Routing Problem (CVRP) Using Clustering and Meta-heuristic Algorithm

The capacitated vehicle routing problem (CVRP) is a significant topic in distribution networks. CVRP is essentially a subset of the vehicle routing problem (VRP). As CVRP has many applications in transport, logistics, and telecommunications, exact methods are not properly suitable for finding the optimal solution to large-scale CVRP problems, so most of the researchers are focusing on meta-heuristics like genetic algorithms and ant colony algorithms. As the CVRP is an NP-hard problem, it means that an efficient algorithm for solving the problem optimally is unavailable. In this paper, approximate optimal solutions to the CVRP are generated using a two-phase method with the modified genetic algorithm. Phase one includes clustering, and the second phase is based on the genetic algorithm, which is a meta-heuristic algorithm used for finding the best solution. The proposed method is tested on a set of benchmark instances from the literature. We report computational results with this meta-heuristic algorithm on some instances taken from the literature.