江晉劍，朱緯綱

（安慶師范大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 安慶 246133）

世界能源短缺問題日益嚴(yán)重，各國都在尋找更加環(huán)保的能源解決方案。2021年北京市印發(fā)的《“十四五”時(shí)期國際科技創(chuàng)新建設(shè)規(guī)劃》文件強(qiáng)調(diào)，積極推進(jìn)先進(jìn)儲(chǔ)能，助力國家2060年前實(shí)現(xiàn)碳中和戰(zhàn)略目標(biāo)。電能作為一種清潔能源，已成為我國能源的重要組成部分[1]。同時(shí)，電動(dòng)汽車作為傳統(tǒng)汽車的有效替代品，可以有效緩解我們對石油的依賴，并減少溫室氣體排放。在電動(dòng)汽車普及初期，由于缺少一套科學(xué)完善的充電樁布局規(guī)劃指南，還沒有形成科學(xué)的充電樁布局體系，導(dǎo)致充電站的選址規(guī)劃不合理，導(dǎo)致用戶體驗(yàn)較差[2]。如何更加合理地確定充電站位置和充電樁數(shù)量，是目前一個(gè)急需解決的問題。針對這一問題，國內(nèi)外學(xué)者已經(jīng)提出了一些方案。例如，IOANNIS等[3]采用一種新的排隊(duì)模型對快速充電站進(jìn)行了分析，其按照汽車電池大小進(jìn)行分類，通過考慮可用的充電點(diǎn)，以及各種電動(dòng)汽車隨機(jī)到達(dá)過程和隨機(jī)充電需求來計(jì)算客戶在隊(duì)列中的平均等待時(shí)間。WANG等[4]提出了一個(gè)綜合考慮電動(dòng)汽車可持續(xù)發(fā)展、充電站特征、充電消費(fèi)者特征、充電需求分布、電網(wǎng)和城市規(guī)劃等因素的電動(dòng)汽車充電站布局多目標(biāo)規(guī)劃模型，然后根據(jù)需求優(yōu)先級(jí)和現(xiàn)有加油站的使用情況設(shè)計(jì)求解算法。HARIS等[5]采用中位數(shù)選址模型來解決了土耳其一家網(wǎng)絡(luò)公司的充電站設(shè)計(jì)問題。加鶴萍等[6]以充電站收益最大化為目標(biāo)函數(shù)，以交通流量為約束目標(biāo)，運(yùn)用模擬退火算法進(jìn)行了最優(yōu)求解。賈永基等[7]基于滿意優(yōu)化理論，提出了電動(dòng)汽車滿意度評(píng)價(jià)函數(shù)，并運(yùn)用免疫算法進(jìn)行了最優(yōu)求解。楊軍峰等[8]將每個(gè)區(qū)域中心作為電動(dòng)汽車充電負(fù)荷中心，采用TLBO優(yōu)化算法計(jì)算出了電動(dòng)汽車充電站的數(shù)量。耿建超等[9]建立了日常出行模型以模擬電動(dòng)汽車用戶充電需求，從宏觀角度規(guī)劃充換電站的布局。肖白等[10]提出了一種在備選站址既定情況下含不同容量充電樁的EVCS選址定容優(yōu)化方法，并結(jié)合模擬退火算法和迪克斯特拉算法對模型進(jìn)行了最優(yōu)求解。梁迪[11]等以各需求點(diǎn)的需求度權(quán)重以及充電站到需求點(diǎn)距離的乘積之和最小為目標(biāo)構(gòu)建了選址優(yōu)化模型，并采用了鯨魚算法（IWOA）來求解。鄒云程[12]等分析了充電技術(shù)發(fā)展對充電設(shè)施布局的影響，構(gòu)建了考慮充電選擇的電動(dòng)汽車均衡交通分配問題模型，通過算例分析驗(yàn)證了所提模型與算法的有效性。劉蕾[13]等將學(xué)校設(shè)為研究對象，利用求出的日充電需求、充電負(fù)荷曲線圖等以成本最低為目標(biāo)建立模型，并用整數(shù)規(guī)劃分枝定界法對該模型求最優(yōu)解。

雖然現(xiàn)階段已有很多關(guān)于充電基礎(chǔ)設(shè)施的空間選址規(guī)劃方案，但其大多是從成本、已有電網(wǎng)等角度出發(fā)，在現(xiàn)實(shí)情況下，由于數(shù)據(jù)量較多，導(dǎo)致算法復(fù)雜度高且模型求解難度大。因此，本文以某市為例，采用Folyd最短路徑算法對待分配充電樁節(jié)點(diǎn)進(jìn)行了選址約簡，并使用自適應(yīng)粒子群算法對模型進(jìn)行最優(yōu)求解，以期得到該區(qū)域充電站合理的位置布局。

1 充電站選址模型構(gòu)建與算法應(yīng)用

2 基于Floyd最短路徑的選址約簡

弗洛伊德最短路徑算法（Floyd）[15]是網(wǎng)絡(luò)流算法的一種，常用于各種中心選址問題的分析，用以實(shí)現(xiàn)中心到各節(jié)點(diǎn)的距離最小，從而達(dá)到經(jīng)濟(jì)效益最優(yōu)。在道路情況復(fù)雜、路口節(jié)點(diǎn)較多的情況下，由于數(shù)據(jù)繁多，對每個(gè)道路節(jié)點(diǎn)進(jìn)行建模計(jì)算的工作量較大。因此，本文采用Floyd最短路徑算法對道路節(jié)點(diǎn)進(jìn)行約簡，只選擇到每個(gè)節(jié)點(diǎn)曼哈頓距離最小的中心節(jié)點(diǎn)進(jìn)行建模計(jì)算，即可保證在時(shí)間成本最小情況下實(shí)現(xiàn)科學(xué)選址。該方法基本思想是，先把帶權(quán)鄰接矩陣A作為距離矩陣D的初值。

當(dāng)k=n時(shí)，Dn=中便是允許中間點(diǎn)為ν1,ν2,ν3,…,νk的，從νi到νj路徑中的最短路徑長度，即是求從νi到νj中間可插入任何頂點(diǎn)的路徑中最短路徑長度，因此Dn即為距離最短矩陣。矩陣Dn的每個(gè)元素都代表了兩點(diǎn)間考慮了其他任意點(diǎn)作中間點(diǎn)時(shí)的最短距離，最后將Dn中的各行元素求和，即可得到每一個(gè)點(diǎn)到其他各點(diǎn)的最小距離和，因此通過比較即可篩選出多個(gè)充電樁選址，在面臨數(shù)據(jù)量較大的選址問題時(shí)，這一操作能夠降低計(jì)算成本，減少問題復(fù)雜度。

3 自適應(yīng)粒子群算法

4 算例分析

本文以美國南達(dá)科他州最大的城市蘇福爾斯為例，該區(qū)總面積80萬平方英里，路口節(jié)點(diǎn)24個(gè)，規(guī)劃在此區(qū)域內(nèi)建立多個(gè)電動(dòng)汽車充電樁。算法參數(shù)：種群規(guī)模為50，學(xué)習(xí)因子c1，c2取1.496 2，慣性因子wmax為0.9，wmin為0.4，迭代次數(shù)取250次。根據(jù)上文的模型構(gòu)建，在充電站候選點(diǎn)生成后再對其進(jìn)行編碼，隨機(jī)生成充電站選址種群，并依次對每個(gè)個(gè)體的目標(biāo)函數(shù)進(jìn)行計(jì)算，且對總成本最低的個(gè)體給予更高的適應(yīng)度，同時(shí)進(jìn)行選擇、交叉、變異遺傳操作以產(chǎn)生下一代個(gè)體，直到到達(dá)設(shè)定的最大迭代次數(shù)，從而得到充電樁最優(yōu)布局。通過對該市車流量信息的調(diào)查，獲得該區(qū)域的日平均車流量見圖2，路口節(jié)點(diǎn)坐標(biāo)見表2。

表1 充電站/車輛參數(shù)數(shù)據(jù)

表2 節(jié)點(diǎn)坐標(biāo)表

圖1 基于自適應(yīng)粒子群優(yōu)化算法的電動(dòng)汽車充電站選址布局流程

5 仿真實(shí)驗(yàn)

通過MATLAB2019 計(jì)算得到了24 個(gè)候選節(jié)點(diǎn)的路徑矩陣，將矩陣的行元素求和后，得到了表2中24個(gè)候選節(jié)點(diǎn)到各點(diǎn)的最小距離和，如表3 所示，可見1、2、6、13、20、21、24號(hào)節(jié)點(diǎn)到各節(jié)點(diǎn)的距離之和的大于最小距離之和平均數(shù)，因此該7個(gè)節(jié)點(diǎn)在仿真實(shí)驗(yàn)中不參與模型求解，并將其余節(jié)點(diǎn)作為充電站候選點(diǎn)，具體節(jié)點(diǎn)之間的位置關(guān)系如圖3所示。

表3 候選節(jié)點(diǎn)到各點(diǎn)的最小距離表

圖3 Folyd算法選址約簡

為了驗(yàn)證算法的優(yōu)化能力，本文分別采用了標(biāo)準(zhǔn)粒子群算法（PSO）和自適應(yīng)粒子群算法（CPSO）對該算例進(jìn)行最優(yōu)求解，得出了兩種算法的最佳適應(yīng)度值圖像（圖4）。對比圖中的兩條曲線可知，PSO在迭代到135次時(shí)收斂，CPSO在迭代到88次時(shí)收斂。在迭代初期，PSO 收斂的性能優(yōu)于CPSO，而CPSO 在迭代的中后期仍保有較好的種群多樣性，并于較少的迭代次數(shù)時(shí)收斂，其綜合優(yōu)化結(jié)果優(yōu)于PSO，其充電站位置如圖5所示。

圖4 算法結(jié)果對比

圖5 充電站最優(yōu)布局

6 結(jié)論

優(yōu)化電動(dòng)汽車充電站的布局是一項(xiàng)具有長期性和復(fù)雜性的工程。本文在該方面取得了一些階段性研究成果，但依然存在一些問題值得探討。本文模型適用于新能源電動(dòng)汽車充電站布局規(guī)劃問題，實(shí)現(xiàn)在綜合成本最低與節(jié)約資源的前提下進(jìn)行充電樁布局。通過Floyd 算法求解距離矩陣，快速找到多源點(diǎn)之間的最短路徑，并選取最優(yōu)節(jié)點(diǎn)作為充電樁的待建點(diǎn)，能夠有效減少計(jì)算成本。在粒子群算法（PSO）基礎(chǔ)上，對慣性權(quán)重的取值進(jìn)行了改進(jìn)，改進(jìn)的粒子群算法（CPSO）有效地提高了迭代速率，使其能更精準(zhǔn)地找到最優(yōu)適應(yīng)度值。通過仿真計(jì)算發(fā)現(xiàn)，該方案能為電動(dòng)汽車提供良好的服務(wù)，同時(shí)能夠避免充電站無序安裝所帶來的社會(huì)資源浪費(fèi)，對城市充電樁最優(yōu)位置的規(guī)劃具有指導(dǎo)意義。當(dāng)前國內(nèi)外充電站的建設(shè)均處于起步階段，充電站建設(shè)區(qū)域的用地面積也只能大致估算，模型在許多方面有待完善。一些理論數(shù)據(jù)與實(shí)際情況仍存在偏差。后續(xù)還可增加季節(jié)、天氣、汽車品牌類型、用戶充電習(xí)慣以及電網(wǎng)負(fù)荷等因素，從而使所建模型更能貼近實(shí)際情況。