Rapid urbanization and e-commerce growth demand innovative last-mile delivery solutions. We propose a Hybrid Strategy-improved Brain Storm Optimization (HSBSO) algorithm for delivery drone task allocation with time windows and simultaneous pickup-delivery constraints. This approach addresses key challenges in urban logistics where traditional vehicles face congestion and emissions limitations.
Delivery UAV operations are modeled as a directed graph $G = (V, A)$ where nodes represent distribution centers and customers. Critical constraints include:
$$ \begin{align*}
\text{Minimize} & \quad f = \sum_{k \in K} \sum_{(i,j) \in A} c_{ij}x_{ijk} \\
\text{Subject to} & \quad \sum_{k \in K} \sum_{j \in \Delta^+(i)} x_{ijk} = 1 \quad \forall i \in N \\
& \quad a_i \leq w_{ik} \leq b_i \quad \forall i \in N, k \in K \\
& \quad L_k^0 \leq Q \quad \forall k \in K \\
& \quad \sum_{(i,j) \in A} c_{ij}x_{ijk} \leq C \quad \forall k \in K
\end{align*} $$
Table 1 defines model parameters essential for delivery drone operations:
| Parameter | Description |
|---|---|
| $c_{ij}$ | Distance between nodes |
| $v$ | Delivery UAV speed |
| $[a_i, b_i]$ | Customer time window |
| $d_i, p_i$ | Delivery/pickup quantities |
| $Q$ | Drone capacity |
| $C$ | Maximum flight distance |
Basic Brain Storm Optimization (BSO) suffers from slow convergence and premature stagnation. Our HSBSO integrates four innovations:
1. Sobol Sequence Initialization enhances population diversity:
$$X_i = lb + S_n \times (ub – lb)$$
where $S_n$ is a low-discrepancy Sobol sequence. Integer mapping ensures feasible delivery UAV routes.
2. Chaotic Quantum Behavior accelerates global search. Intermediate particles are corrected using modified Sine chaotic mapping:
$$ \begin{cases}
d(gen+1) = \sin(\pi \cdot d(gen)) \\
e(gen+1) = \sin(\pi \cdot e(gen)) \\
w(gen) = \text{mod}(d(gen) + e(gen), 1)
\end{cases} $$
$$X_i’ = X_i^* + [w(gen) – 0.5] \cdot (X_j^* – X_k^*)$$
Quantum behavior then generates new particles:
$$X_{\text{new}} = \begin{cases}
X_i’ + |X_i’ – X_j| \cdot \ln(1/\mu) & \lambda < 0.5 \\
X_i’ – |X_i’ – X_j| \cdot \ln(1/\mu) & \lambda \geq 0.5
\end{cases}$$
3. Quadratic Local Search Probability dynamically balances exploration-exploitation:
$$R(gen) = \frac{4(R_{\max} – R_{\min})}{\text{MAXGEN}^2} \cdot \left(gen – \frac{\text{MAXGEN}}{2}\right)^2 + R_{\min}$$
4. Observation-Triggered Mutation escapes local optima when fitness stagnates. Chromosome segments between random positions $y_1$ and $y_2$ are mutated using position-specific operations.
Experimental results demonstrate HSBSO’s superiority for delivery UAV allocation:
| Algorithm | Avg. Distance (m) | Runtime (s) | Std. Dev. |
|---|---|---|---|
| HSBSO | 38,761 | 86 | 450 |
| Basic BSO | 39,329 | 90 | 496 |
| Genetic Algorithm | 47,068 | 171 | 2,202 |
| Simulated Annealing | 40,986 | 147 | 1,240 |
Key findings:
- HSBSO reduces distance by 1.5% vs BSO and 21.4% vs GA
- Runtime scales linearly: +2.2s per additional customer
- 90% of HSBSO solutions outperform BSO’s average fitness
Optimal delivery drone routes for 40 customers (5 drones, total distance 38,581m):
| Drone | Route | Distance (m) |
|---|---|---|
| 1 | 0→2→24→31→39→0 | 4,833.65 |
| 2 | 0→30→34→5→11→19→27→25→33→0 | 5,976.55 |
| 3 | 0→36→29→4→37→3→22→35→10→0 | 7,463.50 |
| 4 | 0→40→15→14→18→7→17→13→21→23→0 | 13,377.85 |
| 5 | 0→16→6→20→9→8→28→1→38→26→12→32→0 | 6,971.15 |
Component analysis reveals:
- Dynamic local search probability reduces runtime by 15% vs fixed probabilities
- Observation-triggered mutation decreases solution variance by 40% vs Lévy flight strategies
- Chaotic quantum behavior accelerates convergence by 22%
Scalability tests confirm consistent performance for delivery UAV fleets servicing 40-80 customers. Runtime growth remains linear while maintaining solution quality superior to alternatives.
Our HSBSO algorithm significantly advances delivery drone task allocation. Future work will extend this framework to multi-objective optimization incorporating energy consumption and service equity metrics for urban air mobility systems.