旅行商问题(Traveling Salesman Problem, TSP)是由冯诺依曼(von Neumann)于1951年提出的最受欢迎和研究最多的组合优化问题。它推动了几个优化技术的发展，如切割平面、分支定界法、局部搜索、拉格朗日松弛和模拟退火。在过去的五年里，出现了许多新兴技术，其中(图)神经网络是一种求解组合优化问题的新算法。现存的主要问题是，深度学习是否可以从数据中更好地学习启发式算法，即取代人类设计的启发式算法。这一研究很有吸引力，因为开发一种有效解决NP-hard问题的算法可能需要多年的研究，而许多行业问题本质上也是一种组合优化问题。文章提出采用最近在自然语言处理上应用效果非常好的Transformer架构来求解TSP。训练是通过强化学习完成的，因此没有TSP训练方案，而解码使用波束搜索。文章改进了最近的启发式学习方法，与TSP50的最佳差距为0.004%，TSP100的最佳差距为0.39%。
代码：https://github.com/xbresson/TSP_Transformer
