基于端到端深度強化學(xué)習(xí)求解有能力約束的車輛路徑問題

摘 要：有能力約束的車輛路徑問題（CVRP）是現(xiàn)階段供應(yīng)鏈應(yīng)用最常見的問題模型，現(xiàn)多采用啟發(fā)式算法求解。但隨著問題規(guī)模增大，啟發(fā)式算法求解速度慢且無法保證解的質(zhì)量。提出端到端深度強化學(xué)習(xí)（DRL）網(wǎng)絡(luò)框架對CVRP進行研究。首先利用邊聚合圖注意力網(wǎng)絡(luò)編碼器（EGATE）對車輛路徑規(guī)劃問題的圖表示進行特征嵌入編碼；然后設(shè)計多頭注意力解碼器（MAD）進行解碼，并提出多解碼策略以增加解的空間多樣性；接著利用帶回滾基線的基線REINFORCE算法對端到端網(wǎng)絡(luò)模型進行訓(xùn)練，基線可自適應(yīng)性更新以提升模型訓(xùn)練效果，并利用獎勵函數(shù)歸一化和Adam優(yōu)化器對算法進行優(yōu)化。最后通過對不同規(guī)模問題的實驗以及與其他算法進行對比，驗證了所提出端到端DRL框架的可行性與有效性，經(jīng)過訓(xùn)練的模型在CVRPLIB公共數(shù)據(jù)集上的平均求解時間僅需0.189 s即可得到較優(yōu)解。

關(guān)鍵詞：車輛路徑問題；路徑規(guī)劃；端到端模型；深度強化學(xué)習(xí)；基線REINFORCE算法

中圖分類號：TP399 文獻標(biāo)志碼：A 文章編號：1001-3695（2024）11-006-3245-06

doi：10.19734/j.issn.1001-3695.2024.03.0101

Solving capacitated vehicle routing problems based on end to end deep reinforcement learning

Ge Bin¹， Tian Wenzhi¹， Xia Chenxing^{1， 2}， Qin Wangbo¹

（1.School of Computer Science amp; Engineering， Anhui University of Science amp; Technology， Huainan Anhui 232001， China; 2.Institute of Energy， Hefei Comprehensive National Science Center， Hefei 230031， China）

Abstract：The capacitated vehicle routing problem （CVRP） is the most prevalent problem model in supply chain applications at present， and researchers often use heuristic algorithms to solve it， but the solution speed is slow and the quality of the solution cannot be guaranteed. This paper proposed an end-to-end deep reinforcement learning （DRL） network framework to study the CVRP problem. Firstly， it used the edge graph attention network encoder （EGATE） to perform feature embedding encoding on the graph representation of VRP. Then， it designed a multi-head attention decoder （MAD） to decode the encoded graph representation. Additionally， it proposed a multi-decoding strategy to enhance the spatial diversity of the solutions. Continuing with the training of the end-to-end network model using the baseline REINFORCE algorithm with a rollout baseline， the adaptive updating of the baseline was employed to enhance the effectiveness of model training. Additionally， reward function normalization and optimization using Adam optimizer were utilized to further improve the algorithm. Finally， this paper validated the feasibility and effectiveness of the proposed end-to-end DRL framework through experiments on problems of different scales， comparing its performance against other algorithms. The average solution time of the trained model on the CVRPLIB public dataset is only 0.189 s to obtain a better solution.

Key words：

vehicle routing problem（VRP）; path planning; end-to-end model; deep reinforcement learning; baseline REINFORCE algorithm

0 引言

車輛路徑問題（VRP）屬于組合優(yōu)化問題中典型的NP-hard問題^［1］。有能力約束的車輛路徑問題（capacitated vehicle routing problem， CVRP）是VRP中的一種基本問題，在運輸和物流配送中起著關(guān)鍵作用。

求解CVRP的傳統(tǒng)方法主要分為精確算法、近似求解法和啟發(fā)式算法^［2］。精確算法雖然能夠求解出最優(yōu)解，但是只在規(guī)模較小的求解情況下有效。近似求解法雖然能夠快速完成計算，但無法保證解的質(zhì)量。

啟發(fā)式算法如蟻群優(yōu)化算法^［3］、帝國競爭算法^［4］、煙花算法^［5］、蛙跳算法^［6］、蝙蝠算法^［7］，由于其高效的求解能力被廣泛應(yīng)用，但是啟發(fā)式算法需要針對不同問題設(shè)定特定的啟發(fā)措施。CVRP涉及多個變量，如車輛位置、剩余容量、客戶位置及其需求等，這些變量的組合形成一個高維度的狀態(tài)空間。上述三種傳統(tǒng)求解方法在如此龐大的狀態(tài)空間中尋找最優(yōu)解往往面臨計算復(fù)雜性和效率問題，盡管已有大量的求解策略，但仍然需要搭建更加高效的求解模型來進一步提升CVRP求解效率。

目前，DRL模型在面對復(fù)雜、數(shù)據(jù)規(guī)模較大的路徑規(guī)劃情景展現(xiàn)出的高效能力廣受研究者青睞，并取得突破性進展^［8］。Vinyals等人^［9］介紹了指針網(wǎng)絡(luò)（pointer network，PN），該網(wǎng)絡(luò)使用長短期記憶網(wǎng)絡(luò)（long-short term memory，LSTM）作為編碼器，注意力機制（attention mechanism，AM）作為解碼器，離線訓(xùn)練該模型以解決車輛路徑問題。受文獻［9］的指引，Ma等人^［10］把PN與GNN相結(jié)合并提出圖指針網(wǎng)絡(luò)（graph pointer network，GPN），利用GNN提取計算節(jié)點特征，再用PN進行解的構(gòu)造，提升了大規(guī)模車輛路徑問題的求解能力。受Transformer^［11］架構(gòu)的啟發(fā)，Kool等人^［12］借用Transformer提出新框架，其利用注意力機制對模型進行改進，超越了先前解決路徑問題的優(yōu)化性能。García-Torres等人^［13］以注意力機制為核心開發(fā)了組合的深度構(gòu)造器和擾動器來解決帶約束的車輛路徑規(guī)劃問題，此外還提出內(nèi)存有效算法，大幅降低內(nèi)存復(fù)雜性。Hu等人^［14］提出了一種雙向圖神經(jīng)網(wǎng)絡(luò)（BGNN），通過模仿學(xué)習(xí)依次生成下一個訪問節(jié)點，并且能夠與啟發(fā)式搜索相結(jié)合以進一步提高性能。Zhu等人^［15］提出一種基于門控余弦的注意力模型（GCAM）來訓(xùn)練策略模型，加速了模型的收斂過程。上述車輛路徑規(guī)劃算法雖然采用DRL框架，但是在使用深度強化學(xué)習(xí)的求解路徑規(guī)劃問題時，對圖表示信息考慮不充分、設(shè)計的解碼方式較為單一，導(dǎo)致模型得到的初始解的質(zhì)量較差，從而使求解結(jié)果不理想。

針對CVRP所存在的問題，以及深度強化學(xué)習(xí)框架目前所存在的局限性，本文提出一種端到端的深度強化學(xué)習(xí)網(wǎng)絡(luò)框架EGATE-MAD（edge-graph attention network encoder and multi-head attention decoder）用于高效求解CVRP。在該框架中，首先將CVRP中的邊信息和節(jié)點信息通過EGATE模塊進行信息聚合編碼，可獲得更加完整的圖結(jié)構(gòu)信息；接著通過多解碼器模塊對嵌入信息進行解碼，并在解碼時使用多解碼器策略來增加解的空間多樣性，以提高模型的求解精度；然后設(shè)計改進基線REINFORCE算法來訓(xùn)練EGATE-MAD模型；最后通過實驗驗證所提端到端深度強化學(xué)習(xí)框架在CVRP上的高效性。

1 問題描述

CVRP如圖1所示，存在單個配送中心為多個客戶節(jié)點配送所需貨物，配送中心擁有一定數(shù)量的車輛，運輸車輛的最大容量和配送中心的坐標(biāo)位置已知；每個客戶節(jié)點的需求量以及位置坐標(biāo)已知；目標(biāo)是通過最優(yōu)車輛路徑規(guī)劃實現(xiàn)總路徑最小化。

為了便于分析和研究，對該問題提出四點假設(shè)：a）

配送中心只有一個，所有車輛均從配送中心出發(fā)且最終返回配送中心；

b）在安排車輛運輸時，已經(jīng)獲取了各客戶節(jié)點的位置信息；

c）每輛運輸車的載貨容量相同;

d）每個客戶點的需求均小于車輛最大容量。

本文通過無向圖G=（V，E，W）定義CVRP，n_i表示節(jié)點，其中i∈V={0，1，…，m}，m表示節(jié)點的數(shù)量，n_i表示第i個節(jié)點的坐標(biāo)，下標(biāo)i=0表示配送中心節(jié)點，i（igt;0）表示第i個客戶節(jié)點，a_ij∈E，i， j∈V代表節(jié)點i到j(luò)之間的邊，e_ij∈W表示a_ij的距離信息。結(jié)果集=（₁，…，_m）表示路徑規(guī)劃序列，_t∈{1，…，m}，_t≠_v，?t≠t′。每輛車都有各自需求大小Dgt;0，每一個客戶節(jié)點i存在一個需求σ_i，0lt;σ_ilt;D。并定義車場節(jié)點的需求σ₀為0。

根據(jù)上述定義，端到端網(wǎng)絡(luò)模型對CVRP進行求解，如圖2所示。端到端模型捕捉CVRP中客戶和車輛之間復(fù)雜的空間關(guān)系，通過處理圖結(jié)構(gòu)數(shù)據(jù)，能夠有效表示CVRP實例中的節(jié)點信息（客戶）和邊信息（路徑），即編碼器將所有輸入實例的節(jié)點特征編碼映射到高維特征。在給定的問題實例s情況下，解碼器根據(jù)編碼器的輸出在每一個時間步長t根據(jù)解碼得到概率矩陣，采用搜索策略選擇下一個節(jié)點從而產(chǎn)生結(jié)果序列，不僅可以滿足問題約束，而且使總路程長度最小化，總路程長度被定義為

L（|s）=‖n_m－n₁‖₂+∑m－1t=1‖n_t－n_t+1‖₂（1）

其中：‖·‖₂表示L₂范式，本文端到端網(wǎng)絡(luò)模型為實例s定義一個隨機策略p（|s）；基于鏈?zhǔn)礁怕室?guī)則，序列的選擇概率由網(wǎng)絡(luò)模型參數(shù)集θ計算：

p_θ（|s）=∏mt=1p_θ（_t|s，_t′，?t′lt;t）（2）

采用回滾基線的REINFORCE強化學(xué)習(xí)算法，通過模擬和經(jīng)驗積累，逐步優(yōu)化路徑規(guī)劃策略p（|s）以達到收斂。后續(xù)將介紹上述端到端模型的搭建以及強化學(xué)習(xí)算法的設(shè)計。

2 端到端模型建立

由于GAT對圖拓?fù)浣Y(jié)構(gòu)具有強大的表示能力，文獻［16，17］在解決組合優(yōu)化問題時均采用其進行編碼，鑒于此，本文的編碼器EGATE（edge-graph attention network encoder）基于圖注意力網(wǎng)絡(luò)（graph attention network，GAT）設(shè)計。同時解碼器是基于Transformer進行構(gòu)建，但由于Transformer的輸出維度預(yù)先固定，不能根據(jù)輸入維度而變化，所以不能直接用于解決組合優(yōu)化問題（CVRP是組合優(yōu)化問題的一種）。Vinyals等人^［9］提出的PN使用注意力機制，基于softmax概率分布，在每個解碼步驟從輸入序列中選擇一個成員作為輸出。PN使Transformer模型能夠應(yīng)用于組合優(yōu)化問題，其中輸出序列的長度由源序列決定?？紤]到這一想法，解碼器的設(shè)計遵循PN的方式來輸出節(jié)點，其中每個節(jié)點在每個解碼時間步長通過使用softmax概率分布作為“指針”的概率值。

2.1 編碼器

將圖G=〈V，E，W〉作為輸入，經(jīng)過編碼器模塊，得到融合的節(jié)點嵌入信息，如圖3所示。

輸入的節(jié)點特征由一個二維坐標(biāo)n_i和采用歐幾里德算法得到的邊信息特征e_ij，i， j∈{1，2，…，m}組成。之后再通過全連接層（圖3中的FC layer）將維度擴展到d_x維和d_e維。嵌入操作是由一個W_i和b_i組成的可學(xué)習(xí)線性變換執(zhí)行，即

x^（0）_i=BN（W₀n_i+b₀）

?i∈{1，…，m}（3）

_ij=BN（W₁e_ij+b₁）

?ij∈{1，…，m}（4）

其中：用x^（l）_i來表示EGAT模塊中第l層嵌入，l∈{1，…，L}，BN（·）表示批歸一化處理；x^（0）_i（x⁰₁，x⁰₂，…，x⁰_i），x^（0）_i∈R^d_x表示EGAT中的第一層輸入，隨著層數(shù)的增加，x^（l）_i隨之變換，而邊信息特征={₁₁，₁₂，…，_mm}，_ij∈R^d_e將保持不變。

圖4詳細(xì)描述了EGAT如何將節(jié)點嵌入信息和邊嵌入信息進行聚合。將擴展嵌入信息（x^（l）_i，_ij）作為輸入。注意力權(quán)重向量計算為

h_{concat，i， j}=concat（x^（l）_i，x^（l）_j，_ij）（5）

α_{i， j}=LeakyReLU（W_L*h_{concat，i， j}）（6）

_{i， j}=exp（α_{i， j}）∑jexp（α_{i， j}）（7）

其中：W_L為可學(xué)習(xí)的權(quán)重矩陣。然后，通過類似于GAT的注意力機制更新每個節(jié)點信息的嵌入以產(chǎn)生EGAT的輸出：

x^（l+1）_i=x^（l）_i+∑j_ijUn^（l）_j（8）

其中：_ij代表可以進行學(xué)習(xí)的權(quán)重矩陣；x^（l）_i經(jīng)過一輪EGAT模塊后得到融合邊的嵌入信息x^（l+1）_i。最后，將最高層輸出的節(jié)點嵌入x^（L）_i被進一步送到平均池化層，得到表示整個解決方案的編碼器的最終輸出。

2.2 解碼器

解碼器采取類似于Transformer模型的結(jié)構(gòu)，但不使用殘差連接、批歸一化處理以及全連接層，而是使用兩個注意力子層代替。在此基礎(chǔ)之上設(shè)計了多解碼器結(jié)構(gòu)，即具有相同結(jié)構(gòu)但不共享參數(shù)的多個解碼器，不同的解碼器使用索引d∈{1，…，D}來表示。圖5說明了單個解碼器的解碼過程。

其中，第一層通過多頭注意力機制來計算上下文向量，第二層通過自注意力層和softmax層來輸出將要選擇節(jié)點的概率分布。解碼器在每個時間步長t∈{1，…，m}，會根據(jù)節(jié)點嵌入信息，和先前的輸出節(jié)點_t′的信息生成_t（tlt;t′）。在t時刻，解碼器的上下文信息輸入q^（0）_t是通過第一個輸出的節(jié)點信息₁和最后一個輸出的節(jié)點信息_t－1計算而來。在t=1時，q^（0）₁可根據(jù)編碼器輸出的全局圖嵌入信息和一個可學(xué)習(xí)的d_x維的參數(shù)向量v進行計算：

q^（0）_t=+W_x（x^（L）_π1‖x^（L）_πt－1）

tgt;1

+v t=1 （9）

其中：W_x是一個可學(xué)習(xí)的矩陣；q^（0）_t表示解碼器第一層的上下文信息。之后，通過多頭（H個）注意力機制產(chǎn)生的新的上下文信息q^（1）_t。

針對解碼器的多頭注意力機制，本文定義維度d_v，通過節(jié)點嵌入信息和上下文向量q^（0）_t來計算k_i∈R^d_v，v_i∈R^d_v，q∈R^d_v：

q=W^Qq^（0）_t

v_i=W^Vx^（L）_i

k_i=W^Kx^（L）_i

i∈{1，2，…，m}（10）

其中：W^K∈R^d_v^×d_x、W^Q∈R^d_v^×d_x、W^V∈R^d_v^×d_x為可學(xué)習(xí)的權(quán)重矩陣（d_v=d_x/H）。然后，q和K={k₁，…，k_m}用來計算第一層解碼器中t時刻的注意力系數(shù)u^（1）_i，t∈R，i∈{1，…，m}。

u^（1）_i，t=q^Tk_id_v

if i≠_t′?t′lt;t

－∞ otherwise （11）

其中：將在t時刻已經(jīng)被選擇的節(jié)點的注意力系數(shù)設(shè)置為-∞。之后，使用softmax激活函數(shù)將注意力系數(shù)u^（1）_i，t進行歸一化處理，如式（12）所示。

^（1）_i，t=softmax（u^（1）_i，t）（12）

接下來H頭注意力機制通過式（13）進行操作，第H頭歸一化注意力系數(shù)表示為

q^（1）_t=W_f·（‖H_h－1∑mi=1（^（1）_i，t）^hvhi）（13）

其中：W_f是可訓(xùn)練權(quán)重矩陣。多頭注意力機制有助于增強注意力學(xué)習(xí)過程的穩(wěn)定性。

第二層是一個以上下文信息向量q^（1）_t作為輸入的自注意力機制層，使用式（12）來計算此層的時刻t下的注意力系數(shù)^（2）_i，t∈R，i∈{1，…，m}，將注意力系數(shù)用tanh函數(shù)劃分在［－C，C］，C=10。對于任意節(jié)點i∈{1，…，m}，都可以通過式（14）獲得它的選擇概率p_i，t。最后，根據(jù)概率分布p_i，t，可使用采樣或貪婪策略來預(yù)測要訪問的下一個節(jié)點，直至形成一次路徑規(guī)劃任務(wù)。

p_i，t=p_θ（_t|s，_t′?t′lt;t）=softmax（u^（2）_i，t）（14）

本文對車輛剩余容量、解碼器上下文向量與掩碼進行如下設(shè)置：

a）車輛剩余容量更新。屏蔽已經(jīng)服務(wù)過的需求節(jié)點，因此，不需要更新已服務(wù)需求節(jié)點的需求。解碼器在t時刻選擇下一個節(jié)點_t，剩余的車輛容量用D′_t表示，并且按照式（15）更新。

D′_t=D′_t－1－δ′_t

_t=i，i∈{1，…，m}

D _t=0（15）

b）解碼器上下文向量更新。解碼器t時刻的上下文向量q^（0）_t由圖嵌入信息，節(jié)點嵌入信息_t和車輛剩余容量D′_t－1組成，如式（16）所示。

q^（0）_t=+W_x（n^（L）_t－1‖D′_t－1）

tgt;1

+W_x（n^（L）₀‖D′_t） t=1 （16）

c）掩碼更新。掩碼由需求節(jié)點掩碼和車場節(jié)點掩碼兩部分組成，掩碼操作屏蔽已經(jīng)服務(wù)的需求節(jié)點或需求節(jié)點需求大于車輛剩余容量時的需求節(jié)點。即當(dāng)δ′_igt;D′_t－1或i≠_t′?t′lt;t，i∈{1，…，m}時，將需求節(jié)點的注意力系數(shù)進行如下更改：u^（0）_i，t，u^（1）_i，t=－∞。對于車場掩碼，如果車場不是下一個要訪問的節(jié)點，或者剛從倉庫節(jié)點離開，即當(dāng)t=1（車輛剛離開車場節(jié)點）或者_t－1=0（車輛在車場節(jié)點），作如下更新：u^（0）_0，t，u^（1）_0，t=-∞。

圖6顯示了多解碼器的結(jié)構(gòu)，其中的單個解碼器模塊如圖5所示。它們具有相同結(jié)構(gòu)但是不共享參數(shù)，每個單獨的解碼器都可以生成一個排列^d=（₁，…，_m），d∈（1，…，D），從排列的排列池中擇優(yōu)選擇最終解決方案以增加解空間的多樣性。

3 回滾基線REINFORCE算法

本文引入改進的基線REINFORCE算法來訓(xùn)練端到端模型。該算法通過計算單智能體的累計回報估計策略梯度并訓(xùn)練單智能體策略。將損失函數(shù)定義為Loss（θ|s）=E_{～pθ（|s）}［L（|s）］。參數(shù)θ通過一種帶回滾基準(zhǔn)b的REINFORCE算法進行優(yōu)化，如式（17）所示。

Kool等人^［12］在解決路徑規(guī)劃問題時提出了帶回滾基準(zhǔn)的REINFORCE算法，并證明了其有效性，算法流程如圖7所示。該算法基于actor-critic算法^［18］，actor網(wǎng)絡(luò)指的是前文的圖注意力網(wǎng)絡(luò)，而critic網(wǎng)絡(luò)是由多個一維卷積層組成，并且與actor共享相同的編碼器網(wǎng)絡(luò)。actor-critic算法中的critic網(wǎng)絡(luò)被基線actor網(wǎng)絡(luò)所取代，該網(wǎng)絡(luò)可以被描述為雙actor結(jié)構(gòu)。在每個歷元結(jié)束時，使用解碼策略來比較當(dāng)前訓(xùn)練策略和基線策略的結(jié)果。然后，根據(jù)現(xiàn)有研究中對評估實例進行在顯著性水平為α（α=0.05）的T檢驗，如果策略網(wǎng)絡(luò)輸出的解顯著優(yōu)于基準(zhǔn)網(wǎng)絡(luò)，則對基準(zhǔn)網(wǎng)絡(luò)參數(shù)θ進行回滾更新。在訓(xùn)練過程中，本文使用了包括獎勵函數(shù)歸一化和Adam優(yōu)化器學(xué)習(xí)率退火在內(nèi)的“代碼級優(yōu)化”來提高基線REINFORCE算法的訓(xùn)練能力。

每個小批量中的獎勵函數(shù)歸一化：在標(biāo)準(zhǔn)的基線方法實現(xiàn)中，不是將獎勵直接從環(huán)境中輸入目標(biāo)，而是執(zhí)行某種基于折扣的縮放方案。本文沒有執(zhí)行這種基于折扣的縮放方案，相反，通過減去每個小批量中的平均值并除以標(biāo)準(zhǔn)偏差來歸一化獎勵L（|s）。

Adam優(yōu)化器學(xué)習(xí)率退火：在訓(xùn)練過程中使用了學(xué)習(xí)率衰減，并在每個歷元結(jié)束時更新了學(xué)習(xí)率：

l_new=l_old·（β）^epoch（18）

其中：l_new和分別為更新前后的學(xué)習(xí)率；β是退火率。圖7是整個基線算法流程。

用于組合優(yōu)化問題的有效搜索算法包括波束搜索、鄰域搜索、樹搜索、采樣搜索、貪婪搜索等。本文使用采樣搜索算法以及貪婪搜索算法進行訓(xùn)練。在采樣搜索時，在解碼的每個時刻t∈{1，…，m}，隨機策略p_{θ（t|S，t′}，?t′lt;t）根據(jù)當(dāng)前概率分布對要選擇的節(jié)點進行采樣，為了提高采樣的多樣性，本文采用文獻［12］方法，使用溫度超參數(shù)來修改采樣方程，修改后的方程如下：

p_i，t=p_θ（_t|s，_t′?t′lt;t）=softmaxu^（2）_i，tλ（19）

其中：采用文獻［12］的設(shè)定，取超參數(shù)λ=2，1.8，1.2（分別對應(yīng)CVRP20、50、100）確保采樣的多樣性，使p_i，t的分布略微分散，防止模型盲目自信。在訓(xùn)練過程中，通常需要隨機采樣來探索環(huán)境，以獲得更好的模型性能，而貪婪解碼總是選擇概率最大的節(jié)點，雖然搜索速度大幅提高，但是模型性能會降低。

4 實驗

4.1 實驗環(huán)境設(shè)置

為證明本文端到端深度強化學(xué)習(xí)框架的效果，在文獻［19］定義的車輛路徑問題環(huán)境下進行實驗，自該環(huán)境提出以來被用于訓(xùn)練及測試國內(nèi)外各類DRL方法來解決車輛路徑規(guī)劃相關(guān)問題^{［19～22］}。

分別對三個問題規(guī)模為20、50和100的CVRP進行實驗，實驗所需訓(xùn)練數(shù)據(jù)、驗證數(shù)據(jù)和測試數(shù)據(jù)都是在單位正方形［0，1］×［0，1］中隨機均勻繪制。生成節(jié)點個數(shù)為21、51、101的實例，其中第一個節(jié)點為車場節(jié)點。因此，每種路徑規(guī)劃問題實例的規(guī)模為20、50、100，以及對應(yīng)的車容量設(shè)為30、40、50。需求節(jié)點的需求從{1，2，…，9}進行均勻采樣，本文將需求節(jié)點的需求通過公式σ′_i=σ_i/10進行標(biāo)準(zhǔn)化處理，使需求分布在［0，1］，因此，對應(yīng)的車容量變?yōu)?、4、5。在訓(xùn)練階段，為基線REINFORCE強化學(xué)習(xí)算法生成節(jié)點規(guī)模為20和50的實例各409 600個，節(jié)點規(guī)模為100的實例384 000個。訓(xùn)練迭代次數(shù)為100。對于驗證數(shù)據(jù)和測試數(shù)據(jù)，使用與其他研究相同數(shù)據(jù)分布的實例數(shù)據(jù)。此外，采用來自公共數(shù)據(jù)庫CVRPLIB的基準(zhǔn)測試數(shù)據(jù)。

基于上述設(shè)定，實驗在GPU為RTX A4000（16 GB）、CPU為12 vCPU Intel Xeon Gold 5320 CPU @ 2.20 GHz、內(nèi)存為32 GB的平臺上使用PyTorch進行構(gòu)造，并用Python 3.7實現(xiàn)。表1列出了訓(xùn)練過程的相關(guān)超參數(shù)的值。

4.2 實驗結(jié)果分析

實驗結(jié)果如表2、3所示。表2列出了所提框架在不同規(guī)模（CVRP20、50、100）的生成實例上的訓(xùn)練結(jié)果。分別與近年來較為熱門的算法：AM^［12］、CDCP^［13］、GCAM^［15］、文獻［20］、AM-D^［21］、L2I^［23］、LKH3^［24］、HGS^［25］、Gurobi進行比較，其中，Gurobi為組合優(yōu)化問題的高效求解器。表3選取公開數(shù)據(jù)集CVRLIB中的不同實例對已經(jīng)訓(xùn)練好的模型進行測試并與蟻群算法（ACO）、超啟發(fā)式算法HH_PG^［26］進行對比。其中：距離越小越好；Gap值表示與現(xiàn)有最優(yōu)結(jié)果的差距（CVRP20、50、100的最優(yōu)結(jié)果分別來自于Gurobi、LKH3^［24］、L2I^［23］），越小越好；OPT為最優(yōu)值；時間為總耗時，越少越好，值為10 000個實例求解時間的平均值。

由表2可以看出，采樣解碼策略（本文方法（sampling））取得了優(yōu)異的效果，優(yōu)于AM、AM-D、GCAM，僅次于CDCP、文獻［20］。但是在求解時間上，以規(guī)模20的實驗結(jié)果為例，訓(xùn)練時間遠(yuǎn)少于它們。貪婪解碼（本文方法（greedy））貪婪地選擇概率最大的節(jié)點作為下一個訪問節(jié)點，又由于神經(jīng)網(wǎng)絡(luò)進行并行計算能夠同時處理多個算例，從而讓貪婪解碼能夠以非?？斓乃俣惹蠼鈫栴}。例如CVRP20中，本文方法（greedy）耗時為3 s，而本文方法（sampling）耗時15 min。此外，訓(xùn)練迭代曲線如圖8所示，可以看出各個規(guī)模的訓(xùn)練在100個epoch內(nèi)都可以得到很好的收斂。圖9為CVRP20、50、100訓(xùn)練的可視化結(jié)果，其中，每個回路代表車輛從車場出發(fā)，運輸完成后返回車場節(jié)點。

表3的實驗結(jié)果進一步證明了本文模型的求解能力，該實驗選取公開數(shù)據(jù)集CVRLIB中的不同實例對已經(jīng)訓(xùn)練好的模型進行測試。實驗使用規(guī)模為50的已訓(xùn)練模型，采用貪婪解碼策略對每個實例進行單次求解，并且與蟻群算法（ACO）、超啟發(fā)式算法HH_PG^［26］進行對比。由表3可知，雖然HH_PG算法在求解質(zhì)量上優(yōu)于本文方法（2.80% vs 0.032%），但是HH_PG算法的結(jié)果是針對每個算例進行單獨執(zhí)行20次并選出最優(yōu)解。相反，本文所提框架對每個算例只進行單次求解，求解時間遠(yuǎn)優(yōu)于HH_PG算法和ACO算法（0.189 s vs 142.14 s）。因此，本文框架在求解質(zhì)量和運行時間上較為均衡，并且可以在本地進行訓(xùn)練，在實際應(yīng)用中進行實時求解。

4.3 消融實驗

為證明所設(shè)計端到端深度強化學(xué)習(xí)框架中模塊的有效性，在本節(jié)完成了消融實驗工作。需要證明該框架中的兩個重要組成部分均有效：model1表示邊信息的融入模塊；model2表示多解碼器策略模塊。為此設(shè)計了四個實驗，分別為基模型base、base+model1、base+model2、base+model1+model2。四種實驗使用相同的參數(shù)，在三種問題規(guī)模（20、50、100）的數(shù)據(jù)集上進行訓(xùn)練，并且分別使用相應(yīng)規(guī)模的測試數(shù)據(jù)來進行測試并比較，消融實驗結(jié)果如表4所示。

從表4可以得出以下結(jié)論：當(dāng)完整模型缺少model1、mo-del2中任意模塊或同時缺少兩種模塊時，平均距離均增加。因此，本文端到端深度學(xué)習(xí)框架中兩個重要組成部分均有效。

5 結(jié)束語

本文提出一種端到端深度強化學(xué)習(xí)的網(wǎng)絡(luò)框架來解決車輛路徑規(guī)劃問題。在編碼器部分，以圖注意力網(wǎng)絡(luò)為基礎(chǔ)，編碼器將節(jié)點信息和邊信息充分融合得到編碼信息。在解碼器部分，使用基于Transformer的解碼器進行解碼，采用多解碼器策略來增加解的空間多樣性。接著為端到端網(wǎng)絡(luò)模型設(shè)計了基于回滾基線REINFORCE的強化學(xué)習(xí)算法進行訓(xùn)練，并使用獎勵函數(shù)歸一化和Adam優(yōu)化器進行優(yōu)化。最后通過隨機生成的大量實例以及公開數(shù)據(jù)集進行實驗并與現(xiàn)有深度強化學(xué)習(xí)方法、啟發(fā)式方法作對比。此外，還設(shè)置了消融實驗證明模塊的有效性。實驗結(jié)果表明，所提框架在各種實例上的求解時間和求解質(zhì)量更為均衡，可以實現(xiàn)線下訓(xùn)練和線上實時求解，并且邊信息融入和多解碼器結(jié)構(gòu)模塊對整體框架均有效。

本文考慮在固定分布和規(guī)模上進行深度模型訓(xùn)練，由于車輛路徑規(guī)劃問題的隨機性較強，對于不同規(guī)模、不同分布、甚至未知規(guī)模或者分布的實例，模型的求解能力會降低。未來，在本文基礎(chǔ)上，將考慮如何提高模型在不同規(guī)模或者分布上的泛化能力。

參考文獻：

［1］蔡延光， 王世豪， 戚遠(yuǎn)航， 等. 帝國競爭算法求解CVRP［J］. 計算機應(yīng)用研究， 2021， 38（3）： 782-786. （Cai Yanguang， Wang Shihao， Qi Yuanhang， et al. Empire CVRP competition algorithm［J］. Application Research of Computers， 2021， 38（3）： 782-786.）

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

［3］孫志國， 肖碩， 吳毅杰， 等. 基于遷移學(xué)習(xí)和參數(shù)優(yōu)化的干擾效能評估方法［J］. 電子與信息學(xué)報， 2024， 46（6）： 2515-2524. （Sun Zhiguo， Xiao Shuo， Wu Yijie， et al. Interference performance evaluation method based on transfer learning and parameter optimization［J］. Journal of Electronics amp; Information Technology， 2024， 46（6）： 2515-2524.）

［4］丁增良， 陳玨， 邱禧荷. 一種應(yīng)用于旅行商問題的萊維飛行轉(zhuǎn)移規(guī)則蟻群優(yōu)化算法［J］. 計算機應(yīng)用研究， 2024， 41（5）： 1420-1427. （Ding Zengliang， Chen Jue， Qiu Xihe. An ant colony optimization algorithm for Lévy flight transfer rules applied to traveling salesman problems［J］. Application Research of Computers， 2024， 41（5）： 1420-1427.）

［5］魏振春， 傅宇， 馬仲軍， 等. 帶時間窗的無線可充電傳感器網(wǎng)絡(luò)多目標(biāo)路徑規(guī)劃算法［J］. 電子學(xué)報， 2022， 50（8）： 1819-1829. （Wei Zhenchun， Fu Yu， Ma Zhongjun， et al. Multi objective path planning algorithm for wireless rechargeable sensor networks with time windows［J］. Acta Electronica Sinica， 2022， 50（8）： 1819-1829.）

［6］蔡勁草， 王雷， 雷德明. 基于蛙跳算法的分布式裝配混合流水車間調(diào)度［J］. 華中科技大學(xué)學(xué)報： 自然科學(xué)版， 2023， 51（12）： 37-44. （Cai Jincao， Wang Lei， Lei Deming. Distributed assembly hybrid flow shop scheduling based on frog jump algorithm［J］. Journal of Huazhong University of Science and Technology： Natural Science Edition， 2023， 51（12）： 37-44.）

［7］謝良波， 李宇洋， 王勇， 等. 基于自適應(yīng)蝙蝠算法的室內(nèi)RFID定位算法［J］. 通信學(xué)報， 2022， 43（8）： 90-99. （Xie Liangbo， Li Yuyang， Wang Yong， et al. Indoor RFID positioning algorithm based on adaptive bat algorithm［J］. Journal on Communications， 2022， 43（8）： 90-99.）

［8］雷坤， 郭鵬， 王祺欣， 等. 基于end-to-end深度強化學(xué)習(xí)的多車場車輛路徑優(yōu)化［J］. 計算機應(yīng)用研究， 2022， 39（10）： 3013-3019. （Lei Kun， Guo Peng， Wang Qixin， et al. End-to-end deep reinforcement learning framework for multi-depot vehicle routing problem［J］. Application Research of Computers， 2022， 39（10）： 3013-3019.）

［9］Vinyals O， Fortunato M， Jaitly N. Pointer networks［C］// Proc of the 28th International Conference on Neural Information Processing Systems. Cambridge， MA： MIT Press， 2017： 2692-2700.

［10］Ma Qiang， Ge Suwen， He Danyang， et al. Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning［EB/OL］. （2019-11-12）. https：//arxiv.org/abs/1911.04936.

［11］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. Red Hook， NY： Curran Associates Inc.， 6000-6010.

［12］Kool W， Van Hoof H， Welling M. Attention， learn to solve routing problems！ ［EB/OL］. （2019-02-07）. https：//arxiv.org/abs/1803.08475.

［13］García-Torres R， Macias-Infante A A， Conant-Pablos S E， et al. Combining constructive and perturbative deep learning algorithms for the capacitated vehicle routing problem［EB/OL］. （2022-11-25）. https：//arxiv.org/abs/2211.13922.

［14］Hu Yujiao， Zhang Zhen， Yao Yuan， et al. A bidirectional graph neural network for traveling salesman problems on arbitrary symmetric graphs［J］. Engineering Applications of Artificial Intelligence， 2021， 97： 104061.

［15］Zhu Tianyu， Shi Xinli， Xu Xiaoping， et al. An accelerated end-to-end method for solving routing problems［J］. Neural Networks， 2023， 164： 535-545.

［16］Drori I， Kharkar A， Sickinger W R， et al. Learning to solve combinatorial optimization problems on real-world graphs in linear time［C］// Proc of the 19th IEEE International Conference on Machine Learning and Applications. Piscataway， NJ： IEEE Press， 2020： 19-24.

［17］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.

［18］Engstrom L， Ilyas A， Santurkar S， et al. Implementation matters in deep policy gradients： a case study on PPO and TRPO［EB/OL］. （2020-05-25）. https：//arxiv.org/abs/2005.12729.

［19］Nazari M， Oroojlooy A， Taká M， et al. Reinforcement learning for solving the vehicle routing problem［C］// Proc of the 32th International Conference on Neural Information Processing Systems. Red Hook， NY： Curran Associates Inc.， 2018： 9861-9871.

［20］Wu Yaoxin， Song Wen， Cao Zhiguang， et al. Learning improvement heuristics for solving routing problems［J］. IEEE Trans on Neural Networks and Learning Systems， 2021， 33（9）： 5057-5069.

［21］Peng Bo， Wang Jiahai， Zhang Zizhen. A deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems［C］// Proc of the 11th International Conference on Automation， Information and Computing. Berlin： Springer， 2020： 636-650.

［22］Falkner J K， Schmidt-Thieme L. Learning to solve vehicle routing problems with time windows through joint attention ［EB/OL］. （2020-06-16）. https：//arxiv.org/abs/2006.09100.

［23］Lyu Hao， Zhang Xingwen， Yang Shuang. A learning-based iterative method for solving vehicle routing problems［C/OL］// Proc of International Conference on Learning Representations. （2019-12-20） ［2024-02-27］. https：//iclr.cc/virtual/2020/poster/1827.

［24］Helsgaun K. An effective implementation of the Lin-Kernighan traveling salesman heuristic［J］. European Journal of Operational Research， 2000， 126（1）： 106-130.

［25］Vidal T. Hybrid genetic search for the CVRP： open-source implementation and SWAP^* neighborhood［J］. Computers amp; Operations Research， 2022， 140： 105643-105643.

［26］張景玲， 孫鈺粟， 趙燕偉， 等. 策略梯度的超啟發(fā)算法求解帶容量約束車輛路徑問題［J］. 控制理論與應(yīng)用， 2024， 41（6）： 1111-1122. （Zhang Jingling， Sun Yusu， Zhao Yanwei， et al. Hyper-heuristic for the capacitated vehicle routing problem with policy gradient［J］. Control Theory and Applications， 2024，41（6）：1111-1122.）

［27］唐捷凱， 胡蓉， 錢斌， 等. 混合帝國競爭算法求解帶多行程批量配送的多工廠集成調(diào)度問題［J］. 電子學(xué)報， 2022， 50（7）： 1621-1630. （Tang Jiekai， Hu Rong， Qian Bin， et al. Hybrid empire competition algorithm for multi factory integrated scheduling problem with multi itinerary batch delivery［J］. Acta Electronica Sinica， 2022， 50（7）： 1621-1630.）

［28］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.

［29］Scarselli F， Gori M， Tsoi A C， et al. The graph neural network model［J］. IEEE Trans on Neural Networks， 2008， 20（1）： 61-80.