基于深度強化學(xué)習(xí)的電力物資配送多目標(biāo)路徑優(yōu)化

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

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

0 引言

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

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

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

1 電力物資配送建模

1.1 問題描述

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

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

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

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

1）物資需求點的需求量最大不超過運輸車輛的載重；

2）一個物資需求點需要且只需要進行一次物資配送；

3）物資運輸車輛行駛速度恒定，加油時間恒定；

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

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

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

1.2 電力物資配送模型

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

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

約束條件為：

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

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

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

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

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

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

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

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

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

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

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

DQN 算法使用改進的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)下選擇的動作；θ為神經(jīng)網(wǎng)絡(luò)的參數(shù)。DQN 算法可以很好地解決狀態(tài)空間大且是離散的問題［15］，從而保證數(shù)據(jù)處理的時效性，快速進行電力物資配送的路徑優(yōu)化，同時節(jié)約存儲空間。

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

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

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

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

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

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

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

輸入 估計網(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ī)劃兩個部分，結(jié)構(gòu)如圖4 所示。

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

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

3 實驗與結(jié)果分析

3.1 實驗數(shù)據(jù)與仿真說明

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

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

3.2 實驗分析

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

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

由表2 可知，對于大多數(shù)EVRP 案例來說，DRL-EVRP 求得的結(jié)果都比SA 和ECW 算法求得的結(jié)果更優(yōu)；同時對于接近半數(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 各個算法對不同案例的求解結(jié)果對比Tab.2 Comparison of solution results of different algorithms for different cases

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

以案例EVRP1 為例，各點的經(jīng)緯度坐標(biāo)信息如表3 所示，其中第0 點為電力物資配送中心，第1～3 點為加油站，其余20 點為電力物資需求點。利用DRL-EVRP 對其進行求解，得到電力物資配送的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。合計得到5 條電力物資配送路徑，其總長度為1 774.02 km。

表3 各個算法對不同案例的運行時間對比 單位：sTab.3 Comparison of running time of different algorithms for different cases unit：s

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

4 結(jié)語

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