⚛️ quantum physics

Traveling Salesman Problem with a preprocessing method for classical and quantum optimization

本文提出了一种通过限制候选弧并仅保留每个顶点最低成本邻居来显著缩减优化模型规模的预处理策略，该策略在经典和量子优化方法中均有效降低了决策变量数量、缩短了计算时间并缩小了最优性间隙，从而提升了旅行商问题求解的可扩展性。

原作者： Alessia Ciacco, Luigi Di Puglia Pugliese, Francesca Guerriero

发布于 2026-03-25

📖 1 分钟阅读🧠 深度阅读

原作者： Alessia Ciacco, Luigi Di Puglia Pugliese, Francesca Guerriero

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

这篇论文讲述了一个关于**“如何更聪明地规划旅行路线”**的故事，特别是针对那些既想用传统电脑算，又想尝试最新“量子电脑”算的科学家们。

我们可以把这篇论文的核心内容想象成**“给旅行规划师做减法”**。

1. 核心难题：贪心的旅行推销员

想象一下，你是一名旅行推销员，手里有一张地图，上面有几十个城市。你的任务是：不重复地访问每一个城市，最后回到起点，并且走的总路程最短。

这就是著名的“旅行商问题”（TSP）。

难点在哪里？ 城市越多，可能的路线组合就像爆炸一样呈指数级增长。
- 如果有 5 个城市，路线还不多；
- 如果有 20 个城市，路线数量就比全宇宙的原子数还多！
目前的困境： 传统的电脑（经典优化）算起来很慢；而新兴的“量子电脑”（Quantum Annealing）虽然理论上很快，但它的“内存”（量子比特）非常有限，根本装不下这么多复杂的路线选项。这就好比你想用一个小背包去装一座山的石头，根本装不下。

2. 论文提出的妙招：CAF（成本过滤法）

作者提出了一种**“预处理”**方法，叫 CAF（基于成本的弧过滤）。

🌰 生活中的类比：
想象你要去拜访 100 个朋友。

传统做法： 你手里拿着电话簿，觉得“也许我该去拜访住在地球另一端的朋友”，于是你把所有 100 个朋友之间的连线（路线）都列出来，试图找出最短路径。这会让你的大脑（或电脑）累死。
CAF 的做法： 你运用常识：“我肯定更倾向于去离我最近的 50 个朋友家，而不是去那些需要坐飞机跨越半个地球的朋友家。”
- 于是，你直接扔掉了那些“长途”路线，只保留了每个城市最近的一半邻居。
- 关键承诺： 作者通过数学证明（引用了一个叫狄拉克定理的古老数学结论），保证即使你扔掉了那些“长途”路线，依然能拼出一条完美的、不重复的旅行路线。你并没有把路堵死，只是把路变窄了，但好路还在。

3. 这个方法有什么用？

A. 对传统电脑（经典优化）：跑得更快

效果： 通过只保留“最近的一半邻居”，他们把需要计算的变量（路线选项）减少了大约 30%。
比喻： 就像你原本要在一个巨大的迷宫里找出口，现在有人帮你把那些明显是死胡同的墙拆掉了。虽然迷宫还是很大，但你只需要探索更小的区域，计算时间直接缩短了一半，而且找到的路线依然和原来一样好（甚至更好）。

B. 对量子电脑（量子优化）：终于能“跑”起来了

这是这篇论文最亮眼的地方。

现状： 量子电脑很娇贵，现在的硬件只能处理非常小的问题（比如只有几个城市）。如果城市多了，量子电脑就“死机”了，因为它处理不了那么多变量。
突破： 用了 CAF 方法后，问题变小了。作者成功用混合量子算法解决了15 个城市的问题。
比喻： 以前量子电脑只能玩“贪吃蛇”的小游戏，因为屏幕太小。CAF 方法相当于把游戏地图缩小了一半，让量子电脑终于能在它的“小屏幕”上玩起稍微复杂一点的“俄罗斯方块”了。
结果： 在量子计算中，这种方法不仅让问题变得可解，还让找到的路线更接近最优解（误差更小），速度也更快。

4. 总结：为什么这很重要？

这篇论文并没有发明一种新的“超级算法”来直接解决所有问题，而是发明了一个**“过滤器”**。

对于经典世界： 它是一个高效的**“减负工具”**，让现有的电脑算得更快。
对于量子世界： 它是一个**“桥梁”**。因为现在的量子电脑还不够强大（硬件限制），这个预处理方法把巨大的问题“压缩”成量子电脑能消化的大小。

一句话总结：
作者告诉我们要想走得快（无论是用旧电脑还是新量子电脑），不要试图一次性看完所有的路，而是先聪明地扔掉那些明显不靠谱的远路，只专注于那些最有可能成功的近路。这样，无论是现在的电脑还是未来的量子电脑，都能更轻松地找到最佳路线。

论文技术总结：带有预处理方法的旅行商问题（TSP）经典与量子优化研究

1. 研究背景与问题定义

旅行商问题（TSP） 是运筹学中最经典的组合优化问题之一，旨在寻找访问每个城市恰好一次并返回起点的最短路径。该问题被证明是 NP-hard 的，随着城市数量（ $n$ ）的增加，搜索空间呈指数级增长。

核心挑战：传统的 TSP 数学模型（如整数线性规划 ILP）包含大量的决策变量（弧的数量为 $n(n-1)$ ）和复杂的子回路消除约束（Subtour Elimination Constraints）。
量子计算的局限性：虽然量子退火（Quantum Annealing, QA）和混合量子 - 经典优化为解决此类问题提供了新视角，但受限于当前量子硬件的连通性、嵌入需求及变量数量限制，现有的量子方法通常只能处理极小规模或人工生成的 TSP 实例，难以应对实际基准测试集（如 TSPLIB）中的中等规模问题。

2. 方法论：基于成本的弧过滤（CAF）

本文提出了一种名为 基于成本的弧过滤（Cost-Based Arc Filtering, CAF） 的预处理策略，旨在在保持问题可行性的前提下，显著缩小优化模型的规模。

2.1 核心思想

策略：对于图中的每个顶点 $i$ ，仅保留与其相连的 $k$ 个成本最低的邻居节点对应的弧，剔除长距离连接。
参数设定：设定 $k = \lceil n/2 \rceil$ （即保留每个节点的一半邻居）。
理论依据：基于图论中的 Dirac 定理。该定理指出，若一个无向图中每个顶点的度数至少为 $n/2$ $n /2$ ，则该图包含哈密顿回路。
- 可行性保证：通过保留每个节点度数至少为 $\lceil n/2 \rceil$ 的弧，预处理后的图 $G'$ 在理论上仍保证至少存在一条哈密顿回路，从而确保优化问题的可行性不被破坏。

2.2 算法流程

输入城市集合 $V$ 和成本矩阵 $C$ 。
计算 $k = \lceil n/2 \rceil$ 。
对每个顶点 $i$ ，将其余顶点按距离 $c_{ij}$ 升序排列。
仅选取前 $k$ 个顶点，构建新的候选弧集合 $\tilde{A}$ 。
在缩减后的图 $\tilde{G}=(V, \tilde{A})$ 上重新构建 TSP 模型。

2.3 优化动机

在欧几里得 TSP 实例中，最优解通常由连接邻近城市的短弧组成，长距离连接极少出现在最优路径中。CAF 利用这一几何特性，通过剔除长距离弧来集中搜索空间，同时大幅减少决策变量数量。

3. 实验设置

数据集：使用 TSPLIB 中的标准基准实例（基于 berlin52.tsp 生成的不同规模实例，顶点数 $V$ 从 5 到 50）。
求解器：
- 经典优化：Gurobi Optimizer 11.0.1（用于验证最优性和计算时间）。
- 量子/混合优化：D-Wave Leap 混合求解器（Constrained Quadratic Model, CQM），运行在 Advantage2_system1.4 量子处理单元上。
对比组：
1. 原始完整模型（无 CAF）。
2. 经过 CAF 预处理后的缩减模型。

4. 关键实验结果

4.1 模型规模缩减（变量数量）

变量减少：CAF 预处理将决策变量数量减少了约 30%。
趋势：随着顶点数 $V$ 的增加，变量减少的绝对值和比例均呈上升趋势。例如，在 $V=50$ 时，变量从 2450 个减少到 1652 个（减少 33%）。
意义：显著降低了搜索空间的复杂度，使模型更紧凑。

4.2 经典优化性能（Gurobi）

最优性保持：在 $V \le 20$ 的实例中，CAF 模型与原始模型均能找到相同的最优解（Gap = 0%），证明预处理未丢失最优解。
计算时间：
- 对于中等规模实例（ $V \ge 10$ ），CAF 显著缩短了求解时间。
- 例如， $V=19$ 时，求解时间从 257.61 秒降至 139.12 秒（减少约 46%）； $V=20$ 时，时间减少超过 50%。
- 在 $V=21$ 时，原始模型在 300 秒限制内无法收敛（Gap 无限大），而 CAF 模型虽然也未证明最优性，但找到了更优的可行解（目标值更低）。

4.3 量子混合求解器性能（D-Wave）

可扩展性突破：得益于变量减少，该方法成功在量子框架下求解了 $V=15$ 的实例，这超出了当前大多数量子 TSP 研究能处理的规模（通常局限于极小实例）。
解的质量（Gap）：
- 对于 $V \le 11$ 的实例，两种方法均能 100% 找到最优解。
- 随着规模增大，CAF 的优势明显。例如在 $V=13$ 时，未预处理模型的 Gap 高达 43%，而 CAF 模型将其降至 11%。
- 整体平均 Gap 降低了约 29-31%。
求解效率：CAF 模型的平均求解时间减少了约 5-17%（取决于实例规模），表明更紧凑的模型在量子硬件上执行更高效。
成功率：在 $V=15$ 时，CAF 模型在 10 秒限制内的求解成功率达到 40%，而未预处理模型难以稳定求解。

5. 主要贡献与意义

理论创新：首次将 Dirac 定理应用于 TSP 的预处理阶段，从理论上严格证明了在保留 $\lceil n/2 \rceil$ 个最近邻的情况下，哈密顿回路的可行性得以保留。
量子计算赋能：解决了量子优化在 TSP 应用中的“规模瓶颈”。通过减少变量和约束，使得利用当前受限的量子硬件（如 D-Wave）解决更大规模（ $V=15$ ）的实际基准问题成为可能。
通用性提升：该方法不仅对量子求解器有效，对经典 ILP 求解器（如 Gurobi）也能显著加速，证明了该预处理策略在混合计算环境中的广泛适用性。
基准测试验证：不同于以往使用人工生成的小规模玩具问题，本文在 TSPLIB 标准基准上进行了评估，提供了更具现实意义的性能评估。

6. 结论

本文提出的 CAF 预处理方法 是一种高效、理论可靠的策略，它通过剔除长距离弧来缩减 TSP 模型规模。实验表明，该方法在保持解的最优性和可行性的同时，显著降低了决策变量数量，从而大幅提升了经典和量子求解器的计算效率及求解质量。这项工作为在现有硬件限制下扩展量子优化在组合优化问题中的应用提供了重要的实践路径。未来的研究可进一步探索动态迭代优化策略，以应对更大规模的 TSP 实例。