Efficient Implementation of a Genetic Algorithm for the Capacitated Vehicle Routing Problem on a High-Performance FPGA

The Capacitated Vehicle Routing Problem (CVRP) is one of the most relevant optimization problems in operations research and logistics nowadays. While current state-of-the-art solutions to this problem implement evolutionary approaches such as Genetic Algorithms (GAs) on GPUs and multi-core CPUs, this work focuses on implementing a GA for CVRP on a high-performance FPGA to achieve an improved calculation efficiency: While maintaining a comparable solution quality and speed, the FPGA consumes only a fraction of the energy required by traditional computing platforms. This is achieved through leveraging algorithmic parallelism by a custom-fitted hardware architecture, combined with customized data representation for efficient processing.