Abstract:
Many organisations face the problem of delivering goods from a warehouse to a number of retail sites using a fleet of vehicles. The Vehicle Routing Problem (VRP) is a mathematical model that closely approximates the problem faced by many of these organisations. While the VRP can be solved exactly by various techniques, the time required is often excessive as the problem is NP-hard. In this thesis we develop heuristics that find high quality solutions in a reasonable amount of computer time. Foster and Ryan [FR76] introduced the petal method, which solves an overconstrained version of the VRP optimally. We improve on their solution technique, using a network formulation to produce optimal solutions of the overconstrained problem in much less time. For instance, the petal selection process for a 100 customer problem is more than 300 times faster when the network formulation is used. Also a fast Travelling Salesman Problem (TSP) heuristic that takes advantage of the sequential route building process of the petal method has been developed. These improvements allow examination, in a reasonable amount of time, of cyclic orders other than the radial cyclic order considered by Foster and Ryan. To effectively search through the space of cyclic orders we use three metaheuristics; GRASP, tabu search, and genetic algorithms (GAs). For tabu search we investigated a number of different schemes to control the tabu list length. Of these, the recently developed reactive tabu search method performed best, and required little parameter tuning. In order to obtain quality solutions when using the GA, specialised crossovers were developed, and a local search component was added. The tabu search and GA metaheuristics outperform GRASP. The difference between tabu search and the GA is less marked, tabu search producing better results on a set of 30 randomly generated test problems. However, another set of test problems suggest that tabu search may not be as globally robust as the GA. Overall the algorithms developed are superior to early (pre-1990) VRP heuristics, and are comparable in solution quality and execution time to current state of the art VRP heuristics.