The Granular Tabu Search and Its Application to the Vehicle-Routing Problem
- 1 November 2003
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 15 (4), 333-346
- https://doi.org/10.1287/ijoc.15.4.333.24890
Abstract
We describe a new variant, calledgranular tabu search, of the well-known tabu-search approach. The method uses an effective intensification/diversification tool that can be successfully applied to a wide class of graph-theoretic and combinatorial-optimization problems. Granular tabu search is based on the use of drastically restricted neighborhoods, not containing the moves that involve only elements that are not likely to belong to good feasible solutions. These restricted neighborhoods are calledgranular, and may be seen as an efficient implementation of candidate-list strategies proposed for tabu-search algorithms. Results of computational testing of the proposed approach on the well-known symmetric capacitated and distance-constrained vehicle-routing problem are discussed, showing that the approach is able to determine very good solutions within short computing times.Keywords
This publication has 16 references indexed in Scilit:
- Classical and modern heuristics for the vehicle routing problemInternational Transactions in Operational Research, 2000
- The Impact of Metaheuristics on Solving the Vehicle Routing Problem: Algorithms, Problem Sets, and Computational ResultsPublished by Springer Nature ,1998
- Exact Solution of the Vehicle Routing ProblemPublished by Springer Nature ,1998
- A heuristic algorithm for the asymmetric capacitated vehicle routing problemEuropean Journal of Operational Research, 1996
- A Parallel Tabu Search Algorithm Using Ejection Chains for the Vehicle Routing ProblemPublished by Springer Nature ,1996
- Probabilistic diversification and intensification in local search for vehicle routingJournal of Heuristics, 1995
- Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problemAnnals of Operations Research, 1993
- Parallel iterative search methods for vehicle routing problemsNetworks, 1993
- Tabu Search—Part IINFORMS Journal on Computing, 1989
- An Algorithm for the Vehicle-dispatching ProblemJournal of the Operational Research Society, 1969