摘 要：如何在客戶規(guī)定的時間內(nèi)合理安排車輛運輸路線，一直是物流領(lǐng)域亟待解決的問題?；诖?，文章提出使用基于軟更新策略的決斗雙重深度Q網(wǎng)絡(luò)（Dueling Double Deep Q-network， D3QN），設(shè)計動作空間、狀態(tài)空間與獎勵函數(shù)，對帶時間窗的綠色車輛路徑問題進行建模與求解。選擇了小、中、大規(guī)模的總計18個算例，將三種算法的實驗結(jié)果在平均獎勵、平均調(diào)度車輛數(shù)、平均里程和運算時間四個維度進行比較。實驗結(jié)果表明：在大多數(shù)算例中，與Double DQN和Dueling DQN相比，D3QN能在可接受的增加時間范圍內(nèi)，獲得更高的獎勵函數(shù)，調(diào)度更少的車輛數(shù)，運輸更短的里程，實現(xiàn)綠色調(diào)度的目標(biāo)。

關(guān)鍵詞：深度強化學(xué)習(xí)；路徑優(yōu)化；決斗雙重深度Q網(wǎng)絡(luò)；D3QN算法；車輛路徑問題

中圖分類號：U116.2 文獻標(biāo)志碼：A DOI：10.13714/j.cnki.1002-3100.2024.19.017

Abstract： How to reasonably arrange vehicle transportation routes within the time specified by customers has always been an urgent problem in the field of logistics. Based on this， this paper proposes to use Dueling Double Deep Q-network（D3QN）based on soft update strategy to design action space， state space and reward function to model and solve the green vehicle routing problem with time window. A total of 18 small， medium and large scale examples are selected， and the experimental results of the three algorithms are compared in four dimensions： Average reward， average number of scheduled vehicles， average mileage and operation time. The experimental results show that， in most examples， compared with Double DQN and Dueling DQN， D3QN can obtain higher reward function， dispatch fewer vehicles， transport shorter mileage， and achieve the goal of green dispatch within the range of acceptable increase in time.

Key words： deep reinforcement learning; path optimization; Dueling Double Deep Q network; D3QN algorithm; vehicle routing problem

0 引 言

帶時間窗的車輛路徑問題（Vehicle Routing Problems with Time Windows，VRPTW）是指在時間窗口約束下，將一定數(shù)量的配送或服務(wù)點分配給若干個車輛，使得所有配送或服務(wù)點被訪問一次，并滿足各車輛容量約束條件的配送路徑問題。VRPTW問題最早可以追溯到20世紀(jì)70年代末和80年代初，它通常基于圖論建立數(shù)學(xué)模型，是一個典型的NP-hard問題。

隨著計算機算力的提升，深度學(xué)習(xí)算法逐步用于解決實際問題。2013年，Mnih et al.[1]首次提出了深度Q網(wǎng)絡(luò)（Deep Q

-network）模型，該模型是一個卷積神經(jīng)網(wǎng)絡(luò)，用Q學(xué)習(xí)的變體訓(xùn)練，成功地直接從高維感覺輸入中學(xué)習(xí)控制策略。2016年，Silver et al.[2]將深度強化學(xué)習(xí)算法運用到圍棋游戲中，并且引入了蒙特卡洛樹搜索法。在此算法的基礎(chǔ)上，他們編寫了程序AlphaGo。同年3月，AlphaGo以4比1的總比分戰(zhàn)勝了圍棋世界冠軍李世石，成為第一個直接擊敗人類選手的人工智能機器人。由于傳統(tǒng)的Q學(xué)習(xí)算法在某些情況下會高估動作值，從而使得整體的決策無法達到最優(yōu)，Hasselt et al.[3]提出了深度雙Q網(wǎng)絡(luò)（Double DQN， DDQN）算法。Wang et al.[4]提出了對決深度Q網(wǎng)絡(luò)（Dueling DQN）算法，這種算法能夠更準(zhǔn)確地估計狀態(tài)的價值，區(qū)分不同動作的重要性。

強化學(xué)習(xí)的經(jīng)典算法包括深度Q網(wǎng)絡(luò)，在此基礎(chǔ)上又衍生出了深度雙Q網(wǎng)絡(luò)，決斗深度Q網(wǎng)絡(luò)和決斗雙重深度Q網(wǎng)絡(luò)等。決斗雙重深度Q網(wǎng)絡(luò)作為前兩者算法的演化與升級，在其他領(lǐng)域取得了優(yōu)于前二者算法的表現(xiàn)。袁帥等[5]借助帶經(jīng)驗回放機制的D3QN算法，實現(xiàn)移動機器人在未知環(huán)境中更好地獲取最優(yōu)路徑。在收斂速度方面，相比DQN提升了56%。韓磊等[6]使用改進的D3QN算法，提升了可變限速控制策略的靈活性。此外，也有學(xué)者將強化學(xué)習(xí)的方法運用到經(jīng)典的路徑優(yōu)化問題中。Kool et al.[7]使用借助基于注意力機制和指針網(wǎng)絡(luò)的強化學(xué)習(xí)解決旅行社問題，其結(jié)果接近其他專業(yè)算法。Nazari et al.[8]提出了一個端到端的強化學(xué)習(xí)框架來解決車輛路徑問題，該模型僅通過觀察獎勵信號并遵循可行性規(guī)則，就可以從給定分布中采樣問題實例找到接近最優(yōu)的解決方案。其計算質(zhì)量優(yōu)于經(jīng)典的啟發(fā)式方法和Google的OR-Tools，并且計算時間相當(dāng)。Lin et al.[9]運用深度強化學(xué)習(xí)研究電動汽車車隊的路徑優(yōu)化問題，所提出的模型能夠有效解決現(xiàn)有方法難以求解的大規(guī)模調(diào)度問題。

帶時間窗的車輛路徑問題作為一個經(jīng)典的物流領(lǐng)域調(diào)度規(guī)劃問題，不少學(xué)者使用精確式算法、近似算法對該問題及其變種問題進行建模和求解。隨著環(huán)保理念的深入，學(xué)者們對考慮環(huán)境影響、碳排放的車輛路徑優(yōu)化問題也逐漸深入，車輛路徑優(yōu)化問題逐漸向著綠色調(diào)度的方向發(fā)展。

此外，隨著人工智能技術(shù)的發(fā)展，強化學(xué)習(xí)的方法逐步運用到路徑優(yōu)化問題的求解中，并且取得了一定的成效。以往的研究往往借助基礎(chǔ)的深度Q網(wǎng)絡(luò)，對VRPTW問題進行求解，該方法容易造成對Q值的高估，從而降低訓(xùn)練的質(zhì)量。雙重深度Q網(wǎng)絡(luò)算法作為一種新興的算法，在解決此類問題上仍然有較大的潛力。傳統(tǒng)的深度Q網(wǎng)絡(luò)使用的是硬更新的方式對目標(biāo)網(wǎng)絡(luò)進行更新。本文運用了基于策略的深度強化學(xué)習(xí)方法中的參數(shù)更新方式，使用基于軟更新策略的決斗雙重深度Q網(wǎng)絡(luò)算法，定義狀態(tài)空間、動作空間和獎勵函數(shù)，借助算法的智能體決策解決帶時間窗的運輸問題，驗證了該算法在解決帶時間窗的綠色車輛路徑問題上的有效性。

1 算法概述

1.1 深度雙Q網(wǎng)絡(luò)與競爭深度Q網(wǎng)絡(luò)

在原始的DQN算法中，由于原始算法采用的是新策略的方法，容易出現(xiàn)Q值估計偏高的情形。算法每次在學(xué)習(xí)時，不是使用下一次交互使用的真實動作，而是使用當(dāng)前策略認為的價值最大的動作，產(chǎn)生最大化偏差，使得估計動作的Q值偏大。

為了解決這個問題，將動作選擇和價值估計進行解耦，Hasselt等提出了深度雙Q網(wǎng)絡(luò)。DDQN算法相較于DQN算法，改變了目標(biāo)值的計算方法，這使得訓(xùn)練過程更加穩(wěn)定，能夠有效地解決后者對于動作價值的高估問題，提高了算法的收斂性和性能。

DDQN基于經(jīng)驗回放機制與目標(biāo)網(wǎng)絡(luò)技巧，構(gòu)建兩個動作價值神經(jīng)網(wǎng)絡(luò)，一個用于估計動作，另外一個用于估計該動作的價值。DDQN算法不直接通過最大化的方式選取目標(biāo)網(wǎng)絡(luò)計算的所有可能Q值，而是首先通過評估網(wǎng)絡(luò)選取最大Q值對應(yīng)的動作。

接著，再將評估網(wǎng)絡(luò)選擇出的動作a，輸入目標(biāo)網(wǎng)絡(luò)計算目標(biāo)值：

式中：y表示目標(biāo)值，w表示評估網(wǎng)絡(luò)參數(shù)，w表示目標(biāo)網(wǎng)絡(luò)參數(shù)。

Dueling DQN算法是傳統(tǒng)DQN的一個拓展，它包含了一種新的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)——競爭網(wǎng)絡(luò)（Duel Network）。Dueling DQN通過引入一個基準(zhǔn)網(wǎng)絡(luò)和一個優(yōu)勢網(wǎng)絡(luò)，將值函數(shù)的估計分解為狀態(tài)值和動作優(yōu)勢。狀態(tài)值表示在給定狀態(tài)下的期望回報，而動作優(yōu)勢表示每個動作相對于平均值的優(yōu)劣程度。通過這種分解，Dueling DQN可以將注意力集中在對狀態(tài)值的學(xué)習(xí)上，而無需為每個動作單獨計算值。這使得算法更加高效，并且能夠更好地處理動作空間較大的環(huán)境。Dueling DQN的評估網(wǎng)絡(luò)結(jié)構(gòu)如下：

式中：V為最優(yōu)狀態(tài)價值函數(shù)，A為最優(yōu)優(yōu)勢函數(shù)，第三項為在動作a平均取值情況下的優(yōu)勢函數(shù)，一般為0。

1.2 軟更新策略的決斗雙重深度Q網(wǎng)絡(luò)

決斗雙重深度Q網(wǎng)絡(luò)（D3QN）結(jié)合了Double DQN和Dueling DQN算法的思想，進一步提升了算法的性能，是二者的演化與升級。它與Dueling DQN算法的唯一區(qū)別在于計算目標(biāo)值的方式，其目標(biāo)網(wǎng)絡(luò)計算方式借鑒了Double DQN的思想，即利用評估網(wǎng)絡(luò)獲取s狀態(tài)下最優(yōu)動作價值對應(yīng)的動作，然后利用目標(biāo)網(wǎng)絡(luò)計算該動作的動作價值，從而得到目標(biāo)值。

本文使用基于軟更新策略的D3QN來解決VRPTW問題。D3QN的目標(biāo)網(wǎng)絡(luò)與評估網(wǎng)絡(luò)的模型和參數(shù)完全一致。這兩個網(wǎng)絡(luò)的更新方式包括硬更新和軟更新，本文采取軟更新的方式對評估網(wǎng)絡(luò)的參數(shù)進行更新。評估網(wǎng)絡(luò)的參數(shù)每更新迭代一次，目標(biāo)網(wǎng)絡(luò)的參數(shù)也會隨之更新。軟更新通過在每次更新時將一小部分評估網(wǎng)絡(luò)的參數(shù)與目標(biāo)網(wǎng)絡(luò)的參數(shù)進行混合，從而使目標(biāo)網(wǎng)絡(luò)的更新過程平滑化。這種混合比例由超參數(shù)tau控制。具體更新公式如下：

w=tau*w+1-tau*w （4）

軟更新可以減輕強化學(xué)習(xí)算法中的不穩(wěn)定性問題。盡管相比于硬更新，其學(xué)習(xí)速度可能相對較慢，但如軟更新在訓(xùn)練過程中提供了一種平滑的、逐漸更新的方式，更能增加算法的穩(wěn)定性。

2 帶時間窗的綠色車輛路徑問題描述

2.1 問題描述

本文所研究的帶時間窗的綠色車輛路徑問題，在規(guī)劃路線過程中考慮了環(huán)境保護和可持續(xù)性的因素，旨在最小化運輸成本的同時，減少運輸過程中的碳排放。綠色車輛問題的優(yōu)化可以通過車輛調(diào)度和路徑規(guī)劃、車輛種類的選擇以及燃料消耗等方面實現(xiàn)，降低對環(huán)境的影響[10]。在本文的模型中，所有的配送車輛被認為是相同的，因此，它們的排放量也相同。對于綠色車輛路徑問題，本文的攻克重點放在車輛的調(diào)度數(shù)量和路線的距離上。車輛啟動所排放的二氧化碳量是固定的，因此，調(diào)度越少的車輛，服務(wù)單位客戶的碳排放越低。基于此，本文模型的優(yōu)化目標(biāo)為：首先實現(xiàn)調(diào)度車輛數(shù)量最小化，其次實現(xiàn)運輸路線距離最小化，以期實現(xiàn)對環(huán)境的最小影響。獎勵與懲罰函數(shù)的設(shè)置也關(guān)系到模型的優(yōu)劣程度。本文對于車輛的調(diào)度成本設(shè)置為120個單位，而服務(wù)單個客戶的成本為90個單位。對于智能體而言，需要服務(wù)至少兩個客戶，才能實現(xiàn)正收益，進一步保證了運輸?shù)挠行院驼{(diào)度的綠色性。

VRPTW問題的模型目標(biāo)為：設(shè)計一組使總成本最小化的路線，首先最小化調(diào)度車輛數(shù)，其次最小化總運輸距離。該問題的其他調(diào)度規(guī)則有：

每一個顧客僅服務(wù)一次；

每一條路線從0節(jié)點開始，到n+1節(jié)點結(jié)束；

能夠?qū)崟r觀測到客戶的時間窗，車輛的容量限制；

車輛在節(jié)點之間的移動距離在數(shù)值上等同于移動所花費的時間。

VRPTW問題的模型如下：

式（5）為目標(biāo)函數(shù)，表明模型的目標(biāo)是最小化總運輸成本。式（6）確保每一個客戶僅被訪問一次。式（7）表明單一車輛的運輸上限為它的容量上限。式（8）、式（9）和式（10）表明單一運輸車輛必須從車庫0出發(fā)，在服務(wù)客戶后，最終回到車庫節(jié)點n+1。式（11）建立了從上一個客戶到下一個客戶的車輛離開時間的關(guān)系。式（12）確保車輛服務(wù)時間在顧客的時間窗內(nèi)。式（13）表明x為一個決策變量，保證單個車輛服務(wù)對應(yīng)的客戶。式（14）規(guī)定了多個變量的取值范圍。

2.2 D3QN求解目標(biāo)問題

使用D3QN算法求解帶時間窗的綠色車輛路徑問題，需要對算法的狀態(tài)空間與動作空間、獎勵函數(shù)兩個方面進行重新設(shè)計。本節(jié)也從這兩各方面進行介紹。

狀態(tài)空間與動作空間方面，本文的狀態(tài)空間指的是將車輛進行調(diào)度，服務(wù)顧客的過程中所處狀態(tài)的集合。在本文問題中，車輛的狀態(tài)為訪問顧客的序列，長度為n。本文定義：在一輛車出發(fā)后，服務(wù)顧客，最終回到倉庫時，車輛的坐標(biāo)更新，容量重置為初始容量，調(diào)度時間歸零，調(diào)度車輛序號增加1。

本文的動作空間定義為：將訪問序列輸入神經(jīng)網(wǎng)絡(luò)D60+iQ6532T6fe0KTWa+RohNF66HWZiwyOj1lIJa4os=，與環(huán)境進行交互所得到新的訪問序列。動作空間的維度也為n，它會隨著訓(xùn)練集中顧客數(shù)量的增加而增加。神經(jīng)網(wǎng)絡(luò)輸出層輸出的是采取動作a的情況下，進入下一個狀態(tài)s可能選擇的各種動作所對應(yīng)的Q值大小。車輛將持續(xù)選擇Q值最大的動作，更新位置與獎勵。神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示。

車輛狀態(tài)輸入神經(jīng)網(wǎng)絡(luò)后，通過ReLU函數(shù)激活（見圖2），傳遞給下一個隱藏層或輸出層。當(dāng)車輛容量無法滿足下一個顧客的需求，或是獎勵過小時，車輛將直接返回倉庫（0號節(jié)點），并調(diào)度下一輛車進行服務(wù)。

車輛每進行一次服務(wù)，將更新一次車輛移動的總距離，進行一次獎勵函數(shù)的計算和累計，更新一次車輛的服務(wù)順序序列，更新一次車內(nèi)的剩余容量。

獎勵函數(shù)的設(shè)置方面，深度強化學(xué)習(xí)的目標(biāo)是最大化累計獎勵。獎勵函數(shù)的設(shè)置會影響到模型的學(xué)習(xí)效果。本文模型的實現(xiàn)目標(biāo)為：首先實現(xiàn)調(diào)度車輛數(shù)量最小化，其次實現(xiàn)總運輸距離最小化。前者的優(yōu)先級要高于后者?；谶@個原則，智能體在訓(xùn)練過程中調(diào)用的車輛越多，調(diào)度成本越高，懲罰應(yīng)當(dāng)越大；所有車輛運輸?shù)目偩嚯x越短，獎勵越大。這兩個部分作為公式的第一項和第二項，以負整數(shù)的形式表示。由于在本模型中，車輛行駛距離長短的數(shù)值等同于所花費的時間，因此，車輛的行駛距離越短，也意味著所花費的時間越少。在公式的第三項中，車輛每服務(wù)一個客戶，進行一次固定的獎勵。

本文研究問題的時間窗為硬時間窗，即車輛只能在規(guī)定時間內(nèi)為客戶服務(wù)。因此，提前到達客戶地點的車輛，需要等待到客戶的服務(wù)時間窗，才能進行服務(wù)，對于這部分車輛，不進行懲罰。

因此，將D3QN的累計獎勵函數(shù)設(shè)置為三部分之和，具體公式如下：

R=-c-cx+nβ （15）

式中：c為調(diào)用單位車輛的固定成本，對于所有車輛來說，它們的固定成本是一樣的。β為一個正整數(shù)，根據(jù)本文的算例和不斷實驗調(diào)整得到。在本文的算例中，設(shè)置β為90。

2.3 研究與算法流程

本文的研究流程如圖3所示。

本文算法的偽代碼如表1所示。

3 算法訓(xùn)練

3.1 算法模型與參數(shù)設(shè)置

本文應(yīng)用算法為基于軟更新策略的決斗雙重深度Q網(wǎng)絡(luò)，基于Python3.9語言與Pytorch1.13框架實現(xiàn)，配置12th Gen Intel（R）Core（TM）i9-12900H 2.50 GHz，RAM 16.0GB。VRPTW模型借助Python中的gym庫進行編譯。

探索策略方面，本文使用ε-貪心策略（epsilon-greedy）來對目標(biāo)問題進行求解。

式中：ε為一個小于1的正數(shù)，P=ε表示算法以ε的概率隨機選擇動作空間的動作，P=1-ε表示算法以1-ε的概率選擇當(dāng)前時間步內(nèi)價值最大的動作作為下個時間步要執(zhí)行的動作。

算法方面，D3QN的評估網(wǎng)絡(luò)共有四層網(wǎng)絡(luò)結(jié)構(gòu)。算法的第一層為輸入層，共有四個輸入維度，分別是：當(dāng)前車輛所在節(jié)點的序號、車內(nèi)的實時容量、當(dāng)前的時間以及當(dāng)前調(diào)度車輛的序號。算法的第二層、第三層和第四層為隱藏層，它們都是有128個神經(jīng)元結(jié)點的全連接層，使用ReLU函數(shù)進行激活。算法的第五層為輸出層，輸出層輸出的是對于各個動作的價值評估，輸出維度會隨著客戶數(shù)量的變化而變化。根據(jù)各個動作的價值，智能體選擇價值最高的動作采取下一步的行動。本文使用Adam優(yōu)化器進行梯度下降法的求解。

D3QN算法的超參數(shù)設(shè)置如表2所示。

模型方面，借助gym庫，構(gòu)建了VRPTW模型的虛擬環(huán)境，以便接入強化學(xué)習(xí)算法中進行訓(xùn)練。本文選擇了客戶數(shù)量分別為10、20和50的多個數(shù)據(jù)集，分別代表小規(guī)模，中規(guī)模和大規(guī)模調(diào)度問題，以便驗證算法在不同規(guī)模上的性能。越大規(guī)模的問題，智能體獲得獎勵的函數(shù)趨近收斂所需要的實驗迭代次數(shù)越多。因此，針對不同規(guī)模的調(diào)度問題，本文也設(shè)置了不同的約束和實驗的迭代次數(shù)。模型的部分超參數(shù)如表3所示。

至此，本文的模型已經(jīng)構(gòu)建完畢。

3.2 實驗與分析

本文選擇了Double DQN以及Dueling DQN算法，將它們與D3QN算法在不同問題規(guī)模的數(shù)據(jù)集上進行對比實驗，以檢驗D3QN算法在解決此類問題上的優(yōu)越性。

在表4所展示的18個不同規(guī)模的實驗結(jié)果中，有14個實例中，D3QN取得了最高的獎勵，占總實驗次數(shù)的77.8%。由于本文實驗的研究目標(biāo)為：首先最小化調(diào)度車輛數(shù)量，其次最小化運輸距離。因此，基于研究問題的綠色性原則，取得最高獎勵的實驗案例，運輸里程未必最短。將三種算法在不同規(guī)模實例下的實驗結(jié)果進行平均取值，具體結(jié)果如圖4所示：

從圖4發(fā)現(xiàn)：在平均最高獎勵方面，D3QN算法比Double DQN高5.45%，比Dueling DQN高11.27%；在平均車輛調(diào)度數(shù)方面，D3QN算法比Double DQN低3.34%，比Dueling DQN低6.17%；在平均里程方面，D3QN算法比Double DQN低2.93%，比Dueling DQN低5.38%。

此外，本文還對實驗的總運算時間和收斂時的迭代次數(shù)兩個變量進行了統(tǒng)計，具體結(jié)果如表5所示：

?; 本文分別設(shè)置模型規(guī)模為10、20、50的算例的總迭代次數(shù)為100、200和300次。總體而言，三種算法總運算時間較短，收斂時的迭代次數(shù)較快。將統(tǒng)計數(shù)據(jù)進行平均取值，具體結(jié)果展示如圖5所示。

從圖5中發(fā)現(xiàn)：在平均總運算時間方面，D3QN比Double DQN多7.71%，絕對值為0.13s，比Dueling DQN多4.35%，絕對值為0.08s；在平均收斂迭代次數(shù)方面，D3QN比Double DQN少36.17%，比Dueling DQN少35.16%。造成這種結(jié)果的原因可能是算法的結(jié)構(gòu)不同。D3QN算法作為后兩者算法的組合，其計算復(fù)雜度要更高，因而會耗費更長的時間。但是，從絕對數(shù)值的角度分析，D3QN多增加的運算時間平均保持在0.15s內(nèi)，在實際應(yīng)用中處于可接受范圍內(nèi)。此外，由于D3QN算法比后兩者算法收斂速度要快，因此，在減少相同迭代次數(shù)的情況下，D3QN算法會比后兩者算法花費更少的時間收斂。

圖6展示了在客戶為50個的問題下，以C204數(shù)據(jù)進行實驗的三種算法的獎勵變化、調(diào)度車輛變化以及里程的變化。為了更直觀地展示實驗效果，本文設(shè)置實驗次數(shù)為150輪。在前40輪中，D3QN算法最高獎勵的上升速度較快，并且最先收斂。在此實例的實驗中，三種算法所得到的最高獎勵值接近，且用時均在2s以內(nèi)。在圖6（c）中，里程變化是上下波動的，因為調(diào)度車輛的減少可能導(dǎo)致獎勵值和運輸里程的增加。這也印證了本文研究問題的綠色性。

通過上述表格以及圖，得出結(jié)論：在可接受的增加運算時間的情況下，基于軟更新策略的D3QN算法相比于Double DQN和Dueling DQN算法能更快的收斂，得出更優(yōu)的解。在帶時間窗的綠色車輛路徑優(yōu)化問題中，D3QN算法相比于后兩者算法更具備優(yōu)越性。前者在算法層面結(jié)合了后者的優(yōu)點。由于強化學(xué)習(xí)算法的探索具有一定的隨機性，算法的表現(xiàn)基于不同的算例可能有差異。同時，算法的表現(xiàn)也受到實驗參數(shù)、獎勵函數(shù)、訓(xùn)練次數(shù)和深度以及計算機性能等方面因素的影響。隨著這些因素的不斷調(diào)整與優(yōu)化，算法的表現(xiàn)也會越來越好。

4 結(jié)論與展望

本文使用基于軟更新策略的D3QN算法對帶時間窗的綠色車輛路徑問題進行研究，將車輛的調(diào)度問題轉(zhuǎn)化成顧客訪問的排序問題；通過設(shè)置獎勵函數(shù)，優(yōu)先實現(xiàn)最小化調(diào)度車輛的目標(biāo)，保證運輸?shù)木G色低碳；借助Python中的gym庫，使算法的智能體與環(huán)境進行交互，重新規(guī)劃序列。D3QN算法結(jié)合了Double DQN和Dueling DQN算法的技巧。在大部分算例中，D3QN算法在此類問題上的表現(xiàn)要優(yōu)于這二者，能更快地尋找到更優(yōu)質(zhì)量的解。

本文的主要貢獻如下：

（1）使用D3QN算法為帶時間窗的綠色車輛路徑問題設(shè)計了相應(yīng)的動作空間與狀態(tài)空間和獎勵函數(shù)，能夠較好地將問題轉(zhuǎn)化為強化學(xué)習(xí)中智能體的運算與迭代。

（2）使用軟更新的策略對D3QN算法的評估網(wǎng)絡(luò)參數(shù)進行更新，能保證算法的穩(wěn)定性和收斂性。

（3）在小、中、大的共18個數(shù)據(jù)集上進行了實驗，將Double DQN與Dueling DQN作為對比，驗證了D3QN算法的有效性。

綜上所述，D3QN算法在解決VRPTW問題上仍然有較大的潛力。隨著模型的優(yōu)化和計算機算力的提升，該算法的性能也會進一步提升。

參考文獻：

[1] MNIH V， KAVUKCUOGLU K， SILVER D， et al. Playing atari with deep reinforcement learning[EB/OL]. （2021-12-19）[2023-09-20]. https：//arXiv.org/pdf/1312.5602.pdf.

[2] SILVER D， HUANG A， MADDISON C， et al. Mastering the game of go with deep neural networks and tree search[J]. Nature， 2016，529：484-489.

[3] VAN HASSELT H， GUEZ A， SILVER D. Deep reinforcement learning with double q-learning[C] // Proceedings of the AAAI Conference on Artificial Lintelligence， 2016.

[4] WANG Z， SCHAUL T， HESSEL M， et al. Dueling network architectures for deep reinforcement learning[C] // International Conference on Machine Learning PMLR， 2016：1995-2003.

[5] 袁帥，張莉莉，顧琦然，等. 移動機器人優(yōu)先采樣D3QN路徑規(guī)劃方法研究[J]. 小型微型計算機系統(tǒng)，2023，44（5）：923-929.

[6] 韓磊，張輪，郭為安. 混合交通流環(huán)境下基于改進強化學(xué)習(xí)的可變限速控制策略[J]. 交通運輸系統(tǒng)工程與信息，2023，23（3）：110-122.

[7] KOOL W， VAN HOOF H， WELLING M. Attention， learn to solve routing problems！[EB/OL]. （2021-10-24）[2003-09-20]. https：//github.com/wouterkool/attention-learn-to-route.

[8] NAZARI M， OROOJLOOY A， SNYDER L， et al. Reinforcement learning for solving the vehicle routing problem[EB/OL]. （2023-09-08）[2023-09-20]. https：//github.com/optML Group/VRP-RL.

[9] LIN B， GHADDAR B， NATHWANI J. Deep reinforcement learning for the electric vehicle routing problem with time windows[J]. IEEE Transactions on Intelligent Transportation Systems， 2021，23（8）：11528-11538.

[10] ASGHARI M， AL-E S M J M. Green vehicle routing problem： A state-of-the-art review[J]. International Journal of Production Economics， 2021，231：107899.

[11] SOLOMONMM. Vehicle routing and scheduling with time window constraints： Imodels and algorithms （heuris tics）[D]. University of Pennsylvania， 1984.

[12] SAVELSBERGH M W P. The vehicle routing problem with time windows： Minimizing route duration[J]. ORSA Journal on Computing， 1992，4（2）：146-154.

[13] MARTIN DESROCHERS， JACQUES DESROSIERS， MARIUS SOLOMON. A new optimization algorithm for the vehicle routing problem with time windows[J]. Operations Research， 1992，40（2）：342-354.

[14] K C TAN， L H LEE， K OU. Artificial intelligence heuristics insolving vehicle routing problems with time window constraints[J]. Engineering Applications of Artificial Intelligence， 2001，14（6）：825-837.

[15] 劉虹慶，王世民. 基于強化學(xué)習(xí)的車輛路徑規(guī)劃問題研究[J]. 計算機應(yīng)用與軟件，2021，38（8）：303-308.

[16] SAMUEL A L. Some studies in machine learning using the game of checkers[J]. IBM Journal of Research and Development， 1959，3（3）：210-229.

[17] WATKINS C J C H， DAYAN P. Q-learning[J]. Machine Learning， 1992（8）：279-292.

[18] HUANG Y， WEI G L， WANG Y X. VD D3QN： The variant of double deep q-learning network with dueling architecture

[C] // 第37屆中國控制會議論文集（F），2018.

[19] KALLEHAUGE B， LARSEN J， MADSEN O B G， et al. Vehicle routing problem with time windows[M]. Springer US， 2005.

[20] 韓巖峰. 基于深度強化學(xué)習(xí)的無人物流車隊配送路徑規(guī)劃研究[D]. 大連：大連理工大學(xué)，2021.

[21] 周瑤瑤，李燁. 基于排序優(yōu)先經(jīng)驗回放的競爭深度Q網(wǎng)絡(luò)學(xué)習(xí)[J]. 計算機應(yīng)用研究，2020，37（2）：486-488.

[22] 馮超. 強化學(xué)習(xí)精要[M]. 北京：電子工業(yè)出版社，2018.

[23] 劉馳，王占健，戴子彭. 深度強化學(xué)習(xí)學(xué)術(shù)前沿與實戰(zhàn)應(yīng)用[M]. 北京：機械工業(yè)出版社，2020.

[24] YANG S， XU Z， WANG J. Intelligent decision-making of scheduling for dynamic permutation flowshop via deep reinforcement learning[J]. Sensors， 2021，21（3）：1019.

[25] 孫滬增，李章維，秦子豪，等. 帶時間窗車輛路徑規(guī)劃算法研究與實現(xiàn)[J]. 小型微型計算機7a4019138b4b6d4f1e2855f6b56a0e9290d1caf14133d0fb1134951c9679e173系統(tǒng)，2020（5）：972-977.

[26] TICHA H B， ABSI N， FEILLET D， et al. Multigraph modeling and adaptive large neighborhood search for the vehicle routing problem with time windows[J]. Computers & Operations Research， 2019，104：113-122.

[27] 李茹楊，彭慧民，李仁剛，等. 強化學(xué)習(xí)算法與應(yīng)用綜述[J]. 計算機系統(tǒng)應(yīng)用，2020，29（12）：17-29.

[28] BURSUC A， GUETTIER C， et al. Optimal solving of constrained path-planning problemswith graph convolutional networks and optimized tree search[C] // 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems （IROS）， IEEE， 2019：3519-3525.