A Genetic Algorithm for the Vehicle Routing Problem

The purpose of this research was to develop a version of a genetic algorithm (GA ) which would provide near optimal solutions for Vehicle Routing Problems (VRP) with both time and weight constraints. The genetic algorithm used for the experimentation was adapted from a GA which had been developed by James Bean at the University of Michigan to solve machine scheduling problems. The VRP data sets used in this research were obtained from the literature. Various aspects of the GA were experimented with in order to develop a version which would perform consistently well for all the data sets. The results of the final version of the genetic algorithm were then compared to the results presented in the original papers.

The results from this research indicated that the genetic algorithm seems to perform relatively well for smaller problems with 50 or fewer customers. However, the results seem to become progressively worse as the problem becomes larger.