徐郁，朱韻攸，劉筱，鄧雨婷，廖勇

（1.國(guó)網(wǎng)重慶市電力公司 永川供電分公司，重慶 402160；2.國(guó)網(wǎng)重慶市電力公司 信息通信分公司，重慶 401120；3.重慶錦禹云能源科技有限公司，重慶 400050；4.重慶大學(xué) 微電子與通信工程學(xué)院，重慶 400044）

0 引言

隨著我國(guó)電力需求的不斷增長(zhǎng)、電網(wǎng)規(guī)模不斷擴(kuò)大，電力系統(tǒng)的物資需求量正在不斷增加，保障電力物資的及時(shí)供應(yīng)是亟待解決的問題［1］。強(qiáng)化學(xué)習(xí)（Reinforcement Learning，RL）對(duì)人工智能（Artificial Intelligence，AI）的發(fā)展產(chǎn)生了重大影響［2］，智能體（agent）在學(xué)習(xí)過程中定期作出決策，根據(jù)觀察結(jié)果自動(dòng)調(diào)整其策略以實(shí)現(xiàn)最佳決策。最近，由于深度強(qiáng)化學(xué)習(xí)（Deep Reinforcement Learning，DRL）的出現(xiàn)，克服了強(qiáng)化學(xué)習(xí)的局限性，從而為強(qiáng)化學(xué)習(xí)的發(fā)展開辟了一個(gè)新的時(shí)代［3］。DRL 利用深度神經(jīng)網(wǎng)絡(luò)（Deep Neural Network，DNN）的優(yōu)勢(shì)來訓(xùn)練學(xué)習(xí)過程，從而提高了學(xué)習(xí)效率和性能。在路徑優(yōu)化領(lǐng)域，DRL 已被用作有效解決各種問題和挑戰(zhàn)的新興工具［4］。

車輛路徑問題（Vehicle Routing Problem，VRP）自提出以來，一直受到廣泛關(guān)注與研究，此后VRP 被拓展到了更多的場(chǎng)景［5］。目前有多種智能算法可用于解決此類問題，例如擴(kuò)展C-W（Extended Clarke and Wright，ECW）節(jié)約算法［6］、模擬退火（Simulated Annealing，SA）算法［7］、遺傳算法［8］等。最近，應(yīng)用DRL 來解決VRP 成為一種新興趨勢(shì)，例如文獻(xiàn)［9］中提出了一種基于深度Q-網(wǎng)絡(luò)（Deep Q-Network，DQN）的全局路徑規(guī)劃方法，機(jī)器人能在多障礙物中獲得其最佳移動(dòng)路徑，仿真結(jié)果表明該方法相較于傳統(tǒng)優(yōu)化方法更高效，是DRL算法在路徑規(guī)劃領(lǐng)域成功的應(yīng)用。針對(duì)裝卸貨問題（Pickup and Delivery Problem，PDP）的配對(duì)和優(yōu)先級(jí)關(guān)系，文獻(xiàn)［10］中設(shè)計(jì)了基于異構(gòu)注意力機(jī)制集成的新型神經(jīng)網(wǎng)絡(luò)的DRL算法，為PDP 提供了更高質(zhì)量的解決方案，但網(wǎng)絡(luò)模型過于復(fù)雜，計(jì)算難度大。針對(duì)當(dāng)前電力物資配送的信息化需求，文獻(xiàn)［11］中建立了多中心、多場(chǎng)地和多配送需求的多點(diǎn)配送模型，但是該模型僅考慮了最短距離為目標(biāo)。文獻(xiàn)［12］中構(gòu)建了電力應(yīng)急物資配送路徑優(yōu)化的多目標(biāo)優(yōu)化模型，設(shè)計(jì)了改進(jìn)的ε-constraint 算法進(jìn)行求解，但是求解過程較為復(fù)雜。

對(duì)于電力物資配送路徑優(yōu)化問題，可以將其看作VRP的擴(kuò)展，即電力物資車輛路徑問題（Electric power material Vehicle Routing Problem，EVRP）［13］。針對(duì)現(xiàn)有EVRP 優(yōu)化算法求解效率不高且模型考慮的目標(biāo)較為單一、約束不全面的問題，本文在充分考慮了電力物資配送區(qū)域的加油站分布情況、物資運(yùn)輸車輛的油耗等約束，建立了以電力物資配送路徑總長(zhǎng)度最短、成本最低、物資需求點(diǎn)滿意度最高為目標(biāo)的多目標(biāo)電力物資配送模型。為了提高模型求解效率，快速進(jìn)行電力物資配送的路徑優(yōu)化，本文設(shè)計(jì)了一種基于DRL 的電力物資配送路徑優(yōu)化算法DRL-EVRP，將RL 與改進(jìn)的指針網(wǎng)絡(luò)（Pointer Network，Ptr-Net）結(jié)合成DQN，無需人為設(shè)計(jì)和調(diào)整繁雜的求解過程，DQN 使用一個(gè)記憶庫來存儲(chǔ)之前的樣本數(shù)據(jù)，隨機(jī)選擇小批量樣本進(jìn)行網(wǎng)絡(luò)訓(xùn)練，提高學(xué)習(xí)效率，可讓DRL-EVRP 對(duì)電力物資配送的樣本數(shù)據(jù)訓(xùn)練學(xué)習(xí)后，達(dá)到最優(yōu)電力物資配送路徑規(guī)劃的效果，從而有效解決EVRP。實(shí)驗(yàn)結(jié)果表明，相較于SA 和ECW 算法，所提算法具有較優(yōu)的求解結(jié)果，算法的運(yùn)算時(shí)間在接受范圍，從而可以快速準(zhǔn)確地實(shí)現(xiàn)電力物資配送路徑優(yōu)化。

1 電力物資配送建模

1.1 問題描述

本文主要探討電力物資配送路徑優(yōu)化問題，以電力物資配送總成本最小、滿意度最高為優(yōu)化目標(biāo)，建立基于物資配送區(qū)域加油站網(wǎng)絡(luò)、路徑最短（運(yùn)輸時(shí)長(zhǎng)最短）、考慮配送車輛載重量和配送車輛油耗的電力物資配送多目標(biāo)路徑優(yōu)化模型。

電力物資配送路徑優(yōu)化問題可以描述為無向的完全圖G=(V，E)，如圖1 所示。其中頂點(diǎn)集由一個(gè)配送中心Vn（n=1，2，…，v）、物資需求點(diǎn)集I={I1，I2，…，Ii}和加油站集F={F1，F(xiàn)2，…，F(xiàn)f}共同組成，即V={Vn}∪I∪F。于是可以用V={v0，v1，…，vm}來表示圖G的頂點(diǎn)集，其中：頂點(diǎn)v0表示物資配送中心，m=1 +i+f；E={(vx，vy)：vx，vy∈V，x＜y}是連接V中各頂點(diǎn)邊的集合，每個(gè)物資需求點(diǎn)有不同的需求量dx，每條邊(vx，vy)都對(duì)應(yīng)著路徑長(zhǎng)度disxy、運(yùn)輸時(shí)間txy和運(yùn)輸成本cxy。

本文電力物資配送路徑優(yōu)化問題的優(yōu)化目標(biāo)即為找到k條配送路徑（每條路徑對(duì)應(yīng)一輛物資配送車輛），使得其電力物資配送總成本最小、物資需求點(diǎn)滿意度最高。本文考慮路徑最短、成本最低、物資需求點(diǎn)滿意度最佳的配送多目標(biāo)路徑優(yōu)化模型。每條配送路徑從物資配送中心Vn出發(fā)，運(yùn)輸車輛前往每個(gè)物資需求點(diǎn)進(jìn)行電力物資的貨物卸載，當(dāng)運(yùn)輸車輛油量不足時(shí)可前往加油站進(jìn)行加油，最后回到物資配送中心，物資運(yùn)輸車輛的最大載重為Wmax，同時(shí)路徑總運(yùn)輸時(shí)長(zhǎng)不會(huì)超過駕駛員最大可接受駕駛時(shí)間Tmax，滿意度由實(shí)際送達(dá)時(shí)間與期望送達(dá)時(shí)間的偏離程度來衡量。

為了更好地求解本文中電力物資配送路徑優(yōu)化問題，需要進(jìn)行前提設(shè)置，具體如下：

1）物資需求點(diǎn)的需求量最大不超過運(yùn)輸車輛的載重；

2）一個(gè)物資需求點(diǎn)需要且只需要進(jìn)行一次物資配送；

3）物資運(yùn)輸車輛行駛速度恒定，加油時(shí)間恒定；

4）每次加油后，運(yùn)輸車輛即為滿油量狀態(tài)，且加油次數(shù)不限；

5）滿油量的運(yùn)輸車輛能從配送中心直接行駛到任一加油站，即不考慮離配送中心過遠(yuǎn)的加油站；

6）滿油量的車輛從電力物資配送中心出發(fā)至任一物資需求點(diǎn)并返回配送中心過程中最多需要經(jīng)過一個(gè)加油站，即不考慮過遠(yuǎn)的物資需求點(diǎn)。

1.2 電力物資配送模型

由于物資需求點(diǎn)必須且只能被訪問一次，而加油站可能被訪問多次，所以還需要將頂點(diǎn)集V擴(kuò)大為V'=V∪Φ，其中Φ由虛擬點(diǎn)構(gòu)成，即Φ={vi+f+1，vi+f+2，…，vi+f+f'}，每個(gè)虛擬點(diǎn)對(duì)應(yīng)著一次對(duì)加油站的額外訪問；相應(yīng)地，E可擴(kuò)充為E'，G'=(V'，E')。

根據(jù)上述分析與假設(shè)，本文建立的電力物資配送模型的目標(biāo)函數(shù)為：

約束條件為：

其中：C1和C2分別為物資運(yùn)輸車輛固定成本和運(yùn)輸成本；a、b為物資需求點(diǎn)Ii對(duì)時(shí)間的敏感系數(shù)；Ti為物資期望送達(dá)時(shí)間；ti為物資實(shí)際送達(dá)時(shí)間，需求點(diǎn)在時(shí)間［Ti-ε，Ti+ε］內(nèi)收到電力物資則滿意程度為1，否則滿意度會(huì)隨偏離時(shí)間的加大而遞減；ε為時(shí)間長(zhǎng)度；Hi(ti)為ti物資送達(dá)時(shí)間下的物資需求點(diǎn)的滿意度；I0表示物資配送中心和物資需求點(diǎn)集，即I0={v0}∪I；F0表示配送中心和加油站集，即F0={v0}∪F'，其中F'=F∪Φ；K表示所有運(yùn)輸車輛集合，即K={1，2，…，k}；txy表示運(yùn)輸車輛從點(diǎn)x到點(diǎn)y的時(shí)間；τy表示運(yùn)輸車輛到達(dá)點(diǎn)y后所花費(fèi)的時(shí)間（從物資配送中心出發(fā)時(shí)，τ0=0）；px表示在頂點(diǎn)x所需要的時(shí)間服務(wù)時(shí)間（如果x∈I，則px為在物資需求點(diǎn)的服務(wù)時(shí)間，如果x∈F，則px為在加油站的加油所耗的時(shí)間）；qy為運(yùn)輸車輛到達(dá)y點(diǎn)后的剩余油量（到達(dá)物資配送中心和加油站加油后，令qy=Q）；r表示運(yùn)輸車輛的油耗速率；Q為運(yùn)輸車輛的油箱容積，也即運(yùn)輸車輛滿油狀態(tài)下的油量。

式（1）～（3）表示本文模型的優(yōu)化目標(biāo)；式（4）、（6）確保每個(gè)物資需求點(diǎn)有且僅有一輛運(yùn)輸車輛到達(dá)和離開；式（5）～（6）約束了至多有一輛運(yùn)輸車到達(dá)和離開加油站以及對(duì)應(yīng)的虛擬點(diǎn)；式（7）～（8）表示至多有k輛車到達(dá)和離開物資配送中心；式（9）確保同一路徑上的運(yùn)輸車輛到達(dá)時(shí)間遵從時(shí)間順序；式（10）保證了每輛車的駕駛時(shí)間不會(huì)超過駕駛員的最長(zhǎng)可接受的駕駛時(shí)間Tmax；式（11）確保運(yùn)輸車輛從物資配送中心出發(fā)后，到達(dá)任意一點(diǎn)都能在Tmax內(nèi)回到物資配送中心；式（12）是運(yùn)輸車輛油耗情況；式（13）～（14）跟運(yùn)輸車輛油量相關(guān)；式（15）保證了運(yùn)輸車輛不會(huì)超重；式（16）約束了每個(gè)物資需求點(diǎn)只有一輛車服務(wù)；式（17）表示同一路徑上的頂點(diǎn)由同一輛車進(jìn)行電力物資運(yùn)輸；式（18）～（19）可分別表示為：

2 基于DQN的電力物資配送路徑優(yōu)化

Q-學(xué)習(xí)（Q-learning）算法是強(qiáng)化學(xué)習(xí)中經(jīng)典的算法，它使用一個(gè)Q 值表（Q-table）來存儲(chǔ)每個(gè)狀態(tài)-動(dòng)作對(duì)下的獎(jiǎng)勵(lì)值，通過智能體與環(huán)境的交互得到獎(jiǎng)勵(lì)值，然后更新Q 值表，使得選擇獎(jiǎng)勵(lì)值最大的動(dòng)作的概率不斷增加，從而智能體能夠獲得最優(yōu)的策略與獎(jiǎng)勵(lì)。假設(shè)智能體在時(shí)刻t下的狀態(tài)為s，智能體根據(jù)策略選擇動(dòng)作a，智能體到達(dá)下一狀態(tài)s'，環(huán)境反饋獎(jiǎng)勵(lì)值r，根據(jù)s、a和r更新Q 值表，更新表達(dá)式可表示為：

其中：α是學(xué)習(xí)率，γ是獎(jiǎng)勵(lì)的衰減率。不斷對(duì)Q 值表進(jìn)行更新直到達(dá)到最終狀態(tài)。

在本文電力物資配送路徑優(yōu)化問題中，環(huán)境較復(fù)雜，狀態(tài)數(shù)和動(dòng)作數(shù)較多，Q 值表維度太高會(huì)導(dǎo)致Q-learning 算法效率很低，所以本文使用結(jié)合改進(jìn)的指針網(wǎng)絡(luò)（Ptr-Net）和Q-learning 的DQN 算法來解決此問題。

2.1 DQN結(jié)構(gòu)

根據(jù)自然語言處理（Natural Language Processing，NLP）［14］，可以將本文中的EVRP 的解看作一個(gè)序列Y，則T+1可看作是序列的長(zhǎng)度，序列模型的目標(biāo)是最大化得到的序列的概率，即

其中：X={xi│i=0，1，…，M}表示輸入，xi表示第i個(gè)節(jié)點(diǎn)的相關(guān)信息，M=i+f；Y={yt│t=0，1，…，T}表示最后輸出的序列，yt表示第t個(gè)訪問節(jié)點(diǎn)的序號(hào)；Xt表示在t時(shí)刻的輸入；Yt={y0，y1，…，yt}表示截止到t時(shí)刻的輸出；f(·)表示狀態(tài)轉(zhuǎn)移方程。將輸入拆分成兩部分，即xi={xi=(si，) │t=0，1，…，T}，si表示頂點(diǎn)i的坐標(biāo)，與時(shí)刻t無關(guān)，始終不變；表示時(shí)刻t時(shí)物資運(yùn)輸車輛的剩余油量、路徑的剩余時(shí)間、物資需求點(diǎn)的需求量以及滿意度等，與時(shí)刻t有關(guān)，式（21）為輸入信息的更新表達(dá)式，物資運(yùn)輸車輛離開了某個(gè)物資需求點(diǎn)時(shí)，該需求點(diǎn)的需求量更新為0。

傳統(tǒng)的指針網(wǎng)絡(luò)使用雙向長(zhǎng)短期記憶（Bi-directional Long Short-Term Memory，Bi-LSTM）網(wǎng)絡(luò)作為編碼器，使得網(wǎng)絡(luò)增加了額外的復(fù)雜度，本文使用改進(jìn)的指針網(wǎng)絡(luò)來處理包含序列信息的數(shù)據(jù)，如圖2 所示，省略了由Bi-LSTM 構(gòu)成的編碼器，并直接使用嵌入層的輸入而不是Bi-LSTM 的隱藏狀態(tài)，改進(jìn)后在不降低模型的效率的同時(shí)可以降低計(jì)算復(fù)雜度。模型將輸入Xt=(s，dt)通過一維卷積神經(jīng)網(wǎng)絡(luò)（One Dimensional Convolutional Neural Network，1DCNN）映射到高維空間，得到嵌入層（Embedding Layer）的輸入，將輸入到由LSTM 作為基本單元組成的解碼器中，可得到解碼器輸出的隱藏狀態(tài)值ht，將其與輸入到注意力 層（Attention Layer），進(jìn)而可得到輸出。注意力機(jī)制計(jì)算表達(dá)式如下：

其中：式（24）～（25）計(jì)算得到的at為t時(shí)刻對(duì)各節(jié)點(diǎn)的注意力權(quán)重；式（26）為t時(shí)刻對(duì)各輸入的線性加權(quán)的和，輸出得到內(nèi)容向量ct；式（27）計(jì)算下一時(shí)刻的概率分布；va、vc、Wa、Wc是可訓(xùn)練的參數(shù)。

DQN 算法使用改進(jìn)的Ptr-Net 作為Q 值函數(shù)來代替Q 值表，本文所使用的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)如圖2 所示，它的Q 值函數(shù)可近似表示為：

其中：s是當(dāng)前智能體的狀態(tài)；at是智能體在當(dāng)前狀態(tài)下選擇的動(dòng)作；θ為神經(jīng)網(wǎng)絡(luò)的參數(shù)。DQN 算法可以很好地解決狀態(tài)空間大且是離散的問題［15］，從而保證數(shù)據(jù)處理的時(shí)效性，快速進(jìn)行電力物資配送的路徑優(yōu)化，同時(shí)節(jié)約存儲(chǔ)空間。

根據(jù)上述改進(jìn)的指針網(wǎng)絡(luò)，建立本文DQN 的結(jié)構(gòu)如圖3所示。DQN 中使用非線性方法表示Q 估計(jì)值函數(shù)，即Q(s，a；θ)，則DQN 中的損失函數(shù)定義為：

神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練從而更新參數(shù)θ，參數(shù)更新表示為：

DQN 是一種離線學(xué)習(xí)方法，使用一個(gè)記憶庫D 來解決連續(xù)樣本間的相關(guān)性問題，D 中儲(chǔ)存的是過去的電力物資配送路徑優(yōu)化經(jīng)驗(yàn)，然后從D 中隨機(jī)選擇小批量樣本進(jìn)行網(wǎng)絡(luò)訓(xùn)練，減小樣本間的相關(guān)性，從而提高DQN 的學(xué)習(xí)效率［16］。使用新舊經(jīng)驗(yàn)可以更加有效地訓(xùn)練神經(jīng)網(wǎng)絡(luò)，同時(shí)提高了經(jīng)驗(yàn)數(shù)據(jù)的利用率。DQN 中神經(jīng)網(wǎng)絡(luò)部分由兩個(gè)結(jié)構(gòu)相同但參數(shù)不同的改進(jìn)的指針網(wǎng)絡(luò)組成，即估計(jì)網(wǎng)絡(luò)和目標(biāo)網(wǎng)絡(luò)。估計(jì)網(wǎng)絡(luò)作為主網(wǎng)絡(luò)擁有最新的參數(shù)，輸出當(dāng)前狀態(tài)-動(dòng)作對(duì)下的Q 估計(jì)值Q(s，a)；目標(biāo)網(wǎng)絡(luò)不會(huì)及時(shí)更新參數(shù)，而是在訓(xùn)練時(shí)，每隔一定迭代步長(zhǎng)c從估計(jì)網(wǎng)絡(luò)將參數(shù)復(fù)制到目標(biāo)網(wǎng)絡(luò)中（網(wǎng)絡(luò)克隆），它產(chǎn)生Q 目標(biāo)值Q+(s，a)，用來評(píng)估當(dāng)前狀態(tài)—?jiǎng)幼鲗?duì)下的損失函數(shù)，從而進(jìn)行反向傳播調(diào)整網(wǎng)絡(luò)參數(shù)，具體過程見算法1。

本文基于DQN 的電力物資配送路徑優(yōu)化系統(tǒng)中的Q-learning 算法基本要素可表示為：

1）環(huán)境（environment）：電力物資配送網(wǎng)絡(luò)。

2）智能體（agent）：電力物資配送路徑優(yōu)化系統(tǒng)。

3）動(dòng)作（action）：在電力物資配送路徑優(yōu)化過程中，動(dòng)作at可表示為在步驟t選擇G'中一個(gè)頂點(diǎn)，其中∈V'。

4）狀態(tài)（state）：狀態(tài)st=(Lt)表示電力物資配送路徑優(yōu)化的部分解，其中Lt包含在步驟t之前所有經(jīng)過的頂點(diǎn)，L0指物資配送中心。

5）獎(jiǎng)勵(lì)（reward）：為了最小化電力物資配送路徑，本文首先假設(shè)成本與路徑長(zhǎng)度成正比關(guān)系，故而將獎(jiǎng)勵(lì)函數(shù)定義為路徑長(zhǎng)度的負(fù)值與滿意度之和，因此獎(jiǎng)勵(lì)值可表示為R=，其中rt是在步驟t的累積增量路徑長(zhǎng)的負(fù)值-disxy與滿意度累積和Hi，可以表示為：

6）策略（policy）：隨機(jī)策略π從s0開始，在每個(gè)時(shí)間步下自動(dòng)選擇一個(gè)頂點(diǎn)，進(jìn)入下一個(gè)狀態(tài)st+1=，這個(gè)過程重復(fù)進(jìn)行，直到完成所有的電力物資配送服務(wù)且滿意度最高。執(zhí)行該策略產(chǎn)生的最終結(jié)果是經(jīng)過的頂點(diǎn)的排列，它規(guī)定了運(yùn)輸車輛訪問每個(gè)頂點(diǎn)的順序，即π={π0，π1，…，πT}，基于鏈?zhǔn)椒▌t，輸出解的概率［17］可表示為：

算法1 基于DQN 的電力物資配送路徑優(yōu)化。

輸入 估計(jì)網(wǎng)絡(luò)權(quán)值θ，目標(biāo)網(wǎng)絡(luò)權(quán)值θ?=θ。

輸出 已訓(xùn)練好的DQN 模型。

初始化：記憶庫大小N；

2.2 網(wǎng)絡(luò)訓(xùn)練與參數(shù)設(shè)置

基于DQN 的電力物資配送路徑優(yōu)化結(jié)構(gòu)主要分為訓(xùn)練和路徑規(guī)劃兩個(gè)部分，結(jié)構(gòu)如圖4 所示。

DQN 算法的核心在于訓(xùn)練神經(jīng)網(wǎng)絡(luò)［18］，為了使DQN 模型適用于電力物資配送路徑優(yōu)化場(chǎng)景，需要獲取該場(chǎng)景下的足夠多的電力物資配送系統(tǒng)的數(shù)據(jù)樣本，利用這些數(shù)據(jù)樣本對(duì)DQN 進(jìn)行訓(xùn)練，通過迭代求解不斷更新網(wǎng)絡(luò)參數(shù)，得到最小均方誤差下的最優(yōu)參數(shù)。對(duì)于路徑規(guī)劃，此時(shí)DQN 已經(jīng)學(xué)習(xí)完所有電力物資配送系統(tǒng)數(shù)據(jù)樣本的特性，因此直接將訓(xùn)練好的DQN 進(jìn)行電力物資配送的路徑優(yōu)化，得到最優(yōu)電力物資配送路徑。本文中網(wǎng)絡(luò)訓(xùn)練相關(guān)參數(shù)設(shè)置如表1所示。

本文使用自適應(yīng)矩估計(jì)（ADAptive Moment estimation，ADAM）算法［19］和隨機(jī)梯度下降（Stochastic Gradient Descent，SGD）法更新神經(jīng)網(wǎng)絡(luò)的參數(shù)集，ADAM 算法與傳統(tǒng)采用固定學(xué)習(xí)率的梯度下降算法不同，它可以在訓(xùn)練過程中自適應(yīng)地更新學(xué)習(xí)率。使用批訓(xùn)練法進(jìn)行訓(xùn)練，訓(xùn)練集大小設(shè)為20 000，驗(yàn)證集大小設(shè)為2 000；測(cè)試時(shí)采取隨機(jī)抽樣，樣本大小設(shè)為500。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)與仿真說明

為了驗(yàn)證本文所提的基于DQN 的電力物資配送路徑優(yōu)化算法的求解效果，下面使用Ko?等［5］設(shè)計(jì)的10 個(gè)算例的數(shù)據(jù)和案例進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證所提算法的實(shí)用性，每個(gè)算例的約束條件的設(shè)置值與文獻(xiàn)［5］一致。每個(gè)算例可描述為在預(yù)先指定的時(shí)間限制內(nèi)需要規(guī)劃從一個(gè)倉庫到一組分散的客戶的貨物運(yùn)輸成本最低的路線，并且不超過運(yùn)輸車輛的油箱容量的行駛里程，以最小化總路程或總成本，車輛的油箱容量有限，可以在需要時(shí)加油，車輛可以在加油站和倉庫加油。

本次實(shí)驗(yàn)所使用的設(shè)備配置為圖靈架構(gòu)GeForce RTX 2080TI 顯卡，Intel Xeon E5-2698 V4 處理器，RAM 64 GB；軟件運(yùn)行環(huán)境為Ubuntu 20.04 操作系統(tǒng)，Python 3.7，PyTorch 1.7 框架。實(shí)驗(yàn)中本文直接將訓(xùn)練好的DQN 用于電力物資配送路徑規(guī)劃中。

3.2 實(shí)驗(yàn)分析

本文DQN 在訓(xùn)練過程的損失變化曲線和獎(jiǎng)勵(lì)值變化曲線分別如圖5～6 所示。圖5中，可以看出隨著迭代次數(shù)的增加，DQN 的損失值在不斷下降，并且在訓(xùn)練迭代次數(shù)達(dá)到1 500 次時(shí)，DQN 已經(jīng)基本可以達(dá)到想要的結(jié)果。圖6中，包含累積迭代獎(jiǎng)勵(lì)值和累積平均獎(jiǎng)勵(lì)值，可以看出訓(xùn)練過程中前1 500 次迭代中獎(jiǎng)勵(lì)值在明顯增加，這意味著電力物資配送的路徑優(yōu)化性能在不斷提高，可以規(guī)劃出路徑最短、運(yùn)輸成本最低以及物資需求點(diǎn)滿意度最高的配送路線的效果越來越好，經(jīng)過2 000 次的迭代后，DQN 基本收斂，不管是迭代獎(jiǎng)勵(lì)值還是平均獎(jiǎng)勵(lì)值基本保持在-1 000 上下浮動(dòng)。

接下來使用10 個(gè)EVRP 案例進(jìn)行仿真實(shí)驗(yàn)，并對(duì)訓(xùn)練好的DRL-EVRP 與ECW［6］、SA 算法［7］求得的結(jié)果以及優(yōu)化軟件求得的最佳解UBest進(jìn)行對(duì)比。對(duì)比結(jié)果如表2 所示，主要比較的是路徑總長(zhǎng)度f、各算法求得的結(jié)果與UBest的差距的百分比Gap以及滿意度累積和Hi，其中物資需求點(diǎn)數(shù)和加油站數(shù)分別為20 和3、路徑長(zhǎng)度即為本文1.1 節(jié)中無向圖頂點(diǎn)間的距離，即空間距離。

由表2 可知，對(duì)于大多數(shù)EVRP 案例來說，DRL-EVRP 求得的結(jié)果都比SA 和ECW 算法求得的結(jié)果更優(yōu)；同時(shí)對(duì)于接近半數(shù)的EVRP 案例，DRL-EVRP 的求解結(jié)果要優(yōu)于UBest的結(jié)果；就平均值來看，DRL-EVRP 的求解結(jié)果分別為f=1 626.00 km、Gap=0.54%和Hi=18.49，顯然比SA 算法和ECW 算法要更優(yōu)。

表2 各個(gè)算法對(duì)不同案例的求解結(jié)果對(duì)比Tab.2 Comparison of solution results of different algorithms for different cases

另外，在求解復(fù)雜度方面，文獻(xiàn)［5］中指出，對(duì)于啟發(fā)式的算法對(duì)每個(gè)案例求解時(shí)間均要小于1 s，但是對(duì)于優(yōu)化軟件求解出的UBest結(jié)果，在求解復(fù)雜模型時(shí)，是非常耗時(shí)的。不過，對(duì)于本文所提的已經(jīng)訓(xùn)練好的DRL-EVRP 測(cè)試每個(gè)案例時(shí)，平均耗時(shí)在可接受的范圍內(nèi)，并且DQN 可以并行運(yùn)行，因此可以減少算法運(yùn)算時(shí)間［20］，從而快速進(jìn)行電力物資配送路徑優(yōu)化。表3 給出了不同算法下求解不同案例所需的時(shí)間，可以看出本文算法平均運(yùn)行時(shí)間為0.131 s，相較于SA 和ECW 算法總體在可接受范圍內(nèi)。

以案例EVRP1 為例，各點(diǎn)的經(jīng)緯度坐標(biāo)信息如表3 所示，其中第0 點(diǎn)為電力物資配送中心，第1～3 點(diǎn)為加油站，其余20 點(diǎn)為電力物資需求點(diǎn)。利用DRL-EVRP 對(duì)其進(jìn)行求解，得到電力物資配送的5 條配送路徑結(jié)果為：1）0-16-14-3-22-0，共432.27 km；2）0-6-9-11-19-21-2-0，共382.04 km；3）0-20-8-23-12-0，共292.43 km；4）0-15-13-10-1-18-0，共393.05 km；5）0-7-17-5-4-0，共274.23 km。合計(jì)得到5 條電力物資配送路徑，其總長(zhǎng)度為1 774.02 km。

表3 各個(gè)算法對(duì)不同案例的運(yùn)行時(shí)間對(duì)比 單位：sTab.3 Comparison of running time of different algorithms for different cases unit：s

表4 案例EVRP1各點(diǎn)的位置信息Tab.4 Location information of each point in case EVRP1

4 結(jié)語

本文針對(duì)電力物資配送路徑優(yōu)化問題，提出了一種基于DRL 的電力物資配送多目標(biāo)路徑優(yōu)化算法DRL-EVRP。首先，將EVRP 描述為無向的完全圖，圖的頂點(diǎn)集分別為物資配送中心、加油站和物資需求點(diǎn)。然后，在充分考慮了電力物資配送區(qū)域的加油站分布情況、運(yùn)輸車輛的載重量約束和車輛油耗等約束下，建立了特別針對(duì)EVRP 的以總運(yùn)輸路徑長(zhǎng)度最短、成本最低、物資需求點(diǎn)滿意度最高為目標(biāo)的電力物資配送模型。最后，基于強(qiáng)化學(xué)習(xí)設(shè)計(jì)了一種基于DRLEVRP 的路徑優(yōu)化求解算法，可快速規(guī)劃出全局最優(yōu)的電力物資配送路線，將電力物資輸送至需求點(diǎn)。通過仿真實(shí)驗(yàn)驗(yàn)證了該算法在求解具有多約束條件下的EVRP 的有效性和收斂性，與ECW、SA 算法相比，該算法總體上具有更好的路徑優(yōu)化效果，能夠規(guī)劃出電力物資配送路徑相對(duì)較短的路線，從而保證及時(shí)將電力物資配送至所有需求點(diǎn)。本文下一步的研究工作考慮將此算法擴(kuò)展到更復(fù)雜的電力物資配送問題上，如具有電力物資配送優(yōu)先級(jí)的EVRP。