A Granular Variable Tabu Neighborhood Search for the capacitated location-routing problem

• We propose a novel heuristic for the Capacitated Location Routing Problem (CLRP).
• The algorithm includes a Granular Tabu Search within a Variable Neighborhood Search.
• The proposed algorithm is able to obtain good solutions in short CPU times.
• The algorithm finds 5 new best solutions on the benchmarking instances for the CLRP.

This paper proposes a new heuristic algorithm for the Capacitated Location-Routing Problem (CLRP), called Granular Variable Tabu Neighborhood Search (GVTNS). This heuristic includes a Granular Tabu Search within a Variable Neighborhood Search algorithm. The proposed algorithm is experimentally compared on the benchmark instances from the literature with several of the most effective heuristics proposed for the solution of the CLRP, by taking into account the CPU time and the quality of the solutions obtained. The computational results show that GVTNS is able to obtain good average solutions in short CPU times, and to improve five best known solutions from the literature. The main contribution of this paper is to show a successful new heuristic for the CLRP, combining two known heuristic approaches to improve the global performance of the proposed algorithm for what concerns both the quality of the solutions and the computing times required to find them.