Optimizing a GPU-accelerated genetic algorithm for the vehicle routing problem

The capacitated vehicle routing problem (CVRP) is an NP-hard optimization problem with many applications. Genetic algorithms (GAs) are often used to solve CVRPs but require many parameters and operators to tune. Incorrect settings can result in poor solutions. In this work, a design of experiments (DOE) approach is used to determine the best settings for GA parameters. The GA runs entirely on an NVIDIA RTX 3090 GPU. The GPU execution for a 200-node benchmark shows a speed by a factor of 1700 compared to that on an octa-core i7 CPU with 64 GB RAM. The tuned GA achieved a solution for a 400-node benchmark that is 72% better than that of an arbitrarily tuned GA after only 263 generations. New best-known values for several benchmarks are also obtained. A comparison between the performance of the algorithm with different hardware and tuning sets is also reported