The Traveling Salesman Problem (TSP) is a well-known problem in combinatorial
optimization with applications in various domains. However, existing TSP
solvers face challenges in producing high-quality solutions with low latency.
To address this issue, we propose NAR4TSP, which produces TSP solutions in a
Non-Autoregressive (NAR) manner using a specially designed Graph Neural Network
(GNN), achieving faster inference speed. Moreover, NAR4TSP is trained using an
enhanced Reinforcement Learning (RL) strategy, eliminating the dependency on
costly labels used to train conventional supervised learning-based NAR models.
To the best of our knowledge, NAR4TSP is the first TSP solver that successfully
combines RL and NAR decoding. The experimental results on both synthetic and
real-world TSP instances demonstrate that NAR4TSP outperforms four
state-of-the-art models in terms of solution quality, inference latency, and
generalization ability. Lastly, we present visualizations of NAR4TSP's decoding
process and its overall path planning to showcase the feasibility of
implementing NAR4TSP in an end-to-end manner and its effectiveness,
respectively.

NAR4TSP 是第一个成功结合强化学习和非循环解码的解决 TSP 问题的算法，通过使用一个特殊设计的图神经网络以非循环的方式生成 TSP 解决方案，实现更快的推理速度，其训练使用了增强型强化学习策略，消除了传统基于监督学习的非循环模型的昂贵标签依赖，实验结果表明 NAR4TSP 在解决质量、推理延迟和泛化能力方面优于四个最先进的模型，此外，我们展示了 NAR4TSP 解码过程和整体路径规划的可行性和有效性的可视化。