伍康 夏維 王子源

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

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

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

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

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

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

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

1 CVRP問(wèn)題

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

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

2.1 原始嵌入特征

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

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

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

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

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

eij=［dij，bij］（2）

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

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

2.2 編碼器

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

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

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

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

2.3 解碼器

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

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

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

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

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

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

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

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

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

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

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

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

3.1 馬爾可夫過(guò)程定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.4 模擬退火算法

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

D（t）dist

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

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

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

4 計(jì)算實(shí)驗(yàn)

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

4.1 實(shí)驗(yàn)數(shù)據(jù)和參數(shù)設(shè)置

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

對(duì)于不同規(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，測(cè)試評(píng)估批量大小為100。

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

4.2 實(shí)驗(yàn)結(jié)果分析

4.2.1 基于標(biāo)準(zhǔn)算例的對(duì)比實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

參考文獻(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)伯雄，吳李知. 鐵路客運(yùn)網(wǎng)絡(luò)列車開(kāi)行方案優(yōu)化模型的列生成算法［J］. 運(yùn)籌與管理，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問(wèn)題的快速貪婪算法［J］. 管理工程學(xué)報(bào)，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］李凱文，張濤，王銳，等. 基于深度強(qiáng)化學(xué)習(xí)的組合優(yōu)化研究進(jìn)展［J］. 自動(dòng)化學(xué)報(bào)，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］胡尚民，沈惠璋. 基于強(qiáng)化學(xué)習(xí)的電動(dòng)車路徑優(yōu)化研究［J］. 計(jì)算機(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.