論文解讀 張雲天，王飛龍
編者按
旅行商問題（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] https://www.msra.cn/zh-cn/news/features/aaai-2023-industrial-applicable-ai
[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連結：https://www.microsoft.com/en-us/research/uploads/prod/2023/02/8643.PanX_.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.