鄭 振 唐 菲

（1.武漢軟件工程職業(yè)學(xué)院，湖北 武漢 430205；2.武漢船舶職業(yè)技術(shù)學(xué)院，湖北 武漢 430000）

0 引言

與傳統(tǒng)的內(nèi)燃機汽車相比，新能源汽車效率更高，許多國家都制定了相關(guān)政策來促進新能源汽車的發(fā)展。新能源汽車需要頻繁充電，因此汽車的充電路徑調(diào)度和規(guī)劃系統(tǒng)必不可少。如何讓充電過程更加便捷成為研究的重點。有研究者提出充電樁規(guī)劃方法，例如Cui Qiushi等人建立了混合整數(shù)非線性的多目標優(yōu)化模型，以降低充電站、配電網(wǎng)擴建等聯(lián)合成本。Zhang Ying等人提出了一種面向多標準的充電設(shè)施部署方法，設(shè)計了具有性能保證的充電站放置加速算法。有研究著重分析了充電樁的比例及其使用情況，提出了算法來估算停車充電需求。然而，多數(shù)研究并沒有對充電的路徑進行規(guī)劃。新能源汽車的位置會隨著時間發(fā)生變化，其充電的需求具有時空特性。新能源汽車在慢速充電模式下，汽車需要很長時間才能充滿電，會產(chǎn)生較長的停車時間。在進行路徑規(guī)劃時，需要考慮汽車的剩余電量是否能支持汽車達到充電站。該文研究新能源汽車充電路徑規(guī)劃，以減少總充電時間和為了充電所花費的額外距離作為目標。結(jié)合深度學(xué)習(xí)算法，提出了新能源汽車充電路徑規(guī)劃模型，為用戶規(guī)劃新能源汽車充電路線。

1 優(yōu)化模型

新能源汽車充電路徑規(guī)劃問題的目標是將汽車調(diào)度到合適的充電樁進行充電，以使總的充電時間最小化，并最大限度地縮短新能源汽車從起點到目的地的距離。新能源汽車在充電上花費的總時間包括到充電站的行程時間、排隊時間和實際充電時間。這個問題的解決方案可以簡化為尋找最近的快速充電樁，而忽略電動汽車的排隊時間。如果只考慮電動汽車的排隊時間，策略是選擇具有較少等待充電車輛的充電站。在現(xiàn)實世界中，電動汽車充電調(diào)度問題有以下約束：每輛電動汽車只能選擇一個充電樁進行充電，直到其電池達到上界E；電池中剩余的電量使電動汽車無法到達某些充電站；充電站的快充樁m 、慢充m 的數(shù)量和充電速率有限，導(dǎo)致實際的電池充電時間較長。為了減少在有限數(shù)量的充電站充電所花費的總時間，為汽車設(shè)計最優(yōu)和高效的充電策略更重要。新能源汽車的充電需求具有時空特性。在實際應(yīng)用中，新能源汽車的充電模式可分為慢速充電和快速充電。在慢速充電模式下，汽車產(chǎn)生較長的停車時間。此外，在進行路徑規(guī)劃時，需要考慮汽車的剩余電量是否能支持汽車達到充電站。結(jié)合上述約束，新能源汽車充電路徑規(guī)劃問題的表述如公式（1）所示。

充電路徑規(guī)劃的流程如圖1所示。其中，充電能耗模型模塊計算每輛新能源汽車的行駛用電量，該模塊獲取汽車的參數(shù)，如初始電池電量、到充電站的距離，并輸出EV的耗電量；數(shù)據(jù)預(yù)處理模塊以能耗模型、路網(wǎng)數(shù)據(jù)和充電站數(shù)據(jù)的結(jié)果作為輸入，對原始數(shù)據(jù)進行預(yù)處理，并使用地圖匹配將每個汽車的GPS點映射到相應(yīng)的路段上；汽車和充電站圖模塊用于建立汽車和充電站的分布圖，將用于為汽車充電調(diào)度系統(tǒng)構(gòu)建仿真環(huán)境；路徑規(guī)劃模塊是基于深度Q學(xué)習(xí)的學(xué)習(xí)模型，為所有需要充電的汽車推薦最優(yōu)調(diào)度決策。

圖1 充電路徑規(guī)劃的流程

2 路徑規(guī)劃算法

由于汽車電池的初始剩余電量會影響其充電時間和可用行駛距離，因此使用汽車行駛的距離來預(yù)測相應(yīng)的用電量。通過對實際數(shù)據(jù)的分析可知，汽車的行駛距離與電池電量消耗之間具有近似線性關(guān)系。該文使用線性回歸模型來預(yù)測汽車用電量，如公即式（2）所示。

其中，、如公式（3）、公式（4）所示。

充電路徑規(guī)劃問題是一個順序決策問題，其目的是最大限度地減少充電所花費的總時間，并減少行駛距離。

使用元組，，，，來表示馬爾可夫過程，其中為狀態(tài)集合，為動作集合，為從狀態(tài)S到狀態(tài)S的轉(zhuǎn)移概率，（，）為獎勵函數(shù)，為折扣因子。

汽車充電調(diào)度系統(tǒng)可以定義為一個代理，它通過對所有需要充電的電動汽車的充電站選擇和充電路徑做出一系列決策來完成所有電動汽車的充電。使用馬爾可夫過程模型對汽車充電調(diào)度過程進行建模。

獎勵反映了通過執(zhí)行從狀態(tài)s開始并導(dǎo)致下一個狀態(tài)s的動作觀察到的特定狀態(tài)轉(zhuǎn)換的可取性。

獎勵信號是強化學(xué)習(xí)目標的形式化表現(xiàn)。在訓(xùn)練學(xué)習(xí)的每步中，獎勵是一個實數(shù)值信號。學(xué)習(xí)目標就是獎勵的最大化，但是這個最大化的目標不一定是即時獎勵（即每步行動后環(huán)境反饋給智能體的獎勵），而是從長期角度來看的累計的總體獎勵。用總體獎勵來作為學(xué)習(xí)目標的形式化描述是強化學(xué)習(xí)的區(qū)別于其他人工智能學(xué)習(xí)類型的一個最獨特的特征。路徑規(guī)劃的目標是最大限度地減少所有汽車充電所花費的總時間，并最大限度地縮短汽車的起點和目的地之間的距離。因此，獎勵函數(shù)就具有的形式如公式（5）所示。

充電任務(wù)的最佳調(diào)度需要確定一個固定策略，該策略定義了在步驟t所使用的調(diào)度動作a。學(xué)習(xí)汽車調(diào)度任務(wù)的目標是找到一個最優(yōu)策略，以最大化調(diào)度獎勵的總和。最優(yōu)策略的計算如公見式（6）所示。

將最優(yōu)動作值函數(shù)Q（s，a）定義為智能體狀態(tài)為s并采取最優(yōu)動作a時的最大預(yù)期回報，其定義如公式（7）所示。

使用深度Q網(wǎng)絡(luò)（DQN）對汽車的充電路徑規(guī)劃進行建模。在DQN模型中，近似的動作價值函數(shù)為（s，a；），其中（s，a；）≈Q（s，a）。在學(xué)習(xí)過程中，Q網(wǎng)絡(luò)通過在每次迭代時最小化損失函數(shù)L（θ），并且可以被訓(xùn)練來學(xué)習(xí)動作值函數(shù)的參數(shù)。損失函數(shù)L（θ）的定義如公式（8）所示。

式中：θ為第次更新時神經(jīng)網(wǎng)絡(luò)的參數(shù)。對迭代時神經(jīng)網(wǎng)絡(luò)參數(shù)的損失函數(shù)進行微分，得到公式（9）。

該模型使用隨機梯度下降方法來優(yōu)化損失函數(shù)。為了平衡exploration和exploitation的過程，該模型學(xué)習(xí)了最優(yōu)動作a，同時選擇了隨機動作來確保對狀態(tài)空間的充分探索。即智能體以1-的概率選擇當(dāng)前的最優(yōu)動作，并以的概率選擇一個隨機動作。

3 試驗評估

該節(jié)進行了有效的試驗來評估上述系統(tǒng)。首先描述使用的數(shù)據(jù)集，其次展示試驗結(jié)果。試驗從Open Street Map（OSM）收集道路網(wǎng)絡(luò)數(shù)據(jù)，汽車充電站數(shù)據(jù)來自高德地圖。OSM是一個網(wǎng)上地圖協(xié)作計劃，是由網(wǎng)絡(luò)大眾共同打造的免費開源、可編輯的地圖服務(wù)，其目標是創(chuàng)造一個內(nèi)容自由且能讓所有人編輯的世界地圖。每個充電站數(shù)據(jù)包括充電站ID、充電站位置、充電站經(jīng)緯度坐標（GPS點）、快充樁和慢充樁數(shù)量。

隨機生成汽車的GPS坐標數(shù)據(jù)，將GPS點映射到道路網(wǎng)絡(luò)中的相應(yīng)路段。選擇汽車一定范圍內(nèi)的興趣點（如學(xué)校、銀行、飯店、醫(yī)院）作為目的地。汽車的行駛距離是根據(jù)OSM路網(wǎng)中汽車與充電站之間的最短導(dǎo)航距離計算得出。為了評估電動汽車的排隊時間，采用到達充電站的充電樁數(shù)量和當(dāng)前到達電動汽車的充電時間來估計。

試驗部分評估了充電路徑規(guī)劃模型的有效性。汽車的平均速度為55 km/h，電池的充電上限為900 Ah，下限為200 Ah。深度Q學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)由4個密集連接層組成，每個連接層的神經(jīng)元數(shù)量分別為100個、1024個、512個和4個。激活函數(shù)是整流線性單元，用于訓(xùn)練的優(yōu)化器是Adam，學(xué)習(xí)率為0.0001。

不同參數(shù)設(shè)置下汽車起點到目的點距離減小的概率密度函數(shù)如圖2所示。對=1、=10，距離減少量小于0的概率遠低于=10、=1的情況。其中，距離減少量為負，表明選擇的充電站距離汽車的初始目的地較遠。當(dāng)減少量更接近1時，選擇的充電站更接近汽車的初始目的地。由于受每輛汽車初始剩余電量的影響，電動汽車可以到達的充電站選擇有限。因此，算法對行駛距離的優(yōu)化是有限的，但調(diào)整參數(shù)和可以使充電策略在有限的選擇中更傾向于選擇更接近電動汽車目的地的充電站。

圖2 距離減少量的概率密度函數(shù)

將該文提出的方法與最近鄰基線算法進行比較。最近鄰算法將每輛汽車安排到離它最近的充電站，然后根據(jù)到達時間選擇該站的充電樁，使其最早開始充電。汽車完成充電時間的累計分布函數(shù)如圖3所示。由結(jié)果可知，最近鄰算法的完成充電時間比該文算法長。對該文算法，超過90%的汽車能夠在4 h內(nèi)完成充電。對最近鄰算法，大約20%的汽車充電時間超過了4 h。由于最近鄰算法只考慮距離當(dāng)前充電電動汽車最近的充電站（即最快到達的充電站），而沒有考慮充電站的充電樁數(shù)量和不同充電樁的充電率，所以電動汽車的完成充電時間比該文算法長。

圖3 完成充電時間的累計分布函數(shù)

4 結(jié)論

該文提出了基于深度學(xué)習(xí)的充電路徑規(guī)劃模型，對新能源汽車充電進行調(diào)度。使用真實數(shù)據(jù)集試驗，結(jié)果表明該文所提出的模型減少了充電時間，縮短了車輛的行駛距離。該模型從新能源汽車用戶的角度考慮約束，即汽車的行駛距離限制、不同的充電模型以及充電請求的空間特征。在后續(xù)的研究工作，將計劃利用實時交通和充電站狀態(tài)數(shù)據(jù)來進一步改進該文模型。