A First Guess is Rarely the Final Answer: Learning to Search in the Travelling Salesperson Problem
作者: Andoni Irazusta Garmendia
分类: cs.LG, cs.AI
发布日期: 2026-04-08
💡 一句话要点
NICO-TSP：学习TSP问题的搜索策略，提升求解效率与泛化性
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 旅行商问题 局部搜索 神经优化 强化学习 组合优化
📋 核心要点
- 现有TSP神经求解器侧重于单解输出，忽略了实际应用中常用的搜索和优化步骤。
- NICO-TSP通过学习2-opt局部搜索策略，直接优化TSP路径，避免了传统方法的局限性。
- 实验表明，NICO-TSP在求解效率、泛化性和作为后处理模块的性能上均优于现有方法。
📝 摘要（中文）
针对旅行商问题（TSP），现有神经求解器通常训练输出单一解，而实际应用中会花费额外计算资源进行采样或后处理搜索。本文提出能否学习搜索过程本身的问题。神经改进方法通过学习策略对候选解进行局部修改，并在改进轨迹上累积增益。然而，TSP的已学习改进方法仍不成熟，性能和可扩展性不足。本文认为关键原因是设计不匹配：许多方法沿用单解方法的状态表示、架构选择和训练方案，而非围绕局部搜索机制构建。为此，本文提出了NICO-TSP（组合优化的神经改进）：一个用于TSP的2-opt改进框架。NICO-TSP使用与邻域算子对齐的n个边token表示当前路径，直接对2-opt移动进行评分，无需路径位置编码，并通过两阶段程序进行训练：模仿学习到短视距最优轨迹，然后通过无评论员的基于群体的强化学习进行更长期的探索。在计算匹配的评估下，NICO-TSP在搜索步骤和实际时间方面都提供了比先前学习和启发式搜索基线更强大、更高效的改进，更可靠地泛化到更大的分布外实例，并且可以作为经典局部搜索的竞争替代方案以及构造性求解器的强大测试时细化模块。
🔬 方法详解
问题定义：论文旨在解决旅行商问题（TSP）的求解效率和泛化性问题。现有神经求解器通常输出单一解，缺乏后续优化能力，且在面对大规模或分布外实例时性能下降。传统的局部搜索方法虽然有效，但依赖人工设计的启发式规则，难以适应不同类型的TSP实例。
核心思路：论文的核心思路是学习一个神经策略，用于指导TSP的2-opt局部搜索过程。通过模仿学习和强化学习，使模型能够自动发现高效的搜索策略，从而在更短的时间内找到更好的解。这种方法避免了人工设计启发式规则的困难，并有望提高求解效率和泛化性。
技术框架：NICO-TSP框架包含以下主要模块：1) 边token表示：使用n个边token表示当前TSP路径，每个token对应一条边。2) 2-opt移动评分：模型直接对2-opt移动进行评分，无需路径位置编码。3) 两阶段训练：首先通过模仿学习，学习短视距最优轨迹；然后通过无评论员的基于群体的强化学习，进行更长期的探索。
关键创新：NICO-TSP的关键创新在于其针对局部搜索机制的设计。与现有方法不同，NICO-TSP直接学习2-opt移动的评分函数，并使用边token表示路径，避免了传统方法中对路径位置编码的依赖。此外，两阶段训练策略结合了模仿学习和强化学习的优点，提高了模型的学习效率和泛化能力。
关键设计：NICO-TSP的关键设计包括：1) 边token表示：每个token包含边的起点和终点信息。2) 2-opt移动评分网络：使用Transformer网络对边token进行编码，并预测每个2-opt移动的收益。3) 损失函数：模仿学习阶段使用交叉熵损失，强化学习阶段使用策略梯度损失。4) 训练策略：使用基于群体的强化学习，鼓励模型探索不同的搜索策略。
🖼️ 关键图片
📊 实验亮点
实验结果表明，NICO-TSP在计算资源匹配的情况下，比现有学习和启发式搜索方法更有效率，能够更快地找到更好的解。NICO-TSP在更大规模和分布外的TSP实例上表现出更强的泛化能力。例如，在特定测试集上，NICO-TSP的性能优于经典的局部搜索算法，并且可以作为现有构造性求解器的有效改进模块。
🎯 应用场景
NICO-TSP可应用于物流配送、路线规划、芯片设计等领域，通过优化旅行路线或资源分配，降低成本、提高效率。该方法有望替代传统启发式搜索算法，并作为后处理模块集成到现有TSP求解器中，提升其性能和鲁棒性。未来，该研究可推广到其他组合优化问题，如车辆路径问题、调度问题等。
📄 摘要（原文）
Most neural solvers for the Traveling Salesperson Problem (TSP) are trained to output a single solution, even though practitioners rarely stop there: at test time, they routinely spend extra compute on sampling or post-hoc search. This raises a natural question: can the search procedure itself be learned? Neural improvement methods take this perspective by learning a policy that applies local modifications to a candidate solution, accumulating gains over an improvement trajectory. Yet learned improvement for TSP remains comparatively immature, with existing methods still falling short of robust, scalable performance. We argue that a key reason is design mismatch: many approaches reuse state representations, architectural choices, and training recipes inherited from single-solution methods, rather than being built around the mechanics of local search. This mismatch motivates NICO-TSP (Neural Improvement for Combinatorial Optimization): a 2-opt improvement framework for TSP. NICO-TSP represents the current tour with exactly $n$ edge tokens aligned with the neighborhood operator, scores 2-opt moves directly without tour positional encodings, and trains via a two-stage procedure: imitation learning to short-horizon optimal trajectories, followed by critic-free group-based reinforcement learning over longer rollouts. Under compute-matched evaluations that measure improvement as a function of both search steps and wall-clock time, NICO-TSP delivers consistently stronger and markedly more step-efficient improvement than prior learned and heuristic search baselines, generalizes far more reliably to larger out-of-distribution instances, and serves both as a competitive replacement for classical local search and as a powerful test-time refinement module for constructive solvers.