黃 琰，張 錦,2,3

（1.西南交通大學，交通運輸與物流學院，成都 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)實情況，學者們將相關(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)進行建模和求解，并不具備自主學習和決策的能力。

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

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

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

一方面，相關(guān)學者通過逐一插入節(jié)點的方式設(shè)計“端到端”輸出解的車輛路徑問題的深度強化學習方法。Nazari 等[12]受到TSP 旅行商問題的深度強化學習相關(guān)研究的啟示，結(jié)合車輛路徑問題的特性，通過改進指針網(wǎng)絡(luò)PtrNet 的編碼器，設(shè)計了適用于VRP 問題的深度強化學習方法。KOOL等[13]提出了AM 方法，引入注意力機制Attention并設(shè)定探索基線Rollout Baseline 用于修正強化學習的獎勵。Vera 等[14]基于深度強化學習在多智能體協(xié)作系統(tǒng)中的應(yīng)用，提出了解決固定車隊規(guī)模的多車輛路徑問題的深度強化學習方法，相比啟發(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è)計了一種在線-離線學習相結(jié)合的方法。韓巖峰[18]提出了基于注意力機制和AC 算法框架的深度強化學習方法，并用于解決帶時間窗的無人物流車隊配送問題。

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

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

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

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

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

1 問題與目標

1.1 問題描述

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

1.2 優(yōu)化目標

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

參考本文研究的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）進行傳導和更新，每個注意力模塊由一個多頭自注意力層（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)學者可通過增加掩碼M規(guī)則將該方法拓展至各類車輛路徑問題。

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

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

深度強化學習的決策過程為馬爾科夫決策過程（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è)定直接決定了強化學習方法的收斂性和優(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ò)訓練過程是通過近似估計一個函數(shù)逼近現(xiàn)實的狀態(tài)動作值函數(shù)的過程。由于初始狀態(tài)未知以及原始參數(shù)的設(shè)定，會導致這個過程的開始對于函數(shù)的估計產(chǎn)生偏差。而由于深度Q 網(wǎng)絡(luò)選擇執(zhí)行的是Q 估計值最大的動作，因此過高估計的動作被選擇的概率較大；深度Q網(wǎng)絡(luò)目標網(wǎng)絡(luò)凍結(jié)的機制，也會導致其不斷放大值的過大估計，導致最終結(jié)果出現(xiàn)偏差。

同時，由于DQN 選擇執(zhí)行的是Q 估計值最大的動作，智能體每次進行交互的軌跡是一致的，對于未選擇動作的探索程度較小，僅是對已經(jīng)確定的策略進行利用，而非對環(huán)境進行探索，難以覆蓋所有的狀態(tài)和動作。若單純使用深度Q 網(wǎng)絡(luò)會導致陷入局部最優(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等。

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

但由于ε-greedy策略是隨機無向的探索，在小規(guī)模的簡單問題中尚能進行。但面對較為復雜的問題，特別是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、最大訓練迭代步數(shù)M、折扣率γ、學習率α、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ù)梯度下降訓練Q網(wǎng)絡(luò)，每隔C步更新對照Q網(wǎng)絡(luò)參數(shù)。

步驟7 判斷是否符合訓練終止條件，進入步驟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ò)中敏感度較高、能夠顯著影響訓練效果的參數(shù)（經(jīng)驗池容量N、UCT 修剪數(shù)、對照動作價值網(wǎng)絡(luò)更新間隔C、折扣率γ和學習率α）進行敏感性分析。其中，經(jīng)驗池容量N、UCT 修剪數(shù)、對照動作價值網(wǎng)絡(luò)更新間隔C并未對算法收斂和累計獎勵結(jié)果變化造成顯著的影響，因此本文對變化較為顯著的折扣率γ和學習率α進行詳細分析。

為更好地展示算法訓練效果和變化情況，本文通過把每100 個訓練匯合所得獎勵求平均的方式將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)注，導致最終累計獎勵值未能更好地趨近最優(yōu)值；而當γ為0.7 時，過小的折扣率導致未能很好地學習過去較好的動作選擇，最終未在設(shè)定迭代步數(shù)內(nèi)完成收斂。

4.1.2 學習率的分析與選擇

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

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

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

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

為了更好地與其他深度強化學習方法進行對比，本文在文獻[12]定義的車輛路徑問題環(huán)境下進行實驗，該環(huán)境自提出以來被用于測試國內(nèi)外各類深度強化學習方法[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 的學習過程和收斂情況并直觀地與RP-DQN[16]進行對比，本文將各數(shù)據(jù)規(guī)模上兩種方法的獎勵及優(yōu)化目標變化情況進行了繪制，如圖6所示。其中，優(yōu)化目標依據(jù)公式（1）為車輛行駛總距離的成本，成本越低，實驗效果越優(yōu)。同時，為加強實驗結(jié)果的可讀性，本文通過每20步取平均值的方式對獎勵和優(yōu)化目標值進行了平滑處理。

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

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

對比兩種方法，在CVRP-20 中，由于實驗規(guī)模較小，兩種方法均較快地探索到較好的解決方案，并 很 快 收 斂；在CVRP-50 和CVRP-100 中，RPDQN 方法雖較快呈現(xiàn)出收斂趨勢，但由于探索局限和過估計問題，過分依賴已探索的動作策略，導致最終收斂的值尚有一定的提升空間。本文的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 以及其他“端到端”的深度強化學習方法結(jié)果進行對比，結(jié)果整理如表4所示。其中，本文以每個數(shù)據(jù)規(guī)模下的最優(yōu)結(jié)果為基線，對比其他方法和求解器與其的成本偏差，偏差率值越小，方法所得結(jié)果越優(yōu)。

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

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

5 結(jié)束語

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