A Two-Layer Improved Heuristic Algorithm for Balanced k-Cycle Fixed Route Planning

In multi-agent fixed route inspection scenarios like wind farm maintenance, efficient and fair path planning is of critical importance. Traditional dynamic programming methods cannot scale to large problem sizes due to exponential complexity. This paper proposes a two-layer clustering-based heuristic algorithm: the lower layer constructs a locally optimal solution using Multidimensional Scaling (MDS) and K-means, followed by local search and random perturbation; the upper layer runs multiple lower-layer processes in parallel to iteratively refine the global best solution until convergence. In a 10-node scenario, the algorithm exactly matches the globally optimal solution found by dynamic programming, achieving convergence in 13 iterations and 2.30 seconds. In a real-world 30-node wind farm UAV inspection task, our algorithm increases total path weight by 1.28% but reduces workload variance by 35.52% compared to the MDS + K-means baseline, confirming its effectiveness in balancing inspection workloads with minimal cost increase. The proposed method offers an efficient and scalable solution to multi-objective mTSP problems in fixed-route multi-agent inspection scenarios.