The rapid evolution of unmanned aerial vehicle (UAV) technology has positioned delivery drones as transformative solutions for last-mile logistics. With growing e-commerce demands, optimizing urban airspace operations becomes critical. This study addresses the delivery UAV take-off sequencing problem through dynamic priority-based scheduling to minimize total delay costs while accommodating operational constraints.
Dynamic Priority-Based Scheduling Framework
Order prioritization integrates four critical parameters: cargo value ($V$), delivery distance ($D$), latest acceptable delivery time ($L_{max}$), and cargo weight ($W$). Qualitative parameters like cargo value are converted into triangular fuzzy numbers for quantification:
$$ \phi_{i1} = (\alpha_{li}, \alpha_{mi}, \alpha_{ui}) \quad i=1,2,\dots,n $$
Table 1 shows the linguistic-to-numerical mapping for cargo value assessment:
| Linguistic Description | Triangular Fuzzy Number | Scale |
|---|---|---|
| Very Low | (0.00, 0.00, 0.25) | 0.00 |
| Low | (0.00, 0.25, 0.50) | 0.25 |
| Medium | (0.25, 0.50, 0.75) | 0.50 |
| High | (0.50, 0.75, 1.00) | 0.75 |
| Very High | (0.75, 1.00, 1.00) | 1.00 |
Quantitative parameters are normalized using min-max scaling:
$$ \hat{\phi}_{ik} = \frac{\phi_{ik} – \min_{1\leq i\leq n}\{\phi_{ik}\}}{\max_{1\leq i\leq n}\{\phi_{ik}\} – \min_{1\leq i\leq n}\{\phi_{ik}\}}, \quad k=2,3,4 $$
Entropy weight method determines parameter weights $\omega_k$. Weighted similarity between orders $i$ and $j$ combines qualitative and quantitative measures:
$$ S_{ij} = \sum_{k=1}^{4} \omega_k \cdot r_{ijk} $$
where $r_{ijk}$ denotes feature-specific similarity. Fuzzy clustering using the Xie-Beni index ($XB=1.28$ optimal) groups orders into priority classes.
Three-Dimensional Priority Index
Each cluster $t$ is evaluated through cargo value ($X_t$), weight ($Y_t$), and delivery urgency ($Z_t$) indices:
$$X_t = \begin{cases}
1 & \text{if } \bar{X}_t \geq \bar{X} \\
2 & \text{otherwise}
\end{cases}$$
$$Y_t = \begin{cases}
1 & \text{if } \bar{Y}_t \geq \bar{Y} \\
2 & \text{otherwise}
\end{cases}$$
$$Z_t = \begin{cases}
1 & \text{if } \bar{Z}_t < \bar{Z} \\
2 & \text{otherwise}
\end{cases}$$
The priority score $P_t$ and delay penalty coefficient $c_t$ are calculated as:
$$ q_t = X_t + Y_t + Z_t $$
$$ P_t = \frac{(q_t-1)(q_t-2)(q_t-3)}{6} + \frac{(2q_t – X_t – 2)(X_t – 1)}{2} + Y_t $$
$$ c_t = 1 + \frac{1}{P_t} $$
Lower $P_t$ yields higher $c_t$, prioritizing time-sensitive deliveries for delivery UAV scheduling.
Take-off Scheduling Optimization Model
The model schedules $n$ delivery drones at a vertiport under safety and time constraints. Key definitions include:
- Earliest departure time: $E_i = ET_i – \frac{d_i}{v}$
- Latest departure time: $L_i = LT_i – \frac{d_i}{v}$
where $ET_i$/$LT_i$ denote earliest/latest delivery times, $d_i$ is distance, and $v$ is drone speed. The objective minimizes total delay cost:
$$ \min \ C = \sum_{i=1}^{n} c_i \left[ \max(T_i – L_i, 0) + \max(E_i – T_i, 0) \right] $$
where $T_i$ is actual departure time. Constraints include:
- Maximum delay tolerance: $T_i – L_i \leq lt_i \quad \forall i=1,\dots,n$
- Safety separation: $T_i – T_j \geq t_{ij} \quad \text{for consecutive UAVs } i,j$
Adaptive Genetic Algorithm Implementation
A dual-structure chromosome encodes drone sequence and departure times:
| Drone ID | $U_1$ | ⋯ | $U_i$ | ⋯ | $U_n$ |
|---|---|---|---|---|---|
| Departure Time | $T_1$ | ⋯ | $T_i$ | ⋯ | $T_n$ |
Fitness inversely relates to total delay cost:
$$ f(i) = \frac{1}{\sum_{i=1}^{n} c_i (T_i – L_i) + 1} $$
Adaptive crossover ($P_c$) and mutation ($P_m$) probabilities enhance convergence:
$$ P_c = \begin{cases}
0.6 & f < f_{avg} \\
0.3 \frac{f_{max} – f}{f_{max} – f_{avg}} & f \geq f_{avg}
\end{cases} $$
$$ P_m = \begin{cases}
0.1 & f < f_{avg} \\
0.3 \frac{f_{max} – f}{f_{max} – f_{avg}} & f \geq f_{avg}
\end{cases} $$
Algorithm workflow includes:
- Population initialization with dual-structure chromosomes
- Fitness evaluation
- Roulette wheel selection
- Position-based crossover
- Swap mutation within time windows
- Elitist replacement
Computational Experiments
Tests used Solomon datasets with H4 delivery UAV parameters: speed=4.2 km/h, safety interval=150m. Entropy weights were $\omega = (0.13, 0.34, 0.28, 0.25)$. Comparative results for 20 delivery drones show significant improvements:
| Metric | FCFS | Genetic Algorithm | Improvement |
|---|---|---|---|
| Total Delay Cost | 157.18 | 0.17 | 99.9% |
| Delayed Drones | 4 | 1 | 75.0% |
Scalability analysis demonstrates consistent outperformance versus First-Come-First-Served (FCFS) scheduling:
| Fleet Size | Cost Reduction | Delay Count Reduction |
|---|---|---|
| 10 | 98.7% | 85.7% |
| 20 | 99.9% | 75.0% |
| 30 | 72.3% | 53.8% |
| 40 | 68.1% | 45.5% |
| 50 | 63.9% | 41.2% |
The algorithm achieves superior delay cost distribution fairness. For 50 delivery UAVs:
- FCFS: Max delay cost = 142.3, Min = 8.2, Range = 134.1
- Genetic Algorithm: Max delay cost = 38.7, Min = 5.3, Range = 33.4
Conclusion
This research establishes an effective framework for delivery drone take-off scheduling through dynamic prioritization and adaptive genetic optimization. The three-dimensional priority index successfully translates operational constraints into cost-driven scheduling objectives. Key advantages include:
- Reduction in total delay costs up to 99.9% for small fleets
- Decrease in delayed delivery UAV counts by 85.7% for 10-drone operations
- Improved fairness in delay cost distribution across orders
- Effective handling of time-window and safety constraints
The methodology proves particularly effective for fleets ≤20 delivery drones, where cost reductions exceed 90% and delay count improvements surpass 70%. Future work will integrate vertiport surface movement dynamics and actual commercial delivery UAV operational data to enhance practical applicability.