Hybrid Metaheuristic Combining the Dragonfly Algorithm and Tabu Search for the Traveling Salesman Problem
2026-06-08 • Neural and Evolutionary Computing
Neural and Evolutionary Computing
AI summaryⓘ
The authors tackle the Traveling Salesman Problem (TSP), which asks for the shortest route visiting all cities once. They combine two methods: the Dragonfly Algorithm (DA), which searches broadly for solutions, and Tabu Search (TS), which fine-tunes solutions by avoiding repeats. This hybrid approach first explores possible routes with DA, then improves them with TS. Testing on known benchmark problems shows their method generally finds better routes than using DA or TS alone. However, results depend a lot on parameter choices and problem size, so the authors suggest more testing is needed.
Traveling Salesman ProblemNP-hardDragonfly AlgorithmTabu SearchMetaheuristicGlobal SearchLocal SearchHigh-Level Relay HybridizationTSPLIBGrid Search
Authors
Ammar Bouketta
Abstract
The Traveling Salesman Problem (TSP) is a classical NP-hard combinatorial optimization problem that aims to find the shortest Hamiltonian cycle visiting each city exactly once and returning to the starting point. This paper proposes a hybrid metaheuristic for the TSP by combining the Dragonfly Algorithm (DA), a swarm-intelligence-based global search method, with Tabu Search (TS), a memory-based local search technique. The proposed method follows a High-Level Relay Hybridization (HRH) scheme, in which DA is first used to explore the solution space and generate a promising initial tour, while TS subsequently refines this solution through neighbourhood-based improvement and tabu memory. The hybrid approach is evaluated on standard TSPLIB benchmark instances, including burma14, att48, and ch150, and compared with standalone DA, standalone TS, and several classical metaheuristics such as Genetic Algorithm, Ant Colony Optimization, Particle Swarm Optimization, and Random Search. A systematic grid-search procedure is also conducted to study the influence of the main hyperparameters on solution quality and execution time. The experimental results indicate that the proposed hybrid can improve tour quality compared with the standalone DA and TS on the tested instances, highlighting the benefit of combining global exploration with local exploitation. However, the results also suggest that performance remains sensitive to parameter settings and problem size, motivating further validation on larger benchmarks and stronger TSP-specific baselines.