Article ID: | iaor20003491 |
Country: | Netherlands |
Volume: | 119 |
Issue: | 1 |
Start Page Number: | 147 |
End Page Number: | 157 |
Publication Date: | Nov 1999 |
Journal: | European Journal of Operational Research |
Authors: | Baker Barrie M., Sheasby Janice |
Keywords: | heuristics |
Although tabu search has generally given the best results for benchmark vehicle routing problems, it has been observed that such heuristics require substantial computing times and several parameter settings. Thus, when good quality solutions are required quickly, there is still a need for relatively fast and effective heuristics. The generalised assignment heuristic for the basic vehicle routing problem can be extended by adjusting seed positions to reduce the optimal objective value for the generalised assignment problem. Combined with a simple Lagrangean heuristic, this gives a relatively straightforward method for obtaining solutions within a few percent of the best known values for benchmark problems.