李繁菀,張 瑩,華云鵬,李沐陽,陳元暢
(華北電力大學控制與計算機工程學院,北京 102206)
隨著社會經濟的發(fā)展和生活水平的提高,人們對汽車的需求量逐年大幅度上漲,環(huán)境問題也隨之而來,汽車尾氣的排放對環(huán)境造成極其嚴重的影響。面對嚴峻的環(huán)境問題,我國大力推動碳達峰、碳中和各項工作,電動汽車產業(yè)普及率不斷提升[1]。電動汽車一方面滿足人們的短距離出行需求,另一方面它以電作為主要動力源,相比以燃油為驅動的汽車更加節(jié)能和環(huán)保。目前對于路徑規(guī)劃的研究主要針對燃油汽車,而對燃油汽車的路徑規(guī)劃無須考慮電量的因素,該場景不適用于電動汽車。隨著電動汽車的普及,由于電動汽車的特殊屬性以及“里程焦慮”[2],電動汽車的出行規(guī)劃顯得尤為重要。若能有效引導電動汽車用戶選擇可達目的地、能及時充電、行駛時間短、充電時間短的路線行走,出行效率就能有效提高。
本文提出了一種基于逆強化學習(Inverse Reinforcement Learning,IRL)的電動汽車出行規(guī)劃(Electric Vehicle Travel Planning,EVTP)方法,將考慮充電行為的Dijkstra算法作為專家示例以保證專家策略的優(yōu)越性,在對電動汽車進行出行規(guī)劃時須同時考慮電量和路徑兩方面因素,從而得到一條滿足電量可達條件的最優(yōu)路徑。此外,本文還對充電策略進行考慮,在充電時采用部分充電策略以提高充電效率,使充電時間盡可能短。逆強化學習算法旨在對尋找路徑的策略進行學習,因此有別于傳統路徑規(guī)劃算法依賴于路網結構的特性。
電動汽車出行規(guī)劃(EVTP)問題可以拆分為電動汽車路徑規(guī)劃問題(Electric Vehicle Routing Problem,EVRP)以及充電策略問題。電動汽車的路徑規(guī)劃問題會受到電動汽車電池容量的限制,即電動汽車的電量不能低于某個限定最小值。因此,EVRP也可以被建模為受約束的最短路徑規(guī)劃問題,此類問題與經典的最短路徑問題的不同之處在于解決方案必須滿足附加約束,這是典型的NP-hard問題[3]。目前,求解受約束的最短路徑問題大體上可分為兩類方法:精確方法和啟發(fā)式方法。
精確方法通過嚴謹的數學模型或數據結構規(guī)劃問題,利用數學法則或數據結構搜尋的方式求得問題最優(yōu)解[4]。Lu等[5]提出了一種運用整數線性規(guī)劃來求解電動汽車最優(yōu)路線問題的方法,該方法以最小化電動汽車行駛時間為優(yōu)化目標,然而線性規(guī)劃的方法計算復雜度較高,僅在小型實例中有很好的表現,一旦應用在大型路網中往往需要很大的存儲空間而導致方法不可用,因而其效率取決于實際路網的規(guī)模且不可直接遷移到其他未經預處理的路網中。
由于精確方法有較高的計算復雜度而不便應用于實際情況,在此方面有一定改善的啟發(fā)式方法是EVRP中更為常用的一種求解方法。啟發(fā)式方法[4]的主要思想是以當前解為基點,在當前解的鄰域中尋找較優(yōu)解賦給當前解,并繼續(xù)尋找,直到沒有更優(yōu)解為止。Lebeau等[6]對每條路徑計算合并一條新路徑的成本,對可行路徑按成本量排序,再以貪心方式進行歸并得到路徑集。Felipe等[7]采用兩階段啟發(fā)法,在得到初始可行解的基礎上不斷對路徑進行調整,以逐漸靠近最優(yōu)目標,并在每一步更新目標函數的值,反復迭代直到目標函數的值收斂為止。類似地,Dijkstra算法和A*算法[8]在路徑規(guī)劃問題中也被廣泛運用,對其稍加修改也可以運用到EVRP中。Cuch等[3]提出了一種基于A*算法計算電動汽車最優(yōu)路線的方法,并將減少充電行為中的等待時間作為優(yōu)化的一部分。Kobayashi等[9]提出了一種基于Dijkstra算法的電動汽車路線搜索方法,這種方法對于充電行為也有一定的考慮,但未對充電時間作出優(yōu)化。雖然啟發(fā)式方法能有效減少運行時間,但是此類方法仍然不能獨立于實際路網,即其運行效率仍與路網規(guī)模相關,且應用在不同路網時需要重新進行生成鄰接矩陣等數據預處理工作。而本文提出的基于逆強化學習的方法與具體路網結構無關,即在某個路網中訓練得到的模型也能在其他路網中有較優(yōu)的性能。
對于EVTP問題,為得到一條最優(yōu)路徑,除了路徑最短之外,充電策略也是需要重點考慮的因素。Wang等[10]提出了一個基于電量驅動的上下文感知路徑規(guī)劃框架,該算法通過電量的約束限制A*算法對路徑進行搜索,并且對于需要充電而繞路的情況給出了最佳方案。然而,此類方法在到達充電站時仍假設電動汽車會將電量充滿,這并不適用于實際情況。在現實生活中,電動汽車通常只需要使其電量在接下來的路程中不會低于限定值即可,這樣既可以減少充電時間又能滿足可達性。此外,電動汽車的充電函數并不是線性的,電動汽車的充電效率會隨著電量的變化而變化[11]。因此,本文提出了一種更接近于真實情況的充電策略,即分段充電以及部分充電策略。
對于EVTP問題,電動汽車車主通常希望得到一條行駛時間短、充電時間短、充電次數少的可達路徑。因此,目標可形式化表達為
此外,在尋找路徑的過程中還應滿足以下條件:(1)電動汽車選擇的每一個節(jié)點都在路網的點集G中,選擇行走的每一條路徑都在邊集E中;(2)路網中的邊為無向圖,選擇邊(i,j)等價于選擇邊(j,i),即xij=xji;(3)選擇的任意兩個連續(xù)的充電樁之間的電量消耗要小于限制條件,即到達充電樁時的電量大于限定的最小電量;(4)充電次數盡可能少。充電次數越多,充電樁總計服務時間越長[12],從而會降低電動汽車的出行效率。
為將逆強化學習(IRL)算法應用到EVTP問題中,EVTP問題可被建模為馬爾可夫決策過程[13,14]。在此場景中的馬爾可夫決策過程可由以下5元組表示。
(1)狀態(tài)集S。在EVTP問題中,狀態(tài)集S中的每一個狀態(tài)s由當前電動汽車的電量(pow)、與終點的距離比例(distance_ratio)、行走的角度(degree)、繞路情況(loop)組成。通過pow可以判斷當前狀態(tài)是否滿足可達性條件,即行走時電動汽車的電量是否在限定值以上。另外,狀態(tài)值的其他組成部分也是電動汽車選擇路徑過程中需要特別關注的因素,狀態(tài)值中不包含具體位置信息,使得訓練得到的模型在新的路網中也能有較好的表現。
(2)動作集A。由于電動汽車的特性,動作集A中的動作a包含兩類:行走行為和充電行為。在本文的設定中,動作集中共包含10個動作,前8個動作表示行走行為(假設所有的節(jié)點最多有4個鄰接節(jié)點),后2個動作表示充電行為,集中離散化的動作用one-hot編碼[15]表示。在行走行為中,電動汽車的目標是向更接近終點的方向行駛,且需要為之后可能出現的充電行為做準備。因此,行走行為中的前4個動作對某一位置的相鄰點按照(degree,distance_ratio)升序排列,即先按照degree升序排列,若degree相同再按照distance_ratio升序排列;行走行為中的后4個動作對某一位置的相鄰充電站按照上述規(guī)則排序,以便之后選擇充電行為。若選擇動作集中后2個動作,即電動汽車選擇充電行為,在充電行為中本文對于充電量進行了區(qū)分,其中一個動作表示電量充到80%,而另一個動作表示電量充到100%,這種部分充電的策略有利于節(jié)省充電時間。
(3)獎勵r。傳統強化學習算法中的即時獎勵r往往是人為設定的,然而在復雜問題中僅憑經驗通常無法設置最優(yōu)的獎勵值。例如,本文的場景需要同時考慮行走行為以及充電行為,難以人為設置兼顧二者的最優(yōu)獎勵。獎勵是影響強化學習算法性能的重要因素,因此,本文采用基于逆強化學習的方法對獎勵值進行設定[16],通過專家示例以及學習策略過程中得到的軌跡間的交互,求得最優(yōu)的獎勵值。
(4)動作價值Q。Q(s,a)表示選擇了動作a之后直到到達終點的獎勵總和的期望,即
本文用Dueling DQN算法[17]近似動作價值Q,即將某一時刻的狀態(tài)st作為輸入,輸出對每個動作a的價值預測。此時Q值被定義為Q(s,a;θ),其中θ為神經網絡中的參數。
(5)策略π。策略π(st)依據當前狀態(tài)對動作進行選擇。在本文中使用ε-greedy以一定的概率進行探索,即大概率選擇動作價值最大的動作,以極小的概率對動作進行隨機選擇來避免陷入局部最優(yōu)。ε-greedy的計算公式如下:
π(st)=
根據上述5元組,對算法整體流程表示如圖1所示。
圖1 算法整體流程圖
狀態(tài)是馬爾可夫決策過程中的重要組成部分,狀態(tài)的選擇尤為重要。特征是狀態(tài)到真實值的映射,包含一些重要的屬性,且與獎勵值有密切關系。在本文中將EVTP問題的特征定義為5個方面。
(1)電量pow。pow表示電動汽車是否迫切需要充電。此特征用當前狀態(tài)下電動汽車的剩余電量來定義,剩余電量越少越迫切需要充電。
fpow(st)=Soct。
(2)充電時間charge_time。充電時間是電動汽車需要重點考慮的特征之一。充電時間過長會導致旅程時間過長,從而導致效率過低;充電時間過短可能會使電量不能滿足接下來旅程的需要,從而導致目的地不可達。電動汽車的充電時間需要在滿足可達的條件下盡可能短。
fcharge_time(st)=
式中,C表示充電樁節(jié)點的集合;location(t)表示t步所在位置,location(t)∈C即t步時所在節(jié)點為充電樁節(jié)點;charge_index表示充電指示,由t步時選擇的動作決定,charge_index(t)=1即表示在t步時需要充電;ct表示計算得到的在t步時的充電時間。
(3)角度degree。degree表示當前狀態(tài)所在位置與終點的連線以及起點與終點的連線之間的夾角,夾角越小說明電動汽車行駛的方向與終點方向越接近。
fdegree(st)=|getdegree(origin,destination)-getdegree(location(t),destination)|,
fdegree(st)=min(fdegree(st),360-fdegree(st)),
式中,getdegree表示得到兩點之間方位角的函數;origin表示路徑的起點;destination表示路徑的終點。
(4)距離比例distance_ratio。distance_ratio表示當前所在位置與終點的距離以及起點與終點的距離之間的比例關系,比例越小則越接近終點,所有距離均用haversine公式[18]進行計算:
fdistance_ratio(st)=
式中,haversine (A,B)表示點A與點B之間的haversine距離。
(5)繞路loop。loop表示尋找某起點終點對的路徑過程中是否重復訪問某一位置。
式中,runway_history表示電動汽車走過的節(jié)點位置的集合,若當前位置已經在runway_history中,則說明電動汽車已經訪問過該節(jié)點,即出現了繞路。若出現繞路往往說明某步的決策不是最優(yōu),因此并不希望路徑中出現繞路的情況。繞路情況如圖2所示。
圖2 繞路情況
給定起點、終點對(A,H),電動汽車由E到達D后,在D點若根據角度選擇下一個點,極有可能選擇點E,此時便出現了繞路,虛線表示可能出現的繞路情況。
在上述特征中,電量對逆強化學習算法得到的獎勵產生正向影響,充電時間、角度、距離比例、繞路均對獎勵產生負向影響。
在對特征進行選擇時,路徑因素以及充電因素都需要被考慮以適用于EVTP問題,從而得到一條兼顧行駛和充電的最優(yōu)路徑。
除了對特征的選擇外,對動作的選擇在逆強化學習中也十分重要。逆強化學習算法與傳統強化學習算法的區(qū)別僅在于獎勵函數,雖然其算法流程與傳統強化學習相似,但是在得到獎勵函數之后仍需要正向訓練更新Q值來學習策略??捎肣(s,a)近似累計獎勵,即
Q(s,a)=E[rt+γ·rt+1+γ2·rt+2+…|st=s,at=a,μ]。
根據上述設定,需要求得最優(yōu)動作值Q*,最優(yōu)動作值函數基于貝爾曼方程[19],表示如下:
Q*(s,a)=Es′[r+γ·maxa′Q*(s′,
a′)|s,a]。
式中,α和β分別為價值函數和優(yōu)勢函數的參數。
在普通DQN算法中,若想更新某個動作的Q值會直接更新Q網絡,使得該動作的Q值改變。然而在Dueling DQN算法中,由于所有動作的優(yōu)勢函數A值的和為0,不便于對優(yōu)勢函數進行更新,因此Q網絡將優(yōu)先對價值函數進行更新,即相當于對所有動作的Q值均進行更新,從而提升學習效果。Dueling DQN的網絡結構如圖3所示。在得到所有動作的Q值后,ε-greedy可被應用于動作的選擇中。
圖3 Dueling DQN的網絡結構
在馬爾可夫決策過程中,除狀態(tài)和動作外,獎勵也尤為重要。無論是傳統強化學習還是逆強化學習,最基本的假設都是最大化累積的獎勵,因此獎勵的設計非常關鍵。傳統強化學習的即時獎勵通常憑借經驗人為設定,然而像電動汽車出行規(guī)劃等復雜問題,僅憑經驗設置獎勵往往難以精準量化,因此,逆強化學習算法應運而生。本文將逆強化學習方法應用到電動汽車出行規(guī)劃中以得到最優(yōu)的獎勵函數。
逆強化學習的思想與模仿學習有一定的相似之處,均需要借助專家示例庫對問題進行優(yōu)化。行為克隆是最早的模仿學習形式,與行為克隆簡單學習一個狀態(tài)到動作的映射不同,逆強化學習算法中獎勵函數的學習方法原理如下:假設專家策略本身是根據某種獎勵學到的最優(yōu)策略,那么專家示例即可取得最優(yōu)獎勵值。根據此假設,設置參數化的獎勵函數,并且尋找參數使得專家示例的獎勵優(yōu)于其他任意數據,這樣即可求解出獎勵函數。然而,上述“其他任意數據”并不具備可操作性,因此常采用迭代過程:根據當下學到的獎勵函數學習策略并生成軌跡數據,該軌跡數據替代“其他任意數據”,對比專家示例和生成的軌跡數據,來學習下一輪獎勵函數。逆強化學習的流程如圖4所示。
圖4 逆強化學習流程圖
獎勵被定義為線性結構,即特征向量的加權和,表示如下:
r(st)=θTf(st),
式中,θ=[θ1,θ2,…,θK]為K維權值向量,K為特征向量維度;f(st)=[f1(st),f2(st),…,fK(st)]為根據狀態(tài)定義的與獎勵相關的特征向量。因此,一條軌跡ζ的獎勵可以表示為
R(ζ)=∑tr(st)=θTfζ=θT∑st∈ζf(st),
給定Dijkstra算法得到的專家示例集D={ζ1,ζ2,ζ3,…,ζM},其中M為專家示例軌跡的數目,問題轉化為找到參數θ使得專家示例的獎勵最優(yōu)。因此,目標函數如下:
由上述獎勵函數的表示方式,目標函數轉化為
獎勵函數參數θ的更新使用了梯度上升的方法,直到其收斂。為防止過擬合,本文引入了參數θ的L2正則化,目標函數改寫為
式中,λ為正則化參數,且滿足λ>0。
因此,梯度公式變?yōu)閮绍壽E集間特征期望的差異加上正則化項的梯度:
參數θ的更新公式為
θ=θ+α?θJ(θ),
式中,α表示學習率。
經過上述過程的迭代,即可求得最優(yōu)參數θ,從而得到最優(yōu)的獎勵函數。然而,上述算法如果被運用,還需要得到專家示例庫,才可通過與專家策略進行對比求得獎勵函數的參數。
在逆強化學習中,專家示例的選擇會直接影響策略的學習,因此,如何構建專家示例十分關鍵。Dijkstra算法使用了廣度優(yōu)先搜索解決賦權有向圖或者無向圖的單源最短路徑的問題,在路徑規(guī)劃問題中得到了廣泛的應用[23,24]??紤]到Dijkstra算法能生成最短路徑的特點,本文將Dijkstra算法生成的路徑設置為專家示例。然而,傳統的Dijkstra算法只考慮最短路徑的問題,而無法同時考慮選擇充電點以及計算充電時間等充電相關動作,因此需要在傳統Dijkstra算法上做出一定改進。在本文中,給定起點、終點對,需要先利用傳統Dijkstra算法得到最短路徑,再考慮該條最短路徑有哪些點在充電樁節(jié)點的集合中,由這些點作為分割點得到子路徑Sub_path。對于每條子路徑Sub_pathi的耗電量情況進行分析,充電指示charge_index取值如下:
charge_index=
式中,use_power(Sub_pathi)表示子路徑Sub_pathi的耗電量;Soci-1表示電動汽車在最短路徑中第i-1個充電樁節(jié)點時的剩余電量;limitbatt表示電動汽車的最低電量,本文設定limitbatt=0.1。charge_index=1時表示需要充電,即對于某一個路徑中的充電樁節(jié)點,若下一條子路徑耗電量大于剩余電量與最低電量之間的差值,則在該充電樁節(jié)點需要充電。
對于充電的目標電量,本文采取部分充電的策略[25]:若下一條子路徑的耗電量小于等于0.7,則在此充電樁將電量充到0.8;若下一條子路徑的耗電量大于0.7,則此次充電需要將電量充到1。此外,為了更接近現實中的情況,本文也考慮了分段充電的策略,從電量0充到目標電量x的充電時間charge_time如下:
charge_time=
式中,電動汽車的電量達到0.8之前的充電效率高于其電量達到0.8之后的充電效率,這與現實中的設定相同。為簡化運算,本文將電量達到0.8之后所需的充電時間也用線性函數表示。關于電量的充電時間函數如圖5所示。
圖5 充電時間函數
因此,一條包含充電策略的最短路徑可被求得,并將此路徑作為專家示例。Dijkstra算法在較小的路網中有較好的性能,然而當其運用在大型路網中,該算法需要花費很長的時間得到鄰接矩陣,且它的運行效率與路網規(guī)模成正比。而本文基于逆強化學習的方法是在專家示例中學習其行走與充電的策略,這種策略對于不同的路網或大型路網也同樣適用,而無需對模型重新進行訓練。
選用兩個路網分別對模型進行訓練,兩個路網均是北京市路網中的一部分。路網Ⅰ包含76個節(jié)點以及105條邊,緯度為39.893°-39.898° N,經度為116.390°-116.405° E。路網Ⅱ包含75 956個節(jié)點以及101 052條邊,緯度為39.4°-40.4° N,經度為115.8°-117.0° E。路網的數據集由兩部分構成:點集與邊集,其中點集中包含各點的經緯度信息,邊集中包含每條路徑起點、終點的經緯度以及起點、終點之間的距離,由點集與邊集構成的路網如圖6所示。由于充電樁節(jié)點的數據集未公開,且關于充電樁的布局不是本文的研究重點,因此隨機選擇點集中的點作為充電樁,這對實驗結果并不影響。
圖6 北京市部分路網
通過將所提出的方法與以下基準方法進行比較,開展性能驗證。
(1)Dijkstra &完全充電策略(Dijkstra & Full charge)。Dijkstra算法在小型路網中能夠高效地得到最短路徑,但未考慮充電策略。如2.6節(jié)所示,此基準方法對Dijkstra進行改進并采用完全充電策略,即每次在充電樁節(jié)點充電時都將電量充滿,以驗證部分充電策略的有效性。
(2)RL & Dueling DQN。與本文相同,此方法結合Dueling DQN算法對Q值進行近似。然而,強化學習中的獎勵憑借人為經驗進行設置,用此基準方法可驗證逆強化學習算法獲得的獎勵函數的優(yōu)越性。
(3)RL & DQN。與方法(2)相同,此方法的獎勵同樣人為給定,且與方法(2)設置相同的獎勵,并通過經典的DQN算法對Q值進行近似,此方法用來驗證Dueling DQN算法的有效性。
本文從有效性和高效性兩方面對模型進行評價。在有效性評估方面,對于電動汽車的出行規(guī)劃,行駛時間(Tpath)以及充電時間(Tch)兩個基本評價指標尤為重要,直接影響電動汽車的出行效率。此外,充電頻率(Frqch)高會導致充電服務時間長,因此充電頻率也是一個重要的評價指標,本文用路徑中包含的充電次數對該指標進行衡量。除上述3個評價指標外,由于用戶在行駛過程中希望盡可能避免繞路,因此繞路次數也值得關注,這一指標用loop值衡量。因此本文對于有效性的評價指標包括:行駛時間、充電時間、充電頻率、繞路次數。本文用Gap來量化所提出的方法與基準方法之間的差異,前兩個指標的Gap表示為
式中,ExistF表示基準方法的性能,PropF表示本文提出的方法的性能;GapTpath和GapTch分別表示兩種方法之間行駛時間以及充電時間的差異。由于后面兩個指標中PropF的值可能為0,因而直接用兩種方法的差值表示Gap,類似地可表示為
Gap(Frqch)=ExistF(Frqch)-PropF(Frqch),
Gap(loop)=ExistF(loop)-PropF(loop)。
Gap的值越大,說明本文提出的方法性能相對基準方法越好。
對于高效性的評估,使用運行模型所需的時間作為評價指標在不同的模型之間進行比較。模型運行時間越短,說明模型越高效。
表1 路網Ⅰ及路網Ⅱ中本文方法與基準方法的效果比較
通過Gap詳細對比不同方法生成的每條路徑,將起點、終點對相同的路徑歸為一組,路網Ⅰ中的結果對比如圖7所示,路網Ⅱ中的結果對比如圖8所示。本文模型在絕大多數路徑中表現最為優(yōu)秀。
圖7 路網Ⅰ中不同方法生成的路徑結果對比
圖8 路網Ⅱ中不同方法生成的路徑結果對比
為驗證模型的高效性,對路網Ⅰ、Ⅱ模型的運行時間進行對比,如圖9所示。在高效性驗證中,Dijkstra算法在較小的路網中運行時間略微短于強化學習以及逆強化學習模型。然而Dijkstra算法的運行時間與路網規(guī)模強相關,因此在大型路網中,Dijkstra算法的運行時間遠遠長于強化學習模型與逆強化學習模型。這也證明了本文模型在大型路網中的高效性。
圖9 模型運行時間對比
該模型的收斂性如圖10所示,在訓練一定輪數后每一輪獲得的獎勵值趨于穩(wěn)定且神經網絡的參數也逐漸收斂。
圖10 模型收斂性
此外,訓練出來的模型也能較好地直接應用在其他路網上而無需重新訓練,而Dijkstra算法不具備此特點。處理不同的路網時,Dijkstra算法需要重新進行數據預處理而不能將原有模型直接應用在新路網中,即不具備遷移性。本文在兩個未經訓練的新路網中運行模型用以驗證遷移性,在路網Ⅲ和路網Ⅳ中隨機設置起點、終點對運行模型,觀察能否得到可達路徑,利用可達路徑的比例評估不同模型的遷移性。在兩個路網中各模型的可達路徑比例如表2所示,本文模型在兩個路網中均表現最佳。
表2 模型遷移性對比
本文將考慮充電行為的Dijkstra算法生成的軌跡作為專家示例,使用Dueling DQN算法對Q值近似,提出了一種基于逆強化學習的電動汽車出行規(guī)劃方法。該方法能夠有效引導電動汽車用戶選擇一條可達目的地,并且行駛時間短、充電時間短、充電頻率少的路線行走。通過引入分段充電以及部分充電策略,使研究場景更接近現實情況,從而有效地提高了充電效率;并利用北京市真實路網中的部分路網圖對模型進行評估,結果表明,本文提出的方法優(yōu)于其他基準方法。此外,本文方法具有很好的遷移性,可以有效地應用在其他未經訓練的路網中。在后續(xù)的研究中,基于現有方法策略以及實驗結果,本文模型可引入非線性獎勵函數形式,進一步挖掘特征向量之間的聯系以得到更適用的獎勵函數,從而提升模型的性能。