基于自適應粒子群算法的電動汽車充電樁布局優化

江晉劍，朱緯綱

（安慶師范大學 計算機與信息學院，安徽 安慶 246133）

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

雖然現階段已有很多關于充電基礎設施的空間選址規劃方案，但其大多是從成本、已有電網等角度出發，在現實情況下，由于數據量較多，導致算法復雜度高且模型求解難度大。因此，本文以某市為例，采用Folyd最短路徑算法對待分配充電樁節點進行了選址約簡，并使用自適應粒子群算法對模型進行最優求解，以期得到該區域充電站合理的位置布局。

1 充電站選址模型構建與算法應用

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

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

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

3 自適應粒子群算法

4 算例分析

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

表1 充電站/車輛參數數據

表2 節點坐標表

圖1 基于自適應粒子群優化算法的電動汽車充電站選址布局流程

5 仿真實驗

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

表3 候選節點到各點的最小距離表

圖3 Folyd算法選址約簡

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

圖4 算法結果對比

圖5 充電站最優布局

6 結論

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