In the rapidly evolving landscape of e‑commerce and low‑altitude economy, the integration of electric vehicles (EVs) and unmanned aerial vehicles (drones) has emerged as a promising solution for last‑mile logistics. In China, the deployment of China drone technology in urban delivery has gained significant attention due to its ability to circumvent ground traffic congestion and reduce carbon emissions. However, the practical implementation of an EV‑drone collaborative system faces critical challenges, particularly regarding battery charging constraints for both vehicles and drones. Our research focuses on a novel problem: the Electric Vehicle Routing Problem with Drones considering Charging of Electric Vehicles and Drones (EVRPD‑CEVD). We propose a mathematical model and an advanced algorithm to minimize total operational costs while satisfying hard time windows, multiple drone types, and dynamic energy replenishment. Our work contributes to the growing body of knowledge on China drone logistics by providing a practical optimization framework for real‑world delivery scenarios.
Problem Statement and Mathematical Model
We consider a delivery scenario where a fleet of homogeneous electric vehicles starts from a central depot. Each EV carries two drones of different types (type A and type B) with distinct payload capacities, flight speeds, and energy consumption rates. The EVs can either serve customers directly or launch drones to perform deliveries and recover them at subsequent nodes. Both EVs and drones require charging when their battery levels drop below thresholds. We incorporate realistic charging stations that allow partial recharging. The objective is to minimize the sum of fixed vehicle costs, travel costs, fixed drone costs, and drone flight costs. The model is subject to customer time windows, capacity limits, and energy feasibility.
Sets and indices:
- $$V$$: set of electric vehicles, indexed by $$v$$.
- $$U$$: set of drones, indexed by $$u$$.
- $$A$$: set of drone types, indexed by $$a$$.
- $$P$$: set of all nodes (depot 0 and $$n+1$$, customers, charging stations).
- $$X$$: set of customer nodes.
- $$W$$: set of charging stations.
Parameters:
| Symbol | Description |
|---|---|
| $$m_i$$ | Package weight at customer $$i$$ |
| $$t_i^{\text{early}}, t_i^{\text{late}}$$ | Time window of customer $$i$$ |
| $$\tau$$ | Service time per customer |
| $$s_{ij}$$ | Distance between nodes $$i$$ and $$j$$ |
| $$v^{\text{car}}, v_a^{\text{UAV}}$$ | Speed of EV and drone type $$a$$ |
| $$C_{\text{car}}^{\text{fixed}}$$ | Fixed cost per EV |
| $$C_{\text{car}}^d$$ | Energy cost per km for EV |
| $$E_{\text{car}}^{\text{max}}$$ | Maximum battery capacity of EV |
| $$E_a^{\text{max}}$$ | Maximum battery capacity of drone type $$a$$ |
| $$M_a^{\text{max}}$$ | Payload capacity of drone type $$a$$ |
| $$C_a^{\text{UAV,fixed}}$$ | Fixed cost per drone type $$a$$ |
| $$C_a^{\text{de}}$$ | Energy cost per kWh for drone type $$a$$ |
| $$P_a^{\text{in}}$$ | Charging power of drone type $$a$$ |
| $$\omega_1,\omega_2$$ | Power consumption coefficients for drone payload and self‑weight |
Decision variables:
| Variable | Type | Meaning |
|---|---|---|
| $$x_{ij}^v$$ | binary | 1 if EV $$v$$ travels from $$i$$ to $$j$$ |
| $$y_{ij}^{au}$$ | binary | 1 if drone $$u$$ of type $$a$$ flies from $$i$$ to $$j$$ |
| $$\alpha_i^v$$ | binary | 1 if EV $$v$$ serves customer $$i$$ |
| $$\beta_i^{au}$$ | binary | 1 if drone $$u$$ of type $$a$$ serves customer $$i$$ |
| $$\kappa_{vau}$$ | binary | 1 if EV $$v$$ carries drone $$u$$ of type $$a$$ |
| $$\gamma_i^{au}$$ | binary | 1 if drone $$u$$ of type $$a$$ launches at node $$i$$ |
| $$\theta_i^{au}$$ | binary | 1 if drone $$u$$ of type $$a$$ lands at node $$i$$ |
| $$\varepsilon_k^v$$ | binary | 1 if EV $$v$$ visits charging station $$k$$ |
| $$\mu_{vau}$$ | binary | 1 if EV $$v$$ charges drone $$u$$ of type $$a$$ |
Objective function:
$$
\min Z = Z_1 + Z_2 + Z_3 + Z_4
$$
$$
Z_1 = C_{\text{car}}^{\text{fixed}} \cdot N_{\text{car}}
$$
$$
Z_2 = \sum_{v\in V}\sum_{i\in P^b}\sum_{j\in P^e} C_{\text{car}}^d \cdot E_{ij}^v \cdot x_{ij}^v
$$
$$
Z_3 = \sum_{a\in A} C_a^{\text{UAV,fixed}} \cdot N_{\text{car}} \cdot N_a
$$
$$
Z_4 = \sum_{a\in A}\sum_{u\in U}\sum_{i\in P^b}\sum_{j\in P^e} C_a^{\text{de}} \cdot E_{ij}^{au} \cdot y_{ij}^{au}
$$
Key constraints (selected):
- Each customer is served exactly once: $$\sum_v \alpha_i^v + \sum_a\sum_u \beta_i^{au} = 1, \forall i\in X$$.
- EV route continuity: $$\sum_j x_{0j}^v = \sum_i x_{i,n+1}^v = 1, \forall v$$.
- Drone launch/land balance: $$\sum_j y_{ij}^{au} – \gamma_i^{au} = 0$$, $$\sum_i y_{ij}^{au} – \theta_j^{au} = 0$$.
- Drone payload capacity: $$\sum_{i\in X} m_i \beta_i^{au} \leq M_a^{\text{max}}$$.
- Time window enforcement: $$t_i^{\text{early}} \leq t_{\text{arrive},i} \leq t_i^{\text{late}}$$.
- EV battery level: $$E_{\text{arrive},j}^v \leq E_{\text{leave},i}^v – E_{ij}^v$$, $$E_{\text{leave},0}^v = E_{\text{car}}^{\text{max}}$$.
- EV minimum departure battery: $$E_{\text{leave},i}^v \geq 0.2 E_{\text{car}}^{\text{max}}$$ (can be adjusted).
- EV charging upper bound: $$E_{\text{after charge}}^v \leq 0.8 E_{\text{car}}^{\text{max}}$$.
- Drone battery constraint: $$E_{\text{arrive},j}^{au} = E_{\text{leave},i}^{au} – E_{ij}^{au}$$, $$E_{\text{leave},i}^{au} \geq 0.3 E_a^{\text{max}}$$ for launch.
- Drone safe landing: $$E_{\text{leave},i}^{au} – E_{ij}^{au} \geq 0.1 E_a^{\text{max}}$$.
These constraints ensure feasible and cost‑effective collaborative delivery while managing charging activities for both the EVs and the drones – a critical aspect for real‑world China drone operations where battery life is limited.
Solution Methodology: WOA‑ALNS Algorithm
We propose a hybrid algorithm combining Whale Optimization Algorithm (WOA) with Adaptive Large Neighborhood Search (ALNS). The algorithm operates in four phases: (1) initial EV route construction using WOA, (2) insertion of charging stations into EV routes, (3) conversion of selected EV‑served customers to drone‑served customers, and (4) iterative improvement via ALNS.
Encoding: A solution is represented by three integer vectors: EV route (starting and ending at depot, with charging station indices), type A drone routes, and type B drone routes. Each drone route is segmented by launch and land nodes.
Phase 1 – Initial EV Route Construction: We employ a time‑window‑driven greedy heuristic to generate an initial feasible EV route. Then, the WOA’s bubble‑net attacking and spiral updating mechanisms refine the route. The WOA position update formulas are:
$$
D = |C \cdot X_{\text{best}}(t) – X(t)|, \quad X(t+1) = X_{\text{best}}(t) – A \cdot D
$$
$$
X(t+1) = D’ \cdot e^{bL} \cdot \cos(2\pi L) + X_{\text{best}}(t), \quad p \ge 0.5
$$
where $$A=2a \cdot r_1 – a$$, $$C=2r_2$$, and $$a$$ decreases linearly from 2 to 0.
Phase 2 – Charging Station Insertion: We apply a greedy insertion strategy: identify the first customer where the EV’s remaining battery is insufficient to reach the next node, then insert the nearest charging station before that customer, ensuring post‑charge battery does not exceed 80% of capacity.
Phase 3 – Drone Path Addition: We iteratively convert EV customer points to drone‑served points, prioritizing customers with small package weights. A candidate drone mission is accepted if it satisfies payload, energy, and time‑window constraints and reduces total cost. This step leverages the high efficiency of China drone platforms in short‑range deliveries.
Phase 4 – ALNS Optimization: Six operator pairs (destruction + repair) are designed to explore the neighborhood. The operator selection uses a roulette wheel based on adaptive weights. The table below summarizes the operator pairs.
| Pair | Destruction Operator | Repair Operator | Objective |
|---|---|---|---|
| 1 | Remove redundant charging stations | Insert charging station before critical point | Energy feasibility |
| 2 | Remove charging stations with surplus energy | Insert charging station later to maximize residual | Reduce charging cost |
| 3 | Remove one of two adjacent charging stations | Insert removed station into another path | Balance energy distribution |
| 4 | Remove EV charging station in drone‑service gap | Replace EV points with drone points near that gap | Improve EV‑drone synergy |
| 5 | Remove a customer from a high‑load drone route | Insert into a low‑load drone route | Balance drone payload |
| 6 | Remove a customer from a high‑energy drone route | Insert into a low‑energy route | Optimize energy consumption |
After each destruction‑repair cycle, the new solution is accepted via a Metropolis criterion. Weight updates follow: $$\rho_q^{(i+1)} = \lambda \rho_q^{(i)} + (1-\lambda) \psi$$, where $$\psi$$ is the score based on solution improvement.
Experimental Results
We conduct numerical experiments on three modified CVRPTW instances with 100 customers, 4 EVs, and 4 drones (2 of each type). Parameters are set as shown in the table below.
| Parameter | Value | Parameter | Value |
|---|---|---|---|
| $$v^{\text{car}}$$ | 40 km/h | $$v_a^{\text{UAV}}$$ (A/B) | 50/60 km/h |
| $$E_{\text{car}}^{\text{max}}$$ | 60 kWh | $$E_a^{\text{max}}$$ (A/B) | 0.4 / 0.6 kWh |
| $$C_{\text{car}}^{\text{fixed}}$$ | 100 CNY/vehicle | $$C_a^{\text{UAV,fixed}}$$ (A/B) | 20 / 40 CNY |
| $$C_{\text{car}}^d$$ | 0.5 CNY/kWh | $$C_a^{\text{de}}$$ | 0.5 CNY/kWh |
| $$\tau$$ | 120 s | $$P_a^{\text{in}}$$ (A/B) | 20/25 Wh/min |
Algorithm Comparison: We compare WOA‑ALNS with standard WOA and Artificial Bee Colony (ABC). Each algorithm runs 20 times per instance. Results are summarized below.
| Instance | Metric | ABC | WOA | WOA‑ALNS |
|---|---|---|---|---|
| 1c2b3a4c | Best cost (CNY) | 855.16 | 1059.82 | 824.54 |
| Avg. cost (CNY) | 867.99 | 1068.17 | 833.96 | |
| 1c2c3c4b | Best cost (CNY) | 888.13 | 1029.43 | 863.81 |
| Avg. cost (CNY) | 897.22 | 1042.13 | 871.09 | |
| 1c2c3a4a | Best cost (CNY) | 847.58 | 1057.70 | 820.29 |
| Avg. cost (CNY) | 863.54 | 1065.81 | 816.81 |
Our WOA‑ALNS achieves improvements of 19%–30% over WOA and 2.8%–5.7% over ABC, demonstrating its effectiveness in solving the EVRPD‑CEVD problem. The algorithm also increases the number of drone‑served customers, leveraging the agility of China drone fleets.
Effect of Considering Drone Charging: We compare the full model (EVRPD‑CEVD) with a variant that ignores drone charging (EVRPD‑CEV). Results show an average cost increase of 5.43% when drone charging is considered, confirming the necessity of incorporating this realistic constraint for practical China drone operations.
| Instance | Model | Best cost (CNY) | Increase (%) |
|---|---|---|---|
| 1c2b3a4c | EVRPD‑CEV | 783.20 | 5.28% |
| EVRPD‑CEVD | 824.54 | ||
| 1c2c3c4b | EVRPD‑CEV | 814.81 | 6.01% |
| EVRPD‑CEVD | 863.81 | ||
| 1c2c3a4a | EVRPD‑CEV | 772.89 | 6.13% |
| EVRPD‑CEVD | 820.29 |
Sensitivity Analysis: We investigate the impact of EV and drone charging thresholds. For EVs, varying the upper charging limit (70%–90%) and minimum departure battery (30%–10%) reveals an optimal upper limit of 85% and a minimum of 15% (peak hours 25%) to minimize total cost. For drones, the best trade‑off occurs at an upper limit of 85% and a minimum of 25%. These findings provide actionable guidelines for logistics companies deploying China drone fleets in urban environments.
| Charging threshold | Value | Total cost (CNY) | # EV charges |
|---|---|---|---|
| EV upper limit (20% min) | 70% | 823.15 | 21 |
| 75% | 798.47 | 15 | |
| 80% | 783.20 | 11 | |
| 85% | 748.91 | 9 | |
| Drone upper limit (30% min) | 75% | 838.15 | 14 |
| 80% | 827.39 | 12 | |
| 85% | 816.73 | 9 | |
| 90% | 824.54 | 11 |
Conclusion
In this work, we addressed the vehicle routing problem with drones under charging constraints for both EVs and drones – a pressing issue for sustainable last‑mile logistics in China. We formulated a comprehensive mixed‑integer programming model and developed a novel WOA‑ALNS algorithm. Extensive experiments on benchmark instances demonstrated that our algorithm outperforms standard WOA and ABC by up to 30% in solution quality. Sensitivity analysis revealed optimal charging thresholds: 85% upper limit and 15% minimum for EVs, and 85% upper limit with 25% minimum for drones. Our findings offer practical insights for logistics operators integrating China drone technology into their delivery networks. Future work will explore dynamic launch‑point selection for drones while the EV is in motion, further improving the flexibility and efficiency of collaborative delivery systems.