Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem

Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem

0.00 Avg rating0 Votes
Article ID: iaor19932221
Country: Switzerland
Volume: 41
Issue: 1/4
Start Page Number: 421
End Page Number: 451
Publication Date: May 1993
Journal: Annals of Operations Research
Authors:
Keywords: optimization: simulated annealing, heuristics
Abstract:

The vehicle routing problem (VRP) under capacity and distance restrictions involves the design of a set of minimum cost delivery routes, originating and terminating at a central depot, which services a set of customers. Each customer must be supplied exactly once by one vehicle route. The total demand of any vehicle must not exceed the vehicle capacity. The total length of any route must not exceed a pre-specified bound. Approximate methods based on descent, hybrid simulated annealing/tabu search, and tabu search algorithms are developed and different search strategies are investigated. A special data structure for the tabu search algorithm is implemented which has reduced notably the computational time by more than 50%. An estimate for the tabu list size is statistically derived. Computational results are reported on a sample of seventeen bench-mark test problems from the literature and nine randomly generated problems. The new methods improve significantly both the number of vehicles used and the total distances travelled on all results reported in the literature.

Reviews

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