強化學習求解組合最優化問題的研究綜述

王 揚，陳智斌，吳兆蕊，高 遠

昆明理工大學 理學院，昆明650000

在實際工程應用中，有一類優化問題需要從集合的所有組合中找出一個最優方案或編排，這類離散空間中的優化問題稱為組合最優化問題（combinatorial optimization problem，COP）。組合最優化（combinatorial optimization，CO）的求解方法廣泛應用于交通運輸、管理、電力、航天、通信等領域，其快速求解具有重要的理論意義和實用價值。例如，車輛的調度、金融資產的配置、倉庫貨物存儲和運輸路線的設計等實際問題都屬于COP 問題，隨著這些優化問題實例規模的不斷增大和實例中動態及隨機因素的增加，傳統方法的求解將耗費巨大的時間，問題結構一旦發生變化，傳統方法需要重新搜索求解，計算成本也會隨之提高，快速求解這些優化問題變得十分困難。

近年來隨著深度學習（deep learning，DL）技術在計算機視覺、自然語言處理、語音識別、推薦系統等領域的廣泛應用，特別是深度強化學習（deep reinforcement learning，DRL）在AlphaGo、AlphaGo Zero的成功應用，表明在沒有人類干預和指導的前提下，DL 和強化學習（reinforcement learning，RL）的結合仍然能夠取得很大的成功，甚至超越了人類經驗的指導，具有快速求解、泛化能力強、求解精度高等優勢，為求解COP 問題提供一個全新的思路方法。鑒于此，近年來涌現出許多采用RL 求解COP 問題的新方法，即利用RL 訓練模型的方法替代傳統算法，讓機器從算法中學習算法，從而快速且有效地解決實際問題，適應現代科技的發展，進而滿足人類生活需求。

業界相關的工作已經逐漸開展，如2017 年Hu 等人采用DRL 的方法求解三維裝箱問題；2018 年Lin等人把RL 應用在共享出行中的車輛管理和派單問題上；2019 年Mao 等人將RL 的方法應用在分布式集群任務調度中；2020 年Mirhoseini 等人又將RL應用到芯片布局設計中。這些研究都是通過RL 的方法解決實際生活中的COP 問題，核心思路是：RL序貫決策的功能與具有序列決策性質的COP 問題有天然的相似性，RL 模型可以通過智能體與環境的不斷交互，自身逐步積累經驗來獲取問題的一個較優策略，在少量樣本甚至無樣本的情況下，通過自學習的方式快速求解實際生活中的優化問題，從而得到優化問題的解，在求解過程中傳統方法和新思路的流程如圖1 所示。

圖1 求解COP 問題的兩種思路Fig.1 Two approaches to solving COP problem

RL 求解COP 問題是近年來一個新興研究領域，目前系統的研究和綜述較少，因此本文對RL 求解COP 問題的方法進行文獻綜述，回顧總結各類求解方法和應用研究，分析求解模型的優缺點，為各位學者在新興方向的研究提供參考。

1 組合最優化問題和強化學習的介紹

1.1 組合最優化問題的簡單概述

CO（又稱離散優化）是最優化理論的一個重要組成部分，它是運籌學與計算機領域的一個交叉學科，主要研究具有離散結構的優化問題，即研究如何從一組有限的對象中找到一個最優對象的一類問題，這類問題的數學模型如下：

其中，為決策變量，為目標函數，為約束條件，為離散空間中有限點組成的定義域。

比較有代表性的幾個COP 問題：旅行商問題（traveling salesman problem，TSP）、施泰納樹問題（Steiner tree problem，STP）、車輛路徑問題（vehicle routing problem，VRP）、裝箱問題（bin packing，BP）、背包問題（knapsack problem，KP）、平行機排序問題（parallel machines scheduling problem，PMSP）、最小頂點覆蓋（minimum vertex cover，MVC）、集合覆蓋問題（set covering problem，SCP）、最大割問題（max-cut）。

這些COP 問題普遍存在于日常的生活中，它們屬于非確定性多項式問題（non-deterministic polynomial，NP），如何提高解的精度、減少時間復雜度、增強泛化能力、快速且有效地得到問題的較優解是長期以來最優化理論的熱點研究課題，其中求解方法的選擇顯得尤為重要，本文會在1.2 節對COP 問題的求解方法進行總結。

1.2 組合最優化問題求解方法概述

（1）傳統方法

①精確算法（exact algorithm）：枚舉法、分支定界（branch and bound，BB）、動態規劃（dynamic programming，DP）等均是通過不斷迭代的方式求解COP 問題的全局最優解。

②近似算法（approximation algorithm）：貪婪算法、局部搜索、線性規劃等可以在多項式時間內來近似最優解，保證最壞情況下給出的解不低于（最大化問題）最優解一定的倍數。

③（元）啟發式算法（heuristic algorithm）：遺傳算法、蟻群算法、模擬退火算法等均可以針對一般的COP 問題求解。

上述方法通稱為傳統算法，以經典的TSP 問題為例，其中枚舉法和DP 法求解TSP 問題的時間復雜度分別為(!) 和(2)，隨著實例問題規模的擴大，該方法很難快速求解大規模的TSP 問題，因此精確算法對求解COP 問題規模有一定的局限性；假定P≠NP，一般形式的TSP 問題是不可被近似的，設計近似算法多數要考慮問題的特殊情況，因此近似算法對求解COP 問題的條件有一定的限制；蟻群算法等可以快速求解TSP 問題，但缺乏理論支撐以及無法保證解的全局最優性，導致啟發式算法很難保證求解的質量。

（2）基于機器學習的COP 問題求解方法

①基于神經網絡（neural network，NN）求解TSP問題：Hopfield 等人提出一種Hopfield 網絡，首次嘗試用機器學習（machine learning，ML）的方法求解小規模的TSP 問題，之后很多相關工作也相繼出現，早期采用NN 求解COP 問題的文章可見Smith的綜述。

②基于指向型網絡（Pointer network，PN）求解COP 問題：Vinyals 等人針對Seq2Seq序列模型輸入輸出維度是固定的問題，對其改進，提出PN 架構，并加入注意力機制（attention mechanism，AM）使得序列模型不受輸入輸出維度的限制。PN 架構為基于ML 等新方法求解COP 問題的工作奠定了很好的理論基礎。

③基于DRL 求解COP 問題：監督學習（supervised learning，SL）需要大量標簽，且COP 問題的高質量標簽不易獲得。RL 使智能體與環境不斷交互，通過獎勵值來激勵學習得到數據，克服了SL 中大量標簽的花費問題。Zhang 等人將RL 應用到NP-hard 的車間調度問題，Bello 等人提出神經組合最優化模型（neural combinatorial optimization，NCO），為后續基于RL 方法求解COP 問題的推進奠定了基礎。

④基于Transformer框架求解COP 問題：Transformer 框架延續了AM 中編碼-解碼的結構，其網絡架構均由自注意力機制和全連接層（fully connected，FC）組成，模型中多重注意力機制（multihead attention，MHA）的自注意力機制計算方法，增加更多計算層，以便提取到深層節點的特征信息，有效克服信息丟失問題。

⑤基于圖神經網絡（graph neural networks，GNNs）求解COP 問題：GNNs 近幾年發展迅速，是一種將深度神經網絡（deep neural network，DNN）模型應用于解決圖上相關任務的方法，通過低維的向量信息來表征圖的節點及拓撲結構，此方法可以很好地處理非歐幾里德數據，有效抽取圖結構中的關鍵節點信息。

⑥基于ML 與傳統方法結合的求解方法：此方法求解COP 問題主要是端到端的輸出解。針對搜索過程中子問題不同的特性，Liberto 等人提出DASH（dynamic approach for switching heuristics）架構，動態切換合適的啟發算法求解COP 問題。He 等人引入模仿學習（imitation learning，IL），以SL 的方式得到自適應的節點搜索策略。此方法能夠利用ML 方法的優點，同時還能保證傳統方法的最優性。

近年來采用ML 方法求COP 的方法逐漸增多，其中Bengio 等人的綜述介紹了ML 與COP 求解的方法導論，說明ML 方法可以求解部分COP 問題，這對COP 問題的求解提供了部分理論支撐。文中表1 分析并總結了基于RL 的COP 問題求解方法，圖2 匯總了求解COP 問題的方法框架。

圖2 COP 解決方案框架Fig.2 COP solution framework

表1 研究方法、求解問題、模型算法的分析與總結Table 1 Analysis and summary of research methods,solving problems and models

1.3 強化學習的簡單概述

RL 被定義為智能體與環境不斷交互，獲取相應的獎勵，不斷學習以完成特定的目標任務。從圖3可以理解為智能體在與環境進行交互的過程中，通過不斷的嘗試，從錯誤中學習經驗，并根據經驗調整其策略，來最大化最終所有獎勵的累積值。RL 的獎勵很重要，具有獎勵導向性，這種獎勵導向性類似于SL 中正確的標簽，從一開始沒有數據和標簽，不斷嘗試在環境中獲取這些數據和標簽，然后再學習哪些數據對應哪些標簽，通過學習這樣的規律，不斷更新智能體的狀態，使之盡可能選擇高分行為。RL 不是簡單學習運算一個結果，而是學習問題的一種求解策略。

圖3 強化學習簡要模型Fig.3 Brief model of reinforcement learning

DRL 是DL 和RL 的結合，同時具有感知能力和決策能力。具體來說，DRL 通過RL 來定義問題本身和優化目標函數，DL 來解決狀態表示、策略表達等問題，DNN 來擬合RL 中的值函數、策略，然后采用誤差反向傳播算法來優化目標函數。DRL 是一種端到端的感知與控制系統框架，一種更接近人類思考的ML 方法。從圖4 可以看出，DRL 結構與RL 結構類似，為解決復雜決策系統提供方便。

圖4 深度強化學習簡要模型Fig.4 Brief model of deep reinforcement learning

RL 根據馬爾可夫決策過程（Markov decision process，MDP）可以分為基于模型的RL 算法和無模型的RL 算法，其原理分別是基于DP 和蒙特卡羅方法，RL 算法的具體分類見圖5。

圖5 強化學習主流算法Fig.5 Mainstream reinforcement learning algorithms

（1）強化學習

RL 可以建模為一個MDP，其過程可以用五元組(,,,,)表示。其中表示環境的狀態集合，表示智能體的動作集合，是各個狀態的轉移概率，是采取某一動作后到達下一個狀態的獎勵值，是折扣因子。

MDP 可表示成：

的概率：

給定策略(|)，智能體與環境一次交互過程的軌跡所收到的累積獎勵為總回報：

其中，∈[0,1]是折扣率，當接近于0 時，智能體會注重短期回報，而當接近于1 時，智能體會注重長期回報。

最優策略是每個狀態所獲得的總回報最大的策略，最優策略的目標函數為：

（2）基于策略梯度的深度強化學習

基于策略梯度（policy gradient，PG）的DRL 常應用于狀態空間過大或連續空間的RL 問題上，它不需要計算值函數，可以用DNN 來表示從狀態空間到動作空間的一個參數化映射函數=π()。策略搜索是通過尋找參數使得目標函數π()輸出概率最大，直接計算與動作相關的PG，沿梯度方向調整動作，好的行為會增加被選中的概率，不好的行為會減弱下一次被選中的概率，是一種端到端的輸出形式。

通常選擇隨機梯度下降（stochastic gradient descent，SGD）的REINFORCE 算法對策略的參數進行訓練優化：

其中，(τ)為作為起始時刻收到的總回報。

采用REINFORCE 算法求解TSP 問題會導致不同路徑之間的方差很大，從而模型結果難以收斂，這是高維空間中使用蒙特卡羅方法普遍存在的，為此引入一個和a無關的基準函數(s)來減小PG 的方差，其中(s)和(τ)相關性越大效果越好，一個很自然的選擇是令(s)作為值函數V(s)，其中帶基準線REINFORCE 算法中參數的值函數和策略函數的更新如下：

（3）基于值函數的深度強化學習

2013 年Mnih 等人提出深度Q-網絡（deep Qnetwork，DQN）算法，2015 年Mnih 等人又改進了DQN 算法，使其訓練過程具有穩定性。此算法是DL與RL 的首次結合，采用DNN 端到端地擬合Q-學習中的Q 值，充分發揮出DNN 對高維數據處理的能力，其中關鍵的評估策略π(|)可分為兩個值函數：狀態值函數和狀態-動作值函數。

狀態值函數的策略期望回報可以分解為：

從狀態開始，策略得到的期望總回報：

狀態-動作值函數是指初始狀態為并執行動作，然后通過策略得到期望總回報：

（4）基于行動者-評論家的深度強化學習

行動者-評論家（actor critic，AC）算法是結合PG和時序差分（temporal difference，TD）的一種RL 算法。行動者通過策略函數π(,)學習到一個更高回報的策略。評論家經由值函數V()表示，對當前策略的值函數進行估計，即評估行動者策略的好壞。借助于值函數，AC 算法可以進行單步策略更新參數，不需要所有回合結束再更新參數，如Lillicrap等人采用深度確定性策略梯度（deep deterministic policy gradient，DDPG）來實現AC 算法。

DeepMind研究人員基于AC 算法，提出它的變體A3C，即多個智能體并行學習，以固定的時間間隔但不同步地去探索環境，實時更新權重，然后讓其主網絡接受這些權重，這樣每個智能體都可以改善主網絡，并且智能體之間可以相互激勵，以便更好地訓練參數，增強模型的穩定性。針對A3C 算法智能體的異步性，DeepMind團隊接著提出A2C 算法模型，其更新都是同步的，且均在較大批次上運行，這樣可以更好地利用GPU 加速。針對訓練過程中權重更新不穩定的問題，Schulman 等人提出近端策略優化算法（proximal policy optimization，PPO），修改了A2C 算法的損失函數，解決訓練不穩定的問題。同時為了更好地激勵智能體自主探索環境，加快訓練速度，Haarnoja 等人基于AC 算法提出柔性行動者-評論家算法（soft actor-critic，SAC），它可以很好地學習獎勵，還能最大化其行為的熵，即盡可能地讓智能體的行為不可預測，同時還能獲得更大的獎勵。由于RL 中經常會出現獎勵的稀疏性，這使智能體的學習效率很低，為此Pathak 等人提出Curiosity-based的探索算法，讓智能體極端好奇地去探索環境，利用好奇心這一特性，讓智能體嘗試預測接下來的行為動作，并預測與結果不吻合的值，讓獎勵成為智能體固有的性質，而不是從環境獲得,有利于智能體進行高性能計算。為了更好地理解RL 主流算法，可以參考劉全等人和Li對RL 的研究綜述。

2 強化學習求解組合最優化問題的分析

2.1 組合最優化問題的求解難點

針對NP-難的COP 問題實例進行快速求解，傳統方法是以設計近似算法為主，這類算法都是針對問題本身而設計的。首先需證明所求解的問題是存在近似算法的，比如：假定P ≠NP，一般形式的TSP 問題沒有近似算法；NP 難解的KP 問題沒有多項式時間算法；對任意的＞0，BP 問題不存在近似比保證為3/2-的近似算法。其次考慮要求解的問題是否可以歸約到其對偶問題上求解（利用線性規劃的思想）。不論如何設計算法都需要對其正確性進行證明并找到合適的緊例子，才可以說明算法的嚴謹性及對算法的分析是好的，因此許多COP 問題的算法設計需要大量的人力和專家的經驗。在未來，隨著科技發展和進步，對求解各種COP 問題（變體問題）的要求會更高，在優化算法設計上要取得重大的突破也是困難的。

同時，針對同一個COP 問題的求解，常常會出現下述情況，先前的求解對后面問題的求解基本沒有幫助，但是大多數優化問題又具有相同的優化結構，而傳統算法的設計不僅沒有很好利用相同問題之間的相似性，還難以考慮動態及隨機因素，由此建立的數學模型泛化能力弱，不能很好地遷移到相同問題的不同實例上。比如為匹配（matching）問題和SCP問題設計近似算法時，會立即遇到下述困難，為確定近似比，會對算法產生的邊費用以及最優解的邊費用進行比較，其中不僅尋找最優解是NP 難解的，而且計算最優解費用也是NP 難解的，這正是此類問題的難點所在，即使通過確定OPT 的下界方法來保證近似比，還需尋找不同COP 問題的對偶問題，這個過程也是困難的。假如通過上述方法確定了下界，想要改進基數頂點覆蓋的近似保證，這是不可能的，因為考慮二部圖K給出的無限實例族，說明近似算法的分析是緊的，以這種OPT 的下界方式建立的近似保證，不可能設計出比它更好保證的近似算法。

隨著人工智能、大數據時代的到來，COP 問題實例的規模不斷增大，隨之會出現“組合爆炸”的現象，相關問題計算的時間和空間復雜度會呈指數增長，傳統方法很難快速求解大規模性的實際問題，即使解決了這類問題，求解時間和花費也是人們無法接受的。在權衡時間和精度的條件下，目前傳統算法仍然是求解NP 問題的有效方法，但高效求解大規模COP 問題實例及其變體問題成為一個很大的挑戰。在P ≠NP 的假設下，放眼國內外專家團隊對COP 算法的研究，傳統方法在短時間內不會取得重大突破，未來的發展是基于線下訓練、線上求解的高性能計算設計上。

這款臻釀標志著Penfolds當代釀制工藝，突出地域特色的同時，也代表了法國橡木桶釀制赤霞珠的成熟技巧，既是Penfolds精巧技藝的映射，同時也是Penfolds對多樣性的不倦追求。

2.2 強化學習求解組合最優化問題的優勢

許多COP 問題都是NP 難解的，設計算法的過程本身難度就很大，且不容易被刻畫，無模型的RL 方法可以通過智能體與環境的不斷交互，學習到相應策略，模型訓練完成后，短時間內給出一個高質量解，甚至比傳統算法求解的質量要高。如Alipour 等人提出一種遺傳算法和多主體RL 算法結合的混合算法來求解TSP 問題，文獻[52]采用GA-MARL+NICH-LS 算法使得求解的精度高于幾個傳統算法；Fairee 等人提出一種采用RL 算法更新解的模型和基于人工蟻群的組合變體算法，文獻[53]在6 個測試集上測試，在收斂速度上，RL 更新的解快于人工蟻群算法。

針對傳統方法難以解決多維度的問題方面，RL可以采用值函數近似和直接策略搜索等算法，使問題的描述更加全面，從而得到更高質量的解。如Hu等人提出一種多智能體RL 框架求解多重旅行商問題（multiple traveling salesman problem，MTSP）。網絡架構由GNNs 和分布式策略網絡組成，利用RL 算法訓練模型參數，采用S-樣本（批次訓練）的方法減少梯度方差，提高模型的整體性能。針對大規模問題求解，該框架學習的策略優于整數線性規劃和啟發式算法。

針對求解動態和受隨機因素影響的問題上，RL可在智能體與環境之間的交互以及狀態轉移過程中加入隨機因素，增強模型的魯棒性，且模型一旦訓練完成，對同一問題的變體，也可以很好地適應新數據的變化。如Yao 等人提出一種端到端的RL 框架求解COP 問題，核心思想是把狀態空間作為問題的解，解的擾動信息作為智能體的動作空間。模型利用GNNs 抽取潛在的表征信息，對狀態行為進行編碼。推理階段采用深度Q-學習改善解（轉換或交換向量標簽）的質量，得到問題的最優策略。在Max-cut 和TSP 問題上，此模型相比學習算法和啟發式算法有更優的表現和泛化能力，更好地適應動態和隨機因素。

目前，DL 的實驗平臺配置逐漸完善，如Pytorch、TensorFlow 等DL 框架，這些面向對象的開源庫，降低了各位學者的使用門檻，還有硬件設施GPU、TPU 的快速發展，使得COP 問題會在更短的時間內得到顯著的優化效果。利用RL 和計算機科學的這些優點，對求解路徑優化、庫存控制以及車間工件調度等COP 問題領域的大規模動態問題、隨機決策問題、各種變體問題會更為有利，為COP 的研究提供一種新方法。雖然處于初級階段，但也取得一定的成果，說明此方法求解COP 問題的可行性。具體來說，采用RL 求解COP 問題的優勢總結如下：

（1）泛化能力的增強：傳統方法對于一個新問題或者其變體問題，大多都需要重新設計新算法，然而ML 有讓算法具有學習的能力，從算法中學習設計算法，替代手工設計算法。模型一旦訓練完成，其參數可以相互調用，通過遷移學習的方式傳遞給相應的策略函數，從而在給定一個新問題時能夠有效快速地獲得解。

（2）求解速度的加快：傳統的算法是基于初始解的迭代，RL 對一些COP 問題可以產生質量較高的初始解，不斷更新解得到更優的解。DRL 采用DNN 對模型進行合適的特征表示，進而降低求解空間的大小，即減少了搜索寬度和深度。

（3）伸縮性的提高：RL 中一些算法可以降低COP 問題的時間復雜度，再結合GPU、TPU 的加速計算，使其應用于求解大規模的COP問題。模型一旦訓練完成，可以適用于不同的COP 問題，無需為每個問題設計新的算法或重新建立新的模型，從而避免人力資源的浪費，為實時求解動態COP 問題成為可能，以便高效求解實際生活中所面臨的眾多NP-難問題。

（4）初始解的要求降低：DL 中的SL 需要大量訓練數據作為標簽，COP 問題中生成這些數據需要解決大量的NP 難問題，獲得標簽的代價是巨大的，限制了SL 的適用性。然而RL 在給定一組實例解時通過計算優化目標來評估解的質量相對容易，在大多數RL 的框架中，其目標是學習一種隨機策略，以高概率輸出高質量的解。訓練出的模型可以在各種復雜的真實環境中更好地泛化，減少對數據標簽的依賴和未知數據的擾動。

2.3 強化學習與組合最優化問題的結合分析

首先RL 用于序貫決策，即根據當前的環境狀態做出相應的行為選擇，并根據行為的反饋不斷調整自身的策略，從而達到特定的學習目標。COP 問題即在離散空間中選擇事件的最優次序、編排等，與RL的行為選擇具有天然的相似性。以經典的TSP 問題為例，當任意兩城市之間的距離與城市排列順序無關時，定義環游長度如下：

首先將TSP 問題建模成MDP，再利用RL 相關算法訓練參數，學習到一個最優策略(|)以較大概率輸出路徑長度最短的環游，該策略可以建模為：

其狀態、行為、獎勵、策略表示為：

（1）狀態：已經訪問過城市的坐標集合。

（2）狀態轉移：根據已經訪問過的城市和城市的坐標計算接下來將要訪問的城市概率。

（3）動作空間：第步將要選擇的城市π。

（4）獎勵：已訪問過城市路徑總距離的負數（最短路徑）。

（5）策略：狀態到動作的映射，即得到的是選擇城市的概率p(|)。

通過這樣的建模，簡單地實現了RL 與COP 問題的結合，不斷地訓練相關參數得到更為準確的策略，為COP 問題求解提供一種全新的思路。

3 強化學習求解組合最優化問題的方法

目前基于RL 求解COP 問題的方法主要分為基于NCO 模型的求解方法、基于動態輸入的COP 模型的求解方法、基于圖結構模型的求解方法、基于RL結合傳統算法的求解方法、基于改進RL 模型的求解方法等五大類，本文主要對以上方法的研究進行綜述，對各類代表性研究所解決COP 問題的研究問題、算法模型、優化效果進行對比分析（見表1），并對不同方法局限性及使用場景的限制進行了綜合評述。

3.1 基于神經組合最優化模型求解方法

為克服SL 樣本需求的問題，Bello 等人把NN和RL 相結合，提出NCO 模型。文章以PN 為基礎，采用REINFORCE 算法訓練模型參數，將TSP 問題的每個實例作為一個訓練樣本，目標函數是實例中城市的最短環游長度。模型引入critic 網絡為基準構建與策略網絡參數無關的估值網絡，降低訓練方差，該網絡使用均方誤差（mean square error，MSE）評判估值網絡和SGD 法來優化目標函數，還指出結合推理搜索的求解方式能進一步改善解的質量。由于評估一條環游長度需要很小的計算量，可以讓模型輸出更多候選解，然后在求解空間中找到最優解，加快求解速度。文獻[32]的實驗結果顯示，NCO 求解100-TSP問題的環游長度優于Christofides算法和專業求解器，200-Knapsack 達到最優解。

針對傳統的搜索方法依賴于啟發式算法且在許多COP 實例中采用啟發式算法求解速度慢等問題，Chen 和Tian對此提出NeuRewriter 框架求解COP問題，以迭代的方式不斷改進問題的解直到收斂，從而加快求解速度。整個策略分為兩部分：區域挑選策略和規則挑選策略。區域挑選策略用于選取當前狀態（每個解是一個狀態）要更改的區域；規則挑選策略用于選取重寫的規則。文獻[57]采用RL 中的QAC 算法訓練模型參數。實驗結果顯示：簡化表達超過Z3 模型；JSP 超過DeepRM 模型和專業求解器；CVRP 超越了部分基于ML 的方法，比基于啟發式算法和DNN 直接生成解的質量要高。

為進一步提高模型的泛化能力，Joshi 等人結合SL 和RL 訓練100-TSP 問題，測試模型在一個變化的圖上，最大到500 個節點。在固定大小的圖上，采用協同訓練的方式會更接近最優解，用GCN 編碼替代Transformer 架構編碼對模型求解影響較小，還證明了模型的泛化能力取決于RL 模型中的學習范式。Joshi 等人之后改進NCO 模型，將小范圍TSP問題泛化成求解大范圍的TSP 問題（128 萬個節點）。

Miki 等人針對經典的TSP 問題提出了DL 和RL 算法（EV-貪婪+EV-2opt）結合的框架。此方法采用卷積神經網絡（convolutional neural network，CNN）將TSP 問題的最優路線作為圖像進行卷積學習操作。推理階段結合EV-貪婪和EV-2opt 算法，高效輸出最優解，同時比較2opt 和S2V-DQN 算法在TSBLIB 數據集上的優化效果。文獻[60]結合DL 和RL 模型在求解質量和速度上優于單個模型，通過SL 得到的解再結合RL 訓練可以提高解的質量。

鑒于DNN 模型以端到端的方式輸出問題的解，Li等人采用DRL方法近似求解覆蓋商問題（covering salesman problem，CSP）。模型以PN為基礎，利用MHA采集結構信息，加入動態嵌入模型處理動態信息，使用REINFORCE 算法訓練模型參數。該模型下求解CSP 問題的時間比傳統啟發式算法（LS1、LS2）快20倍，相比PN、動態指向型網絡、AM 模型有更好的收斂性，且模型一旦訓練完成（時間較慢），可以泛化到多種類型的CSP 問題上。

上述PN 模型原理是將COP 問題的實例編碼成向量，使其在隱藏層輸出，最后解碼時通過Softmax對向量進行處理，輸出具體實例中較大的概率向量，且輸出向量維度與輸入向量維度一致，具體模型如圖6 所示。

圖6 Pointer networks模型Fig.6 Pointer networks model

表2 NCO 模型的局限性分析Table 2 Limitation analysis of NCO model

3.2 基于動態輸入的組合最優化模型求解方法

針對VRP 問題的輸入是動態變化的，使用PN 無法直接求解這類問題，Nazari 等人將PN 拓展成能夠處理動態信息的COP 模型，采用一維CNN 替代編碼輸入層的LSTM，即替換編碼部分，保留解碼部分，這樣使得模型的輸出和輸入的順序無關，從而有效地解決動態問題的輸入對問題求解的影響。模型的訓練采用了經典的PG 方法，并加入貪婪算法和波束搜索（beam search，BS）兩種推理技術提高解的質量。模型一旦訓練完成，對于不同規模的實例，無需重新訓練。文獻[62]的實驗是在50 和100 規模的VRP 問題上進行的，運用該模型在求解質量上相比經典Clarke-Wright savings heuristic、Sweep heuristic啟發式算法有一定優勢。推理階段結合BS 后求解時間對比專業求解器有60%以上的優勢。

鑒于Transformer 在語義信息深層特征的提取上有良好表現，Kool 等人改進其架構，編碼部分中未采用位置編碼，使節點嵌入與順序無關。模型沿用了Transformer 架構中的MHA 和前饋FF 結構來得到每個城市對應的節點嵌入。解碼采用了經典的自回歸調整模式，并引入上下文節點來表征解碼時的上下文向量，它包含了圖嵌入層以及第一個節點（它是起點也是終點）與前一個輸出節點的嵌入。最后解碼結構加入一個單層AM（即=1 的MHA），通過激活函數softmax 輸出，即為當前一步的輸出。文獻[63]采用經典REINFORCE 算法訓練模型參數，其中基準函數通過策略模型進行確定的貪婪搜索得到。實驗考慮了幾種路徑問題：TSP和VRP及其變體問題（SDVRP、PCTSP、SPCTSP），實驗結果顯示基于確定貪婪搜索的方法在求解質量和速度上優于先前端到端的模型，在100-TSP 問題上的優化性能超越了傳統啟發式算法，且模型的收斂性明顯優于傳統方法。

許多RL 模型會受到實例輸入維度大小的影響，Emami 等人提出一種基于SPG（sinkhon policy gradient）算法學習策略模型，克服上述問題，并結合AC 架構求解COP 問題中的排列問題，該模型可以端到端地求解TSP 問題和Matching 問題，并把問題遷移到更大規模的圖問題中求解。

更進一步，Oren 等人提出一個離線學習、在線搜索的框架（SOLO）求解COP 問題，該框架的求解過程可以看作一個MDP，采用深度Q-學習網絡從圖模型的狀態行為空間中學習出一個最優策略，并結合蒙特卡羅樹搜索（Monte Carlo tree search，MCTS）提升模型的穩定性和泛化能力等。文獻[61]的實驗在PMSP 和CVRP 兩個COP 問題上進行，實驗結果顯示，該框架下在求解時間和模型的表達能力上超越了專業數學求解器和前沿的學習算法以及傳統的啟發式算法。

為了使智能體在每一個回合限制中可以探索動態的節點信息和隱藏層的信息結構，快速處理實例中的動態隨機因素，Bo 等人提出動態的編碼-解碼架構，建立一個動態AM 模型求解VRP問題，文獻[66]實驗結果顯示此模型求解VRP 的表現優于先前RL的方法且有很強的泛化能力。

上述模型中，AM 編碼-解碼的結構不受COP 問題輸入和輸出序列長度的限制，結合RL 算法后文獻[62-66]中模型表現出顯著的優勢，可以廣泛應用于求解COP 問題，具體模型如圖7 所示。

圖7 Attention 模型示意圖Fig.7 Schematic diagram of Attention model

2018 年Nazari 等人提出了一種求解具有動態因素COP 問題的模型，整體框架以AC 為基準，對PN 進行改進。借鑒循環神經網絡（recurrent neural network，RNN）的原理，針對處理時間相關性較強的COP 問題，編碼采用一維CNN 替代RNN 序列元素的嵌入。解碼階段利用AM 融合動態和靜態的嵌入向量，最后通過softmax 函數進行歸一化處理，從估值網絡中得到每個輸入元素的概率分布，再通過策略網絡輸出嵌入向量序列并進行加權求和，以較大概率輸出解。針對RL 處理動態信息在決策過程中出現的不穩定性、有效節點信息的稀疏性問題，限制模型的優化效果，表3 分析了基于動態輸入的COP 模型求解方法的局限性。

表3 動態輸入模型的局限性分析Table 3 Analysis of limitation of dynamic model

3.3 基于圖結構模型的模型求解方法

GNNs 是基于DL 的方法處理具有圖結構信息的一種網絡結構，通過聚合、更新、融合等操作對圖結構進行特征提取，快速處理圖數據。鑒于此，Dai 等人將RL 和GNNs 結合，提出一種新的優化算法（S2V-DQN），即將RL 算法與圖嵌入結合，充分利用圖中的特殊結構，讓S2V-DQN 模型泛化到更多新問題的實例中。文獻[67]利用GNNs 中S2V 的方法并配合使用RL 中Q-學習算法求解MVC、Max-cut、TSP問題。同時對比NCO 模型與啟發式算法，該模型將TSP 和MVC 問題的規模分別擴大到300 個和500 個節點，同時可以將訓練完成的圖模型參數遷移到規模更大的圖上（最大1 200 個節點）。

Drori 等人采用RL 訓練GNNs 模型參數的方法，提出一種基于GNNs 的RL 架構，模型采用GAT編碼，解碼時加入Attention，求解MST、TSP、VRP 等經典COP 問題。文獻[68]的實驗訓練過程在小圖和隨機圖上，測試過程在大圖和真實圖上，最終使得所求解問題的近似比接近1。

針對處理百萬級大小圖上的困難問題，如何讓算法解決訓練集中類似分布的問題實例，并將之延拓到更大規模的問題（百萬級節點）上，Mittal 等人提出GCOMB 框架（由SL 和RL 模型結合組成）克服上述問題，整個算法分為訓練和推理兩個階段。訓練階段第一步通過SL 的方式訓練GCN 中的參數，采用新的概率貪婪機制預測單個節點的質量和修剪不是解空間的集合，其本質上是讓嵌入的點集合能夠反映每個節點對于解的重要程度，用于構造嵌入輸入；第二步采用RL 中Q-學習算法體系分析剩余高質量節點，把高質量解挑選出，作為COP 問題的解。推理階段，先用訓練完成的GCN 模型作為嵌入，然后通過Q-學習的Q 函數迭代計算問題的輸出解，即用貪心算法以增量方式構造解。文獻[69]的實驗結果顯示，此框架在求解最大流問題的速度上比最前沿的學習算法快100 倍，解的質量也略有提高。

為了更好解決具有圖結構性質的COP 問題，Barrett 等人提出探究組合最優化（ECO-DQN）的方法框架，其模型架構由S2V-DQN、RevAct、ObsTun、IntRew 組成。其中S2V-DQN 是Dai 等人提出的方法；RevAct 指允許一個節點翻轉多次仍可以被選擇的操作；ObsTun 指求解狀態包含7 個觀察步驟，如基于頂點狀態等，提供的信息呈現多元化，用于確定選取相應動作的價值，實時提供歷史信息避免出現過擬合狀況，在有限步的回合保證外部和內部獎勵回報符合馬爾可夫特性；IntRew 指通過獎勵塑造的形式，當達到新的局部最優解時，給一個小的中間獎勵作為內部獎勵，很好地克服獎勵稀疏的問題。文獻[70]的實驗結果顯示，該框架下在Max-cut 上的求解效果優于SOTA 的RL 方法。該算法可以從任意的初始解迭代，因此可以與其他搜索方法相結合，進一步提升解的質量。

隨著AlphaGo Zero的成功應用，Abe 等人將其思想延拓到COP 問題上，提出了CombOpt Zero 框架。模型利用MCTS 算法，在訓練時提升了探索效率，增強了模型的泛化能力，在進行決策推理時增強了智能體的穩定性。一般的COP 問題與圍棋相比有兩點不同：一是狀態由不同大小的圖表示，通過GNNs 處理非歐幾里德數據，能夠抽取數據中的有效特征；二是獲得獎勵的值域不固定，文獻[72]中通過回報歸一化技術來解決。文獻[72]還在網絡模型中嘗試不同GNNs 的變體模型，如圖同構網絡（graph isomorphism network，GIN）、不變圖網絡（invariant graph network，IGN）。實驗在MVC、Max-cut、MC 問題上結果顯示此模型的泛化能力優于S2V-DQN，且求解速度更快。

為了更好利用圖模型的優勢，Bresson 等人將Transformer 架構應用到求解TSP 問題上，模型采用RL 算法訓練參數，通過自注意力機制編碼，解碼中加入BS 推理技術。文獻[73]的實驗結果顯示，該框架的表現能力超越了基于學習的啟發式算法，采樣2 500 次后，50-TSP 問題的最優間隙為0.004%，100-TSP 問題的最優間隙為0.39%。

針對COP 中出現的大量與圖模型相關的問題，采用GNNs對圖模型進行預處理，文獻[66-74]中GNNs架構對求解COP 問題顯示出優異的效果，未來RL 和GNNs 模型的結合是一個較好的研究方向，GNNs 模型如圖8 所示。

圖8 GNNs模型示意圖Fig.8 Schematic diagram of GNNs model

2017 年Dai 等人提出一種處理圖結構的COP問題的新方法。模型框架在PN 架構基礎上加入Attention、Transformer、GNNs 等結構處理圖信息。編碼-解碼時，采用圖嵌入操作，即將圖中的頂點信息映射成一個低維稠密向量，保證在原圖中相似的低維表達空間也接近，從而有利于信息提取。模型參數的訓練大多采用Q-學習和Q-迭代的RL 算法，從而克服了獎勵延遲問題，保證參數更新的穩定性和獨立性。圖的特殊結構可以承載更多的節點信息，讓網絡模型學習到有效的特征信息，從而擴大COP 問題的求解范圍，同時圖的拓撲性質導致RL 學習困難，巨大的解空間在搜索過程中也是困難的，限制了圖結構模型的優化效果，表4 分析了基于圖結構模型的求解方法的局限性。

表4 圖結構模型的局限性分析Table 4 Limitation analysis of graph structure model

3.4 基于強化學習結合傳統算法的求解方法

以PN 為基礎的RL 模型在求解COP 問題上已經展現出良好的效果，為提高解的質量，Deudon 等人改進Bello 等人的NCO 模型，編碼層延續了Transformer 架構，其編碼的網絡架構均由層疊的自注意力機制和逐點的全連接層組成，編碼層沒有使用LSTM 架構。此模型中采用自注意力機制替換Seq2Seq 模型中的Attention。在解碼層改進策略網絡，采用PG 和REINFORCE 算法訓練模型參數。模型在解的質量與運行時間等方面的表現結果與Christofides算法的表現結果相當，可以快速求解大規模的路徑優化問題。實驗還將50-TSP 問題的模型參數遷移到100-TSP 問題上進行求解，其表現結果相當，說明該模型有很好的泛化能力。此外，推理階段結合2-opt推理技術，可以快速提升解的質量，體現出ML 與傳統算法結合的優勢。

針對如何有效找到最優解的確界問題，Cappart等人提出一種利用DRL 來確定變量順序的方法。決策圖（decision diagram，DD）是一種分層的有向無環圖，它得到的上界和下界比傳統方法更好，由于界的質量又依賴于構建DD 過程中變量的選取順序，采用NN 擬合Q-學習中Q 值的方法來確定變量順序。文獻[75]的實驗數據表明此方法所確定變量順序的結果比利用線性規劃取得的更優。針對DRL 求解TSP 問題泛化能力弱且沒有一個系統的方法去提高解的質量及無法有效證明近似比等缺陷，Cappart 等人又提出了一個基于DRL 結合約束規劃求解COP問題的模型，為了更好地結合這兩種方法，對于給定的COP 問題，首先采用動態規劃的方法對問題進行建模，然后將模型編碼成DRL 和約束規劃可以學習的輸入形式，在編碼中加入約束規劃可以更好地探索解空間，其中RL 中的網絡使用了GAT 和Transformer架構作為圖嵌入。文獻[76]還考慮了三種約束規劃搜索策略：BB、迭代有限差異搜索法（iteration limited discrepancy search，ILDS）、基于搜索的重新啟動法（restart based search，RBS）。此方法求得的解與業界的專業求解器相比，在帶時間窗的旅行商問題（traveling salesman problem with time window，TSPTW）和4-PORT 問題上有很好的優化效果，體現了DRL 結合約束規劃的方法具有一定優勢。

為擴大求解范圍，Gao 等人采用AC 框架去學習一個局部搜索啟發式算法求解VRP 問題，模型通過GAT 進行編碼操作和使用GRU（gate recurrent unit）架構進行解碼操作。兩者結合的學習方式可以解決大規模（400 個節點）的VRP 問題，優化效果超過其他傳統的啟發式算法。

更進一步，Costa 等人提出一種由DRL 的方法學習2-opt操作的局部搜索啟發式算法。模型為一個策略神經網絡，即采用PG 算法學習2-opt 操作，從隨機策略得到一個循環解，采用點注意力機制，使模型更容易拓展到更一般的情形k-opt 操作。文獻[78]的實驗結果顯示，此模型學習到的策略與先前的DL 方法對比，該方法會以更快的收斂速度逼近問題的最優解。

在RL 算法的基礎上，為提高模型的伸縮性和魯棒性，Zheng 等人基于變鄰域搜索和LKH3 算法，提出一個VSR-LKH 新框架求解TSP 問題。該框架采用Q-學習、Sarsa、蒙特卡羅三個RL 算法取代LKH3算法的遍歷操作，即讓訓練好的模型自動挑選適合的邊加入到候選集合中。實驗結果顯示，在TSPLIB數據集上測試，該方法求解的精度超越了傳統的LKH3 算法。

該思路是近年來諸多學者嘗試的一種新方法，在RL 中加入傳統算法構造解的方法已經在COP問題中取得較好成果。文獻[52,54,74-79]中的方法大多數還是需要結合一些傳統的方法，如經過貪婪搜索、2-opt 操作、BS、采樣（sampling）、LK 等處理后，解的最優間隙會隨之降低，進一步加快搜索時間和提升解的質量，甚至會超越傳統的SOAT 模型。RL結合傳統方法的策略表明目前的模型仍然有較大的優化空間，其中RL 模型學習效率低、收斂慢等問題會對COP 問題的求解造成影響，表5 分析了基于RL結合傳統算法模型的求解方法的局限性。

表5 RL 結合傳統算法模型的局限性分析Table 5 Limitation analysis of RL combined with traditional algorithm model

3.5 基于改進強化學習模型的求解方法

針對LHK 和傳統算法中出現的求解速度慢及求解節點稀疏等問題，使用經典RL 模型不能很好選擇高質量解，為此Lu 等人改進框架結構，首次提出一種基于學習迭代的方法求解CVRP，采用分層和REINFORCE 算法訓練模型。文獻[81]中模型優化后的解在速度上超越傳統算法，并且求解100-CVRP 問題上達到了目前最好的結果（平均花費15.57）。

針對進化算法無法解決大規模優化問題的缺陷，Li 等人改進框架結構，提出一種基于DRL 解決多目標COP 問題的框架（DRL-MOA），在PN 中融入分解策略和鄰居多參數傳遞策略，采用AC 算法訓練模型參數。文獻[82]的實驗結果顯示，該模型下求解動態TSP 問題、多目標TSP 問題的速度和泛化能力超越NSGA-Ⅱ、MOEA/D、MOGLS 等經典多目標優化模型。

為了讓智能體快速、準確調整自身的行為（通過環境和其他智能體的交互），Silva 等人對智能體改進，加入一個新的自適應技巧，提出多元啟發式算法優化多元智能體的框架（AMAM）。文獻[83]的實驗結果顯示，VRPTW 和UPMS 兩個COP 問題在AMAM框架下求解的質量優于其他傳統算法和單智能體優化框架。

更進一步，Tassel 等人提出一個高效的DRL 模型求解PMSP 問題，該模型以端到端的形式輸出解，即在一個時間方案的限制下，模型可以自動地學習調度工作方案。文獻[84]的實驗結果顯示，該方法的表現超越了現有的DRL 方法，接近于當前SOTA 傳統COP 問題的求解方法。

針對現有框架難以求解大規模TSP 和TSPTW問題，Ma 等人改進框架結構，提出圖指向型網絡（graph pointer network，GPN）架構。具體采用分層強化學習（hierarchical reinforcement learning，HRL）訓練模型參數，編碼由點編碼和圖編碼兩部分組成，點編碼依賴于LSTM 架構，由此得到城市的點嵌入，圖編碼依賴GNNs 架構，得到城市的圖嵌入。解碼過程中加入Context vector操作后，使得attention 更好地分配到相應節點，高效輸出COP 問題的最優解。文獻[85]的實驗結果顯示該模型下求解小規模（50/100個節點）TSP 問題的模型參數可以很好地遷移到大規模（500/1 000 個節點）TSP 問題上，說明此操作提高了GPN 模型的泛化能力。此方法求解TSPTW 問題在時間和精度上超越了專業求解器和蟻群算法。另外，實驗證明了分層圖指向型網絡（hierarchical graph pointer network，HGPN）模型的優化效果和收斂速度均優于GPN。

Delarue 等人提出一種基于值函數的RL 框架（RLCA-16）求解CVRP 問題。該框架下每步更新考慮單個距離，而不是等待模型訓練完成后獲取距離，通過一個直接的策略迭代更新每步距離。文獻[86]在CVRPLIB 數據集上測試，實驗結果顯示，相比其他RL 算法和傳統運籌優化算法有較好的效果，該模型平均最優間隙達到1.7%，并將此模型推廣到求解PCTSP 問題上。

該思路是近年來諸多學者進一步求解COP問題的一種新方法。針對目前RL 模型存在訓練的不穩定性和輸出難以收斂的問題，可以通過不斷改進RL 算法或者采用更多復雜DRL 的方法，更好地適應各類COP 問題的求解。現有DRL 模型中難免會存在價值網絡、策略網絡獎勵機制構造不合理的情況，網絡結構的瑕疵會對求解的質量造成影響，表6 分析了基于改進RL 模型的求解方法的局限性。

表6 改進RL 模型的局限性分析Table 6 Limitation analysis of improved RL model

3.6 經典COP 問題的實驗對比

由于TSP 是COP 問題中的經典問題，TSP 又是VRP 的特例，這兩個問題都是運籌學和CO 領域的熱點問題。基于RL 求解COP問題的方法在TSP、VRP以及它們的變體問題上已經取得較好結果，相比傳統算法，該方法是近年來研究的熱點內容。表7、表8對上述求解方法在不同規模TSP、VRP 上的優化效果進行實驗對比，實驗數據來自各個文獻的實驗結果，均通過Pytorch、TensorFlow 深度學習框架實現。

表7 不同模型在TSP 上的優化效果比較Table 7 Comparison of optimization effects of different models on TSP

表8 不同模型在VRP 上的優化效果比較Table 8 Comparison of optimization effects of different models on VRP

通過實驗結果比較可以看出，Joshi（BS）和Costa的方法在20-TSP 問題上與專業求解器的優化效果基本相同，但運行時間相對較慢。Kool（GS）的方法可以在短時間高效求解，但精度略低于最優解。Bresson的方法可以達到最優解，求解速度超越了傳統的優化器和目前的SOTA 模型，但求解范圍有限。總體來看，目前RL 方法求解TSP 在精度、泛化能力等方面有許多問題待解決，僅僅在推理速度方面超越目前最先進的求解器Concorde、Gurobi、OR-Tools。改進Transformer 架構以及結合GNNs提升模型穩定性是未來一個重要的研究內容。

通過實驗結果比較可以看出，Lu和Chen的方法在精度上超越了LKH3 和OR-Tools 等專業求解器，運行時間慢于OR-Tools。Kool的貪婪搜索方法在幾秒內可得到近似解，適用于在線快速求解。近年來多數采用RL 結合傳統算法的方式求解VRP問題，僅僅在推理速度超越目前最先進的啟發式算法LKH3 和求解器OR-Tools。由于VRP 問題復雜的約束條件，目前的整體研究較少，如何選取適合的RL算法和融入傳統算法的思想是未來一個重要的研究內容。

3.7 RL 求解COP 問題的方法總結

由上述綜述方法可見，以RL 模型為基礎的求解方法在求解速度、求解規模上超越了傳統算法，甚至可以求解傳統算法難以解決的問題，是近年來研究的熱點方法，此方法不受人工經驗的限制，可以自動發現求解問題的策略，模型一旦訓練完成，可對任意類似問題進行泛化求解，擺脫了傳統算法針對相同結構問題專門設計算法的弊端。隨著問題規模的增大，RL 的優化效果和速度遠遠超越傳統算法，其中基于RL 結合傳統算法的求解方法、部分改進RL 模型的求解方法取代了人工設計的搜索規則，對搜索算法進行自主學習，但本質上仍然是迭代求解，速度遠不如端到端的模型。基于NCO 模型的求解方法、動態輸入的COP 模型的求解方法、圖結構模型的求解方法等都是以端到端的形式輸出解，解的收斂性和質量難以保證。由于結合PN 和GNNs，加入Attention機制，模型的性能得到提高，權衡優化效果和求解速度，可以根據實際問題的需求選擇不同的優化方法。

基于RL 的COP 求解方法是一個新興的研究領域，處于剛剛起步的階段，到目前為止，取得的成果只能驗證這個思路是可行的，并沒有取得重大實質性的突破，關鍵在于缺少理論基礎和近似比的保證。為了結合兩者的優點，如采用RL 方法并加入相應的后處理操作，直接根據所給定的問題實例以端到端的方式輸出解，或者將RL 算法加入到傳統算法設計中，如建立RL 模型學習策略指導分支定界算法的執行。同時，可以看到一些工作中，基于RL 的方法已經能在一些實例中與傳統SOTA 算法相當，從其發展歷程可以看出，這個方向正隨著ML 中的一些算法的蓬勃發展而快速推進，相信將來會有更多的想法被提出并融入到COP 中，它會成為傳統算法的有力補充甚至會完全替代傳統算法，期待RL 與CO 可以緊密結合，共同發展，推動NP 問題的求解算法與理論進展。

4 研究展望

RL 是ML 中的一個研究熱點，RL 解決問題的方式和學習策略是實現智能化的一個重要途徑，尤其是DRL 這種端到端的感知與決策系統的快速發展，使得這類方法廣泛應用于智能交通、機器人、計算機視覺等領域。COP 問題又是實際生活中普遍存在的，傳統的方法如精確算法、近似算法、啟發式算法等，很難在可接受的時間內獲取到問題實例的最優解。目前RL 求解COP 問題的方法與傳統方法相比，是一種全新的數據驅動的求解方式，也是一個新型交叉學科。

近年來基于RL 求解COP 問題的相關工作已經大量出現，在運籌優化領域已經形成新的研究熱點，如Mazyavkina 等人的綜述主要梳理RL 求解COP問題的進展，提供了運籌優化和ML 的必要背景，比較了RL 算法和傳統優化算法求解COP 問題的效果，說明未來可以采用RL 的方法求解COP 問題。Yang等人的綜述主要針對RL 在COP 問題中的應用，以TSP 問題為例，比較了RL 算法與傳統算法的差異。隨著ML 的發展，闡明了計算能力對RL 中算法的影響，文獻[91]闡明了DL 的方法可以遷移到COP 問題上來，可以優化TSP 問題的結果。Vesselinova 等人的綜述重點梳理RL 解決圖上的COP 問題的相關文獻，以及總結拓展COP 問題在通訊領域中的應用。

雖然RL 理論及其應用已經取得重大進展，現有研究也展現出RL 求解COP 問題的優勢，相關的應用研究仍處于探索階段，希望各位學者可以從以下幾個方面繼續研究：

（1）擴大COP 問題的求解范圍：針對傳統算法求解大規模COP 問題速度過慢的問題，可借鑒分而治之的思想，通過子圖采樣、圖轉換、分割等技術簡化搜索空間的大小，再采用熱圖合并、主動搜索等技術合成解，從而在RL 領域擴大求解范圍。比如研究HRL，即將大規模問題分解成若干子問題來學習層次化策略，再組合子問題的策略形成全局的最優策略。同時如何有效地將其與COP 問題進行結合及解決狀態分解過程的有效信息丟失問題是一個很好的研究點。

（2）求解更復雜、多類型的COP 問題：目前大多數學者的研究集中在經典的TSP、VRP 等問題上，且研究內容相對單一簡單，實際上COP 問題具有動態性、多目標、多約束條件等特征，傳統算法難以求解該類問題以及變體問題。未來在追求模型的精度和快速求解的要求下，基于RL 對多目標優化、多約束條件、在線動態求解等問題進行求解是一個重要的研究熱點。

（3）模型上的改進：目前的研究中，許多優化模型是以端到端的形式輸出解，從而解的質量較差，因此在模型改進上有很大的提升空間。同時BS、MCTS耗時長等問題影響其效率，為了提高求解速度和求解質量，未來可以進一步結合GNNs 和DRL，改進Transformer 架構中編碼-解碼的結構，考慮在網絡結構上結合微分方程數值解的方法（用于網絡參數的權重學習）進行研究，如何提高網絡性能和壓縮模型的大小是一個較好的研究點，進一步改善模型訓練過程中收斂性差、不穩定等問題。

（4）應用范圍的推廣：許多運籌優化問題都滿足序貫決策的性質，與高性能計算相結合，可以應用嘗試快速求解各種決策問題，如何利用基于RL 求解COP 問題的方法高效解決工程實際中的動態路徑規劃問題、在線調度問題是一個重要的研究方向。