  Metaheuristics are widely employed to solve hard optimization problems, like
vehicle routing problems (VRP), for which exact solution methods are
impractical. In particular, local search-based metaheuristics have been
successfully applied to the capacitated VRP (CVRP). The CVRP aims at defining
the minimum-cost delivery routes for a given set of identical vehicles since
each vehicle only travels one route and there is a single (central) depot. The
best metaheuristics to the CVRP avoid getting stuck in local optima by
embedding specific hill-climbing mechanisms such as diversification strategies
into the solution methods. This paper introduces a hybridization of a novel
adaptive version of Iterated Local Search with Path-Relinking (AILS-PR) to the
CVRP. The major contribution of this paper is an automatic mechanism to control
the diversity step of the metaheuristic to allow it to escape from local
optima. The results of experiments with 100 benchmark CVPR instances show that
AILS-PR outperformed the state-of-the-art CVRP metaheuristics.
