A genetic algorithm for unmanned aerial vehicle routing

Genetic Algorithms (GAs) can efficiently produce high quality results for hard combinatorial real world problems such as the Vehicle Routing Problem (VRP). Genetic Vehicle Representation (GVR), a recent approach to solving instances of the VRP with a GA, produces competitive or superior results to the standard benchmark problems. This work extends GVR research by presenting a more precise mathematical model of GVR than in previous works and a thorough comparison of GVR to Path Based Representation approaches. A suite of metrics that measures GVR's efficiency and effectiveness provides an adequate characterization of the jagged search landscape. A new variation of a crossover operator is introduced. A previously unmentioned insight about the convergence rate of the search is also noted that is especially important to the application of a priori and dynamic routing for swarms of Unmanned Aerial Vehicles (UAVs). Results indicate that the search is robust, and it exponentially drives toward high quality solutions in relatively short time. Consequently, a GA with GVR encoding is capable of providing a state-of-the-art engine for a UAV routing system or related application.