Department of Business Administration2024-11-0920210305-054810.1016/j.cor.2021.1052692-s2.0-85107091578http://dx.doi.org/10.1016/j.cor.2021.105269https://hdl.handle.net/20.500.14288/12144We 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 com-putational 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.Computer science, interdisciplinary applicationsEngineering, industrialOperations research and management scienceJournal Article1873-765X659230600002Q110852