Solving the Vehicle Routing Problem with Genetic Algorithms

This thesis addresses the Capacitated Vehicle Routing Problem (CVRP) using the Genetic Algorithm (GA). Two encoding schemes of route solutions wereimplemented in this work; fixed-assignment and cyclic assignment. A grid searchwas conducted to optimize the GA parameters, specifically the mutation, selection, and crossover operator and offspring ratio choice, on a custom-generateddataset Gotland-n250-k5. The best performing configurations were evaluated onthe standard Augerat benchmark dataset to assess its generalization and performance against established instances. The Cyclic Assignment choice demonstratedfavorable performance in as little as 20% of the time necessary, using Roulette WheelSelection and OX1 crossover with Exchange Mutation. The results highlight thesignificance of appropriate encoding and operator choices that can influence the GAperformance for the CVRP.