A multi-start ILS-RVND algorithm with adaptive solution acceptance for the CVRP

This study proposes a novel hybrid algorithm based on Iterated Local Search (ILS) and Random Variable Neighborhood Descent (RVND) metaheuristics for the purpose of solving the Capacitated Vehicle Routing Problem (CVRP). The main contribution of this work is that two new search rules have been developed for multi-starting and adaptive acceptance strategies, and applied together to enhance the power of the algorithm. A comprehensive experimental work has been conducted on two common CVRP benchmarks. Computational results demonstrate that both multi-start and adaptive acceptance strategies provide a significant improvement on the performance of pure ILS-RVND hybrid. Experimental work also shows that our algorithm is highly effective in solving CVRP and comparable with the state of the art.