基于变邻域改进的蚁群算法的TSP问题仿真

Simulation of TSP Problem Based on Ant Colony Algorithm Improved by Variable Neighborhood

摘要: 旅行商问题(TSP)作为组合优化领域的经典难题，对物流路径规划等领域具有重要意义。传统蚁群算法(ACO)虽具备全局搜索能力，但存在易陷入局部最优和收敛速度不足的问题。为此，本文提出一种融合变邻域搜索(VNS)的改进蚁群算法(ACO-VNS)，旨在通过动态调节信息素挥发系数、并在算法停滞时引入邻域扰动策略，以增强全局寻优能力与收敛效率。实验基于TSPLIB实例库中的典型问题，对比传统ACO、ACS、Rank-AS及ACO-VNS的性能。结果表明：ACO-VNS在解质量与收敛速度上均显著优于其他方法，且解稳定性更高。结论表明，ACO-VNS通过动态参数调整与变邻域搜索的有效结合，成功克服了传统算法易陷入局部最优和收敛速度不足的缺陷，为复杂TSP问题提供了高效解决方案。

Abstract: The Traveling Salesman Problem (TSP), a classic challenge in combinatorial optimization, plays a vital role in logistics path planning and related fields. While traditional Ant Colony Optimization (ACO) algorithms demonstrate global search capabilities, they often suffer from being prone to local optima and insufficient convergence speed. To address these limitations, this study proposes an enhanced ACO variant (ACO-VNS) that integrates variable neighborhood search (VNS). The proposed algorithm dynamically adjusts pheromone decay rates and incorporates neighborhood disturbance strategies during stagnation phases, thereby improving global optimization capabilities and convergence efficiency. Experimental results based on typical problems from the TSPLIB benchmark demonstrate that ACO-VNS significantly outperforms conventional methods like ACO, Ant Colony Search (ACS), Rank-AS, and ACO-VNS in both solution quality and convergence speed, with superior solution stability. The conclusions indicate that ACO-VNS effectively overcomes traditional algorithms' limitations of local optima trapping and insufficient convergence through dynamic parameter adjustments combined with variable neighborhood search, providing an efficient solution for complex TSP problems.