Urban emergencies demand rapid material distribution to minimize life and property losses. Traditional ground transportation faces limitations in congested disaster zones, where delivery drones offer superior mobility and rapid response. This work addresses the critical challenge of multi-UAV cooperative path planning for urban emergency logistics, introducing a novel Evolutionary Multi-Task Optimization (MCPP-EMTO) framework. Unlike single-task approaches, our method leverages simplified auxiliary tasks to accelerate optimization of complex primary objectives while handling real-world constraints unique to delivery UAV operations.
The path planning problem for delivery drones incorporates dual objectives: minimizing total energy consumption and mission completion time. For K drones servicing N demand points, these objectives are formalized as:
$$ \text{minimize} \quad f = (f_1, f_2)^T $$
$$ f_1 = \chi \sum_{k=1}^K \sum_{(u,v) \in \mathcal{P}_k} d_{uv} \zeta_{uv} $$
$$ f_2 = \max_{1 \leq k \leq K} \sum_{(u,v) \in \mathcal{P}_k} d_{uv} \zeta_{uv} $$
where \(d_{uv}\) is Euclidean distance between nodes \(u\) and \(v\), \(\zeta_{uv}\) is a binary path indicator, \(\chi\) is a fuel coefficient, and \(\mathcal{P}_k\) denotes the path of drone \(k\). Energy and time objectives exhibit inherent conflict: deploying more delivery UAVs reduces \(f_2\) but increases \(f_1\).
Operational constraints for delivery drones include:
| Constraint Type | Formulation | Description |
|---|---|---|
| Altitude | \(z_{\text{min}} < z_i \leq z_{\text{max}}\) | Safe flight height range |
| Range | \(\sum_{i=1}^{s+1} l_i \leq l_{\text{max}}\) | Maximum travel distance |
| Payload | \(\sum_{n=1}^N X_n \leq l_{\text{max}}\) | Maximum cargo capacity |
| Turning Angle | \(\theta_i \leq \theta_{\text{max}}\) | Maneuverability limit |
| Pitch Angle | \(\frac{|z_i – z_{i-1}|}{\sqrt{(x_i – x_{i-1})^2 + (y_i – y_{i-1})^2}} \leq \tan \gamma_{\text{max}}\) | Climb/descent safety |
| Collision Avoidance | \(\| \mathbf{T}_e(t) – \mathbf{T}_w(t) \| \geq d_{\text{safe}}\) | Drone-to-drone separation |
| Obstacle Clearance | \(\| \mathbf{T}_e – \mathbf{T}_{ob} \| \geq d_{\text{min}}\) | Building avoidance |
| Demand Satisfaction | \(\sum_{k=1}^K X_k^n = C_n \, \forall n\) | Complete material delivery |
Our MCPP-EMTO algorithm solves this constrained multi-objective problem through symbiotic optimization of two tasks:
$$ \begin{align*}
\text{Primary Task (T1)} &: \text{Original constrained problem} \\
\text{Auxiliary Task (T2)} &: \min(f_1,f_2) \ \text{s.t.} \ \text{only collision/altitude constraints}
\end{align*} $$
Knowledge transfer occurs through adaptive migration. When migrating from T1 to T2, we evaluate T1 populations on the simplified T2 problem. The migration success rate \(\eta\) determines transfer direction:
$$ \eta_{\mathcal{P}\rightarrow\text{T2} = \frac{\text{num}_{\mathcal{P}\rightarrow\text{feasible}}{\text{NP}}, \quad \eta_{\mathcal{OP}}\rightarrow\text{T2} = \frac{\text{num}_{\mathcal{OP}}\rightarrow\text{feasible}}{\text{NP}/2} $$
where \(\mathcal{P}\) and \(\mathcal{OP}\) denote parent and offspring populations. Higher-\(\eta\) populations transfer solutions. Reverse migration (T2→T1) uses the same mechanism evaluated on T1 constraints.
The complete MCPP-EMTO procedure integrates evolutionary multi-task optimization with local refinement:
1: Initialize populations P1 (T1) and P2 (T2) 2: while G ≤ G_max do 3: if G < β·G_max then 4: Generate offspring via genetic operators 5: else 6: Generate offspring via binary tournament 7: Calculate migration success rates η 8: Transfer high-η solutions between tasks 9: end if 10: Merge populations and evaluate 11: Apply constraint-dominated selection 12: Refine solutions via Adaptive Large Neighborhood Search (ALNS) 13: Update populations 14: end while
ALNS enhances local exploitation through destroy-repair operations tailored for delivery drone paths:
| Destroy Operator | Repair Operator | Application |
|---|---|---|
| Random node removal | Greedy reinsertion | Path segment optimization |
| Worst-energy removal | Energy-aware insertion | Battery-critical missions |
| Cluster removal | Demand-based insertion | High-density areas |
Experimental validation used three urban scenarios with varying complexity:
| Scenario | Area (m²) | Demand Points | Delivery Drones | Obstacles |
|---|---|---|---|---|
| S1 | 2000×2000 | 9 | 6 (3 bases) | 15 |
| S2 | 2000×2000 | 15 | 6 (3 bases) | 22 |
| S3 | 2000×2000 | 25 | 6 (3 bases) | 31 |
Performance was evaluated using hypervolume (HV) metrics across 20 runs:
| Algorithm | S1 (HV ↑) | S2 (HV ↑) | S3 (HV ↑) |
|---|---|---|---|
| NSGA-II | 2.5225×10⁴ ±484 | 4.2850×10⁴ ±1501 | 4.5318×10⁴ ±3633 |
| MOPSO | 2.4895×10⁴ ±791 | 3.9697×10⁴ ±3289 | 3.2663×10⁴ ±5836 |
| MOSTA/D | 2.5641×10⁴ ±393 | 4.3453×10⁴ ±1267 | 4.8353×10⁴ ±2976 |
| MOEA-2DE | 2.5388×10⁴ ±446 | 4.3739×10⁴ ±1074 | 4.9159×10⁴ ±2846 |
| MCPP-EMTO | 2.6792×10⁴ ±293 | 4.6079×10⁴ ±724 | 5.2025×10⁴ ±435 |
Statistical analysis confirmed MCPP-EMTO’s superiority (Friedman test, α=0.05). Component ablation studies demonstrated critical contributions:
$$ \text{HV}_{\text{MCPP-EMTO}} > \text{HV}_{\text{NoTransfer}} \ (p<0.01), \quad \text{HV}_{\text{MCPP-EMTO}} > \text{HV}_{\text{NoALNS}} \ (p<0.01) $$
Sensitivity analysis revealed delivery UAV performance boundaries:
$$ \begin{align*}
f_2 &\propto v^{-1} \quad \text{(Completion time vs. velocity)} \\
\lim_{l_{\text{max}}\to\infty} \Delta f_1 &= 0 \quad \text{(Energy saturation at high payloads)}
\end{align*} $$
| Parameter | Varied Range | Optimal Range | Performance Impact |
|---|---|---|---|
| Velocity (m/s) | 5-25 | 15-20 | Nonlinear \(f_2\) reduction |
| Payload (kg) | 30-50 | 40-45 | Diminishing \(f_1\) returns >45kg |
| Battery (km) | 8-15 | 12-15 | Feasibility critical <10km |
Pareto-optimal solutions for delivery drones reveal fundamental tradeoffs:
$$ \frac{\partial f_2}{\partial f_1} = -k \frac{\sqrt{N}}{K} \quad (k \approx 0.73 \pm 0.08) $$
where steeper tradeoffs emerge in high-density urban environments (N>20). Practical deployment scenarios show:
- Single delivery UAV solutions minimize energy (2500m avg. path) but maximize time (520s)
- 6-drone configurations minimize time (280s) but increase total path length (≥4100m)
- Hybrid 3-drone solutions balance objectives (340s, 3200m)
This research establishes that evolutionary multi-task optimization significantly enhances delivery UAV path planning in complex urban emergencies. By transferring knowledge between constrained and simplified problems, MCPP-EMTO achieves superior convergence and diversity. Future work will integrate real-time weather adaptation and dynamic demand response for operational deployment of delivery drones in humanitarian logistics.