Offline Decision Transformers for Neural Combinatorial Optimization: Surpassing Heuristics on the Traveling Salesman Problem

📄 arXiv: 2603.25241v1 📥 PDF

作者: Hironori Ohigashi, Shinichiro Hamada

分类: cs.LG

发布日期: 2026-03-26

备注: 11 pages, 1 figures. Accepted at NeurIPS 2025 Workshop on DiffCoALG

💡 一句话要点

利用离线决策Transformer解决TSP问题，超越传统启发式算法

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 旅行商问题 组合优化 离线强化学习 决策Transformer 指针网络

📋 核心要点

  1. 神经组合优化依赖在线强化学习，部署困难且未能充分利用现有算法知识。
  2. 利用离线决策Transformer，直接从启发式解的数据集中学习更优策略，超越模仿。
  3. 实验表明，该方法优于四种经典启发式算法，证明了离线RL的潜力。

📝 摘要（中文）

旅行商问题（TSP）等组合优化问题在工业界至关重要，但属于NP难问题。神经组合优化展现了潜力，但其对在线强化学习（RL）的依赖限制了部署，且未能充分利用数十年的算法知识。本文通过应用离线RL框架——决策Transformer，直接从启发式解的数据集中学习更优策略，旨在不仅模仿，而且综合并超越它们，从而解决这些局限性。具体而言，我们（i）集成了一个指针网络来处理节点选择的实例相关、可变动作空间，以及（ii）采用期望回归来乐观地调节Return-to-Go，这对于最优值差异很大的实例至关重要。实验表明，我们的方法始终产生比训练所用的四种经典启发式算法更高质量的路径，证明了离线RL在解锁和超越现有领域知识中所蕴含的性能方面的潜力。

🔬 方法详解

问题定义：论文旨在解决旅行商问题（TSP），这是一个经典的NP难组合优化问题。现有的神经组合优化方法通常依赖于在线强化学习，这需要大量的在线交互和训练，计算成本高昂，并且难以部署。此外，这些方法往往未能充分利用已有的启发式算法的知识，这些算法经过多年的研究和优化，蕴含着丰富的领域经验。

核心思路：论文的核心思路是利用离线强化学习，特别是决策Transformer，直接从已有的启发式算法生成的数据集中学习。通过将TSP问题建模为一个序列决策问题，并利用决策Transformer强大的序列建模能力，学习启发式算法的策略，并在此基础上进行优化，从而超越启发式算法的性能。这种方法避免了在线强化学习的昂贵计算成本，并且能够充分利用已有的领域知识。

技术框架：整体框架包括数据收集、模型训练和策略部署三个阶段。首先，使用多种启发式算法生成TSP实例及其对应的解，构建离线数据集。然后，使用决策Transformer模型对该数据集进行训练，学习一个策略网络。该网络以TSP实例和当前状态作为输入，输出下一步要选择的节点。为了处理TSP问题的可变动作空间，论文集成了指针网络。在策略部署阶段，使用训练好的策略网络对新的TSP实例进行求解。

关键创新：论文的关键创新在于将离线强化学习框架决策Transformer应用于神经组合优化，并针对TSP问题的特点进行了改进。具体来说，(1) 集成了指针网络来处理实例相关的可变动作空间，使得模型能够处理不同规模的TSP问题。(2) 采用了期望回归来乐观地调节Return-to-Go，这对于最优值差异很大的实例至关重要，可以提高模型的鲁棒性和性能。

关键设计：在模型结构方面，使用了标准的Transformer结构，并集成了指针网络来处理动作空间。在训练方面，使用了期望回归损失函数来优化Return-to-Go的估计。Return-to-Go是指从当前状态到最终状态的期望回报，通过优化Return-to-Go的估计，可以引导模型学习更优的策略。此外，论文还使用了多种数据增强技术来提高模型的泛化能力。具体参数设置未知。

🖼️ 关键图片

fig_0

📊 实验亮点

实验结果表明，该方法在TSP问题上取得了显著的性能提升，超越了四种经典的启发式算法。具体性能数据未知，但论文强调该方法能够始终产生更高质量的路径，证明了离线RL在神经组合优化中的潜力。

🎯 应用场景

该研究成果可应用于物流配送、路径规划、电路设计等领域，具有重要的实际应用价值。通过学习和超越现有启发式算法，可以显著提高问题求解效率和优化程度，降低成本，提升服务质量。未来，该方法有望推广到其他组合优化问题，为解决实际工程问题提供更有效的工具。

📄 摘要（原文）

Combinatorial optimization problems like the Traveling Salesman Problem are critical in industry yet NP-hard. Neural Combinatorial Optimization has shown promise, but its reliance on online reinforcement learning (RL) hampers deployment and underutilizes decades of algorithmic knowledge. We address these limitations by applying the offline RL framework, Decision Transformer, to learn superior strategies directly from datasets of heuristic solutions; it aims to not only to imitate but to synthesize and outperform them. Concretely, we (i) integrate a Pointer Network to handle the instance-dependent, variable action space of node selection, and (ii) employ expectile regression for optimistic conditioning of Return-to-Go, which is crucial for instances with widely varying optimal values. Experiments show that our method consistently produces higher-quality tours than the four classical heuristics it is trained on, demonstrating the potential of offline RL to unlock and exceed the performance embedded in existing domain knowledge.