Source-linked AI summary
A Variable Neighborhood Search for Flying Sidekick Traveling Salesman Problem
Julia C. Freitas, Puca Huachi V. Penna
TL;DR
Drone-assisted delivery addresses the need to reduce delivery time and operational cost while combining trucks’ capacity with drones’ speed. The paper develops HGVNS by improving an optimal TSP tour with GVNS, and experiments report substantial improvements, including delivery-time reductions up to 67.79%.
Problem
Drone delivery must coordinate drones’ speed and limited endurance with trucks’ larger capacity to reduce delivery time and operational cost.
Method
HGVNS uses a MIP solver to obtain an optimal TSP tour and then enhances it with the General Variable Neighborhood Search metaheuristic.
Results
Up to 67.79% delivery-time improvement was reported from collaborative truck-and-drone parcel delivery.
Takeaways & Limitations
The results demonstrate the effectiveness of combining trucks and drones for last-mile parcel delivery.
Takeaways & Limitations
The Agatz et al. instances could not be compared with their method because that work did not provide a complete review of its experiments.
Abstract
from arXiv · showhide
The efficiency and dynamism of Unmanned Aerial Vehicles (UAVs), or drones, present substantial application opportunities in several industries in the last years. Notably, the logistic companies gave close attention to these vehicles envisioning reduce delivery time and operational cost. A variant of the Traveling Salesman Problem (TSP) called Flying Sidekick Traveling Salesman Problem (FSTSP) was introduced involving drone-assisted parcel delivery. The drone is launched from the truck, proceeds to deliver parcels to a customer and then is recovered by the truck in a third location. While the drone travels through a trip, the truck delivers parcels to other customers as long as the drone has enough battery to hover waiting for the truck. This work proposes a hybrid heuristic that the initial solution is created from the optimal TSP solution reached by a TSP solver. Next, an implementation of the General Variable Neighborhood Search is used to obtain the delivery routes of truck and drone. Computational experiments show the potential of the algorithm to improve the delivery time significantly. Furthermore, we provide a new set of instances based on well-known TSPLIB instances.
1. Introduction
Drone delivery is motivated by demand for faster service, but drones’ limited payload and endurance complement trucks’ larger capacity. The paper proposes combining both vehicles through FSTSP routes and contributes a heuristic and new TSPLIB-based instances.
- 43% of customers identified enhanced delivery options as an important purchasing characteristic.
- Drones offer speed but limited payload and endurance, whereas trucks carry numerous parcels more slowly.
- FSTSP combines truck and drone operations to exploit their complementary delivery capabilities.
- The proposed heuristic builds collaborative truck-and-drone routes and introduces new instances based on TSPLIB instances.
2. Related Works
Related work covers diverse drone-delivery problems, vehicle configurations, network assumptions, objectives, and solution methods. FSTSP and related variants differ in how trucks and drones coordinate, serve customers, and model travel.
- Prior studies address truck-and-drone routing, drone-only delivery, same-day delivery, environmental impact, and multi-objective urban logistics.
- FSTSP uses one truck and one drone in tandem, while PDSTSP assigns nearby customers primarily to drones and distant customers to trucks.
- Some studies compare solution quality and runtime, with GRASP outperforming TSP-LS in quality but requiring more computational time.
- Researchers apply heuristics, genetic algorithms, integer programming, dynamic programming, local search, simulated annealing, and policy approximation.
- Related formulations vary in whether trucks and drones share road networks, whether launch and return locations may coincide, and whether waiting is allowed.
3. Problem Description
The FSTSP models one truck and one drone collaboratively serving eligible customers under payload, endurance, travel-time, and routing constraints. Drone trips reduce truck travel and can reduce overall delivery time, but overlapping trip patterns are prohibited.
- One truck and one drone collaboratively serve customers, with drone eligibility constrained by payload capacity and flight endurance.
- Truck travel follows the road network while drone travel uses straight-line paths, and travel time accounts for differing vehicle speeds and service operations.
- Serving customers 4 and 8 by drone shortens the truck route and reduces the overall delivery time in the illustrated nine-customer route.
- FSTSP assigns customers to truck-only, drone-only, or mixed roles within a route.
- The drone trip comprises launch, visiting, and return nodes, with the return occurring at a truck-serviced customer or depot.
- Two prohibited situations prevent overlapping or nested drone trips in the single-drone route.
4. HGVNS Algorithm
HGVNS combines an exact TSP-based initialization with neighborhood-search heuristics to construct and improve coordinated truck–drone delivery routes.
- HGVNS framework: HGVNS uses an exact model to obtain an initial solution and GVNS as the improvement heuristic.The framework uses truck and drone travel-time matrices, τ and τ′.
- Initial solution: The initial solution starts with the optimal truck-only TSP route, which is feasible for FSTSP without drone trips.This route is then passed to a procedure that adds drone trips.
- Initial solution: CreateInitialSolution removes eligible customers from the truck route and assigns them to drone trips when the computed savings are positive.The procedure repeatedly evaluates savings across truck subroutes and updates the route when maxSavings > 0.
- GVNS and RVND: GVNS generates a solution from successive neighborhoods, applies RVND local search, and restarts from the first neighborhood after an improvement.If no improvement occurs, GVNS advances to the next neighborhood until the neighborhood list is exhausted.
- GVNS and RVND: RVND randomly shuffles neighborhoods, selects the best neighbor, and reinitializes the neighborhood list whenever it improves the current solution.The search stops after all neighborhoods are explored without improvement.
4.1. Neighborhoods
The neighborhood framework stores truck and drone routes explicitly, evaluates local changes efficiently, and accepts only feasible moves.
- Solution representation: The solution is stored in arrays, with each drone trip represented by launch, visit, and return nodes.The drone array therefore encodes each trip as a three-value tuple.
- Cost evaluation: Truck-only customer changes can be evaluated in O(1) using the cost difference between removed and reconnected edges.Equation (1) uses the fixed-size edge sets θ− and θ+ rather than recomputing the full route cost.
- Cost evaluation: For mixed truck–drone moves, the drone trip changes solution cost only when its last trip returns to the depot.Otherwise, the new cost can be determined entirely from changes to the truck route.
- Feasibility: A neighborhood move is accepted only if it remains feasible, satisfies drone endurance, and avoids the prohibited situations shown in Figure 2.These conditions constrain the neighborhood operations before route updates are accepted.
4.2. Reinsertion
The reinsertion neighborhood removes one customer and inserts it at another position, potentially changing the associated drone trip.
- Reinsertion: Reinsertion relocates a customer to another position in a tentative solution.Relocating a customer can increase the truck route during a drone trip and alter that trip’s structure.
- Reinsertion: A relocation may preserve the original drone launch node or invert the trip so the relocated customer becomes its return node.These alternatives are illustrated as cases (b) and (c) in Figure 3.
4.3. Or-opt2
The Or-opt2 neighborhood relocates two adjacent truck-path nodes and can either leave the drone route unchanged or extend a drone subroute.
- Or-opt2: Or-opt2 relocates two adjacent truck-path nodes to an arbitrary position in a tentative solution.The example moves consecutive nodes 5 and 3.
- Or-opt2: The relocation may leave the drone route unchanged or increase a subroute containing a drone trip.These alternatives are shown in Figure 4 cases (a) and (b).
4.4. Exchange
The Exchange neighborhood swaps one customer with another while preserving feasibility by changing the drone trip’s return node when necessary.
- 4.4. Exchange: Exchange swaps a customer with another in a tentative solution.If keeping the original launch and return nodes would violate prohibition 2b, the return node is changed.
- 4.4. Exchange: In the example, customer 2 becomes the new returning node, changing trip {5, 7, 1} to {5, 7, 2}.
4.5. Exchange(2,1)
Exchange(2,1) swaps two adjacent customers with one customer and adjusts drone-trip structure to avoid prohibited overlaps.
- 4.5. Exchange(2,1): Exchange(2,1) swaps two adjacent customers with another customer in a tentative solution.
- 4.5. Exchange(2,1): The first trip {5, 7, 1} changes its return node to 2 to avoid the prohibition illustrated in Figure 2b.
- 4.5. Exchange(2,1): In the example, trip {6, 3, 1} is inverted, increasing truck travel distance and drone waiting time.
4.7. 2-opt
The 2-opt neighborhood reconnects routes after removing two edges, while customer relocation can create a new drone trip intended to reduce delivery time.
- 4.7. 2-opt: 2-opt removes two truck-only or mixed-node edges and reconnects the resulting paths to maintain a valid tour.If a removed edge belongs to a drone trip, another return node must be selected.
- 4.7. 2-opt: Customer relocation removes a truck customer and inserts it into a new drone trip after forming feasible sub-routes.The launch node, drone customer, and return node are then evaluated.
5. Computational Experiments
Computational experiments evaluate HGVNS on literature benchmarks and new TSPLIB-based instances, comparing delivery solutions with TSP and prior FSTSP results.
- Experimental setup: HGVNS was implemented in C++ and tested on three benchmark sets, including a new TSPLIB-based instance set.The experiments used Concorde to obtain an optimal TSP solution and ran on an Intel Core i7 system with 16 GB RAM.
- Ponza (2016) instances: 19.50% average improvement and up to 30.38% lower total travel time were obtained over classical TSP solutions in the Ponza instance set.
- Ponza (2016) instances: HGVNS produced better results in all Ponza instances than Ponza’s results, with a 24.84% improvement in instance 150.2 and 10.15 seconds average runtime.The paper notes that runtime comparisons are imprecise because Ponza (2016) does not report computer configuration.
- Agatz et al. (2016) instances: In Agatz-based experiments, α = 1 produced the worst results, while the 75-customer single-center instance achieved a 62.24% improvement over the optimal TSP solution.Higher drone speed enabled visits to more and farther customers; uniform distributions had the lowest average improvement.
- Agatz et al. (2016) instances: Runtime was unaffected by customer distribution, but increased when vehicles had the same speed and customers were uniformly distributed.
- TSPLIB instances: The new TSPLIB set contains 25 adapted instances with 51–200 nodes, and HGVNS improved on the TSP optimum for every instance.Improvement ranged from 4% for pr107 to 0.35% for d198; the pr107 solution assigned 16 deliveries to the drone.
6. Concluding Remarks
The paper applies a hybrid heuristic combining truck and drone delivery, evaluates it across benchmark and newly generated instances, and reports substantial delivery-time improvements.
- 6. Concluding Remarks: HGVNS combines truck and drone capabilities, starting from an optimal TSP tour and improving it with General Variable Neighborhood Search.The method uses a mixed-integer programming solver for the initial TSP solution before applying the metaheuristic.
- 6. Concluding Remarks: HGVNS was evaluated on three benchmark sets, including Ponza, Agatz et al., and a new set derived from TSPLIB instances.The new instances extend evaluation beyond the two literature-based sets.
- 6. Concluding Remarks: 24.84% improvement was achieved over previously best-known solution values for the majority of Ponza instances.This is the largest improvement reported for that benchmark set.
- 6. Concluding Remarks: Drone speed affected total delivery time in 1,383 TSP-D instances, while doubling and tripling truck speed produced similar effects.The best improvement occurred with 75 customers when the drone traveled twice as fast as the truck; the least improvements occurred at equal speeds.
- 6. Concluding Remarks: 45.48% improvement over the optimal TSP tour value was obtained on the new TSPLIB-based instances.These instances were created to address the need for large cases following the original Murray and Chu model.
- 6. Concluding Remarks: Collaborative truck-and-drone delivery reduced delivery times by up to 67.79%.The reported result supports the effectiveness of combining the complementary characteristics of both vehicles for last-mile parcel delivery.