基于end-to-end深度強化學習的多車場車輛路徑優化

摘要：為提高多車場車輛路徑問題（multi-depot vehicle routing problem，MDVRP）的求解效率，提出了端到端的深度強化學習框架。首先，將MDVRP建模為馬爾可夫決策過程（Markov decision process，MDP），包括對其狀態、動作、收益的定義；同時，提出了改進圖注意力網絡（graph attention network，GAT）作為編碼器對MDVRP的圖表示進行特征嵌入編碼，設計了基于Transformer的解碼器；采用改進REINFORCE算法來訓練該模型，該模型不受圖的大小約束，即其一旦完成訓練，就可用于求解任意車場和客戶數量的算例問題。最后，通過隨機生成的算例和公開的標準算例驗證了所提出框架的可行性和有效性，即使在求解客戶節點數為100的MDVRP上，經訓練的模型平均僅需2 ms即可得到與現有方法相比更具優勢的解。

關鍵詞：多車場車輛路徑問題；深度強化學習；圖神經網絡；REINFORCE算法；Transformer模型

中圖分類號：TP399文獻標志碼：A

文章編號：1001-3695（2022）10-020-3013-07

doi：10.19734/j.issn.1001-3695.2022.03.0095

End-to-end deep reinforcement learning framework for multi-depot vehicle routing problem

Lei Kun1a，Guo Peng1a，1b，Wang Qixin1a，Zhao Wenchao1a，Tang Liansheng2

（1.a.School of Mechanical Engineering，b.Technology amp; Equipment of Rail Transit Operation amp; Maintenance Key Laboratory of Sichuan Province，Southwest Jiaotong University，Chengdu 610031，China；2.School of Economics amp; Management，Ningbo University of Technology，Ningbo Zhejiang 315211，China）

Abstract：This paper proposed an end-to-end deep reinforcement learning framework to improve the efficiency of solving the multi-depot vehicle routing problem（MDVRP）.This paper modeled a novel formulation of the Markov decision process（MDP） for the MDVRP，including the definitions of its state，action，and reward.Then，this paper exploited an improved graph attention network（GAT） as the encoder to perform feature embedding on the graph representation of MDVRP，and designed a Transformer-based decoder.Meanwhile，it used the improved REINFORCE algorithm to train the proposed encoder-decoder model.Furthermore，the designed encoder-decoder model wasn’t bounded by the size of the graph.That was，once the framework was trained，it could be used to solve MDVRP instances with different scales.Finally，the results on randomly generated and published standard instances verified the feasibility and effectiveness of the proposed framework.Significantly，even on solving MDVRP with 100 customer nodes，the trained model takes only two milliseconds on average to obtain a very competitive solution compared with existing methods.

Key words：multi-depot vehicle routing problem；deep reinforcement learning；graph neural network；REINFORCE algorithm；Transformer model

0引言

隨著電子商務和交通運輸產業的不斷壯大，物流業飛速發展，中國乃至世界物流經歷了連續十多年的爆炸式增長。例如，2021年菜鳥、京東、順豐等大型物流公司的全國快遞業務量突破1 083億件，隨著構建新發展格局的加快和物流需求的增長，未來我國物流業務量仍會保持較快的增長。同時，物流行業的高速發展對大型實時物流調度系統提出了更高的要求，然而，物流配送產生的運輸和倉儲成本居高不下?；谖锪髋渌同F狀和時代需求，尋求高效的物流配送模式受到了學界和業界的廣泛關注。多車場車輛路徑問題（MDVRP）具有廣泛的應用場景，包括交通運輸、物流配送和快遞分發等實際情況，探索該問題的高效求解方法對我國供應鏈發展具有重要的理論和現實意義。MDVRP問題屬于車輛路徑問題（capacitated vehicle routing problem，CVRP）的一個變體。由于CVRP已是NP-hard問題，相比單車場的CVRP而言，MDVRP的解空間更加龐大，所以MDVRP也屬于NP-hard問題。

求解MDVRP的傳統方法主要包括精確算法、多項式時間近似算法、元啟發式算法。精確算法能夠求得最優解，但由于其NP-hard性質很難應用于求解50個客戶以上的問題［1］。多項式時間近似算法通常能夠得到有質量保證的解，但最優性保證較弱，甚至不能得到該問題的局部最優解。元啟發式算法如狼群算法［2］、蟻群優化算法［3］、蝙蝠算法［4］和變鄰域搜索算法［5］，由于其高性能被廣泛使用，但通常需要針對特定的問題定制和專業的領域知識［6］，并且難以在多項式時間內尋找到大規模問題的較優解。以上三種方法很少利用優化問題的共同特征，經常反復求解相同類型問題的算例，對于這些算例可以認為目標函數或約束中的系數值是從相同的基礎分布中采樣所得［7］。盡管出現了大量的求解策略，但求解效率仍然有進一步的提升空間和基于更加高效的求解框架搭建的必要，因此，引入學習的方法以高效尋找接近最優解決方案尤為重要。

近年來，越來越多的研究將深度強化學習（deep reinforcement learning，DRL）技術應用于求解組合優化問題，并取得了突破性進展。表1對現有基于強化學習求解路徑問題的方法進行了總結。強化學習可以進一步分為基于模型的和無模型的方法，而無模型強化學習方法可以分為value-based和policy-based方法或者兩者的結合（actor-critic）；此外，按路徑問題可以分為旅行商問題（travelling salesman problem，TSP）、CVRP和MDVRP。

大多數基于DRL的應用集中在路徑問題，如TSP和VRP。Vinyals等人［24］引入了sequence-to-sequence模型指針網絡（PtrNet）的監督學習框架來訓練求解TSP等組合優化問題，該模型通過softmax注意力機制（指針）來選擇輸入序列中的元素作為輸出的遞歸架構。Bello等人［25］引入了actor-critic風格的深度強化學習算法以無監督的方式訓練PtrNet來求解TSP，并且其性能在多達100個節點的TSP上優于以前的大多數近似算法。Nazari等人［16］在Bello的框架上進行了擴展以解決VRP。

包括VRP在內的大多數組合優化問題都具有圖結構［6］，可以很容易地通過現有的圖嵌入或圖網絡嵌入技術來建模，將圖信息嵌入到連續的節點表示中。圖神經網絡的最新發展可以用于網絡設計，因為它在信息嵌入和圖拓撲的信念傳播方面具有很強的能力［6］。然而，上述工作中使用的sequence-to-sequence神經網絡結構不能充分利用并提取該問題的圖結構信息，如圖中節點包含客戶的位置和需求信息、邊包含權重信息。作為處理非歐氏數據和捕捉圖結構信息的有力工具，圖神經網絡（graph neural network，GNN）近年來得到了廣泛的研究。

近年來基于GNN的近似求解器經過訓練后，其算法時間復雜度明顯優于傳統的運籌優化算法。Li等人［26］應用圖卷積網絡（GCN）［27］以及引導樹搜索算法來解決基于圖的組合優化問題，如最大獨立集和最小頂點覆蓋問題。Dai等人［7］通過GNN對問題算例進行編碼，與序列到序列模型相比，圖神經網絡具有節點順序不變性，更好地反映了TSP的組合結構，他們使用DQN［28］訓練structure2vec圖嵌入模型［29］。受Transformer架構［30］的激勵，Kool等人［8］提出了注意力模型以解決多種組合優化問題，并在策略梯度算法中使用Rollout基線顯著地改善了小規模路徑問題的求解結果。Nowak等人［31］以監督學習的方式使用深度GCN通過高度并行的波束搜索以非自回歸的方法構建有效的TSP圖表示并輸出行程。Drori等人［13］開發了新的框架來解決圖上的組合優化問題，該框架運用GAT求解眾多圖組合優化問題，他們稱該框架具有從小圖上的訓練到大圖上的測試和從隨機圖上的訓練到現實世界的圖上測試的泛化性能。然而大多數機器學習方法聚焦于求解單車場的車輛路徑問題，對于多車場車輛路徑問題的研究較少。王萬良等人［23］基于多頭注意力機制設計了多智能體強化學習框架求解MDVRP，并利用策略梯度算法進行訓練，他們的實驗結果表明所提出的多智能體深度強化學習模型及其與搜索策略的結合能夠快速獲得高質量的解；然而，文獻［23］沒有驗證其訓練后的模型泛化到不同規模算例的性能及泛化到真實世界算例（標準算例）的性能。相反，本文提出的編碼器—解碼器模型不受問題規模（即車場和客戶數）的約束，即經過訓練的模型可適用于任意車場和客戶數的算例，且能夠在毫秒級給出解決方案，該框架具有較強的泛化性能。通過對隨機生成數據集的測試，驗證了該框架的有效性；此外，通過VRPLIB的標準算例測試，驗證了該框架具有從隨機算例訓練到真實世界算例測試的泛化能力。

以上基于GNN的learning-based方法激勵本文探索其在求解MDVRP中的潛力，提出了基于端到端（end-to-end）的深度強化學習框架用于高效求解MDVRP。在該框架中，首先將MDVRP建模為馬爾可夫決策過程（MDP）。本文提出了殘差—邊—圖注意力網絡（residual edge graph attention network，RE-GAT）模型作為編碼器提取嵌入MDVRP圖表示的狀態特征，該模型是對GAT的改進。GAT在提取圖結構信息的過程中僅考慮節點的信息而忽視了邊的信息，而邊的特征可以為學習策略提供與優化目標相關的更多直接信息（如加權距離）。此外，同時輸入節點和邊信息有利于挖掘不同節點之間空間鄰接關系的特征。提出的RE-GAT模型將MDVRP圖表示中節點和邊（如權重）的信息進行融合并更新，并在層與層之間添加了殘差連接，有效地防止了深層模型中梯度消失和模型退化的問題。同時還基于Transformer模型設計了解碼器用于求解過程中高效地預測節點。所提出的編碼器—解碼器模型一經訓練即可適用于任意車場和客戶數量的算例，且能夠在毫秒級給出路徑優化方案。換言之，該框架可作為一種線下訓練、線上測試的實時優化框架。

為驗證該框架的可行性和有效性，本文設計了隨機生成的算例對框架進行訓練和測試，通過VRPLIB標準算例測試該框架的泛化性能，并與最新的基于機器學習方法和元啟發式算法進行對比，以驗證所提框架的優越性。最后，通過實驗驗證并分析了框架在訓練和測試階段運行時間的復雜度。

1問題描述

一般地，MDVRP可以描述為具有容量限制的一輛車向需求有限的多個客戶運送貨物，當車輛載物用完或不滿足客戶需求時返回倉庫，其目標是在滿足所有客戶需求的基礎上使得總路線長度最小化，圖1展示了具有兩車場的MDVRP示意圖。本文通過無向圖G=（V，E，W）來定義MDVRP，其中節點包括客戶和多個車場i={1，…，k，k+1，…，m}表示其原始特征ni，包括該節點的坐標n′i和需求信息δi。其中，i={1，…，k}表示車場節點，igt;k表示第i個客戶節點。客戶節點i∈{k+1，…，m}的貨物需求為δi，其中0lt;δilt;D，且Dgt;0表示車輛的容量。假設車場的需求δi=0，i∈{1，…，k}，aij∈E，i，j∈V，i≠j表示從節點i到j的邊，eij∈W表示aij的距離信息。車場和客戶節點坐標均從單位平方［0，1］×［0，1］中隨機生成，即對客戶節點數量為20、30、50的問題，本文分別生成n=20+k、50+k、100+k個節點，與之三個規模問題相對應的車輛容量為30、40、50，每個客戶節點需求在{1，…，9}中隨機產生。此外，將客戶節點需求歸一化到［0，1］，車輛容量D相應地變換為3、4、5。

本文引入所有節點的排列=（1，…，z）表示該問題的解，其中t∈{1，…，z}并且t≠t′，t≠t′。本文的目標是在給定問題算例的情況下找到問題的解，使得每個客戶節點只能訪問一次（車場節點可以多次訪問，即有z≥m），并且總路線長度最小。排列的長度定義為

L（|s）=‖nz-n1‖2+∑z-1t=1‖nt-nt+1‖2（1）

其中：‖·‖2表示2范數；‖nz-n1‖2表示最后服務的客戶節點到車場的距離。本文的圖—注意力模型為MDVRP算例s定義了一個隨機策略p（|s）?；阪準礁怕史▌t，序列的選擇概率可以基于圖—注意模型的參數集合θ計算：

pθ（|s）=∏mt=1pθ（t|s，t′，t′lt;t）（2）

編碼器對所有輸入節點的原始特征編碼嵌入到高維特征；解碼器基于編碼器的輸出在每一個時間步驟t選擇一個節點，從而產生輸入節點的排列。

2MDVRP的馬爾可夫決策過程定義

以下對MDVRP的馬爾可夫決策過程進行建模，其中包括對狀態、動作和收益的定義：

a）狀態。在時間步驟t，狀態由已訪問的節點所構成的子圖G′（G′G=（V，E，W））表示。

b）動作。在時間步驟t，動作是未進行服務的客戶節點或車場節點。

c）收益。本文的優化目標是最小化車輛的行駛距離L（|s）。首先計算時間步驟t到t+1所訪問的兩個節點的距離（‖nt-nt+1‖2），然后將智能體的即時收益定義為 -‖nt-nt+1‖2（強化學習的目標是最大化收益，因此取負值）。

3參數化強化學習智能體行為策略網絡

3.1編碼器

編碼器將圖G=（V，E，W）作為輸入，其結構如圖2所示。輸入節點特征為ni，輸入邊的特征為歐氏距離eij，i，j∈{1，…，m}。上述兩個特征分別通過全連接層（圖2中的FC層）嵌入（embedding）到dx和de維特征中，然后被送入RE-GAT進行編碼。式（3）（4）分別描述了節點和邊的嵌入過程。

x（0）i=BN（A0ni+b0）i∈{1，…，m}（3）

ij=BN（A1eij+b1）i，j∈{1，…，m}（4）

其中：A0和A1分別表示可學習的權重矩陣；b0和b1分別表示可學習的權重向量；BN（·）表示批歸一化（batch normalization）［32］。

本文中編碼器包含L層RE-GAT，圖3描述了單層RE-GAT如何將邊的信息集成到節點信息中并更新每個節點的信息。注意力系數αij表示第l（l∈{1，…，L}）層中節點j相對于節點i的權重系數（注意力系數），其中i，j∈{1，…，m}。

αij = exp（σ（gT［W（x（-1）i‖x（-1）j‖ij ）］））∑mz=1exp（σ（gT［W（x（-1）i‖x（-1）z‖iz ）］））（5）

其中：（·）T表示轉置運算符；·‖·表示連接操作符；g和W是可學習的權重向量和權重矩陣；σ（·）是LeakyReLU激活函數。圖2展示了具有多層RE-GAT的編碼器模型結構。RE-GAT的每一層通過式（5）和（7）描述的注意機制更新每個節點的特征向量。模型在每兩層之間使用了殘差連接（由式（6）表示），也就是說，第層的輸出被計算為

x（）i=x（）i，R+x（-1）i2lt;lt;L（6）

其中：x（）i，R由式（7）計算所得。

x（）i，R=∑mj=1αijW1x（-1）j（7）

其中：W1表示可學習的權重矩陣。第L層RE-GAT輸出每個節點的最終嵌入特征向量x（L）i。然后，用它們計算最終的圖嵌入向量={1，…，dx}，j∈Euclid Math TwoRAp，對于每個節點j∈{1，2，…，dx}由式（8）表示。

j=1m∑mi=1（x（L）i）jj=1，…，dx（8）

3.2解碼器

在解碼過程中，解碼器基于注意力機制生成待選擇節點（所有車場和客戶）的概率分布，即每個節點都會關聯一個概率值；然后通過掩碼（下文將詳細介紹）機制來處理相關約束，即避免重復訪問已服務的客戶節點和連續兩次選擇車場節點；最后，搜索策略基于所輸出的概率分布進行節點選擇，如貪婪搜索（貪婪地選擇概率最大的節點）或采樣的解碼策略（基于概率分布進行采樣）。調度中心的選取同樣適用于該解碼機制。傳統的啟發式算法通常采用先分組后規劃的思想［23］求解MDVRP，存在以下缺點［23］：a）不同分組各自規劃，這導致分組之間整體關聯性的缺失；b）啟發式方法中分組的優劣通常決定了整體規劃的優劣，而分組規則的制定需要專家領域知識，人為選取的分組規則很難達到最優效果。相反，深度強化學習智能體能夠通過數據驅動的方式與調度環境進行交互，進而不斷更新進化自身策略以最大化收益（對于路徑問題為總路線長度的負值），即在本文的解碼過程中強化學習策略選取調度中心的過程中無須依靠人為啟發式地進行干預。

本文采用類似于Transformer［30］模型所采用的多頭注意力機制來設計針對MDVRP的解碼器。與原始Transformer模型的結構不同，本文所設計的基于多頭注意力機制的解碼器為了提升計算效率只包含兩個注意力子層，且不使用殘差連接、批量歸一化和全連接層網絡。第一層通過多頭注意機制計算上下文向量，第二層輸出所選節點的概率分布，并基于此分別選擇節點。解碼按順序進行，在時間步驟t，首先利用圖嵌入向量、t-1時刻選擇的節點t-1的嵌入向量和車輛的剩余容量計算出上下文向量c（0）t：

c（0）t=+Wx（x（L） t-1‖D′t-1）tgt;1

+Wx（x（L）0‖D′t）t=1（9）

其中：Wx是可學習的權重矩陣；D′t-1和D′t分別表示兩個解碼步驟車輛的剩余容量。D′t的更新公式如下：

D′t=D′t-1-δ′tt∈{1，…，m}

Dt=0（10）

解碼器第一層的輸入是上下文向量c（0）t，該層產生新的上下文向量c（1）t。特別地，該上下文向量是通過一個多頭（H頭）注意力機制獲得的。式（11）描述了多頭注意力機制通過編碼器輸出的節點的嵌入向量和上下文向量c（0）t來分別計算鍵向量ki∈Euclid Math TwoRApdv、值向量vi∈Euclid Math TwoRApdv、查詢向量q∈Euclid Math TwoRApdv。

q=WQc（0）t，vi=WVx（L）i，ki=WKx（L）i i∈{1，2，…，m}（11）

其中：WK∈Euclid Math TwoRApdv×dx、WQ∈Euclid Math TwoRApdv×dx和WV∈Euclid Math TwoRApdv×dx（dv=dx/H）都是可學習的權重矩陣。本文使用上下文向量c（0）t來計算每個查詢向量q，然后利用編碼器輸出的節點嵌入向量x（L）i，i∈{1，2，…，m}計算鍵向量k={k1，…，km}和值向量v={v1，…，vm}，并利用查詢向量q和鍵向量k={k1，…，km}計算第一解碼層的注意系數u（1）i，t∈Euclid Math TwoRAp，i∈{1，…，m}。

u（1）i，t=

-∞if i≠t′（t′lt;t）or δ′igt;D′t-1 or t=1 or t-1∈{1，…，k}

qTkidvotherwise（12）

本文通過掩碼（mask）來避免重復選擇客戶節點、車輛剩余容量不滿足該客戶節點和連續兩次選擇車場節點（即在t-1時刻選擇車場節點t-1∈{1，…，k}）。具體地，在式（12）中，通過將上述情況的注意力系數設置為-∞來掩碼，然后使用式（13）通過softmax激活函數將注意力系數u（1）i，t歸一化。

（1）i，t=softmax（u（1）i，t）i∈{1，…，m}（13）

其次，根據式（14）計算第h（h∈{1，…，H}）頭歸一化注意力系數（（1）i，t）h，其中1≤i≤m；然后將每個頭計算出的向量串聯起來，并通過全連接層計算得到最終的上下文向量c（1）t：

c（1）t=Wf·（‖Hh=1∑mi=1（（1）i，t）hvhi）（14）

其中：Wf是可學習的權重矩陣。該多頭注意機制有助于提高注意力學習過程的穩定性［33］。

第二層解碼器基于單頭注意力機制，其輸入是上下文向量c（1）t，然后利用式（15）計算第二解碼層在t時刻的注意力系數u（2）i，t∈Euclid Math TwoRAp，i∈{1，…，m}?；谖墨I［25］的工作，采用tanh激活函數將該系數截斷在［-C，C］內（本文選取C =10），再通過式（16）采用softmax激活函數獲得每個節點的選擇概率pi，t，i∈{1，…，m}。

u（2）i，t=

-∞if i≠t′（t′lt;t） or δi′gt;D′t-1 or t=1 or t-1 ∈{1，…，k}

C×tanh（c（1）tTkidv）otherwise（15）

pi，t=pθ（t|s，t′，t′lt;t）=softmax（u（2）i，t）（16）

最后，根據策略概率分布的pi，t，使用采樣或貪婪解碼來預測下一個要訪問的節點（車場或客戶節點）。

4基于策略梯度的深度強化學習算法

本文引入改進的REINFORCE算法來訓練所提出的模型，將損失函數定義為loss（θ|s）=Euclid Math TwoEAp～pθ（|s）［L（|s）］。該改進REINFORCE算法具有actor-critic風格，但又與傳統的將狀態—價值估計函數作為critic不同，與該算法的原始版本相比，本文所實現的版本添加了Rollout基線方法［8］以加速算法收斂速度以及增強優化性能。其損失函數的梯度計算過程如下：

θloss（θ|s）=Euclid Math TwoEAp～pθ（|s）［（L（|s）-b）θ log pθ（|s）］（17）

在所提出的具有Rollout基線版本的REINFORCE算法中，critic網絡被基線actor所取代。該算法的流程如圖4所示。算法可以描述為具有兩個actor的結構，基線actor的策略網絡πθBL（ θBL為參數集合）在每個epoch內被固定（即其參數不進行更新），該策略類似于DDQN［34］中固定目標Q-網絡；在每個epoch結束時，使用貪婪解碼來比較當前訓練actor和基線actor的結果；基線actor策略網絡的參數只有在測試算例上具有顯著提升（對其進行T檢驗，顯著性水平α=5%）才會進行更新。在訓練過程中，本文還采用代碼級優化的策略對該算法進行改進，包括Adam優化器的學習率衰減和獎勵函數的歸一化，提高了該算法的性能。

有效的組合優化搜索算法主要包括束波搜索、鄰域搜索和樹搜索。Bello等人［25］提出了諸如采樣、貪婪搜索和主動搜索等搜索策略。本文使用了以下兩種解碼策略：

a）貪婪解碼。一般來說，貪婪算法構造局部最優解并提供全局最優解的快速近似值。在每個解碼步驟中，貪婪地選擇概率最高的節點，當所有節點的要求都被滿足時，即搜索終止，從而構造出有效解。

b）隨機采樣。在每個解碼時間步驟t，隨機策略pθ（t|s，t′t′lt;t）根據概率分布隨機選擇節點來構造有效解。在測試過程中，Bello等人利用溫度超參數λ∈Euclid Math TwoRAp對式（16）進行修正，以保證采樣的多樣性。修改后的公式如下：

pi，t=pθ（t|s，t′t′lt;t）=softmax（u（2）i，tλ）（18）

通過對溫度超參數的網格搜索發現，溫度值分別為2.5、1.8、1.2時對于MDVRP20（客戶節點數為20）、MDVRP50和MDVRP100效果最好。在訓練過程中，通常需要模型探索環境以獲得更好的模型性能，因此采用隨機采樣的解碼策略；在測試過程中，本文使用了貪婪解碼策略。此外，根據現有研究的測試方法［8，25］，本文還采用隨機采樣的方法求得了1 280個解決方案并報告其最好的一個。

5計算實驗

本文通過實驗驗證所提出框架的可行性和有效性，實驗包括訓練和測試兩個部分，由于訓練需要大量數據，訓練數據由均勻分布隨機產生。測試數據集包括隨機生成的算例和公開的標準算例（Cordeau等人提出［35，36］），其分別用于測試所提出框架的有效性和泛化性能。此外本文還將所提出的框架與其他learning-based的方法、Google OR-tools和元啟發式算法進行了比較。

5.1數據集與超參數的選擇

為提高可讀性，本文將MDVRP的規模以客戶數—車場數的格式表示。本文所用到的數據集包括隨機生成的訓練數據、驗證數據和隨機測試數據，分別針對規模20-2、50-2和100-2從單位平方［0，1］×［0，1］中隨機生成MDVRP算例，并分別為20-2的訓練集生成了819 200個算例，為50-2和100-2的訓練集生成了768 000個算例，且每個模型訓練100個epoch。對于驗證數據和隨機測試數據，使用與訓練數據相同的分布，分別為每個規模生成10 000個算例。此外，本文還采用公開的標準算例（Cordeau等人提出［35，36］）來評估所提出的模型由隨機生成的算例訓練到真實世界算例測試的泛化性能以及測試不同規模算例（不同數量的車場以及客戶）的泛化性能。所有實驗在具有一塊Turbo HT（100W） DDR4-2400 CPU和一塊NVIDIA GeForce RTX 3090 GPU的計算機上進行。表2列出了訓練過程的其他相關超參數的值。本文的模型由PyTorch構造，并用Python 3.7進行實現。

5.2計算結果分析

5.2.1隨機算例分析

表3列出了所提框架（根據解碼策略的不同由Greedy、Sampling128和Sampling1280表示）、Google OR-tools和其他基于DRL的方法［23］在不同規模隨機生成的MDVRP上的測試結果。該表中距離（越小越好）和相對最優gap值為10 000個算例的平均值。此外，還給出了所有測試算例的平均運算時間。

由表3可以看出，采樣解碼策略能夠獲得所有方法給出結果的最好解。該策略對每個算例都執行128或1 280次采樣，即構造128或1 280個解并報告最好的一個。相反，貪婪解碼策略僅通過訓練后的模型在每次解碼過程中貪婪地選擇具有最高概率的節點以構造單個解。此外，基于神經網絡的并行計算可以對多個算例進行批處理，這使得訓練后的模型以貪婪解碼的方式具有極快的求解速度。例如，對于規模為100-2的10 000個MDVRP算例，所提出方法以貪婪解碼的方式求解單個算例只需要1.8 ms，而采樣的解碼方式需要1 580 ms。

Google OR-tools是基于局部搜索的高效求解器，文獻［23］是深度強化學習方法。然而，在所有規模的MDVRP上，所提出的框架無論采用貪婪解碼還是采樣解碼的方式都優于OR-tools和文獻［23］所提出的強化學習方法，且貪婪解碼方式在運行時間上也要遠優于這兩種方法。此外，圖5展示了訓練過程中各規模MDVRP的收斂曲線，可以看出，各規模的算例訓練在80個epoch后都能很好地收斂。

5.2.2公開算例分析

為評估所提出框架從隨機生成的算例泛化到真實世界算例以及泛化到不同規模（即不同客戶和車場數）的性能，本節將訓練后的模型（通過隨機生成的規模為100-2的MDVRP算例進行訓練）用于求解Cordeau等人［35，36］針對MDVRP提出的公開標準算例（客戶數50～160），所有結果均列在表4中。此外，為進一步評估所提出框架的性能，還與最先進的元啟發式算法（改進ACO［38］）進行比較，其結果同樣列在表4中。兩種方法的gap值均基于已知最好的解（best known solutions，BKS）求得。

由表4可以看出，雖然改進ACO算法在大部分算例上優于本文所提出的框架，且其平均gap值也更優（1.98% vs. 4.97%），但該改進ACO方法的結果是針對每個算例單獨執行100次并報告最好的一個，表中時間為平均時間；相反，本文所提出的框架采用貪婪解碼的策略對每個算例進行單次求解。本文所提出的框架在運行時間上要遠優于改進ACO算法［38］（0.09 s vs.51.59 s）。因此，本文所提出的框架在該數據集的求解質量和運行時間上較為均衡。此外，所提出的框架可以作為一種線下訓練線上測試使用的實時求解框架。

5.2.3拓展計算分析（CVRP）

為進一步評估所提出框架對于不同場景車輛路徑問題的求解性能及泛化能力，將所提出的框架用于求解單車場的CVRP。本節采用隨機算例進行實驗驗證，即由均勻分布隨機生成10 000個算例（與文獻［8，16］保持一致），并通過與現有的learning-based方法（表5中PtrNet和AM都是基于深度強化學習的方法）、Google OR-tools、Gurobi精確求解器和LKH3求解器進行對比來驗證所提出框架在單車場CVRP上的有效性。不同規模的CVRP算例的測試結果如表5所示。表中所列出的結果根據其求解方法的屬性可以分為三個大類，包括求解器、貪婪方法和采樣/搜索方法。除了所提出模型的結果，該表的其他結果均取自文獻［8］。在模型性能方面，所提出的框架無論是采樣還是貪婪解碼策略的結果都要優于其他所列出的基于學習的方法，其結果說明了所提出的框架在單車場CVRP場景下仍然具有較好的泛化性能，同時驗證了該模型具有遷移到其他場景VRP的潛力。

5.2.4框架計算時間復雜度分析

該框架通過線下訓練和線上測試的方式來求解路徑問題。接下來，通過對TSP的求解（大多數文獻通過求解TSP來分析時間復雜度［7，13］，為了便于與文獻中的方法進行比較，本文也通過TSP進行評估）來評估所提出模型在訓練和測試階段隨圖規模（即節點數）增大和運行時間的關系。本節采用的所有算例均由均勻分布隨機生成（與文獻［7，13］保持一致）。對于訓練階段，訓練時間不僅取決于問題的圖規模，還取決于訓練數據的數量和批量大小。不失一般性，這里用10 000個訓練實例和相同的批量大?。ㄅ看笮?28）測試了單個epoch內節點數從1增加到100實例的運行時間。圖6（a）顯示了所提出的框架在訓練階段的運行時間隨圖節點的增長呈線性增長。在測試階段，測試了圖規模（節點數）從1增加到500時，整個編碼器—解碼器模型的運行時間。圖6（b）顯示了所提出的模型在測試階段的運行時間隨圖規模（節點數）的增加呈線性增長。

表6總結了幾類方法，包括精確算法、啟發式算法和基于學習的方法在規模為100個節點的TSP上的運行時間復雜度、運行時間（平均值）和平均最優解間距。除了所提出框架的結果以外，所有的結果都取自表1。精確算法、近似算法、啟發式算法的運行時間在圖規模上至少呈平方增長，S2V-DQN［7］是強化學習方法，運行時間復雜度為O（n2），且具有較大的最優解間距（為8.4%），本文所提出框架的運行時間復雜度為O（n），在運行時間和最優解間距上都有較大的提升。GAT［13］與所提出的框架都具有相同的運行時間復雜度，但其最優解間距更大。

6結束語

本文提出了端到端的深度強化學習框架用于提升MDVRP的求解效率。為MDVRP建模了馬爾可夫決策過程，設計了改進圖注意力網絡作為編碼器對求解過程中的狀態信息進行編碼，還基于Transformer模型設計了解碼器模型。為訓練所提出的編碼器—解碼器模型，設計了改進REINFORCE算法。此外，所設計的框架不受問題規模的約束，一旦模型完成訓練就可以應用于不同規模的算例問題（不同的客戶數和車場數）。為驗證所提出框架的可行性和有效性，通過隨機生成的算例和公開標準算例進行了數值實驗，并與現有的learning-based方法、Google OR-tools、元啟發式算法進行對比。計算結果表明，所提出的框架對于求解不同規模及不同場景下的車輛路徑問題具有可行性和高效性。

本文考慮了靜態環境下的MDVRP，而在實際的物流運輸過程中，運輸環境通常是瞬息萬變的，即會面臨訂單動態到達的情況。基于本文所提出框架求解該問題的快速性，其具有在動態環境下進行實時調度車輛的潛力。因此，未來的研究將會專注于構建動態環境下的端到端深度強化學習框架。

參考文獻：

［1］Sharma N，Monika.A literature survey on multi depot vehicle routing problem［J］.International Journal for Scientific Research Deve-lopment，2015，3（4）：1752-1757.

［2］葉勇，張惠珍.多配送中心車輛路徑問題的狼群算法［J］.計算機應用研究，2017，34（9）：2590-2593.（Ye Yong，Zhang Huizhen.Wolf pack algorithm for multi-depot vehicle routing problem［J］.Application Research of Computers，2017，34（9）：2590-2593.）

［3］胡蓉，陳文博，錢斌，等.學習型蟻群算法求解綠色多車場車輛路徑問題［J］.系統仿真學報，2021，33（9）：2095-2108.（Hu Rong，Chen Wenbo，Qian Bin，et al.Learning ant colony algorithm for green multi-depot vehicle routing problem［J］.Journal of System Simulation，2021，33（9）：2095-2108.）

［4］戚遠航，蔡延光，蔡顥，等.泰森多邊形的離散蝙蝠算法求解多車場車輛路徑問題［J］.控制理論與應用，2018，35（8）：1142-1150.（Qi Yuanhang，Cai Yanguang，Cai Hao，et al.Voronoi diagram-based discrete bat algorithm for multi-depot vehicle routing problem［J］.Control Theory amp; Applications，2018，35（8）：1142-1150.）

［5］李洋，胡蓉，錢斌，等.兩階段算法求解多車場車輛路徑問題［J］.信息與控制，2020，49（6）：752-760.（Li Yang，Hu Rong，Qian Bin，et al.Two-stage algorithm for multi-depot vehicle routing problem［J］.Information and Control，2020，49（6）：752-760.）

［6］Bengio Y，Lodi A，Prouvost A.Machine learning for combinatorial optimization：a methodological tour d’horizon［J］.European Journal of Operational Research，2021，290（2）：405-421.

［7］Dai Hanjun，Khalil E B，Zhang Yuyu，et al.Learning combinatorial optimization algorithms over graphs［C］//Proc of the 31st Internatio-nal Conference on Neural Information Processing Systems.Red Hook，NY：Curran Associates Inc.，2017：6351-6361.

［8］Kool W，Van Hoof H，Welling M.Attention，learn to solve routing problems?。跜］//Proc of International Conference on Learning Re-presentations.2018.

［9］Malazgirt G A，Unsal O S，Kestelman A C.TauRiel：targeting traveling salesman problem with a deep reinforcement learning inspired architecture［EB/OL］.（2019-05-14）.https：//arxiv.org/pdf/1905.05567.pdf.

［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/pdf/1911.04936.pdf.

［11］Cappart Q，Moisan T，Rousseau L M，et al.Combining reinforcement learning and constraint programming for combinatorial optimization［EB/OL］.（2020-06-02）.https：//arxiv.org/pdf/2006.01610.pdf.

［12］Subramaniam V，Lee G K，Ramesh T，et al.Machine selection rules in a dynamic Job-Shop［J］.International Journal of Advanced Manufacturing Technology，2000，16（10）：902-908.

［13］Drori I，Kharkar A，Sickinger W R，et al.Learning to solve combinatorial optimization problems on real-world graphs in linear time［EB/OL］.（2020-06-06）.https：//arxiv.org/pdf/2006.03750.pdf.

［14］Zhang Rongkai，Prokhorchuk A，Dauwels J.Deep reinforcement lear-ning for traveling salesman problem with time windows and rejections［C］//Proc of International Joint Conference on Neural Networks.Piscataway，NJ：IEEE Press，2020.

［15］Hu Yujiao，Yao Yuan，Lee W S.A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs［J］.Knowledge-Based Systems，2020，204（9）：106244.

［16］Nazari M，Oroojlooy A，Snyder L，et al.Reinforcement learning for solving the vehicle routing problem［EB/OL］.（2018-05-21）.https：//arxiv.org/pdf/1802.04240.pdf.

［17］Chen Xinyun，Tian Yuandong.Learning to perform local rewriting for combinatorial optimization［EB/OL］.（2019-10-30）.https：//arxiv.org/pdf/1810.00337.pdf.

［18］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，2021，22（11）：7208-7218.

［19］Lu Hao，Zhang Xingwen，Yang Shuang.A learning-based iterative method for solving vehicle routing problems［C］//Proc of International Conference on Learning Representations.2019.

［20］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/pdf/2002.08539.pdf.

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

［22］Zhang Ke，He Fang，Zhang Zhengchao，et al.Multi-vehicle routing problems with soft time windows：a multi-agent reinforcement learning approach［J］.Transportation Research Part C：Emerging Technologies，2020，121（12）：102861.

［23］王萬良，陳浩立，李國慶，等.基于深度強化學習的多配送中心車輛路徑規劃［J］.控制與決策，2022，37（8）：2101-2109.（Wang Wanliang，Chen Haoli，Li Guoqing，et al.Deep reinforcement learning for multi-depot vehicle routing problem［J］.Control and Decision，2022，37（8）：2101-2109.）

［24］Vinyals O，Fortunato M，Jaitly N.Pointer networks［EB/OL］.（2017-01-02）.https：//arxiv.org/pdf/1506.03134.pdf.

［25］Bello I，Pham H，Le Q V，et al.Neural combinatorial optimization with reinforcement learning［EB/OL］.（2017-01-12）.https：//arxiv.org/pdf/1611.09940.pdf.

［26］Li Zhuwen，Chen Qifeng，Koltun V.Combinatorial optimization with graph convolutional networks and guided tree search［C］//Proc of the 32nd International Conference on Neural Information Processing Systems.2018：537-546.

［27］Kipf T N，Welling M.Semi-supervised classification with graph convolutional networks［EB/OL］.（2017-02-22）.https：//arxiv.org/pdf/1609.02907.pdf.

［28］Mnih V，Kavukcuoglu K，Silver D，et al.Playing atari with deep reinforcement learning［EB/OL］.（2013-12-19）.https：//arxiv.org/pdf/1312.5602.pdf.

［29］Dai Hanjun，Dai Bo，Song Le.Discriminative embeddings of latent va-riable models for structured data［C］//Proc of the 33rd International Conference on Machine Learning.2016：2702-2711.

［30］Vaswani A，Shazeer N，Parmar N，et al.Attention is all you need［EB/OL］.（2017-12-06）.https：//arxiv.org/pdf/1706.03762.pdf.

［31］Nowak A，Villar S，Bandeira A S，et al.A note on learning algorithms for quadratic assignment with graph neural networks［EB/OL］.（2017-12-06）.https：//arxiv.org/pdf/1706.07450v1.pdf.

［32］Ioffe S，Szegedy C.Batch normalization：accelerating deep network training by reducing internal covariate shift［C］//Proc of International Conference on International Conference on Machine Learning.2015：448-456.

［33］Velickovic P，Cucurull G，Casanova A，et al.Graph attention networks［C］//Proc of International Conference on Learning Representations.2018.

［34］Van H H，Guez A，Silver D.Deep reinforcement learning with double Q-learning［C］//Proc of the 30th AAAI Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，2016：2094-2100.

［35］Cordeau J F，Gendreau M，Laporte G.A tabu search heuristic for perio-dic and multi-depot vehicle routing problems［J］.Networks，1997，30（2）：105-119.

［36］Cordeau J F，Maischberger M.A parallel iterated tabu search heuristic for vehicle routing problems［J］.Computers amp; Operations Research，2012，39（9）：2033-2050.

［37］Kingma D P，Ba J.Adam：a method for stochastic optimization［EB/OL］.（2017-01-30）.https：//arxiv.org/pdf/1412.6980.pdf.

［38］Stodola P.Using metaheuristics on the multi-depot vehicle routing problem with modified optimization criterion［J］.Algorithms，2018，11（5）：74.

收稿日期：2022-03-07；修回日期：2022-04-29基金項目：浙江省高校重大人文社科攻關計劃資助項目（2018QN060）

作者簡介：雷坤（1998-），男，四川南充人，碩士，主要研究方向為深度強化學習、運籌優化；郭鵬（1988-），男，四川南充人，副教授，碩導，博士，主要研究方向為生產調度、智能制造、運作管理、智慧物流、深度強化學習等；王祺欣（1999-），男，四川南充人，碩士研究生，主要研究方向為深度強化學習、路徑優化；趙文超（1996-），男，重慶巫溪人，碩士，主要研究方向為生產調度；唐連生（1974-），男（滿族）（通信作者），遼寧蓋州人，教授，副院長，博士，主要研究方向為數字物流與智能技術、物流產業經濟、物流系統仿真、港口物流等（lianshengtang_nb@163.com）.