Solving the Capacitated Vehicle Routing Problem with a Genetic Algorithm

The Capacitated Vehicle Routing Problem involves finding vehicle routes, such that the goods that a customer demand are delivered in one visit and the travelling distance is minimised. Each customer has a known demand quantity and the vehicles in the fleet have limited capacity. The Capacitated Vehicle Routing Problem can further be extended by introducing travelling limits per vehicle, which is called the distance constrained version of the Capacitated Vehicle Routing Problem. The length of each route may not exceed this distance limit. The general idea of a Genetic Algorithm is closely related to the theory of evolution by means of natural selection. An initial population with candidate solutions is created and this population is improved, such that the fitness of the individuals in the population becomes better through different generations. New individuals are created with crossover and small mutations are applied to these children. There must be a balance between the genetic quality and the diversity of the individuals to support efficient search. A Genetic Algorithm is an iterative process, which terminates when a pre-specified number of generations is produced or when the solution quality is sufficient. The Genetic Algorithm for the Vehicle Routing Problem described in the article of Baker and Ayechew [1] is implemented and the performance of the algorithm is analysed. The algorithm is applied to four different vehicle routing instances. In this bachelor thesis, the results are analysed and compared to the results described by Baker and Ayechew [1]. We found out that our results are in some cases better than the results mentioned in the article of Baker and Ayechew [1]. However, the time after which the Genetic Algorithm terminates is longer in our case. The main cause for this observation is that we used a different programming language than Baker and Ayechew [1] to implement the Genetic Algorithm. The algorithm turns out to be adequate for problem instances for which the optimal tours are known. Different variations of the algorithm were tried. The best results were obtained when each of the population members has an equal chance of being selected as a parent. However, not all possible modifications are implemented and there is no evidence that this specific modification performs well for all vehicle routing instances. Besides that, combinations of modifications can be tested. Two or more adaptations together may improve the performance of the algorithm even further. It turns out that the Hybrid Genetic Algorithm is competitive with tabu search and simulating annealing in terms of solution quality. Tabu search and simulating annealing are methods that have been used to obtain the best known results for benchmark Vehicle Routing Problems. The computing time of the Genetic Algorithm is much longer than those of the other two methods mentioned above. The use of Matlab as the implementing environment can be an explanation for this observation and our advice is to use another programming language, such as C.