对于庞大规模的旅行推销员问题（TSP），现有算法在计算效率和解决方案质量方面面临巨大挑战。为了解决这个问题，我们提出了一种分层销毁和修复（HDR）方法，通过一系列精心设计的销毁和修复操作来改进初始解。一个关键创新概念是分层搜索框架，它递归地修复部分边缘，并将输入实例压缩成小规模的 TSP，在某种等价保证下。这个巧妙的搜索框架能够在合理的时间内提供极具竞争力的解决方案。基于 19 个著名的大规模实例（城市数量从 10,000 到 10,000,000 个），公平比较显示 HDR 在计算效率和解决方案质量方面与现有最先进的 TSP 算法高度竞争。值得注意的是，在 3,162,278 个和 10,000,000 个城市的两个大型实例中，HDR 打破了 LKH 及其变体先前创下的世界纪录（即无论计算时间如何，都是最好的已知结果），而 HDR 完全独立于 LKH。最后，通过消融研究来证明分层搜索框架的重要性和有效性。

Aug, 2023

本文提出了一个基于增强学习的启发式算法 VSR-LKH，它运用 Q-learning、Sarsa、Monte Carlo 三种方法改进了已有的 TSP 算法 Lin-Kernighan-Helsgaun (LKH)，将其高效应用于 111 个 TSP 基准测试，结果表明，该方法表现出具有良好的性能。

Dec, 2020

本文针对旅行商问题，通过训练一个能够根据图形采样、转化和热力图合并等技术建立任意规模的热力图的小型模型，并采用强化学习算法进行高质量解的搜索，显著提高了该模型的泛化能力和性能。该方法优于现有基于机器学习的 TSP 算法。

Dec, 2020

本文提出了一种神经组合优化方法，将学习算法与模型架构相结合，以实现在训练过程中看不到的更大规模的问题的推广。通过对零样本推广的原理研究，控制实验提供了第一手数据，并提供了深度学习的新方向。

Jun, 2020

我们提出了 UTSP，这是一个用于解决旅行推销员问题（TSP）的无监督学习框架，使用基于图神经网络（GNN）的代理损失。该方法在参数效率和数据效率方面优于目前的数据驱动 TSP 启发式方法。

Mar, 2023

本论文使用基于深度加强学习方法的策略梯度算法，通过 2-opt 操作符学习本地搜索启发式，提出了一种可以轻松扩展到更一般 k-opt 移动的策略神经网络，实验结果表明，所学习的策略比之前的具有最先进性能的深度学习方法更快接近最优解。

Apr, 2020

本研究提出了 Variable Strategy Reinforced LKH (VSR-LKH) 与 VSR-LKH-3 算法，分别引入了三种强化学习方法与 LKH 算法相结合，以解决 TSP 问题和 TSP 变体（包括 TSPTW 和 CTSP），经 236 个 TSP 基准测试表明，这些算法具有显著的性能优势。

Jul, 2022

本文利用强化学习和 Transformer 结构设计了用于 Traveling Salesman Problem 的新型算法，相较于以往的算法在 TSP50 和 TSP100 上有了更好的表现

Mar, 2021

本研究提出了一种基于模仿学习框架的策略来解决旅行商问题，并展示了所训练的图神经网络在大规模的 TSP 实例上的较快求解能力。

Oct, 2022

提出一种基于深度强化学习的经理 - 工作人员框架来解决一种复杂但非常重要的旅行商问题的变体（即具有时间窗口和拒绝的多车 TSP），其中不能在截止日期前提供服务的客户可能被拒绝。经过实验结果证明，该框架在解决大型问题时具有高质量的解决方案和更短的计算时间。

Sep, 2022