A genetic algorithm for the vehicle routing problem

This study considers the application of a genetic algorithm (GA) to the basic vehicle routing problem (VRP), in which customers of known demand are supplied from a single depot. Vehicles are subject to a weight limit and, in some cases, to a limit on the distance travelled. Only one vehicle is allowed to supply each customer. The best known results for benchmark VRPs have been obtained using tabu search or simulated annealing. GAs have seen widespread application to various combinatorial optimisation problems, including certain types of vehicle routing problem, especially where time windows are included. However, they do not appear to have made a great impact so far on the VRP as described here. In this paper, computational results are given for the pure GA which is put forward. Further results are given using a hybrid of this GA with neighbourhood search methods, showing that this approach is competitive with tabu search and simulated annealing in terms of solution time and quality. The basic vehicle routing problem (VRP) consists of a number of customers, each requiring a specified weight of goods to be delivered. Vehicles despatched from a single depot must deliver the goods required, then return to the depot. Each vehicle can carry a limited weight and may also be restricted in the total distance it can travel. Only one vehicle is allowed to visit each customer. The problem is to find a set of delivery routes satisfying these requirements and giving minimal total cost. In practice, this is often taken to be equivalent to minimising the total distance travelled, or to minimising the number of vehicles used and then minimising total distance for this number of vehicles. Most published research for the VRP has focused on the development of heuristics. Although the development of modern heuristics has led to considerable progress, the quest for improved performance continues. Genetic algorithms (GAs) have been used to tackle many combinatorial problems, including certain types of vehicle routing problem. However, it appears that GAs have not yet made a great impact on the VRP as described here. This paper describes a GA that we have developed for the VRP, showing that this approach can be competitive with other modern heuristic techniques in terms of solution time and quality.