A genetic algorithm for the vehicle routing problem

A genetic algorithm for the vehicle routing problem

0.00 Avg rating0 Votes
Article ID: iaor20033159
Country: United Kingdom
Volume: 30
Issue: 5
Start Page Number: 787
End Page Number: 800
Publication Date: Apr 2003
Journal: Computers and Operations Research
Authors: ,
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.