The Vehicle Routing Problem is an NP-complete problem that has been studied extensively since it was introduced in 1958 by G. B. Dantzig and J. H. Ramser. This thesis creates three algorithms that endeavor to find an optimal solution for each problem tested. Two of the algorithms (Simulated Annealing and Tabu Search) have been used previously to solve this problem. These two solution methods are revisited to discover whether a new approach to creating routes will produce the best-known optimal values every time. New routes are created by forming route neighborhoods and then selecting cities from these neighborhoods for insertion. The third algorithm is an original algorithm which combines Simulated Annealing and Tabu Search. The algorithms presented do not produce the best-known optimal values, but are competitive with previously published algorithms.
White, Jeffrey Dale and Gillett, Billy E., "A Simulated Annealing/Tabu Search Algorithm for the Vehicle Routing Problem" (1993). Computer Science Technical Reports. 53.
© 1993 University of Missouri--Rolla, All rights reserved.
01 Dec 1993