  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.
