As demand for urban delivery services intensifies, delivery drones (unmanned aerial vehicles, UAVs) present a transformative solution for last-mile logistics. However, efficiently navigating complex urban airspace while minimizing risks remains challenging. We propose a three-dimensional route planning methodology integrating environmental risk modeling with an enhanced artificial fish swarm algorithm (AFSA) to optimize safety and efficiency for delivery UAV operations.
Environment Modeling for Delivery Drone Operations
We partition the operational airspace into a grid structure. Each grid cell is assigned a risk value $\theta_i$ combining collision probability and ground impact severity:
$$ \theta_i = \frac{N_i}{26} + k_r Z_i U_i $$
where $N_i$ is the count of obstacle-occupied neighboring cells (0–26 range), $k_r$ is the crash risk coefficient (0–0.01), $Z_i$ denotes altitude (0–120 m), and $U_i$ represents ground population density (0–10 scale). This formulation ensures delivery UAV routes avoid high-risk zones.
Delivery UAV Route Optimization Model
Our model minimizes total operational cost for a delivery UAV traveling from start $S(x_0,y_0,z_0)$ to goal $G(x_n,y_n,z_n)$:
$$ \min W = k_1 P_L + k_2 P_R + k_3 P_A $$
where weights satisfy $k_1 + k_2 + k_3 = 1$. Cost components are:
- Path Length Cost:
$$ P_L = \sum_{i=1}^{n} u \sqrt{(x_i – x_{i-1})^2 + (y_i – y_{i-1})^2 + (z_i – z_{i-1})^2} $$
$u$ scales distance cost. - Grid Risk Cost:
$$ P_R = \sum_{i=1}^{n} \theta_{i_w} $$
$\theta_{i_w}$ is the normalized risk value. - Altitude Adjustment Cost:
$$ P_A = \sum_{i=1}^{n} \Delta Z_{(i-1,i)_w} $$
$\Delta Z_{(i-1,i)_w}$ is the normalized height change between nodes.
Constraints for delivery UAV kinematics include:
- Maximum Turning Angle:
$$ 0 \leq \alpha_i = \arccos\left(\frac{(x_i – x_{i-1})(x_{i+1} – x_i) + (y_i – y_{i-1})(y_{i+1} – y_i)}{\sqrt{(x_i – x_{i-1})^2 + (y_i – y_{i-1})^2} \cdot \sqrt{(x_{i+1} – x_i)^2 + (y_{i+1} – y_i)^2}}\right) \leq \alpha_{\max} $$ - Flight Altitude Limits:
$$ z_{\min} \leq z_i \leq z_{\max} $$ - Maximum Pitch Angle:
$$ -\beta_{\max} \leq \beta_i = \tan^{-1}\left(\frac{z_{i+1} – z_i}{\sqrt{(x_{i+1} – x_i)^2 + (y_{i+1} – y_i)^2}}\right) \leq \beta_{\max} $$
| Parameter | Value | Parameter | Value |
|---|---|---|---|
| Maximum Range | 27 km | $k_1$ | 0.4 |
| Maximum Speed | 16.7 m/s | $k_2$ | 0.4 |
| $\alpha_{\max}$ | 60° | $k_3$ | 0.2 |
| $\beta_{\max}$ | 60° | $k_r$ | 0.005 |
| $z_{\min}$ | 20 m | $u$ | 0.05 |
| $z_{\max}$ | 120 m | – | – |
Enhanced Artificial Fish Swarm Algorithm
Standard AFSA simulates fish behaviors—foraging, swarming, chasing, and random movement—for optimization. For a delivery UAV swarm with $N$ individuals in 3D space:
- State: Position $X_i = (x_i, y_i, z_i)$
- Food Concentration: Objective function $Y_i = f(X_i)$
- Perception Distance: $a$
- Step Size: $s$
We enhance AFSA with two mechanisms:
- Grid Taboo Table: Each delivery drone records visited grid cells:
$$ \text{tab}_i = \{ L_i, O_1, O_2, \dots, O_m \} $$
Prevents revisit cycles and local optima entrapment. - Fish Jumping Behavior: Triggers when improvement stagnates over $m$ iterations:
$$ | \argmin f_{t-m}(X) – \argmin f_t(X) | < \eta $$
Jump position: $X_h = X_i + s_h \cdot \text{rand}(0,1)$. Update if beneficial:
$$ X_i(t+1) = X_i(t) + \frac{X_h(t) – X_i(t)}{\| X_h(t) – X_i(t) \|} \cdot s_h \cdot \text{rand}(0,1) $$
Enables escape from local minima.
Simulation Results and Analysis
Tests used a $500 \times 500 \times 150$ m urban airspace. Our enhanced AFSA was benchmarked against standard AFSA, ant colony optimization (ACO), and particle swarm optimization (PSO).
| Algorithm | Convergence Time (s) | Reduction vs. Standard AFSA |
|---|---|---|
| Enhanced AFSA | 7.52 | 9.9% |
| Standard AFSA | 8.35 | – |
| ACO | 8.63 | 12.9% slower |
| PSO | 9.37 | 19.7% slower |
| Algorithm | Path Cost | Risk Cost | Altitude Cost | Total Cost |
|---|---|---|---|---|
| Enhanced AFSA | 37.33 | 23.42 | 34.16 | 31.13 |
| Standard AFSA | 37.78 | 24.52 | 34.16 | 31.75 |
| ACO | 37.86 | 25.57 | 33.13 | 32.00 |
| PSO | 39.16 | 34.13 | 37.14 | 36.74 |
The enhanced AFSA achieved the lowest total cost and fastest convergence, demonstrating superior efficiency for delivery drone path planning.
Parameter Sensitivity
Key parameters were tested in complex and simple terrains:
- Perception Distance ($a$): Larger $a$ accelerated convergence in both environments by expanding search scope.
- Step Size ($s$): In complex terrain, larger $s$ improved convergence; in simple terrain, smaller $s$ enhanced precision by preventing overshoot.
Conclusion
Our enhanced AFSA with grid taboo tables and jumping behavior optimizes delivery UAV routes by minimizing flight distance, risk exposure, and energy-intensive altitude changes. It converges 9.9% faster than standard AFSA while generating safer, lower-cost paths. Parameter tuning should adapt to environmental complexity: larger perception distances universally improve efficiency, while step sizes require terrain-dependent calibration. This approach offers a robust framework for urban delivery drone operations, balancing efficiency with stringent safety requirements for widespread adoption.