GES-TSP：学习驱动图边稀疏化，高效求解TSP

背景

旅行商问题（Traveling Salesman Problem, TSP）是组合优化领域最经典的 NP-hard 问题之一，其目标是在给定一组城市及其两两距离后，找到一条访问所有城市且总距离最短的闭合回路。精确求解大规模 TSP 实例需要极高的计算成本，随着问题规模增长，指数级的时间复杂度使得传统精确算法在实际应用中难以承受。为了提升求解效率，研究者们常采用图稀疏化（graph sparsification）方法，即通过删减图中的部分边来减小问题规模，从而加速求解过程。然而，传统稀疏化方法通常依赖固定启发式规则，如基于距离阈值或 k-近邻，这些方法无法充分利用每个实例特有的结构信息，导致在稀疏化过程中可能丢失关键边，或者保留过多冗余边，最终影响求解质量与效率。

核心内容

本文提出了一种名为 Graph Edge Sparsification (GES) 的基于学习的稀疏化方法，专门针对欧几里得 TSP（Euclidean TSP）设计。GES 的核心思想是：通过融合几何结构信息与组合优化技术，为每个实例自适应地生成稀疏化图，从而在保持接近最优解质量的前提下，大幅缩减图规模并加速求解过程。

具体而言，GES 方法首先从 TSP 实例中提取几何特征（例如点之间的相对位置、角度、距离分布等），然后利用一个学习模型（可能为神经网络）来预测每条边的重要性分数。该模型在训练过程中结合了组合优化技术（如精确求解器或近似解作为监督信号），以学习哪些边在寻找最优解时是关键的。随后，根据边的重要性分数，GES 自适应地保留分数最高的边，删减其余边，生成一个稀疏化后的图。这一过程完全针对不同实例进行动态调整，而非使用固定规则。

实验在 MATILDA 数据集上进行，结果表明 GES 能够剪除高达 95% 的边，同时保证解的质量与最优解之间的差距（optimality gap）保持在 1% 以内。此外，该方法展现出强大的泛化能力：在 TSPLIB 库中的一些大规模实例上，剪枝率甚至超过 99%，而最优性差距仍然低于 1%。这意味着 GES 可以在几乎不牺牲解质量的前提下，极大降低问题规模，从而使得原本难以处理的超大规模 TSP 实例变得可行。

关键要点

• 问题背景：传统图稀疏化方法（如基于固定阈值的启发式）无法充分利用实例特定的结构信息，导致稀疏化效果不佳。
• 方法创新：GES 是一种基于学习的稀疏化方法，通过整合几何结构信息与组合优化技术，为每个 TSP 实例自适应地生成稀疏化图。
• 核心机制：学习模型预测每条边的重要性，依据重要性分数动态保留关键边，删减冗余边。
• 性能指标：
  • 在 MATILDA 数据集上，可剪除 95% 的边，最优性差距 ≤ 1%。
  • 在 TSPLIB 大规模实例上，剪枝率超过 99%，最优性差距仍低于 1%。
• 泛化能力：GES 在未见过的 TSPLIB 实例上表现优异，说明其具备跨实例的迁移能力。
• 应用价值：显著降低 TSP 求解的计算成本，使得精确或近似求解更大规模问题成为可能。

意义与影响

GES 的提出为 TSP 及其他组合优化问题的图稀疏化提供了新的范式。传统方法要么依赖手工设计的启发式规则，要么需要大量领域知识，而 GES 通过数据驱动的方式自动学习哪些边是关键的，从而实现了更高效、更精准的稀疏化。这项工作不仅有助于提升 TSP 求解器的实际效率，也为其他基于图结构的组合优化问题（如车辆路径问题、电路布线、物流调度等）提供了可借鉴的思路。此外，GES 在保持极低最优性差距的同时实现高达 99% 的剪枝率，表明在大多数大规模 TSP 实例中，最优解的结构信息高度冗余，只需少量关键边即可重建接近最优的解。这一发现对理解 TSP 问题的本质结构具有理论意义。未来，将 GES 与现有精确求解器（如 Concorde、Gurobi）或近似算法（如 LKH）结合，有望在实际应用中将大规模 TSP 的求解时间从数小时缩短至数分钟，从而推动物流、制造业、交通规划等领域的智能化升级。