Paper Info
Title
Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem
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.
Year
DOI
Venue
1993
10.1007/BF02023004
Annals OR
Keywords
Field
DocType
vehicle routing,simulated annealing,hybrid algorithm,vehicle routing problem,heuristics,data structure,local search,tabu search
Simulated annealing,Data structure,Mathematical optimization,Vehicle routing problem,Guided Local Search,Algorithm,Heuristics,Local search (optimization),Tabu search,Mathematics
Journal
Volume
Issue
ISSN
41
1-4
1572-9338
Citations 
PageRank 
References 
336
53.05
16
Authors
2
Search Limit
100336
Name
Order
Citations
PageRank
Ibrahim H. Osman181594.23
OsmanIbrahim Hassan233653.05