I investigate the combined delivery system of trucks and UAV drones for last‑mile logistics. This problem, known as the Vehicle Routing Problem with Drones (VRPD), is an NP‑Hard extension of the classical VRP. I design a two‑stage heuristic based on Adaptive Large Neighborhood Search (ALNS) to minimize the total delivery cost. The first stage generates a feasible initial solution using a savings‑greedy approach, and the second stage improves it with novel removal and insertion operators. A Simulated Annealing (SA) acceptance criterion helps escape local optima. Computational experiments on random instances demonstrate that my algorithm converges quickly and yields high‑quality solutions.
1. Introduction
Traditional truck‑only delivery faces low efficiency and high cost, especially in congested urban areas. UAV drones offer a promising alternative for last‑mile logistics due to their ability to bypass traffic. Recently, the concept of a truck carrying multiple UAV drones has emerged: the truck acts as a mobile base, launching and retrieving drones to serve customers in parallel. This hybrid system can significantly reduce total travel time and operational expense. However, jointly optimizing truck routes and drone flight paths is computationally challenging. The VRPD is a generalization of the VRP and is NP‑Hard. Many researchers have proposed exact and heuristic methods. I extend the literature by developing a two‑stage ALNS algorithm tailored to this problem, focusing on practical constraints such as drone payload, battery energy, and synchronization between truck and UAV drones.
2. Problem Definition and Mathematical Model
I consider a complete graph G=(V,E) where V = {0,1,…,n} is the set of vertices, with vertex 0 being the depot and the remaining vertices representing customers. Each customer i (i>0) has a demand q_i (kg) and must be served either by the truck or by a UAV drone.
2.1 Parameters
| Parameter | Description |
|---|---|
| n | Number of customers |
| q_i | Demand of customer i (kg) |
| C | Truck capacity (kg) |
| Q | Drone payload capacity (kg) |
| E | Drone battery energy (kWh) |
| v_t | Truck speed (m/s) |
| v_d | Drone speed (m/s) |
| c_t | Cost per hour for truck ($/h) |
| c_d | Cost per hour for drone ($/h) |
| d_{ij} | Euclidean distance between i and j (km) |
2.2 Decision Variables
I define binary variables: $$x_{ij}^t = 1$$ if the truck travels from i to j; $$y_{ij}^d = 1$$ if a drone flies from i to j; and $$z_{ik} = 1$$ if customer i is served by drone k. Continuous variables track drone load and energy consumption.
2.3 Objective Function
The total cost is the sum of truck travel cost and drone flight cost:
$$ \min \sum_{(i,j)\in E} c_t \cdot \frac{d_{ij}}{v_t} \cdot x_{ij}^t + \sum_{(i,j)\in E} c_d \cdot \frac{d_{ij}}{v_d} \cdot y_{ij}^d $$
I also include a penalty for unmet time windows in some extended variants, but the base model assumes no time windows.
2.4 Constraints
- Truck capacity: The total demand on a truck route does not exceed C.
- Drone payload: A drone can serve at most one customer per launch, and its payload Q must not be exceeded.
- Energy limit: The total flight distance of a drone between launch and retrieval must not exceed its battery range (derived from E).
- Sync: The drone must take off from and land on the truck at predetermined rendezvous points.
- Routing: Each customer is visited exactly once by either the truck or a drone.
The detailed MILP formulation follows the classical VRPD model. Because of space, I omit the full constraint set, but the key difficulty lies in the coupling between truck and UAV drones.
3. Proposed Two‑Stage ALNS Algorithm
The VRPD is NP‑Hard; exact solvers cannot handle instances with more than 20 customers within reasonable time. I therefore design a two‑stage heuristic:
- Stage 1: Construct an initial feasible solution using a savings‑greedy algorithm.
- Stage 2: Improve the solution using ALNS with customized removal and insertion operators, guided by adaptive weight selection and SA acceptance.
3.1 Initial Solution Generation
I begin by building a truck route that visits all customers, then greedily offload some customers to UAV drones. The procedure is:
- For each truck route, collect all nodes into set N. Identify nodes that can be served by a drone (based on demand ≤ Q) and place them in set M.
- Set the first node of the route as the drone launch point.
- For each node m in M, compute ratio δ = demand(m) / distance(launch, m). Select the node with highest δ, add it to the drone path, and remove it from N and M. Update drone load and remaining energy.
- Repeat step 3 until the drone load or energy is exhausted.
- Select the node in N that is closest to the last drone‑served node as the landing point. Remove it from M and update the drone’s energy.
- Among remaining nodes in N, pick the one closest to the current truck end node, add it to the truck route, and repeat until the landing point is added. This completes one truck‑drone pair.
- If N and M are not empty, start a new truck route from the depot and go back to step 2.
- All trucks return to the depot when N and M are empty.
This greedy approach always yields a feasible solution quickly.
3.2 Removal Operators
During the ALNS improvement phase, I remove a certain number of customers from the current solution. I use five removal operators:
| Operator | Description |
|---|---|
| Random removal | Randomly select ρ customers and remove them. |
| Max‑saving removal | For each customer, compute the distance saved if removed. Sort descending and remove the top ρ. |
| Similarity removal | Remove a cluster of customers that are similar in terms of location, demand, or service type (truck or drone). Similarity distance is a weighted sum. |
| Whole‑truck removal | Randomly select one truck route and remove all customers on that route. |
| Whole‑drone removal | Randomly select several drone paths and remove all customers served by those drones. |
The number of removed customers ρ is random between 0.1n and 0.4n.
3.3 Insertion Operators
After removal, I re‑insert the removed customers using four operators:
| Operator | Description |
|---|---|
| Greedy distance‑based | For each unplaced customer, evaluate all feasible insertion positions (truck or drone) and choose the one with smallest added distance. |
| Randomized distance‑based | Same as above, but add a random perturbation –0.1 to 0.1 times the maximum distance increment to avoid greediness. |
| Greedy time‑based | Insert customers to minimize the increase in total travel time. |
| Randomized time‑based | Add a random perturbation to the time increment. |
These operators allow UAV drones to be used only when a feasible drone launch/retrieval pair exists.
3.4 Adaptive Weight Adjustment
Each removal or insertion operator has a weight w_r. During an iteration, an operator is selected using a roulette‑wheel mechanism based on its current weight. After every N_w iterations (e.g., 20), weights are updated:
$$ w_r = (1-\theta) w_r + \theta \frac{\pi_r}{\#\text{uses}} $$
where θ = 0.8, and π_r is the cumulative score of operator r. Scores are increased by σ₁ = 6 if the new solution is the global best, by σ₂ = 4 if it improves the current solution, and by σ₃ = 2 if it is accepted even though worse.
3.5 Acceptance Criterion
To escape local optima, I adopt the Metropolis criterion from Simulated Annealing. If the new solution has cost f_new and the current solution cost f_cur, the acceptance probability is:
$$ P = \begin{cases} 1 & \text{if } f_{\text{new}} < f_{\text{cur}} \\ e^{-(f_{\text{new}} – f_{\text{cur}}) / T} & \text{otherwise} \end{cases} $$
Temperature T starts at T₀ = 300 and is reduced each iteration by δ = 0.98 until Tmin = 1. This allows moderate deterioration early but converges to a greedy search later.
4. Experimental Results
I implement the algorithm in MATLAB R2020b on a machine with an Intel i5‑9300H CPU (2.40 GHz) and 16 GB RAM. I generate random instances within a 10 km × 10 km square; the depot is at the center.
4.1 Parameter Settings
The physical parameters for the truck and UAV drones are:
| Parameter | Truck | Drone |
|---|---|---|
| Capacity | 100 kg | 2 kg |
| Speed | 5 m/s | 6 m/s |
| Cost rate | 0.6 $/h | 0.15 $/h |
| Gravitational acceleration | g = 9.81 N/kg | – |
| Air density | ρ = 1.204 kg/m³ | – |
Algorithm parameters: T₀ = 300, δ = 0.98, Tmin = 1, weight update period = 20, θ = 0.8, scores (σ₁,σ₂,σ₃) = (6,4,2), maximum iterations = 300.
4.2 Convergence Behavior
I solve an instance with 50 customers. The algorithm records the minimum total cost in each generation. The cost quickly drops in the first 50 iterations and then gradually stabilizes, demonstrating effective convergence.
The figure above illustrates a typical UAV drone used in the experiments. The drone’s flight range and payload are critical constraints.
4.3 Comparison with Baseline
I compare my ALNS results against the initial greedy solution for different numbers of customers. The following table shows the average total cost over 10 random runs for each instance size.
| No. customers | Initial cost ($) | ALNS cost ($) | Improvement (%) |
|---|---|---|---|
| 20 | 42.3 | 35.8 | 15.4 |
| 30 | 68.7 | 56.2 | 18.2 |
| 50 | 124.5 | 98.3 | 21.1 |
| 80 | 215.4 | 166.7 | 22.6 |
| 100 | 298.1 | 225.4 | 24.4 |
Improvements increase with instance size, confirming that the ALNS is especially beneficial for larger problems where manual tuning is impossible.
4.4 Impact of UAV Drones
To understand the value of UAV drones, I run the algorithm in two modes: trucks only, and trucks + drones. For a 50‑customer instance, the truck‑only solution cost is $145.2, while the hybrid solution cost is $98.3 – a 32% reduction. This demonstrates the significant potential of integrating UAV drones into last‑mile delivery.
5. Conclusion
I have presented a two‑stage ALNS algorithm for the Vehicle Routing Problem with Drones (VRPD). The method first constructs a feasible initial solution using a savings‑greedy heuristic, then applies adaptive removal and insertion operators with SA acceptance to improve quality. Computational experiments on random instances show that the algorithm converges quickly and yields solutions that are 15–25% better than the initial greedy solution. Furthermore, the use of UAV drones reduces total cost by over 30% compared to truck‑only delivery. Future work will extend the model to include time windows, multiple drone types, and dynamic re‑routing.