This paper introduces a new learning-based approach for approximately solving
the Travelling Salesman Problem on 2D Euclidean graphs. We use deep Graph
Convolutional Networks to build efficient TSP graph representations and output
tours in a non-autoregressive manner via highly parallelized beam search. Our
approach outperforms all recently proposed autoregressive deep learning
techniques in terms of solution quality, inference speed and sample efficiency
for problem instances of fixed graph sizes. In particular, we reduce the
average optimality gap from 0.52% to 0.01% for 50 nodes, and from 2.26% to
1.39% for 100 nodes. Finally, despite improving upon other learning-based
approaches for TSP, our approach falls short of standard Operations Research
solvers.

本文介绍了一种基于深度学习算法的解决平面欧几里得图中旅行商问题的方法，通过使用图卷积网络构建 TSP 图表示，并通过高度并行化的 Beam Search 非自回归方法输出巡回路径，我们在解决相同节点规模下的问题中比最近提出的自回归深度学习技术表现更好，最终平均优化差距从 50 个节点降低到 0.01％，100 个节点从 2.26％降至 1.39％，尽管相较于标准的运筹学求解器，我们的方法还有所欠缺。