深度強化學習求解車輛路徑問題的研究綜述

楊笑笑，柯 琳，陳智斌

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

組合最優化（combinatorial optimization，CO）是運籌學和組合領域的新興學科。組合最優化問題（combinatorial optimization problem，COP）[1]是一類在離散狀態下求極值的最優化問題，在交通、管理決策等領域有著廣泛的應用。日常生活中常見的COP問題有旅行商問題（traveling salesman problem，TSP）、車輛路徑問題（vehicle routing problem，VRP）、車間作業調度問題（job shop scheduling，JSP）、最小頂點覆蓋問題（minimum vertex cover，MVC）、施泰納樹問題（Steiner tree problem，STP）以及裝箱問題（bin packing，BP）等。

先前工作中，傳統算法是求解COP問題的首要方法。傳統算法主要分為三類，精確算法（exact algorithm）[1]、近似算法（approximation algorithm）[1]、啟發式算法（heuristic algorithm）[2]，詳細分類如圖1所示。精確算法[1]是指可求出最優解的算法，求解小規模COP問題有較好結果，但在求解大規模COP問題時不能在規定的時間內輸出最終的結果；近似算法[1]是指在合理的計算時間內找到一個近似最優解，但較多COP問題無法確定近似比的保證；啟發式算法[2]可以根據相關問題快速有效地設計算法，但依賴問題本身，當問題描述發生變化時，需重新設計算法，且可能陷入局部最優解；由于現實世界中具有挑戰性的VRP問題通常受到車輛容量、配送中心數量、車輛行駛里程、時間等限制，因此傳統算法在應用于現實任務時會有求解速度慢、解質量差等不足[3]。

圖1 傳統算法分類示意圖Fig.1 Schematic diagram of traditional algorithm classification

隨著人工智能技術的發展，深度學習（deep learning，DL）[4]在計算機視覺（computer vision，CV）[5]、自然語言處理（natural language processing，NLP）[6]等許多領域取得了突破性的進展。在CV領域[5]，DL取代了人類手工設計算法成為了當前的核心算法；在NLP領域[6]，DL將NLP從統計模型轉到神經網絡（neural network，NN）模型，不斷學習語言特征，使得在大量特征工程的NLP獲得精確的結果；在推薦系統領域[7]，DL可以高效地學習用戶和項目之間的特征，便于從海量數據中挖掘出匹配關系。作為DL一個重要分支，強化學習（reinforcement learning，RL）和深度強化學習（deep reinforcement learning，DRL）[8]主要應用于序貫決策任務，AlphaGo[9]和AlphaGo Zero[10]圍棋算法利用DRL模型結合蒙特卡洛樹（Monte Carlo tree，MCT）搜索，成功擊敗了世界圍棋冠軍，將DRL的理論和應用研究推向新高度，為利用DRL求解VRP[11]開創全新思路。VRP在離散決策空間進行決策變量的最優選擇與RL序貫決策的功能具有天然的相似性，且DRL“離線訓練”“在線決策”的特征使VRP在線實時求解成為了可能。

NN解決VRP問題是Vinyals等人[12]將問題類比為機器翻譯過程，提出了指針網絡（pointer network，PN）模型，使用長短期記憶網絡（long-short term memory，LSTM）作為編碼器，注意力機制（attention mechanism，AM）[13]作為解碼器，從城市坐標中提取特征。但是PN采用監督學習（supervise learning，SL）方式訓練網絡，需要構造大量高質量的標簽，因此大多數研究利用DRL求解VRP問題。除PN模型外，隨著圖神經網絡（graph neural network，GNN）技術的興起，Scarselli等人[14]利用GNN對每個節點特征進行學習，從而進行節點預測，主要求解思路是利用GNN對節點特征進行學習，由編碼器對問題的輸入序列進行編碼，再利用解碼器結合注意力計算方法，以自回歸的方式逐步構造解，根據學習到的特征進行后續的節點預測。進一步地，Ma等人[15]把PN與GNN相結合提出圖指針網絡（graph pointer network，GPN），利用GNN提取計算節點特征，再用PN進行解的構造，提升了大規模TSP問題的泛化能力。與大多數經典啟發式算法相比，基于RL訓練的模型對問題變化具有魯棒性，當問題輸入發生變化時，RL可以自動適應問題變化輸出較優的解。

最近，受Transformer[16]架構的啟發，Kool等人[17]借用Transformer提出新框架，其主要求解思路是利用AM對模型進行改進，提出將輸入元素分為靜動態兩種表示，利用嵌入的方式替代循環神經網絡（recurrent neural network，RNN）的編碼過程對靜動態元素進行向量表示，解碼階段將靜態向量表示輸入到解碼RNN中獲得隱含層向量與動態向量結合，通過AM獲得下一個決策點的概率分布，超越了先前解決路徑問題的優化性能。后續的研究工作大部分是基于Kool等人[17]的AM模型開展的，經過不斷調整編碼器、解碼器的結構以及RL訓練方法，進一步提升VRP的優化性能。

本文對近年來利用DRL方法求解VRP進行文獻綜述，對各種網絡模型的結構進行詳細分析，并比較各個算法模型的優缺點以及優化性能，指出未來求解路徑問題的解決思路，為學者在基于DRL求解VRP方向的研究提供指導。

1 深度強化學習的介紹

本章討論求解VRP的DRL方法，RL通過智能體與環境交互的方式不斷學習，使預期回報最大化。下面介紹RL相關原理和將VRP轉化為序列決策問題的馬爾可夫決策過程（Markov decision process，MDP）[18]，以及經典的RL算法[19]。

1.1 強化學習

RL是智能體在與環境的交互過程中，通過學習策略以最大化提高獎勵或實現特定目標的模型。RL可以建模為MDP，MDP實際就是一個多元組[S,A,P,R,γ]。其中，初始狀態空間S(st∈S)是起點城市或是部分解；A為動作空間(at∈A)，動作是對部分解的添加或者對完整解進行改變；P為狀態轉移概率矩陣；R是獎勵函數，表明在特定狀態下選擇的動作對解決方案造成的影響。γ∈(0,1)是折扣因子，調控智能體考慮短期回報。

RL詳細操作如圖2，智能體執行動作at之后，環境會轉換到新狀態st+1，并給出獎勵信號rt+1，智能體根據新狀態st+1以及獎勵信號rt+1按照訓練的策略π執行新動作at+1。以TSP問題為例，初始環境st為已訪問的城市或起始城市節點，新狀態st+1是實時更新的解決方案，動作at是下一個將要訪問的城市，獎勵信號rt在訪問完節點時（以負的路徑長度）激勵智能體做出下一步決策。

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

1.2 強化學習算法

RL算法[19]主要分為兩大類，有模型學習和無模型學習。有模型學習對環境有提前的認知，可以提前感知優化；無模型學習在訓練速度上遜于前者，但更易實現，在真實場景下可以快速調整到較優的狀態。利用RL解決VRP的方法主要分為：基于值函數的方法和基于策略優化的方法。RL算法詳細分類如圖3。

圖3 機器學習算法分類Fig.3 Machine learning algorithm classification

2 DRL求解車輛路徑問題的思路

2.1 車輛路徑問題的簡單概述

隨著電商在線銷量的增加，物流產業的快速發展，VRP問題一直是COP的研究熱點。如何提高解的精度，加快搜索速度，減少時間復雜度、增強模型泛化能力等是求解VRP最關注的問題。在實際場景中，VRP會超出普通路徑問題的限制，例如，帶有時間窗口的旅行商問題（traveling salesman problem with time windows，TSPTW）[20]將時間窗口約束添加到TSP中的節點，即節點只能在固定的時間間隔內訪問；帶容量的車輛路徑問題（capacity vehicle routing problem，CVRP）[21]，旨在為訪問一組客戶（即城市）的車隊（即多個銷售人員）找到最佳路線，每輛車都具有最大承載容量的限制。VRP根據不同的應用場景和現實條件需要考慮更多的約束（車載容量、配送中心數量、車輛行駛里程、時間限制等），因此衍生出許多變體，例如：帶時間窗的車輛路徑問題（vehicle routing problem with time windows，VRPTW）[22]、無人機和卡車協同配送的無人機車輛路徑問題（vehicle routing problem with drones，VRPD）[23]、多車型車輛路徑問題（heterogeneous fleet vehicle routing problem，HFVRP）[24]等。

2.2 基于深度強化學習求解路徑問題的步驟

利用DRL求解VRP的思路是將城市的原始坐標作為輸入，利用PN，GNN或Transformer結合經典圖搜索算法建設性地構建近似解，整體求解框架見圖4。

圖4 求解整體框架Fig.4 Solving overall framework

步驟1將問題轉化為圖結構信息，VRP問題是一個全連接圖，圖的節點對應于城市節點，邊對應兩城市之間的道路，如圖5所示。圖通過啟發式算法進行稀疏化，使模型能夠擴展到所有節點的成對計算來解決難以處理的大型實例，或者通過減少搜索空間來更快地學習策略。

圖5 問題定義Fig.5 Problem definition

步驟2獲取圖中節點和邊的初始嵌入，如圖6所示。嵌入是GNN或Transformer編碼器將TSP圖中的每個節點或邊作為輸入，來計算高維空間表示或嵌入特征。在編碼的每一層，節點從其鄰居節點收集特征，通過遞歸傳遞表示局部圖結構。堆疊L層后，網絡能夠從每個節點的L層鄰域中構建節點的特征。Transformer中基于AM的GNN已成為編碼路徑問題的默認選擇，AM作用在于根據對現在節點的相對重要性來權衡鄰居節點。

圖6 圖嵌入Fig.6 Graph embedding

步驟3圖的節點或邊被編碼為高維空間表示，解碼為離散的TSP，如圖7所示。首先，將概率分配給每個節點或每條邊，通過分配的概率將節點或邊添加到解集中；然后通過經典圖搜索技術（例如由概率預測引導的貪心搜索或波束搜索）將預測概率轉換為離散決策。

圖7 解碼和搜索Fig.7 Decoding and searching

步驟4模型訓練。整個編碼器-解碼器模型以端到端的方式進行訓練，一般情況下，通過模仿最優求解器來訓練模型以產生接近最優的解。

由于TSP問題通常需要順序決策以最小化特定于問題的成本函數，可以天然地利用RL框架訓練智能體最大化獎勵函數。對于未充分研究的問題以及缺乏標準解決方案的情況下，RL是一種最優的替代方案。

3 基于DRL求解VRP的方法

近年來出現的大量研究，旨在使用DRL方法開發新的學習算法來自動解決路徑問題，以實現動態高效的求解。DRL求解VRP的方法主要分為PN、GNN、Transformer以及混合模型四類模型。以上通用的路徑問題求解框架，可以適用于求解VRP的變體問題，運行速度和精度相比傳統算法有較大優勢。表1和表2對近幾年求解TSP及其變體問題和VRP及其變體問題的模型進行分析與總結。下面對以上四類模型方法進行介紹，對各類方法的代表性模型、優化性能進行對比和分析。

表1 TSP及其變體問題的模型算法分析與總結Table 1 Model algorithm analysis and summary of TSP and its variant problems

表2 VRP及其變體問題的模型算法分析與總結Table 2 Model algorithm analysis and summary of VRP and its variant problems

3.1 基于PN求解VRP

3.1.1 求解模型

2015年Vinyals等人[12]首次提出將PN與VRP結合，使得模型架構不受輸入輸出維度的限制，采用SL方式進行離線訓練，以預測訪問城市的序列，解決了小規模的TSP問題，為PN求解VRP開辟了新的道路。PN模型原理是將VRP問題編碼成向量，使其在隱層輸出、解碼時通過激活函數對向量進行處理，輸出問題實例中較大的概率向量。例如PN求解TSP的步驟為：首先將每個城市的坐標轉化為高維節點特征向量，由編碼器讀入城市坐標，編碼為對應的存儲輸入序列信息的向量，然后解碼器對向量進行解碼，在解碼過程中，利用AM和隱層狀態計算選擇各個城市的概率P(yt|y1,y2,…,yt-1)，在解碼時使用uit作為指向向量選擇輸入序列中的元素。

Vinyals等人[12]以SL方式訓練模型，需要大量TSP示例及其最優解作為訓練集，標簽不易獲得。為了擺脫對高質量標簽的依賴，Bello等人[25]采用了RL中的行動者-評論家（actor-critic，AC）算法訓練網絡參數，提出神經組合優化（neural combinatorial optimization，NCO）模型，以PN為基礎構建策略網絡，訓練過程中模型輸出的序列值可以通過深度神經網絡（deep neural network，DNN）訓練估值網絡參數，再通過獎勵機制微調，不斷改進策略網絡，擴大了TSP的求解規模，但該框架不適用于隨時間變化的更復雜的VRP問題。在此基礎上，Nazari等人[40]提出了一種可以系統處理靜態和動態元素的訓練方法，模型對輸入序列保持不變，因此改變任何兩個輸入的順序不會影響模型狀態。在VRP問題中輸入是無序的客戶位置及客戶需求，輸入順序對問題求解影響較小，因此模型未采用RNN編碼器，而通過簡單的節點嵌入替換了PN的LSTM編碼器，進而縮短了訓練時間，且不會降低模型的訓練效率。

面對多目標優化問題（multi-objective optimization problems，MOPs）時，Li等人[26]提出了一種使用DRL解決MOP的端到端框架，模型將多目標問題分解為一系列子問題，再通過PN來解決多目標旅行商問題（multiobjective traveling salesman problem，MOTSP）。該模型探索了使用DRL以端到端的方式求解MOTSP的可能性，即給定n個城市作為輸入，可以通過訓練網絡的前向傳播直接獲得最優解。

3.1.2 模型總結

以上模型依賴梯度信息指導搜索，基于搜索的求解VRP方法通常由啟發式方法指導，在各種條件和情況下調整啟發式方法通常非常耗時。為此Chen等人[41]使用雙向LSTM嵌入路徑，提出NeuRewriter模型，模型學習一種策略來選擇啟發式方法并重寫當前解決方案的局部組件，以迭代方式改進直到收斂。實驗果表明模型可求出CVRP20的最優解，CVRP100的優化性能優于求解器OR-Tools。

3.2 基于Transformer求解VRP

3.2.1 求解模型

RNN參數在序列的所有元素之間共享，當模型獲取最后一個時間步的輸出時，它可能會“忘記”序列中先前元素的信息。而AM通過保留編碼器對輸入序列的隱層向量序列，在解碼階段對獲得的向量序列加權求和得到上下文向量ct，由于在輸出過程中注意力的權重不同，因此權重參數αit越大，在t時刻輸出第i個向量的概率越大。進一步，Google團隊[16]提出了由AM和多層感知機組成的網絡結構“Transformer”，Transformer的MHA可以注意到子空間的信息，從不同角度、不同維度提取到問題的深層特征，允許節點通過不同的通道傳遞相關信息，實現并行計算。因此來自編碼的節點嵌入可以學習圖的上下文中關于節點的信息。

Kool等人[17]提出了一種有效的模型和訓練方法，以改進上述基于學習的啟發式求解路徑問題。通過用AM層代替遞歸網絡來減少節點輸入順序的影響，應用RL算法訓練模型。與Bello等人[25]不同，此模型引入貪婪策略得到的解作為基線，提高了模型的收斂速度。Joshi等人[31]基于Kool等人[17]的實驗設置，結合SL和RL訓練100個節點的TSP，提升了模型的準確率。

在Kool等人[17]模型中，節點特征通過嵌入方式進行編碼，該嵌入隨時間推移而固定。而問題實例的狀態應根據模型在不同的構造步驟所做的決定而改變，節點特征應該相應地更新。因此，Peng等人[48]提出了一種具有動態編碼器-解碼器結構的動態注意力模型，該模型能夠動態地探索節點特征，并在不同的構造步驟中有效地利用隱藏的結構信息。與Kool等人[17]相比，該模型在圖的上下文中動態地刻畫每個節點，這可以在不同的構造步驟中有效地探索和利用隱藏的結構信息。

受Transformer在NLP中的啟發，Bresson等人[27]將Transformer用于求解TSP，編碼器與Kool等人[17]和Deudon等人[28]相同，通過RL訓練模型，使用帶有MHA模塊的部分解來構建查詢，添加一個不存在的城市，該城市通過自注意力模塊查詢所有城市，并在最佳位置使用波束搜索解碼。結果表明，TSP50的最優間隙為0.004%，TSP100的最優間隙為0.39%。

雖然DRL方法可以直接輸出問題的解，但是其優化效果與專業求解器相比仍有一定差距。由于局部搜索是求解組合優化問題的經典方法，學者們開始研究利用DRL方法來自動學習局部搜索算法的啟發式規則，從而比人工設計的搜索規則具有更好的搜索能力。相比之下，Wu等人[29]利用DRL來自動發現更好的改進策略，提出了一個DRL框架來改進啟發式算法解決路徑問題。模型首先提出一種用于改進啟發式算法的RL公式，其中策略網絡由兩部分組成，分別學習節點嵌入和節點對選擇，用來指導下一個解決方案的選擇；并利用AC算法訓練策略網絡，然后通過鄰域搜索來改進初始解，不斷地提高解的質量，最后利用基于自注意力的框架參數化策略。將模型應用于求解TSP和CVRP的實驗結果表明，模型明顯優于現有的基于線性規劃的求解TSP和CVRP方法，在改進啟發式算法過程中，學習到的策略確實比傳統的手工規則更有效，并且可以通過簡單的集成策略進一步增強。

基于Transformer還有更多的改進，Falkner等人[49]采用修復和破壞算子，通過局部搜索過程和維護少量候選解來進一步擴展大鄰域搜索（large neighborhood search，LNS）。LNS是神經修復算子與局部搜索過程、啟發式破壞算子和部分解的選擇過程相結合，以獲得高效的求解方法，LNS主要思想是利用學習的模型來重構部分被破壞的解，并通過破壞啟發式（或隨機策略本身）引入隨機性來有效地探索大鄰域。文獻[49]啟發式方法針對解決方案的不同部分，將銷毀分為兩種不同的操作：創建部分路線、刪除完整的路線。與文獻[49]每次考慮一個節點的構造啟發式相反，Hottung和Tierney[50]直接學習神經修復算子，以重新組合由CVRP的隨機分裂產生的路徑片段。

基于Falkner等人[49]，Ma等人[51]提出雙方面協作Transformer（dual-aspect collaborative transformer，DACT）神經領域搜索模型，使用雙向編碼器分別學習節點和位置特征的嵌入，利用循環格雷碼鄰接相似、首尾相似的特性設計高維空間連續的循環位置編碼（cyclic positional encoding，CPE），訓練過程中使用課程學習獲得更高效的采樣速率，以及更快的收斂速度和更小的方差，提高求解VRP的泛化性能。應用DACT求解TSP和CVRP的結果表明，DACT優于現有的鄰域搜索求解器，并且具有更優的泛化性能。

3.2.2 模型總結

現實生活中VRP問題涉及車輛容量、時間窗口等約束，雖然近年來已經開發了RL模型來比優化啟發式更快地解決基本的VRP問題，但很少考慮復雜的約束。啟發式算法高效的鄰域搜索功能是求解VRP問題的關鍵組成部分，Ma等人[52]針對取貨和送貨問題（pickup and delivery problem，PDP）問題設計基于并改進DACT[51]的神經鄰域搜索方法N2S，N2S將DACT-Attention改進為高效的Synth-Attention，允許最基本的自我注意機制合成關于解決方案的各種特征，同時利用兩個自定義解碼器自動學習執行取貨和送貨節點對的移除和重新插入，以解決優先級約束。模型甚至在更多約束的PDP變體上超過了人工設計的LKH3求解器。

3.3 基于GNN模型求解VRP

3.3.1 求解模型

近年來，研究人員設計了用于處理圖數據的神經網絡結構GNN，其核心思想是根據每個節點的原始信息（如城市坐標）和各個節點之間的關系（城市之間的距離），計算得到各個節點的特征向量，依據節點特征向量進行節點預測、邊預測等任務。GNN與圖嵌入密切相關，圖嵌入旨在通過保留圖的拓撲結構和節點內容信息，將圖中頂點表示為低維向量，以便使用RL算法進行處理。Scarselli等人[14]利用GNN模型處理圖上的數據表示問題，實現了函數將圖中的節點映射到多維歐幾里德空間，適用于以圖及其節點為中心的應用。

GNN通過低維的向量信息來表征圖的節點及拓撲結構，有效的提取圖中關鍵節點信息。Nowak等人[53]以SL的方式訓練GNN，直接輸出一個環游作為鄰接矩陣，結合波束搜索將其轉換為可行的路徑方案。該方法被提出之后，structure2vec（S2V）[54]、GCN[54]、圖注意力網絡（graph attention network，GAT）[54]等模型相繼被提出，用于解決VRP。

在許多實例中，相似的路徑問題通常保持相似的問題結構，但數據不同，這為學習啟發式算法提供了契機。Khalil等人[30]指出上述網絡架構不能有效反映TSP的圖結構，并提出了一種將RL與圖嵌入神經網絡相結合的框架，以增量方式構造TSP和其他VRP問題的解決方案，引入基于S2V的圖嵌入網絡，以捕獲解決方案的當前狀態和圖的結構，然后使用Q-learning來學習貪婪策略，該策略決定將哪個頂點插入部分游覽，可求解大范圍的TSP問題。

GPN擴展了傳統的PN，增加了一層圖嵌入，這種轉換實現了對大規模問題的更好推廣。Kool等人[17]將GNN和PN進行結合求解CVRP，加入MHA以及自注意力機制，AM能有效地捕捉深層節點信息，采用AM計算每一步的節點選擇概率，以自回歸的方式逐步構造得到完整解，且模型通過設計超參數展示了在合理大小的多個VRP問題上的靈活性。為學習更好的啟發式方法解決廣泛的VRP問題提供思路。

Joshi等人[31]基于Kool等人[17]的實驗設置，在PN基礎上用圖卷積神經網絡（graph convolutional networks，GCN）編碼代替Transformer架構編碼，結合SL和RL訓練100個節點的TSP，提升了模型的準確率，利用SL訓練GNN，以預測邊出現在TSP中的概率，通過波束搜索生成可行的回路。為TSP20/50/100訓練基于自回歸的GAT模型，并評估從TSP20到TSP500的實例，通過REINFORCE訓練RL模型和貪婪算法推出基線，以最大限度地減少模型在每一步的預測和最優目標。

GCN[54]是許多復雜GNN模型的基礎，其核心思想是學習一個函數映射，通過映射圖中的節點，聚合節點與其鄰居節點的特征來生成節點的新表示。Groshev等人[55]和Joshi等人[56]通過SL訓練GCN來解決TSP。Joshi等人[56]在TSP20/50/100的優化效果略微超越了Kool等人[17]的方法，接近LKH3、Concorde等求解器得到的最優解，但是該方法的求解時間慢于LKH3、Concorde等方法，在泛化能力上該方法也不及Kool等人[17]的方法。Groshev等人[55]使用經過訓練的GCN來指導啟發式算法輸出解決方案，利用這些解決方案作為標簽重新訓練大規模TSP的GCN，進一步，Prates等人[57]使用SL來訓練GNN，將邊緣權重視為每個實例的特征，模型輸出的解決方案與最優解的偏差可以小于2%。

以上工作都是利用人工智能的泛化能力來探索滿足問題的車輛路徑，仍受到城市規模、大型交通網絡帶來的計算復雜度的困擾。James等人[58]提出一種基于DRL的NCO策略，將在線VRP問題轉換為車輛游覽生成問題，并提出一種圖嵌入式PN結構來迭代開發游覽。由于構造NN所需的SL數據具有高計算復雜度，利用具有無監督輔助網絡的DRL機制來訓練模型參數，同時設計多采樣方案，以進一步提高模型性能。

3.3.2 模型總結

GNN和GCN用來提取圖的特征并部署記憶增強NN和RNN傳遞順序信息，GAT是一種基于空間的GCN網絡。GAT是通過AM傳播節點信息，對圖拓撲具有強大的表示能力。因此，Gao等人[42]在GAT基礎上改進提出EGATE模型（element-wise GAT with edgeembedding，EGATE），模型的編碼器是將節點嵌入和邊嵌入集成修改的GAT，以及一個基于GRU的解碼器，模型通過AC訓練，實驗結果表明，在中等規模的數據集上，該模型優于傳統啟發式算法和NCO模型，能夠處理大規模數據集。由于VRP問題的高復雜性，難以擴展且大多受到問題模型容量的限制。因此，學者提出利用混合方法來求解VRP及其變體問題。

3.4 混合模型求解VRP

3.4.1 RL結合傳統算法求解VRP

在求解CVRP問題時，LKH3等經典算法求解效率低，難以擴展到更大的問題?；贒RL的方法求解效率高，但是DRL解的質量與傳統經典方法求得解的質量仍存在相當大的差距，為此Lu等人[59]提出一種在解決方案中迭代搜索，通過不斷地改善解，直到滿足某個終止條件的框架。模型將啟發式算子分為改進算子和擾動算子，即給定一個問題實例，算法首先生成一個可行解，然后用改進算子或擾動算子迭代地更新解，在一定次數的步驟之后，模型將在所有訪問的解決方案中選擇最好的一個。

經典算法除了求解效率不高，求解VRP問題還面臨著狀態空間爆炸問題，可行解的數量隨著問題規模的大小呈指數級增長，使得解決大規模VRP變得棘手。Cappart等人[32]提出一種基于DRL和約束規劃（constraint programming，CP）混合模型求解TSPTW，模型核心是將TSPTW通過動態規劃（dynamic programing，DP）建模，模型架構分為三個部分：學習階段、求解階段和統一表示，其中智能體的動作銜接學習和求解兩個階段，學習階段是通過RL訓練問題實例，求解階段利用CP評估問題實例。通過實驗證明，該模型的性能優于獨立的RL和CP解決方案，與求解器OR-Tools效果擔當。

為進一步提高模型的泛化能力，Fu等人[33]提出一個在固定大小的圖上預訓練的網絡，通過對子圖進行采樣，推斷和合并結果以解決更大規模的問題。在此基礎上，Xin等人[60]提出將DL與傳統啟發式LKH相結合的算法NeuroLKH解決TSP。該模型訓練了一個稀疏圖網絡（sparse graph network，SGN），分別通過SL和無監督學習訓練邊緣分數、節點懲罰，以此提高LKH的性能，基于SGN的輸出，NeuroLKH創建邊緣候選集并轉換邊緣距離以指導LKH的搜索過程。文獻[60]實驗結果顯示，NeuroLKH顯著優于LKH，并且模型可以很好地推廣到CVRP、PDP。

DRL方法通常缺少在解空間內搜索的能力。為克服以上問題，王原等人[61]提出了深度智慧型蟻群優化算法（deep intelligent ant colony optimization，DIACO），采用DRL方法提取問題特征，并形成對應的特征矩陣，蟻群算法基于特征矩陣進行搜索求解，蟻群算法的加入提高了DRL解空間搜索性能，同時DRL提升了蟻群算法的計算能力，該方法能夠有效求解不同規模的TSP。

一些求解VRP的模型可以通過Q-learning很好地訓練，但不能通過Sarsa訓練，降低了模型的性能。因此，Zheng等人[62]提出一種基于RL的啟發式算法VSR-LKH，該算法顯著提升了著名的LKH算法，它將Q-learning、Sarsa和MCT三種算法相結合，取代LKH的遍歷操作，是一種可變策略?？勺儾呗缘乃枷胧鞘芸勺冟徲蛩阉鞯膯l，定義一個Q值來代替α值，通過結合城市距離和α值來進行候選城市的選擇和排序，并且通過迭代搜索過程中產生的可行解的信息自適應地調整Q值，以進一步提高模型泛化性能。

3.4.2 RL與神經網絡相結合的混合模型

由于RL學習方法大多直接學習端到端的解決方案，以及VRP問題的高復雜性，難以擴展且受到RL模型容量的限制，為克服上述問題，Wang等人[63]設計了一個雙層框架求解器，上層學習框架來優化圖（例如，添加、刪除或修改圖中的邊），下層啟發式算法在優化的圖上求解，這樣的雙層網絡簡化了對原始問題的學習，并且可以有效地減輕對模型容量的需求。

面對更復雜或者大范圍的路徑問題時，經典的DRL算法仍然得不到好的優化效果，訓練好的模型泛化到大范圍時解的質量會下降。于是研究者提出了分層強化學習（hierarchical reinforcement learning，HRL）模型，HRL在面對高維度問題時不會出現維度災難，將一個復雜的問題分解為簡單的子問題，從而來解決大規模的TSP。Ma等人[15]使用RL訓練分層GPN，在約束條件下學習分層策略尋找最優解，該模型在小范圍TSP訓練且泛化到大范圍TSP也具有更快的計算速度和最短距離。

而對于問題TSP-D，Bogyrbayeva等人[34]提出了一種AM-LSTM混合模型，用于考慮車輛和無人機之間交互作用的高效路徑，該模型由一個基于AM的編碼器和一個基于LSTM的解碼器組成，AM對高度連通的圖形進行編碼，LSTM存儲所有車輛的歷史路徑。數值結果所示，這種混合模型在解決方案質量和計算效率方面都優于基于AM機制的模型，以及模型泛化到對最小-最大容量約束車輛路徑問題的實驗也證實了混合模型比基于注意的模型更適合于多車輛協調的路徑問題。

與啟發式方法相比，經典的DP算法保證了最優解，但隨著問題規模的增大使得泛化性很差。為此Kool等人[64]提出深度策略動態規劃（deep policy dynamic programming，DPDP），將神經啟發式的優勢與DP算法的優勢相結合。DPDP使用來自DNN的策略對DP狀態空間進行優先級排序和限制，以及使用GNN對部分解進行評估，對DP算法進行“神經增強”。實驗結果表明，神經策略有效地提高了DP算法的性能，對于具有TSP100，該方法產生與高度優化的LKH求解器相接近的結果，在TSPTW100上，DPDP的求解速度顯著快于LKH。

面對CVRP，王揚等人[43]提出動態圖Transformer（dynamic graph transformer model，DGTM）混合模型，使用動態位置編碼技術，用于循環編碼動態序列，使得節點坐標在嵌入過程滿足平移不變性，其次將GNN的聚合操作處理應用于Transformer解碼架構中，最后通過雙重損失的REINFORECE算法訓練DGTM，有效調節不同節點間的差異分布程度，防止過早收斂。DGTM在處理CVRP問題上優化結果得到顯著提高且具有較好的泛化性能。

3.4.3 模型總結

之前關于求解車輛路徑的工作主要集中在自回歸模型，但當與任何形式的搜索方法相結合時，需要為每個部分解來評估模型，導致模型的計算成本很高。而Kool等人[64]提出的模型每個實例只需要對NN進行一次評估，因此可以進行更大范圍的搜索。

4 DRL求解VRP的分析

4.1 求解方法局限性

利用RL求解VRP需要不斷調整參數，改進策略網絡，在訓練過程中難免會出現模型不穩定、泛化能力差或過于依賴標簽等情況，都會對模型的最終性能造成影響。下面分別對基于PN、基于GNN、基于Transformer和混合模型求解VRP的相關模型進行局限性分析。

基于PN模型局限性分析：PN結構簡單，無法處理動態信息；網絡層數少，不利于充分提取問題的特征信息；在處理動態信息過程中，信息本身的不穩定性、節點信息稀疏性都會限制模型的優化效果影響解的輸出。

基于Transformer模型局限性分析：網絡層數多、結構復雜，模型參數變多且不易訓練。

基于GNN模型局限性分析：模型需借助驗證集早停提升模型性能；訓練是整個批次進行的，難以擴展到大規模網絡，且收斂較慢；網絡層數太深時，模型參數不能得到有效的訓練；圖的拓撲性質會導致巨大的解空間在搜索過程也是困難的，從而限制模型的優化效果。

混合模型求解VRP局限性分析：使用傳統算法搜索導致訓練時間較長，優化性能無法保證，可能出現解碼錯誤等情況。

因此無論是基于圖結構模型、還是基于DRL結合傳統算法模型求解VRP，都有一定的局限性，表3對求解VRP的經典模型進行局限性分析。

表3 DRL求解VRP的模型局限性分析Table 3 Model limitation analysis for DRL solving VRPs

4.2 RL求解VRP問題的優勢及實驗對比

VRP有很多變體涉及動態不確定因素，利用傳統方法求解問題難度很大，且不會有很大的突破[68]。RL與傳統算法的結合求得的結果優于只使用傳統算法的結果，例如Alipour等人[69]面對多約束條件的路徑問題，使用RL算法使問題描述更加全面，解的質量也很高。VRP變體都是在經典的TSP上衍生的，具有相似的優化結構，傳統算法在問題描述發生輕微變化時，就要重新設計算法，面對VRP眾多變體，設計很多算法將消耗大量人力，因此，單獨地使用傳統算法是不可行的。

在面對具有多個約束條件的問題時，輸入輸出是隨機的、動態的，且前一步的結果可能會對下一步求解有影響。一些傳統算法難以考慮隨機和動態因素，導致模型泛化能力弱，不能在各個變體中通用或者得到解的質量很差。而NN中的嵌入方式可以根據問題的情況做靜態嵌入和動態嵌入，充分保證了原始問題的真實性。Li等人[36]提出DRL方法求解覆蓋旅行商問題（covering salesman problem，CSP），模型基于PN加入動態嵌入模型處理動態信息，計算速度比傳統啟發式快近20倍。利用RL求解VRP與傳統方法相比，RL有優質的表現和泛化能力，加入動態嵌入可以更好地處理動態信息，深層次的網絡更有利于提取深層次潛在的隱含信息。

總的來說，RL求解VRP相比傳統算法的優勢如下：（1）求解速度快。DNN模型對問題特征進行全方位的表示，減少了解空間的搜索寬度和深度；硬件設施CPU更高、更快、更強和GPU在ML領域的優異表現，使得VRP問題在最短的計算時間內得到顯著的優化效果；模型一旦訓練完成，以O(n)的復雜度輸出解。（2）泛化能力的提高。面對具有相似結構的問題，只需調用參數通過遷移學習傳遞給相應的策略函數，就能輸出合適的解，減少對數據標簽的依賴性，節省大量資源和計算時間。通過DRL學出來的策略有希望比人工設計出來的更高效，不需要重新設計算法。（3）解決了多維度問題。面對多維度問題，可以使用不同嵌入方式結合AM使問題的描述更加詳細，挖掘更深層次的關系，從而輸出高質量的解。DRL有望能夠求解一些復雜約束條件下的NP難問題。

本文對端到端的DRL方法作了詳細的介紹，為保持實驗數據公平性，所有實驗均基于Pytorch-1.9.0深度學習平臺，在Windows11操作系統環境下使用單張Nvidia RTX 3050 GPU和i5-11300H CPU運行VRP模型，這里總結了常用的基于DRL的方法和啟發式算法的最新實驗結果，表4是針對CVRPlib數據集實例上具有代表性模型的優化效果的對比。實驗結果顯示，DACT模型的優化性能超越了目前基于DRL的模型和專業求解器。

表4 經典模型在CVRPlib數據集實例上的性能比較Table 4 Performance comparison of solutions for CVRPlib on instances

5 總結及未來發展方向

最近，許多研究人員回顧了基于RL求解VRP，每篇綜述都有各自的優點和不足，本文對最近發表的綜述進行整理分析：Mazyavkina等人[70]總結了一些常用的基于策略和基于價值的強化學習算法，沒有比較模型間的差距，沒有數據對比；Kotary等人[71]對ML學習方法進行分類，側重于端到端的學習范式，籠統地介紹了GNN；Cappart等人[72]對GNN在各種推理任務中的應用進行了高級概述沒有描述學習在CO推理中的具體作用和過程；Bengio等人[73]對COP的ML算法進行概述，為ML應用到COP提供理論基礎，但未對ML求解COP的建模過程進行詳細介紹。

DRL將VRP問題與DNN結合起來，將VRP的特殊性和DRL的優勢結合起來，克服了單獨使用傳統算法求解效果不理想的局限性，是目前解決VRP及其變體最流行的方法。本文對RL的相關算法以及DRL模型的構建過程進行了詳細的介紹，并梳理了先前模型的創新點和不足之處，重點分析了DRL模型架構的主要作用和特性。VRP是多變體多維度的，且現實數據與訓練數據會有差距，導致模型在應用到實例會出現效果不好、最優間隙差等情況，由這些模型的不足可以看到，將來使用DRL解決VRP及其變體問題仍存在挑戰性。

（1）現有基于學習的方法僅僅訓練特定的路徑問題，對特定路徑問題的范圍進行泛化求解。未來可以考慮將訓練完成的路徑策略通過遷移學習技術，在不同實例上進行泛化求解，會節省大量的計算資源，提高模型的利用率。進一步深入探求不同參數之間的內在聯系，建立VRP問題變體之間的源域到目標域的映射關系是未來值得研究的問題。

（2）現有RL模型求解VRP屬于端到端的方法，求解過程類似于黑箱優化，缺乏相應的理論保證。未來工作中，尋找一種通用的體系結構，有效地保證DRL求解方法的可行性，還需要進一步評估和檢驗。未來工作中可以考慮將DRL及其網絡架構遷移至運籌優化算法中，以增強求解的可靠性。因此繼續深入探求DRL的求解過程和增強模型的可解釋性是未來值得研究的問題。

（3）大多數網絡使用均勻分布或者隨機生成數據來訓練策略網絡，訓練好的模型可以泛化到不同的問題上，但是模型泛化能力的好壞或許與訓練數據有關，若節點位置分布不知或不遵循任何分布，此時構建一個穩定的模型具有很大挑戰。如何為VRP及其變體問題構建魯棒性的訓練模型是未來工作中的關鍵研究點。未來考慮通過知識蒸餾的方法提升DRL模型在不同數據分布下的泛化能力。

（4）RL含有大量手工設計的超參數，不同的參數往往對模型的性能影響較大。為減少超參數對實驗結果的影響，考慮將自動RL參數調整技術引入到模型訓練中。自動調整學習率和衰減率對模型收斂性的控制是未來一個重要的研究方向。