Hybrid Approach to Solve the Capacitated Vehicle Routing Problem

The Capacitated Vehicle Routing Problem (CVRP) is one of the most studied problems in the field of transport logistics. This given that transport represents up to 10% of the value of a product. CVRP addresses the situation of finding the optimal number of vehicles to meet the demands of a set of customers. The assignment of vehicles to customers must be consolidated in routes of minimum cost, distance or time. Because this problem is of the NP-hard type, there are few instances that can be solved optimally. In this article, a greedy algorithm is presented to obtain approximate solutions to this problem in a fast way with the free license software Octave. For the comparison of results, instances with optimal values of the CVRPLIB database were used. The results showed that this algorithm was able to obtain feasible solutions with errors less than 14.0% for medium to large CVRP instances. In some cases, near-optimal solutions were obtained.