An ILS matheuristic for the Capacitated Vehicle Routing Problem

The Capacitated Vehicle Routing Problem (CVRP) is a classic combinatorial optimization problem with wide theoretical and practical applications and has been studied for nearly 70 years. This work proposes a hybrid matheuristic for the CVRP to evaluate how initial solution methods, local searches, and perturbations affect final solution quality and computation time. The approach is based on Iterative Local Search (ILS) and, after execution, applies a column-and-cut procedure to compute the optimality gap and search exactly for new integer solutions. Tests on benchmark instances show that the method finds about 35% of known optimal solutions with an average runtime of 176 seconds.