張景玲，馮勤炳，趙燕偉，劉金龍，冷龍龍

(浙江工業(yè)大學 特種裝備制造與先進加工技術(shù)教育部重點實驗室，浙江 杭州 310014)

0 引言

為了有效分配物流資源，減少運輸成本，車輛路徑問題(Vehicle Routing Problem, VRP)一直是物流調(diào)度領(lǐng)域研究的熱點問題。車輛路徑問題最早由Dantizg等[1]于1959年提出，其基本問題為有容量車輛路徑問題(Capacitated Vehicle Routing Problem, CVRP)，該問題在滿足車載量約束條件下，以服務(wù)所有客戶的最小化車輛行駛距離為目標，達到降低物流配送成本的目的。因此，本文提出一種基于強化學習的超啟發(fā)算法，致力于更有效地優(yōu)化配送路徑，解決車輛路徑問題。

近年來，各種算法被應(yīng)用于求解VRP以及衍生類問題。精確算法方面，如：分支定界法[2]，最小化K-trees[3]，動態(tài)規(guī)劃算法[4]等，此類算法能求得全局最優(yōu)解，但是當客戶點規(guī)模較大時，求解時間較長；傳統(tǒng)啟發(fā)式算法方面，如：節(jié)約法[5]，兩階段法[6]等，相較于精確算法，能夠更加有效地找尋最優(yōu)解，但同樣在大規(guī)模問題上，效率不佳；智能算法，因其既能得到優(yōu)解，又能保證效率的優(yōu)點，得到許多研究者青睞。Osman[7]使用模擬退火以及禁忌搜索算法作為策略，在VRP上求得了不錯的結(jié)果。Bullnheimer等[8]和Baker等[9]，分別提出了一種改進蟻群算法、遺傳算法，用于VRP，并將其與模擬退火算法和禁忌搜索算法效果相比較。Marinakis等[10]在粒子群算法中融合了局部搜索和路徑重構(gòu)策略，用于隨機需求車輛路徑問題中，取得了較好的效果。Zhang等[11]使用量子進化算法求解以路徑及客戶滿意度兩個方面為目標的多目標VRP。Marshall等[12]提出了基于語言進化的超啟發(fā)算法，在解決問題域經(jīng)驗不足的情況下，同樣可以求解VRP問題，并在實例中得到效果驗證。

超啟發(fā)算法(Hyper-heuristics Algorithm, HH)被稱為“尋找啟發(fā)式算法的啟發(fā)式算法”，其主要由高層啟發(fā)式策略(High-Level Heuristic，HLH)和底層啟發(fā)式算子(Low-Level Heuristics，LLH)兩個部分組成。LLH是對實際問題進行獨立搜索，而HLH是對LLH進行科學合理的選擇，并對產(chǎn)生的解判別接受。HLH設(shè)計主要指選擇策略和解的接受準則兩個方面。

超啟發(fā)算法由于具有通用性、高效性等優(yōu)點，已被廣泛運用于多個領(lǐng)域。Cowling等[13]將超啟發(fā)算法用于人員調(diào)度，減少了分配時間，提升了分配質(zhì)量。Kheiri等[14]研究了基于序列分析的超啟發(fā)算法，將其用于基準水網(wǎng)調(diào)配優(yōu)化。邱俊熒[15]提出了基于帶path-relinking的GRASP超啟發(fā)算法，由構(gòu)造底層算子序列階段、局部搜索階段和path-relinking階段組成，并將其與模擬退火算法進行了比較。Walker等[16]在超啟發(fā)算法局部搜索算子中添加自適應(yīng)機制，將其用于帶時間窗的車輛路徑問題。Sabar等[17]提出構(gòu)建蒙特卡洛樹搜索框架的超啟發(fā)算法，即將底層算子看作一棵樹，用蒙特卡洛法識別其不同序列。Soria-Alcaraz等[18]對超啟發(fā)算法的確定有效啟發(fā)式子集進行了討論，提出一種新穎的迭代局部搜索算子。Dokeroglu等[19]利用標準庫中有關(guān)最新的元啟發(fā)式，模擬退火，魯棒禁忌搜索，蟻群優(yōu)化和突破局部搜索算子，來解決二次指派問題。Zamli等[20]將禁忌搜索作為高層選擇策略，將教學學習優(yōu)化算法、全局領(lǐng)域算法、粒子群算法和布谷鳥算法作為底層搜索算子，改進超啟發(fā)算法。Choong等[21]設(shè)計了基于強化學習的超啟發(fā)算法，將Q算法用于高層選擇策略，驗證了其算法與其他性能最好的算法效果相當。

鑒于超啟發(fā)算法優(yōu)秀的搜索性能，而強化學習又能基于學習評價動作，本文將強化學習策略——深度Q神經(jīng)網(wǎng)絡(luò)(Deep Q Network，DQN)算法引入超啟發(fā)算法的高層策略設(shè)計，旨在利用學習機制，對底層啟發(fā)式算子立即獎懲、將來獎懲進行權(quán)衡；設(shè)置較優(yōu)序列池，同時使用模擬退火的接受準則，更有效地引導底層算子搜索，獲得優(yōu)質(zhì)解。并利用所提算法對CVRP進行求解，驗證其性能。本文首先介紹了CVRP的描述與模型，然后構(gòu)造了一種基于DQN算法的超啟發(fā)算法，最后使用該算法對標準算例進行計算。根據(jù)仿真實驗的結(jié)果，并與其他算法進行比較分析，證明了基于DQN算法的超啟發(fā)算法在解決CVRP上的有效性。

1 有容量車輛路徑問題

1.1 問題描述

CVRP描述為：假設(shè)有一個已知位置的配送中心，對多個已知位置和需求量的客戶點進行貨物配送。約束為：每個客戶點有且僅有一輛車對其服務(wù)；每輛車有一定標準載重量；完成配送任務(wù)后，每輛車須返回配送中心。目標為：求在保證最小使用車輛數(shù)的前提下，所有車輛行駛的最短總距離(或最低總成本)以及路徑分布。由于其是一個NP-hard問題，當客戶規(guī)模較大時，傳統(tǒng)的數(shù)學規(guī)劃方式難以求解，而傳統(tǒng)啟發(fā)式算法、智能算法也容易陷入局部最優(yōu)，無法獲得全局最優(yōu)解的情況。為此，設(shè)計能克服以上難點的算法，求得問題最優(yōu)解，具有較大意義。

1.2 數(shù)學模型

將上述問題轉(zhuǎn)化為數(shù)學模型[22]：配送中心設(shè)為i=0，客戶點設(shè)為L(i=1,2,3,…,L)，最多車輛數(shù)設(shè)為K(k=1,2,3,…,K)，每輛車具有相同載重量為q，每個客戶點需求量設(shè)為di(i=1,2,3,…,L)，客戶i到客戶j的距離設(shè)為cij。定義以下變量：

數(shù)學模型如下：

(1)

(2)

(3)

(4)

且≠Φ?k。

(5)

其中：式(1)表示所求目標函數(shù)，即最短總距離；式(2)為每輛車的標準載重量約束；式(3)保證每個客戶點都被服務(wù)；式(4)保證每個客戶有且僅有一輛車服務(wù)；式(5)表示消除子回路。

2 基于強化學習的超啟發(fā)式算法設(shè)計

鑒于CVRP的NP-hard屬性，設(shè)計了基于強化學習的超啟發(fā)算法。利用聚類方式提升初始解的質(zhì)量。在此基礎(chǔ)上，將強化學習引入超啟發(fā)算法的高層選擇策略，為了更好地選擇底層算子，設(shè)計常數(shù)Ck輔助判別State值，利用學習機制，主動記錄在所有狀態(tài)下算子的相對優(yōu)劣性；結(jié)合模擬退火算法，選擇性接收優(yōu)劣算子。并設(shè)計序列池，動態(tài)存儲當前序列，從而一定程度上擴大全局搜索能力。

超啟發(fā)算法的設(shè)計主要包括以下幾方面：初始解的設(shè)計；高層啟發(fā)式策略HLH設(shè)計；底層啟發(fā)式算子LLH設(shè)計；算法流程框架設(shè)計。

2.1 初始解的設(shè)計

對一個可行解的要求是：能夠包含所有客戶，且每個客戶點只出現(xiàn)一次；在滿足車輛標準載重量的條件下，粗略劃分路徑數(shù)，即大致確定由k輛車運輸；每條路徑起始點、終點皆為配送中心。如果在算法初期，給予較優(yōu)質(zhì)初始解，則有助于減少算法搜索的時間，提升效率。因此，本文采用聚類[23]的思想。但由于通常的聚類方法都需要不斷迭代，尋找聚類點，為了降低選取聚類點產(chǎn)生的耗時性，本文將按距離最短選擇聚類點，雖不能獲得準確點，但已經(jīng)能達到優(yōu)化初始解的目的。

具體步驟如下：

步驟1對于第k條路徑，先設(shè)配送中心點為i=L+1(也可設(shè)為“0”)，即該路徑兩端點都為i=L+1；隨機挑選客戶點L(i=1,2,3,…,L)，加入首尾點中間，判斷該車輛現(xiàn)載重量情況。

步驟2從剩下的客戶點中繼續(xù)隨機挑選，依次加入路線，直到超出標準載重量，則產(chǎn)生第k+1條路徑；將超超出標準載重量的點，加入新路線中；重復(fù)循環(huán)，當所有客戶點都被選取，則一個初始種群個體生成。

步驟3多次進行上述操作，生成一定數(shù)量個體的種群，數(shù)量為Npop。對Npop個個體進行路徑判斷，選出具有最短路徑數(shù)的個體，記最短路徑數(shù)為k，將k作為劃分塊的數(shù)量。

步驟4計算所有客戶點與倉庫點的距離ci-L+1(i=1,2,3,…,L)。為了節(jié)省聚類分類的時間，將ci-L+1升序排列，只取前k個點作為聚類中心點，設(shè)為LKC(KC=1,2,3,…,k)，KC代表聚類塊，以除聚類中心點外的其他客戶點，與各聚類中心的距離最短為原則，進行聚類。

步驟5隨機排列KC塊，按車輛載重量分配，依KC塊排列順序，隨機挑選客戶。若KC塊中客戶點未能滿足k車輛載重，則向KC+1塊中隨機抽取客戶點，直至滿足，反之則向后延用至k+1輛車，共組成k條路徑，由此產(chǎn)生一個初始解個體。

2.2 超啟發(fā)算法的高層啟發(fā)式策略HLH構(gòu)建

超啟發(fā)算法的高層啟發(fā)式策略HLH主要包括底層算子的選擇策略和解的接受準則兩方面。這兩方面的設(shè)計是超啟發(fā)算法設(shè)計的關(guān)鍵。對于底層算子的選擇策略，本文將強化學習中的DQN算法[24-25]引入超啟發(fā)算法。對于解的接受準則，本文利用模擬退火的接受準則，對劣勢解選擇性接收，引導解向較好效果的方向發(fā)展。

2.2.1 基于DQN的底層算子的選擇策略

DQN算法主要基于Q-Learning算法的思想，利用當前狀態(tài)State，下一步行動Action，下一步狀態(tài)Statet，延用Q值的計算方法，建立損失函數(shù)，構(gòu)建神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，起到預(yù)測下一步底層算子性能表現(xiàn)的作用。將DQN算法作為底層算子的選擇策略，根據(jù)當前解的狀態(tài)(或者解的發(fā)展趨勢)，挑選下一步底層算子。

(1)State設(shè)計

State表示事物當前的狀態(tài)。設(shè)計目的：盡可能體現(xiàn)Action對事物產(chǎn)生的影響以及能夠為挑選之后的Action起到預(yù)測選擇作用。由于本文將算法用于求解CVRP，難以對State值提前劃分確切范圍，State值完全取決于各Action對解的適應(yīng)度值的影響，同時為了在挑選算子中，保證解的多樣性，State值在一定時期(未求到最優(yōu)解的情況下)，須在一定范圍內(nèi)不斷變化。將State代表適應(yīng)度值的變化程度，設(shè)計當前代的適應(yīng)度值為fit，上一代的適應(yīng)度值為fit′，上一代的平均適應(yīng)度為avg(fit′)，設(shè)計State的表達式為以下兩種：

State=-(fit-avg(fit′))/avg(fit′)，

(6)

State=-(fit-fit′)/fit′。

(7)

對以上兩個表達式進行實驗仿真，設(shè)初始狀態(tài)為“0”，結(jié)果如圖1所示。

由圖1可得，兩式在一定代數(shù)之內(nèi)State因外部環(huán)境都呈現(xiàn)上下?lián)u擺的情況。但是式(6)容易在求得局部最優(yōu)解后，隨著代數(shù)的增加，呈現(xiàn)“假State”狀態(tài)，此時的fit=fit′為局部最優(yōu)值，一直未發(fā)生變化，但State由于

(8)

式(8)中分子增長后的值小于分母(iter為迭代次數(shù))，整體呈現(xiàn)逐漸下降趨勢，是對當前狀態(tài)的錯誤反應(yīng)。而式(7)表示的State值在局部最優(yōu)后穩(wěn)定為0，正確反映當前狀態(tài)，有利于算法對產(chǎn)生局部最優(yōu)狀態(tài)的判別，更符合設(shè)計要求。

因為在此類求最優(yōu)問題中，單純的運行趨勢無法確切表示當前狀態(tài)。在算子選擇中，本文采用了3種類型的算子，將其分為局部優(yōu)化算子與變異算子兩大類，鑒于兩類算子優(yōu)化性能不同，為了更好地體現(xiàn)算子對當前狀態(tài)的影響，添加State值的輔助判別機制：利用常數(shù)Ck值，作為State基數(shù)，需滿足的條件為，對State值的影響遠大于由fit值變化引起的影響(起到區(qū)分算子種類作用，利于后續(xù)求解算子獎懲值)，經(jīng)測試觀察，fit值變化引起的式(7)大小變化范圍見如1右圖所示，值約為[-1.4,0.6]，變化區(qū)間的長度約為2。經(jīng)分析，若局部優(yōu)化算子Ck=10，變化區(qū)間長度占Ck值的20%，影響較大，基準性較差；取局部優(yōu)化算子Ck=20，變化區(qū)間長度占Ck值的10%，滿足既能擾動State值，且影響較小的條件；取局部優(yōu)化算子Ck=60，變化區(qū)間長度占Ck值的3%，擾動性較低。因此，最終選擇局部優(yōu)化算子Ck=20。因為基準值越大，State值越大，越容易被選擇。且由于變異算子較局部優(yōu)化算子效果更具間接性，即變異算子根據(jù)適應(yīng)度值較優(yōu)的準則不容易被選擇，為了平衡兩種算子被選擇的概率，定變異算子的Ck值為局部優(yōu)化算子的2倍，變化區(qū)間長度占Ck值的5%。由于變異算子相較于局部優(yōu)化算子優(yōu)化效果更間接性，定變異算子的Ck值為局部優(yōu)化算子的2倍，變化區(qū)間長度占Ck值的5%。因此定義如下：

則

State=-(fit-fit′)/fit′+Ck。

(9)

(2)Action，Reward設(shè)計

由于本文在HLH中使用算法的目的是選擇LLH的算子，利用算子在問題解的空間中，搜索優(yōu)質(zhì)解，Action值為LLH算子的指代值(如算子“1”，算子“2”……)。

在考慮State值時，已經(jīng)對算子種類進行對應(yīng)區(qū)分，因此擾動算子的Reward值判斷方法，不再區(qū)別于其他種類算子。因此，利用Reward代表立即回報值，若當前解的質(zhì)量比上代解的質(zhì)量提升，則Reward=1；未提升則Reward=0；質(zhì)量下降，則Reward=-1。

(3)DQN算法主要結(jié)構(gòu)部分設(shè)計

DQN算法結(jié)構(gòu)中主要包括經(jīng)驗池、估值網(wǎng)絡(luò)、目標網(wǎng)絡(luò)。

為了提供歷史經(jīng)驗，對Q值計算提供參考，在DQN算法中設(shè)計經(jīng)驗池(Experience Pool, EP)。EP存儲的是NE組數(shù)據(jù)，N代表經(jīng)驗池的容量。每組數(shù)據(jù)由State，Action，Reward，Statet四個部分組成，記錄的是當前事物狀態(tài)以及進行下一步動作后的立即回報值和下一步狀態(tài)值。

傳統(tǒng)的Q值計算與神經(jīng)網(wǎng)絡(luò)相結(jié)合的算法，只采用一個神經(jīng)網(wǎng)絡(luò)，若其中具有錯誤歷史(即某個連續(xù)時刻，某個動作獎賞極大)，則會使該動作的Q值評價大于實際性能水平，因此設(shè)計估值網(wǎng)絡(luò)與目標網(wǎng)絡(luò)來均衡歷史的影響。估值網(wǎng)絡(luò)與目標網(wǎng)絡(luò)是同結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)。包含同樣的隱藏層數(shù)及結(jié)構(gòu)，以及相同個數(shù)的神經(jīng)元節(jié)點。輸入層節(jié)點數(shù)根據(jù)State輸入值設(shè)置為一個，輸出層節(jié)點數(shù)根據(jù)低層算子數(shù)量進行設(shè)置。利用隨機，初始化估值網(wǎng)絡(luò)的閾值ωe、權(quán)值be以及目標值網(wǎng)絡(luò)的閾值ωt、權(quán)值bt。估值網(wǎng)絡(luò)的輸入值為NE組中某一組的State，目標值網(wǎng)絡(luò)的輸入值為對應(yīng)組中的Statet。在估值網(wǎng)絡(luò)輸出值中取對應(yīng)第NE組中Action所對應(yīng)的Qe，即Qe(Action)，而在目標值網(wǎng)絡(luò)的輸出值中取最大的輸出值max(Qt)，將兩者根據(jù)下式進行計算，作為更新估值網(wǎng)絡(luò)的損失函數(shù)值的判斷：

Loss=((Reward+γ·max(Qt))-

Qe(Action))2。

(10)

根據(jù)Loss值，對ωe和be作更新處理，其中γ為折扣率。一定代數(shù)以后，將ωe和be分別替代ωt和bt，以此更新目標網(wǎng)絡(luò)。利用更新后的估值網(wǎng)絡(luò)，對當前狀態(tài)的下個動作產(chǎn)生的影響進行預(yù)測，根據(jù)預(yù)測情況選擇Action值。

2.2.2 解的接受準則

接受準則的目的就是判斷是否需要用當前解代替先前解。當產(chǎn)生改進解時，必然接受；當產(chǎn)生非改進解時，一律接受，容易使算法整體運算緩慢；一律拒絕，則會導致種群缺乏多樣性，最終陷入局部最優(yōu)的情況。因此，接受準則對算法的收斂速度及優(yōu)化精度有很大影響。張景玲等[26]采用模擬退火算法(Simulated Annealing, SA)作為接受準則，取得了不錯的效果，因此本文也引用其作為算法的接受準則，以概率p選擇性接受非改進解，

p=exp(ΔE/Tk)，

(11)

Tk+1=Tk·β。

(12)

其中：ΔE表示算子作用后，前后解的質(zhì)量差，β表示降溫系數(shù)，k為溫度計數(shù)器。

2.2.3 搜索空間優(yōu)化

本文的主體搜索方式為先分配后排序，以減小搜索空間的目的進行設(shè)計。由2.1節(jié)可知，采用先將客戶點按載重分配，在滿足載重的條件下，進行順序優(yōu)化的方法。在算法過程中，采用縮小解的搜索空間的思想[27]設(shè)計序列池(Sequence pool，SP)，保存算子優(yōu)化后得到的最優(yōu)解序列(一輛車的路徑)，進行后續(xù)搜索。如圖2所示。

圖2左圖代表搜索空間所屬，可知如果沒有任何約束，只對序列進行排序，則搜索空間最大；若利用載重等約束條件進行限制，則相對縮小了搜索空間；在約束后的基礎(chǔ)上，再次進行序列的優(yōu)化，則能獲得更小的搜索空間。圖2右圖代表實施過程，即因為采用局部搜索算子優(yōu)化后，所得的序列(每輛車的路徑分布)都是較優(yōu)序列，搜索序列池，判斷是否存在該序列點集。若不存在，則直接存入序列池；存在則對比，替代該序列或者更新序列池。

2.3 超啟發(fā)算法的底層啟發(fā)式算子LLH設(shè)計

根據(jù)VRP的特點，設(shè)計對應(yīng)的幾種算子，主要為局部優(yōu)化算子(Local Research，LLH-L)、變異算子(Mutation，LLH-M)和破壞與重構(gòu)算子(Location-based Radial Ruin，LLH-LR)3大類。將變異算子與破壞重構(gòu)算子合為一類，具體算子為如表1所示。

表1 底層算子表

將其根據(jù)作用分類是為了方便設(shè)計State的基數(shù)。局部優(yōu)化算子主要通過點或者部分交換以及重定位的方式，對路徑進行優(yōu)化，作用后能夠絕對判別作用效果(Reward值大，則效果好，反之效果差)；變異算子主要起到擾動作用，作用后作用效果并非可以絕對判別。1)～3)是路徑內(nèi)局部優(yōu)化算子；4)～6)是路徑間局部優(yōu)化算子；7)～11)為變異算子。

2.4 基于強化學習的超啟發(fā)式算法框架設(shè)計

利用DQN算法的學習機制，對在不同狀態(tài)下，使用不同LLH算子對解產(chǎn)生的影響作評價，保留較優(yōu)序列和較優(yōu)解，由此選擇相對較優(yōu)的LLH算子進行解的搜索，設(shè)計如下算法流程(如圖3)：

步驟1初始化。先生成Npop組個體的種群，得到使用的最小車輛數(shù)為k，利用聚類思想將客戶點區(qū)域劃分為k塊，稱劃分成的每塊區(qū)域為“KC塊”，由KC塊隨機挑選生成可行解組P(pi=p1,p2,p3,…,pNP)，計算種群適應(yīng)度f(fi=f1,f2,f3,…,fNP)。隨機挑選一組可行解pi以及對應(yīng)適應(yīng)度值fi，設(shè)PB為最優(yōu)解個體，F(xiàn)B為最優(yōu)適應(yīng)度值，設(shè)LLH算子數(shù)量為NA，Action取值為(1,2,3,…,NA)整數(shù)，初始化PB=pi，F(xiàn)B=fi，State=0，Action=random(NA)(隨機挑選一個范圍NA中的數(shù))。

步驟2經(jīng)驗池、序列池存儲。操作上步Action后，產(chǎn)生的個體為Ind，適應(yīng)度值fit，根據(jù)適應(yīng)度值，判斷立即回報值Reward，此時狀態(tài)即為“下一個狀態(tài)”，判斷該State和Statet所屬狀態(tài)，利用式(12)計算Statet值。設(shè)EP代表經(jīng)驗池，將上述值存入，則EPnE=[State,Action,Reward,Statet]，nE代表經(jīng)驗池中數(shù)據(jù)組數(shù)。當達到一定次數(shù)后，判斷此時State值所屬狀態(tài)，如果為15≤State≤25，則此時Action為路徑內(nèi)算子，對此時的序列進行篩選，質(zhì)量優(yōu)則存入SP，SP代表序列池，反之，則更新序列。SP設(shè)常量Qsp為容量，且每次對比SP中序列，若此時序列在SP中有對應(yīng)序列集，則SP中該序列計數(shù)一次。當SP容量已滿，則刷新對比次數(shù)最少的序列。

步驟3解的接受保留。判斷，如果fit隨機值，則同樣保留好解，同時更新狀態(tài)，反之，則舍去該解，此時Statet=State，fit′=fit′。

步驟4判斷經(jīng)驗池容量。判斷經(jīng)驗池內(nèi)組數(shù)nE，n≥NE，則進入步驟7學習環(huán)節(jié)，否則，進入步驟5選擇Action步驟。

步驟5選擇Action。設(shè)置epsilon值，若隨機值>epsilon，將State值，輸入估值網(wǎng)絡(luò)，輸出Qe值，取max(Qe)所對應(yīng)的Action，若隨機值

步驟6保留全局最優(yōu)解，判斷算法是否結(jié)束。若fit≤FB，更新全局最優(yōu)解，F(xiàn)B=fit，PB=Ind，否則保留原有解。若nG≥G，返回步驟2，否則算法結(jié)束。

步驟7選擇學習樣本，并初始化神經(jīng)網(wǎng)絡(luò)。從EP中隨機挑選NS組，作為學習樣本，記為ESP。初始化估值網(wǎng)絡(luò)和目標網(wǎng)絡(luò)的閾值和權(quán)值ωe、be、ωt、bt。

步驟9更新目標值網(wǎng)絡(luò)。判斷學習代數(shù)Ln≥LN，則令ωt、bt替代ωe、be的值。

步驟10判斷學習結(jié)束情況。若學習代數(shù)Ln≤(3/4)×NS，則進入步驟8繼續(xù)學習更新。反之，則進入步驟5選擇Action，返回主循環(huán)。

2.5 基于強化學習的超啟發(fā)式算法復(fù)雜度分析

對算法的時間復(fù)雜度進行分析是對算法運行時間性能的一種評估方法。本文算法為基于強化學習的超啟發(fā)算法，簡稱為HH-RLDQN。影響本文算法的復(fù)雜度計算的因素有：初始化種群的種群規(guī)模NP，客戶數(shù)量N，車輛數(shù)量K，迭代次數(shù)Gmax，底層算子數(shù)量為NL，序列池容量SP，神經(jīng)網(wǎng)絡(luò)中學習樣本數(shù)量LN，神經(jīng)網(wǎng)絡(luò)的隱藏層節(jié)點數(shù)HN。

對本文算法計算時間復(fù)雜度：隨機化初始并聚類種群復(fù)雜度為O(2×NP×N2+NP×K)，計算適應(yīng)度值復(fù)雜度為O(NP)；高層策略中，求解經(jīng)驗池(State, Action, Reward, Statet三個值的求解以及寫入經(jīng)驗池)復(fù)雜度為O(1+1+1+1)，每次所得序列與序列池中序列的對比次數(shù)設(shè)為最大值(與全池序列對比)復(fù)雜度為O(SP)，接受策略復(fù)雜度為O(1)，神經(jīng)網(wǎng)絡(luò)學習復(fù)雜度約為O(LN×(HN+3×HN+1))，選擇Action選耗時更長復(fù)雜度為O(HN)；底層算子執(zhí)行，由于每一步選擇的算子未知，選擇耗時最長的算子復(fù)雜度為O(N2)[28]。算法迭代一次的復(fù)雜度約為O(2×NP×N2+NP×K)+O(NP)+O(4)+O(SP)+O(1)+O(LN×(HN+3×HN+1))+O(HN)+O(N2)，算法總體計算復(fù)雜度約為：

O(HH-RLDQN)=O(2×NP×N2+NP×K)+

Gmax×(O(NP)+O(4)+O(SP)+O(1)+

O(LN×(HN+3HN+1))+O(HN)+O(N2))

≈O((Gmax+NP)×N2+Gmax×LN×HN)。

(13)

由式(13)可得，算法的總體復(fù)雜度約為O((Gmax+NP)×N2+Gmax×LN×HN)，即高層策略的復(fù)雜度除了神經(jīng)網(wǎng)絡(luò)部分，其他忽略不計。本文算法復(fù)雜度主要的影響因素還是迭代次數(shù)Gmax，初始化種群的種群規(guī)模NP，客戶數(shù)量N，神經(jīng)網(wǎng)絡(luò)中學習樣本數(shù)量LN，神經(jīng)網(wǎng)絡(luò)的隱藏層節(jié)點數(shù)HN。文獻[29-30]中計算總體復(fù)雜度用本文符號表示都為O(Gmax×NP×N2)，因為

O((Gmax+NP)×N2)<

NP×N2)且HN≈NP。

(14)

本文的神經(jīng)網(wǎng)絡(luò)中學習樣本數(shù)量LN取值范圍始終小于1 000，則LN≤N2恒成立，即

O((Gmax+NP)×N2+Gmax×LN×HN)

≤O(Gmax×NP×N2)，

(15)

式(15)恒成立。由上述分析可得，本文算法的計算復(fù)雜度與其他群體智能進化算法計算復(fù)雜度在同一個量級，在計算機計算的可承受范圍之內(nèi)。

3 數(shù)值實驗

實驗環(huán)境Intel(R)core-i5-3230M, 12 GB RAM，MATLAB語言編寫程序。經(jīng)過反復(fù)測試，程序中使用的參數(shù)有Q值函數(shù)中折扣率γ=0.8，epsilon初始值=0.5，迭代最大代數(shù)Gmax=10^6，經(jīng)驗池NE=800，學習挑選樣本NS=600。

實驗利用HH-RLDQN，對CVRP的標準算例進行求解。分別選取Set A，Set E和Set P的標準算例求解，對每個算例計算20次。所有算例可在網(wǎng)址：http://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-instances/下載。其中算例最優(yōu)距離解(BK)，實驗所得最優(yōu)解距離解(Min)，所得最優(yōu)解距離解平均值(Avg)，實驗所得最優(yōu)解與算例最優(yōu)解誤差(DEV%)(DEV=(Min-BK)/BK)。

表2為本文使用的HH-RLDQN算法及文獻[29-32]對Set A標準算例的計算結(jié)果。表中加粗且標有“*”的數(shù)字表示求得當前算例最優(yōu)解。由表2可知，文獻中的LNS-ACO和SC-ESA兩種算法都求得27個算例中的17個算例的最優(yōu)解，求最優(yōu)解成功率為62.96%；HVNSOS算法求得20個最優(yōu)解，求解成功概率為74%；NHQEA算法求得23個最優(yōu)解，求解成功率為85.18%。本文算法求得22個最優(yōu)解，求解成功率為81.48%，相較于前兩種算法，提升18.52%，提升較為明顯，相較于第3種算法提升7.48%，具有一定優(yōu)勢，相較于第4種算法，僅低了3.7%。求得各算法對于該27個算例最優(yōu)解的誤差率平均值分別為：0.6%，0.16%，0.13%，0.07%，本文算法的誤差平均值為0.07%，相較于前3種算法降低了0.53%，0.09%，0.06%。值得一提的是，本文算法在低于NHQEA算法最優(yōu)值求解成功率的情況下，仍與其具有相同的誤差平均值。在求解n61,n64和n65這3個算例上，本文算法在本次實驗中相較于NHQEA算法，具有一定優(yōu)勢。對于20次實驗的最優(yōu)值平均值觀察可得，有8個算例平均值均達到算例最優(yōu)值，除n69和n80算例，平均值與算法所得最優(yōu)值相差為9和13，其他算例差值均在[1,6]之間，可見本文算法在此些算例中求解具有相對準確性。由此可得，本文算法相對于多種群搜索的其他4種算法而言，在Set A標準算例上，具有較好的搜索效果。

表2 CVRP Set A-標準算例測試

續(xù)表2

表3是本文使用的HH-RLDQN算法，及文獻[31-32]對Set E標準算例的計算結(jié)果，表中“～”表示文獻中并未給出計算值。由表3可知，LNS-ACO和SC-ESA兩種算法分別求得8個算例中的4和5個算例的最優(yōu)解，求最優(yōu)解成功率為50%和62.5%；本文算法求得9個算例中的5個算例最優(yōu)解，求最優(yōu)解成功率為55.56%，求最優(yōu)解成功率與兩種算法效果相同。求得兩種算法對于8個算例的最優(yōu)值平均誤差率為0.68%和0.63%，本文算法為0.32%，分別下降0.36%和0.31%，幾乎為一半，尤其在n76-k7和n76-k8算例上，誤差率僅為0.01%和0.03%，效果相較于兩種算法，極其優(yōu)秀。由以上數(shù)據(jù)可知，本文算法，在Set E-標準算例上相對于LNS-ACO和SC-ESA同樣具有較好搜索效果。

表3 CVRPSet E-標準算例測試

表4為本文使用的HH-RLDQN算法及文獻[29-32]對Set P標準算例的計算結(jié)果。由表4可知，除了SC-ESA算法整體搜索求解效果不是很理想，17個算例中，只求得6個，LNS-ACO，HVNSOS，NHQEA以及本文算法都具有較好的搜索求解效果。LNS-ACO，HVNSOS，NHQEA在17個算例中求得最優(yōu)解算例的個數(shù)分別為12,13和13個，求最優(yōu)解成功率分別為75%，76.47%和76.47%，本文算法求得最優(yōu)解算例個數(shù)為16個，求最優(yōu)解成功率高達94.12%，較3種算法提升近20%左右。本文未求得的算例n50-k10，NHQEA算法同樣未求到，且求得為同值697，差值僅為1，誤差率為0.14%。在平均誤差率上，由于本文算法就一例未求得，故僅為0.02%，相較于其他算法分別降低0.51%，0.65%，0.08%，0.02%。本文算法對表中前7個算例實驗中平均值求得算例最優(yōu)值，除n50-k8算例，其余算例與平均值差值范圍均為[1,6]，具有較強準確性。

表4 CVRP Set P-標準算例測試

圖4所示為本文算法在Set A/P標準算例實驗中所得平均值與最優(yōu)值偏差，對兩種類型的算例，平均值與所求得的最優(yōu)值之間相差幾乎不大，44個例子中，只有2例偏差在[10,15]之間，1例為30(原因為各車容量相對緊湊，造成實驗結(jié)果一直在最少車輛數(shù)為8和9之間交替出現(xiàn)，且當9輛車時最優(yōu)值甚至求得629，小于8輛車的最優(yōu)值，而出現(xiàn)8輛車的最優(yōu)值實驗結(jié)果742，遠大于實驗?zāi)繕俗顑?yōu)值)，其余全在[0,6]之間，充分反映了本文算法的求解穩(wěn)定性。

圖5所示為計算Set E客戶點數(shù)為50標準算例，所得的DQN神經(jīng)網(wǎng)絡(luò)收斂圖。縱坐標為網(wǎng)絡(luò)的均方誤差值，橫坐標為學習代數(shù)。在算法中設(shè)定，經(jīng)驗池刷新一定值后，才重新進入學習，因此橫坐標代數(shù)少于實際算法運行代數(shù)，由此導致在算法中，學習代數(shù)不多，最后收斂時，均方誤差為0.016 7，未達到穩(wěn)定狀態(tài)。且其中變異算子并非絕對優(yōu)化效果，即使在同樣的State值情況下，依舊可能會出現(xiàn)負優(yōu)化，造成樣本數(shù)據(jù)偏差，因此圖中曲線有起伏，但整體仍呈現(xiàn)下降趨勢，體現(xiàn)了較好的學習情況。均方誤差值逐漸減小，則DQN神經(jīng)網(wǎng)絡(luò)部分越接近真實，對底層算子性能的評價及其選擇也越準確，提升超啟發(fā)算法整體的搜索能力，算法的效果從之前的結(jié)果表、圖中已經(jīng)得到了體現(xiàn)。

通過上述3種標準算例的計算結(jié)果，可得本文所設(shè)計算法能在CVRP上得到了較好的效果，在保證能求得較多最優(yōu)值的情況下，多次實驗的平均值均接近最優(yōu)值，從而表明算法具有較強的搜索能力和穩(wěn)定性。通過與其他四種算法的對比表明，實驗總體效果優(yōu)于LNS-ACO算法和SC-ESA算法，較優(yōu)于HVNSOS算法，與NHQEA算法效果相當，但在小客戶點算例上，本文算法較NHQEA算法具有相對更好的搜索求解效果。

4 結(jié)束語

本文提出了一種基于強化學習的超啟發(fā)算法求解有容量車輛路徑問題。在初始種群的設(shè)計中，引入聚類思想，提升初始解的質(zhì)量。在超啟發(fā)算法高層策略設(shè)計中，引入強化學習中的DQN算法，結(jié)合Q學習算法的思想與神經(jīng)網(wǎng)絡(luò)算法的結(jié)構(gòu)，對底層算子在解的每個狀態(tài)下表現(xiàn)的性能進行評價，評分由立即獎懲和將來獎懲兩部分組成，同時利用模擬退火的接受準則以及序列池，對得出的非改進解有條件接受，引導算法跳出局部最優(yōu)情況，向優(yōu)質(zhì)解的空間持續(xù)搜索。

利用所提算法對CVRP三種標準算例進行實驗求解，將求解所得結(jié)果與目前最優(yōu)結(jié)果和文中所提4種其他算法所得結(jié)果相比較，通過最優(yōu)值、誤差率和平均值分析，驗證了本文算法在該問題的求解上具有相對準確性和穩(wěn)定性，總體求解效果優(yōu)于對比算法。

下一步的工作將嘗試采用該算法求解CVRP大規(guī)?？蛻酎c的問題及其衍生問題。同時，雖然本文算法在實驗求解中整體獲得不錯的效果，但在客戶規(guī)模較大的車輛路徑問題上，仍具有較大的改進空間，之后將繼續(xù)優(yōu)化其高層策略，爭取有所突破。