DECK-GA: A Hybrid Clustering and Distance Efficient Genetic Algorithm for Scalable Multi-UAV Path Planning

The Multi-Travelling Salesman Problem (mTSP) provides a fundamental mathematical framework for modelling the complexities of effective and optimised multi-UAV path planning and for developing solution strategies. Different methodologies have been studied for multi-UAV path planning, such as clustering-based techniques for waypoint allocation. Despite classical Kmeans clustering being commonly employed for its efficiency, centroid instability produces an inefficient distribution of UAVs. Traditional Genetic Algorithms (GA) often encounter difficulties with premature convergence and ineffective crossover operations, leading to suboptimal paths. This paper presents DECK-GA, a hybrid framework that combines Dynamic Centroid Kmeans (DCKmeans) clustering with Distance Efficient Genetic Algorithm (DEGA) to address centroid instability, suboptimal UAV path distribution, and premature convergence. DECK-GA applies DCKmeans to improve centroid initialisation and integration, maintaining stable cluster formations; and DEGA to enhance path planning through fitness-proportionate selection and adaptive crossover mutation, increasing diversity and accelerating convergence. DECK-GA is tested in a simulated environment using 30 and 100 randomly distributed 3D waypoints, minimising travel distances by 56.06% and 69.03%, respectively. Computation times are reduced to 28.17 and 43.21 seconds, correspondingly surpassing classical Kmeans, GA, and other six additional clustering methods combined with traditional GAs and DEGA. The enhancements show the efficiency of DECK-GA in multi-UAV waypoint clustering and path planning for the mTSP, especially in applications that require efficient global path optimisation using GNSS waypoints.