In the rapidly evolving landscape of e-commerce and low-altitude economies, traditional last-mile delivery models are increasingly inadequate. The integration of electric vehicles (EVs) and unmanned aerial vehicles (UAVs), particularly China UAVs, has emerged as a promising solution to enhance flexibility and reduce carbon emissions. This paper investigates the electric vehicle routing problem with drones considering charging of both EVs and China UAVs (EVRPD-CEVD), a complex combinatorial optimization problem that accounts for time windows, heterogeneous UAV fleets, and dynamic charging requirements. We formulate a mixed-integer linear programming model to minimize total operational costs, including fixed vehicle costs, travel energy costs, and UAV usage costs. To address the NP-hard nature of the problem, we propose a hybrid Whale Optimization Algorithm integrated with Adaptive Large Neighborhood Search (WOA-ALNS). Extensive experiments on adapted benchmark instances demonstrate that our algorithm achieves 19%–30% cost reduction compared to standard WOA and Artificial Bee Colony (ABC) algorithms. Sensitivity analyses on charge thresholds provide actionable guidelines for logistics enterprises. Our work contributes to the growing body of research on sustainable urban logistics and highlights the role of China UAV technology in transforming last-mile delivery systems.
1. Introduction
The booming e-commerce sector in China has generated an unprecedented demand for efficient and sustainable last-mile delivery services. Conventional van-based delivery fleets suffer from traffic congestion, high fuel costs, and limited flexibility. In response, logistics companies are exploring innovative solutions combining electric vehicles (EVs) and unmanned aerial vehicles (UAVs). The EV-drone cooperative paradigm leverages the long-haul capacity of EVs and the agile, traffic-free nature of drones. This synergy is particularly vital in dense urban environments where China UAVs are increasingly deployed for autonomous parcel drops.
However, practical implementation faces challenges: both EVs and China UAVs are constrained by battery capacity, requiring careful charging scheduling; UAVs come in multiple models with different payload and energy profiles; and customer time windows impose strict temporal constraints. Existing research often neglects the joint charging requirements of both vehicle types or assumes infinite battery lifetime. This paper addresses these gaps by modeling a realistic scenario where EVs can recharge at charging stations and UAVs can be recharged while docked on the mother EV. We aim to minimize the total cost while ensuring all constraints are met. The main contributions are:
- We propose an extended EVRPD-CEVD model incorporating heterogeneous UAV types and dynamic charging of both EVs and China UAVs.
- We design a novel WOA-ALNS hybrid metaheuristic that combines the global search ability of Whale Optimization Algorithm with the local refinement capability of Adaptive Large Neighborhood Search.
- We conduct sensitivity analyses on charge upper limits and minimum charge thresholds, offering practical recommendations for logistics operators.
- We validate our model and algorithm on multiple benchmark instances, demonstrating significant improvements over existing methods.
The remainder of this paper is organized as follows: Section 2 reviews related literature; Section 3 presents the mathematical model; Section 4 describes the proposed algorithm; Section 5 reports experimental results and analysis; Section 6 concludes.
2. Problem Formulation
2.1 Problem Description
Consider a distribution center located at origin, servicing a set of customers scattered in an urban area. The fleet consists of homogeneous EVs, each equipped with a fixed number of China UAVs of two types (Type A and Type B). Each EV starts from the depot fully charged, carries parcels and China UAVs, and must return to the depot. During the journey, an EV may visit customers directly (EV delivery) or release a China UAV to perform one or multiple deliveries before being recovered at a later node. Both the EV and the China UAVs have limited battery capacities; the EV can recharge at intermediate charging stations, and the China UAVs can recharge only while docked on the EV (which itself may be stationary or moving). Each customer has a strict time window and a known parcel weight. The objective is to minimize the sum of fixed vehicle usage costs, EV energy consumption costs, UAV fixed costs, and UAV flight energy costs.
2.2 Assumptions
- All EVs are identical; each EV carries exactly one Type A and one Type B China UAV.
- Each customer is visited exactly once, either by EV or by a China UAV.
- Time windows are hard; service times are uniform for all customers.
- UAVs can take off and land only at the depot, a customer served by the EV, or a charging station.
- UAVs can serve multiple customers in a single flight as long as payload and battery allow.
- EV travel speed and UAV flight speed are constant; UAV speed is higher than EV speed.
- Travel distances are Euclidean; no traffic or stochastic events.
- Charging time is proportional to the energy charged.
2.3 Notation
| Symbol | Description |
|---|---|
| V | Set of EVs, indexed by v |
| U | Set of China UAVs, indexed by u |
| A | Set of UAV types (a,b) |
| P | Set of all nodes (depot 0, n+1, customers, charging stations) |
| X | Set of customer nodes |
| W | Set of charging station nodes |
| mi | Parcel weight at customer i |
| [tiearly, tilate] | Time window of customer i |
| τ | Service time per customer |
| sij | Distance between nodes i and j |
| Ncar | Number of EVs used |
| vcar | EV speed |
| Ccarfixed | Fixed cost per EV |
| Mviarrive | Remaining payload of EV v when arriving at node i |
| tviarrive, tvileave | Arrival and departure times of EV v at node i |
| Ecarmax | Maximum battery capacity of EV (60 kWh) |
| ecards | Energy consumption per km for EV (0.15 kWh/km) |
| Ccar | Cost per kWh for EV (0.5 yuan/kWh) |
| Eviarrive, Evileave | Remaining battery of EV v at node i |
| rc | Charging rate (50 kWh/h) |
| Mamax | Maximum payload of type a China UAV (A:3.5 kg, B:5.5 kg) |
| Na | Number of type a China UAV per EV (1 each) |
| maz | Self-weight of type a China UAV (A:1.5 kg, B:3.0 kg) |
| va | Flight speed of type a China UAV (A:50 km/h, B:60 km/h) |
| Eamax | Max battery of type a China UAV (A:0.4 kWh, B:0.6 kWh) |
| CUAV,afixed | Fixed cost per type a China UAV (A:20 yuan, B:40 yuan) |
| Cade | Energy cost per kWh for UAV (0.5 yuan/kWh) |
| eads | Energy consumption per km for type a UAV (A:0.020 kWh/km, B:0.025 kWh/km) |
| Pain | Charging input power on EV (A:20 Wh/min, B:25 Wh/min) |
| xvij | =1 if EV v travels from i to j |
| yauij | =1 if type a China UAV u flies from i to j |
| αvi | =1 if customer i served by EV v |
| βaui | =1 if customer i served by China UAV u |
| κvau | =1 if EV v carries China UAV u |
| γaui | =1 if China UAV u takes off at i |
| θaui | =1 if China UAV u lands at i |
| εvk | =1 if EV v visits charging station k |
| μvau | =1 if EV v charges China UAV u |
2.4 Objective Function
Minimize total cost Z = Z1 + Z2 + Z3 + Z4, where:
$$
Z_1 = N_{car} \cdot C_{car}^{fixed}
$$
$$
Z_2 = \sum_{v\in V}\sum_{i\in P^b}\sum_{j\in P^e} C_{car} \cdot e_{car}^{ds} \cdot s_{ij} \cdot x_{vij}
$$
$$
Z_3 = \sum_{a\in A} C_{UAV,a}^{fixed} \cdot N_{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}^{de} \cdot e_{a}^{ds} \cdot s_{ij} \cdot y_{auij}
$$
Z1: fixed cost of EVs; Z2: EV travel energy cost; Z3: fixed cost of China UAVs; Z4: UAV flight energy cost.
2.5 Constraints
Customer coverage: Each customer must be served exactly once by either EV or China UAV:
$$
\sum_{v\in V} \alpha_{vi} + \sum_{a\in A}\sum_{u\in U} \beta_{aui} = 1,\quad \forall i \in X
$$
EV route continuity: Each EV starts and ends at depot:
$$
\sum_{j\in X} x_{v0j} = 1,\quad \sum_{i\in X} x_{vi(n+1)} = 1,\quad \forall v
$$
UAV flight constraints: Each takeoff must be followed by a landing, and the number of takeoffs/landings at a node cannot exceed the number of China UAVs carried by the EV at that node:
$$
\sum_{i\in P^b} \gamma_{aui} \leq 1,\quad \sum_{j\in P^e} \theta_{auj} \leq 1,\quad \forall a,u
$$
$$
\gamma_{aui} + \theta_{aui} \leq \kappa_{vau} \cdot N_a,\quad \forall a,u,v,i
$$
Energy constraints: The EV must maintain battery above 20% of capacity before departure after charging; charging cannot exceed 80% of capacity. For China UAVs, the battery must be at least 30% before takeoff and cannot exceed 90% during flight; a safety floor of 10% is enforced:
$$
E_{vi}^{leave} \geq 0.2 E_{car}^{max},\quad \text{if EV leaves node } i
$$
$$
E_{vk}^{arrive} + e_{vk} \leq 0.8 E_{car}^{max},\quad \forall v,k
$$
$$
E_{aui}^{leave} \geq 0.3 E_{a}^{max},\quad \forall a,u,i \text{ with } \gamma_{aui}=1
$$
$$
E_{auij} \leq 0.9 E_{a}^{max},\quad \forall a,u,i,j
$$
$$
E_{aui}^{leave} – E_{auij} \geq 0.1 E_{a}^{max},\quad \text{if China UAV flies from i to j}
$$
Time window constraints ensure that all arrivals and departures occur within [tiearly, tilate]. The complete model includes additional flow and synchronization constraints omitted here for brevity.
3. WOA-ALNS Algorithm
We develop a hybrid metaheuristic that combines the global exploration of the Whale Optimization Algorithm (WOA) with the adaptive neighborhood search of ALNS. The algorithm proceeds in four phases:
- Initial EV routes construction using a time-feasible sequential insertion heuristic, then improved by WOA’s spiral and encircling mechanisms.
- Charging station insertion using a greedy strategy: for each EV route, identify the first customer where remaining battery is insufficient to reach the next node; insert the cheapest charging station that enables completion.
- UAV task assignment: Convert some EV-served customers to China UAV-served customers if the UAV payload and energy constraints are satisfied and the total cost decreases. Priority is given to lightweight parcels and customers causing high EV energy consumption.
- ALNS optimization: Six destroy-repair operator pairs are designed (Table 2) and selected adaptively using a roulette wheel based on recent performance scores. The algorithm iterates until a maximum number of iterations or a Metropolis-based termination criterion is met.
| Pair | Destroy | Repair | Purpose |
|---|---|---|---|
| 1 | Remove redundant charging stations (EV never below threshold) | Insert charging station before critical customer | Guarantee energy feasibility |
| 2 | Remove charging station where EV arrives with surplus | Insert charging station after next customer | Reduce charging cost |
| 3 | Remove one of two consecutive charging stations | Insert removed station into another EV route without charging | Balance energy distribution |
| 4 | Remove a charging station in a UAV idle segment | Replace EV-served customers with China UAV service | Improve EV–UAV synergy |
| 5 | Remove a customer from a high-payload China UAV route | Insert that customer into a low-payload route | Balance UAV load |
| 6 | Remove a customer from a high-energy-consumption China UAV flight | Insert into a low-energy flight | Optimize energy distribution |
The algorithm maintains an adaptive weight for each operator pair. Scores are updated using four levels: †1 = new global best, †2 = better than current, †3 = accepted by Metropolis, †4 = otherwise. Weight update:
$$
\rho_q^{i+1} = \lambda \rho_q^i + (1-\lambda)\psi_q
$$
where λ is a smoothing factor (0.8 in our experiments).
4. Experimental Results and Discussion
4.1 Instance Generation and Parameter Settings
We adapt three large CVRPTW benchmark instances (1c2b3a4c, 1c2c3c4b, 1c2c3a4a) to urban distances (scaling coordinates). Each instance contains 100 customers, one depot, and one charging station. Table 3 shows a partial example.
| ID | X (km) | Y (km) | Weight (kg) | Early | Late |
|---|---|---|---|---|---|
| 0 (depot) | 121.38 | 279.54 | – | 08:00 | 20:00 |
| 1 | 120.86 | 278.45 | 1.5 | 10:00 | 12:00 |
| 2 | 124.95 | 283.08 | 1.5 | 14:00 | 16:00 |
| 3 | 118.61 | 276.29 | 3.0 | 16:00 | 18:00 |
| 4 | 119.68 | 276.56 | 1.0 | 16:00 | 18:00 |
| 5 | 121.95 | 277.78 | 5.5 | 12:00 | 14:00 |
| … | … | … | … | … | … |
Electric vehicle parameters: Ccarfixed=100 yuan, Ecarmax=60 kWh, ecards=0.15 kWh/km, charging rate 50 kWh/h. China UAV parameters as described in Table 1. The algorithm parameters were tuned via Taguchi experiments: population size=50, max iterations=100, ALNS destroy rate (10%,20%,30%), and local optimization cycles=20.
4.2 Comparison of Algorithms
We compare our WOA-ALNS with standard WOA and Artificial Bee Colony (ABC) algorithms. Each algorithm runs 20 independent trials per instance. Table 4 summarizes the results.
| Instance | Metric | Algorithm | Total Cost (yuan) | #UAV Customers | Time (s) | Cost Gap (%) |
|---|---|---|---|---|---|---|
| 1c2b3a4c | Best | ABC | 855.16 | 35 | 694 | 3.71 |
| WOA | 1059.82 | 47 | 390 | 28.54 | ||
| WOA-ALNS | 824.54 | 47 | 698 | – | ||
| Avg | ABC | 867.99 | 34 | 672 | 4.08 | |
| WOA | 1068.17 | 45 | 363 | 28.08 | ||
| WOA-ALNS | 833.96 | 46 | 692 | – | ||
| 1c2c3c4b | Best | ABC | 888.13 | 30 | 681 | 2.82 |
| WOA | 1029.43 | 45 | 431 | 19.17 | ||
| WOA-ALNS | 863.81 | 47 | 718 | – | ||
| Avg | ABC | 897.22 | 29 | 659 | 3.00 | |
| WOA | 1042.13 | 43 | 400 | 19.63 | ||
| WOA-ALNS | 871.09 | 45 | 711 | – | ||
| 1c2c3a4a | Best | ABC | 847.58 | 32 | 648 | 3.33 |
| WOA | 1057.70 | 47 | 384 | 28.94 | ||
| WOA-ALNS | 820.29 | 41 | 692 | – | ||
| Avg | ABC | 863.54 | 31 | 628 | 5.72 | |
| WOA | 1065.81 | 44 | 356 | 30.48 | ||
| WOA-ALNS | 816.81 | 40 | 686 | – |
Our WOA-ALNS consistently achieves the lowest total cost across all instances, with improvements ranging from 19% to 30% over WOA and 3% to 6% over ABC. Although computational time is slightly higher than WOA (due to ALNS iterations), the solution quality improvement is substantial. Moreover, WOA-ALNS deploys more China UAVs (higher #UAV customers) on average, indicating better utilization of drone capabilities.
4.3 Sensitivity Analysis of Charge Parameters
We investigate the impact of varying the charge upper limit (maximum allowed battery after charging) and the minimum charge threshold (battery level below which charging is triggered) for both EVs and China UAVs. Experiments are performed on instance 1c2b3a4c with 20 runs for each parameter combination. Tables 5 and 6 summarize the results.
| Upper Limit | Total Cost (yuan) | #Charging Events |
|---|---|---|
| 70% | 823.15 | 21 |
| 75% | 798.47 | 15 |
| 80% | 783.20 | 11 |
| 85% | 748.91 | 9 |
| 90% | 775.62 | 14 |
| Min Threshold | Total Cost (yuan) | #Charging Events |
|---|---|---|
| 30% | 818.97 | 19 |
| 25% | 795.33 | 13 |
| 20% | 783.20 | 11 |
| 15% | 764.28 | 7 |
| 10% | 779.85 | 9 |
For EVs, the optimal operating point is at 85% upper limit and 15% min threshold, achieving the lowest cost (748.91 yuan) with only 9 charging events. Exceeding 85% increases charging time and risks time-window violations; lowering the threshold below 15% leads to emergency charging penalties. For China UAVs (Tables omitted for brevity), the best configuration is 85% upper limit and 25% min threshold, balancing flight endurance and recharging frequency.
These findings guide logistics managers: maintain EV charging upper limit at 85% during peak hours (to avoid delays) and 15% min threshold during off-peak hours (to exploit cheaper electricity); for China UAVs, set upper limit to 85% and min threshold to 25% to maximize service capacity while ensuring reliability.
5. Conclusion
This paper presents a comprehensive study on the collaborative delivery problem of electric vehicles and China UAVs with joint charging considerations. We formulate a realistic mathematical model incorporating heterogeneous UAV types, time windows, and charging dynamics. A novel hybrid WOA-ALNS algorithm is developed to solve the NP-hard problem efficiently. Extensive computational experiments on adapted benchmark instances demonstrate that our algorithm outperforms traditional WOA and ABC by 19%–30% and 3%–6%, respectively, while achieving faster convergence. Sensitivity analyses reveal optimal charge thresholds for both EVs and China UAVs, offering actionable insights for logistics operators. The integration of China UAV technology into urban delivery fleets, combined with intelligent charging scheduling, promises significant cost savings and environmental benefits. Future work may explore dynamic takeoff/landing point selection while the EV is moving, further enhancing the flexibility and efficiency of this emerging cooperative paradigm.