牛鵬飛，王曉峰，2，蘆 磊，張九龍

1.北方民族大學(xué)計算機科學(xué)與工程學(xué)院，銀川 750021

2.北方民族大學(xué)圖像圖形智能處理國家民委重點實驗室，銀川 750021

隨著經(jīng)濟社會快速發(fā)展及交通基礎(chǔ)設(shè)施的不斷完善，城市物流業(yè)是當(dāng)今社會關(guān)注的一個重要話題。2020年全國快遞業(yè)務(wù)量突破750億件，隨著構(gòu)建新發(fā)展格局的加快，未來我國快遞業(yè)務(wù)量仍會保持較快的增長。物流業(yè)的快速發(fā)展使得對超大型物流系統(tǒng)的快速調(diào)度提出了更高的要求。車輛路徑問題（vehicle routing problem，VRP）是在車輛數(shù)一定的條件下，盡量縮短車輛行駛距離，找到一組總成本最小的路線。同時，根據(jù)優(yōu)化目標不同，可以加入不同約束從而滿足不同種類問題的實際需求。

車輛路徑問題作為一個眾所周知的組合優(yōu)化問題，最早由Dantzig和Ramser[1]于1959年作為卡車調(diào)度問題提出的，并被Lenstra 和Kan[2]證明是NP-難問題。經(jīng)典的車輛路徑問題被定義為：有一個倉庫（depot）節(jié)點和若干個客戶（customers）節(jié)點，已知各個節(jié)點在二維空間上的位置和客戶的需求，在滿足約束條件下，使得車輛從倉庫節(jié)點出發(fā)訪問客戶節(jié)點，滿足客戶需求，最后返回倉庫。在不考慮負載的情況下，VRP等價于旅行商問題，應(yīng)用到現(xiàn)實生活中，研究較多的是有容量約束的車輛路徑問題（capacitated vehicle routing problem，CVRP）[3]。當(dāng)客戶的需求不定時，產(chǎn)生了隨機車輛路徑問題（stochastic vehicle routing problem，SVRP）[4]；當(dāng)客戶對需求提出時間要求時，產(chǎn)生了帶時間窗的車輛路徑問題（capacitated vehicle routing problem with time windows，CVRPW）[5]；針對客戶當(dāng)日要求交付的需求，產(chǎn)生了當(dāng)日交付的車輛路徑問題（same-day delivery problem with vehicle routing problems，SDDVRP）[6]。關(guān)于VRP的詳細描述見文獻[7]。

多年來大量國內(nèi)外學(xué)者致力于VRP 的研究，目前求解VRP的主要方法分為常規(guī)算法和基于強化學(xué)習(xí)的算法，其中常規(guī)算法包括精確算法、啟發(fā)式算法等?；趶娀瘜W(xué)習(xí)的算法主要包括基于馬爾科夫決策過程的強化學(xué)習(xí)和近年來方興未艾的深度強化學(xué)習(xí)。

本文將首先簡略概述基于常規(guī)算法求解VRP的各類算法，再對基于強化學(xué)習(xí)求解VRP 的各類模型進行詳細的介紹。

1 基于常規(guī)方法求解VRP技術(shù)

目前求解VRP 的常規(guī)算法包括精確算法、啟發(fā)式算法和元啟發(fā)式算法。

（1）精確算法主要包括線性規(guī)劃法[8]、分支限界法[9]等。這類算法適用于VRP規(guī)模較小、結(jié)構(gòu)簡單的情況，當(dāng)VRP 中有較多約束條件時，精確算法無法在有效時間內(nèi)得到問題的最優(yōu)解。

（2）啟發(fā)式算法主要包括節(jié)約法[10]、線性節(jié)約法[11]和插入檢測法[12]等。這類算法適用于規(guī)模較大的VRP，面對CVRP、CVRPW 等這些有較多約束條件的VRP 變種問題時，該類算法仍較為快速求解，具有求解效率高、占用內(nèi)存少的優(yōu)勢，因為該類算法改進目標一直是求解速度，因而問題規(guī)模增大時無法得到最優(yōu)解。

（3）元啟發(fā)式算法主要包括模擬退火算法[13]、禁忌搜索算法[14]、基于群思想的算法[15-18]等。這類算法具有求解速度快、效率高的特點。但這類算法在求解VRP時容易陷入局部最優(yōu)而無法得到全局最優(yōu)解，以及不容易收斂等問題。

表1 對上述求解VRP 的各類常規(guī)算法的缺點進行了對比。

表1 求解車輛路徑問題的常規(guī)方法優(yōu)缺點對比Table.1 Comparison of advantages and disadvantages of conventional approaches applied to VRP

2 強化學(xué)習(xí)概述

2.1 強化學(xué)習(xí)基礎(chǔ)

強化學(xué)習(xí)（reinforce learning，RL）是人工智能的一個重要分支，它不需要監(jiān)督信號來進行學(xué)習(xí)，而是依賴個體（agent）在環(huán)境（environment）中的反饋回報信號，依據(jù)反饋回報信號對個體的狀態(tài)和行動進行更正，使得個體逐步實現(xiàn)獎勵（Reward）的最大化，從而使得強化學(xué)習(xí)具有較強的自主學(xué)習(xí)能力。強化學(xué)習(xí)的描述如圖1所示。

圖1 強化學(xué)習(xí)示意圖Fig.1 Schematic diagram of reinforce learning

2.2 強化學(xué)習(xí)算法分類

對強化學(xué)習(xí)算法的分類可以根據(jù)有無模型分為基于模型（model-based）和無模型（model-free）的學(xué)習(xí)算法。在求解VRP中常見的基于模型的學(xué)習(xí)方法有動態(tài)規(guī)劃法；無模型的學(xué)習(xí)算法主要有基于價值的時序差分算法[18]、Q-learning 算法[19]、DQN 算法[20]等；基于策略的REINFORC算法[21]，價值和策略相結(jié)合的Actor-Critic算法[22]、Advantage Actor-Critic 算法等。如圖2 總結(jié)了一些已經(jīng)應(yīng)用到VRP求解中的經(jīng)典強化學(xué)習(xí)算法。

圖2 強化學(xué)習(xí)算法分類圖Fig.2 Classification diagram of reinforcement learning algorithm

3 基于模型的算法

在強化學(xué)習(xí)中“模型”指環(huán)境，基于模型的強化學(xué)習(xí)算法意為通過預(yù)先給定或通過學(xué)習(xí)的方式得到MDP模型。最典型的給定環(huán)境模型方法是打敗圍棋冠軍柯潔的阿爾法狗算法，通過學(xué)習(xí)的環(huán)境模型方法有world models 算法[23]。在VRP 求解中運用最多的基于模型的強化學(xué)習(xí)算法為動態(tài)規(guī)劃算法，及由動態(tài)規(guī)劃算法衍生出來的近似動態(tài)規(guī)劃算法和深度神經(jīng)網(wǎng)絡(luò)動態(tài)規(guī)劃算法?；谀Ｐ偷乃惴ㄍㄟ^MDP模型預(yù)測以后可能的狀態(tài)S和動作A，從而對個體行動提供指導(dǎo)，但在現(xiàn)實生活中環(huán)境模型可能很復(fù)雜以至于難以建模。

3.1 動態(tài)規(guī)劃算法

動態(tài)規(guī)劃算法是由美國數(shù)學(xué)家Bellman在研究多階段決策過程的優(yōu)化問題時提出的，“動態(tài)規(guī)劃”一詞中“動態(tài)”意為問題是可以通過一個個子問題去求解，“規(guī)劃”意為優(yōu)化策略。在給定一個用馬爾科夫決策過程描述的完備環(huán)境模型下，其可以計算最優(yōu)的模型。在強化學(xué)習(xí)中，動態(tài)規(guī)劃算法的目的是使用價值函數(shù)求解最優(yōu)策略，常規(guī)的動態(tài)規(guī)劃算法因“維數(shù)災(zāi)難”無法有效的求解強化學(xué)習(xí)問題，但后續(xù)其他的方法都是對動態(tài)規(guī)劃算法的改進和近似。運用動態(tài)規(guī)劃算法求解強化學(xué)習(xí)問題就是求解給定策略π時對應(yīng)的價值V*(S) 。價值V*(S)表示為：

公式表示k+1 輪的價值Vk+1(s)可由前k輪的Vk(S)出來，策略π(a|s)為給定狀態(tài)s時選擇動作a的概率，Ras為給定狀態(tài)s時選擇動作a的獎勵，γ為折扣率，為下一步狀態(tài)的概率乘以價值函數(shù)之和。

3.1.1 基于近似動態(tài)規(guī)劃的方法

Secomandi 等人[24]將首次神經(jīng)網(wǎng)絡(luò)近似動態(tài)規(guī)劃（network approximate dynamic programming，NDP）方法應(yīng)用到求解帶有隨機需求的VRP 中，NDP 是在動態(tài)規(guī)劃中使用神經(jīng)網(wǎng)絡(luò)對策略進行近似的新模型，實驗結(jié)果表明在有隨機需求的VRP中，基于rollot策略的NDP算法的性能要優(yōu)于近似策略迭代的NDP 算法。Tatarakis和Minis[25]對隨機需求下有倉庫補貨的單車輛路徑問題（stochastic vehicle routing with depot returns problem，SVRDRP）進行了研究，通過對交付產(chǎn)品的劃分，提出了一種近似動態(tài)規(guī)劃算法從而在合理的時間內(nèi)可得到最優(yōu)策略。

針對運輸和物流中出現(xiàn)的隨機優(yōu)化問題，Powell等人[26]在2012年提出了一個完整的研究框架，其中對近似動態(tài)規(guī)劃（ADP）算法在動態(tài)VRP的應(yīng)用做了細致的說明。?imen和Soysal[27]將VRP的優(yōu)化目標從成本最小化更改為排放最小化，從而給出了綠色帶時間窗有容量約束的隨機車輛路徑問題（green stochastic time-dependent capacitated vehicle routing problem，GSTDCVRP）的MDP模型和基于近似動態(tài)規(guī)劃的啟發(fā)式算法。

Ulmer等人[28]利用近似動態(tài)規(guī)劃的方法對價值函數(shù)進行近似，從而提出了有求解隨機服務(wù)請求的車輛路徑問題（vehicle routing problem with stochastic service requests，VRPSSR）的ATB算法。為降低VRP中因客戶的隨機需求帶來的高額計算，Ulmer 等人[29]針對隨機服務(wù)請求的單車輛路徑問題（single-vehicle routing problem with stochastic service requests，SVRPSSR），將客戶請求服務(wù)的時間以及客戶自身的空間位置納入近似動態(tài)規(guī)劃中，從而生成動態(tài)的路線策略。

為降低由交通擁堵引起的成本，Kok 等人[30]針對CVRPW，在近似動態(tài)規(guī)劃算法中加入了避免交通擁堵的策略，結(jié)果表明該方法能夠有效降低通勤中擁堵時長。Secomandi等人[31]針對只有一輛車的隨機需求車輛路徑問題（SDVRP），通過有限階段的MDP進行建模，使用部分再優(yōu)化（partial reoptimization）的方法對SDVRP進行研究，并通過PH、SH兩種啟發(fā)式算法選擇MDP的狀態(tài)子集，以此來計算最優(yōu)策略。Goodson 等人[32]提出了基于rollot 策略的近似動態(tài)規(guī)劃框架，并將該框架應(yīng)用于求解具有隨機需求和持續(xù)時間限制的多車輛路徑問題（vehicle routing problem with stochastic demand and duration limits，VRPSDL）。

3.1.2 基于深度動態(tài)規(guī)劃的方法

Kool 等人[33]提出了結(jié)合學(xué)習(xí)神經(jīng)啟發(fā)式和動態(tài)規(guī)劃的深度策略動態(tài)規(guī)劃對VRP 進行求解，模型根據(jù)圖神經(jīng)網(wǎng)絡(luò)（graph neural network，GNN）得到的每個客戶頂點特征向量，通過注意力機制計算每個客戶頂點被選中的概率，并將這個概率作為動態(tài)規(guī)劃算法對部分解進行選擇的策略，最后根據(jù)此策略構(gòu)造最優(yōu)解。

3.1.3 基于動態(tài)規(guī)劃的方法總結(jié)

常規(guī)方法通常只能求解靜態(tài)確定性問題，難以求解帶有動態(tài)和隨機信息的問題。動態(tài)規(guī)劃算法可有效求解靜態(tài)車輛路徑問題和動態(tài)車輛路徑問題，具有求解范圍較廣的優(yōu)勢。求解車輛路徑問題時，需首先建立MDP模型，設(shè)計算法求解該模型，并用rollout策略在啟發(fā)式算法基礎(chǔ)上得到最優(yōu)值函數(shù)，但動態(tài)規(guī)劃算法無法解決客戶節(jié)點規(guī)模大的車輛路徑問題。因此，學(xué)者們設(shè)計出近似動態(tài)規(guī)劃算法，利用神經(jīng)網(wǎng)絡(luò)的泛化能力，通過價值函數(shù)近似或策略函數(shù)近似得到獎勵函數(shù)，從而不用直接求解貝爾曼方程，解決了動態(tài)規(guī)劃算法帶來的“維數(shù)災(zāi)難”問題。學(xué)者們的改進方向主要是近似動態(tài)規(guī)劃算法中神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)，其主要區(qū)別是針對不同車輛路徑問題中的各類相關(guān)信息進行編碼作為神經(jīng)網(wǎng)絡(luò)的輸入信息，輸入的信息越豐富，獎勵函數(shù)的近似精度就越高，進而近似動態(tài)規(guī)劃算法的優(yōu)化效果越好。其次是對rollout策略的改進，以減少模型的計算成本和計算量。

相較于傳統(tǒng)運籌學(xué)有建模不準確的問題，以近似動態(tài)規(guī)劃算法為代表的基于模型的強化學(xué)習(xí)算法，可以通過智能體與環(huán)境不斷交互學(xué)習(xí)到最優(yōu)策略。在動態(tài)車輛路徑問題中動態(tài)規(guī)劃算法可以在于環(huán)境交互的過程中不斷加入獲取的隨機信息?；谝陨蟽?yōu)點使有模型強化學(xué)習(xí)算法適合求解具有動態(tài)結(jié)構(gòu)和隨機信息的車輛路徑問題。

3.1.4 動態(tài)規(guī)劃算法局限性分析

動態(tài)規(guī)劃算法在車輛路徑問題等領(lǐng)域中應(yīng)用較廣。但也存在許多問題，比如維數(shù)災(zāi)難、系統(tǒng)不可知、實時求解效率低、近似動態(tài)規(guī)劃算法雖能有效避免上述問題但也因采用神經(jīng)網(wǎng)絡(luò)，其魯棒性較差。分析原因如下：

（1）維數(shù)災(zāi)難

現(xiàn)實生活中的車輛路徑問題規(guī)模較大，以至于通過MDP 建模以后動作空間和狀態(tài)空間過大，導(dǎo)致動態(tài)規(guī)劃算法失效。因而動態(tài)規(guī)劃算法在求解大規(guī)模車輛路徑時性能較差。

（2）系統(tǒng)不可知

動態(tài)規(guī)劃算法可求解靜態(tài)的車輛路徑問題和動態(tài)的車輛路徑問題但需對問題先建模，但實際場景中的車輛路徑問題因系統(tǒng)的狀態(tài)轉(zhuǎn)移函數(shù)未知，從而無法對問題進行建模，或?qū)栴}進行過理想化處理，使得動態(tài)規(guī)劃算法應(yīng)用受限。

（3）實時求解效率低

當(dāng)下車輛路徑問題求解的實時性要求不斷提高，即需要在較短的時間內(nèi)給出問題的解，動態(tài)規(guī)劃算法雖能給出問題的最優(yōu)解，但耗費的時間較長且求解的效率較低。通過神經(jīng)網(wǎng)絡(luò)計算的近似動態(tài)規(guī)劃算法雖能比動態(tài)規(guī)劃算法求解算法快，但因當(dāng)前計算機的性能，算法實時求解能力仍有待提高。

（4）魯棒性差

目前改進的動態(tài)規(guī)劃算法均是采用神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，且使用自舉采樣的方式獲取數(shù)據(jù)，數(shù)據(jù)的關(guān)聯(lián)性較高，算法的魯棒性較差，且算法的抗擾動能力較弱。使得近似動態(tài)算法在實際生活中的車輛路徑問題應(yīng)用有限。

3.1.5 基于動態(tài)規(guī)劃求解VRP分析對比

表2 將上述基于動態(tài)規(guī)劃求解VRP 的各類模型的訓(xùn)練方法、求解問題、以及優(yōu)化效果進行了對比。

表2 基于動態(tài)規(guī)劃求解車輛路徑問題的方法對比Table 2 Comparison of approaches of dynamic programming applied to VRP

4 無模型的算法

無模型的強化學(xué)習(xí)算法是指MDP模型中的環(huán)境參數(shù)未知，即在給定狀態(tài)條件下個體采取動作以后，未來的狀態(tài)和獎勵值未知。因此，個體不對問題進行建模，而是先和環(huán)境進行交互，在不斷試錯中尋找最優(yōu)策略。無模型的強化學(xué)習(xí)算法主要分為基于值函數(shù)進行優(yōu)化的算法、基于策略進行優(yōu)化的算法、值函數(shù)和策略結(jié)合進行優(yōu)化的算法。

4.1 基于值函數(shù)的算法

基于值函數(shù)的強化學(xué)習(xí)算法通過對值函數(shù)進行優(yōu)化從而得到最優(yōu)策略。在VRP 中，值函數(shù)是對路徑策略π優(yōu)劣的評估，值函數(shù)分為狀態(tài)價值函數(shù)V*(s)和狀態(tài)-動作價值函數(shù)q*(s,a)，V*(s)表示為：

q*(s,a)表示為：

在求解VRP 中，基于值函數(shù)的強化學(xué)習(xí)算法主要有時序差分算法、Q-learning 算法、DQN 算法、Dueling DQN算法。

4.1.1 時序差分算法

時序差分算法由Wang 等人[14]提出，是強化學(xué)習(xí)的核心算法之一，它結(jié)合了動態(tài)規(guī)劃算法和蒙特卡洛方法的原理，是通過部分狀態(tài)序列來求解問題的強化學(xué)習(xí)算法。在時序差分算法中，價值函數(shù)的更新是通過兩個連續(xù)的狀態(tài)和其的獎勵值的差來實現(xiàn)的。最基本的時序差分算法的價值函數(shù)更新公式為：

其中α為學(xué)習(xí)率，Rt+1+γV(St+1)-V(St)為時序差分誤差，因此使用這種更新方法的時序差分也被稱為單步時序差分。

針對帶時間窗的動態(tài)車輛路徑問題（CDVRPTW），Joe 和Lau[35]提出了DRLSA 模型，通過基于神經(jīng)網(wǎng)絡(luò)的時序差分算法和經(jīng)驗放回策略去近似價值函數(shù)，然后運用模擬退火算法生成路徑。實驗表明，DRLSA 模型在有48 個客戶節(jié)點的CDVRPTW 上優(yōu)化效果超越了經(jīng)典的基于值函數(shù)近似算法和MSA 算法。該方法解決了當(dāng)動態(tài)請求普遍存在時，該如何給出有效的路徑規(guī)劃。

時序差分算法作為經(jīng)典的無模型算法，對模型環(huán)境要求低，無需訓(xùn)練結(jié)束即可獲得各類參數(shù)的增量。在規(guī)模較小的車輛路徑問題中優(yōu)化效果較好，但收斂速度較慢，作為表格型傳統(tǒng)強化學(xué)習(xí)算法不足以解決復(fù)雜的車輛路徑問題。

4.1.2 Q-learning算法

Q-learning算法是Watkins等人[19]提出的，該算法求解強化學(xué)習(xí)問題時，使用兩個控制策略，一個策略用于更新動作，另一個用于更新價值函數(shù)，核心思想為離軌策略下的時序差分控制。Q-learning算法在強化學(xué)習(xí)的控制問題中應(yīng)用最為廣泛。該算法價值函數(shù)的更新公式為：

其中α為學(xué)習(xí)率，Rt+1為t+1 步的獎勵，α為狀態(tài)St+1能執(zhí)行的動作。

Zhang等人[34]提出來一種基于查找表的值函數(shù)近似VFA模型求解帶有隨機需求的VRP。具體來說，將當(dāng)前狀態(tài)和決策的重要信息存儲在一個Q-表中，并用改進的Q-learning算法進行學(xué)習(xí)。

針對多任務(wù)的車輛路徑問題，Bouhamed 等人[36]提出了一種基于Q-learning 算法的多任務(wù)代理路由調(diào)度框架。該模型首先將與任務(wù)相關(guān)的時間段定義為一個集合，并據(jù)此設(shè)計出了相應(yīng)的Q-表，再通過Q-learning算法對Q-表進行更新從而對問題進行求解，實驗結(jié)果表明，該模型在復(fù)雜的VRP 上優(yōu)化效果接近目前最優(yōu)方法。

Q-learning 算法因優(yōu)先執(zhí)行動作，主動探索能力強?？捎行У那蠼鈳в须S機需求信息的車輛路徑問題。但因是把狀態(tài)和不同的動作存儲在Q 表中并一直更新，易使算法陷入局部最優(yōu)，降低算法的學(xué)習(xí)效率，搜索耗時較長。更新Q表時Q表一直發(fā)生動態(tài)變化，所以更新的效果不穩(wěn)定。

4.1.3 DQN算法

DQN算法是Mnih等人[20]提出的，該模型將Q-learning算法與深度神經(jīng)網(wǎng)絡(luò)相結(jié)合起來，通常使用DNN 或者CNN來構(gòu)建模型，使用Q-learning算法訓(xùn)練。DQN算法對Q-learning 的改進主要有以下兩個方面：（1）DQN 算法利用神經(jīng)網(wǎng)絡(luò)逼近值函數(shù)。（2）DQN算法利用了經(jīng)驗回放訓(xùn)練強化學(xué)習(xí)的學(xué)習(xí)過程。DQN算法的損失函數(shù)如下：

目前，DQN 算法在VRP 中的應(yīng)用是一個新興的研究熱點，國內(nèi)外的主要研究成果有：

針對帶有多個倉庫（depots）的車輛路徑問題（MDVRP）和動態(tài)車輛路徑問題，Bdeir 等人[37]提出了基于DQN 的RP-DQN 模型，該模型框架如圖3 所示。RP-DQN 模型中為有效降低問題的計算復(fù)雜性，編碼器不僅對靜態(tài)的客戶節(jié)點位置、客戶需求進行編碼，并對問題中的動態(tài)特征信息進行編碼，使用Q-learning 算法對模型進行優(yōu)化。在客戶數(shù)量為20、50、100 的CVRP 上優(yōu)化效果均超過了Kool 等人[38]的方法。首次將深度Q 網(wǎng)絡(luò)運用到MDVRP 的求解過程中，在客戶數(shù)量為20、50、100 的MDVRP上RP-DQN模型的優(yōu)化效果也好于Kool等人[38]的方法?？傮w來說RP-DQN 模型的泛化能力要高于Kool等人[38]提出的AM模型。

圖3 RP-DQN模型示例Fig.3 Example of RP-DQN model

針對客戶當(dāng)日要求交付（same-day delivery）的需求，Chen 等人[39]提出了車輛和無人機的當(dāng)天交付問題（same-day delivery problem with vehicles and drones，SDDPVD），建模過程中采用和Powell[26]相同的模型架構(gòu)，并使用Ulmer等[40]提出的路由策略來模擬路線的更新和演變，首先將SDDPVD 建模為MDP 模型，為了使決策快速有效，將動作空間和狀態(tài)空間進行簡化，通過設(shè)計DQN算法去近似每個特征向量的值。

4.1.4 DQN算法總結(jié)

DQN算法作為具有里程碑意義的深度強化學(xué)習(xí)算法，不同于傳統(tǒng)強化學(xué)習(xí)算法中值函數(shù)線性近似方法，使用多層深度神經(jīng)網(wǎng)絡(luò)近似代替Q-learning 算法中的Q-表，從而可以將高維輸入值映射到Q-空間。DQN 算法通過一個經(jīng)驗池來存儲以前的數(shù)據(jù)，每次更新參數(shù)的時候從經(jīng)驗池中抽取一部分的數(shù)據(jù)來更新，打破信息間存在的關(guān)聯(lián)，從而可有效求解有狀態(tài)、動作高維復(fù)雜，數(shù)據(jù)間彼此有關(guān)聯(lián)的車輛路徑問題。

基于DQN算法求解車輛路徑問題的各類模型主要是通過對DQN算法的狀態(tài)、動作、獎勵的表示做出相應(yīng)的修改，對價值函數(shù)進行映射，通過對價值函數(shù)做出評價，以此改進初始策略。但DQN 算法在求解車輛路徑問題仍存在很多不足，比如因需對Q-網(wǎng)絡(luò)進行最大化操作引起過估計問題，DQN 算法只能求解單車輛的車輛路徑問題。

4.1.5 DQN算法局限性分析

DQN 算法因運用經(jīng)驗放回機制和設(shè)定一個固定Q目標值神經(jīng)網(wǎng)絡(luò)，具有較好的收斂性和兼容性。但在車輛路徑問題求解中也存在較多問題，例如過擬合問題、樣本利用率低、得分不穩(wěn)定。具體以上問題原因為：

（1）過擬合問題

DQN 算法在訓(xùn)練智能體過程中，會采用Q 網(wǎng)絡(luò)最大化的操作，從而出現(xiàn)過度適應(yīng)當(dāng)前環(huán)境的情況，使算法出現(xiàn)過擬合現(xiàn)象。

（2）樣本利用率低

DQN 算法和環(huán)境交互的過程中，樣本之間有很強的關(guān)聯(lián)性，降低了深度神經(jīng)網(wǎng)絡(luò)的更新效率，算法需要很長的時間才能達到合適的得分標準，使得DQN 算法在車輛路徑問題中的數(shù)據(jù)樣本利用率較低。

（3）得分不穩(wěn)定

使用DQN算法求解車輛路徑問題時，Q-learning學(xué)習(xí)過程中會對Q值過高估計，容易產(chǎn)生較高誤差，導(dǎo)致算法穩(wěn)定性較差，得分性能不穩(wěn)定。

4.1.6 Dueling DQN算法

針對無模型的強化學(xué)習(xí)問題，Wang 等人[41]提出了一種新的DQN 模型：Dueling DQN（DDQN）。不同于DQN 算法，DDQN 算法把在卷積層得到的特征分為狀態(tài)值和動作優(yōu)勢函數(shù)兩部分：

式中，Qπ(s,a)為狀態(tài)s下選擇動作a的獎勵值，狀態(tài)值Vπ(s)是對狀態(tài)s的評價，動作優(yōu)勢函數(shù)Aπ(s,a)是對狀態(tài)s下各個動作優(yōu)劣的評價指標。

Zhang等人[42]為有效解決車輛路徑問題中的供需匹配難題，提出了QRewriter-DDQN 模型。將可用車輛提前調(diào)度給需求級別高的客戶。QRewriter-DDQN模型由Qrewriter 模塊和-DDQN 模塊構(gòu)成，DDQN 模塊將車輛和客戶之間的KL分布作為激勵函數(shù)，從而得到供需之間的動態(tài)變化。之后，運用Qrewriter 模塊用來改進DDQN生成的調(diào)度策略。

4.1.7 Dueling DQN算法總結(jié)

Dueling DQN 算法是通過改進深度神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)來提高DQN算法性能。該算法采用卷積神經(jīng)網(wǎng)絡(luò)處理車輛路徑問題中的初始信息，并使用兩個全連接神經(jīng)網(wǎng)絡(luò)把Q值劃分為狀態(tài)值和動作優(yōu)勢函數(shù)兩部分，通過這種改變可以有效地區(qū)分出獎勵值的來源。因為優(yōu)勢函數(shù)存在，Dueling DQN算法可以讓一個狀態(tài)下的所有動作同時更新，加快了算法收斂速度。尤其是在有大規(guī)模動作空間的車輛路徑問題中，相較于初始DQN 算法Dueling DQN算法能更加高效的學(xué)習(xí)價值函數(shù)。

4.2 基于策略的方法

以上基于值的算法是通過值函數(shù)近似方法對價值函數(shù)進行參數(shù)化比較，從而使個體選擇相應(yīng)動作。另一種常見的是基于策略的算法，直接對策略進行優(yōu)化，尋找最優(yōu)策略。常用于VRP的基于策略的算法有蒙特卡洛REINFORCE算法、Actor-Critic算法等。

基于策略的算法具有策略參數(shù)化簡單、收斂速度快的優(yōu)點，且適用于連續(xù)或者高維的動作空間。策略就是策略參數(shù)化，即πθ，參數(shù)化后的策略為一個概率密度函數(shù)θ。與策略相對應(yīng)，策略搜索分為隨機策略搜索和確定性策略搜索。策略搜索的目的就是找到最優(yōu)的參數(shù)θ，定義目標函數(shù)：

定義策略梯度公式為：

更新策略的參數(shù)：

4.2.1 蒙特卡洛REINFORCE方法

蒙特卡洛REINFORCE 方法是最簡單的策略梯度算法[43]，該算法使用價值函數(shù)V*(s)來近似代替策略梯度公式里面的Qπ(s,a)，首先輸入N個蒙特卡洛完整序列，用蒙特卡洛方法計算每個時間位置t的狀態(tài)價值Vt(s)，再按照以下公式對策略θ進行更新：

不斷執(zhí)行動作直到結(jié)束，在一個回合結(jié)束之后計算總反饋，然后根據(jù)總反饋更新參數(shù)。pθ(π|s)為每一步動作選擇概率的累乘，則lnpθ(π|s)則為每一步動作選擇概率對數(shù)的求和，?lnpθ(π|s)為梯度值，L(π)-b(s)為梯度下降的方向，b(s)為策略的平均表現(xiàn)。

自Vinyals等人[44]在2015年提出了指針網(wǎng)絡(luò)（Ptr-Net）模型求解旅行商問題后，在小規(guī)模的旅行商問題上，相較于傳統(tǒng)的啟發(fā)式搜索算法。該模型具有求解更快的特點，這是深度學(xué)習(xí)在組合優(yōu)化問題上的首次應(yīng)用，旅行商問題是VRP的一種特例，因此，研究人員開始將指針網(wǎng)絡(luò)模型應(yīng)用于VRP的求解。

Nazari等人[45]針對CVRP構(gòu)建Ptr-Net—REINFORCE模型，該模型是一個end-to-end的深度強化學(xué)習(xí)模型，通過Ptr-Net進行建模，在構(gòu)建指針網(wǎng)絡(luò)階段，Ptr-Net中的輸入為靜態(tài)值（客戶位置）與動態(tài)值（客戶需求），其模型結(jié)構(gòu)如圖4 所示。不同于Ptr-Net 在訓(xùn)練模型時采用監(jiān)督式方法，使用REINFORCE 算法對模型進行訓(xùn)練，分別在客戶數(shù)為10、20、50、100 的CVRP 數(shù)據(jù)集上進行了測試，取得了比經(jīng)典的啟發(fā)式搜索算法CW、SW更好的效果。Xin 等人[46]為解決深度強化學(xué)習(xí)算法在構(gòu)造解的過程中無法修改以前決策，提出基于REINFORCE算法的分步SW-Ptr-Net 模型和近似SW-AM 模型。該方法有效提升了Ptr-Net 模型和AM 模型[47]對CVRP 的優(yōu)化效果。

圖4 Ptr-Net-REINFORCE模型示例Fig.4 Example of Ptr-Net-REINFORCE model

（1）基于Ptr-Net的深度強化學(xué)習(xí)模型總結(jié)

Ptr-Net 模型使用編碼器對車輛路徑問題中的初始信息進行編碼得到特征向量，再通過解碼器對特征向量進行解碼，利用注意力機制計算每個客戶節(jié)點的選擇概率，從而構(gòu)造車輛路徑問題的解。所有運用Ptr-Net 模型構(gòu)造車輛路徑問題的構(gòu)造過程大致如下：

首先通過Embedding 層把每個客戶節(jié)點的地理位置和需求轉(zhuǎn)化為節(jié)點表征向量s，傳入循環(huán)神經(jīng)網(wǎng)絡(luò)中得到上下文信息和隱藏層信息。然后通過解碼器對上下文信息進行解碼，利用注意力機制按照隱藏層中的信息和上下文信息得到每個客戶節(jié)點的被選概率，每一步都選擇被選概率最大的客戶節(jié)點加入解中，逐步構(gòu)造車輛路徑問題的解。若使用監(jiān)督式方法訓(xùn)練模型，需要得到已有最優(yōu)解的車輛路徑問題訓(xùn)練集，車輛路徑問題是經(jīng)典的NP 難問題，因此得到實例的最優(yōu)解非常困難。且車輛路徑問題均可建模成MDP 模型，使用強化學(xué)習(xí)算法訓(xùn)練Ptr-Net 模型是非常合適的。由式（12）可知，REINFORCE 算法是以反向傳播作為參數(shù)更新的標準，智能體在探索解空間時，可以不斷提升初始解的質(zhì)量。因而，當(dāng)使用Ptr-Net 模型求解車輛路徑問題時，國內(nèi)外學(xué)者常采用REINFORCE算法對模型進行優(yōu)化。

Ptr-Net 模型這一新型深度神經(jīng)網(wǎng)絡(luò)模型，主要解決輸入時序與位置相關(guān)的離散個體組成輸出時序的問題，是求解具有時間序列特性的車輛路徑問題的主要深度學(xué)習(xí)模型。相較于循環(huán)神經(jīng)網(wǎng)絡(luò)處理具有自回歸問題，Ptr-Net 模型對輸入序列長度可變時，直接使用歸一化方式輸出各個客戶節(jié)點在當(dāng)前解碼位置的概率分布。但Ptr-Net 模型復(fù)雜度較高，且需要大量的采樣和局部搜索改善Ptr-Net 模型得到的初始解，使模型收斂較慢。

Kool 等人[38]首次將transformer 模型應(yīng)用到VRP 的求解中，和大多數(shù)seq2seq 模型一樣，transformer 的結(jié)構(gòu)也是由編碼器和解碼器組成。在編碼器中作者沒有使用transformer模型輸入時的positional encoding，從而使得節(jié)點嵌入不受輸入順序影響，但仍采用經(jīng)典transformer 模型中的多頭-attention 機制。在解碼器中作者為了提高計算效率并未采用transformer 模型解碼層的多頭-attention 機制，而是只使用一個自-attention 機制。采用加入rollout baseline的REINFORCE算法對模型進行訓(xùn)練，并在CVRP 和SDVRP 等問題的求解上取得了比基于指針網(wǎng)絡(luò)模型更好的效果，且與經(jīng)典的運籌學(xué)求解器LKH3、Gurobi相比求解效果相差無幾。

Falkner 等人[47]針對CVRPTW，提出了JAMPR 模型，該模型由多個編碼器和一個解碼器組成，編碼器采用了self-attention 計算方法，通過加入兩個新的編碼器產(chǎn)生上下文信息以及增強聯(lián)合行動空間，解碼器使用transform模型的多頭-attention機制。使用REINFORCE算法對JAMPR 模型進行訓(xùn)練，模型架構(gòu)如圖5 所示。在對CVRP-TW 的3 種變體（hard、partly-soft、soft）的實驗中，該模型的優(yōu)化效果要好于現(xiàn)有的元啟發(fā)式算法和基于attention機制的強化學(xué)習(xí)模型。

圖5 JAMPR模型示例Fig.5 Example of JAMPR model

Xin 等人[48]提出了一個多解碼器注意模型（multidecoder attention model，MDAM）來訓(xùn)練波束搜索（beam search）的策略，MDAM 由一個編碼器和多個解碼器組成，編碼器采用和transformer模型相同的多頭-attention機制，每個解碼器采用節(jié)點嵌入的方式來產(chǎn)生訪問每個有效節(jié)點的概率。使用REINFORCE 算法對JAMPR 模型進行訓(xùn)練。在對CVRP 和SDVRP 等問題的求解中，相較于所選基準算法該模型的優(yōu)化效果要更好。為有效地解決具有軟時間窗的多車輛路徑問題（multi-vehicle routing problem with soft time windows，MVRPSTW），Zhang 等人[49]提出了多智能體注意力模型（multi-agent attention model，MAAM），使用REINFORCE 算法對MAAM 模型進行訓(xùn)練。實驗結(jié)果表明，求解速度優(yōu)于Google OR-tools 求解器和傳統(tǒng)的啟發(fā)式算法。Xu 等人[50]以AM模型[38]為基礎(chǔ)構(gòu)建了具有多重關(guān)系的MRAM模型，更好地獲取車輛路徑問題的動態(tài)特征。

（2）基于transformer的深度強化學(xué)習(xí)模型總結(jié)

Ptr-Net 模型中因編碼器和解碼器使用循環(huán)神經(jīng)網(wǎng)絡(luò)因而存在不能捕獲問題的長程相關(guān)性，且模型訓(xùn)練消耗大量時間，因transformer 模型中的多頭attention 可以提取車輛路徑問題中更加深層次的特征，所以學(xué)者們借鑒transformer 模型提出了基于attention 機制提出各類新模型，此類深度強化學(xué)習(xí)模型僅通過attention機制對輸入輸出的全局依賴關(guān)系進行建模，這類模型可以捕獲客戶節(jié)點間的長程相關(guān)性且有較高的計算效率。但attention 機制需要極大的計算量和內(nèi)存開銷，所以這類模型的主要改進是通過改變編碼器和解碼器的個數(shù)以及編碼方式、解碼方式、注意力機制來實現(xiàn)的。因REINFORCE 算法具有自適應(yīng)性，可自行調(diào)節(jié)參數(shù)，基于transformer 的各類模型常使用REINFORCE 算法作為訓(xùn)練模型的算法，但因為REINFORCE 算法方差較大，訓(xùn)練結(jié)果不穩(wěn)定，研究人員引入帶有基線函數(shù)的REINFORCE算法，該訓(xùn)練算法加快了模型的收斂速度。

Peng等人[51]結(jié)合動態(tài)attention方法與REINFORCE方法設(shè)計了一種AM-D 模型來求解VRP，動態(tài)attention方法是基于動態(tài)編碼器-解碼器結(jié)構(gòu)來改進的，改進的關(guān)鍵是動態(tài)挖掘?qū)嵗慕Y(jié)構(gòu)特征，并在不同的構(gòu)造步驟中有效地挖掘隱藏的結(jié)構(gòu)信息，模型架構(gòu)如圖6 所示。實驗結(jié)果表明，在客戶數(shù)量為20、50、100 的CVRP 上優(yōu)化效果均超過了Kool等人[38]提出的AM方法，并明顯減小了最優(yōu)性差距。Lu等人[52]提出了基于迭代的learn to improve（L2I）框架，算法首先給出一個可行解，運用基于REINFORCE 方法的控制器選擇改進算子或基于規(guī)則的控制器選擇擾動算子迭代更新解，經(jīng)過一定迭代步驟后從所有訪問的解決方案中選擇最優(yōu)解。對于CVRP，該模型不僅在優(yōu)化效果上超過了Google ORtools、LKH3等專業(yè)運籌學(xué)求解器，還是第一個在CVRP上求解速度低于LKH3求解器的強化學(xué)習(xí)框架，模型架構(gòu)如圖6所示。

圖6 L2I 模型框架Fig.6 Framework of L2I model

Hottung和Tierney[53]提出神經(jīng)大鄰域搜索（NLNS）框架對CVRP、SDVRP等問題進行求解，運用基于attention機制的神經(jīng)網(wǎng)絡(luò)對LNS 中的毀壞算子和重建算子進行學(xué)習(xí)，并用REINFORCE 算法對NLNS 模型進行訓(xùn)練。實驗結(jié)果表明，在CVRP 實例上NLNS 模型與LKH3 性能相當(dāng)；在SDVRP 實例上，NLNS 能夠在擁有100 個客戶的實例上勝過目前最先進的方法。

（3）強化學(xué)習(xí)與局部搜索算法結(jié)合的模型總結(jié)

基于transformer 模型和Ptr-Net 模型求解車輛路徑問題雖然速度較快，但優(yōu)化效果仍不及專業(yè)運籌學(xué)求解器。在組合優(yōu)化問題求解中，局部搜索算法仍然是主流代表算法，局部搜索算法往往涉及到算法參數(shù)設(shè)置和問題配置，這些都需要算法設(shè)計者有高超的算法設(shè)計技巧才能保證啟發(fā)式算子的效果。學(xué)者們基于不同車輛路徑問題的特征和算法結(jié)構(gòu)得到合適的參數(shù)和策略，運用強化學(xué)習(xí)方法對局部搜索策略進行訓(xùn)練，擴大了局部搜索算法啟發(fā)式算子的搜索能力，以此來提高解的質(zhì)量。目前，求解車輛路徑問題的最優(yōu)算法就是基于強化學(xué)習(xí)的局部搜索算法。

4.2.2 REINFORCE算法局限性分析

隨著計算機計算能力不斷增加，REINFORCE 算法已成為深度神經(jīng)網(wǎng)絡(luò)模型解決車輛路徑問題最常用的訓(xùn)練方法之一。REINFORCE 算法相較于基于值函數(shù)的算法，可以表示隨機策略，當(dāng)策略不定時，可以輸出多個動作的概率分布。但是REINFORCE 算法也存在很多問題，比如數(shù)據(jù)利用率低、算法收斂速度慢、方差較大導(dǎo)致算法收斂性變差。分析存在以上的原因如下：

（1）數(shù)據(jù)利用率低

REINFORCE 算法是回合更新的算法，需要完成整個回合，才能更新狀態(tài)-動作對。這種更新方式使得整個軌跡的一系列動作被當(dāng)作整體，若軌跡的收益較低，即使包含一些好的動作，但下次被選的概率仍會下降，使得數(shù)據(jù)利用率低。

（2）算法收斂速度慢

對于REINFORCE算法，車輛路徑問題中的每個樣本只能被訓(xùn)練一遍，有些能具有高收益的樣本沒有被重復(fù)利用，這不僅浪費計算資源，還增加算法了的收斂時間，使得算法收斂速度慢。

（3）算法收斂性差

在車輛路徑問題中，REINFORCE 算法為控制訓(xùn)練個體的時間，不可能遍歷所有狀態(tài)，只能通過采樣得到大量軌跡，但這樣的做法會造成REINFORCE 算法與環(huán)境交互不充分，那些未被選中的動作有可能對應(yīng)著較高獎勵，因而產(chǎn)生較大方差，導(dǎo)致算法收斂速度變慢。所以經(jīng)常通過在算法中加入基線函數(shù)來避免高方差。

4.2.3 Actor-Critic算法

Actor-Critic 算法是一種基于值方法和基于策略方法相結(jié)合而產(chǎn)生的算法。該算法的架構(gòu)包括兩個部分：Actor 部分是基于策略方法的，通過生成動作并和環(huán)境交互，用來逼近策略模型πθ(s,a)；Critic部分是基于值方法的，判定動作的優(yōu)劣性，并且選擇下一個動作，用來逼近值函數(shù)Q(s,a)。Actor 與Critic 之間互補的訓(xùn)練方式相較于單獨的算法更加有效。策略梯度函數(shù)為：

Actor的策略網(wǎng)絡(luò)的更新公式為：

Critic的值函數(shù)網(wǎng)絡(luò)的更新公式為：

Zhao 等人[55]提出一種改進的Actor-Critic 算法對模型進行訓(xùn)練，首先通過路由模擬器生成大量VRP 實例用于訓(xùn)練和驗證，在Actor 網(wǎng)絡(luò)的編碼過程中將靜態(tài)特征和動態(tài)特征分別編碼，在基本attention機制[38]中，模型對輸入序列的順序很敏感。為了克服這個問題，采用了圖嵌入的方法，Critic 網(wǎng)絡(luò)由一個Simple 網(wǎng)絡(luò)和一個Actor網(wǎng)絡(luò)組成，為加快模型收斂速度，還借鑒了圖像字幕[56]中的Self Critic 思想，據(jù)此構(gòu)成了Adaptive Critic網(wǎng)絡(luò)，網(wǎng)絡(luò)架構(gòu)如圖7所示。新的Actor-Critic模型在客戶點數(shù)分別為20、50 和100 的3 個數(shù)據(jù)集上進行測試。實驗結(jié)果表明，該模型找到了更好的解決方案，同時實現(xiàn)了5到40倍的加速。還觀察到，與其他初始解決方案相比，將深度強化學(xué)習(xí)模型與各種局部搜索方法相結(jié)合，可以以更快的求解速度得到解。

圖7 Adaptive Critic 網(wǎng)絡(luò)示例Fig.7 Example of Adaptive Critic network

在日常生產(chǎn)生活中，一個客戶可能總是有他自己的送貨點，比如同城快遞服務(wù)[57]和拼車服務(wù)[58]，而不是像VRP那樣為所有客戶共享一個倉庫。所有這類VRP可描述為提貨和交貨問題（pickup and delivery problem，PDP）。Li 等人[56]提出了一種基于異構(gòu)attention 機制的編碼器-解碼器模型，其編碼層在多頭attention注意力方法中加入了異構(gòu)attention 方法以期更早得到優(yōu)先級較高的關(guān)系，采用Actor-Critic算法對該模型進行訓(xùn)練。在PDP 求解中該模型的優(yōu)化效果要好于傳統(tǒng)的啟發(fā)式算法。Gao 等人[57]提出了基于圖注意力網(wǎng)絡(luò)的模型用去求解VRP、CVRP。該模型的編碼器是由一個graph attention network 組成，模型首先對每個客戶位置進行編碼得到每個客戶頂點的邊緣嵌入和頂點嵌入，在通過attention機制計算出每個客戶被選擇的概率。解碼器采用和Ptr-Net一樣的架構(gòu)，為VLNS算法的破壞算子提供一個節(jié)點子集作為移除候選。依然采用Actor-Critic 算法對該模型進行訓(xùn)練。

當(dāng)VRP、CVRP、CVRPW 等問題的規(guī)模較大時（多于400 頂點），該模型優(yōu)于傳統(tǒng)啟發(fā)式算法和現(xiàn)有求解VRP的深度強化學(xué)習(xí)模型。

強化學(xué)習(xí)與圖神經(jīng)網(wǎng)絡(luò)結(jié)合的模型總結(jié)：車輛路徑問題是典型的具有圖結(jié)構(gòu)的組合優(yōu)化問題，因圖神經(jīng)網(wǎng)絡(luò)能夠有效求解具有圖結(jié)構(gòu)的問題，所以有學(xué)者把圖神經(jīng)網(wǎng)絡(luò)應(yīng)用到了車輛路徑問題的求解中，運用圖神經(jīng)網(wǎng)絡(luò)求解車輛路徑問題的構(gòu)造。

過程大致如下：將車輛路徑問題建模為圖G=(V,E)，其中V代表節(jié)點集合，E代表邊集合。圖神經(jīng)網(wǎng)絡(luò)根據(jù)用戶節(jié)點Vi本身的二維空間位置和需求、邊的特征，以及節(jié)點Vi鄰居節(jié)點的二維空間位置和需求對節(jié)點Vi特征向量進行更新，從而得到每個節(jié)點的特征向量。為加快模型收斂，研究人員通常把圖神經(jīng)網(wǎng)絡(luò)求得的用戶節(jié)點的特征向量加入transformer 模型和Ptr-Net 模型的編碼器中，在通過attention 機制計算出每個客戶被選擇的概率。因為Actor-Critic 算法融合了基于值的算法和基于策略的算法的優(yōu)點，即可解決連續(xù)動作空間問題，還能進行單步更新從而加快學(xué)習(xí)速度，所以在圖神經(jīng)網(wǎng)絡(luò)中常使用Actor-Critic 算法訓(xùn)練模型。

4.2.4 Actor-Critic算法局限性分析

Actor-Critic 算法是目前最為流行的強化學(xué)習(xí)算法之一，結(jié)合了基于值算法和基于策略算法的優(yōu)點，既能應(yīng)用于連續(xù)動作空間，有能進行單步更新。但仍然存在一些問題，比如學(xué)習(xí)效率低，收斂速度慢。分析存在以上問題的原因如下：

（1）學(xué)習(xí)效率低

Actor-Critic 算法中涉及到Actor 網(wǎng)絡(luò)和Critic 網(wǎng)絡(luò)兩部分，Actor網(wǎng)絡(luò)基于概率選擇動作等價于策略函數(shù)，Critic網(wǎng)絡(luò)等價于價值函數(shù)。Actor-Critic算法每次更新都會涉及到這兩個深度神經(jīng)網(wǎng)絡(luò)，而且每次都在連續(xù)狀態(tài)中更新參數(shù)，參數(shù)更新時有很強的相關(guān)性。導(dǎo)致算法學(xué)習(xí)效率低。

（2）收斂速度慢

Actor-Critic算法中Critic網(wǎng)絡(luò)收斂速度慢，若Critic網(wǎng)絡(luò)不收斂，那么它對Actor網(wǎng)絡(luò)的評估就不準確，導(dǎo)致Actor網(wǎng)絡(luò)難收斂，使得Actor-Critic算法收斂速度慢。

4.2.5 Advantage Actor-Critic算法

Advantage Actor-Critic（A2C）算法又稱同步優(yōu)勢Actor-Critic算法是Mnih等人2016年提出的。在Actor-Critic 算法中Critic 網(wǎng)絡(luò)輸入Q值來對策略梯度進行計算，但這種計算方式存在高方差的問題，從而可以引入Baseline 的方式減小梯度使得訓(xùn)練更加平穩(wěn)，通過這種改進就能得到A2C 算法。A2C 算法的策略梯度函數(shù)為：

A2C算法的優(yōu)勢函數(shù)為：

A2C 算法將Critic 網(wǎng)絡(luò)對Q值的估計改為對優(yōu)勢函數(shù)的估計，估算每個決策相較于平均值的優(yōu)勢。A2C算法的整體架構(gòu)與Actor-Critic算法類似，只是在其基礎(chǔ)上加入了并行計算的能力，即整個個體由一個全局網(wǎng)絡(luò)和多個并行的工作體（worker）組成，每個工作體都包括一個Actor-Critic網(wǎng)絡(luò)。

Vera和Abad[58]針對固定車隊規(guī)模的容量受限多車輛路徑問題（capacitated multi-vehicle routing problems，CMVRP），提出了基于Attention 機制的Seq2Seq模型，采用A2C 算法對模型進行訓(xùn)練，與經(jīng)典的啟發(fā)式算法SW 和CW 相比該模型生成的解具有更低的標準差。

A2C算法使用一個優(yōu)勢函數(shù)作為評價標準，這個優(yōu)勢函數(shù)用來評價當(dāng)前所選動作與所有動作平均值之間的差值，從而降低了AC 算法所產(chǎn)生的誤差。但運用A2C算法求解車輛路徑問題時，智能體在環(huán)境訓(xùn)練中的穩(wěn)定性較差。

4.3 基于動態(tài)規(guī)劃求解VRP分析對比

基于無模型強化學(xué)習(xí)方法求解VRP 的對比結(jié)果見表3。

表3 無模型方法求解車輛路徑問題對比Table 3 Comparison of approaches of model-free applied to VRP

5 強化學(xué)習(xí)算法總結(jié)分析

近年來，強化學(xué)習(xí)在車輛路徑問題求解中涌現(xiàn)了很多優(yōu)秀的算法，在應(yīng)用過程中這些算法有自己的優(yōu)勢，但也暴露出一些自身局限性，將上述內(nèi)容進行總結(jié)分析，如表4所示。

表4 強化學(xué)習(xí)總結(jié)Table 4 Summary in reinforcement learning

基于模型的強化學(xué)習(xí)算法求解車輛路徑問題時需先構(gòu)建MDP模型，智能體通過與環(huán)境的不斷交互，智能體對數(shù)據(jù)的利用率較高。為增強求解問題的實時性，使用rollout框架對初始策略進行迭代更新，逐步逼近最優(yōu)解。近似動態(tài)規(guī)劃中使用自舉采樣法訓(xùn)練神經(jīng)網(wǎng)絡(luò)，自舉采樣得到的數(shù)據(jù)不是獨立同分布的，這樣的采樣方式使模型穩(wěn)定性降低。

現(xiàn)在的使用深度強化學(xué)習(xí)模型解決車輛路徑問題時主要的創(chuàng)新點是對深度神經(jīng)網(wǎng)絡(luò)架構(gòu)的設(shè)計上，即設(shè)計更加契合車輛路徑問題的數(shù)據(jù)結(jié)構(gòu)，主要包括像Ptr-Net 模型和transform 模型這種把問題建模為序列形式的輸入，然后基于各類attention機制對客戶節(jié)點的選擇優(yōu)先級進行排序；因車輛路徑問題天然是圖結(jié)構(gòu)，可基于圖神經(jīng)網(wǎng)絡(luò)和基于圖神經(jīng)網(wǎng)絡(luò)的attention 機制提取車輛路徑問題的特征。通過以上方法得到局部解后以自回歸的方式擴展得到最優(yōu)解。因為監(jiān)督式學(xué)習(xí)方法不適用與組合優(yōu)化問題，學(xué)者們采用具有反向?qū)W習(xí)能力的強化學(xué)習(xí)算法訓(xùn)練模型。深度強化學(xué)習(xí)模型求解速度遠超傳統(tǒng)的啟發(fā)式算法，模型泛化能力較強。

強化學(xué)習(xí)算法的優(yōu)勢是智能體通過和環(huán)境進行交互可以得到最優(yōu)策略，從而具備解決大規(guī)模復(fù)雜組合優(yōu)化問題的可能性，但其也存在著算法執(zhí)行時間過長、模型不易收斂等局限性。因此，可用其他啟發(fā)式算法和強化學(xué)習(xí)融合，主要是使用強化學(xué)習(xí)算法對啟發(fā)式搜索算子進行學(xué)習(xí)，加快求解速度，提高解的質(zhì)量，相較于人工設(shè)置搜索策略，強化學(xué)習(xí)算法可以擴大搜索空間和提高搜索策略效率，具有較強的優(yōu)化能力。

6 結(jié)論與展望

本文旨在對近年來基于強化學(xué)習(xí)求解車輛路徑優(yōu)化問題的各類算法進行較為全面的綜述，重點分析了各類強化學(xué)習(xí)算法的機制特點和優(yōu)劣性。如今在VRP的求解中各類深度強化學(xué)習(xí)模型不斷涌現(xiàn)，本文對這些模型的特點和優(yōu)化效果進行了總結(jié)?；谀Ｐ偷膹娀瘜W(xué)習(xí)算法必須對問題進行建模，但往往車輛路徑問題建模過程與現(xiàn)實環(huán)境總有差距。在基于編碼器-解碼器的transformer 模型和Ptr-Net 模型以及圖神經(jīng)網(wǎng)絡(luò)中強化學(xué)習(xí)算法都是作為訓(xùn)練模型的算法出現(xiàn)，選擇強化學(xué)習(xí)算法時目的性不強。且強化學(xué)習(xí)自身存在較強的探索和利用困境，個體不僅要學(xué)習(xí)以前樣本中的動作，還要對未來可能帶來高獎勵的動作進行探索，但車輛路徑問題是高度復(fù)雜的大型問題，強化學(xué)習(xí)常用的探索策略常常失效，探索策略的可擴展性較差。強化學(xué)習(xí)算法常因為經(jīng)驗樣本只被采樣一次或隨著經(jīng)驗的積累，同一個樣本被多次抽樣的概率越來越小，從而導(dǎo)致樣本的采樣率較低。計算機本身計算能力也限制了強化學(xué)習(xí)算法的效果。且目前基于強化學(xué)習(xí)求解車輛路徑問題的模型，主要都是對客戶節(jié)點小于100的問題進行求解，很少有作者對大規(guī)模車輛路徑問題進行求解。因此，未來基于強化學(xué)習(xí)模型求解車輛路徑問題的工作可從以下方面展開：

（1）建立更小誤差的環(huán)境模型。對于有模型的強化學(xué)習(xí)算法，精確的環(huán)境模型可以減少個體和環(huán)境的交互，可以通過模型仿真生成大量樣本數(shù)據(jù)，使得算法快速學(xué)習(xí)。通過更加科學(xué)的方式定義參數(shù)，減少人為設(shè)定引起不確定性，可增強模型的可靠性。但當(dāng)數(shù)據(jù)量較少的時候，學(xué)到的模型誤差較大，且現(xiàn)實生活中的車輛路徑問題的環(huán)境動力學(xué)較為復(fù)雜，從而使得建立精確模型更為困難。

（2）提高數(shù)據(jù)采樣率。針對無模型的強化學(xué)習(xí)算法數(shù)據(jù)采樣率低的問題，可以重新設(shè)計采樣方法，使用離軌策略設(shè)計并行架構(gòu)進行學(xué)習(xí)；針對有模型的強化學(xué)習(xí)算法采樣率低的問題，可以將模型誤差納入模型設(shè)計中，從而提高數(shù)據(jù)采樣率。

（3）設(shè)計更加高效的模型。目前求解車輛路徑的深度強化學(xué)習(xí)模型中，運用深度神經(jīng)網(wǎng)絡(luò)直接求解得到初始解的質(zhì)量較差，大多數(shù)模型都需要與其他方法結(jié)合提升解的質(zhì)量，使得求解時間變長。因而，未來可以對神經(jīng)網(wǎng)絡(luò)的理論基礎(chǔ)進行深入研究，設(shè)計更加高效的深度網(wǎng)絡(luò)結(jié)構(gòu)和表示方法，得到更加高效模型。尤其是圖神經(jīng)網(wǎng)絡(luò)與新型注意力機制結(jié)合是未來的重點研究方向之一。

（4）選擇更加合適模型訓(xùn)練算法。目前基于編碼器-解碼器求解車輛路徑問題的模型，常直接選用REINFORCE算法、Actor-Critic算法等常規(guī)的強化學(xué)習(xí)算法，不同類型的車輛路徑問題優(yōu)化目標不同，能有效解決復(fù)雜問題的多智能體強化學(xué)習(xí)和分層強化學(xué)習(xí)尚處在探索階段，如何選用更新高效強化學(xué)習(xí)算法作為模型的訓(xùn)練方法，對提升模型性能至關(guān)重要。這也是一個重要的改進方向。

（5）提升模型穩(wěn)定性?，F(xiàn)有的深度強化學(xué)習(xí)模型一旦訓(xùn)練完成，就可以求解同類型的問題，泛化能力較強，但是優(yōu)化效果無法保證，局部搜索算法可移植性差，但優(yōu)化效果較好。因此，運用更加高效的強化學(xué)習(xí)算法提升一些經(jīng)典局部搜索算法的求解速度，是未來重要的研究內(nèi)容。

（6）提高解決現(xiàn)實工程問題的能力。車輛路徑問題和現(xiàn)實生活息息相關(guān)，通常具有多約束、動態(tài)變化的特點，當(dāng)前的強化學(xué)習(xí)算法和深度強化學(xué)習(xí)模型可以求解的車輛路徑問題約束較少，規(guī)模較小。深度學(xué)習(xí)模型的最大優(yōu)勢就是可以在大規(guī)模問題上有良好表現(xiàn)，因此，設(shè)計更加契合車輛路徑問題的深度神經(jīng)網(wǎng)絡(luò)架構(gòu)是有效求解大規(guī)模、復(fù)雜車輛路徑問題的方法之一，這也是未來可著重研究的方向。

強化學(xué)習(xí)已成為熱門的組合優(yōu)化問題求解方法之一，但就目前而言，基于強化學(xué)習(xí)求解車輛路徑問題的算法模型并不具備真正的工程應(yīng)用能力。隨著研究不斷深入和理論不斷創(chuàng)新，強化學(xué)習(xí)將會和其他最新先進技術(shù)結(jié)合，讓強化學(xué)習(xí)在車輛路徑問題求解中發(fā)揮更大作用。