ADPSO-ERLS: A Hybrid Discrete PSO with Enhanced Local Search for the Traveling Salesman Problem

Abstract

The Traveling Salesman Problem is a canonical setting for studying how a population-based method should allocate a fixed search budget between exploration and progressively stronger local intensification. We propose ADPSO-ERLS, a discrete swarm algorithm that treats this allocation as an explicit, tunable design variable. It couples memory-guided swap mutation, heterogeneous initialization, selective candidate-restricted 2-opt during evolution, and an incumbent-only final refinement combining candidate-restricted and optional full 2-opt with double-bridge perturbations. The method is PSO-inspired, using personal and global memories yet dispensing with velocity, inertia, and acceleration coefficients. All six algorithms are implemented in Rust, run on identical hardware, and stopped at a strict, recorded limit of 100,000 candidate-solution assessments, so that programming language, hardware, and evaluation budget are held common across methods; wall-clock time is reported separately because equal assessment counts need not correspond to equal arithmetic work. Over 50 runs on five symmetric TSPLIB instances under the integer \texttt{EUC\_2D} convention, ADPSO-ERLS attains the lowest best and mean cost on every instance, with best-tour Gap of $1.93$--$4.17\%$ and relative error of $3.04$--$5.50\%$. It ranks first under the Friedman test, and all twenty-five multiplicity-controlled Wilcoxon comparisons favor it with large, near-complete distributional separation. A paired ablation with common seeds links initialization, in-run local search, and final refinement to quality gains, while candidate restriction chiefly cuts runtime, by up to a factor of roughly $38$. Further experiments up to $16{,}862$ cities keep best-tour Gaps below $6.7\%$, solving the largest case in under eleven minutes.