伍康 夏維 王子源

摘 要：近年來圖神經(jīng)網(wǎng)絡(luò)與深度強化學(xué)習(xí)的發(fā)展為組合優(yōu)化問題的求解提供了新的方法。當(dāng)前此類方法大多未考慮到算法參數(shù)學(xué)習(xí)問題，為解決該問題，基于圖注意力網(wǎng)絡(luò)設(shè)計了一種智能優(yōu)化模型。該模型對大量問題數(shù)據(jù)進(jìn)行學(xué)習(xí)，自動構(gòu)建鄰域搜索算子與序列破壞終止符，并使用強化學(xué)習(xí)訓(xùn)練模型參數(shù)。在標(biāo)準(zhǔn)算例集上測試模型并進(jìn)行三組不同實驗。實驗結(jié)果表明，該模型學(xué)習(xí)出的鄰域搜索算子具備較強的尋優(yōu)能力和收斂性，同時顯著降低了訓(xùn)練占用顯存。該模型能夠在較短時間內(nèi)求解包含數(shù)百節(jié)點的CVRP問題，并具有一定的擴展?jié)摿Α?/p>

關(guān)鍵詞：組合優(yōu)化；CVRP；鄰域搜索；圖注意力網(wǎng)絡(luò)；深度強化學(xué)習(xí)

中圖分類號：TP183?? 文獻(xiàn)標(biāo)志碼：A??? 文章編號：1001-3695（2024）05-018-1402-07

doi： 10.19734/j.issn.1001-3695.2023.08.0410

Improved neighborhood search algorithm based on graph neural network

Abstract：In recent years， the development of graph neural network（GNN） and deep reinforcement learning provides new methods to solve combinatorial optimization problems. Currently， most of these methods do not consider the problem of algorithm parameter learning. This paper developed an intelligent optimization model based on graph attention networks to solve this problem. The model automatically learned neighborhood search operators and destructive sequence terminators according to a significant amount of problem data， and trained model parameters based on reinforcement learning. This article used standard examples to test the model and conducted three different groups of experiments. The experimental results show that the learned neighborhood search operator has a remarkable ability to optimize and converge， while significantly reducing the training memory occupation. It can solve CVRP problems containing hundreds of nodes in a short time and has the potential for expansion.

Key words：combinatorial optimization; CVRP; neighborhood search; graph attention network（GAT）; deep reinforcement learning（DRL）

0 引言

組合優(yōu)化問題是一類在離散狀態(tài)下求極值的最優(yōu)化問題［1］，廣泛應(yīng)用于交通運輸規(guī)劃、生產(chǎn)流程優(yōu)化等領(lǐng)域。常見的組合優(yōu)化問題有車輛路徑問題（vehicle routing problem，VRP）［2］、車間作業(yè)調(diào)度問題（Job-Shop scheduling problem，JSP）等。組合優(yōu)化問題通常是NP-hard的，在多項式時間內(nèi)無法尋找到最優(yōu)解。目前求解組合優(yōu)化問題的算法分為精確算法和近似算法兩類，精確算法指可以求解出問題全局最優(yōu)解的方法，包括分支定界法［3］、列生成法［4］和動態(tài)規(guī)劃等。近似算法指可以求出問題局部最優(yōu)解的方法，有近似算法［5］和啟發(fā)式算法［6］兩類，近似算法包括貪心算法［7］、線性規(guī)劃等，啟發(fā)式算法有模擬退火算法［8］、遺傳算法［9］及迭代鄰域搜索方法［10］等。精確算法雖然可以計算出最優(yōu)解，然而當(dāng)問題規(guī)模較大時，將耗費巨大計算資源，難以拓展到大規(guī)模問題。解決規(guī)模較大的組合優(yōu)化問題時，多采用啟發(fā)式算法獲得近似最優(yōu)解，然而啟發(fā)式規(guī)則需要領(lǐng)域?qū)＜沂止ぴO(shè)計，高度依賴專業(yè)知識。隨著圖神經(jīng)網(wǎng)絡(luò)（GNN）結(jié)合深度強化學(xué)習(xí)（DRL）在求解組合優(yōu)化問題領(lǐng)域的發(fā)展，基于深度神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)啟發(fā)式算子與操作符，并混合經(jīng)典啟發(fā)式求解框架已經(jīng)成為求解組合優(yōu)化問題的新途徑。

基于DRL求解組合問題算法主要分為端到端算法與迭代搜索算法兩類［11］。端到端算法將給定問題作為輸入，通過訓(xùn)練好的深度神經(jīng)網(wǎng)絡(luò)直接輸出問題最終解。Bello等人［12］引入強化學(xué)習(xí)訓(xùn)練指針網(wǎng)絡(luò)模型（pointer network，Ptr-Net）。文獻(xiàn)［13］首次利用GNN編碼問題，使用深度Q-網(wǎng)絡(luò)解決旅行商問題（travelling salesman problem， TSP）。Kool等人［14］引入了Transformer［15］的注意力機制，提出注意力模型求解TSP、VRP問題。上述基于端到端的算法能快速直接輸出問題解，但在中大規(guī)模問題上優(yōu)化結(jié)果與求解器差距較大。迭代搜索類算法根據(jù)學(xué)習(xí)到的啟發(fā)式規(guī)則進(jìn)行迭代搜索，通常具有良好的優(yōu)化結(jié)果，但在求解速度上不如端到端方法。Chen等人［16］提出的鄰域搜索模型Neuwriter求解JSP和VRP問題的表現(xiàn)均優(yōu)于Google OR-tools。Yolcu等人［17］結(jié)合GNN與強化學(xué)習(xí)訓(xùn)練鄰域搜索選擇算子，尋找適定性問題最優(yōu)解時，算法迭代步數(shù)少于傳統(tǒng)啟發(fā)式算法。此外許多學(xué)者利用DRL學(xué)習(xí)設(shè)計其他搜索類算法［18，19］，如蟻群算法、集束搜索等。文獻(xiàn)［20，21］分別研究與提升了搜索模型的泛化性。根據(jù)上述研究可以看出迭代搜索類框架很適合與深度神經(jīng)網(wǎng)絡(luò)結(jié)合形成混合優(yōu)化算法，這也是本文的主要研究動機。

大規(guī)模鄰域搜索（large neighborhood search，LNS）［22］是一種主流的啟發(fā)式搜索框架，每次迭代時通過搜尋現(xiàn)有解的鄰域獲得更優(yōu)解，即破壞算子和修復(fù)算子的不斷交替迭代。Gao等人［23］結(jié)合圖注意力神經(jīng)網(wǎng)絡(luò)（GAT）［24］與DRL學(xué)習(xí)LNS的鄰域算子以求解VRP問題。Wu等人［25］利用DRL和GNN學(xué)習(xí)解決整數(shù)規(guī)劃問題的LNS策略，用以改進(jìn)Gurobi等商業(yè)求解器求解效率。Cheng等人［26］在搜索的同時加入選擇操作，加快了整體算法運行速度。然而上述研究未考慮LNS算法參數(shù)學(xué)習(xí)問題，例如破壞節(jié)點數(shù)目、鄰域搜索步長及深度等。只采用單一的參數(shù)組合，算法探索空間過小，易陷入局部最優(yōu)解［27］。

綜上所述，本文受seq2seq［28］模型中序列終止符學(xué)習(xí)機制的啟發(fā)，提出了一種學(xué)習(xí)鄰域搜索算子的終止符-邊-圖注意力網(wǎng)絡(luò)（terminator edge graph attention network，TE-GAT）模型。TE-GAT模型采用編碼器-解碼器架構(gòu)，編碼器負(fù)責(zé)提取問題圖結(jié)構(gòu)特征，基于GAT進(jìn)行信息匯聚。解碼器負(fù)責(zé)充當(dāng)破壞算子輸出有序破壞節(jié)點序列，根據(jù)學(xué)習(xí)獲得的算法終止符進(jìn)行有序解碼，算法中的貪心算子接收該有序序列生成新的迭代解。模型通過構(gòu)建虛擬節(jié)點的方式在編碼器中加入可學(xué)習(xí)的終止符，并在網(wǎng)絡(luò)訓(xùn)練過程中將最優(yōu)的算法終止位置指向該虛擬節(jié)點。本文基于actor-critic架構(gòu)使用近端策略優(yōu)化（proximal policy optimization，PPO）算法訓(xùn)練所提模型，模型代表的策略網(wǎng)絡(luò)在每回合與價值網(wǎng)絡(luò)的互相改進(jìn)中不斷更新參數(shù)，訓(xùn)練后得到準(zhǔn)確穩(wěn)定的模型。通過終止符學(xué)習(xí)機制，TE-GAT模型進(jìn)一步學(xué)習(xí)LNS算法參數(shù)，提升了算法對近似最優(yōu)解的搜索能力與不同特征問題的適應(yīng)性。

VRP問題是組合優(yōu)化領(lǐng)域一類極具應(yīng)用性的優(yōu)化調(diào)度問題，本文以解決大規(guī)模具有容量限制的車輛路徑規(guī)劃問題（capacitated vehicle routing problem，CVRP）為例，進(jìn)行三組不同實驗以證明TE-GAT模型的實用性和可行性。第一組實驗針對問題規(guī)模分別為51、101、200及251等CVRP問題，使用隨機生成實例訓(xùn)練模型，從CVRPLIB［29］標(biāo)準(zhǔn)算例庫中選擇對應(yīng)規(guī)模算例測試，并與Google OR-tools、Random-LNS算法及EGATE模型對比實驗結(jié)果。第二組實驗通過參數(shù)實驗分析了終止符學(xué)習(xí)機制的實際效用。最后探索了模型求解服務(wù)節(jié)點數(shù)量超過500的大規(guī)模CVRP問題的性能表現(xiàn)，證明算法在大規(guī)模問題數(shù)據(jù)集下具有良好的尋優(yōu)能力和進(jìn)一步解決更大規(guī)模問題的潛力。

1 CVRP問題

VRP問題屬于組合優(yōu)化領(lǐng)域中的一類經(jīng)典問題，可被簡單描述為：一組車輛向多個需求有限用戶運送貨物，若車輛無法完成或已經(jīng)完成用戶需求，立即返回倉庫。問題優(yōu)化目標(biāo)是在完成所有用戶需求的情況下使運輸路線總成本最小。本文主要解決CVRP問題，圖1為CVRP問題示意圖。問題定義在無向完全圖Euclid Math OneGAp=（Euclid Math OneNAp，A）上，i={0，1，2，…，n}代表所有節(jié)點集合，如果i≠0，則節(jié)點i表示用戶點。如果i=0，則節(jié)點i表示倉庫。用戶點i∈{1，2，…，n}的貨物需求量為Q且滿足約束μ1

2 基于圖神經(jīng)網(wǎng)絡(luò)的鄰域搜索算子策略網(wǎng)絡(luò)

2.1 原始嵌入特征

為了從當(dāng)前CVRP問題解決方案的圖結(jié)構(gòu)中獲得節(jié)點與邊信息表示問題特征，本文設(shè)計如下提取原始節(jié)點嵌入特征及邊嵌入特征的向量化表示方法。

按式（1）定義原始節(jié)點嵌入特征xi：

xi=［D（j）i，D（j），Qi，Q（j）］（1）

其中：D（j）i表示在當(dāng)前路線j下車輛到達(dá)節(jié)點i時已經(jīng)行駛的距離；D（j）表示當(dāng)前路線j的總距離；Qi表示節(jié)點i的需求量；Q（j）表示當(dāng)前線路j的總需求量。

按式（2）定義原始邊嵌入特征eij：

eij=［dij，bij］（2）

其中：dij表示節(jié)點i到j(luò)的邊距離；bij表示是否存在路線經(jīng)過aij，是則為1，否則為0。

以上特征向量的所有元素都會經(jīng)過歸一化處理，歸一化后的原始特征向量將會作為CVRP圖特征輸入到編碼器。此外，本文采取通用的稀疏矩陣存儲格式（coordinate format，COO）［30］來存儲節(jié)點連接信息，COO是一個形狀為2×E（E為邊的數(shù)量）的矩陣，其每列存儲圖中某對源節(jié)點與目標(biāo)節(jié)點之間的連接信息，該格式為大多數(shù)學(xué)者［31，32］采用。嵌入特征和COO矩陣組合成可用于計算處理的圖數(shù)據(jù)類，本文使用目前被廣泛使用的PyTorch-Geometric［33］庫合成與處理上述圖數(shù)據(jù)。

2.2 編碼器

TE-GAT在編碼過程中不僅考慮節(jié)點的信息，節(jié)點相連邊的嵌入特征也參與到GAT信息傳播的過程中。為節(jié)約計算資源，TE-GAT信息匯聚時，根據(jù)節(jié)點特征向量之間距離大小，只選取待更新節(jié)點最近的k個點作為鄰居節(jié)點。圖2描述了單層TE-GAT在GAT基礎(chǔ)上如何使用最近鄰算法更新邊和節(jié)點信息的過程。在此基礎(chǔ)上，本文提出如圖3所示的編碼器結(jié)構(gòu)。

編碼器以原始節(jié)點特征xi（i∈{0，1，2，…，n}）和原始邊嵌入特征eij（i，j∈{0，1，2，…，n}）為輸入，兩種嵌入特征分別進(jìn)入不同的全連接層，輸出維度分別為dx和de的新嵌入特征，計算過程見式（3）（4）。

相對權(quán)重系數(shù)，計算過程見式（6）。TE-GAT層最后按式（7）更新節(jié)點i特征。

根據(jù)問題規(guī)模，編碼器可包含多個TE-GAT層，設(shè)置2、3層可以滿足大多數(shù)任務(wù)需求。編碼器執(zhí)行完所有TE-GAT層后，將所有節(jié)點特征按行順序依次排列獲得節(jié)點特征矩陣X。隨后輸入X到平均池化層，編碼器按式（8）計算出可表征當(dāng)前VRP問題的圖嵌入特征向量xG。

2.3 解碼器

解碼器代替了LNS的破壞算子，生成帶有后續(xù)修復(fù)算子接收順序的破壞節(jié)點序列η={η1，η2，…，ηN}。解碼器網(wǎng)絡(luò)是一個能輸出η的策略網(wǎng)絡(luò)π，與傳統(tǒng)破壞算子設(shè)計不同，π能在訓(xùn)練中改進(jìn)啟發(fā)式規(guī)則并能探索更多的參數(shù)空間，輸入xG到π，其按式（9）計算不同η的概率分布并從中采樣輸出η。

p（π（［η1，η2，…，ηN］））=

p（η1）·p（η2|η1）·…·p（ηN|η1，…，ηN－1）（9）

其中：［·］表示有順序排列的破壞節(jié)點序列η；p（π（η））表示策略網(wǎng)絡(luò)π輸出η的聯(lián)合概率。解碼器根據(jù)概率分布采樣到η后，按序輸入到修復(fù)算子重構(gòu)路線。本文算法使用了單個貪心算子修復(fù)解，從而完成鄰域搜索過程。該貪心算子按照最小成本插入的原則將η插入到破壞后的線路，構(gòu)成新的解路線。

Google公司2014年提出的seq2seq［28］模型為解決斷句問題，在目標(biāo)字典中添加終止符，解碼器在解碼過程中遇到終止符或達(dá)到最大解碼次數(shù)即停止解碼，從而在訓(xùn)練中學(xué)習(xí)目標(biāo)序列長度。借鑒于此，本文在解碼器中添加了一種終止符學(xué)習(xí)機制，以此動態(tài)學(xué)習(xí)解碼過程中破壞節(jié)點數(shù)目，解碼器按圖4所示結(jié)構(gòu)執(zhí)行解碼過程。

當(dāng)編碼器輸出特征矩陣X后，解碼器在X向量維度方向末尾加上用于充當(dāng)終止符的NV個虛擬節(jié)點特征xV，得到新的特征矩陣X′，具體節(jié)點個數(shù)NV根據(jù)問題規(guī)模決定。本文根據(jù)觀察到的大量參數(shù)實驗結(jié)果發(fā)現(xiàn)，當(dāng)虛擬節(jié)點特征向量與圖嵌入相同（即xV=xG）時，模型測試效果最佳，因此本文實驗中所有虛擬節(jié)點特征向量均設(shè)置為圖嵌入xG。

在進(jìn)入下一解碼單元前，解碼器需要判斷選擇的破壞節(jié)點是否為終止節(jié)點。一旦終止節(jié)點被選擇，對于該CVRP實例，本輪生成有效序列η的解碼過程已經(jīng)結(jié)束，但是模型在訓(xùn)練過程中需要同時并行訓(xùn)練批量不同CVRP實例，每個實例特征不同，對應(yīng)合適的破壞節(jié)點數(shù)目也不盡相同，因此解碼過程不可能恰好同時結(jié)束。解碼過程結(jié)束較早的實例只能繼續(xù)調(diào)用解碼單元直到所有實例解碼結(jié)束，因此解碼器需要分別識別每個實例對應(yīng)實際破壞數(shù)目和將不必要的解碼單元考慮到后期梯度更新的計算過程。上述過程不僅增加了訓(xùn)練難度，而且顯著降低了模型推理準(zhǔn)確度，模型不再適合繼續(xù)并行訓(xùn)練。

為實現(xiàn)批量訓(xùn)練以提高訓(xùn)練效率，本文設(shè)計了一種實時更新的mask機制：當(dāng)前被選擇ηt在mask矩陣對應(yīng)位置所在元素更新為1，選擇的破壞節(jié)點特征xi與當(dāng)前GRU隱藏狀態(tài)ht作為下一時間步GRU模塊的輸入，一旦解碼器選擇了終止節(jié)點，mask矩陣對應(yīng)節(jié)點位置所在元素將被標(biāo)記為-1，下一時間步，該終止節(jié)點（同時適用于所有節(jié)點）的注意力分?jǐn)?shù)uti按式（12）更新，經(jīng)過softmax函數(shù)后終止節(jié)點被選擇的概率會與1充分接近，因此其他節(jié)點幾乎無法再被解碼器選擇，修復(fù)算子可以直接剔除后續(xù)所有相同終止節(jié)點。所有時間步的解碼過程結(jié)束后，解碼器按式（13）計算聯(lián)合概率p（π（η）），由于終止節(jié)點被選擇的概率接近1，計算中其被取對數(shù)后接近于0，對后續(xù)的模型訓(xùn)練與推理造成的影響可以忽略不計。

實時更新的mask機制可以設(shè)置模型學(xué)習(xí)參數(shù)的范圍。例如破壞節(jié)點數(shù)目范圍［Nmin，Nmax］：通過設(shè)置GRU調(diào)用次數(shù)約束模型學(xué)習(xí)到的最大破壞節(jié)點數(shù)目Nmax。針對最小破壞節(jié)點數(shù)目Nmin，解碼器在解碼前將所有終止節(jié)點對應(yīng)mask值都設(shè)置為1（即uti=－∞），經(jīng)softmax函數(shù)輸出的被選擇概率接近于0。一旦已生成Nmin個待破壞節(jié)點，解碼器就恢復(fù)終止節(jié)點的初始mask值（默認(rèn)為0），進(jìn)而可以選擇到終止節(jié)點，繼續(xù)終止符學(xué)習(xí)過程。

解碼器完成上述所有解碼任務(wù)后，最后輸出破壞節(jié)點序列η。修復(fù)算子從η中刪除所有虛擬節(jié)點，得到可用于與環(huán)境實際交互的破壞節(jié)點序列η′，之后嚴(yán)格按照η′中節(jié)點順序依次修復(fù)路線。

3 基于PPO的強化學(xué)習(xí)訓(xùn)練算法

本文采用基于actor-critic架構(gòu)的PPO算法訓(xùn)練模型，其核心思想在于：PPO每次更新策略時，會根據(jù)一種叫clipped surrogate objective的損失函數(shù)，對當(dāng)前策略的優(yōu)化幅度進(jìn)行限制，從而保持網(wǎng)絡(luò)優(yōu)化過程的穩(wěn)定性。本文將由編碼器和解碼器構(gòu)成的TE-GAT模型作為訓(xùn)練算法框架的策略網(wǎng)絡(luò)即actor，負(fù)責(zé)輸出動作，再單獨設(shè)計一個兩層的前饋神經(jīng)網(wǎng)絡(luò)作為價值網(wǎng)絡(luò)即critic，負(fù)責(zé)評估當(dāng)前訓(xùn)練狀態(tài)的價值函數(shù)。θ和分別表示actor和critic的網(wǎng)絡(luò)參數(shù)。

3.1 馬爾可夫過程定義

利用LNS算法框架解決VRP問題時，解路線會根據(jù)接受規(guī)則從當(dāng)前解迭代到另一個解，此過程是一個馬爾可夫決策過程（Markov decision process，MDP）［34］。在使用PPO算法訓(xùn)練神經(jīng)網(wǎng)絡(luò)前，需要對該MDP建模，具體定義MDP基本元素：狀態(tài)、動作、獎勵函數(shù)、折扣因子及狀態(tài)轉(zhuǎn)移函數(shù)等。由于PPO是基于策略梯度的強化學(xué)習(xí)算法，無須定義一個顯式的狀態(tài)轉(zhuǎn)移函數(shù)，本文只討論前四項基本元素：

b）獎勵。在訓(xùn)練過程中的每一步，將獎勵定義為這一步路線成本與上一步路線成本之差，具體定義見式（14）（15）。

Ccost（t）=Ddist（t）+C×K（14）

Rt=Ccost（t）-Ccost（t-1）（15）

其中：Ddist（t）表示當(dāng)前第t時間步時所有解路線總距離；K表示當(dāng)前解路線總數(shù)；C表示單輛車單次出車的固定成本；Ccost（t）表示第t時間步時所有解路線總距離與固定成本之和；Rt表示第t時間步環(huán)境給出的獎勵。

c）折扣因子。折扣因子是一個介于0～1的實數(shù)，用于調(diào)節(jié)當(dāng)前獎勵和未來獎勵之間的重要性比重。本文使用γ表示折扣因子，實驗中設(shè)定為0.99。

d）動作。在狀態(tài)st下，動作為解碼器輸出的有序排列破壞節(jié)點序列at。

3.2 基于經(jīng)驗回放的數(shù)據(jù)采樣

為了充分利用數(shù)據(jù)，提高樣本使用效率，本文使用經(jīng)驗回放（experience replay）［35］來收集訓(xùn)練數(shù)據(jù)。經(jīng)驗回放會構(gòu)建一個回放緩沖區(qū)（replay buffer）：某一個特定策略與環(huán)境交互之后儲存收集數(shù)據(jù)的地方。

具體到本文，從初始解出發(fā)，TE-GAT模型可以從環(huán)境中采樣得到一系列四元組數(shù)據(jù)（狀態(tài)st、動作at、獎勵Rt、下一狀態(tài)st+1），通過對MDP設(shè)置限定的步數(shù)，得到由若干四元組數(shù)據(jù)構(gòu)成的軌跡。收集訓(xùn)練數(shù)據(jù)的過程：訓(xùn)練算法使用當(dāng)前策略下的actor與環(huán)境不斷交互，生成大量軌跡數(shù)據(jù)。為訓(xùn)練actor和critic，算法需要收集的數(shù)據(jù)與四元組數(shù)據(jù)不同，具體為狀態(tài)st、動作at、對數(shù)動作概率ln pt及優(yōu)勢函數(shù)A^t等，由此組成新四元組數(shù)據(jù)。訓(xùn)練算法將軌跡數(shù)據(jù)包含的新四元組數(shù)據(jù)收集起來，打亂順序按訓(xùn)練批量BS分別存儲到回放緩沖區(qū)，后續(xù)訓(xùn)練網(wǎng)絡(luò)參數(shù)時再從中采樣數(shù)據(jù)。

3.3 價值網(wǎng)絡(luò)和策略網(wǎng)絡(luò)訓(xùn)練

針對critic的訓(xùn)練，本文按式（16）定義損失函數(shù)［36］：

其中：V（st）表示當(dāng)前狀態(tài)st和網(wǎng)絡(luò)參數(shù)下critic的策略梯度；α為學(xué)習(xí)率。

針對actor的訓(xùn)練，本文采用PPO-截斷LCLIP（θ）作為目標(biāo)函數(shù)，按式（20）最大化LCLIP（θ）。

3.4 模擬退火算法

為提升學(xué)習(xí)效果，本文LNS算法框架根據(jù)模擬退火（simulated annealing，SA）［8］算法更新每次迭代的解，以此獲得高質(zhì)量的問題解作為訓(xùn)練數(shù)據(jù)。SA是一種迭代類算法，能夠很好地應(yīng)用于鄰域搜索算法［37］。模型需要大量隨機問題的較優(yōu)問題解來指導(dǎo)學(xué)習(xí)，而SA在解決大規(guī)模問題方面能提供較優(yōu)解，從而形成強化學(xué)習(xí)的環(huán)境［38～40］。具體針對訓(xùn)練過程中解的迭代即MDP軌跡上的每一步，若新產(chǎn)生的解在成本上優(yōu)于現(xiàn)有解或者滿足式（21），則可替代現(xiàn)有解進(jìn)行下一次迭代。

D（t）dist

其中：rnd表示隨機數(shù)，服從［0，1］的均勻分布；T（t）為MDP第t步時的溫度，隨迭代次數(shù)的增加，按照T（t+1）=αTT（t）計算更新，αT為溫度更新參數(shù)。

算法1 TE-GAT訓(xùn)練算法框架

算法描述了使用基于PPO的強化學(xué)習(xí)算法訓(xùn)練TE-GAT模型的流程，當(dāng)達(dá)到設(shè)定訓(xùn)練回合數(shù)Nepoch后，訓(xùn)練算法終止。通過引入PPO算法，能夠有效地控制策略更新幅度，避免過大的策略變動，從而提高訓(xùn)練的穩(wěn)定性和效果。

4 計算實驗

本文通過三組實驗驗證TE-GAT模型的實用性和可行性。三組實驗都需訓(xùn)練與測試模型：訓(xùn)練時，根據(jù)問題規(guī)模的不同，使用隨機生成的CVRP實例訓(xùn)練對應(yīng)模型。測試時，從公開數(shù)據(jù)集CVRPLIB選取對應(yīng)規(guī)模標(biāo)準(zhǔn)算例測試。第一組實驗包含四種規(guī)模CVRP，將TE-GATE與Google OR-tools、基于相同LNS框架的EGATE［23］及Random-LNS算法進(jìn)行比較，測試本文模型的實際性能。第二組實驗針對EGATE設(shè)置了六組破壞節(jié)點數(shù)目參數(shù)實驗，驗證學(xué)習(xí)算法參數(shù)的效用價值。第三組實驗探索本文所提改進(jìn)鄰域搜索算法求解大規(guī)模CVRP問題時的尋優(yōu)能力。

4.1 實驗數(shù)據(jù)和參數(shù)設(shè)置

本文將考慮解決的CVRP問題規(guī)模設(shè)置為n，對訓(xùn)練中的每個CVRP實例，n個節(jié)點的坐標(biāo)都在100×100或1 000×1 000的方格網(wǎng)絡(luò)中按均勻分布隨機生成，第一個生成的節(jié)點默認(rèn)為倉庫。根據(jù)對應(yīng)測試標(biāo)準(zhǔn)算例設(shè)置需求區(qū)間與最大負(fù)載Ccap，例如標(biāo)準(zhǔn)算例E-n51-k5，每個需求點的需求滿足［1，41］的均勻分布，每輛車的最大負(fù)載設(shè)為160。每一回合訓(xùn)練中，算法通過上述設(shè)定隨機生成128個CVRP實例數(shù)據(jù)，不斷迭代更新實例。每回合共收集了640 000個實例數(shù)據(jù)，每個實例數(shù)據(jù)分布相同，總共訓(xùn)練500回合。

對于不同規(guī)模訓(xùn)練任務(wù)超參數(shù)的設(shè)置，BS=100，Nmin均設(shè)為0，Nmax依次為5、10、20和25，NV依次為5、10、20和25。Nrollout=10，dx=64，de=16，TE-GAT層數(shù)為2，鄰居數(shù)目k=5，模型優(yōu)化器選擇Adam［41］算法，學(xué)習(xí)率為3×10－4，測試評估批量大小為100。

實驗主要在Ubuntu操作系統(tǒng)下使用一臺配置單張2.20 GHz Intel Xeon Gold 5220R CPU和NVIDIA Geforce RTX 2080Ti GPU的服務(wù)器訓(xùn)練測試TE-GAT和其他對比模型。對問題規(guī)模在200節(jié)點以上的模型，額外使用一臺搭載Tesla V100 GPU的服務(wù)器訓(xùn)練。本文利用PyTorch構(gòu)造模型，使用Python 3.6編寫。

4.2 實驗結(jié)果分析

4.2.1 基于標(biāo)準(zhǔn)算例的對比實驗

本組實驗選取四種不同規(guī)模的CVRP問題，對應(yīng)使用的測試標(biāo)準(zhǔn)算例是E-n51-k5，M-n101-k10、M-n200-k16和X-n251-k28。實驗分別對比了Google OR-tools、Random-LNS和EGATE模型。其中Google OR-tools求解器內(nèi)置了專門解決VRP問題的模塊，Random-LNS所用鄰域搜索基本框架與本文設(shè)計相同，但其鄰域算子通過隨機函數(shù)生成破壞節(jié)點。

實驗中，EGATE與TE-GAT測試時輸入數(shù)據(jù)批量設(shè)置成100，在SA框架下迭代1 000次。由于模型并行計算特性，本文將一份問題算例復(fù)制100批次，在一次模型評估時間下計算出100份測試結(jié)果，實驗計算最終這100次測試的平均成本和最小成本。Random-LNS算法測試過程與前述一致。調(diào)用Google OR-tools時，基于局部搜索啟發(fā)式算法求解問題算例，搜索時間設(shè)置為其他方法運行的最長時間。

表1列舉TE-GAT、EGATE、Google OR-tools和Random-LNS在標(biāo)準(zhǔn)算例集上的測試結(jié)果。表中算法的組成結(jié)構(gòu)為{模型名}{評估批次}-{迭代次數(shù)}，例如TE-GAT100-1K表示TE-GAT模型在實驗中的評估批量為100，迭代次數(shù)為1 000。由表1可以看出，對于不同規(guī)模的CVRP問題，除求解器外，本文TG-GAT模型優(yōu)化結(jié)果均優(yōu)于其他方法。隨著問題規(guī)模增大，TE-GAT測試結(jié)果的優(yōu)勢更顯著，但與最優(yōu)值的求解差距也在增大，在n=51、200的情況下其最小值的gap分別優(yōu)于求解器1.19%、9.96%。其他規(guī)模下，兩者gap相差不超過1.2%，但求解器搜索時間顯著長于本模型。

表2展示了TE-GAT與EGATE在訓(xùn)練規(guī)模n=51、101、200及251的CVRP問題時模型所占用的顯卡內(nèi)存大小。隨著問題規(guī)模從51～251的增大，EGATE模型占用顯存增長速度顯著快于TE-GAT模型，求解X-n251-k28時TE-GAT模型占用的顯存與EGATE相差12.9倍，實驗數(shù)據(jù)證明對于更大規(guī)模的問題，TE-GAT更適合用于訓(xùn)練。

圖5描繪了不同問題規(guī)模下不同模型的平均成本收斂曲線圖。由曲線圖可知，與其他算法相比，TE-GAT在所有問題規(guī)模下收斂速度最快，收斂值也更接近最優(yōu)值。問題規(guī)模越大， TE-GAT相對其他算法的平均收斂值差距與收斂速度逐漸增大。實驗結(jié)果表明本文設(shè)計的終止符學(xué)習(xí)機制可以提升鄰域搜索算子尋求最優(yōu)解的能力。

4.2.2 破壞節(jié)點數(shù)目分析

本文選擇學(xué)習(xí)破壞節(jié)點數(shù)目的一個潛在研究假設(shè)是：針對同規(guī)模CVRP問題，破壞節(jié)點數(shù)目與模型的尋優(yōu)能力并不一直保持正相關(guān)。為驗證假設(shè)，采用標(biāo)準(zhǔn)算例M-n101-k10測試具有不同固定破壞節(jié)點數(shù)目的EGATE模型，根據(jù)組成結(jié)構(gòu){模型名}-{破壞節(jié)點數(shù)目}依次定義6個模型，分別訓(xùn)練與測試模型，實驗結(jié)果如表3和圖6所示。

由表3和圖6可知，伴隨破壞節(jié)點從10～60的增長，破壞節(jié)點數(shù)目與模型求解性能數(shù)量關(guān)系呈先上升后下降趨勢。針對平均值，EGATE-40求解結(jié)果最優(yōu)，節(jié)點數(shù)目增加到60時，計算與最優(yōu)值之間的gap，EGATE-60比EGATE-10增加了約1.1%。求解最小值時，對比EGATE-30，EGATE-40反而無法尋找到最優(yōu)解。上述分析充分證明了破壞節(jié)點數(shù)目與模型求解性能并不一直呈正相關(guān)，破壞節(jié)點數(shù)目增加過多，模型求解性能逐漸下降，表明本文設(shè)計的終止符學(xué)習(xí)機制具有實際的效用價值。

4.2.3 求解大規(guī)模CVRP問題

為測試TE-GAT模型在大規(guī)模CVRP問題上的表現(xiàn)，本文選擇X-n561-k42算例為測試數(shù)據(jù)集，每個需求點的需求滿足［1，10］的均勻分布，每輛車的最大負(fù)載設(shè)為74。訓(xùn)練問題規(guī)模增大使得模型訓(xùn)練與推理所需計算資源較大，因此本文將訓(xùn)練回合數(shù)減小至200，測試批次減小到50。同時為擴大模型的視野域，將TE-GAT層數(shù)增大到3層，其他參數(shù)設(shè)定與前述實驗相同。測試結(jié)果如圖7所示，TE-GAT的求解表現(xiàn)優(yōu)于OR-tools和SISR［42］算法，后者是當(dāng)前解決CVRP問題較為優(yōu)秀的手工啟發(fā)式算法。TE-GAT尋找到的近似解與最優(yōu)值差距僅為9.2%。

5 結(jié)束語

本文基于圖神經(jīng)網(wǎng)絡(luò)與深度強化學(xué)習(xí)，提出了一個可學(xué)習(xí)的鄰域搜索算子神經(jīng)網(wǎng)絡(luò)模型TE-GAT，以此混合LNS算法形成了一種求解組合優(yōu)化問題的改進(jìn)鄰域搜索算法。TE-GAT模型由編碼器和解碼器組成，編碼器使用圖注意力網(wǎng)絡(luò)對不同問題的圖結(jié)構(gòu)進(jìn)行編碼。解碼器基于GRU解碼單元配合終止符實現(xiàn)有序解碼。終止符學(xué)習(xí)機制通過控制算法解碼過程學(xué)習(xí)LNS算法參數(shù)。本文采用PPO算法訓(xùn)練鄰域搜索智能模型，根據(jù)多種規(guī)模的CVRP標(biāo)準(zhǔn)算例，設(shè)置三組實驗檢驗?zāi)Ｐ涂尚行耘c實用性。實驗結(jié)果證明，本文改進(jìn)鄰域搜索算法在相同迭代次數(shù)或計算時間內(nèi)，相較對比算法模型有更好的優(yōu)化效果與收斂性。對基于深度神經(jīng)網(wǎng)絡(luò)的改進(jìn)鄰域搜索類算法，通過終止符學(xué)習(xí)算法參數(shù)是一條可行的優(yōu)化方向。針對求解大規(guī)模組合優(yōu)化問題，TE-GAT具有顯著的性能優(yōu)勢與進(jìn)一步求解更大規(guī)模組合優(yōu)化問題的潛力。

實驗考慮參數(shù)變化范圍越大，相關(guān)計算量隨之顯著增加，收斂效果也會波動，因此本文模型在實際訓(xùn)練中學(xué)習(xí)的參數(shù)范圍較小。進(jìn)一步的研究方向可以考慮：a）面對學(xué)習(xí)參數(shù)數(shù)量范圍較大的問題，設(shè)計能快速收斂的終止符學(xué)習(xí)機制；b）拓展本研究到其他組合優(yōu)化問題，如TSP問題、JSP問題和多星多任務(wù)調(diào)度問題等。

參考文獻(xiàn)：

［1］Korte B，Vygen J. Combinatorial optimization： theory and algorithms［M］. 5th ed. Berlin： Springer-Verlag，2012： 2-8.

［2］Dantzig G B，Ramser J H. The truck dispatching problem［J］.Mana-gement Science，1959，6（1）： 80-91.

［3］Muter I，Cordeau J F，Laporte G. A branch-and-price algorithm for the multidepot vehicle routing problem with interdepot routes［J］. Transportation Science，2014，48（3）： 425-441.

［4］藍(lán)伯雄，吳李知. 鐵路客運網(wǎng)絡(luò)列車開行方案優(yōu)化模型的列生成算法［J］. 運籌與管理，2012，21（1）： 1-10. （Lan Boxiong，Wu Lizhi. A column-gneration approach to line planning in rail passenger transport［J］. Operations Research and Management Science，2012，21（1）： 1-10.）

［5］Ehrgott M，Shao Lizhen，Schbel A. An approximation algorithm for convex multi-objective programming problems［J］. Journal of Global Optimization，2011，50（3）： 397-416.

［6］Halim A H，Ismail I. Combinatorial optimization： comparison of heuristic algorithms in traveling salesman problem［J］. Archives of Computational Methods in Engineering，2019，26（2）： 367-380.

［7］饒衛(wèi)振，金淳. 求解大規(guī)模CVRP問題的快速貪婪算法［J］. 管理工程學(xué)報，2014，28（2）： 45-54. （Rao Weizhen，Jin Chun. An efficient greedy heuristic for solving large-scale capacitated vehicle routing problem［J］. Journal of Industrial Engineering and Enginee-ring Management，2014，28（2）： 45-54.）

［8］Yu V F，Lin S W，Lee W，et al. A simulated annealing heuristic for the capacitated location routing problem［J］. Computers & Industrial Engineering，2010，58（2）： 288-299.

［9］Wang Jiangjiang，Jing Youyin，Zhang Chunfa. Optimization of capacity and operation for CCHP system by genetic algorithm［J］. Applied Energy，2010，87（4）： 1325-1335.

［10］Loureno H，Martin O，Styutzle T，et al. Iterated local search： framework and applications［M］// Gendreau M，Potvin J Y. Handbook of Metaheuristics. Boston： Springer，2019： 129-168.

［11］李凱文，張濤，王銳，等. 基于深度強化學(xué)習(xí)的組合優(yōu)化研究進(jìn)展［J］. 自動化學(xué)報，2021，47（11）： 2521-2537. （Li Kaiwen，Zhang Tao，Wang Rui，et al. Research reviews of combinatorial optimization methods based on deep reinforcement learning［J］. Acta Automatica Sinica，2021，47（11）： 2521-2537.）

［12］Bello I，Pham H，Le Q V，et al. Neural combinatorial optimization with reinforcement learning［EB/OL］. （2016-11-29） ［2023-10-21］. https：//arxiv. org/abs/1611. 09940.

［13］Khalil E，Dai Hanjun，Zhang Yuyu，et al. Learning combinatorial optimization algorithms over graphs［C］// Proc of the 31st International Conference on Neural Information Processing Systems. Cambridge，MA： MIT Press，2017： 6351-6361.

［14］Kool W，Van H H，Welling M. Attention，learn to solve routing problems！ ［EB/OL］. （2018-03-22） ［2023-10-21］. https：//arxiv. org/abs/1803. 08475.

［15］Vaswani A，Shazeer N，Parmar N，et al. Attention is all you need［C］// Proc of the 31st International Conference on Neural Information Processing Systems. Cambridge，MA： MIT Press，2017： 6000-6010.

［16］Chen Xinyun，Tian Yuandong. Learning to perform local rewriting for combinatorial optimization［C］// Proc of the 33rd International Conference on Neural Information Processing Systems. Cambridge，MA： MIT Press，2019： 6281-6292.

［17］Yolcu E，Póczos B. Learning local search heuristics for Boolean satisfiability［C］// Proc of the 33rd International Conference on Neural Information Processing Systems. Cambridge，MA： MIT Press，2019： 7992-8003.

［18］Ye Haoran，Wang Jiarui，Cao Zhiguang，et al. DeepACO： neural-enhanced ant systems for combinatorial optimization ［EB/OL］. （2023-11-04）. https：//arxiv.org/abs/2309.14032.

［19］Choo J，Kwon Y D，Kim J，et al. Simulation-guided beam search for neural combinatorial optimization［C］// Proc of the 36th International Conference on Neural Information Processing Systems. Cambridge，MA： MIT Press，2022： 8760-8772.

［20］Zhou Jianan，Wu Yaoxin，Song Wen，et al. Towards omni-generalizable neural methods for vehicle routing problems ［EB/OL］. （2023-06-20）. https：//arxiv.org/abs/2305.19587.

［21］Geisler S，Sommer J，Schuchardt J，et al. Generalization of neural combinatorial solvers through the lens of adversarial robustness ［EB/OL］. （2022-03-21）. https：//arxiv.org/abs/2110.10942.

［22］Ropke S，Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows［J］. Transportation Science，2006，40（4）： 455-472.

［23］Gao Lei，Chen Mingxiang，Chen Qichang，et al. Learn to design the heuristics for vehicle routing problem ［EB/OL］. （2020-02-20）. https：//arxiv.org/abs/2002.08539.

［24］Velikovic＇ P，Cucurull G，Casanova A，et al. Graph attention networks［EB/OL］. （2017-10-30） ［2023-10-21］. https：//arxiv. org/abs/1710. 10903.

［25］Wu Yaoxin，Song Wen，Cao Zhiguang，et al. Learning large neighborhood search policy for integer programming［C］// Proc of the 34th International Conference on Neural Information Processing Systems. Cambridge，MA： MIT Press，2021： 30075-30087.

［26］Cheng Hanni，Zheng Haosi，Cong Ya，et al. Select and optimize： learning to solve large-scale TSP instances［C］// Proc of the 26th International Conference on Artificial Intelligence and Statistics. New York： PMLR，2023： 1219-1231.

［27］Chen Mingxiang，Gao Lei，Chen Qichang，et al. Dynamic partial removal： a neural network heuristic for large neighborhood search ［EB/OL］. （2020-05-19） ［2023-10-21］. https：//arxiv.org/abs/2005.09330.

［28］Sutskever I，Vinyals O，Le Q V. Sequence to sequence learning with neural networks［C］// Proc of the 27th International Conference on Neural Information Processing Systems. Cambridge，MA： MIT Press，2014： 3104-3112.

［29］Mavrovouniotis M，Menelaou C，Timotheou S，et al. A benchmark test suite for the electric capacitated vehicle routing problem［C］// Proc of IEEE Congress on Evolutionary Computation. Piscataway，NJ： IEEE Press，2020： 1-8.

［30］Qiu Shenghao，You Liang，Wang Zheng. Optimizing sparse matrix multiplications for graph neural networks［C］// Proc of 34th International Workshop on Languages and Compilers for Parallel Computing. Cham： Springer International Publishing，2021： 101-117.

［31］Foo L G，Li Tianjiao，Rahmani H，et al. Unified pose sequence mode-ling［C］// Proc of IEEE/CVF Conference on Computer Vision and Pattern Recognition. Piscataway，NJ： IEEE Press，2023： 13019-13030.

［32］Réau M，Renaud N，Xue L C，et al. DeepRank-GNN： a graph neural network framework to learn patterns in protein-protein interfaces［J］. Bioinformatics，2023，39（1）： btac759.

［33］Fey M，Lenssen J E. Fast graph representation learning with PyTorch geometric［EB/OL］. （2019-03-06） ［2023-10-21］. https：//arxiv. org/abs/1903. 02428.

［34］Sutton R S，Barto A G. Reinforcement learning： an introduction［M］. 2nd ed. Cambridge，MA： MIT Press，2018.

［35］Mnih V，Kavukcuoglu K，Silver D，et al. Playing Atari with deep reinforcement learning［EB/OL］. （2013-12-19） ［2023-10-21］. https：//arxiv. org/abs/1312. 5602.

［36］胡尚民，沈惠璋. 基于強化學(xué)習(xí)的電動車路徑優(yōu)化研究［J］. 計算機應(yīng)用研究，2020，37（11）： 3232-3235. （Hu Shangmin，Shen Huizhang. Research on electric vehicle routing problem based on reinforcement learning［J］. Application Research of Computers，2020，37（11）： 3232-3235.）

［37］Zhou Yangming，Xu Wenqiang，F(xiàn)u Zhanghua，et al. Multi-neighborhood simulated annealing-based iterated local search for colored traveling salesman problems［J］. IEEE Trans on Intelligent Transportation Systems，2022，23（9）： 16072-16082.

［38］He Feng，Ye Qing. A bearing fault diagnosis method based on wavelet packet transform and convolutional neural network optimized by simulated annealing algorithm［J］. Sensors，2022，22（4）： 1410.

［39］Zhao Jiuxia，Mao Minjia，Zhao Xi，et al. A hybrid of deep reinforcement learning and local search for the vehicle routing problems［J］. IEEE Trans on Intelligent Transportation Systems，2020，22（11）： 7208-7218.

［40］Kosanoglu F，Atmis M，Turan H H. A deep reinforcement learning assisted simulated annealing algorithm for a maintenance planning problem［J/OL］. Annals of Operations Research. （2022-03-15）. https：//doi.org/10.1007/s10479-022-04612-8.

［41］Kingma D P，Ba J. Adam： a method for stochastic optimization［EB/OL］. （2014-12-22） ［2023-10-21］. https：//arxiv.org/abs/1412.6980.

［42］Christiaens J，Berghe G V. Slack induction by string removals for vehicle routing problems［J］. Transportation Science，2020，54（2）： 417-433.