A multi-start ILS–RVND algorithm with adaptive solution acceptance for the CVRP
Articles > Article · 2019
Authors: OSMAN GÖKALP, Aybars UĞUR
Soft Computing, Journal Indexed in SCI Expanded, International, WoS, 2019, vol 24, pp 2941-2953
DOI: 10.1007/s00500-019-04072-6
Summary
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.