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

Warning The system is temporarily closed to updates for reporting purpose.

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