Implementation of a Hybrid Tabu Search Algorithm with Local Search for Solving the Capacitated Vehicle Routing Problem

Abstract

The Capacitated Vehicle Routing Problem (CVRP) consists of generating a customer route for each vehicle in which the sum of the customer demands does not exceed the vehicle's capacity. Each vehicle must start from the depot, and when it finishes visiting the last customer, it must return to the depot, thus managing to visit all customers only once by any of the vehicles and have a route solution where the sum of the distances of all the routes is the minimum. This research proposed using randomness and the Swap local search algorithm to create an initial solution with a good neighborhood. Later, the Tabu Search algorithm is employed to explore the solution space and obtain an improved solution. The proposed algorithms give feasible solutions with an approximation of less than a 10% difference, and in some cases, the best-known solution is obtained.