A Globally Adaptive Ant Colony System with Stagnation Recovery and Candidate-list Search for Traveling Salesman Problems

Source abstract

The Traveling Salesman Problem (TSP) remains a pivotal NP-hard challenge in combinatorial optimization, with critical applications spanning logistics, manufacturing, and industrial scheduling. While Ant Colony Optimization (ACO) is renowned for its distributed search and positive feedback, conventional variants frequently encounter premature convergence and “combinatorial explosion” in computational costs as problem scales expand. To overcome these bottlenecks, this paper proposes the Globally Adaptive Ant Colony System (GACS), a robust metaheuristic incorporating stagnation recovery and candidate-list pruning. The GACS framework integrates three synergistic strategies: (1) A K-nearest neighbor candidate-list compression that significantly reduces the search tree’s branching factor, maintaining high-quality solutions while ensuring effective linear scalability under fixed parameter configurations; (2) A global-adaptive pheromone weighting scheme that dynamically calibrates reinforcement intensity, facilitating a seamless transition from broad exploration to localized refinement; and (3) A multi-level stagnation recovery mechanism utilizing pheromone smoothing to preserve population diversity and bypass sophisticated local optima. Comprehensive evaluations on synthetic datasets and 33 benchmark instances from TSPLIB demonstrate that GACS consistently outperforms several recently published metaheuristic algorithms (including ABCSS, DSMO, and DWHO). Notably, GACS achieves a 5.5-fold acceleration in computational efficiency over hybrid genetic-ACO models and secures a favorable Average Rank of 1.44 across standard benchmarks. These results confirm that GACS provides a competitive balance between optimization accuracy and computational economy, offering a scalable and resilient paradigm for large-scale combinatorial optimization.