A Memetic Algorithm for Solving UAV Routing Problems with Profits

Abstract

This study addresses the Unmanned Aerial Vehicle routing problems with profits, which requires balancing mission profit, path efficiency, and battery health under complex constraints, particularly the nonlinear degradation of batteries. This paper proposes an enhanced memetic algorithm by integrating adaptive local search and a dynamic population management mechanism. The algorithm employs a hybrid initialization strategy to generate high-quality initial solutions. It incorporates an improved linear crossover operator to preserve beneficial path characteristics and introduces dynamically probability-controlled local search to optimize solution quality. To enhance global exploration capability, a population screening mechanism based on solution similarity and a population restart strategy simulating biological mass extinction are designed. Extensive experiments conducted on standard Tsiligirides’s and Chao’s datasets demonstrate the algorithm's robust performance across scenarios ranging from 21 to 66 nodes and time constraints spanning 5 to 130 minutes. The algorithm achieves 95% accuracy relative to theoretical optima within 30 iterations, with accuracy exceeding 99% after 100 iterations. Its comprehensive performance significantly surpasses that of traditional heuristic methods. The proposed method provides an efficient and robust solution for Unmanned Aerial Vehicle routing planning under intricate constraints.