论文解读 张云天，王飞龙

编者按

旅行商问题（Traveling Salesman Problem, TSP）是著名的组合优化问题，属于 NP-hard 问题。例如，给定一个分布在不同位置的客户列表，如何规划访问顺序才能使总旅行路径最短。随着客户数量增加，获取最优解的复杂度也呈指数级增加。当客户数量达到数千个及其以上时，获取次优解也需要花费大量的计算时间，或者在较短时间内难以获取高质量的解。这限制了其在实际问题尤其是规模较大且对求解效率要求较高的场景中的应用，如快递配送中的实时订单调度等 [1]。

近年来基于机器学习的算法已经被尝试应用于求解TSP。『运筹OR帷幄』曾经深度解读由美国人工智能协会主办的顶级学术会议 AAAI'2021 中一篇优秀文章《Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances》。解读旧文重温：OM | 机器学习算法求解更大规模的旅行商问题

本文中，我们解读 AAAI'2023 的一篇新作。该文章由微软亚洲研究院、华中科技大学、中国科学技术大学等合作完成，是应用机器学习技术求解大规模TSP问题的新成果 [2]。

本文提出了一个端到端的基于分层强化学习的方法 H-TSP 来解决此问题。该方法包含两层策略：上层策略用于将原始的规模较大的问题拆解成多个规模较小的子问题；下层策略解决每个子问题并将子方案合并形成原始问题的解决方案。通过实验对比发现，H-TSP 方法能够较好地协调效果与效率时间的平衡。同目前最高效的基于搜索的方法相比，该方法能够在仅损失4%效果的情况下，将求解时间从395秒降低到3.4秒。这也是首个达成处理超过10000的客户规模的端到端方法 [1]。

引言

旅行商问题（Traveling Salesman Problem, TSP）是著名的组合优化问题，属于 NP-hard 问题。学者们已设计诸多精确求解器和启发式算法来求解TSP，例如Concorde，LKH等。但是，它们都非常复杂，由许多设计巧妙的规则组成，并严重依赖于专家知识。为了克服这些局限性，近年来基于机器学习的算法已经被尝试应用于求解TSP。

总的来说，求解TSP的机器学习算法可以分为两类，“迭代寻优”（Iterative）和“步步构造”（Constructive）。

•“迭代寻优”类方法中，初始解即为一个可行解（Feasible solution），核心是设计一个可以不断提升解质量的更新策略。但其相对耗时（Time-consuming）。

•“步步构造”类方法中，算法从第一个城市开始，逐步访问所有城市直至形成完整TSP环游（即一个可行解）。其在推断（Inference）速度上具备优势，但其动作空间随城市规模线性增长，使其面临较重的计算负担。

综上，本文基于“分而治之”（Divide-and-conquer），“问题分解”（Problem Decomposition）的思想，设计了一种分层强化学习方法，以求解大规模TSP。该方法首先利用上层策略将原始规模较大的问题拆解成多个规模较小的子问题，其次应用下层策略解决每个子问题并将子方案合并形成原始问题的解决方案。上层和下层策略以端到端（End-to-end）的方式，基于强化学习算法协同训练。实验结果证实了所提出算法与SOTA对比算法的竞争力，并凸显了其在推断时间上的优势（不到4秒）。同时，算法用到的“分而治之”、“问题分解”的思想或可助力其他复杂、大规模优化问题的高效求解。

算法整体流程上层策略（Upper-Level Model）

上层策略主要是采用分治的思想（Divide-and-conquer）用来将较大规模的TSP问题进行分解，同时不会对最终的求解结果产生较大的影响。文中的分解方法同之前论文的分解方法的不同之处在于：所有的子问题的生成不是一步到位的，二是在上层模型和下层模型交互训练的过程中动态生成的，从而上层模型可以更好地利用交互训练过程中的信息，可以更好地学习一种自适应的策略，基于某个状态的信息（i.e., 当前的partial route和剩余节点信息）做出更好的决策。

1）可扩展的编码器

在对大规模TSP问题进行编码时，一个比较大的难点在于网络中边的数量过于庞大，使得编码信息过多。文章借助了3D点云投影中的处理技术，提出了一种Pixel Encoder，将问题网络作为图像处理。具体处理过程如下：

2）子问题生成与聚合

3）马尔科夫决策过程（Markov Decision Process, MDP）

下层策略（Lower-Level Model）

下层策略旨在求解开环TSPs（Open-loop TSPs）。下层策略将在训练和推断过程中被反复调用，亟需高效的设计。本文参考了先前求解小规模TSP的优秀工作，加以改进，设计了下层策略。

类似上层策略一节，可以定义下层策略的MDP。请感兴趣的读者参见原文。

策略训练

本文应用Proximal Policy Optimization (PPO) 算法训练上层策略，REINFORCE算法训练下层策略。两种强化学习方法均是经典方法，论文原文 [2] 也给出了主要依据和公式，在此不再赘述。本文进一步设计了协同训练（Joint Training）方法。下层策略生成并为上层策略的训练提供轨迹；同时，上层策略生成的子问题被存储下来训练下层策略。两层策略以一种类似“交叉存取”（Interleaving）的方式协同训练。注意到，同时后期实验也证实了，下层策略对解质量影响更大。如果一开始随机生成下层策略，上层策略会收到不良的反馈，训练难以收敛。因此，本文为下层策略设计了warm-up机制，即预训练一个策略。实验表明warm-up机制提升了训练的稳定性与收敛性。

实验结果

为充分评估算法的性能，本文在大量的TSP算例上进行了实验，并与6种先进的算法进行对比，包括：Concorde, LKH-3, OR-Tools, POMO, DRL-2opt, Att-GCN+MCTS（对这些主流/先进对比算法细节感兴趣的读者可移步论文原文）。实验中生成了四个不同规模的TSP数据集，分别为Random1000, Random2000, Random5000, Random10000。所有实验在一台配备NVIDIA®Tesla V100 (16GB) GPU和Intel(R) Xeon(R) Platinum CPU的机器上运行。

Table 1展示了所提出的H-TSP与六种对比算法的结果，主要从解的质量（Gap: %）和求解时间（Time: s）两个角度展现。其中，Concorde由于计算时间受限，难以在5000和10000规模的数据集上测试。可以看到POMO和DRL-2opt两种对比算法在大规模TSP中表现较差。而H-TSP在保证Gap较小的同时，拥有数量级降低的推断时间，这对于实时性要求较高的实际场景很有益。此外，本文还探讨了H-TSP的泛化（Generalization）性能，尤其是从小规模TSP到大规模TSP的泛化能力，实验结果见Figure 1。

本文进一步开展消融实验（Ablation Study），探讨上层和下层策略设计的有效性与发挥的作用，如Figure 2所示。其中，上层策略的替代方案为一种随机策略（Random policy），下层策略的替代方案为启发式策略Farthest Insertion [4]。实验证实了上、下层策略的设计都很有必要，且下层策略发挥的作用更甚。

在TSP这类路径规划问题中，启发式算法LKH-3表现出卓越的性能。结合消融实验得到的结论，本文将下层策略替换为LKH-3并进行实验，实验结果见Table 2。配备了LKH-3的H-TSP算法相较于原始H-TSP，在求解性能上有进一步的提升，但计算耗时也有所增加，不过仍低于Att-GCN+MCTS许多。

本文还对生成子问题（Sub-Problem Generation）过程中的一些算法与训练策略进行了消融实验，详细实验结果见Table 3。值得注意的是，去除warm-up机制（即w/o warm-up一栏）后解的Gap大幅提升，论证了warm-up机制在下层策略中的重要性。如前文所述，warm-up机制通过预训练一个下层策略，提升了训练的稳定性与收敛性。

总结

本文基于“分而治之”、“问题分解”的思想提出了一种分层强化学习框架H-TSP，用以求解大规模TSP。四个不同规模数据集上的大量实验证明了算法的性能与计算效率。通过消融实验，本文验证了所设计策略的有效性，并探索了利用诸如LKH-3这样的先进启发式算法进一步提升下层策略的可行性。进一步地，本文提出的设计思想，或将助力其他复杂、大规模优化问题（如车辆路径规划、车间调度）的高效求解。

参考文献

[1]

[2] (论文原文) Xuanhao Pan, Yan Jin, Yuandong Ding, Mingxiao Feng, Li Zhao, Lei Song, & Jiang Bian. (2023). H-TSP: Hierarchically Solving the Large-Scale Traveling Salesman Problem. In Proceedings of the AAAI Conference on Artificial Intelligence. 附PDF链接：

[3] Lang, A. H., Vora, S., Caesar, H., Zhou, L., Yang, J., & Beijbom, O. (2019). Pointpillars: Fast encoders for object detection from point clouds. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition (pp. 12697-12705).

[4] Rosenkrantz, D. J., Stearns, R. E., & Lewis, P. M. (1974, October). Approximate algorithms for the traveling salesperson problem. In 15th Annual Symposium on Switching and Automata Theory (swat 1974) (pp. 33-42). IEEE.