An efficient variable neighborhood search with tabu shaking for a class of multi-depot vehicle routing problems

We present a Variable Tabu Neighborhood Search (VTNS) algorithm for solving a class of Multi-Depot Vehicle Routing Problems (MDVRP). The proposed algorithm applies a granular local search mechanism in the intensification phase and a tabu shaking mechanism in the diversification phase of Variable Neighborhood Search. Furthermore, it allows the violation of problem-specific constraints throughout the search in an attempt to escape from local optima and to converge to a high-quality feasible solution. VTNS is a flexible algorithm; with simple adaptations it can be implemented to solve MDVRP, MDVRP with Time Windows (MDVRPTW) and Multi-Depot Open Vehicle Routing Problem (MDOVRP). Our computational tests on these three problems show that VTNS provides promising results competitive with state-of-the-art algorithms from the literature in terms of both solution quality and run time. Overall, we achieve six new best-known solutions in the MDVRP, one in the MDVRPTW, and four in the MDOVRP benchmark data sets.