Road emergencies including traffic accidents, vehicle failures, infrastructure damage, and natural disasters frequently occur simultaneously across multiple locations, creating complex challenges for emergency response operations. Modern drone technology offers transformative potential in these scenarios, with Unmanned Aerial Vehicles (UAVs) demonstrating significant effectiveness in reconnaissance and data collection missions. This research establishes a mathematical framework for multi-drone task allocation during emergency responses and develops an advanced hybrid optimization algorithm to enhance mission efficiency.
We formulate the multi-drone reconnaissance problem as a Multiple Traveling Salesman Problem (MTSP) with dual objectives: minimizing both the number of UAVs deployed and the total flight distance. The mathematical representation incorporates critical operational constraints:
$$ \begin{aligned}
&\min F_1 = \sum_{k=1}^{m} \sum_{j=1}^{n} x_{0jk} \\
&\min F_2 = \sum_{k=1}^{m} \sum_{i=0}^{n} \sum_{j=0}^{n} d_{ij} x_{ijk} \\
&\text{Subject to:} \\
&\sum_{k=1}^{m} \sum_{i=0}^{n} x_{ijk} = 1, \quad \forall j \\
&\sum_{j=0}^{n} x_{0jk} = \sum_{i=0}^{n} x_{i0k} = 1, \quad \forall k \\
&\sum_{i=1}^{n} \sum_{j=0}^{n} x_{ijk} t_{ij} + \sum_{i=1}^{n} s_i y_{ik} \leq T_k^{\max}, \quad \forall k \\
&x_{ijk}, y_{ik} \in \{0,1\}
\end{aligned} $$
Where \(F_1\) minimizes drone count, \(F_2\) minimizes total flight distance, \(x_{ijk}\) indicates drone \(k\)’s movement between locations, and \(y_{ik}\) denotes task assignment. Critical constraints ensure: 1) Each target is visited once, 2) Drones depart/return to base, 3) Mission duration respects drone endurance limits \(T_k^{\max}\).
The algorithmic foundation combines Particle Swarm Optimization (PSO) and Grey Wolf Optimization (GWO). Standard PSO updates particle positions using:
$$ \begin{aligned}
&v_i^d = \omega v_i^{d-1} + c_1 r_1 (pbest_i^d – x_i^d) + c_2 r_2 (gbest_i^d – x_i^d) \\
&x_i^{d+1} = x_i^d + v_i^d
\end{aligned} $$
Standard GWO simulates wolf hunting hierarchies through position updates:
$$ \begin{aligned}
&D_\alpha = |C_1 \cdot X_\alpha – X_i|, \quad D_\beta = |C_2 \cdot X_\beta – X_i|, \quad D_\delta = |C_3 \cdot X_\delta – X_i| \\
&X_1 = X_\alpha – A_1 \cdot D_\alpha, \quad X_2 = X_\beta – A_2 \cdot D_\beta, \quad X_3 = X_\delta – A_3 \cdot D_\delta \\
&X_i^{t+1} = \frac{X_1 + X_2 + X_3}{3}
\end{aligned} $$
Our enhanced CPS-GWO algorithm introduces four key innovations:
| Improvement | Mechanism | Mathematical Formulation |
|---|---|---|
| Kent Chaotic Initialization | Enhances population diversity | $$x_{i+1} = \begin{cases} \frac{5}{2}x_i & 0 < x_i \leq 0.4 \\ \frac{5}{3}(1 – x_i) & 0.4 < x_i < 1 \end{cases}$$ |
| Nonlinear Parameter Adjustment | Optimizes convergence behavior | $$a = 2 – 2\left(\frac{t}{t_{\max}}\right)^2$$ |
| Adaptive Position Update | Balances exploration-exploitation | $$\omega_i^d = \begin{cases} \omega_{\min} + (\omega_{\max} – \omega_{\min}) \frac{f(x_i^d) – f_{\min}^d}{f_{\text{avg}}^d – f_{\min}^d} & f(x_i^d) \leq f_{\text{avg}}^d \\ \omega_{\max} & \text{otherwise} \end{cases}$$ |
| Hierarchical Weighting | Prioritizes elite solutions | $$\lambda_1 = \frac{\|D_\delta\|}{\|D_\alpha\| + \|D_\beta\| + \|D_\delta\|}, \quad \lambda_2 = \frac{\|D_\beta\|}{\|D_\alpha\| + \|D_\beta\| + \|D_\delta\|}, \quad \lambda_3 = \frac{\|D_\alpha\|}{\|D_\alpha\| + \|D_\beta\| + \|D_\delta\|}$$ |
Experimental validation utilized TSPLIB datasets with parameters: maximum mission duration \(T_k^{\max} = 120\) minutes, drone speed \(v_k = 20\) m/s, and ISR time \(s_i = 0.1\) hours. Population size was set to 50 with 100 maximum iterations.
| Instance | Events | UAVs | Distance (km) | Time (s) |
|---|---|---|---|---|
| burma14 | 14 | 2 | 20.614 | 1.00 |
| ulysses16 | 16 | 3 | 51.441 | 1.09 |
| ulysses22 | 22 | 3 | 51.632 | 1.43 |
| bayg29 | 29 | 5 | 302.483 | 2.30 |
Comparative analysis demonstrates CPS-GWO’s superiority in solution quality and computational efficiency:
| Algorithm | burma14 (km) | ulysses16 (km) | ulysses22 (km) | bayg29 (km) |
|---|---|---|---|---|
| Standard GWO | 22.405 | 64.764 | 66.315 | 554.418 |
| IGWO | 22.249 | 62.016 | 55.901 | 400.101 |
| GA-IGWO | 20.749 | 54.444 | 53.401 | 377.236 |
| CPS-GWO | 20.614 | 51.441 | 51.632 | 302.483 |
Further benchmarking against established metaheuristics confirms CPS-GWO’s competitive performance in optimizing drone technology deployments. The Unmanned Aerial Vehicle coordination framework reduces total flight distances by 18.4-45.5% compared to conventional approaches while maintaining computational efficiency. Future research will incorporate heterogeneous UAV capabilities and dynamic emergency scenarios to enhance practical applicability. These advancements in drone technology optimization demonstrate significant potential for improving life-saving emergency response operations.