一種基于圖神經(jīng)網(wǎng)絡的改進鄰域搜索算法

伍康 夏維 王子源

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

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

中圖分類號：TP183?? 文獻標志碼：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］，廣泛應用于交通運輸規(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)解，然而當問題規(guī)模較大時，將耗費巨大計算資源，難以拓展到大規(guī)模問題。解決規(guī)模較大的組合優(yōu)化問題時，多采用啟發(fā)式算法獲得近似最優(yōu)解，然而啟發(fā)式規(guī)則需要領(lǐng)域?qū)＜沂止ぴO計，高度依賴專業(yè)知識。隨著圖神經(jīng)網(wǎng)絡（GNN）結(jié)合深度強化學習（DRL）在求解組合優(yōu)化問題領(lǐng)域的發(fā)展，基于深度神經(jīng)網(wǎng)絡學習啟發(fā)式算子與操作符，并混合經(jīng)典啟發(fā)式求解框架已經(jīng)成為求解組合優(yōu)化問題的新途徑。

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

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

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

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

1 CVRP問題

VRP問題屬于組合優(yōu)化領(lǐng)域中的一類經(jīng)典問題，可被簡單描述為：一組車輛向多個需求有限用戶運送貨物，若車輛無法完成或已經(jīng)完成用戶需求，立即返回倉庫。問題優(yōu)化目標是在完成所有用戶需求的情況下使運輸路線總成本最小。本文主要解決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)絡的鄰域搜索算子策略網(wǎng)絡

2.1 原始嵌入特征

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

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

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

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

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

eij=［dij，bij］（2）

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

以上特征向量的所有元素都會經(jīng)過歸一化處理，歸一化后的原始特征向量將會作為CVRP圖特征輸入到編碼器。此外，本文采取通用的稀疏矩陣存儲格式（coordinate format，COO）［30］來存儲節(jié)點連接信息，COO是一個形狀為2×E（E為邊的數(shù)量）的矩陣，其每列存儲圖中某對源節(jié)點與目標節(jié)點之間的連接信息，該格式為大多數(shù)學者［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}）為輸入，兩種嵌入特征分別進入不同的全連接層，輸出維度分別為dx和de的新嵌入特征，計算過程見式（3）（4）。

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

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

2.3 解碼器

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

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

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

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

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

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

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

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

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

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

3 基于PPO的強化學習訓練算法

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

3.1 馬爾可夫過程定義

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

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

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

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

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

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

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

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

為了充分利用數(shù)據(jù)，提高樣本使用效率，本文使用經(jīng)驗回放（experience replay）［35］來收集訓練數(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ù)據(jù)構(gòu)成的軌跡。收集訓練數(shù)據(jù)的過程：訓練算法使用當前策略下的actor與環(huán)境不斷交互，生成大量軌跡數(shù)據(jù)。為訓練actor和critic，算法需要收集的數(shù)據(jù)與四元組數(shù)據(jù)不同，具體為狀態(tài)st、動作at、對數(shù)動作概率ln pt及優(yōu)勢函數(shù)A^t等，由此組成新四元組數(shù)據(jù)。訓練算法將軌跡數(shù)據(jù)包含的新四元組數(shù)據(jù)收集起來，打亂順序按訓練批量BS分別存儲到回放緩沖區(qū)，后續(xù)訓練網(wǎng)絡參數(shù)時再從中采樣數(shù)據(jù)。

3.3 價值網(wǎng)絡和策略網(wǎng)絡訓練

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

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

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

3.4 模擬退火算法

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

D（t）dist

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

算法1 TE-GAT訓練算法框架

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

4 計算實驗

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

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

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

對于不同規(guī)模訓練任務超參數(shù)的設置，BS=100，Nmin均設為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］算法，學習率為3×10－4，測試評估批量大小為100。

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

4.2 實驗結(jié)果分析

4.2.1 基于標準算例的對比實驗

本組實驗選取四種不同規(guī)模的CVRP問題，對應使用的測試標準算例是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ù)生成破壞節(jié)點。

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

表1列舉TE-GAT、EGATE、Google OR-tools和Random-LNS在標準算例集上的測試結(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在訓練規(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更適合用于訓練。

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

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

本文選擇學習破壞節(jié)點數(shù)目的一個潛在研究假設是：針對同規(guī)模CVRP問題，破壞節(jié)點數(shù)目與模型的尋優(yōu)能力并不一直保持正相關(guān)。為驗證假設，采用標準算例M-n101-k10測試具有不同固定破壞節(jié)點數(shù)目的EGATE模型，根據(jù)組成結(jié)構(gòu){模型名}-{破壞節(jié)點數(shù)目}依次定義6個模型，分別訓練與測試模型，實驗結(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ù)目增加過多，模型求解性能逐漸下降，表明本文設計的終止符學習機制具有實際的效用價值。

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

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

5 結(jié)束語

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

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

參考文獻：

［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］藍伯雄，吳李知. 鐵路客運網(wǎng)絡列車開行方案優(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］. 管理工程學報，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］李凱文，張濤，王銳，等. 基于深度強化學習的組合優(yōu)化研究進展［J］. 自動化學報，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］胡尚民，沈惠璋. 基于強化學習的電動車路徑優(yōu)化研究［J］. 計算機應用研究，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.