## 4 Methodology of APSO-LS
### Adaptive Perturbation PSO with Local Search (APSO-LS)  
To solve the optimization problem at each stage, we propose the APSO-LS algorithm, which enhances the standard PSO with adaptive perturbation and local search mechanisms. In this algorithm, each particle in the APSO-LS algorithm represents a candidate solution, consisting of the following:  
* Task allocation: A matrix \(W\in\mathbb{R}^{N_{U}\times N_{D_{k}}}\), where \(W_{i,j}\) denotes the workload assigned to UAV \(U_{i}\) for task \(D_{j}\). * Routes: A set of routes \(\mathcal{R}=\{R_{1},R_{2},\ldots,R_{N_{U_{i}}}\}\), where each \(R_{i}\) is an ordered sequence of tasks and charging stations visited by UAV \(U_{i}\). The particle's position is encoded as a vector that combines the flattened task allocation matrix and the route sequences for all UAVs. The population of PSO is initialized using a heuristic approach to ensure feasibility and diversity according to the following rules. * Task allocation: Workloads are initially assigned to UAVs based on their proximity to tasks, ensuring that each task's workload is fully allocated. * Routes: Initial routes are constructed by assigning tasks to UAVs in a greedy manner, considering energy constraints and the need for recharging. This heuristic initialization provides a good starting point for the optimization process, reducing the number of iterations required for convergence. In APSO-LS, we introduce an adaptive perturbation strategy to dynamically adjust the exploration-exploitation trade-off. The perturbation rate \(\rho\) is adjusted based on the improvement in the global best solution. If the global best has not improved for a certain number of iterations, \(\rho\) is increased to encourage exploration. Conversely, if improvements are frequent, \(\rho\) is decreased to focus on exploitation. The velocity update equation incorporates the perturbation rate given in (10):  
\[v_{k+1}=wv_{k}+c_{1}r_{1}(p_{\text{best}}-x_{k})+c_{2}r_{2}(g_{\text{best}}-x_{ k})+\rho\cdot\xi, \tag{10}\]  
where \(w\) is the inertia weight, \(c_{1}\) and \(c_{2}\) are cognitive and social coefficients, \(r_{1}\) and \(r_{2}\) are random numbers, \(p_{\text{best}}\) is the personal best position, \(g_{\text{best}}\) is the global best position, and \(\xi\) is a random perturbation vector. The corresponding position update mechanism is provided in (11):  
\[x_{k+1}=x_{k}+v_{k+1}. \tag{11}\]  
To further refine the solutions and escape local optima, a simulated annealing (SA)-based local search is applied to the best particle in each iteration. * Neighborhood search: Small perturbations are applied to the task allocation and route sequences to generate neighboring solutions. * Acceptance criterion: A neighboring solution is accepted if it improves the objective function, with a probability \(\exp(-\Delta J/T)\), where \(\Delta J\) is the change in the objective function and \(T\) is the current temperature. * Cooling schedule: The temperature \(T\) is gradually decreased according to a cooling rate \(\alpha\), allowing the algorithm to converge to a high-quality solution. This local search mechanism enhances the exploitation capability of the algorithm, ensuring that the final solution is both optimal and feasible. In addition, energy management is a critical component of the proposed methodology. During the evaluation of each particle, the energy consumption of each UAV is tracked along its route:  
* Energy check: Before visiting each task, the UAV's current energy level is checked. If the energy is insufficient to reach the task and return to the nearest station, the UAV is routed to the nearest available charging station. * Charging time: The time spent charging is calculated based on the required energy to reach \(E_{\text{max}}\), using the station's charging rate \(r_{\text{charge}}\). * Station capacity: The algorithm ensures that the number of UAVs charging at any station does not exceed \(C_{\text{max}}\) by scheduling charging slots accordingly.