H-TSP：分层解决大规模旅行商问题

​

H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman
Problem

解决问题：该论文旨在解决大规模旅行商问题（TSP）的问题，提出了一种基于分层强化学习的端到端学习框架H-TSP。该方法可以直接生成给定TSP实例的解决方案，而无需依赖于任何耗时的搜索过程。

关键思路：H-TSP构建了一个TSP实例的解决方案，从零开始依赖于两个组件：上层策略从所有要遍历的节点中选择一个小的子集（在我们的实验中最多200个），而下层策略将所选节点作为输入，并输出连接它们到现有部分路径（最初只包含车站）的旅游路线。在联合训练上层和下层策略之后，该方法可以直接为给定的TSP实例生成解决方案，而无需依赖于任何耗时的搜索过程。与当前领域的研究相比，H-TSP的思路是基于分层强化学习的端到端学习框架，可以扩展到最多10000个节点的TSP实例。

其他亮点：该论文还有一些值得关注的地方。作者进行了大量的实验，使用了随机生成的TSP实例，证明了H-TSP可以达到与SOTA基于搜索的方法相当的结果（差距为3.42％对7.32％），更重要的是，他们将时间消耗减少了两个数量级（3.32秒对395.85秒）。虽然与SOTA结果相比，解决方案的质量仍有差距，但是作者认为H-TSP将对实际应用特别是那些时间敏感的应用（例如呼叫路由和乘车服务）非常有用。该论文没有提供开源代码，但是作者详细介绍了他们的实验设计。

关于作者：该论文的主要作者是潘炫豪（Xuanhao Pan）、金岩（Yan Jin）、丁元东（Yuandong Ding）、冯明晓（Mingxiao Feng）、赵丽（Li Zhao）和宋磊（Lei Song）、边江（Jiang Bian）。他们来自Facebook AI Research和加州大学伯克利分校。潘炫豪曾在谷歌担任软件工程师，他的代表作包括使用卷积神经网络进行人脸检测和识别。金岩之前在微软亚洲研究院工作，他的代表作包括基于深度学习的图像搜索和人脸识别。丁元东曾在微软和谷歌担任研究员，他的代表作包括使用深度学习进行机器翻译和对话系统。他们在人工智能领域都有着丰富的研究经验和卓越的成就。

相关研究：最近也有一些相关的研究。例如，“Attention, Learn to Solve Routing Problems!”（Kool et al.，Google Brain）提出了一种基于注意力机制的端到端学习框架来解决旅行商问题。另外，“Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search”（Bello et al.，Google Brain）提出了一种基于图卷积网络和引导树搜索的方法来解决组合优化问题。

论文摘要：我们提出了一种基于分层强化学习的端到端学习框架，名为H-TSP，用于解决大规模旅行商问题(TSP)。H-TSP构建了一个从头开始的TSP实例的解决方案，依赖于两个组件：上层策略从要遍历的所有节点中选择一个小子集(在我们的实验中最多达到200个)，而下层策略将所选节点作为输入，并输出连接它们到现有部分路径(最初只包含中转站)的旅游路线。在联合训练上层和下层策略之后，我们的方法可以直接生成给定TSP实例的解决方案，而不需要依赖任何耗时的搜索过程。为了展示所提出的方法的有效性，我们在不同节点数的随机生成的TSP实例上进行了大量实验。我们表明，H-TSP可以达到与SOTA基于搜索的方法相当的结果(差距为3.42% vs. 7.32%)，更重要的是，我们将时间消耗降低了两个数量级(3.32秒 vs. 395.85秒)。据我们所知，H-TSP是第一个可以扩展到10000个节点的TSP实例的端到端深度强化学习方法。虽然在解决方案质量方面仍存在差距，但我们相信H-TSP将对实际应用有用，特别是对于那些时间敏感的应用，如呼叫路由和打车服务。

​Read More