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)

[thumbnail of 1-s2.0-S0305054821000617-main.pdf] PDF
1-s2.0-S0305054821000617-main.pdf
Restricted to Registered users only

Download (974kB) | Request a copy

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

Actions (login required)

View Item
View Item