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)
![[thumbnail of 1-s2.0-S0305054821000617-main.pdf]](https://research.sabanciuniv.edu/style/images/fileicons/application_pdf.png)
1-s2.0-S0305054821000617-main.pdf
Restricted to Registered users only
Download (974kB) | Request a copy
Official URL: http://dx.doi.org/10.1016/j.cor.2021.105269
Abstract
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.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Vehicle routing problem, Multi-depot, Time windows, Open vehicle routing, Variable neighborhood search, Tabu shaking |
Subjects: | T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis |
Divisions: | Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering Faculty of Engineering and Natural Sciences |
Depositing User: | Mir Ehsan Hesam Sadati |
Date Deposited: | 11 Jun 2021 17:15 |
Last Modified: | 03 Sep 2022 22:35 |
URI: | https://research.sabanciuniv.edu/id/eprint/41523 |