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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 基于模型的算法

在強(qiáng)化學(xué)習(xí)中“模型”指環(huán)境，基于模型的強(qiáng)化學(xué)習(xí)算法意為通過預(yù)先給定或通過學(xué)習(xí)的方式得到MDP模型。最典型的給定環(huán)境模型方法是打敗圍棋冠軍柯潔的阿爾法狗算法，通過學(xué)習(xí)的環(huán)境模型方法有world models 算法[23]。在VRP 求解中運(yùn)用最多的基于模型的強(qiáng)化學(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，從而對個(gè)體行動提供指導(dǎo)，但在現(xiàn)實(shí)生活中環(huán)境模型可能很復(fù)雜以至于難以建模。

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

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

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

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

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

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

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

為降低由交通擁堵引起的成本，Kok 等人[30]針對CVRPW，在近似動態(tài)規(guī)劃算法中加入了避免交通擁堵的策略，結(jié)果表明該方法能夠有效降低通勤中擁堵時(shí)長。Secomandi等人[31]針對只有一輛車的隨機(jī)需求車輛路徑問題（SDVRP），通過有限階段的MDP進(jìn)行建模，使用部分再優(yōu)化（partial reoptimization）的方法對SDVRP進(jìn)行研究，并通過PH、SH兩種啟發(fā)式算法選擇MDP的狀態(tài)子集，以此來計(jì)算最優(yōu)策略。Goodson 等人[32]提出了基于rollot 策略的近似動態(tài)規(guī)劃框架，并將該框架應(yīng)用于求解具有隨機(jī)需求和持續(xù)時(shí)間限制的多車輛路徑問題（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ìn)行求解，模型根據(jù)圖神經(jīng)網(wǎng)絡(luò)（graph neural network，GNN）得到的每個(gè)客戶頂點(diǎn)特征向量，通過注意力機(jī)制計(jì)算每個(gè)客戶頂點(diǎn)被選中的概率，并將這個(gè)概率作為動態(tài)規(guī)劃算法對部分解進(jìn)行選擇的策略，最后根據(jù)此策略構(gòu)造最優(yōu)解。

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

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

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

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

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

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

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

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

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

（3）實(shí)時(shí)求解效率低

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

（4）魯棒性差

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

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

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

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

4 無模型的算法

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

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

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

q*(s,a)表示為：

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

4.1.1 時(shí)序差分算法

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

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

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

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

4.1.2 Q-learning算法

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

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

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

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

Q-learning 算法因優(yōu)先執(zhí)行動作，主動探索能力強(qiáng)?？捎行У那蠼鈳в须S機(jī)需求信息的車輛路徑問題。但因是把狀態(tài)和不同的動作存儲在Q 表中并一直更新，易使算法陷入局部最優(yōu)，降低算法的學(xué)習(xí)效率，搜索耗時(shí)較長。更新Q表時(shí)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 的改進(jìn)主要有以下兩個(gè)方面：（1）DQN 算法利用神經(jīng)網(wǎng)絡(luò)逼近值函數(shù)。（2）DQN算法利用了經(jīng)驗(yàn)回放訓(xùn)練強(qiáng)化學(xué)習(xí)的學(xué)習(xí)過程。DQN算法的損失函數(shù)如下：

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

針對帶有多個(gè)倉庫（depots）的車輛路徑問題（MDVRP）和動態(tài)車輛路徑問題，Bdeir 等人[37]提出了基于DQN 的RP-DQN 模型，該模型框架如圖3 所示。RP-DQN 模型中為有效降低問題的計(jì)算復(fù)雜性，編碼器不僅對靜態(tài)的客戶節(jié)點(diǎn)位置、客戶需求進(jìn)行編碼，并對問題中的動態(tài)特征信息進(jìn)行編碼，使用Q-learning 算法對模型進(jìn)行優(yōu)化。在客戶數(shù)量為20、50、100 的CVRP 上優(yōu)化效果均超過了Kool 等人[38]的方法。首次將深度Q 網(wǎng)絡(luò)運(yùn)用到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]提出了車輛和無人機(jī)的當(dāng)天交付問題（same-day delivery problem with vehicles and drones，SDDPVD），建模過程中采用和Powell[26]相同的模型架構(gòu)，并使用Ulmer等[40]提出的路由策略來模擬路線的更新和演變，首先將SDDPVD 建模為MDP 模型，為了使決策快速有效，將動作空間和狀態(tài)空間進(jìn)行簡化，通過設(shè)計(jì)DQN算法去近似每個(gè)特征向量的值。

4.1.4 DQN算法總結(jié)

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

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

4.1.5 DQN算法局限性分析

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

（1）過擬合問題

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

（2）樣本利用率低

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

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

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

4.1.6 Dueling DQN算法

針對無模型的強(qiáng)化學(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的評價(jià)，動作優(yōu)勢函數(shù)Aπ(s,a)是對狀態(tài)s下各個(gè)動作優(yōu)劣的評價(jià)指標(biāo)。

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

4.1.7 Dueling DQN算法總結(jié)

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

4.2 基于策略的方法

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

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

定義策略梯度公式為：

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

4.2.1 蒙特卡洛REINFORCE方法

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

不斷執(zhí)行動作直到結(jié)束，在一個(gè)回合結(jié)束之后計(jì)算總反饋，然后根據(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ā)式搜索算法。該模型具有求解更快的特點(diǎn)，這是深度學(xué)習(xí)在組合優(yōu)化問題上的首次應(yīng)用，旅行商問題是VRP的一種特例，因此，研究人員開始將指針網(wǎng)絡(luò)模型應(yīng)用于VRP的求解。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2.2 REINFORCE算法局限性分析

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

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

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

（2）算法收斂速度慢

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

（3）算法收斂性差

在車輛路徑問題中，REINFORCE 算法為控制訓(xùn)練個(gè)體的時(shí)間，不可能遍歷所有狀態(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)包括兩個(gè)部分：Actor 部分是基于策略方法的，通過生成動作并和環(huán)境交互，用來逼近策略模型πθ(s,a)；Critic部分是基于值方法的，判定動作的優(yōu)劣性，并且選擇下一個(gè)動作，用來逼近值函數(shù)Q(s,a)。Actor 與Critic 之間互補(bǔ)的訓(xùn)練方式相較于單獨(dú)的算法更加有效。策略梯度函數(shù)為：

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

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

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

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

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

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

強(qiáng)化學(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)用到了車輛路徑問題的求解中，運(yùn)用圖神經(jīng)網(wǎng)絡(luò)求解車輛路徑問題的構(gòu)造。

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

4.2.4 Actor-Critic算法局限性分析

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

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

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

（2）收斂速度慢

Actor-Critic算法中Critic網(wǎng)絡(luò)收斂速度慢，若Critic網(wǎng)絡(luò)不收斂，那么它對Actor網(wǎng)絡(luò)的評估就不準(zhǔn)確，導(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值來對策略梯度進(jìn)行計(jì)算，但這種計(jì)算方式存在高方差的問題，從而可以引入Baseline 的方式減小梯度使得訓(xùn)練更加平穩(wěn)，通過這種改進(jìn)就能得到A2C 算法。A2C 算法的策略梯度函數(shù)為：

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)論與展望

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

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

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

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

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

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

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

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