基于深度強化學(xué)習(xí)的車輛路徑問題求解方法

黃 琰，張 錦,2,3

（1.西南交通大學(xué)，交通運輸與物流學(xué)院，成都 611756；2.綜合交通運輸智能化國家地方聯(lián)合工程實驗室，成都 611756；3.綜合交通大數(shù)據(jù)應(yīng)用技術(shù)國家工程實驗室，成都 611756）

0 引 言

車輛路徑問題（Vehicle Routing Problem，VRP）于1959 年由Dantzig 和Ramser[1]提出并用于解決卡車調(diào)度問題，后被Lenstra 和Kan[2]證明是一種NP-hard 問題。作為交通運輸與物流領(lǐng)域最為經(jīng)典的組合運籌優(yōu)化問題，VRP 歷經(jīng)幾十年的研究和討論而經(jīng)久不衰。

基于現(xiàn)實情況，學(xué)者們將相關(guān)的約束條件添加到標準的VRP 中，設(shè)計了多種對應(yīng)的VRP 擴展問題。如帶時間窗的車輛路徑問題（Vehicle Routing Problems with Time Windows, VRPTW）、隨機服務(wù)的車輛路徑問題（Vehicle Routing Problem with Stochastic Travel and Service Time and Time Windows, VRPSTSTW）[3]、電動汽車車輛路徑問題[4-5]（Electric Vehicle Routing Problem,EVRP）、考慮增加車場數(shù)量的多車場車輛路徑問題[6]（Multidepot Vehicle Routing Problem, MDVRP）、帶時間窗和人力分配的車輛路徑問題[7]（Manpower Allocation and Vehicle Routing Problem with Time Windows, MAVRPTW）、考慮一致性約束的車輛路徑問 題[8]（Consistent Vehicle Routing Problem, Con-VRP）等，并被廣泛應(yīng)用于物流配送、醫(yī)療服務(wù)[7]以及消防、潛探、巡檢等特殊領(lǐng)域。較為常見的車輛路徑問題的應(yīng)用場景、特征和相關(guān)經(jīng)典文獻詳見文獻[9]。

車輛路徑問題的常規(guī)求解方法主要有精確算法、經(jīng)典啟發(fā)式算法和元啟發(fā)式算法[9-10]。目前，車輛路徑問題的傳統(tǒng)求解方法均能不同程度地適應(yīng)各類型的車輛路徑問題，但傳統(tǒng)求解方法通常針對具體模型和部分靜態(tài)進行建模和求解，并不具備自主學(xué)習(xí)和決策的能力。

深度強化學(xué)習(xí)是一種能夠?qū)崿F(xiàn)從原始輸入到輸出直接控制的人工智能方法[11]，設(shè)計的方法無需人工設(shè)計或推理，使得其自主解決車輛路徑問題，甚至未來自主改進至優(yōu)于傳統(tǒng)方法變得可能。在現(xiàn)代物流快速發(fā)展的基礎(chǔ)上，面對復(fù)雜、數(shù)據(jù)規(guī)模較大的車輛路徑規(guī)劃情景，應(yīng)當設(shè)計可信演化能力更強、算法柔性更大的人工智能方法，以適配實際的車輛路徑問題場景，有效支撐智慧物流的發(fā)展。

常見的深度強化學(xué)習(xí)方法包括深度Q 網(wǎng)絡(luò)方法（Deep Q-learning Networks, DQN）、演員-評論家方法（Actor-Critic,AC）、深度確定性策略梯度方法（Deep Deterministic Policy Gradient, DDPG）、近端策略梯度優(yōu)化方法（Proximal Policy Optimization，PPO）等。目前，深度強化學(xué)習(xí)在VRP 中的應(yīng)用是研究的熱點之一[10]，相關(guān)研究主要集中在采用逐一插入節(jié)點的方式構(gòu)造解的“端到端”深度強化學(xué)習(xí)方法和運用深度強化學(xué)習(xí)方法設(shè)計啟發(fā)式算法兩個方向。相關(guān)文獻運用方法及主要成果整理如表1所示。

表1 深度強化學(xué)習(xí)方法在車輛路徑問題中的應(yīng)用Tab.1 Application of deep reinforcement learning to vehicle routing problems

一方面，相關(guān)學(xué)者通過逐一插入節(jié)點的方式設(shè)計“端到端”輸出解的車輛路徑問題的深度強化學(xué)習(xí)方法。Nazari 等[12]受到TSP 旅行商問題的深度強化學(xué)習(xí)相關(guān)研究的啟示，結(jié)合車輛路徑問題的特性，通過改進指針網(wǎng)絡(luò)PtrNet 的編碼器，設(shè)計了適用于VRP 問題的深度強化學(xué)習(xí)方法。KOOL等[13]提出了AM 方法，引入注意力機制Attention并設(shè)定探索基線Rollout Baseline 用于修正強化學(xué)習(xí)的獎勵。Vera 等[14]基于深度強化學(xué)習(xí)在多智能體協(xié)作系統(tǒng)中的應(yīng)用，提出了解決固定車隊規(guī)模的多車輛路徑問題的深度強化學(xué)習(xí)方法，相比啟發(fā)式方法得到了較優(yōu)的實驗結(jié)果。Peng 等[15]在AM方法的基礎(chǔ)上引入動態(tài)注意力機制，相比文獻[13]將算法效率提升了20～40 倍。Bdeir 等[16]針對VRP設(shè)計編碼器并與DQN思想結(jié)合設(shè)計了RP-DQN方法，并證明在客戶數(shù)量為20、50、100 的CVRP(Capacitated Vehicle Routing Problem)上優(yōu)化效果均優(yōu)于文獻[12]和文獻[13]。ORENJ 等[17]提出運用圖神經(jīng)網(wǎng)絡(luò)表示VRP 的環(huán)境狀態(tài)，并設(shè)計了一種在線-離線學(xué)習(xí)相結(jié)合的方法。韓巖峰[18]提出了基于注意力機制和AC 算法框架的深度強化學(xué)習(xí)方法，并用于解決帶時間窗的無人物流車隊配送問題。

另一個研究方向則是運用深度強化學(xué)習(xí)方法針對特定車輛路徑問題設(shè)計啟發(fā)式算法。Chen[19]等將車輛路徑問題定義為序列到序列的問題，并運用指針網(wǎng)絡(luò)結(jié)合AC 方法設(shè)計啟發(fā)式算法NeuRewriter，并在實驗結(jié)果上優(yōu)于文獻[12]和[13]。LU 等[20]通過定義改進算子和干擾算子并結(jié)合深度強化學(xué)習(xí)方法構(gòu)建了啟發(fā)式算法L2I，首次在實驗結(jié)果上超過了專業(yè)求解器LKH3[21]。之后，Wu 等[22]運用自注意力機制結(jié)合REINFORCE 構(gòu)建了啟發(fā)式算法，通過對歷史解決方案離線學(xué)習(xí)取得了較好的實驗結(jié)果。Falkner 等[23]運用深度強化學(xué)習(xí)方法改進多個并行解決方案，設(shè)計了啟發(fā)式算法JAMPR，并應(yīng)用于CVRP 問題和VRPTW 問題。馮勤炳[24]設(shè)計了基于DQN的強化學(xué)習(xí)超啟發(fā)算法，實驗證明對比傳統(tǒng)方法有效減少了總成本，提升了算法魯棒性。Zhao 等[25]通過將深度強化學(xué)習(xí)方法與局部搜索算法相結(jié)合設(shè)計了啟發(fā)式算法，實驗結(jié)果較好，并將求解效率提升了5～40 倍。Gao 等[26]在大規(guī)模領(lǐng)域搜索算法框架下結(jié)合圖注意力神經(jīng)網(wǎng)絡(luò)GAT 和PPO 構(gòu)建了啟發(fā)式算法，將問題解決規(guī)模擴大至400個客戶服務(wù)點。

綜上，運用深度強化學(xué)習(xí)方法設(shè)計啟發(fā)式算法求解車輛路徑問題可以有效地提升求解的速度和效果，但該類模型較適用于求解固定環(huán)境和類型的車輛路徑問題。部分學(xué)者嘗試離線學(xué)習(xí)實例數(shù)據(jù)求解車輛路徑問題，該類實驗效果較好，但需要大量數(shù)據(jù)和算例作為輸入，一定程度上影響了算法的效率，降低了方法的實用性。許多學(xué)者致力于研究“端到端”的車輛路徑問題求解方法，該類方法能夠較好地針對不同約束條件的車輛路徑問題，但通常需要通過波束搜索、局部搜索等方式提升直接輸出解的質(zhì)量。Bdeir[16]等提出的RPDQN 方法，實驗結(jié)果在現(xiàn)有“端到端”方法中表現(xiàn)較優(yōu)，但由于DQN 方法的動作選擇方式，尚存在值函數(shù)過估計、探索局限等問題，該問題將在后文詳細說明并改進。同時，并未有學(xué)者系統(tǒng)性地對車輛路徑問題強化學(xué)習(xí)決策過程進行詳細設(shè)計。

本文針對CVRP 設(shè)計了“端到端”輸出解的車輛路徑問題的深度強化學(xué)習(xí)方法，其主要貢獻如下：

（1）提出了一種基于上置信區(qū)間算法（Upper Confidence Bound Apply to Tree,UCT）改進策略選擇的DQN 方法，通過平衡智能體對策略的利用與探索，解決現(xiàn)行方法探索局限的問題，提升方法的效果。

（2）針對CVRP，系統(tǒng)性地設(shè)計了車輛路徑問題場景下的強化學(xué)習(xí)決策過程，并設(shè)計了車輛路徑問題場景下的狀態(tài)-動作空間、獎勵函數(shù)、策略選擇方式等決策過程要素。

1 問題與目標

1.1 問題描述

CVRP 即對每一個服務(wù)的車輛都有裝載能力約束的車輛路徑問題，由一組W輛具有裝載能力為cw的車輛，對一系列分布在地理上不同位置的L個顧客進行服務(wù)，每個需求點只能由一輛車服務(wù)且每個車輛的路線開始于車場，完成服務(wù)后回到車場。

1.2 優(yōu)化目標

深度強化學(xué)習(xí)是通過環(huán)境與智能體的不斷交互，修正不同狀態(tài)下的動作選擇，最終輸出一系列較優(yōu)動作的過程。為了達到最終期望的結(jié)果，需要通過設(shè)置一個優(yōu)化目標來更好地引導(dǎo)智能體。

參考本文研究的CVRP 傳統(tǒng)模型中的目標函數(shù)設(shè)定優(yōu)化目標：在滿足車輛裝載約束的基礎(chǔ)上，考慮車輛行駛距離總和最短，如下所示：

2 傳統(tǒng)深度Q網(wǎng)絡(luò)方法

深度Q 網(wǎng)絡(luò)[27-28]是在Q-learning 的基礎(chǔ)上，構(gòu)建一個參數(shù)為Φ的深度神經(jīng)網(wǎng)絡(luò)代替Q-learning的Q值表，并通過智能體與環(huán)境不斷交互更新函數(shù)參數(shù)，使得函數(shù)Q?(s,a)可以逼近現(xiàn)實的狀態(tài)動作值函數(shù)Qπ(s,a)，該過程為：

式中：s′為下一個狀態(tài)s′的向量表示；a′為下一個動作a′的向量表示。

函數(shù)Q?(s,a)與Qπ(s,a)之間的誤差，可表示為損失函數(shù)：

函數(shù)Q?(s,a)逼近Qπ(s,a)的過程就是損失函數(shù)不斷梯度下降的過程。

2.1 值函數(shù)網(wǎng)絡(luò)設(shè)計

本文參考Kool等[13]設(shè)計的基于Transformer框架的注意力模型以及Bdeir等[16]提出的RP-DQN方法，設(shè)計了值函數(shù)網(wǎng)絡(luò)。網(wǎng)絡(luò)結(jié)構(gòu)為基于Transformer 框架的注意力網(wǎng)絡(luò)，主要組件包括輸入層、解碼器、編碼器和輸出層。

值函數(shù)網(wǎng)絡(luò)整體結(jié)構(gòu)如圖1所示，具體細節(jié)詳見文獻[13]和[16]。

圖1 深度Q網(wǎng)絡(luò)值函數(shù)網(wǎng)絡(luò)結(jié)構(gòu)示意圖Fig.1 Structure of value function network of Deep Q-learning Networks

這些節(jié)點嵌入通過N個串聯(lián)的注意力模塊（Attention Blocks,AB）進行傳導(dǎo)和更新，每個注意力模塊由一個多頭自注意力層（Multi-Head Self-Attention Layer, MHA）和一個全連接的前饋層（Feedforward Layer, FF）組成，激活函數(shù)為ReLU函數(shù)，每層MHA 與FF 之間通過殘差連接和批量歸一化處理（Batch Normalization, BN）連接而成，并允許信息傳遞時跳過連接。

2.1.2 解碼器

解碼器由1個MHA 和1個單頭注意力層（Single-Head Attention,SHA）組成。

解碼器每一時刻t的輸入是當前時刻由編碼

式中：u0為選擇訪問車場輸出的q值；ui為選擇訪問節(jié)點i輸出的q值；w?i,t為t時刻節(jié)點i的剩余需求；c?t為t時刻節(jié)點i的車輛的剩余裝載量。

其中，式（8）表示車場不允許被連續(xù)訪問；式（9）表示需求大于車輛剩余裝載的節(jié)點和已被服務(wù)過的節(jié)點（剩余需求為0）不允許被訪問。掩碼M的規(guī)則設(shè)定能夠很好地反映VRP 問題的約束條件。本文僅針對CVRP設(shè)計了掩碼的規(guī)則，相關(guān)學(xué)者可通過增加掩碼M規(guī)則將該方法拓展至各類車輛路徑問題。

式中：dk為維度系數(shù)，用于平衡各節(jié)點之間的數(shù)量級，通常取64；W k和W q分別表示節(jié)點狀態(tài)特征和節(jié)點嵌入權(quán)重向量。

2.2 車輛路徑問題的決策過程

深度強化學(xué)習(xí)的決策過程為馬爾科夫決策過程（Markov Decision Process，MDP）具有馬爾科夫性，即一個隨機過程其未來狀態(tài)的條件概率分布僅依賴于當前狀態(tài)，與之前任意時刻無關(guān)。在CVRP問題中，可將求解的過程視作車輛在某時刻與環(huán)境進行交互的過程，這個過程是一個離散動作空間。在僅考慮統(tǒng)一車型且不考慮時間窗的情況下，模型中w輛車可視為一輛車取貨w次的過程，雖然該過程的每一個決策之間并不存在實際的時間順序，但決策過程依舊僅依賴當前的狀態(tài)，具有馬爾科夫性，故這個過程可以視為半馬爾科夫決策過程。

在這個虛擬的過程中，存在一個智能體即車輛，車輛從起點出發(fā)選擇一個動作a1，由外部環(huán)境給予一個即時的獎勵r，同時環(huán)境根據(jù)動作更改成狀態(tài)s1，這個過程不斷交互，直到所有顧客服務(wù)完畢，此時返回所有獎勵的和。

智能體與環(huán)境交互做出動作的最終目標是達到期望累計獎勵最大，可以表示為：

2.2.2 獎勵函數(shù)

獎勵函數(shù)的設(shè)定直接決定了強化學(xué)習(xí)方法的收斂性和優(yōu)化方向，結(jié)合CVRP問題的相關(guān)約束條件以及式（1）關(guān)于本文優(yōu)化目標的定義，本文定義了智能體每次做出決策，環(huán)境給予該決策對應(yīng)顧客之間距離倒數(shù)的正獎勵如下所示：

式中：rt表示t時刻的獎勵。

3 基于UCT改進的DQN

3.1 傳統(tǒng)DQN的問題

深度Q 網(wǎng)絡(luò)存在對于Q 值過估計的問題。由公式（2）可知，DQN網(wǎng)絡(luò)訓(xùn)練過程是通過近似估計一個函數(shù)逼近現(xiàn)實的狀態(tài)動作值函數(shù)的過程。由于初始狀態(tài)未知以及原始參數(shù)的設(shè)定，會導(dǎo)致這個過程的開始對于函數(shù)的估計產(chǎn)生偏差。而由于深度Q 網(wǎng)絡(luò)選擇執(zhí)行的是Q 估計值最大的動作，因此過高估計的動作被選擇的概率較大；深度Q網(wǎng)絡(luò)目標網(wǎng)絡(luò)凍結(jié)的機制，也會導(dǎo)致其不斷放大值的過大估計，導(dǎo)致最終結(jié)果出現(xiàn)偏差。

同時，由于DQN 選擇執(zhí)行的是Q 估計值最大的動作，智能體每次進行交互的軌跡是一致的，對于未選擇動作的探索程度較小，僅是對已經(jīng)確定的策略進行利用，而非對環(huán)境進行探索，難以覆蓋所有的狀態(tài)和動作。若單純使用深度Q 網(wǎng)絡(luò)會導(dǎo)致陷入局部最優(yōu)，不利于最優(yōu)策略的選取，方法的收斂性和穩(wěn)定性較差。

3.2 方法改進

本文通過結(jié)合UCT 算法改進DQN 中的動作選擇方式以改進DQN的過估計和探索局限問題。

UCT 算法是蒙特卡洛樹搜索算法（MCTS）的一個拓展，MCTS 作為一種經(jīng)典啟發(fā)式搜索算法，最早由Kocsis 等[29]在2006 年提出，UCT 算法是在MCTS 的基礎(chǔ)上，將上置信區(qū)間UCB 值引入MCTS用于算法決策值的計算，被廣泛應(yīng)用于搜索空間較大的決策過程或象棋、圍棋游戲的AI 程序中，如Alpha Go等。

強化學(xué)習(xí)的本質(zhì)是通過不斷探索環(huán)境并充分利用探索的經(jīng)驗進行控制與決策的過程[30]。傳統(tǒng)DQN方法在解決環(huán)境的探索與利用平衡問題時是通過ε-greedy策略，通過調(diào)整貪婪和隨機的概率對環(huán)境進行充分探索。

但由于ε-greedy策略是隨機無向的探索，在小規(guī)模的簡單問題中尚能進行。但面對較為復(fù)雜的問題，特別是VRP問題，要求每個節(jié)點顧客必須得到服務(wù)，因此對每個節(jié)點的特征進行探索是必要的。這種隨機無向的探索數(shù)據(jù)利用率較低，難以保證在短時間內(nèi)對所有節(jié)點特征進行探索。UCT算法則很好地解決了這個問題，UCT 算法定義了一個上置信區(qū)間值UCB為：

具體到本文的改進，是將DQN 算法中智能體做動作選擇時選擇輸出最大q值動作的策略，改為選取k個較大q值的節(jié)點并向下遍歷計算其葉節(jié)點的qUCB值，輸出qUCB值最大的節(jié)點動作。值得一提的是q值的輸出借鑒了Hasselt[31]等設(shè)計的DQN改進方法，為Q 估計與Q 現(xiàn)實中較小的數(shù)值，以此可以減少DQN 的過估計問題。動作a的qUCB值可表示為qUCB(a)，表達式如下：

改進后的方法流程如圖2所示，細節(jié)及具體描述如下。

圖2 基于UCT改進動作選擇的DQN方法流程圖Fig.2 Flow diagram of DQN method for improved policy decision-making based on UCT

步驟1 初始化虛擬狀態(tài)環(huán)境。

步驟2 初始化經(jīng)驗池、動作價值函數(shù)Q 網(wǎng)絡(luò)、對照動作價值函數(shù)Q 網(wǎng)絡(luò)、決策樹估計函數(shù)；設(shè)定參數(shù)：經(jīng)驗池容量N、最大訓(xùn)練迭代步數(shù)M、折扣率γ、學(xué)習(xí)率α、Adam 函數(shù)參數(shù)β1 和β2、Q 網(wǎng)絡(luò)參數(shù)Φ、對照Q 網(wǎng)絡(luò)參數(shù)Φ′、更新間隔C、貪婪概率ε、修剪參數(shù)k、狀態(tài)訪問次數(shù)ns、動作狀態(tài)訪問次數(shù)nsa。

步驟3 有ε概率輸出隨機動作；否則，判斷是否首次訪問節(jié)點，即ns(s)=0。若是，則輸出當前q值最高動作，ai=argamax(q[a])；若不是，則輸出k個節(jié)點中qUCB值最大的動作，ai=argamax(qUCB[a])。

步驟4 執(zhí)行步驟3中選擇的動作，環(huán)境依據(jù)動作給予式（5）和式（6）的即時獎勵ri，并更新得到新的環(huán)境狀態(tài)xi+1。

步驟5 更新經(jīng)驗池和決策樹。當經(jīng)驗池飽和時，從經(jīng)驗池的最底端進行新的數(shù)據(jù)替換。

步驟6 從經(jīng)驗池中隨機采樣并代入式（9）計算損失函數(shù)梯度下降訓(xùn)練Q網(wǎng)絡(luò)，每隔C步更新對照Q網(wǎng)絡(luò)參數(shù)。

步驟7 判斷是否符合訓(xùn)練終止條件，進入步驟8；否則，返回步驟3。

步驟8 輸出結(jié)果。

改進的DQN框架示意圖詳見圖3。

圖3 基于UCT改進動作選擇的DQN框架示意圖Fig.3 Framework schematic diagram of DQN method for improved policy decision-making based on UCT

4 實驗分析

4.1 實驗參數(shù)敏感度分析和選擇

本文選取的實驗參數(shù)敏感度測試數(shù)據(jù)集來自Augerat[32]1995 年提出的Set A 數(shù)據(jù)測試集中的An32-k5 號數(shù)據(jù)集。該數(shù)據(jù)集共有31 個需求點、載具裝載限制為100、載具數(shù)量限制為5 輛，車場坐標、服務(wù)點坐標和需求量如表2 所示，其中序號1為起終點，其余為需求點。

表2 實驗參數(shù)敏感度測試環(huán)境信息Tab.2 Environmental information for sensitivity testing of experimental parameters

依據(jù)上述數(shù)據(jù)，本文在gym 中創(chuàng)建了一個100*100 的網(wǎng)格作為本文方法參數(shù)敏感性實驗的虛擬環(huán)境，將數(shù)據(jù)集數(shù)據(jù)映射到虛擬環(huán)境中。

為測試本文方法在不同參數(shù)下的表現(xiàn)以便選擇較優(yōu)的參數(shù)進行最終的實例求解，本文對深度Q網(wǎng)絡(luò)中敏感度較高、能夠顯著影響訓(xùn)練效果的參數(shù)（經(jīng)驗池容量N、UCT 修剪數(shù)、對照動作價值網(wǎng)絡(luò)更新間隔C、折扣率γ和學(xué)習(xí)率α）進行敏感性分析。其中，經(jīng)驗池容量N、UCT 修剪數(shù)、對照動作價值網(wǎng)絡(luò)更新間隔C并未對算法收斂和累計獎勵結(jié)果變化造成顯著的影響，因此本文對變化較為顯著的折扣率γ和學(xué)習(xí)率α進行詳細分析。

為更好地展示算法訓(xùn)練效果和變化情況，本文通過把每100 個訓(xùn)練匯合所得獎勵求平均的方式將10 000 次迭代等效處理為100 個趨勢點用于累計獎勵變化趨勢圖的繪制。

4.1.1 折扣率的分析與選擇

在其他參數(shù)不變的情況下，分別對折扣率γ取0.7、0.9 和0.99 的情況進行模擬，迭代10 000 次后累計獎勵值變化趨勢如圖4所示。

圖4 不同折扣率下累計獎勵隨迭代次數(shù)變化情況示意圖Fig.4 Variation in rewards with number of iterations under different γ

由圖4 可得，折扣率γ的調(diào)整顯著影響了累計獎勵的變化與收斂情況。γ取較大值0.99 時，由于對以往經(jīng)驗過于關(guān)注，導(dǎo)致最終累計獎勵值未能更好地趨近最優(yōu)值；而當γ為0.7 時，過小的折扣率導(dǎo)致未能很好地學(xué)習(xí)過去較好的動作選擇，最終未在設(shè)定迭代步數(shù)內(nèi)完成收斂。

4.1.2 學(xué)習(xí)率的分析與選擇

在其他參數(shù)不變的情況下，分別對學(xué)習(xí)率α取0.005、0.05 和0.001 的情況進行模擬，迭代10 000次后累計獎勵值變化趨勢如圖5所示。

圖5 不同學(xué)習(xí)率下累計獎勵隨迭代次數(shù)變化情況示意圖Fig.5 Variation in rewards with number of iterations under different α

由圖5 看出，學(xué)習(xí)率α的調(diào)整影響了累計獎勵的收斂速度和穩(wěn)定性。α取0.05 和0.005 時，由于學(xué)習(xí)率過大導(dǎo)致較快出現(xiàn)收斂趨勢，但未能學(xué)習(xí)到最優(yōu)策略導(dǎo)致后續(xù)逐步出現(xiàn)震蕩；當α取值為0.001時，累計獎勵平穩(wěn)上升并有較好的收斂性。

4.2 實驗環(huán)境設(shè)置

為了更好地與其他深度強化學(xué)習(xí)方法進行對比，本文在文獻[12]定義的車輛路徑問題環(huán)境下進行實驗，該環(huán)境自提出以來被用于測試國內(nèi)外各類深度強化學(xué)習(xí)方法[12-20,22,23,25,26]在車輛路徑問題場景下的性能。實驗假設(shè)節(jié)點位置和需求是從固定分布隨機生成的，具體來說，客戶和車場位置是從1×1的單位方格中隨機生成的，每個節(jié)點的需求在[0,10]中隨機選擇。此處為模擬真實需求，遵循了文獻[13]的設(shè)定將需求值定義為離散的正整數(shù)。針對智能體行為設(shè)置，本文假設(shè)車輛在時間0時位于車場，在每次交互過程中，車輛從客戶節(jié)點或倉庫中進行選擇，以便下一步訪問，直至所有節(jié)點訪問結(jié)束，返回車場。

本文將分別對比20、50、100 三個問題規(guī)模下的CVRP 問題，以下分別簡稱為CVRP-20、CVRP-50 和CVRP-100，相應(yīng)規(guī)模下的額定載重分別為30、40 和50。通過在每個數(shù)據(jù)規(guī)模下隨機生成1 000個實例，并且每個實例只使用一次，通過計算平均成本對比實驗結(jié)果。

基于上述實驗設(shè)置本文在Intel(R) Core(TM)i7-4720HQCPU@2.60 GHz、RAM 16.0 GB電腦上使用Python 語言，采用Tensorflow 框架在Jupyter Notebook中實現(xiàn)設(shè)計的基于UCT改進動作選擇的DQN 算法。在參數(shù)敏感性分析的基礎(chǔ)上，實驗參數(shù)設(shè)置如表3所示。

表3 實驗參數(shù)設(shè)置Tab.3 Experimental parameter settings

4.3 方法有效性分析

為反映UCT-DQN 的學(xué)習(xí)過程和收斂情況并直觀地與RP-DQN[16]進行對比，本文將各數(shù)據(jù)規(guī)模上兩種方法的獎勵及優(yōu)化目標變化情況進行了繪制，如圖6所示。其中，優(yōu)化目標依據(jù)公式（1）為車輛行駛總距離的成本，成本越低，實驗效果越優(yōu)。同時，為加強實驗結(jié)果的可讀性，本文通過每20步取平均值的方式對獎勵和優(yōu)化目標值進行了平滑處理。

由圖6可以看出，兩者都是標準的深度強化學(xué)習(xí)曲線。智能體獲取的獎勵值曲線波動上升，說明智能體根據(jù)學(xué)習(xí)情況，逐步調(diào)整動作選擇策略。訓(xùn)練初期由于Q值的估計準確性較低導(dǎo)致曲線波動較大，隨著訓(xùn)練次數(shù)的增加，逐步學(xué)習(xí)到了較好的策略，波動逐步趨于穩(wěn)定，說明兩種深度強化學(xué)習(xí)方法均具有較好的收斂性和準確性。

圖6 各規(guī)模環(huán)境獎勵及優(yōu)化目標隨訓(xùn)練過程變化情況示意圖Fig.6 Variation in rewards and optimization objectives with training process in various environments

對比兩種方法，在CVRP-20 中，由于實驗規(guī)模較小，兩種方法均較快地探索到較好的解決方案，并 很 快 收 斂；在CVRP-50 和CVRP-100 中，RPDQN 方法雖較快呈現(xiàn)出收斂趨勢，但由于探索局限和過估計問題，過分依賴已探索的動作策略，導(dǎo)致最終收斂的值尚有一定的提升空間。本文的UCT-DQN 方法，雖收斂趨勢較為緩慢，但在三個問題規(guī)模中最終都獲得了較高的獎勵和較低的成本。通過統(tǒng)計分析，本文方法在CVRP-20、CVRP-50 和CVRP-100 三個規(guī)模中的平均成本分別為6.24、10.80 和16.23，對比RP-DQN 方法分別提升了1.89%、1.10% 和2.17%，取得了較好的實驗結(jié)果。

本文所提方法對比RP-DQN 方法雖收斂時間較長，但實際應(yīng)用環(huán)境下，依托GPU 服務(wù)器、高性能計算機或超算平臺等，本文的方法可以快速輸出較高質(zhì)量的可行解或作為優(yōu)秀的初始解用于啟發(fā)式算法、求解器等。

將本文方法所得結(jié)果進一步與專業(yè)求解器OR Tools、Gurobi、LKH3、啟發(fā)式算法節(jié)約里程法CW、掃描算法SW 以及其他“端到端”的深度強化學(xué)習(xí)方法結(jié)果進行對比，結(jié)果整理如表4所示。其中，本文以每個數(shù)據(jù)規(guī)模下的最優(yōu)結(jié)果為基線，對比其他方法和求解器與其的成本偏差，偏差率值越小，方法所得結(jié)果越優(yōu)。

由表4 可以看出，本文所提方法在CVRP-20中平均成本僅高于求解器Gurbi、LKH3 以及文獻[17]的SOLO 的在線學(xué)習(xí)方法，與上述三種方法相比，本方法的耗時較短，能夠一定程度上提升運算效率；在CVRP-50 問題中，實驗結(jié)果略遜于LKH3以及文獻[15]的AM-D方法；在CVRP-100問題中，實驗結(jié)果相比LKH3 求解器有3.71%的成本誤差，但優(yōu)于其他所有“端到端”的深度強化學(xué)習(xí)和啟發(fā)式算法。實驗結(jié)果顯示，在充分訓(xùn)練的基礎(chǔ)上，隨著問題規(guī)模的擴大，本文所提方法性能優(yōu)勢逐步顯示，且相比LKH3 求解器雖有較小誤差，但能較好地提升求解效率，說明該方法有較好的應(yīng)用前景。

表4 實驗結(jié)果對比Tab.4 Comparison of experimental results

5 結(jié)束語

本文提出一種基于UCT算法改進動作選擇方式的DQN 方法。所提出的深度強化學(xué)習(xí)方法用于車輛路徑規(guī)劃場景，通過智能體與虛擬環(huán)境交互獲得獎勵尋求行駛距離最短的動作組合策略，“端到端”解決了考慮車輛裝載限制約束的車輛路徑問題。實驗結(jié)果表明，本方法能夠得出與專業(yè)求解器質(zhì)量相當?shù)慕?。所提算法在充分?xùn)練的基礎(chǔ)上，能切實提高車輛路徑問題的求解效率，未來在實際應(yīng)用領(lǐng)域更具可行性。下一步工作，將考慮群智感知環(huán)境下DQN 的可信演化問題，結(jié)合企業(yè)實際進一步驗證模型的場景實用性；同時，將本文方法運用在其他約束條件或更大規(guī)模的車輛路徑問題也是本文的下一步工作之一。