A Memetic Algorithm for Solving UAV Routing Problems with Profits

Hua, S, Xu, J, Zhang, H, Zhang, Q ORCID: 0000-0002-0651-469X, Qin, L and Hua, L (2025) A Memetic Algorithm for Solving UAV Routing Problems with Profits. Instrumentation, 12 (4). pp. 48-56. ISSN 2095-7521

Preview

Text 005_202500300_Siliang+Hua_L.pdf - Published Version Available under License Creative Commons Attribution. Download (2MB) | Preview

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 attains 95% accuracy relative to maximum total score within 30 iterations, surpassing 99% accuracy 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.

Item Type:	Article
Subjects:	Q Science > QA Mathematics > QA76 Computer software T Technology > TA Engineering (General). Civil engineering (General)
Divisions:	Engineering
Publisher:	China Instrument and Control Society
Date of acceptance:	15 December 2025
Date of first compliant Open Access:	9 April 2026
Date Deposited:	09 Apr 2026 13:44
Last Modified:	09 Apr 2026 13:44
DOI or ID number:	10.15878/j.instr.202500300
URI:	https://researchonline.ljmu.ac.uk/id/eprint/28356

View Item