GES-TSP: 面向TSP的图边稀疏化

# GES-TSP：面向TSP的图边稀疏化方法
来源：https://arxiv.org/html/2607.09708
田峰 陈 兰州大学数学与统计学院 chentf2025@lzu\.edu\.cn&李贤月\* 兰州大学数学与统计学院 lixianyue@lzu\.edu\.cn

###### 摘要

精确求解大规模旅行商问题（TSP）计算开销极大。研究者常采用图稀疏化方法以提高计算效率。传统的稀疏化方法通常依赖固定启发式规则，未能充分利用实例特有的结构信息。本文提出一种面向欧几里得TSP的基于学习的稀疏化方法——图边稀疏化（GES）。通过融合几何结构信息与组合优化技术，该方法能针对不同实例自适应地生成稀疏图，显著减小图规模并加速求解过程。实验结果表明，在MATILDA数据集上，我们的稀疏化方法可剪除高达95%的边，同时将解与最优值的差距控制在1%以内。此外，该方法在TSPLIB基准上展现出强大的泛化能力。在部分大规模实例中，剪枝率超过99%，而最优性差距仍低于1%。

## 1 引言

旅行商问题（TSP）是一个经典的NP难组合优化问题Jünger 等 (1995 (https://arxiv.org/html/2607.09708#bib.bib1))。精确方法计算代价高昂，且求解大规模实例通常需要大量时间。作为组合优化中的基本基准问题，欧几里得TSP因其在交通规划、电路设计和路由系统中的广泛应用而受到大量研究。因此，提高欧几里得TSP实例的求解效率具有重要的理论和实践意义。特别地，欧几里得TSP通常建模于完全图之上，其边数随节点数呈二次增长，导致精确求解器或高质量近似求解器在计算上带来显著开销。

图稀疏化 Spielman 和 Teng (2011 (https://arxiv.org/html/2607.09708#bib.bib2)) 是一种广泛使用的策略，通过将搜索空间限制在候选边子集来降低TSP实例的计算复杂度。传统方法主要基于几何启发式，它们在构建稀疏图时并未利用实例特有信息。

最常用的稀疏化技术之一是 kk 近邻（KNN）图 De Berg 等 (2008 (https://arxiv.org/html/2607.09708#bib.bib3))，其中每个节点连接到欧几里得距离最近的 kk 个邻居。另一种广泛采用的稀疏化方法是德劳内三角剖分 Xu 等 (2020 (https://arxiv.org/html/2607.09708#bib.bib4))，它通过最大化所有三角形的最小角来构建平面图。德劳内图具有强大的几何性质，已知在实际中包含了欧几里得TSP最优巡游中的许多边。然而，尽管与KNN图相比提供了结构更优的稀疏化，它在某些分布下仍可能包含冗余边或遗漏与问题相关的结构。

近年来，已有针对TSP的基于学习的端到端方法被提出 Bresson 和 Laurent (2021 (https://arxiv.org/html/2607.09708#bib.bib9))； Joshi 等 (2019 (https://arxiv.org/html/2607.09708#bib.bib7))； Vinyals 等 (2015 (https://arxiv.org/html/2607.09708#bib.bib5))； Bello 等 (2016 (https://arxiv.org/html/2607.09708#bib.bib8))； Kwon 等 (2020 (https://arxiv.org/html/2607.09708#bib.bib6))。这些方法直接学习从数据中构建巡游，典型地采用序列模型或基于注意力的架构。然而，它们通常泛化能力有限，并且模型架构复杂、参数众多。

近期研究探索了基于学习的图稀疏化方法。这些方法不是直接构建巡游，而是旨在识别可能出现在高质量解中的有希望边子集。特别地，图神经网络（GNNs）能够利用节点和边特征来预测边的重要性，从而构建稀疏图，在保持解质量的同时显著降低计算复杂度。

## 2 相关工作

Fitzpatrick 等 Fitzpatrick 等 (2021 (https://arxiv.org/html/2607.09708#bib.bib10)) 提出了一种基于学习的方法，将TSP稀疏化问题重新表述为二分类任务，目标是保留那些很可能出现在最优巡游中的边。他们提取了多种边特征来刻画图的几何和结构性质。基于这些特征，他们使用传统机器学习模型（如逻辑回归和支持向量机）来预测边的重要性，通常将问题建模为二分类问题。Xin 等 Xin 等 (2021 (https://arxiv.org/html/2607.09708#bib.bib11)) 提出了稀疏图网络（SGN）框架，用于构建稀疏候选边集以改进 Lin-Kernighan-Helsgaun（LKH）启发式算法。他们使用节点坐标作为节点特征，欧几里得距离作为边特征。基于这些输入，他们使用所提出的 SGN 来预测边得分。然后，对于每个节点，仅保留得分最高的前 kk 条边以构建候选边集。Tian 等 Tian 等 (2024 (https://arxiv.org/html/2607.09708#bib.bib12)) 也使用 GNNs 进行图稀疏化，但其方法主要关注顶点覆盖和最大独立集问题。然而，这些方法要么泛化能力有限，要么未能充分利用图的结构信息。

本文中，我们提出 GES，一种基于学习的稀疏化方法，能够有效捕捉结构信息和实例特有的图数据，并融合组合优化技术以提高效率和解质量。

## 3 预备知识

### 3.1 TSP 与图稀疏化

TSP 寻求一条访问每个顶点恰好一次并返回起点的最短巡游。给定一个带权图 G=\(V,E\)G=\(V,E\)，目标是找到一个总代价最小的哈密顿环，其中每条边 \(i,j\)\(i,j\) 关联一个代价 cijc_{ij}。

在本工作中，我们关注欧几里得 TSP（ETSP），其中每个顶点 i∈Vi\in V 嵌入于二维坐标 pi=\(xi,yi\)p_{i}=\(x_{i},y_{i}\)，边代价定义为两点间的欧几里得距离。

由于欧几里得 TSP 定义在完全图上，随着顶点数量增长，边数迅速增加。因此，使用精确求解器求解最优解在计算上可能非常昂贵，特别是对于大规模实例。这促使我们采用图稀疏化技术来减小问题规模，同时保持解质量。

图稀疏化 Hashemi 等 (2024 (https://arxiv.org/html/2607.09708#bib.bib13)) 从图 GG 中选择现有边，并输出 G′G^{\prime}=\(V,E′\)\(V,E^{\prime}\)，其中 E′E^{\prime} 是 EE 的子集。我们的目标是在尽可能减少图中边数的同时，保留高质量的 TSP 解。

### 3.2 GNNs

图神经网络（GNNs）广泛用于图结构数据的学习 Scarselli 等 (2008 (https://arxiv.org/html/2607.09708#bib.bib14))； Hu 等 (2020 (https://arxiv.org/html/2607.09708#bib.bib20))。典型的 GNNs 通过迭代消息传递更新节点表示，其中每个节点从其邻居聚合信息。

在众多 GNNs 架构中，本文采用图注意力网络（GAT）Velickovic 等 (2018 (https://arxiv.org/html/2607.09708#bib.bib15))，它利用注意力机制自适应地学习邻居节点的重要性。对于节点 vv 及其邻居 u∈N\(v\)u\in\mathcal{N}\(v\)，注意力系数计算如下：

evu=LeakyReLU\(a⊤\[Whv‖Whu‖Wervu\]\)，e_{vu}=\text{LeakyReLU}\left(\mathbf{a}^{\top}[\mathbf{W}\mathbf{h}_{v}\|\mathbf{W}\mathbf{h}_{u}\|\mathbf{W}_{e}\mathbf{r}_{vu}]\right)，\(1\)其中 hv\(l\)\mathbf{h}_{v}^{(l)} 表示节点 vv 的嵌入，N\(v\)\mathcal{N}\(v\) 表示其邻居集合，W\mathbf{W} 和 We\mathbf{W}_{e} 是可学习权重矩阵，a\mathbf{a} 是注意力向量，rvu\mathbf{r}_{vu} 表示边特征，∥\| 表示拼接。然后使用归一化的注意力系数来聚合邻居信息：

hv′=σ\(∑u∈N\(v\)αvuWhu\)。\mathbf{h}_{v}^{\prime}=\sigma\left(\sum_{u\in\mathcal{N}\(v\)}\alpha_{vu}\mathbf{W}\mathbf{h}_{u}\right)。\(2\)
与传统 GNNs 相比，GAT 能更好地捕捉不同邻居的相对重要性，因此特别适用于 TSP 等图优化问题。

### 3.3 德劳内三角剖分

德劳内三角剖分是计算几何中的基本结构，为平面上的点集提供了一种稀疏图表示。给定 R2\mathbb{R}^{2} 中的一组点，德劳内三角剖分构建一个三角剖分，使得任何点都不位于任何三角形外接圆的内部。

德劳内三角剖分的一个重要性质是它保留了点之间的邻近关系，并包含了许多可能出现在最优欧几里得 TSP 巡游中的边 Xu 等 (2020 (https://arxiv.org/html/2607.09708#bib.bib4))。此外，德劳内三角剖分中的边数与顶点数呈线性关系，即 O\(n\)\mathcal{O}\(n\)，远小于完全图的 O\(n2\)\mathcal{O}\(n^{2}\) 条边。

### 3.4 Christofides 算法

Christofides 算法 Christofides (2022 (https://arxiv.org/html/2607.09708#bib.bib17)) 是一种经典的 TSP 近似算法，最坏情况近似比为 3/23/2。它首先计算最小生成树（MST），即一个连接所有顶点且总边权最小的连通子图。然后，在 MST 的奇数度顶点上构造一个最小权完美匹配，其中每个选定顶点恰好被匹配一次，且匹配总代价最小。通过合并 MST 和匹配边，得到一个欧拉图，即包含一条恰好遍历每条边一次的闭合迹的图。最后，对欧拉巡游中的重复顶点进行捷径操作，产生一个哈密顿环。所得巡游满足 c\(C\)≤32c\(OPT\)c\(C\)\leq\frac{3}{2}c(\mathrm{OPT})，其中 c\(OPT\)c(\mathrm{OPT}) 表示最优巡游长度。

## 4 GES-TSP

求解 TSP 的常见方法包括精确方法、启发式方法和近似算法。精确方法通常依赖优化求解器（如 CPLEX 和 SCIP Achterberg (2009 (https://arxiv.org/html/2607.09708#bib.bib18))）来获得最优解，但计算代价高昂，难以扩展到大规模实例。与精确方法相比，启发式方法可扩展性更好，能够高效地为大规模实例生成高质量解，其中 LKH 算法 Helsgaun (2015 (https://arxiv.org/html/2607.09708#bib.bib19)) 是最有效的方法之一。近似算法提供理论上的性能保证，并能在多项式时间内计算出与最优解比值有界的解。

大多数 TSP 方法都在完全图上操作，由于 O\(n2\)\mathcal{O}\(n^{2}\) 的边数，导致显著的计算开销。这促使采用图稀疏化技术来减小问题规模。特别地，我们的 GES-TSP 提供了一种有前途的数据驱动方法，用于识别相关边并实现高效的 TSP 求解。图 1 展示了 GES-TSP 及求解框架的概览。

参见图注 图 1：GES-TSP 及求解框架概述### 4.1 粗粒度图

为了降低在完全图上求解 TSP 和训练 GNNs 模型的计算负担，我们首先基于几何结构进行粗粒度的图稀疏化。

具体来说，给定欧几里得平面上的一组点，我们构建德劳内三角剖分，它提供了一个保留顶点之间重要邻近关系的稀疏图。德劳内图包含 O\(n\)\mathcal{O}\(n\) 条边，已知保留了可能出现在高质量 TSP 巡游中的许多边。

通过利用德劳内三角剖分，我们得到一个初始稀疏图，在保留局部几何结构的同时显著减少了边数。该粗粒度图作为一个强大的候选边集，为后续使用 GNNs 进行基于学习的细化提供了更高效的输入。

### 4.2 特征构造

在获得粗粒度图后，我们为节点和边构造特征表示。节点特征定义为归一化坐标，而边特征则被精心设计以捕捉结构信息，因为 TSP 主要依赖于边的选择。

在欧几里得 TSP 中，边的代价由两节点间的欧几里得距离决定。我们直接使用该距离作为基本边特征。在最优巡游中，较短的边被选中的可能性显著更高，而较长的边很少被选择。然而，仅凭距离是不够的。它无法捕捉局部结构，在节点密度不同的区域可能效果不佳。这一局限性促使我们引入额外的特征。

我们选择 KNN 特征作为第二个边特征。对于每个节点 ii，令 Nk\(i\)\mathcal{N}_{k}\(i\) 表示其 kk 个最近邻居的集合。对于边 \(i,j\)\(i,j\)，我们定义二进制变量：

KNNij=\{1,if j∈Nk\(i\) or i∈Nk\(j\),0,otherwise。\text{KNN}_{ij}=\begin{cases}1,&\text{if }j\in\mathcal{N}_{k}\(i\)\text{ or }i\in\mathcal{N}_{k}\(j\),\\ 0,&\text{otherwise。}\end{cases}\(3\)
该特征表明两个节点是否相近，并提供局部结构信息。它有助于模型处理不同密度的区域。

虽然 KNN 特征捕捉了两个节点是否局部相近，但它仅提供二进制信号，无法反映边的相对质量。为解决此局限性，我们引入更强的局部特征。对于边 \(i,j\)\(i,j\)，它定义为

Qij=1\+dij1\+mink⁡dik。Q_{ij}=\frac{1+d_{ij}}{1+\min_{k}d_{ik}}。\(4\)
Fitzpatrick 等 Fitzpatrick 等 (2021 (https://arxiv.org/html/2607.09708#bib.bib10)) 构建了六个局部特征。在本工作中，我们将其简化为一个特征。该特征衡量了一条边相对于节点 ii 最短边的质量。值越小表示连接越优。与 KNN 特征相比，Q 值提供了更细粒度的局部边质量度量 Sun 等 (2020 (https://arxiv.org/html/2607.09708#bib.bib21))。它不仅指示两个节点是否相近，还反映了某条边相对于最佳局部选择的不利程度。这使得它在边选择时更具信息量。

最后，我们还需要全局特征来完整描述图的结构。Fitzpatrick 等 Fitzpatrick 等 (2021 (https://arxiv.org/html/2607.09708#bib.bib10)) 提出 IMST 特征。我们迭代