提出统一框架解决邻近型旅行商问题,兼顾精度与泛化能力。
A Unified Deep Reinforcement Learning Approach for Close Enough Traveling Salesman Problem
- 分步决策:先选节点再定路径点,提升规划效率。
- 在多种半径和规模下优于传统方法,解质量更高、速度更快。
- 适合需要动态适应的复杂路径规划场景,如无人机巡检。
近年来,深度强化学习(DRL)在求解NP难的旅行商问题(TSP)中取得进展,但对邻近型旅行商问题(CETSP)关注较少,主要因其基于邻域的访问准则——当智能体进入某节点的紧凑邻域即视为已访问。本文通过离散化方案构建CETSP的马尔可夫决策过程(MDP),提出一种统一双解码器深度强化学习(UD3RL)框架,将决策分解为节点选择与路径点确定两个子任务。采用改进编码器进行特征提取,分别由节点解码器和位置解码器处理;引入k近邻子图交互策略,增强位置解码中的空间推理能力。此外,定制REINFORCE算法训练统一模型,使其可泛化于不同问题规模及邻域半径类型(恒定与随机)。实验表明,UD3RL在解质量与运行时间上均优于传统方法,且对问题尺度、空间分布、半径范围具有强泛化性,并具备动态环境鲁棒性。
原文摘要 · Abstract (English)
In recent years, deep reinforcement learning (DRL) has gained traction for solving the NP-hard traveling salesman problem (TSP). However, limited attention has been given to the close-enough TSP (CETSP), primarily due to the challenge introduced by its neighborhood-based visitation criterion, wherein a node is considered visited if the agent enters a compact neighborhood around it. In this work, we formulate a Markov decision process (MDP) for CETSP using a discretization scheme and propose a novel unified dual-decoder DRL (UD3RL) framework that separates decision-making into node selection and waypoint determination. Specifically, an adapted encoder is employed for effective feature extraction, followed by a node-decoder and a loc-decoder to handle the two sub-tasks, respectively. A k-nearest neighbors subgraph interaction strategy is further introduced to enhance spatial reasoning during location decoding. Furthermore, we customize the REINFORCE algorithm to train UD3RL as a unified model capable of generalizing across different problem sizes and varying neighborhood radius types (i.e., constant and random radii). Experimental results show that UD3RL outperforms conventional methods in both solution quality and runtime, while exhibiting strong generalization across problem scales, spatial distributions, and radius ranges, as well as robustness to dynamic environments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。