A Simulated Annealing Approach for the Homogeneous Capacitated Vehicle Routing Problem

This study addresses the Capacitated Vehicle Routing Problem (CVRP) known to be NP-hard. In this problem, a set of customers with varying demands is considered. To solve the problem, routes were generated for several vehicles with identical capacity, which were responsible for delivering products to a set of geographically dispersed customers. The purpose of the problem is to minimize the total cost of all routes. This problem was solved by applying the metaheuristic Simulated Annealing (SA) and incorporating four different neighborhoods to improve the initial solution generated randomly. In the SA, a set of cooling factors is used. The best solution obtained by SA is refined by the use of Hill Climbing using a double neighborhood. The algorithm was tested with instances from the literature in order to measure its effectiveness in solution quality and execution time. We tested the approach with 106 instances from the literature and obtained the optimum in 93 instances. The average time in most instances was less than five minutes. Delivery companies can benefit from this approach. They only need to identify the depot, the clients, and the distance between locations, and this approach can be used with relative ease.