車聯(lián)網(wǎng)環(huán)境下電動汽車主動充電引導(dǎo)模型

袁曉冬，甘海慶，王明深，滕欣元，阮文駿，龍 寰

（1.國網(wǎng)江蘇省電力有限公司電力科學(xué)研究院，江蘇省 南京市 211103；2.國網(wǎng)江蘇省電力有限公司，江蘇省 南京市 210024；3.東南大學(xué)電氣工程學(xué)院，江蘇省 南京市 210096）

0 引言

近年來，電動汽車的銷售規(guī)模不斷擴(kuò)大，受到中國政府部門、能源企業(yè)以及汽車制造商的關(guān)注［1-2］。相比于傳統(tǒng)燃油汽車，電動汽車具有綠色經(jīng)濟(jì)的優(yōu)勢［3］。同時，由于具有負(fù)荷和電源雙重性質(zhì)，電動汽車也可參與電網(wǎng)輔助服務(wù)以支撐電網(wǎng)穩(wěn)定控制［4］。電動汽車用戶行為習(xí)慣、各類型電動汽車保有量的變化、電動汽車類型［5］以及充電站選址等因素會導(dǎo)致電動汽車堆積在某一個或某些特定的充電站，特別是在充電行為高峰期［6-7］。因此，國內(nèi)外對電動汽車充電路徑規(guī)劃、選站策略這一課題展開了深入研究。

在電動汽車路徑規(guī)劃方面，由于電動汽車出行路徑、駕駛需求等會影響交通側(cè)道路的順暢程度，交通信息會影響電動汽車充電路徑選擇［8］。同時，隨著城市化進(jìn)程和交通路網(wǎng)的大力發(fā)展，全局搜索算法在計算速度上無法適應(yīng)實際場景的需求［9］。在減小無用搜索方面，文獻(xiàn)［10］指出了A*算法的平均搜索節(jié)點比靜態(tài)Dijkstra 算法減少50%以上。在城市路網(wǎng)場景下，由于路網(wǎng)節(jié)點較多，交通狀態(tài)變化迅速，基于動態(tài)路網(wǎng)的路徑規(guī)劃問題成為研究熱點［11-12］。文獻(xiàn)［13］提出了一種以平均道路速度為權(quán)重的定向交通網(wǎng)絡(luò)模型，旨在通過交通網(wǎng)調(diào)度最小化給定車輛數(shù)的充電時間并提高充電效率。但該文獻(xiàn)將城市路網(wǎng)不同部分的通行速度簡化為不隨時間變化的平均值，未考慮實際路網(wǎng)存在的因轉(zhuǎn)彎、擁堵等情況造成的動態(tài)時間消耗。文獻(xiàn)［14］提出了一種車輛通過車聯(lián)網(wǎng)通信向智能交通系統(tǒng)傳遞基本信息，進(jìn)而利用智能交通系統(tǒng)尋找最優(yōu)充電站的調(diào)度方法。在實驗部分，該文獻(xiàn)將所有車輛在道路上的行駛速度均設(shè)為相同值進(jìn)行仿真，同樣未考慮在實際路網(wǎng)中行駛時存在的不可控因素造成的時間損耗。文獻(xiàn)［15］提出了一種結(jié)合了灰狼優(yōu)化算法和旗魚優(yōu)化算法的灰色旗魚優(yōu)化算法，通過智能交通系統(tǒng)的調(diào)度提高交通效率，進(jìn)而優(yōu)化充電調(diào)度。在案例仿真部分，該文獻(xiàn)設(shè)定電動汽車的速度為恒定值，并以此推算出不同車輛密度下在一定空間范圍內(nèi)電動汽車前往最近充電站的平均距離，進(jìn)而判斷所提出的算法是否有效縮短了電動汽車前往充電站的通行時間。由此可見，現(xiàn)有相關(guān)文獻(xiàn)雖使用了動態(tài)路徑規(guī)劃方法，但在路網(wǎng)建模方面較為粗糙，通行時長常定義為與道路長度相關(guān)的線性函數(shù)。在實際城市路網(wǎng)中，由于存在大量紅綠燈、交通堵塞等情況，簡單地將路網(wǎng)建模為線性模型將與實際情況產(chǎn)生較大的偏差，亟須在路徑規(guī)劃階段精細(xì)化路網(wǎng)的建模以符合實際城市路網(wǎng)場景。

在電動汽車充電站等待時間預(yù)測，特別是短期預(yù)測方面現(xiàn)有研究較少。在車聯(lián)網(wǎng)背景下，文獻(xiàn)［16］權(quán)衡時間感知公平性和電動汽車整體等待時間，提出了一個雙目標(biāo)充放電調(diào)度模型。文獻(xiàn)［17］提出了一種基于時空圖卷積網(wǎng)絡(luò)的電動汽車充電站運行狀態(tài)預(yù)測模型，通過預(yù)測電動汽車充電站使用情況來預(yù)測電動汽車充電等待時間。文獻(xiàn)［18］提出了一種公共充電站占用率預(yù)測模型，對電動汽車用戶等待時間進(jìn)行預(yù)測。但是以上研究中均采用統(tǒng)計方式得到數(shù)據(jù)指標(biāo)，忽視了電動汽車到站的隨機(jī)性和周邊交通路網(wǎng)的實時變化性。文獻(xiàn)［19］介紹了一種考慮“路-車-源-荷”多重不確定性因素的交通網(wǎng)與配電網(wǎng)概率聯(lián)合流分析方法，在考慮擁堵效應(yīng)下電動汽車的等待時間時，將等待時間與電動汽車在該充電站的平均排隊時間相關(guān)聯(lián)而建立關(guān)系式。文獻(xiàn)［20］表明，以單一車輛為例，用戶的充電時間受當(dāng)日或近期的出行規(guī)劃影響較大。文獻(xiàn)［21］以電動出租車為研究對象，對充電站排隊系統(tǒng)內(nèi)的車輛到達(dá)間隔時間和充電時長進(jìn)行了統(tǒng)計分析，建立了M/G/k 排隊論模型，提高了充電站排隊系統(tǒng)的服務(wù)能力。但在車聯(lián)網(wǎng)背景下，利用網(wǎng)聯(lián)的充電站實時數(shù)據(jù)可以更有效地處理用戶的短時傾向，預(yù)測充電等待時長的時變分布，為電動汽車主動充電引導(dǎo)提供依據(jù)。

針對上述問題，本文提出了一種車聯(lián)網(wǎng)環(huán)境下的電動汽車主動充電引導(dǎo)方案?；诟倪M(jìn)A*路徑規(guī)劃算法，求解實時路網(wǎng)狀態(tài)下電動汽車充電路徑時間花費；基于深度置信網(wǎng)絡(luò)（deep belief network，DBN）模型，預(yù)測充電站的電動汽車短時到達(dá)率，采用排隊論M/G/k 模型，完成電動汽車充電等待時間短時預(yù)測，實現(xiàn)電動汽車主動充電引導(dǎo)。

1 電動汽車主動充電引導(dǎo)架構(gòu)

本文提出的車聯(lián)網(wǎng)環(huán)境下的電動汽車主動充電引導(dǎo)方法從用戶角度出發(fā)，目標(biāo)是最小化用戶的時間成本，如式（1）所示。

式中:Ttotal為電動汽車用戶充電綜合時長；Troad為電動汽車路徑行駛時長；Twait為電動汽車充電站排隊等待時間。

電動汽車主動充電引導(dǎo)方法架構(gòu)如圖1 所示。當(dāng)用戶發(fā)出充電需求指令，標(biāo)定出發(fā)點O和備選充電站集合D，對所有備選充電站di∈D，根據(jù)改進(jìn)A*算法進(jìn)行初次路徑規(guī)劃，獲取車輛到達(dá)備選充電站di的預(yù)計路徑行駛總時長troad，i。以時間、物理環(huán)境量、di周邊實時交通狀態(tài)量、di車輛歷史到達(dá)量為輸入，基于DBN 預(yù)測電動汽車到達(dá)量λi，選取歷史充電服務(wù)時長分布，確定di的M/G/k 排隊論模型，以當(dāng)前充電站狀態(tài)和troad，i為初始化狀態(tài)，基于蒙特卡洛（Monte-Carlo，MC）采樣預(yù)測troad，i時間后備選充電站di的充電等待時間twait，i。計算總時間成本ttotal，i，擁有最小ttotal，i的充電站為最優(yōu)備選充電站dbest，其到達(dá)路徑標(biāo)記為最優(yōu)路徑pbest。電動汽車沿推薦最優(yōu)路徑pbest行駛，在從節(jié)點Vi移動到下一個節(jié)點Vi+1前完成如下工作:

圖1 車聯(lián)網(wǎng)環(huán)境下電動汽車主動充電引導(dǎo)方法架構(gòu)Fig.1 Architecture of active charging guidance method for electric vehicles based on Internet of vehicles

1）以當(dāng)前節(jié)點Vi和目標(biāo)充電站di兩點連線外擴(kuò)x距離所組成的矩形為標(biāo)準(zhǔn)，劃定路網(wǎng)狀態(tài)更新區(qū)域A，根據(jù)區(qū)域內(nèi)的道路是否處于非穩(wěn)定時段、是否發(fā)生事故，決定路網(wǎng)信息的更新方式，更新路網(wǎng)時空狀態(tài)矩陣W；

2）使用改進(jìn)A*算法，求解下一個節(jié)點Vi+1至終點di的預(yù)計通行時間troad，i和路徑pi；

3）基于DBN 預(yù)測電動汽車到達(dá)量λi，選取歷史充電服務(wù)時長分布，確定di的M/G/k 排隊論模型，以當(dāng)前充電站狀態(tài)和troad，i為初始化狀態(tài)，基于MC采樣預(yù)測troad，i時間后備選充電站di的充電等待時間twait，i；

4）計算總時間成本ttotal，i，選擇最小ttotal，i的充電站為最優(yōu)備選充電站dbest，其到達(dá)路徑標(biāo)記為最優(yōu)路徑pbest。

車輛按照最優(yōu)路徑pbest向最優(yōu)備選充電站dbest前進(jìn)，直至到達(dá)。

2 電動汽車充電動態(tài)路徑規(guī)劃

2.1 時變路網(wǎng)建模

本文所研究的城市路網(wǎng)區(qū)域包含M條道路、N個道路節(jié)點，可用式（2）所示的圖論G=（V，E，W）方式描述。

式中:節(jié)點V表示N個道路節(jié)點，即路口；邊E表示交通圖G中的M條城市道路。

城市交通的狀態(tài)通常由交通流量、速度和密集度衡量［22］，但在本文的設(shè)定中，電動汽車主動充電引導(dǎo)方案以時間為導(dǎo)向，故將道路通行時長作為路網(wǎng)時空狀態(tài)矩陣W的元素，如式（3）所示。

式中:Eij為0-1 變量，其值取1 表示節(jié)點Vi與節(jié)點Vj存在直連道路，否則其值取0；tij、lij、vij分別為道路（Vi，Vj）的通行時長、長度和平均車速。

由于城市路網(wǎng)較為密集，矩陣W的更新將占用大量的時間和計算資源，故有必要減少矩陣W的更新范圍和頻率。在更新范圍方面，將更新區(qū)域A限定為以電動汽車當(dāng)前節(jié)點Vi與目標(biāo)充電站di兩點為對角線所組成的矩形長寬分別外擴(kuò)x距離的矩形，僅對更新區(qū)域A內(nèi)的路網(wǎng)情況進(jìn)行更新；在更新頻率方面，通過引入道路車速不穩(wěn)定時間段和交通事故狀態(tài)量實現(xiàn)。

2.1.1 道路車速不穩(wěn)定時間段

通過對已有城市交通流量速度的分析，由于早晚高峰的存在，同一條道路的通行速度在一天內(nèi)呈現(xiàn)周期性，傳統(tǒng)將道路通行時長簡單定義為一個關(guān)于道路長度的線性函數(shù)的方式在城市場景下并不適用。因此，為了降低更新頻率，引入道路車速不穩(wěn)定時間段的概念。

基于市內(nèi)各道路平均行駛速度數(shù)據(jù)集，以10 min 為間隔，根據(jù)式（4）計算某道路日平均行駛速度的變化，根據(jù)式（5）計算平均速度變化率。

式中:T為天數(shù)；vt，n為第n天時段t某道路的通行速度；為該道路時段t的平均通行速度；vt，tr為平均通行速度變化率，在本文中，將|vt，tr|＞0.15 的時段設(shè)定為某道路的車速不穩(wěn)定時間段，其余時間段為車速穩(wěn)定時段。因此，對于G內(nèi)的不同道路（Vi，Vj），定義有不穩(wěn)定時段集合={T1，T2，…，Tn}。

在更新矩陣W時，對于更新區(qū)域A內(nèi)的某道路（Vi，Vj），當(dāng)時段t處于不穩(wěn)定時段，矩陣W以1 min的頻率更新；當(dāng)時段t處于穩(wěn)定時段，矩陣W以10 min的頻率更新。

2.1.2 交通事故狀態(tài)量

對于圖G中的每一條道路（Vi，Vj）設(shè)置交通事故狀態(tài)標(biāo)記位，默認(rèn)為0，當(dāng)發(fā)生事故時標(biāo)記1，事故處理完畢標(biāo)記為2，當(dāng)標(biāo)記為2 后5 min 變換為0。在更新矩陣W時，對于更新區(qū)域A內(nèi)的某道路（Vi，Vj），當(dāng)為1 或2 時，按1 min 的頻率更新與道路（Vi，Vj）的首節(jié)點Vi和尾節(jié)點Vj直接相連的路網(wǎng)，以保證獲取路網(wǎng)最新信息。

2.2 基于改進(jìn)A*算法的動態(tài)路徑規(guī)劃

相比于靜態(tài)路徑規(guī)劃Dijkstra 算法，A*算法依靠在決策函數(shù)F（·）中加入預(yù)估項H（·）以規(guī)避搜索明顯對最優(yōu)路徑結(jié)果不產(chǎn)生影響的道路，提高搜索效率［23］。具體地，當(dāng)電動汽車所在道路的后驅(qū)節(jié)點，即下一節(jié)點為Vi時，A*算法的決策函數(shù)如式（6）所示。

式中:F（i）為決策函數(shù)，其值越小，搜索優(yōu)先級越高；G（i）為已知項，在傳統(tǒng)A*算法中即為起點到后驅(qū)節(jié)點Vi消耗的總時間代價，在城市道路中，由于紅綠燈廣泛存在，故本文引入紅綠燈機(jī)制，對已知項G（i）進(jìn)行改進(jìn)；H（i）為預(yù)估項，表示后驅(qū)節(jié)點Vi到終點的預(yù)計時間代價。

圖2 展示了本文對A*算法的2 種改進(jìn)。針對已知項G（i），在城市道路中，由于紅綠燈廣泛存在，故本文引入紅綠燈機(jī)制，對已知項G（i）進(jìn)行改進(jìn)，將紅綠燈等待時間設(shè)置為節(jié)點權(quán)值，加入到已有項G（i）中。在城市路途，特別是短程旅途中，紅綠燈等待時間將成為路徑總耗時的重要組成部分，不可忽略不計。為此，在路徑規(guī)劃的初始化階段，為圖G內(nèi)的每一條道路（Vi，Vj）的后驅(qū)路口節(jié)點Vi初始化紅綠燈等待時間字典。

圖2 A*算法的改進(jìn)Fig.2 Improvement of A* algorithm

如圖2（a）所示，在通過后驅(qū)節(jié)點Vi向終點探索路徑時，Vi有直連節(jié)點Vdir，i={}。根據(jù)式（7），將Vi、∈Vdir，i（u=1，2，3）、車所處節(jié)點Vcar由經(jīng)緯度坐標(biāo)系轉(zhuǎn)換為笛卡爾坐標(biāo)系。

式中:Vi，xyz為節(jié)點Vi的笛卡爾坐標(biāo)；Vi，x、Vi，y、Vi，z為節(jié)點Vi的笛卡爾坐標(biāo)系參數(shù)；R為地球半徑；Vi，lat和Vi，lon分別為節(jié)點Vi的緯度和經(jīng)度參數(shù)。

式中:Vcar，xyz、分別為節(jié)點Vcar、的笛卡爾坐標(biāo)。

將紅綠燈等待時間計入此條探索路徑的已有項Gnew（）中，參與A*算法后續(xù)更新，如式（11）所示。

式中:WEi，u為節(jié)點Vi到節(jié)點V(u)i所耗費的通行時長；tLight為根據(jù)夾角θ(u)dir，i從紅綠燈等待時間字典t(Vi，Vj)Light中選取的等待時長。

針對預(yù)估項H（i），傳統(tǒng)A*算法采用當(dāng)前點到目標(biāo)點的歐氏幾何距離作為預(yù)估項，但在實際生活中，車主大多會傾向于選擇調(diào)頭較少的路徑，即不走回頭路。因此，本文在歐氏距離的基礎(chǔ)上加入回頭路懲罰項。

如圖2（b）所示，在距離終點Vdi有相同歐氏距離的3 個點中，車主更傾向于選擇或以避免調(diào)頭行為。因此，本文將節(jié)點Vi的預(yù)估項H（i）定義為式（12）。

式中:si為節(jié)點Vi到終點Vdi的歐氏距離；vavg為電動汽車平均行駛速度；為起點Vo、節(jié)點、終點Vdi所構(gòu)成的夾角，可由式（7）—式（10）計算得出；ω為懲罰系數(shù)。

基于改進(jìn)A*算法的動態(tài)路徑規(guī)劃算法流程如圖3 所示。

圖3 基于改進(jìn)A*算法的動態(tài)路徑規(guī)劃算法流程Fig.3 Flow chart of dynamic path planning algorithm based on improved A* algorithm

3 充電站等待時間預(yù)測

電動汽車充電方式分為快充和慢充，慢充大多在午夜進(jìn)行，充電時長為7～10 h，對充電引導(dǎo)的需求不大［24］。因此，本文僅考慮城市內(nèi)電動汽車選用快充樁進(jìn)行快充的充電引導(dǎo)場景。電動汽車在充電站的充電行為滿足排隊模型，在此排隊系統(tǒng)中，服務(wù)臺數(shù)目為站內(nèi)快充樁數(shù)目k，隊列容量大小為∞，服務(wù)規(guī)程為單一隊列先到先服務(wù)。因此，需要確定電動汽車到達(dá)和服務(wù)時長的數(shù)學(xué)特征以確定排隊模型的具體類型。本文通過歷史數(shù)據(jù)分析充電站到達(dá)車輛數(shù)據(jù)分布和電動汽車充電時長分布，確定排隊模型為M/G/k。

3.1 充電站到達(dá)車輛數(shù)據(jù)分布

本文對某城市中心區(qū)域5 個電動汽車充電站06:00—21:00 的歷史數(shù)據(jù)進(jìn)行解析，以20 min 為單位統(tǒng)計到達(dá)車輛數(shù)，每天每站共計45 段數(shù)據(jù)。利用Kolmogorov-Smirnov 檢驗（K-S 檢驗）確定數(shù)據(jù)是否服從如式（14）所示的泊松分布。

式中:X為隨機(jī)變量；λ為單位時間內(nèi)隨機(jī)事件的平均發(fā)生次數(shù)，即車輛到達(dá)率。

檢驗結(jié)果表明p-value 均大于0.05，不拒絕原假設(shè)，即可以認(rèn)為充電站到達(dá)車輛數(shù)服從泊松分布。到達(dá)車輛數(shù)泊松分布部分K-S 檢驗結(jié)果見表1。

表1 到達(dá)車輛數(shù)泊松分布部分K-S 檢驗結(jié)果Table 1 Partial K-S test results for Poisson distribution of numbers of arriving vehicles

3.2 基于DBN 的電動汽車到達(dá)量預(yù)測

根據(jù)歷史數(shù)據(jù)可以發(fā)現(xiàn)，在相同日類型下，電動汽車到達(dá)量的變化趨勢相似［25］，考慮到電動汽車用戶充電行為的隨機(jī)性和實時性，鑒于神經(jīng)網(wǎng)絡(luò)模型在非線性建模、噪聲容錯、泛化能力等方面的突出優(yōu)勢，本文采用基于DBN 的單位時間電動汽車到達(dá)量短期預(yù)測模型。

本文選取的模型輸入特征為歷史車輛到達(dá)情況、時間、氣象情況、環(huán)境溫度、日類型、交通狀況等6 類，數(shù)據(jù)需經(jīng)矢量化處理和歸一化處理。輸入層數(shù)據(jù)包括預(yù)測時段前3 個時段、前3 日同時段、前3 個同一類型日（工作日/節(jié)假日）同時段的所有特征。輸出為t時段的電動汽車到達(dá)量預(yù)測值λ。

DBN 模型的輸入層和輸出層之間由r個受限玻爾茲曼機(jī)（restricted Boltzmann machine，RBM）和1 個全連接層堆疊而成，分為無監(jiān)督預(yù)訓(xùn)練和有監(jiān)督微調(diào)2 個階段［26］，如圖4 所示。

圖4 DBN 結(jié)構(gòu)示意圖Fig.4 Schematic diagram of DBN structure

在無監(jiān)督預(yù)訓(xùn)練階段，RBM 采用最大似然估計的方式訓(xùn)練，期望獲得最小能量，其參數(shù)優(yōu)化目標(biāo)函數(shù)如下:

式中:Ts為樣本數(shù)；J（·）為RBM 的能量函數(shù)；參數(shù)θ=(a，b，Wpar)，其中，a為可視層參數(shù)，b為隱含層參數(shù)，Wpar為可視層和隱含層之間的權(quán)重矩陣；h為隱含層表示在特定樣本ts下的可視層的狀態(tài)。利用對比散度算法求解最優(yōu)參數(shù)。

在有監(jiān)督微調(diào)階段，基于交叉熵構(gòu)建損失函數(shù)，并構(gòu)建RBM 優(yōu)化目標(biāo)函數(shù)，如式（16）所示。

本文選用平均絕對誤差（mean absolute error，MAE）和均方根誤差（root mean square error，RMSE）作為評價指標(biāo)。

3.3 電動汽車充電時長分布

在此排隊模型中，服務(wù)時長即為電動汽車在充電站的充電時長。本文對上文所述的5 個充電站相同觀測時段內(nèi)的電動汽車充電時長數(shù)據(jù)進(jìn)行分析。

由圖5 可知，以充電站為劃分依據(jù)，所選站的電動汽車充電時長顯然不服從于已有文獻(xiàn)所指出的負(fù)指數(shù)分布、正態(tài)分布或伽馬分布［27-29］，而近似服從于式（17）所述的混合高斯分布。

圖5 充電站1 中充電時長統(tǒng)計分布Fig.5 Statistical distribution of charging duration at charging station 1

式中:Tch為充電時長分布；NG為高斯分布組件數(shù)；ai為混合高斯分布的權(quán)重；N（μi，）為標(biāo)準(zhǔn)高斯分布，其中，μi為均值，為方差?；谕怀潆娬就粫r段的電動汽車充電時長歷史數(shù)據(jù)，通過計算混合高斯模型的貝葉斯信息準(zhǔn)則（Bayesian information criterion，BIC）并與其他模型進(jìn)行比較，以此來評估模型的擬合優(yōu)度，較低的BIC 值通常表示更好的模型。因此，選擇BIC 值最小的模型，確定高斯分布的數(shù)量，對于每一個高斯分布組件，獲取其權(quán)重ai、均值μi和方差σ2i，得到充電站i電動汽車充電時長分布。

3.4 電動汽車充電站等待時間預(yù)測

基于以上分析，本文所研究的電動汽車在充電站充電符合M/G/k 排隊模型。由于M/G/k 排隊論問題暫無解析解，故本文采用MC 采樣的方法獲取電動汽車充電等待時間的短期預(yù)測。

對于目標(biāo)充電站di，首先構(gòu)建單隊列排隊模型，接著以車聯(lián)網(wǎng)獲取的充電樁實時信息初始化模型，通過DBN 獲取當(dāng)前時段的車輛到達(dá)率λi，t，將其代入式（14）獲得當(dāng)前時段t的電動汽車到達(dá)量分布Pi，t，結(jié)合電動汽車充電時長分布Tch，i，通過MC 采樣獲取troad，i后（即車輛到達(dá)后）的電動汽車充電站平均等待時長，以此作為twait，i。具體步驟如下:

1）建立了k個隊列用于仿真充電站中的k個充電樁，根據(jù)樁當(dāng)前的狀態(tài)（剩余充電時間）初始化k個隊列，如果樁未被占用，則存入0；

2）根據(jù)3.2 節(jié)和3.3 節(jié)所得的分布，采樣得出未來時間troad，i內(nèi)車輛到達(dá)的時間點和充電時長；

3）以先來先服務(wù)的模式模擬未來時間troad，i內(nèi)車輛到達(dá)和排隊的情況（即優(yōu)先選擇隊伍等待時間較短的隊伍進(jìn)行等待），記錄下時間troad，i后車輛的等待時間；

4）循環(huán)足夠多次取平均值（即電動汽車充電站平均等待時長）作為twait，i。

4 實例分析

本文選取中國南京市中心區(qū)域城市路段進(jìn)行實例分析，地圖數(shù)據(jù)來源于開源平臺OpenStreetMap，并通過開源地理信息系統(tǒng)QGIS 進(jìn)行處理，其中，共有149 個路口節(jié)點、233 條道路、5 個充電站節(jié)點，見附錄A 圖A1。本文的計算環(huán)境為單個16 核CPU（3.80 GHz AMD Ryzen7 5700G with Radeon Graphics），集成開發(fā)環(huán)境為PyCharm。

4.1 基于改進(jìn)A*算法的動態(tài)路徑規(guī)劃

為了驗證動態(tài)路網(wǎng)狀態(tài)信息對路徑規(guī)劃結(jié)果的影響，將本文設(shè)計的基于改進(jìn)A*算法的動態(tài)路徑規(guī)劃算法與靜態(tài)Dijkstra 算法進(jìn)行比較，結(jié)果如圖6所示。

圖6 基于改進(jìn)A*算法的動態(tài)路徑規(guī)劃算法與靜態(tài)Dijkstra 算法結(jié)果比較Fig.6 Result comparison between dynamic path planning algorithm based on improved A* algorithm and static Dijkstra algorithm

設(shè)定案例的電動汽車起始點為節(jié)點4，范圍內(nèi)有2 個充電站，分別在節(jié)點2 和節(jié)點6。初始動態(tài)算法與靜態(tài)算法的規(guī)劃路徑均為［4，3，2］，在40 s 后，網(wǎng)聯(lián)數(shù)據(jù)檢測到節(jié)點3-節(jié)點2 路段發(fā)生事故，通行速度放緩，此時車輛正行駛在節(jié)點4-節(jié)點3 的路段上，動態(tài)算法開始更新路網(wǎng)時空狀態(tài)矩陣W，并重新基于改進(jìn)A*算法再次進(jìn)行路徑規(guī)劃，耗時25 ms，規(guī)劃出新路線［4，3，81，97，94，6］，雖然選擇了路程較長的路徑，但是成功繞過擁堵路段。動態(tài)規(guī)劃路線路徑行駛時間為429.2 s，靜態(tài)規(guī)劃算法路徑行駛時間為496.8 s。結(jié)果表明，本文提出的基于改進(jìn)A*算法的動態(tài)路徑規(guī)劃算法可以實現(xiàn)車輛實時引導(dǎo)，規(guī)避交通擁堵路段，實現(xiàn)最小化通行時間。

為了驗證改進(jìn)A*算法的高效性，在區(qū)域內(nèi)使用Dijkstra 算法和改進(jìn)A*算法，并在求解過程中進(jìn)一步使用小根堆數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化，分別隨機(jī)進(jìn)行5 000 次路徑規(guī)劃，計算耗時結(jié)果如表2 所示。結(jié)果表明，改進(jìn)A*算法由于增加了方向性限制，減少了無效的空間搜索，較Dijkstra 全局靜態(tài)路徑規(guī)劃算法計算效率提高了73.67%，采用小根堆結(jié)構(gòu)的改進(jìn)A*算法將尋找F（·）最小值的時間復(fù)雜度從O（n）下降為O（logn），故其計算效率進(jìn)一步提高。由上述2 個實驗可以表明，基于改進(jìn)A*算法的動態(tài)路徑規(guī)劃可以滿足城市導(dǎo)航所需的高效性和及時性需求。

表2 區(qū)域內(nèi)隨機(jī)5 000 次路徑規(guī)劃不同算法計算時間Table 2 Calculation time of different algorithms for 5 000 random path planning within region

4.2 基于DBN 的電動汽車到達(dá)量預(yù)測

采用充電站1 于2021 年5 月至2022 年2 月的實際運行數(shù)據(jù)，以及期間的氣象、溫度、類型日、交通數(shù)據(jù)，經(jīng)矢量化和歸一化處理后，作為輸入數(shù)據(jù)。分別用本文所述DBN 模型、隨機(jī)森林（random tree，RF）模型、支持向量機(jī)（support vector machine，SVM）模型、決策樹（decision tree，DT）模型獲取預(yù)測結(jié)果，如表3 所示。結(jié)果表明，DBN 相比于其他3 種算法，其MAE 和RMSE 均較低，且誤差可以接受，該算法可深入挖掘車輛到達(dá)率與輸入特征間的關(guān)系，精度相對較高，可以用于預(yù)測電動汽車充電站的到達(dá)率。

表3 不同預(yù)測算法性能比較Table 3 Performance comparison of different prediction algorithms

4.3 電動汽車主動充電引導(dǎo)算例

為了驗證本文所提主動充電引導(dǎo)模型的有效性，本實驗取一典型日的交通狀況、氣象狀況、溫度狀況，在區(qū)域內(nèi)隨機(jī)生成900 輛有充電需求的電動汽車，分別按本文所述主動充電引導(dǎo)方案和靜態(tài)路徑充電引導(dǎo)方案（以下簡稱“靜態(tài)引導(dǎo)”）進(jìn)行實驗，其中，靜態(tài)引導(dǎo)采用Dijkstra 最短路徑靜態(tài)路徑規(guī)劃算法，選取路程最近的充電站進(jìn)行充電引導(dǎo)。統(tǒng)計所有電動汽車路徑行駛總時長∑troad、充電站排隊等待時間總時長∑twait和電動汽車用戶充電總綜合時長∑ttotal。下降率按式（18）計算所得，實驗結(jié)果如表4 所示。

表4 主動充電引導(dǎo)算法與靜態(tài)引導(dǎo)算法充電結(jié)果對比Table 4 Charging results of active charging guidance algorithm and static guidance algorithm

式中:dcomp為下降率；tsta為采用靜態(tài)方法進(jìn)行引導(dǎo)的時間；tpaper為采用本文方法進(jìn)行引導(dǎo)的時間。

表4 結(jié)果表明，本文所提主動充電引導(dǎo)方案在減少路途時間以及減少充電站等待時間方面都效果顯著。路徑行駛時長下降18.49%，充電站排隊等待時間下降31.67%，充電綜合時長下降27.27%，驗證了本文所提電動汽車主動充電引導(dǎo)方案在車聯(lián)網(wǎng)及城市路網(wǎng)背景下的有效性。

在以上實驗的基礎(chǔ)上，計算區(qū)域內(nèi)5 個充電站的等待車輛數(shù)量和充電站充電樁使用率。如圖7（a）所示，在采用靜態(tài)算法引導(dǎo)時，由于充電需求和規(guī)劃因素，充電站1 和充電站3 聚集大量車輛，使得這2 個站的充電等待時間較長；采用本文主動充電引導(dǎo)方法后，電動汽車被主動引導(dǎo)至其余充電站，各充電站等待車輛數(shù)均處于低位。如圖7（b）所示，主動充電引導(dǎo)方法的對應(yīng)整點時刻充電樁占用率明顯高于基于靜態(tài)算法的引導(dǎo)充電方法，改善了基于靜態(tài)算法的引導(dǎo)充電導(dǎo)致的充電站使用率不平衡問題，該區(qū)域15:00—16:00 時段充電站的平均利用率由69.50%提升至89.47%，論證了本文所提車聯(lián)網(wǎng)環(huán)境下電動汽車主動充電引導(dǎo)方案可以提高充電樁的利用率。

圖7 5 個充電站的等待車輛數(shù)量和充電樁占用率實驗結(jié)果Fig.7 Test results of number of waiting vehicles and utilization rate of charging piles at five charging stations

5 結(jié)語

本文利用車聯(lián)網(wǎng)環(huán)境下電動汽車動態(tài)信息，提出了一種基于改進(jìn)A*路徑規(guī)劃與排隊論的電動汽車主動充電引導(dǎo)模型。融入紅綠燈等待時間和不走回頭路思想，改進(jìn)城市路徑規(guī)劃A*算法中的已有項G（·）和估算項H（·），利用實際路網(wǎng)狀態(tài)信息更新路網(wǎng)時空狀態(tài)矩陣，求解電動汽車充電路程花費時間，確保電動汽車在到達(dá)下一個節(jié)點前獲取最優(yōu)規(guī)劃行駛路徑。確定充電站到達(dá)車輛數(shù)以及電動汽車充電時長分布，基于DBN 預(yù)測電動汽車到達(dá)量，確定更新策略，采用排隊論M/G/k 模型，利用MC 采樣預(yù)測短時間內(nèi)電動汽車充電等待時間。根據(jù)電動汽車充電路程花費時間和電動汽車充電等待時間，提出電動汽車主動充電引導(dǎo)方法。本文創(chuàng)新和貢獻(xiàn)如下:

1）改進(jìn)A*算法并應(yīng)用于城市場景下的動態(tài)路徑規(guī)劃，在車聯(lián)網(wǎng)環(huán)境下，確保電動汽車行駛路徑最優(yōu)，并驗證了其準(zhǔn)確性。

2）基于DBN 算法預(yù)測充電站車輛到達(dá)量，充電站等待時長短時預(yù)測采用M/G/k 模型具有普適性。

3）提出了用戶視角下考慮路徑行駛時間和充電站等待時長的主動充電引導(dǎo)方案，并驗證了其高效性。

在本文研究中，對于價格因素對電動汽車車主選站的影響考慮得并不充分，且只為用戶給出了一個最優(yōu)充電站和其匹配的最優(yōu)充電路徑，未給出后備方案。未來，可將深度強化學(xué)習(xí)算法引入路徑規(guī)劃中，使其更為高效；通過增加價格因素，以系統(tǒng)最優(yōu)和用戶均衡為目標(biāo)對電動汽車用戶的充電需求進(jìn)行分配，進(jìn)一步減少用戶的充電成本，提高充電站的利用率。

附錄見本刊網(wǎng)絡(luò)版（http：//www.aeps-info.com/aeps/ch/index.aspx），掃英文摘要后二維碼可以閱讀網(wǎng)絡(luò)全文。