The Granular Tabu Search and Its Application to the Vehicle-Routing Problem

TLDR

We propose a new variant of tabu search called granular tabu search. Granular tabu search employs drastically restricted neighborhoods and an intensification/diversification tool to efficiently solve graph‑theoretic and combinatorial‑optimization problems. Computational tests on the symmetric capacitated and distance‑constrained vehicle‑routing problem show the method finds very good solutions quickly.

Abstract

We describe a new variant, called granular tabu search, of the well-known tabu-search approach. The method uses an effective intensification/diversification tool that can be successfully applied to a wide class of graph-theoretic and combinatorial-optimization problems. Granular tabu search is based on the use of drastically restricted neighborhoods, not containing the moves that involve only elements that are not likely to belong to good feasible solutions. These restricted neighborhoods are called granular, and may be seen as an efficient implementation of candidate-list strategies proposed for tabu-search algorithms. Results of computational testing of the proposed approach on the well-known symmetric capacitated and distance-constrained vehicle-routing problem are discussed, showing that the approach is able to determine very good solutions within short computing times.