A Comparative Study on Algorithms for Solving Capacitated Vehicle Routing Problem

Vehicle Routing Problem (VRP) is one of the most widely known questions in a class of combinatorial optimization problems. It is concerned with the optimal design of routes to be used by a fleet of vehicles to serve a set of customers. In this study I analyze Capacitated Vehicle Routing Problem (CVRP) – a subcase of VRP, where the vehicles have a limited capacity. CVRP is aimed at savings in the logistic transportation costs. Typical applications of CVRP are delivery of goods, solid waste collection, street cleaning etc. The problem is NP-hard, therefore heuristic algorithms, which provide near-optimal polynomial-time solutions, will be considered instead of the exact ones. The first aim of this article is to make a survey on mathematical formulations of CVRP and on methods for solving each type of this problem. This paper provides an overview of the most perspective methods to be deeply analyzed in later works. The second goal of this work is to make an experimental comparison of constructive heuristics for classical CVRP as there were not found any such classification. In most cases, the leader by a criterion of quality is Clarke and Wright Savings heuristic; however, there are other algorithms showing better results on a few instances. The third aim of this work is to make an experimental comparison of metaheuristics by criteria of solution quality and computing time as there were not found any such classification also. Five Pareto optimal groups of metaheuristics for different types of input data are defined. It is interesting that Lin, Kernighan and Helsgaun heuristic (LKH-3) – a member of all Pareto optimal groups in a related field (in TSP) – belongs not to all Pareto optimal sets, but only to four of them.