Source-linked AI summary
A Hybrid Genetic Algorithm for the Traveling Salesman Problem with Drone
Quang Minh Ha, Yves Deville, Quang Dung Pham, Minh Hoàng Hà
TL;DR
The paper studies TSP-D, which coordinates a truck and drone to deliver parcels while minimizing operational cost or completion time. It proposes a hybrid genetic algorithm with adaptive search controls and problem-tailored operators. Computational experiments show that HGA outperforms existing methods in solution quality and improves several best known solutions, while taking longer than GRASP.
Problem
TSP-D requires coordinating truck-and-drone parcel delivery while minimizing either total operational cost or vehicle completion time.
Method
HGA combines genetic and local search with population management, adaptive diversity control, penalization, problem-tailored operators, and a restore mechanism.
Results
HGA outperforms existing methods in solution quality and improves a number of best known solutions in the literature.
Takeaways & Limitations
The proposed hybrid search provides improved solution quality for TSP-D under both min-cost and min-time objectives.
Takeaways & Limitations
HGA is 1.5 to 2 times slower than GRASP because of its more complex design.
Abstract
from arXiv · showhide
This paper addresses the Traveling Salesman Problem with Drone (TSP-D), in which a truck and drone are used to deliver parcels to customers. The objective of this problem is to either minimize the total operational cost (min-cost TSP-D) or minimize the completion time for the truck and drone (min-time TSP-D). This problem has gained a lot of attention in the last few years since it is matched with the recent trends in a new delivery method among logistics companies. To solve the TSP-D, we propose a hybrid genetic search with dynamic population management and adaptive diversity control based on a split algorithm, problem-tailored crossover and local search operators, a new restore method to advance the convergence and an adaptive penalization mechanism to dynamically balance the search between feasible/infeasible solutions. The computational results show that the proposed algorithm outperforms existing methods in terms of solution quality and improves best known solutions found in the literature. Moreover, various analyses on the impacts of crossover choice and heuristic components have been conducted to analysis further their sensitivity to the performance of our method.
1. Introduction
The paper develops a hybrid genetic algorithm for TSP-D, where trucks and drones deliver parcels while minimizing operational cost or completion time. Its adaptive search components improve solution quality across objectives and instance sets, outperform existing approaches, and improve some best known solutions.
- Problem motivation: TSP-D coordinates truck-and-drone parcel delivery under either min-cost or min-time objectives.The paper situates this problem within emerging drone-assisted delivery methods.
- Related work: Prior TSP-D research introduced truck-and-drone formulations, heuristics, exact approaches, and extensions involving shared networks, endurance, and cost.The literature includes FSTSP, PDSTSP, and related generalizations such as VRPD.
- Proposed approach: The proposed HGA combines genetic search, local search, population management, diversity control, and penalization to balance feasible and infeasible search.Its problem-tailored components include a new crossover, 16 local search operators, and restore mechanisms.
- Evaluation: Computational experiments evaluate HGA on instance sets under both min-cost and min-time objectives and analyze the importance of its components.The experiments compare solution quality and assess the efficiency of newly proposed elements.
- Results: HGA outperforms existing approaches in solution quality and improves a number of best known solutions.The paper reports these outcomes across the evaluated instance sets and objectives.
2. Problem description
The TSP-D assigns parcel deliveries between a truck and a drone, subject to routing, rendezvous, eligibility, endurance, and waiting requirements. It minimizes either total operational cost or the completion time of both vehicles.
- System and deliveries: A TSP-D solution serves customers with one truck and one drone, both starting and returning to the depot.Each customer is served once by either vehicle, and drone deliveries use launch, delivery, and rendezvous nodes.
- System and deliveries: A drone delivery is represented by ⟨i, j, k⟩, where i launches the drone, j is the drone-served customer, and k is the rendezvous node.The drone must serve an eligible customer and rejoins the truck at k for recovery and preparation.
- Operational constraints: Truck and drone movements must satisfy endurance constraints combining travel and recovery times with the drone’s maximum operational time.Truck recovery may include preparation for a subsequent launch, while drone recovery is included in its own endurance constraint.
- Objectives and costs: The model accounts for vehicle-specific transportation costs and waiting costs incurred when the truck and drone wait at rendezvous points.Truck and drone have separate distance costs, waiting times, and waiting fees.
- Objectives and costs: The min-cost TSP-D minimizes total operational cost, whereas the min-time TSP-D minimizes the completion time of the truck and drone.The formulation represents travel distances, travel times, and effective arrival times for both vehicles.
3. A Hybrid Genetic Algorithm for TSP-D (HGA)
The HGA combines genetic search with TSP-D-specific split, crossover, local search, restoration, population management, diversity control, and adaptive penalization. Its iteration alternates offspring generation and improvement with feasibility handling, survivor selection, penalty adjustment, and diversification.
- The HGA adapts a hybrid genetic framework to TSP-D with new local search operators, crossovers, penalization, and restoration.
- Each iteration selects two parents, generates an offspring, applies split, and educates it using local search.
- Infeasible offspring enter an infeasible subpopulation and have a 50% repair probability; feasible offspring enter the feasible subpopulation.
- When a subpopulation reaches its limit, survivor selection keeps the best individuals, while penalty adjustment and diversification respond to constraint violations and stalled improvement.
- The algorithm returns the best feasible solution after managing feasible and infeasible search through dynamic population procedures.
- The restore method updates the offspring’s giant-tour chromosome after local search, maintaining the representation used by the algorithm.
3.1. Search space
The search space contains both feasible and infeasible TSP-D solutions, with infeasibility arising from violated truck or drone endurance constraints. Min-cost and min-time objectives use penalized evaluations that combine operational measures with weighted constraint violations.
- The search space includes feasible and infeasible solutions, with infeasibility defined by violations of the drone endurance constraint.
- A drone delivery is invalid when the truck travel-time or drone travel-time constraint is violated, subject to the stated depot exception.
- A TSP-D solution consists of a truck tour TD and a set of drone deliveries DD.
- For min-cost TSP-D, penalized cost combines operational cost with weighted excess travel-time penalties for constraint violations.
- The penalized objective is used as the fitness function for evaluating individuals.
- For min-time TSP-D, completion time is the maximum of the truck’s and drone’s completion times, with penalties added for constraint violations.
3.2. Solution representation
HGA represents solutions as giant TSP tours without the two depots and transforms them into TSP-D solutions when needed. Split and restore enable efficient operators across crossover and local search representations.
- An HGA solution is represented as a giant TSP tour with the two depots removed.
- The split procedure converts a giant-tour chromosome into a TSP-D solution for local search.
- The restore method converts a TSP-D solution back into a giant tour.
- The split-and-restore transformation allows efficient operators in both crossover and local search.
3.3. Individual evaluation
Individual evaluation balances penalized solution quality with population diversity. Biased fitness ranks individuals using both factors, while normalized giant-tour distance measures differences between chromosome positions.
- Individual evaluation considers penalized cost and contribution to population diversity.
- Diversity contribution is based on the average distance from an individual to its closest population neighbours.
- Balancing cost and diversity avoids focusing only on rapid convergence or exploring completely different giant tours as random search.
- The distance between two individuals is a normalized Hamming distance over nodes occupying the same giant-tour positions.
- The distance indicator returns 1 when corresponding giant-tour positions contain different nodes and 0 otherwise.
- Biased fitness combines rank by penalized cost with rank by diversity contribution, while preserving a specified number of elite individuals.
3.4. Parent selection and crossover
The HGA selects parents by biased fitness and creates offspring through crossover that combines parent tour information with an educated TSP-D solution. Its DX crossover is tailored to preserve truck and drone delivery characteristics while constructing a valid offspring tour.
- Parent selection: Parents are chosen through tournament selection, retaining the individual with the best biased fitness.
- Crossover choice: The section contrasts DX with classical TSP crossovers including OX, PMX, OBX, and PBX.
- DX crossover: The crossover randomly selects either truck deliveries or drone deliveries, then copies a segment between two cut points into the offspring.
- DX crossover: Remaining offspring positions are filled with nodes from one parent while preserving their relative order from the other parent, then two depots are removed.
- DX crossover: DX uses two parents, an educated TSP-D solution for one parent, and depot-augmented tours as crossover inputs.
3.5. Education using local search
The education phase improves TSP-D solutions through local search using 16 truck- and drone-oriented move operators. Move evaluation separately accounts for min-cost and min-time objectives, while precomputation reduces computation time.
- Local search: The education step improves solution quality through hill-climbing and first-improvement local search.
- Objective evaluation: Move costs are evaluated separately for min-cost and min-time objectives using affected truck and drone travel quantities.
- Acceleration: Truck and drone cumulative quantities and tuple costs are pre-computed at initialization to accelerate the algorithm.
- Drone operators: Drone insertion creates a delivery tuple ⟨i, j, k⟩ only when the move introduces no interfering drone activity between launch node i and rendezvous node k.
3.6. Restore method
The restore method feeds an educated TSP-D solution back into the genetic representation by reinserting drone nodes into the truck tour. This produces a new giant-tour chromosome reflecting the educated truck-and-drone structure.
- Purpose: The restore method uses an educated TSP-D solution to update the existing giant-tour individual.
- Reinsertion: Drone nodes are reinserted at random positions between their launch and rendezvous nodes on the solution’s truck tour.
- Chromosome construction: After reinsertion, two depots are removed to obtain a valid giant-tour individual.
- Outcome: The resulting chromosome represents an educated truck tour with drone nodes reinserted, as illustrated in Figure 3.
3.7. Population management
Population management maintains separate feasible and infeasible subpopulations while applying education, repair, restoration, survivor selection, diversification, and adaptive penalty adjustment. These mechanisms regulate population quality, diversity, and movement between search regions.
- Initialization: The algorithm initializes 4µ individuals using a k-cheapest insertion heuristic with k = 3, producing giant-tour chromosomes.
- Population processing: Individuals pass through splitting, education, probabilistic repair when infeasible, restoration, and assignment to appropriate subpopulations.
- Survivor selection: Each subpopulation contains between µ and µ + λ individuals, and excess populations discard λ clones or individuals with the worst biased fitness.
- Diversification: When search progress stagnates after 0.3IterNI iterations, diversification retains the best 1/3µ individuals and generates 4µ new individuals.
4. Computational Results
The computational evaluation compares HGA with existing methods across min-cost and min-time TSP-D instances, then examines crossover choices and heuristic components. HGA generally improves solution quality, while its more complex design increases runtime and performance depends on problem-specific components.
- Performance on different instance sets: 6.16% and 15.10% average improvements were obtained for min-cost 50- and 100-customer instances, respectively.The improvements reached nearly 15% and 20%, respectively.
- Performance on different instance sets: 2.39% and 4.05% average improvements were obtained for min-time 50- and 100-customer instances, respectively.The improvements reached nearly 6% and 8%, respectively, although HGA was approximately 1.5 times slower than GRASP.
- Crossover performance: DX delivered the best crossover value by percentage gap for both min-cost and min-time objectives.For min-cost, DX was approximately 18%, 5.7%, 283%, and 16.5% better than OX, PMX, OBX, and PBX; for min-time, the corresponding figures were 26.5%, 10.2%, 283%, and 46.9%.
- Sensitivity analysis: Changing infeasibility handling, diversity contribution, repair, or restore settings negatively affected HGA performance.Removing infeasibility handling or diversity control increased the standard gap by more than 50%, supporting the use of feasible and infeasible solutions with diversity control.
5. Conclusion
The paper presents HGA as a hybrid genetic algorithm for solving TSP-D under min-cost and min-time objectives. Experiments report that HGA outperforms existing methods in solution quality, improves best known solutions, and motivates further testing on broader TSP-D variants.
- HGA effectively solves TSP-D under both min-cost and min-time objectives.
- HGA combines problem-tailored local searches, crossover, a restore method, and a penalized mechanism to guide the search.
- Computational experiments show that HGA outperforms existing methods in solution quality and is a state-of-the-art approximation method for TSP-D.
- HGA improves a number of best known solutions found in the literature.
- An extensive analysis examines the importance of HGA's new components to overall performance.
- Future work includes developing an exact method and testing HGA on TSP-D variants with multiple trucks and multiple drones under both objectives.