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

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

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

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

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

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

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

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

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

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

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

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

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

表1 求解車(chē)輛路徑問(wèn)題的常規(guī)方法優(yōu)缺點(diǎn)對(duì)比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)督信號(hào)來(lái)進(jìn)行學(xué)習(xí)，而是依賴(lài)個(gè)體（agent）在環(huán)境（environment）中的反饋回報(bào)信號(hào)，依據(jù)反饋回報(bào)信號(hào)對(duì)個(gè)體的狀態(tài)和行動(dòng)進(jìn)行更正，使得個(gè)體逐步實(shí)現(xiàn)獎(jiǎng)勵(lì)（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í)算法分類(lèi)

對(duì)強(qiáng)化學(xué)習(xí)算法的分類(lèi)可以根據(jù)有無(wú)模型分為基于模型（model-based）和無(wú)模型（model-free）的學(xué)習(xí)算法。在求解VRP中常見(jiàn)的基于模型的學(xué)習(xí)方法有動(dòng)態(tài)規(guī)劃法；無(wú)模型的學(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í)算法分類(lèi)圖Fig.2 Classification diagram of reinforcement learning algorithm

3 基于模型的算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（4）魯棒性差

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

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

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

表2 基于動(dòng)態(tài)規(guī)劃求解車(chē)輛路徑問(wèn)題的方法對(duì)比Table 2 Comparison of approaches of dynamic programming applied to VRP

4 無(wú)模型的算法

無(wú)模型的強(qiáng)化學(xué)習(xí)算法是指MDP模型中的環(huán)境參數(shù)未知，即在給定狀態(tài)條件下個(gè)體采取動(dòng)作以后，未來(lái)的狀態(tài)和獎(jiǎng)勵(lì)值未知。因此，個(gè)體不對(duì)問(wèn)題進(jìn)行建模，而是先和環(huán)境進(jìn)行交互，在不斷試錯(cuò)中尋找最優(yōu)策略。無(wú)模型的強(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í)算法通過(guò)對(duì)值函數(shù)進(jìn)行優(yōu)化從而得到最優(yōu)策略。在VRP 中，值函數(shù)是對(duì)路徑策略π優(yōu)劣的評(píng)估，值函數(shù)分為狀態(tài)價(jià)值函數(shù)V*(s)和狀態(tài)-動(dòng)作價(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é)合了動(dòng)態(tài)規(guī)劃算法和蒙特卡洛方法的原理，是通過(guò)部分狀態(tài)序列來(lái)求解問(wèn)題的強(qiáng)化學(xué)習(xí)算法。在時(shí)序差分算法中，價(jià)值函數(shù)的更新是通過(guò)兩個(gè)連續(xù)的狀態(tài)和其的獎(jiǎng)勵(lì)值的差來(lái)實(shí)現(xiàn)的。最基本的時(shí)序差分算法的價(jià)值函數(shù)更新公式為：

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

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

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

4.1.2 Q-learning算法

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

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

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

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

Q-learning 算法因優(yōu)先執(zhí)行動(dòng)作，主動(dòng)探索能力強(qiáng)。可有效的求解帶有隨機(jī)需求信息的車(chē)輛路徑問(wèn)題。但因是把狀態(tài)和不同的動(dòng)作存儲(chǔ)在Q 表中并一直更新，易使算法陷入局部最優(yōu)，降低算法的學(xué)習(xí)效率，搜索耗時(shí)較長(zhǎng)。更新Q表時(shí)Q表一直發(fā)生動(dòng)態(tài)變化，所以更新的效果不穩(wěn)定。

4.1.3 DQN算法

DQN算法是Mnih等人[20]提出的，該模型將Q-learning算法與深度神經(jīng)網(wǎng)絡(luò)相結(jié)合起來(lái)，通常使用DNN 或者CNN來(lái)構(gòu)建模型，使用Q-learning算法訓(xùn)練。DQN算法對(duì)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í)過(guò)程。DQN算法的損失函數(shù)如下：

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

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

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

針對(duì)客戶(hù)當(dāng)日要求交付（same-day delivery）的需求，Chen 等人[39]提出了車(chē)輛和無(wú)人機(jī)的當(dāng)天交付問(wèn)題（same-day delivery problem with vehicles and drones，SDDPVD），建模過(guò)程中采用和Powell[26]相同的模型架構(gòu)，并使用Ulmer等[40]提出的路由策略來(lái)模擬路線的更新和演變，首先將SDDPVD 建模為MDP 模型，為了使決策快速有效，將動(dòng)作空間和狀態(tài)空間進(jìn)行簡(jiǎn)化，通過(guò)設(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 算法通過(guò)一個(gè)經(jīng)驗(yàn)池來(lái)存儲(chǔ)以前的數(shù)據(jù)，每次更新參數(shù)的時(shí)候從經(jīng)驗(yàn)池中抽取一部分的數(shù)據(jù)來(lái)更新，打破信息間存在的關(guān)聯(lián)，從而可有效求解有狀態(tài)、動(dòng)作高維復(fù)雜，數(shù)據(jù)間彼此有關(guān)聯(lián)的車(chē)輛路徑問(wèn)題。

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

4.1.5 DQN算法局限性分析

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

（1）過(guò)擬合問(wèn)題

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

（2）樣本利用率低

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

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

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

4.1.6 Dueling DQN算法

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

式中，Qπ(s,a)為狀態(tài)s下選擇動(dòng)作a的獎(jiǎng)勵(lì)值，狀態(tài)值Vπ(s)是對(duì)狀態(tài)s的評(píng)價(jià)，動(dòng)作優(yōu)勢(shì)函數(shù)Aπ(s,a)是對(duì)狀態(tài)s下各個(gè)動(dòng)作優(yōu)劣的評(píng)價(jià)指標(biāo)。

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

4.1.7 Dueling DQN算法總結(jié)

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

4.2 基于策略的方法

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

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

定義策略梯度公式為：

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

4.2.1 蒙特卡洛REINFORCE方法

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

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

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

Nazari等人[45]針對(duì)CVRP構(gòu)建Ptr-Net—REINFORCE模型，該模型是一個(gè)end-to-end的深度強(qiáng)化學(xué)習(xí)模型，通過(guò)Ptr-Net進(jìn)行建模，在構(gòu)建指針網(wǎng)絡(luò)階段，Ptr-Net中的輸入為靜態(tài)值（客戶(hù)位置）與動(dòng)態(tài)值（客戶(hù)需求），其模型結(jié)構(gòu)如圖4 所示。不同于Ptr-Net 在訓(xùn)練模型時(shí)采用監(jiān)督式方法，使用REINFORCE 算法對(duì)模型進(jìn)行訓(xùn)練，分別在客戶(hù)數(shù)為10、20、50、100 的CVRP 數(shù)據(jù)集上進(jìn)行了測(cè)試，取得了比經(jīng)典的啟發(fā)式搜索算法CW、SW更好的效果。Xin 等人[46]為解決深度強(qiáng)化學(xué)習(xí)算法在構(gòu)造解的過(guò)程中無(wú)法修改以前決策，提出基于REINFORCE算法的分步SW-Ptr-Net 模型和近似SW-AM 模型。該方法有效提升了Ptr-Net 模型和AM 模型[47]對(duì)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 模型使用編碼器對(duì)車(chē)輛路徑問(wèn)題中的初始信息進(jìn)行編碼得到特征向量，再通過(guò)解碼器對(duì)特征向量進(jìn)行解碼，利用注意力機(jī)制計(jì)算每個(gè)客戶(hù)節(jié)點(diǎn)的選擇概率，從而構(gòu)造車(chē)輛路徑問(wèn)題的解。所有運(yùn)用Ptr-Net 模型構(gòu)造車(chē)輛路徑問(wèn)題的構(gòu)造過(guò)程大致如下：

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

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

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

Falkner 等人[47]針對(duì)CVRPTW，提出了JAMPR 模型，該模型由多個(gè)編碼器和一個(gè)解碼器組成，編碼器采用了self-attention 計(jì)算方法，通過(guò)加入兩個(gè)新的編碼器產(chǎn)生上下文信息以及增強(qiáng)聯(lián)合行動(dòng)空間，解碼器使用transform模型的多頭-attention機(jī)制。使用REINFORCE算法對(duì)JAMPR 模型進(jìn)行訓(xùn)練，模型架構(gòu)如圖5 所示。在對(duì)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）來(lái)訓(xùn)練波束搜索（beam search）的策略，MDAM 由一個(gè)編碼器和多個(gè)解碼器組成，編碼器采用和transformer模型相同的多頭-attention機(jī)制，每個(gè)解碼器采用節(jié)點(diǎn)嵌入的方式來(lái)產(chǎn)生訪問(wèn)每個(gè)有效節(jié)點(diǎn)的概率。使用REINFORCE 算法對(duì)JAMPR 模型進(jìn)行訓(xùn)練。在對(duì)CVRP 和SDVRP 等問(wèn)題的求解中，相較于所選基準(zhǔn)算法該模型的優(yōu)化效果要更好。為有效地解決具有軟時(shí)間窗的多車(chē)輛路徑問(wèn)題（multi-vehicle routing problem with soft time windows，MVRPSTW），Zhang 等人[49]提出了多智能體注意力模型（multi-agent attention model，MAAM），使用REINFORCE 算法對(duì)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模型，更好地獲取車(chē)輛路徑問(wèn)題的動(dòng)態(tài)特征。

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

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

Peng等人[51]結(jié)合動(dòng)態(tài)attention方法與REINFORCE方法設(shè)計(jì)了一種AM-D 模型來(lái)求解VRP，動(dòng)態(tài)attention方法是基于動(dòng)態(tài)編碼器-解碼器結(jié)構(gòu)來(lái)改進(jìn)的，改進(jìn)的關(guān)鍵是動(dòng)態(tài)挖掘?qū)嵗慕Y(jié)構(gòu)特征，并在不同的構(gòu)造步驟中有效地挖掘隱藏的結(jié)構(gòu)信息，模型架構(gòu)如圖6 所示。實(shí)驗(yàn)結(jié)果表明，在客戶(hù)數(shù)量為20、50、100 的CVRP 上優(yōu)化效果均超過(guò)了Kool等人[38]提出的AM方法，并明顯減小了最優(yōu)性差距。Lu等人[52]提出了基于迭代的learn to improve（L2I）框架，算法首先給出一個(gè)可行解，運(yùn)用基于REINFORCE 方法的控制器選擇改進(jìn)算子或基于規(guī)則的控制器選擇擾動(dòng)算子迭代更新解，經(jīng)過(guò)一定迭代步驟后從所有訪問(wèn)的解決方案中選擇最優(yōu)解。對(duì)于CVRP，該模型不僅在優(yōu)化效果上超過(guò)了Google ORtools、LKH3等專(zhuān)業(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）框架對(duì)CVRP、SDVRP等問(wèn)題進(jìn)行求解，運(yùn)用基于attention機(jī)制的神經(jīng)網(wǎng)絡(luò)對(duì)LNS 中的毀壞算子和重建算子進(jìn)行學(xué)習(xí)，并用REINFORCE 算法對(duì)NLNS 模型進(jìn)行訓(xùn)練。實(shí)驗(yàn)結(jié)果表明，在CVRP 實(shí)例上NLNS 模型與LKH3 性能相當(dāng)；在SDVRP 實(shí)例上，NLNS 能夠在擁有100 個(gè)客戶(hù)的實(shí)例上勝過(guò)目前最先進(jìn)的方法。

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

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

4.2.2 REINFORCE算法局限性分析

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

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

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

（2）算法收斂速度慢

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

（3）算法收斂性差

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

4.2.3 Actor-Critic算法

Actor-Critic 算法是一種基于值方法和基于策略方法相結(jié)合而產(chǎn)生的算法。該算法的架構(gòu)包括兩個(gè)部分：Actor 部分是基于策略方法的，通過(guò)生成動(dòng)作并和環(huán)境交互，用來(lái)逼近策略模型πθ(s,a)；Critic部分是基于值方法的，判定動(dòng)作的優(yōu)劣性，并且選擇下一個(gè)動(dòng)作，用來(lái)逼近值函數(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 算法對(duì)模型進(jìn)行訓(xùn)練，首先通過(guò)路由模擬器生成大量VRP 實(shí)例用于訓(xùn)練和驗(yàn)證，在Actor 網(wǎng)絡(luò)的編碼過(guò)程中將靜態(tài)特征和動(dòng)態(tài)特征分別編碼，在基本attention機(jī)制[38]中，模型對(duì)輸入序列的順序很敏感。為了克服這個(gè)問(wèn)題，采用了圖嵌入的方法，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模型在客戶(hù)點(diǎn)數(shù)分別為20、50 和100 的3 個(gè)數(shù)據(jù)集上進(jìn)行測(cè)試。實(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è)客戶(hù)可能總是有他自己的送貨點(diǎn)，比如同城快遞服務(wù)[57]和拼車(chē)服務(wù)[58]，而不是像VRP那樣為所有客戶(hù)共享一個(gè)倉(cāng)庫(kù)。所有這類(lèi)VRP可描述為提貨和交貨問(wèn)題（pickup and delivery problem，PDP）。Li 等人[56]提出了一種基于異構(gòu)attention 機(jī)制的編碼器-解碼器模型，其編碼層在多頭attention注意力方法中加入了異構(gòu)attention 方法以期更早得到優(yōu)先級(jí)較高的關(guān)系，采用Actor-Critic算法對(duì)該模型進(jìn)行訓(xùn)練。在PDP 求解中該模型的優(yōu)化效果要好于傳統(tǒng)的啟發(fā)式算法。Gao 等人[57]提出了基于圖注意力網(wǎng)絡(luò)的模型用去求解VRP、CVRP。該模型的編碼器是由一個(gè)graph attention network 組成，模型首先對(duì)每個(gè)客戶(hù)位置進(jìn)行編碼得到每個(gè)客戶(hù)頂點(diǎn)的邊緣嵌入和頂點(diǎn)嵌入，在通過(guò)attention機(jī)制計(jì)算出每個(gè)客戶(hù)被選擇的概率。解碼器采用和Ptr-Net一樣的架構(gòu)，為VLNS算法的破壞算子提供一個(gè)節(jié)點(diǎn)子集作為移除候選。依然采用Actor-Critic 算法對(duì)該模型進(jìn)行訓(xùn)練。

當(dāng)VRP、CVRP、CVRPW 等問(wèn)題的規(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é)：車(chē)輛路徑問(wèn)題是典型的具有圖結(jié)構(gòu)的組合優(yōu)化問(wèn)題，因圖神經(jīng)網(wǎng)絡(luò)能夠有效求解具有圖結(jié)構(gòu)的問(wèn)題，所以有學(xué)者把圖神經(jīng)網(wǎng)絡(luò)應(yīng)用到了車(chē)輛路徑問(wèn)題的求解中，運(yùn)用圖神經(jīng)網(wǎng)絡(luò)求解車(chē)輛路徑問(wèn)題的構(gòu)造。

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

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

Actor-Critic 算法中涉及到Actor 網(wǎng)絡(luò)和Critic 網(wǎng)絡(luò)兩部分，Actor網(wǎng)絡(luò)基于概率選擇動(dòng)作等價(jià)于策略函數(shù)，Critic網(wǎng)絡(luò)等價(jià)于價(jià)值函數(shù)。Actor-Critic算法每次更新都會(huì)涉及到這兩個(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ò)不收斂，那么它對(duì)Actor網(wǎng)絡(luò)的評(píng)估就不準(zhǔn)確，導(dǎo)致Actor網(wǎng)絡(luò)難收斂，使得Actor-Critic算法收斂速度慢。

4.2.5 Advantage Actor-Critic算法

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

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

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

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

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

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

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

表3 無(wú)模型方法求解車(chē)輛路徑問(wèn)題對(duì)比Table 3 Comparison of approaches of model-free applied to VRP

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

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

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

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

現(xiàn)在的使用深度強(qiáng)化學(xué)習(xí)模型解決車(chē)輛路徑問(wèn)題時(shí)主要的創(chuàng)新點(diǎn)是對(duì)深度神經(jīng)網(wǎng)絡(luò)架構(gòu)的設(shè)計(jì)上，即設(shè)計(jì)更加契合車(chē)輛路徑問(wèn)題的數(shù)據(jù)結(jié)構(gòu)，主要包括像Ptr-Net 模型和transform 模型這種把問(wèn)題建模為序列形式的輸入，然后基于各類(lèi)attention機(jī)制對(duì)客戶(hù)節(jié)點(diǎn)的選擇優(yōu)先級(jí)進(jìn)行排序；因車(chē)輛路徑問(wèn)題天然是圖結(jié)構(gòu)，可基于圖神經(jīng)網(wǎng)絡(luò)和基于圖神經(jīng)網(wǎng)絡(luò)的attention 機(jī)制提取車(chē)輛路徑問(wèn)題的特征。通過(guò)以上方法得到局部解后以自回歸的方式擴(kuò)展得到最優(yōu)解。因?yàn)楸O(jiān)督式學(xué)習(xí)方法不適用與組合優(yōu)化問(wèn)題，學(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)勢(shì)是智能體通過(guò)和環(huán)境進(jìn)行交互可以得到最優(yōu)策略，從而具備解決大規(guī)模復(fù)雜組合優(yōu)化問(wèn)題的可能性，但其也存在著算法執(zhí)行時(shí)間過(guò)長(zhǎng)、模型不易收斂等局限性。因此，可用其他啟發(fā)式算法和強(qiáng)化學(xué)習(xí)融合，主要是使用強(qiáng)化學(xué)習(xí)算法對(duì)啟發(fā)式搜索算子進(jìn)行學(xué)習(xí)，加快求解速度，提高解的質(zhì)量，相較于人工設(shè)置搜索策略，強(qiáng)化學(xué)習(xí)算法可以擴(kuò)大搜索空間和提高搜索策略效率，具有較強(qiáng)的優(yōu)化能力。

6 結(jié)論與展望

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

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

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

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

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

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

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

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