基于深度強化學習的電力物資配送多目標路徑優化

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

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

0 引言

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

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

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

1 電力物資配送建模

1.1 問題描述

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

電力物資配送路徑優化問題可以描述為無向的完全圖G=(V，E)，如圖1 所示。其中頂點集由一個配送中心Vn（n=1，2，…，v）、物資需求點集I={I1，I2，…，Ii}和加油站集F={F1，F2，…，Ff}共同組成，即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)都對應著路徑長度disxy、運輸時間txy和運輸成本cxy。

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

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

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

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

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

4）每次加油后，運輸車輛即為滿油量狀態，且加油次數不限；

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

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

1.2 電力物資配送模型

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

根據上述分析與假設，本文建立的電力物資配送模型的目標函數為：

約束條件為：

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

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

2 基于DQN的電力物資配送路徑優化

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

其中：α是學習率，γ是獎勵的衰減率。不斷對Q 值表進行更新直到達到最終狀態。

在本文電力物資配送路徑優化問題中，環境較復雜，狀態數和動作數較多，Q 值表維度太高會導致Q-learning 算法效率很低，所以本文使用結合改進的指針網絡（Ptr-Net）和Q-learning 的DQN 算法來解決此問題。

2.1 DQN結構

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

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

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

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

DQN 算法使用改進的Ptr-Net 作為Q 值函數來代替Q 值表，本文所使用的神經網絡結構如圖2 所示，它的Q 值函數可近似表示為：

其中：s是當前智能體的狀態；at是智能體在當前狀態下選擇的動作；θ為神經網絡的參數。DQN 算法可以很好地解決狀態空間大且是離散的問題［15］，從而保證數據處理的時效性，快速進行電力物資配送的路徑優化，同時節約存儲空間。

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

神經網絡進行訓練從而更新參數θ，參數更新表示為：

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

本文基于DQN 的電力物資配送路徑優化系統中的Q-learning 算法基本要素可表示為：

1）環境（environment）：電力物資配送網絡。

2）智能體（agent）：電力物資配送路徑優化系統。

3）動作（action）：在電力物資配送路徑優化過程中，動作at可表示為在步驟t選擇G'中一個頂點，其中∈V'。

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

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

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

算法1 基于DQN 的電力物資配送路徑優化。

輸入 估計網絡權值θ，目標網絡權值θ?=θ。

輸出 已訓練好的DQN 模型。

初始化：記憶庫大小N；

2.2 網絡訓練與參數設置

基于DQN 的電力物資配送路徑優化結構主要分為訓練和路徑規劃兩個部分，結構如圖4 所示。

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

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

3 實驗與結果分析

3.1 實驗數據與仿真說明

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

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

3.2 實驗分析

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

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

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

表2 各個算法對不同案例的求解結果對比Tab.2 Comparison of solution results of different algorithms for different cases

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

以案例EVRP1 為例，各點的經緯度坐標信息如表3 所示，其中第0 點為電力物資配送中心，第1～3 點為加油站，其余20 點為電力物資需求點。利用DRL-EVRP 對其進行求解，得到電力物資配送的5 條配送路徑結果為：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 結語

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