用A 星算法進(jìn)行電動汽車快充電樁布局優(yōu)化分析

常 昊，郭明昊，秦林杰，吳浩民，焦烯奧

（南京工程學(xué)院 電力工程學(xué)院，江蘇 南京）

引言

隨著中國經(jīng)濟(jì)迅猛發(fā)展，中國的汽車保有量在不斷增加，由于近年來對環(huán)境保護(hù)的要求也在不斷提高，新能源電動車無疑成了代替燃油車的最佳選擇。伴隨電動汽車市場的興起，充電樁及其配套基礎(chǔ)設(shè)施成為重要需求。因此，相關(guān)電動汽車企業(yè)在充電樁建設(shè)方面投入了大量的資金，許多充電樁被安置在城市內(nèi)，為電動汽車提供了充足的能源保障。

然而，目前電動汽車充電樁存在著一樁難求、城鄉(xiāng)分布不均勻、多樁閑置、技術(shù)隱患大、電價不統(tǒng)一等問題，這將嚴(yán)重制約著電動汽車的發(fā)展。因此，對充電樁進(jìn)行優(yōu)化布局，是推動新能源電動汽車發(fā)展的重要舉措。

充電樁主要有“快充”和“慢充”兩種類型，由于“快充電樁”可以適應(yīng)市內(nèi)巨大的交通車流量，我們選取江蘇南京市作為研究對象，對市內(nèi)“快充電樁”分布進(jìn)行優(yōu)化布局。我們研究此問題主要使用了“A 星算法”（即“A-star 算法”），根據(jù)文獻(xiàn)[1]，“A 星算法（也稱為A*算法）”是基于“Dijkstra 算法”的一種典型的、啟發(fā)式的最短路徑搜索算法，其本質(zhì)是從起點開始搜索代價值最小的節(jié)點作為下一次搜索的起點，直到搜索到目標(biāo)節(jié)點為止，由于搜索從一開始就保證代價估計值是最小的，最終得到的路徑代價值也同樣最小。

該算法被廣泛運(yùn)用于最優(yōu)路徑規(guī)劃等問題，我們將運(yùn)用它進(jìn)行南京市新能源電動汽車充電樁的優(yōu)化布局分析

1 A 星算法

1.1 “Dijkstra 算法”

“A 星算法”的思路來源于“Dijkstra 算法”，這是一種“半啟發(fā)式搜索路徑算法”，以求起始結(jié)點與區(qū)域中所有其他結(jié)點的估價函數(shù)來獲得最短路徑。

根據(jù)文獻(xiàn)[2]，“Dijkstra 算法”的執(zhí)行過程定義如下（程序流程如圖1 所示）：

圖1 “Dijkstra 算法”程序的流程

（1） 定義名為OPEN 和CLOSED 的兩個表；OPEN 用于存放未考察過的結(jié)點，CLOSED 表用于存放已考察過的結(jié)點。

（2） 假設(shè)圖中共有n 個結(jié)點，選取結(jié)點VS 為起點，目標(biāo)結(jié)點為Vi（除VS 的其余結(jié)點，i≤n），將起點VS 放入CLOSED 表中，Vi 放入OPEN 表中。

（3） 判斷OPEN 表是否為空，為空的話表示搜索過程失敗。

（4） 如果不為空的話，計算CLOSED 表中的結(jié)點與Vi 的距離，并將距離最短的結(jié)點Vi 移入CLOSED 表。

（5） CLOSED 表每加入一個新結(jié)點Vi 后要對OPEN 表中各個結(jié)點的最短路徑長度進(jìn)行更新。

（6） 跳轉(zhuǎn)到步驟（4），直至OPEN 表為空。

然而，“Dijkstra 算法”以求起始結(jié)點與區(qū)域中所有其他結(jié)點的估價函數(shù)獲得最短路徑，該算法涉及區(qū)域大、搜索效率較低，難以適用于多障礙、多線路的復(fù)雜最優(yōu)路徑規(guī)劃問題，因此我們選用根據(jù)該算法改良的“A 星算法”。

1.2 “A 星算法”的概念

“A 星算法”在“Dijkstra 算法”的基礎(chǔ)上引入了啟發(fā)函數(shù)，加快了算法收斂速度，由文獻(xiàn)[2]知道，“A 星算法”是一種啟發(fā)式搜索算法，即通過評價函數(shù)對網(wǎng)格上的點進(jìn)行價評估來啟發(fā)式地尋找目標(biāo)結(jié)點，基于最小的代價來尋找通往目標(biāo)結(jié)點最短且最適合的路徑。

A 星算法的估價函數(shù)如下：

式中：f(x,y)表示當(dāng)前結(jié)點到目標(biāo)結(jié)點的估計距離；g(x,y）表示當(dāng)前結(jié)點到考察結(jié)點的實際距離（即既定代價）；h(x,y)表示考察結(jié)點到目標(biāo)結(jié)點的估計距離（即估計代價）。

不同于傳統(tǒng)的“遺傳算法”、“Dijkstra 算法”，此算法的核心是在質(zhì)點移動的過程中對起始結(jié)點到當(dāng)前結(jié)點的既定代價與當(dāng)前結(jié)點到目標(biāo)結(jié)點的估計代價進(jìn)行實時運(yùn)算，在網(wǎng)格模型中起止位置間對每一個結(jié)點進(jìn)行目標(biāo)路徑搜索，最終可以得出最優(yōu)規(guī)劃路徑，因此該方法具有啟發(fā)性和靈活性。

“A 星算法”尋找路徑方式程序的大體思路如圖2 所示，其中“OPEN 集合”表示未訪問的結(jié)點，“CLOSE 集合”表示已經(jīng)訪問過的結(jié)點。

圖2 “A 星算法”程序的流程

（1） 我們選定起始點為“START 結(jié)點”，從START開始，將該結(jié)點首先放入OPEN 集合的列表中。

（2） 對起始點START 的周圍結(jié)點進(jìn)行處理，通常在網(wǎng)格圖中結(jié)點周圍有8 個方位，將這8 個方位的父結(jié)點設(shè)為該“START 結(jié)點”，同樣放入OPEN 集合的列表中。

（3） 待周圍結(jié)點全部搜索完畢后，將初始“START 結(jié)點”從OPEN 集合中移除，并放入CLOSE集合中。

（4） 先遍歷這些預(yù)處理的點，判定其是否為“可用結(jié)點”（不是障礙結(jié)點或不在CLOSE 集合中）。若確定為“可用結(jié)點”，則計算那些處理結(jié)點的f(x,y)、g(x,y)、h(x,y)值，同時在計算的過程中比較各個結(jié)點既定代價、估計代價的大小，每輪循環(huán)都將估價函數(shù)值最低的結(jié)點排在OPEN 集合里面；若確定為“不可用結(jié)點”，則將這些結(jié)點直接放入CLOSE 集合中。

（5） 若某個處理結(jié)點已在OPEN 集合中，檢查使用新的路徑算出的估價函數(shù)是否更低，如果更低，則進(jìn)行結(jié)點更新，并實時調(diào)整目標(biāo)路徑，更新時也需要及時調(diào)整當(dāng)前各結(jié)點的估價函數(shù)大小排序，否則不更新。

（6） 最后判斷該結(jié)點相鄰方格是否為終點，如果不是，則重復(fù)第（4）、第（5）步，如果是，則結(jié)束估價函數(shù)運(yùn)算排序程序，根據(jù)之前每個經(jīng)過結(jié)點周圍已存在的父節(jié)點，反向標(biāo)記，找到終點并輸出最終優(yōu)化路徑，最后結(jié)束全部程序。

1.3 “曼哈頓距離”和“歐幾里得距離”

A 星算法的估價函數(shù)h(x,y)表示當(dāng)前結(jié)點到目標(biāo)結(jié)點的估計距離（即估計代價），主要可以由“曼哈頓距離”與“歐幾里得距離”表示，h(x,y)也分別對應(yīng)著曼哈頓啟發(fā)函數(shù)與歐幾里得啟發(fā)函數(shù)，因此得到最終目標(biāo)路徑的結(jié)果取決于h(x,y)所使用的啟發(fā)函數(shù)。

由文獻(xiàn)[3]和文獻(xiàn)[4]得知，本算法使用的有曼哈頓算法和歐幾里得算法。

曼哈頓啟發(fā)函數(shù)為：

式中：D 表示一個柵格的曼哈頓距離；c 表示當(dāng)前結(jié)點；goal 表示目標(biāo)結(jié)點。

歐幾里得啟發(fā)函數(shù)為：

式中：c 代表當(dāng)前結(jié)點；goal 代表目標(biāo)結(jié)點。

因為歐幾里得距離接近兩點最短距離，所以得到的路徑為最短距離，同時結(jié)合曼哈頓啟發(fā)算法，可以保證路徑的穩(wěn)定性，計算后得到最優(yōu)途徑路線。

“曼哈頓距離”取決于考察結(jié)點與起始結(jié)點、終止結(jié)點的正交型距離（如圖3 所示），在網(wǎng)格圖中操作處理和運(yùn)算較為方便，但是要求單位網(wǎng)格邊長遠(yuǎn)小于目標(biāo)路徑長度以減小誤差；而“歐幾里得距離”則直接量取起點和終點間的直線距離，即為兩點間最短距離（如圖4 所示），誤差小、準(zhǔn)確性高，但是對程序匯編的要求較高，運(yùn)算相對復(fù)雜。

圖3 曼哈頓距離

圖4 歐幾里得距離

我們目前在對充電樁優(yōu)化布局的研究中主要使用的是“曼哈頓啟發(fā)函數(shù)”，今后可能根據(jù)“歐幾里得啟發(fā)函數(shù)”對“A 星算法”進(jìn)行改良，進(jìn)而解決實際生活中更為復(fù)雜的布局問題。

2 使用A 星算法解決電動充電樁優(yōu)化布局問題

2.1 構(gòu)建網(wǎng)格圖

為實現(xiàn)A 星算法進(jìn)行布局的優(yōu)化分析，我們團(tuán)隊聯(lián)系實際，以南京市為整體研究對象，查找了目前清晰度較高的南京市地圖，以單個小格為單位元，繪制出網(wǎng)格表，并以圖層疊加方式將其覆蓋，根據(jù)生活經(jīng)驗和實際考察，將電動汽車難以通行的地方（如山、江、湖）作為障礙物，制作出簡單的網(wǎng)格圖（如圖5 所示），之后又將這些障礙物在網(wǎng)格圖上標(biāo)示（如圖6 所示），之后借助MATLAB2022a 進(jìn)行仿真模擬，再根據(jù)“A 星算法”的估價函數(shù)進(jìn)行運(yùn)算，最終求得最優(yōu)路徑。

圖5 構(gòu)建實物網(wǎng)格圖模型

圖6 構(gòu)建簡易網(wǎng)格圖模型

我們將以此圖為范例，對現(xiàn)有的“A 星算法”計算最優(yōu)路徑啟發(fā)函數(shù)進(jìn)行改進(jìn)，實現(xiàn)新能源汽車充電樁的優(yōu)化布局分析。

2.2 起點和終點的選定

在“A 星算法”最優(yōu)路徑的搜索中，除障礙物以外，還需要有起點和終點位置。我們團(tuán)隊多方查找相關(guān)資料，結(jié)合實地背景通過線上線下相結(jié)合的方式，獲得南京市人口密度圖與南京市道路交通分布圖，尋找南京市邊界的人口密度高值區(qū)與城際道路發(fā)達(dá)區(qū)域的交集，將該區(qū)域抽象化為一個點，作為其中一個起止點，以同樣的方法在南京市邊界內(nèi)共找出5 個點（如圖5、圖6 所示），分別標(biāo)記為1 到5，在南京市邊界上近似均勻分布。

為避免片面性，我們將這5 個點對應(yīng)的周圍極小的區(qū)域類比為數(shù)學(xué)上的“鄰域”思想，由文獻(xiàn)[5]可知，點集，稱為點P0的δ 鄰域。例如，在平面上，如圖7 所示。

圖7 結(jié)點及其鄰域模型

2.3 聯(lián)系A(chǔ) 星算法進(jìn)行的充電樁布局分析

在運(yùn)用A 星算法解決問題的具體實施步驟如下：

（1） 在一定區(qū)域內(nèi)選取5 個結(jié)點（及其鄰域）為初始結(jié)點和目標(biāo)結(jié)點。

（2） 根據(jù)實際區(qū)域的障礙物在網(wǎng)格對應(yīng)位置設(shè)置障礙物。

（3） 根據(jù)A 星算法的“曼哈頓啟發(fā)函數(shù)”尋找出最短路徑。

（4） 再重復(fù)以上步驟找出其他路徑，得到其交點。

我們將對這5 個點（及其鄰域）分別作為該算法“曼哈頓距離”的起止點，我們先創(chuàng)建“OPEN 集合”和“CLOSE 集合”兩個列表，分別用于存放網(wǎng)格圖中未被處理的結(jié)點與已被處理的結(jié)點，我們將結(jié)點（區(qū)域）1定為“START 結(jié)點”，根據(jù)1.2 中的“A 星算法”的相關(guān)流程進(jìn)行運(yùn)算，再用MATLAB2022a 對其進(jìn)行仿真模擬，單一路徑仿真結(jié)果如圖8 所示。

圖8 使用MATLAB2022a 得到的單一路徑仿真結(jié)果

根據(jù)圖8，我們以中間結(jié)點（57,81）為例，介紹A星算法的運(yùn)算流程，搜索完該結(jié)點周圍的8 個父結(jié)點后，判斷出其正下方、右下方兩個父節(jié)點為“不可用結(jié)點”，將其余父結(jié)點入曼哈頓距離式中。

我們可以以當(dāng)前考察結(jié)點作為臨時原點，將其周圍的父節(jié)點用二維數(shù)組（i，j）表示，其中i、j 可取-1、0、1；在此處，二維數(shù)組（i，j）不可取（1，-1）、（0，-1），并且在同一圖表中D 為定值，取，代入得

得到6 個估價函數(shù)值，將其進(jìn)行逐一比較，確定其中的最小值，即實現(xiàn)啟發(fā)式函數(shù)的搜索功能，同時也是對該函數(shù)功能的檢驗。經(jīng)驗證，我們可以得到，即f6是最小估價函數(shù)值，即（-1，-1）將作為下一次“A 星算法”的“START 結(jié)點”進(jìn)行下一輪運(yùn)算，最終完成所有相關(guān)結(jié)點的遍歷，得到最優(yōu)搜索路徑。該路徑規(guī)劃方式完全符合原先預(yù)期，并更新最優(yōu)路徑的點集。

我們團(tuán)隊基于A 星算法在最優(yōu)路徑規(guī)劃方面的現(xiàn)有成果，結(jié)合南京市障礙的網(wǎng)格圖，通過修改A 星算法內(nèi)的相關(guān)參數(shù)，在多個非相鄰點之間尋找最優(yōu)路徑，將1 到5 這5 個結(jié)點（及其鄰域）按照搜索單一路徑的方法進(jìn)行相應(yīng)運(yùn)算，最終結(jié)果如圖9 所示。

圖9 使用MATLAB2022a 得到的單一路徑仿真最終結(jié)果

根據(jù)圖9，我們將人口密集及交通發(fā)達(dá)地區(qū)劃為“外圍區(qū)域”，將路徑交點周圍區(qū)域劃為“內(nèi)部區(qū)域”（如圖10 所示），即鎖定圖線分布較密集的“內(nèi)部區(qū)域”作為適合安置快充電樁的實際地點。后期我們將進(jìn)行實地考察觀測，在圖線相對密集的部分區(qū)域內(nèi)尋找適合建造充電樁的地點，已達(dá)成優(yōu)化布局的最終目的。

圖10 鎖定MATLAB2022a 仿真結(jié)果中符合要求的區(qū)域

【注：圖9、圖10 中的數(shù)據(jù)分別為：第一區(qū)域：“起點（24，90）”“終點（26，88）”“起點（33，90）”“終點（33，88）”；第二區(qū)域：“起點（60，86）”“起點（59，85）”“終點（56，84）”“終點（58，82）”；第三區(qū)域：“起點（（19，52）”“起 點（25，52）”“終 點（22，48）”“終 點（28，49）”；第四區(qū)域：“終點（94，29）”“起點（94，27）”“終點（94，23）”“起點（93，19）”；第五區(qū)域：“終點（47，9）”“終點（45，6）”“起點（44，5）”“起點（45，4）”。（五個區(qū)域自左至右、自上向下排序）】

結(jié)束語

本文利用“A 星算法”現(xiàn)有的應(yīng)用形式，將對電動汽車最優(yōu)路徑分析推廣到充電樁布局規(guī)劃，旨在解決現(xiàn)實中充電樁時空分布不均勻等實際問題，并為“A星算法”后續(xù)的改良以及其他方面的應(yīng)用提供了思路，具有一定的創(chuàng)新性和應(yīng)用價值。發(fā)揮現(xiàn)有“A 星算法”的優(yōu)勢，結(jié)合一系列改良“A 星算法”，進(jìn)一步提高了該算法的實用性。我們在MATLAB2022a 中，將城市道路及障礙模型網(wǎng)格化，對優(yōu)化路徑進(jìn)行一系列仿真實驗，先根據(jù)路徑交點得到一個優(yōu)化布局位置，再依此進(jìn)行推廣，最終解決布局問題。

然而，本算法在解決此問題中無法同時考慮復(fù)雜因素的影響，在后續(xù)的研究中，我們將繼續(xù)細(xì)化該模型，緊密結(jié)合現(xiàn)有城市背景，充分考慮更多現(xiàn)實因素，如有必要還可能與遺傳算法、模擬退火算法等其他經(jīng)典算法（根據(jù)參考文獻(xiàn)[6]、文獻(xiàn)[7]）相結(jié)合對現(xiàn)有算法進(jìn)行優(yōu)化改進(jìn)，進(jìn)一步完善這一思路，使這一改良分析方案成為今后城市建設(shè)方案中的參考之一。