《Algorithms》：A New Approach to Efficiently Solving the Traveling Salesman Problem (TSP) by Combining Artificial Intelligence Techniques and Ant Colony Metaheuristics
编辑推荐：
### 摘要
完全NP（非确定性多项式）问题的高效求解，如旅行商问题（TSP），尤其针对大规模算例，至今仍是运筹学（Operations Research）与组合优化领域的主要挑战，对物流、城市规划及网络等诸多行业的企业尤为重要，这些行业每天都在努力优化路线与
### 摘要
完全NP（非确定性多项式）问题的高效求解，如旅行商问题（TSP），尤其针对大规模算例，至今仍是运筹学（Operations Research）与组合优化领域的主要挑战，对物流、城市规划及网络等诸多行业的企业尤为重要，这些行业每天都在努力优化路线与配送时间。受群体行为启发的优化方法，如蚁群优化（Ant Colony Optimization, ACO），为求解此类问题提供了具有竞争力的结果。主要难点在于算例规模，因为当规模增大时，许多现有算法无法在合理时间内收敛到优质解：执行时间通常极长，且所得解通常远非问题的最优解。本文提出了一种通过人工智能技术与蚁群理论相融合的新型元启发式算法来求解TSP的新方法。为评估该方法的有效性，特别是多蚁群优化版本2-SK（Multi-colony Ant Colony Optimization version 2-SK, MACOV2SK）方法的有效性，研究人员针对多个TSP算例进行了仿真实验，重点关注大规模算例。实验结果清楚表明，所提出的方法在执行时间和解质量方面显著优于文献中的多种其他方法，尤其针对大规模问题。
该论文发表于《Algorithms》期刊，提出了一种名为MACOV2SK的新型混合元启发式算法，用于高效求解大规模的旅行商问题（TSP）。
**研究背景与问题**
TSP是组合优化领域的经典NP-hard问题，旨在给定一组城市及城市间距离的情况下，确定访问每个城市恰好一次后返回起点的最小成本路径。该问题在物流、移动机器人、无线网络规划以及分布式系统资源管理等领域具有广泛的实际应用价值。TSP存在多种变体，包括对称TSP、非对称TSP、时间窗TSP以及随机TSP等。本研究聚焦于对称TSP，即两城市间距离在双向一致的版本，该变体在基于欧几里得距离或无线电距离的无线网络等实际系统中尤为常见，且为大规模算法设计提供了更为稳定的数学结构。
随着问题实例规模的快速增长，现有方法面临显著局限：一方面，旨在降低计算复杂度的简化搜索空间方法往往导致解质量次优；另一方面，能够接近最优解的高级ACO变体或Lin-Kernighan（LK）型启发式算法需要大量计算资源，且在城市数量极高时难以收敛。这种速度和质量之间的二元对立，对同时要求可扩展性和精确性的应用构成了重大挑战。现有基于聚类与启发式混合的方法虽能降低组合复杂度，但在合并阶段常因处理不当而导致最优性损失；基于机器学习的方法虽具前景，却需要大量硬件资源进行模型训练，且现代方法在解质量与时间复杂度之间仍面临权衡。
**研究内容、结论与意义**
研究人员提出了一种混合方法，结合K均值（K-means）聚类算法与新型多蚁群优化版本（Multi-Ant Colony Optimization version 2, MACOV2）来求解TSP，特别是大规模实例。该方法首先利用K-means将空间高效划分为相干子区域，随后多个蚁群并行工作探索这些子区域并局部优化路径，最后通过全局合并与改进策略确保最终路径的一致性和最优性。MACOV2SK作为MACOV2与K-means（SK）的结合体，针对传统MACO在大规模实例中停滞的问题，通过聚类分解降低复杂度，采用边缘重组交叉（Edge Recombination Crossover, ERX）算子保留边连接信息，并基于K-OPT（K-optimal）改进启发式优化簇间合并过程，提供了一种无需训练、资源消耗较低的轻量级替代方案。
实验结果表明，MACOV2SK在解质量和执行时间方面均显著优于MACO、SFLA（Shuffled Frog Leaping Algorithm）、AACO-NC以及K-EACO等文献中的近期算法，尤其针对大规模问题展现出优越的准确性和可扩展性。Wilcoxon秩和检验进一步验证了MACOV2SK相对于对比算法的统计显著性优势。
**主要关键技术方法**
样本队列来源于TSPLIB95在线实例库中的标准TSP测试实例，涵盖小规模、中等规模及大规模算例。方法层面，首先采用K-means无监督聚类算法，通过肘部法则（Elbow Method）确定最优簇数K，将大规模TSP分解为若干子问题；其次，在每个簇内应用改进的MACOV2启发式算法，该算法以经典MACO为基础，引入遗传算法中的ERX交叉算子替代原有的随机搜索机制，以增强解空间多样性和搜索引导能力；随后，将各簇最优解按照簇中心构成的TSP解确定的访问顺序进行智能合并，采用最近点识别、边断裂与重连接技术，并运用3-OPT局部搜索启发式对簇边界连接进行再优化；最后，通过Python 3.12.12及Sklearn库实现算法，并与文献算法进行系统的对比实验与统计检验。
**研究结果**
MACO算法步骤：该部分详细介绍了MACO的算法框架，包括初始化阶段（蚁群置于各城市顶点、全局信息素矩阵初始化为零、首趟巡游后由最优解初始化信息素）、路径构造阶段（基于概率转移规则选择下一城市、利用禁忌列表taboo list防止重复访问、各蚁群配备全局记忆替代个体蚂蚁的局部记忆）以及信息素矩阵更新阶段（信息素强度变量τ
ij(t)的演化遵循特定概率公式与更新规则，α和β参数用于调节信息素与可见度的相对重要性）。
MACOV2改进算法：该部分阐述了MACOV2对MACO的核心改进。MACOV2以ERX交叉算子替代MACO原有的随机盲目搜索成分，通过综合最优解特征来指导搜索、发现解空间中的有前景后代，从而显著改善解空间多样性、降低早熟收敛风险及局部最优陷阱。与MACO相比，MACOV2在保持几乎相同解质量的同时，显著改善了执行时间，对各类规模实例均展现出更高效的性能。
K-means算法在TSP中的应用：该部分介绍了基于scikit-learn库实现的K-means聚类，采用肘部法则确定最优K值。选择K-means的理由在于其平均复杂度O(n)优于层次聚类的O(n
2)，且能产生更紧凑平衡的簇结构以利于局部求解。肘部法则虽存在视觉主观性缺陷，但快速直观，适用于TSP等大数据集。
K对MACOV2SK解的影响：该部分分析了簇数K对解的影响规律。执行时间随K值增加而总体上升但单簇计算时间下降；解质量方面，K过小导致欠分割损失信息，K过大则产生过拟合使各点几乎自成一簇，存在使整体解显著恶化的碎片化阈值。
混合方案实现（MACOV2SK）：该部分详述了三阶段混合架构。第一阶段，采用O(k·n·T)复杂度的K-means将N规模问题分解为K个子问题，肘部法则通过计算不同K值下的WCSS（Within-Cluster Sum of Squares，簇内平方和）确定最优聚类数；第二阶段，以伪并行方式用MACOV2求解各簇，复杂度为O(k·n·m)；第三阶段，先以簇中心为节点求解TSP获得簇访问顺序，再通过最近点识别、边断裂重连接技术合并路径，最后用K-OPT（K=3）启发式优化边界连接，该阶段复杂度为O(k·n·T)。
实验结果分析：该部分展示了与MACO、AACO-NC、STION、K-EACO及ACO-ML等算法的全面对比。MACOV2SK在所有12个实例上均优于AACO-NC（p值=0.00034），在所有测试实例上均优于或持平于MACO（p值=0.00048）。与K-EACO相比，11/11的情况下MACOV2SK执行时间更短。与SFLA、ACO-ML等方法相比，MACOV2SK在大规模实例上展现出更优的执行时间和解质量。参数敏感性分析显示，α<0.5时收敛过快但解质量不佳，α>1.5时类似；β<0.5时收敛缓慢，β过大时解质量下降且算法不稳定。
**讨论总结、研究结论翻译**
研究人员在讨论中指出，MACOV2SK的优越性基于四个关键点：第一，K-means分解显著缩减了搜索空间，使蚁群得以快速收敛至高质量局部解；第二，ERX交叉算子通过组合蚂蚁发现的最优解产生杂交后代，加速全局最优的发现；第三，智能合并策略优化了簇间连接点的处理；第四，相较于机器学习方法，MACOV2SK无需训练即可保证良好性能。与SFLA、K-EACO等聚类蚁群混合方法相比，MACOV2SK在解质量和执行时间上的综合优势更为显著。
**研究结论**
本文提出了针对大规模TSP求解的新方法，将人工智能方法（K-means）与蚁群元启发式算法相结合。研究的各项贡献在TSPLIB标准实例上进行了测试，并与文献中的近期方法（MACO、SFLA、AACO-NC和K-EACO）进行了比较。结果清楚证明了本文方法的有效性，特别是MACOV2SK方法，其突出特点在于能够在较短时间内求解大规模实例。与MACO、SFLA、AACO和K-EACO方法相比，MACOV2SK在求解时间和解质量方面均表现出良好性能，且具有更优的平均误差。未来工作将致力于将MACOV2SK方法应用于其他问题类别，如车辆路径问题（Vehicle Routing Problem, VRP）或多旅行商问题（Multi-Traffic Problem, MTSP）。
