A Novel Hybrid Dynamic Pheromone Optimization Algorithm with Entropy-Guided Learning and Historical Route Intelligence for the Travelling Salesman Problem

Abstract: The Travelling Salesman Problem (TSP) remains one of the most extensively studied NP-hard combinatorial optimization problems due to its wide range of applications in logistics, transportation, manufacturing, and network design. Although Ant Colony Optimization (ACO) has demonstrated promising performance for solving TSP, traditional pheromone updating mechanisms often suffer from premature convergence, loss of population diversity, and stagnation in local optima. This paper proposes Hybrid Dynamic Pheromone Optimization (HDPO), a novel optimization algorithm that integrates entropy-guided learning, adaptive pheromone regulation, historical route intelligence, and dynamic local search mechanisms into a unified framework. HDPO dynamically adjusts pheromone evaporation and reinforcement based on search diversity, route entropy, and solution improvement rates. Furthermore, an elite historical memory structure preserves high-quality route knowledge across generations, while a stagnation recovery mechanism reintroduces exploration when convergence becomes excessive. Experimental evaluations on benchmark instances from TSPLIB can demonstrate that HDPO achieves superior solution quality, faster convergence, and enhanced robustness compared with classical ACO variants. The proposed method offers an effective balance between exploration and exploitation, making it suitable for large-scale TSP instances and other combinatorial optimization problems.

Keywords: Community Network, Travelling Salesman Problem (TSP), Ant Colony Optimization (ACO), HDPO, TSPLIB.