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

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.