An End-to-End Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Drones

📄 arXiv: 2511.05265v1 📥 PDF

作者: Taihelong Zeng, Yun Lin, Yuhe Shi, Yan Li, Zhiqing Wei, Xuanru Ji

分类: cs.LG, cs.AI

发布日期: 2025-11-07

💡 一句话要点

提出基于Transformer和Minimal Gated Unit的深度强化学习框架，解决带无人机的旅行商问题。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱七：动作重定向 (Motion Retargeting)

关键词: 深度强化学习 旅行商问题 无人机 车辆路径问题 Transformer Actor-Critic 物流优化

📋 核心要点

  1. 带无人机的旅行商问题（TSP-D）是NP-hard问题，传统优化方法难以应对其组合复杂性。
  2. 提出一种分层Actor-Critic深度强化学习框架，利用Transformer编码器和Minimal Gated Unit解码器进行策略学习。
  3. 实验表明，该模型在TSP-D基准测试中，相较于启发式算法和现有强化学习方法，在计算时间和性能上均有优势，且训练效率更高。

📝 摘要（中文）

本文针对末端物流中卡车-无人机协同系统的带无人机的旅行商问题（TSP-D），提出了一种分层Actor-Critic深度强化学习框架。该框架包含一个Transformer编码器和一个高效的Minimal Gated Unit解码器。编码器采用优化的k近邻稀疏注意力机制，并融合了全局节点特征，以关注相关的空间关系。解码器处理编码后的表示，高效生成解决方案序列。整个框架在异步优势Actor-Critic范式下运行。实验结果表明，在各种规模（N=10到100）的TSP-D基准实例上，与高性能启发式算法和现有强化学习方法相比，该模型能够以更短的平均计算时间获得有竞争力的甚至更优越的解决方案。此外，与先进的强化学习算法基准相比，该框架显著减少了所需的总训练时间，同时实现了卓越的最终性能，突出了其在训练效率方面的显著优势。

🔬 方法详解

问题定义：论文旨在解决带无人机的旅行商问题（TSP-D），该问题是经典旅行商问题的扩展，涉及卡车和无人机的协同配送。现有方法，如传统优化算法和启发式算法，难以有效处理TSP-D的NP-hard组合复杂性，计算成本高昂。现有的强化学习方法训练效率较低，难以达到最优性能。

核心思路：论文的核心思路是利用深度强化学习，通过自监督策略学习和自适应决策来解决TSP-D的挑战。具体而言，采用Actor-Critic框架，Actor负责生成解的序列，Critic负责评估解的质量，通过不断迭代优化策略。Transformer编码器用于提取节点之间的空间关系特征，Minimal Gated Unit解码器用于高效生成解序列。

技术框架：整体框架是一个分层的Actor-Critic结构。首先，Transformer编码器接收TSP-D问题的节点信息作为输入，通过优化的k近邻稀疏注意力机制和全局节点特征融合，提取节点之间的空间关系表示。然后，Minimal Gated Unit解码器利用编码器的输出，逐步生成TSP-D问题的解序列。最后，Critic网络评估Actor生成的解的质量，并提供反馈信号，用于Actor网络的策略更新。整个训练过程采用异步优势Actor-Critic（A3C）范式，提高训练效率。

关键创新：论文的关键创新在于以下几点：1) 提出了基于Transformer和Minimal Gated Unit的深度强化学习框架，有效解决了TSP-D问题。2) 引入了优化的k近邻稀疏注意力机制，降低了计算复杂度，并关注了相关的空间关系。3) 采用了Minimal Gated Unit解码器，提高了生成解序列的效率。4) 采用了异步优势Actor-Critic（A3C）范式，提高了训练效率。

关键设计：编码器使用了Transformer结构，并引入了k近邻稀疏注意力机制，只关注每个节点周围的k个最近邻节点，从而降低了计算复杂度。解码器使用了Minimal Gated Unit，这是一种轻量级的循环神经网络单元，可以高效地生成解序列。损失函数包括Actor网络的策略梯度损失和Critic网络的均方误差损失。训练过程中，使用了异步优势Actor-Critic（A3C）算法，多个Actor并行探索环境，并将梯度信息异步地更新到全局网络中。

📊 实验亮点

实验结果表明，该模型在TSP-D基准实例（N=10到100）上，与高性能启发式算法和现有强化学习方法相比，能够以更短的平均计算时间获得有竞争力的甚至更优越的解决方案。与先进的强化学习算法基准相比，该框架显著减少了所需的总训练时间，同时实现了卓越的最终性能，突出了其在训练效率方面的显著优势。

🎯 应用场景

该研究成果可应用于末端物流配送、应急救援、灾后重建等领域，通过优化卡车和无人机的协同调度，提高配送效率，降低运营成本，减少环境影响。未来，该方法可以扩展到更复杂的车辆路径问题，例如考虑时间窗、容量限制等约束条件，具有广阔的应用前景。

📄 摘要（原文）

The emergence of truck-drone collaborative systems in last-mile logistics has positioned the Traveling Salesman Problem with Drones (TSP-D) as a pivotal extension of classical routing optimization, where synchronized vehicle coordination promises substantial operational efficiency and reduced environmental impact, yet introduces NP-hard combinatorial complexity beyond the reach of conventional optimization paradigms. Deep reinforcement learning offers a theoretically grounded framework to address TSP-D's inherent challenges through self-supervised policy learning and adaptive decision-making. This study proposes a hierarchical Actor-Critic deep reinforcement learning framework for solving the TSP-D problem. The architecture consists of two primary components: a Transformer-inspired encoder and an efficient Minimal Gated Unit decoder. The encoder incorporates a novel, optimized k-nearest neighbors sparse attention mechanism specifically for focusing on relevant spatial relationships, further enhanced by the integration of global node features. The Minimal Gated Unit decoder processes these encoded representations to efficiently generate solution sequences. The entire framework operates within an asynchronous advantage actor-critic paradigm. Experimental results show that, on benchmark TSP-D instances of various scales (N=10 to 100), the proposed model can obtain competitive or even superior solutions in shorter average computation times compared to high-performance heuristic algorithms and existing reinforcement learning methods. Moreover, compared to advanced reinforcement learning algorithm benchmarks, the proposed framework significantly reduces the total training time required while achieving superior final performance, highlighting its notable advantage in training efficiency.