Article ID: | iaor20001564 |
Country: | United Kingdom |
Volume: | 26 |
Issue: | 3 |
Start Page Number: | 255 |
End Page Number: | 270 |
Publication Date: | Mar 1999 |
Journal: | Computers and Operations Research |
Authors: | Barbarosoglu Gulay, Ozgur Demet |
Keywords: | heuristics |
The purpose of this study is to develop a new tabu search heuristic to solve the single-depot vehicle routing problem of a distribution company carrying goods from a depot to a set of dedicated dealers. The heuristic proposes a new neighbourhood generation procedure which considers the scattering pattern in the locations of the dealers. A set of neighbours are generated by first executing a procedure which ignores the clustering of the vertices and then executing a second procedure which takes into account the relative locations of the dealers; then the feasible non-tabu move among these with the best objective function value is implemented. During neighbourhood construction, a combination of traditional improvement techniques are used simultaneously in order to achieve the exchange of vertices. The intensification efforts, on the other hand, are focused upon the hill-climbing behaviour of the search, and the diversification step which is standard in all previous tabu search approaches is not included in this heuristic. Numerical results on well-known benchmark problems indicate that the performance of the algorithm developed in this study is compatible with the other best-known algorithms in the literature.