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

ADPSO-ERLS is a hybrid discrete Particle Swarm Optimization (PSO) algorithm with enhanced local search for the Traveling Salesman Problem (TSP). The paper addresses the design question of how a population-based method should allocate a fixed search budget between exploration and progressively stronger local intensification. The method treats this allocation as an explicit, tunable design variable.

The algorithm couples a discrete particle-swarm layer, which determines where to search, with a local-search layer, which determines how much quality to extract from selected regions. It replaces the continuous PSO velocity equation with a permutation-safe, memory-driven transformation: at each update, a particle selects its personal best with probability γ and the global best with probability 1−γ, then applies a random swap to a copy of the selected memory. Among up to s independently generated swap candidates, the shortest one becomes the particle's new position. The method has no velocity vector, inertia weight, or acceleration coefficients.

ADPSO-ERLS incorporates three coordinated mechanisms: (1) memory-driven permutation movement with heterogeneous seeding, where an elite fraction α of the swarm is initialized by nearest-neighbor construction while the remainder stays uniformly random; (2) elitist candidate-restricted local search (ERLS), where 2-opt is confined to K-nearest candidate lists, applied only to an elite subset of the swarm, only every l iterations, and only for at most T2 passes; and (3) staged final refinement with controlled perturbation, concentrating the strongest effort on the incumbent alone through candidate-restricted 2-opt, an optional full 2-opt phase, and double-bridge perturbations followed by candidate-restricted repair, each committed only on strict improvement.

The central scheduling rule is Bevo = ⌊ηB⌋ and Bfin = B − Bevo, where B is the global evaluation limit (100,000 in experiments) and η = 0.7 is the fixed fraction assigned to initialization and evolutionary search. The final reserve is partitioned into three cumulative deadlines for the final refinement stages. A strict evaluation accounting rule charges one function-evaluation unit (FES) for every assessed candidate tour, including swap candidates, 2-opt candidates, and double-bridge candidates, regardless of whether the cost is computed via complete summation or incremental edge deltas.

The experimental evaluation uses five symmetric TSPLIB instances (d493, d657, rat783, pr1002, u1060) with reference optimal costs of 35002, 48912, 8806, 259045, and 224094, respectively. ADPSO-ERLS is compared against five baseline methods: SA-DPSO, AACO-LST, DPSO6, DPSO-Q, and AAACO. All six algorithms are implemented in Rust, run on identical hardware, and stopped at a strict, recorded limit of 100,000 candidate-solution assessments.

Over 50 independent runs per instance, ADPSO-ERLS attains the lowest best cost and lowest mean cost on all five instances. Its best-tour Gap ranges from 1.93% to 4.17%, relative error (RE) ranges from 3.04% to 5.50%, and average percentage deviation (APD) ranges from 0.95% to 1.28%. The Gap margin separating ADPSO-ERLS from the second-best method grows monotonically with instance size: 2.14, 2.74, 3.26, 4.85, and 5.62 percentage points from d493 to u1060. The method displays the smallest standard deviation on d493 (265.68) and the second smallest on d657, rat783, pr1002, and u1060, being outperformed in dispersion only by SA-DPSO on those four instances.

The Friedman test assigns ADPSO-ERLS the best attainable mean rank of 1.0, with χ2F(5) = 23.057 and p = 3.292 × 10−4. The Iman–Davenport correction yields FF(5, 20) = 47.471 with p = 2.042 × 10−10, confirming the global difference. All 25 paired Wilcoxon signed-rank comparisons favor ADPSO-ERLS, with 24 of 25 yielding W− = 0, W+ = 1275, Z = 6.154, and p = 7.557 × 10−10. The remaining comparison (versus AACO-LST on d493) yields W− = 1, W+ = 1274, Z = 6.144, and p = 8.031 × 10−10. Even the Bonferroni bound for 25 tests (at most 2.008 × 10−8) keeps every comparison significant. The Vargha–Delaney A12 equals 0 in 23 comparisons, with the only nonzero values being 0.0028 (d493 versus AACO-LST) and 0.0072 (d657 versus AACO-LST), both indicating near-complete empirical separation and large effect sizes.

The ablation study compares the complete method with five variants that respectively remove heterogeneous initialization, evolutionary ERLS, final refinement, double-bridge perturbation, or candidate-list restriction. Removing heterogeneous initialization increases mean cost by 1.09–2.82% across instances; disabling evolutionary ERLS worsens every mean by 0.52–1.60%; removing final refinement produces degradations of 0.83–2.48% and the largest dispersion on d657 and u1060; suppressing double-bridge perturbation has a smaller but consistent effect of 0.10–0.81%. Candidate lists act mainly as an efficiency mechanism: replacing them with complete neighborhoods changes mean cost by only −0.47% to +0.66%, but average runtime rises dramatically, from 19.18 to 166.84 seconds on d493, from 1.70 to 54.47 seconds on d657, from 2.51 to 94.98 seconds on rat783, from 12.51 to 342.88 seconds on pr1002, and from 32.59 to 740.24 seconds on u1060, representing runtime increases by factors of roughly 8.7 up to 37.8.

The scalability experiments extend the evaluation to seven further instances of 1,400 to 16,862 cities: fl1400, u1432, u2319, Canada4663, Japan9847, usa13509, and Italy16862. Under the same strict budget B = 100,000, ADPSO-ERLS keeps best-tour Gaps below 6.7%, with values of 2.13%, 4.91%, 3.32%, 5.14%, 6.41%, 6.05%, and 6.61% respectively. The method processes the 16,862-city Italy16862 instance in under eleven minutes (659.33 seconds per run) on the reported platform. The runtime for u2319 is only 6.52 seconds, indicating that runtime is determined by the interaction among instance structure, population size, candidate-list size, and local-refinement settings rather than by the number of cities alone.

The paper concludes that the principal contribution is methodological: treating the allocation of search effort itself as an explicit, auditable, and optimizable design variable yields a transparent and reproducible framework. The individual ingredients (discrete swarm learning, candidate-list restriction, local search, perturbation, and hybridization) are established, and no novelty is claimed for them in isolation. The evidence supports the reading of ADPSO-ERLS as a coordination of complementary mechanisms rather than a dependence on one operator.

Improvements to AI Systems:

1. Explicit Budget-Allocation Mechanism for Metaheuristics: Implement a tunable parameter (η) that explicitly splits a fixed computational budget between exploration (population-based search) and exploitation (local refinement). This allows AI optimization systems to be audited and optimized for different problem scales, rather than relying on implicit, hard-coded search strategies.

2. Memory-Driven Discrete Movement without Velocity Vectors: Replace continuous velocity/inertia equations in PSO with a permutation-safe, memory-driven update rule (selecting personal best with probability γ, global best with probability 1−γ, then applying random swaps). This enables AI systems to handle combinatorial/discrete search spaces (e.g., scheduling, routing) without requiring continuous relaxation or complex encoding schemes.

3. Elitist Candidate-Restricted Local Search (ERLS) Scheduling: Confine expensive 2-opt local search to only an elite subset of the population, only every l iterations, and only for T2 passes, using K-nearest candidate lists. This allows AI systems to scale to large problem instances (up to 16,862 cities) under strict evaluation limits, reducing runtime by factors of 8.7–37.8 while maintaining solution quality.

4. Staged Final Refinement with Controlled Perturbation: Implement a multi-phase final refinement (candidate-restricted 2-opt → optional full 2-opt → double-bridge perturbation with repair) that applies the strongest effort only to the incumbent solution, committing changes only on strict improvement. This gives AI systems a robust polishing phase that escapes local optima without wasting budget on non-elite solutions.

5. Heterogeneous Seeding for Population Diversity: Initialize an elite fraction (α) of the population with nearest-neighbor construction while keeping the rest uniformly random. This improves AI systems' ability to balance initial solution quality and diversity, reducing mean cost by 1.09–2.82% across instances compared to uniform initialization.

6. Strict Evaluation-Accounting Rule for Fair Comparison: Charge one function-evaluation unit for every assessed candidate (including swap, 2-opt, and double-bridge candidates), regardless of computation method. This enables AI systems to be compared fairly across different algorithms and ensures that computational effort is transparently tracked, preventing hidden budget inflation.

7. Scalable Candidate-List Restriction as an Efficiency Primitive: Use K-nearest candidate lists to restrict neighborhood searches, reducing runtime dramatically (e.g., from 740.24s to 32.59s on u1060) with minimal quality loss (−0.47% to +0.66% mean cost change). This allows AI systems to handle ultra-large instances in real-time or near-real-time applications.

What the Improved AI System Can Do:

• Optimize large-scale combinatorial problems (e.g., logistics routing, circuit design, genome assembly) with up to 17,000 elements under a strict 100,000-evaluation budget, achieving solutions within 6.7% of optimal.

• Adaptively allocate search effort between exploration and exploitation based on a user-defined budget fraction, making it suitable for both time-critical and high-accuracy applications.

• Run efficiently on limited hardware—e.g., solving a 2,319-city instance in 6.52 seconds and a 16,862-city instance in under 11 minutes—enabling deployment in embedded or interactive systems.

• Provide statistically robust performance with near-zero variance in comparisons (A12 effect size = 0 in 23/25 cases), ensuring reliable outcomes across repeated runs.

• Escape local optima systematically via double-bridge perturbations and strict-improvement acceptance, improving final solution quality by 0.83–2.48% over methods without this refinement.

• Scale gracefully with problem size—the performance gap over second-best methods grows monotonically (from 2.14 to 5.62 percentage points) as instance size increases, making it ideal for industrial-scale optimization.

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 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.