Abstract

The Traveling Salesman Problem (TSP) is a fundamental NP-hard combinatorial optimization problem with broad applications in logistics, scheduling, and satellite mission planning. While Ant Colony Optimization (ACO) offers distributed search and positive feedback, conventional variants suffer from premature convergence and quadratic construction costs that limit scalability. We propose the Globally Adaptive Ant Colony System (GACS), which integrates three synergistic mechanisms: (1) K-nearest neighbor candidate-list pruning that reduces per-step construction complexity from O(n) to O(K); (2) a globally adaptive pheromone weighting scheme that dynamically calibrates reinforcement intensity as the search matures; and (3) an adaptive stagnation recovery mechanism that applies pheromone smoothing to escape local optima. Numerical experiments demonstrate that GACS consistently outperforms four traditional ACO baselines under an equivalent time budget. On a large benchmark set from TSPLIB, GACS achieves highly competitive results against various state-of-the-art metaheuristics, with non-parametric statistical tests confirming its significant superiority in both solution quality and convergence rank. Ablation and sensitivity analyses verify that all three mechanisms are individually indispensable and that the framework is robust to parameter perturbation. Specifically, the evaporation rate and stagnation threshold are identified as the most critical parameters affecting performance, while the smoothing and adaptive range parameters exhibit low sensitivity. These results establish GACS as a lightweight, scalable, and adaptable framework for the TSP.

Keywords