🤖 AI

GES-TSP: Graph Edge Sparsification for TSP

本文介绍了 GES，一种针对欧几里得旅行商问题（TSP）的学习型图边稀疏化方法，该方法能够自适应地将图规模缩减高达 99%，同时将最优性差距维持在 1% 以下，从而显著加速大规模实例的求解。

原作者： Tianfeng Chen, Xianyue Li

发布于 2026-07-14

📖 1 分钟阅读☕ 轻松阅读

原作者： Tianfeng Chen, Xianyue Li

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你是一名快递员，手里拿着一张完整的城市地图，你的老板对你说：“去访问每一户人家且仅访问一次，最后回到家，但要尽可能快地完成。”这就是旅行商问题（Traveling Salesman Problem, TSP）。现在，想象这张地图不仅仅是一份房屋清单；它是一个巨大的网络，每一户人家与其他任何一户人家之间都由一条直达道路连接。如果你有 1,000 户人家，那就有近百万条道路需要检查！在这么大的地图上寻找完美路线，就像是在蒙着眼睛于沙漠中寻找一颗特定的沙粒——这既耗时又极其昂贵。

长期以来，人们试图通过使用“固定规则”来解决这个问题，比如总是选择最近的邻居，或者在点之间画三角形。这有点像在说：“我只看离我最近的三户人家，”或者“我只看那些构成完美三角形的房子。”本文的作者 Tianfeng Chen 和 Xianyue Li 指出，这些旧规则过于僵化。它们没有注意到这个特定城市的独特特征。它们可能会错过某个捷径，或者包含了一条实际上是死胡同的道路。

核心思想：一个智能过滤器
作者提出了一种名为 GES-TSP（图边稀疏化）的新技巧。把它想象成雇佣了一名超级聪明的、由人工智能驱动的侦察兵，他观察整个混乱的道路网并说道：“嘿，95% 的这些道路对于最佳路线来说都是没用的。让我们把它们扔掉，只保留最有希望的那些。”

以下是他们的“侦察兵”工作的具体步骤：

草稿阶段（粗糙图）： 首先，侦察兵使用一种经典的几何技巧，称为“德洛内三角剖分”（Delaunay triangulation）。想象一下在纸上连接点，使得任何你画出的三角形内部都没有点。这能瞬间切掉一大块疯狂的长距离道路，留下一个更小、更整洁的网络。这是一个好的开始，但并不完美。
智能大脑（GNN）： 接下来，他们将这个较小的网络输入到一个“图神经网络”（GNN）中。你可以把这看作是一个学习过数千条以往配送路线的学生。学生观察道路，并针对每条路提出四个具体问题：
- 这条路有多长？（短的通常更好）。
- 这两户人家是邻居吗？（它们是否靠近？）。
- 这条路与离开该房屋的最佳道路相比如何？（它是一个“好”选择还是“坏”选择？）。
- 大局观如何？（这条路是否符合城市的整体结构？）。
评分卡： 基于这些问题，AI 会给每条路打分。高分意味着“保留此路！”；低分意味着“丢弃它！”
安全网： 为了确保他们不会意外丢弃连接两个城市部分的唯一道路，他们添加了一些通过名为“Christofides”的传统算法找到的特定道路。这保证了始终存在一条有效的路径。

结果：剔除冗余
当他们在 MATILDA 数据集（一个包含 100 户人家的城市地图集合）上进行测试时，结果令人印象深刻。他们的方法成功剔除了 95% 的道路！这意味着计算机不再需要检查一百万个连接，而只需检查大约 5 万个。更棒的是，他们找到的路线仍然与完美路线非常接近——通常在最佳答案的 1% 误差范围内。

他们还在 TSPLIB 基准测试上进行了测试，其中包括拥有多达 2,392 户人家的更大城市。在这些巨大的地图上，该方法表现得更加激进，剔除了超过 99% 的道路，同时仍将解的差距保持在 1% 以下。

他们拒绝了什么，接受了什么
作者非常明确地指出哪些做法效果不够好。他们明确反对仅仅依赖固定的几何规则（例如仅仅挑选最近的邻居），因为这些方法忽略了每张地图特有的“个性”。他们还指出，虽然其他一些 AI 方法试图从头开始构建整个路线，但那些方法往往难以泛化（无法在新的、未见过的地图上表现良好）或者过于复杂。他们的方法与众不同：他们不构建路线，而是清理地图，以便标准的求解器能更快地找到路线。

他们有多确定？
作者对他们的数字非常有信心，因为他们运行了实际的实验。他们并没有凭空猜测，而是直接在真实数据集（MAT-ILDA 和 TSPLIB）上运行了其方法，并直接与 SGN 和 Fitzpatrick 等其他方法进行了对比。

在 MATILDA 上： 他们的算法始终具有最小的误差率（最优性间隙）和最高的道路削减率（剪枝率）。
在 TSPLIB 上： 他们展示了随着城市规模变大，他们的方法在不损失准确性的情况下，在削减道路方面变得更加高效。
速度： 由于移除了这么多道路，计算机求解问题的速度也大大加快。在测试中，他们的方法是其中最快的。

他们还进行了一个“假设”测试（消融研究），即移除系统中的某些部分。当他们拿掉“德洛内”草稿时，性能下降了。当他们拿掉“智能问题”（特征）时，性能也下降了。这证明了他们系统的每一个部分都在发挥重要作用。

底线
论文表明，通过将传统的几何学与能够理解问题特定形状的现代学习型 AI 相结合，你可以让解决这些大规模配送难题变得更快、更容易。他们并没有“永久解决”旅行商问题（这仍然是一个很难啃的硬骨头！），但他们展示了一种非常有效的方法，可以将问题缩小到易于处理的程度，即使是对于巨大的城市也是如此。目前他们仅专注于这些特定类型的地图（欧几里得 TSP），尚未尝试将其应用于其他类型的谜题，但目前的成果非常令人期待。

技术摘要：GES-TSP：用于 TSP 的图边稀疏化

问题陈述
旅行商问题（TSP），特别是欧几里得变体（ETSP），是一个经典的 NP 难组合优化问题。虽然精确算法（如 CPLEX、SCIP）可以求解到最优解，但由于完全图表述中边的二次增长（ $O(n^2)$ ），在处理大规模实例时计算成本会变得极高。传统的图稀疏化技术，如 $k$ -最近邻（KNN）图和 Delaunay 三角剖分，利用固定的几何启发式方法来缩小搜索空间。然而，这些方法往往无法充分利用特定实例的结构信息，导致产生冗余边或遗漏关键的特定问题结构。相反，近期的端到端学习型 TSP 求解器通常面临泛化能力有限和架构复杂的问题。本文解决的核心挑战是如何自适应地生成一个稀疏图，在显著降低计算开销的同时，保持高质量的解并维持对不同实例分布的强泛化能力。

方法论
作者提出了 GES-TSP（用于 TSP 的图边稀疏化），这是一个将几何结构与图神经网络（GNN）相结合以识别潜在边的学习框架。该方法通过四个关键阶段进行：

粗略图构建： 为了减轻在完全图上训练的计算负担，该方法首先使用 Delaunay 三角剖分 构建一个粗略的稀疏图。这种几何结构保留了局部邻近关系，并包含 $O(n)$ 条边，作为一个强大的初始候选集，其规模显著小于完全图。
特征构建： 模型为每条边 $(i, j)$ $(i, j)$ 使用四维特征向量：
- 欧几里得距离 ( $d_{ij}$ )： 基础成本度量。
- KNN 指标 ( $KNN_{ij}$ )： 一个二进制特征，指示节点是否为相互的 $k$ -最近邻，用于捕捉局部密度。
- Q 值 ( $Q_{ij}$ )： 一种归一化指标，通过比较边的长度与连接节点 $i$ 的最短边，提供比二进制 KNN 更细粒度的局部边质量度量。
- IMST（迭代最小生成树）： 通过迭代计算并移除 MST 得到的全局特征，经过归一化处理以确保在不同图规模下的尺度不变性。
GNN 推理： 采用 图注意力网络（GAT） 来预测边的重要性。模型使用注意力机制聚合邻居信息，结合节点嵌入和上述边特征。输出是每条边的得分，作为二分类任务（边是否包含在最优路径中）进行训练，并使用带有类别不平衡权重的二元交叉熵损失函数。
稀疏图生成与求解： 根据得分阈值对边进行过滤。至关重要的是，为了保证存在可行解，Christofides 算法 的解中的边会被强制包含在稀疏图中。这确保了连通性以及至少存在一个有效的哈密顿回路。生成的稀疏图随后被传递给精确求解器（SCIP）以计算最终路径。

核心贡献

混合框架： 本文引入了一种新颖的方法，将确定性几何启发式算法（Delaunay 三角剖分、Christofides）与数据驱动的学习（GAT）相结合，构建了一个鲁棒的稀疏化流水线。
自适应特征工程： 作者提出了一套特定的边特征，包括 Q 值和归一化 IMST，旨在有效捕捉局部结构质量和全局图属性。
可行性保证： 不同于一些可能导致图不连通的基于学习的剪枝方法，GES-TSP 通过集成 Christofides 边，从数学上保证了剪枝后的图仍然是可解的。
泛化能力： 该方法展示了强大的泛化能力，在无需针对特定实例规模重新训练的情况下，在合成的 MATILDA 数据集和真实的 TSPLIB 基准测试集上均表现出色。

实验结果
实验在 MATILDA 数据集（各种分布的 100 节点实例）和 TSPLIB 基准测试（实例规模从 130 到 2392 节点不等）上进行。

剪枝率： 与基准方法（SGN 和 Fitzpatrick 等）相比，GES-TSP 实现了显著更高的边剪枝率。在 MATILDA 数据集上，它最多可剪枝 94% 的边。在大型 TSPLIB 实例（如 pcb1002、vm1748、pr2392）上，剪枝率超过 99%。
解质量： 尽管进行了激进的剪枝，该方法仍保持了极小的最优性差距（optimality gap）。在 MATILDA 上，平均差距为 0.10%（对比 SGN 的 0.68% 和 Fitzpatrick 的 0.17%）。在 TSPLIB 上，即使对于最大的实例，差距也保持在 1% 以下。
效率： 高剪枝率转化为显著的加速。GES-TSP 在求解时间上持续优于基准方法，证明了缩减后的图规模允许精确求解器运行得更快。
消融实验： 移除 Delaunay 粗略过滤器或将其替换为 KNN 会使剪枝率降低约 3–5%。特征消融证实了 KNN 和 IMST 特征是最具影响力的，而 Q 值和距离特征提供了必要的精细化调整。

意义与主张
本文声称 GES-TSP 为将精确 TSP 求解器扩展到大规模实例提供了一种切实有效的解决方案。通过将图规模缩减 95% 以上（在某些情况下甚至达到 99%），同时将解的差距控制在 1% 以内，该方法弥合了启发式算法的可扩展性与精确算法的最优性保证之间的鸿沟。作者强调，他们的方法成功利用了几何结构信息来引导学习，从而产生了一个在不同数据分布和问题规模下具有良好泛化能力的系统。这项工作凸显了将几何启发式算法与图神经网络相结合用于组合优化的潜力，尽管作者也谦虚地指出，目前的框架仅限于 TSP，尚未扩展到其他组合优化问题。

技术摘要：GES-TSP：用于 TSP 的图边稀疏化

类似论文