An efficient variable neighborhood search with tabu shaking for a class of multi-depot vehicle routing problems
Hesam Sadati, Mir Ehsan and Çatay, Bülent and Aksen, Deniz (2021) An efficient variable neighborhood search with tabu shaking for a class of multi-depot vehicle routing problems. Computers and Operations Research, 133 . ISSN 0305-0548 (Print) 1873-765X (Online)
Official URL: http://dx.doi.org/10.1016/j.cor.2021.105269
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 VariableNeighborhood 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.
Repository Staff Only: item control page