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

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

引言

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

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

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

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

1 A 星算法

1.1 “Dijkstra 算法”

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

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

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

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

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

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

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

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

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

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

1.2 “A 星算法”的概念

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 曼哈頓距離

圖4 歐幾里得距離

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

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

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

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

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

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

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

2.2 起點(diǎn)和終點(diǎn)的選定

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

結(jié)束語

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

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