AILS-II: An Adaptive Iterated Local Search Heuristic for the Large-scale Capacitated Vehicle Routing Problem

A recent study on the classical Capacitated Vehicle Routing Problem (CVRP) introduced an adaptive version of the widely used Iterated Local Search (ILS) paradigm, hybridized with a path-relinking strategy (PR). The solution method, called AILS-PR, outperformed existing meta-heuristics for the CVRP on benchmark instances. However, tests on large-scale instances of the CVRP suggested that PR was too slow, making AILS-PR less advantageous in this case. To overcome this challenge, this paper presents an Adaptive Iterated Local Search (AILS) with two phases in its search process. Both phases include the perturbation and local search steps of ILS. The main difference between them is that the reference solution in the first phase is found by the acceptance criterion, while in the second phase it is selected from a pool of the best solutions found in the search process, the so-called elite set. This algorithm, called AILS-II, is very competitive on smaller instances, outperforming the other methods from the literature with respect to the average gap to the best known solutions. Moreover, AILS-II consistently outperformed the state of the art on larger instances with up to 30,000 vertices.