A tabu search algorithm for the vehicle routing problem

A tabu search algorithm for the vehicle routing problem

0.00 Avg rating0 Votes
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: ,
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.