面向最大使用效益的充電站網絡優化方法

孟祥福，楊 玉，張永庫，張霄雁，陳柔冰，王 澤

遼寧工程技術大學 電子與信息工程學院，遼寧 葫蘆島125105

我國政府投入了大量資金建成了一定規模的充電站，目前完善充電基礎設施體系是大規模運行電動汽車（electric vehicle，EV）的關鍵。根據2018 年中國電動汽車百人論壇發布的數據可知，我國的公共充電設施利用率不足15%，存在著大量閑置且冗余的充電站，局部地區充電站還發生了整體缺樁現象。目前，在充電站網絡優化過程中一個不可缺少且研究不足的問題就是充電站的利用率不足和充電站的冗余問題。

以往大部分的研究工作集中在充電站選址優化過程，并未對現有的充電站布局合理性進行分析，忽略了電動汽車充電高峰期導致的充電站溢出問題、冗余充電站和充電站擁堵問題。如果不考慮現實充電站網絡而直接對充電站進行優化，重新建設新的充電站網絡，不僅需要大量的人力、物力，而且還會造成資源的浪費，不符合可持續發展的理念。另外，隨著電動汽車滲透率迅速增長，電動汽車的需求分布也會隨之發生變化，在充電站布局方面還應避免現實充電站間的無序競爭。針對以上問題，本文綜合考慮了電動汽車充電高峰時期的溢出問題、充電站間的競爭、政府要求和電動汽車充電行為等多重因素對現實充電站網絡優化的影響。利用廣泛的傳感數據感知電動汽車的充電行為，分析電動汽車充電行為規律。并且，分別為不同充電站單獨建立隊列系統，估計不同充電站的電動汽車到達率，分析電動汽車在不同充電站間的活躍程度，以識別城市充電熱點。此外，基于全面挖掘電動汽車的充電行為特性、充電站之間競爭關系以及充電站的地理特征的相互作用，提出了一種新的方法來計算不同充電站之間在網絡中的使用效益情況。最后，建立了充電站使用效益最大化優化模型，求解最佳充電站網絡布局。

1 相關工作

針對電動汽車充電站選址優化問題，已經有許多學者對其進行了不同角度的研究。從電動汽車的充電需求出發，文獻[2]提出了一個多類型純電動汽車（battery electric vehicles，BEV）充電設施定位模型，以最小化公共社會成本為目標，滿足不同類型BEV 的充電需求。Tu 等對電動出租車需求、電動出租車和充電站之間的交互進行建模，提出了一種時空需求覆蓋方法，實現了電動出租車服務水平與充電服務之間的高質量權衡。為了優化充電站，一些研究也開始關注充電站的位置和大小。Ma 等建立了BASS 模型來預測不同年份電動汽車充電站的滲透率和數量。并根據排隊理論，提出了電動汽車充電站選址優化模型，使電動汽車充電站的總成本最小，并采用枚舉法求解該模型。為了提高充電站利用率，節約投資成本，Zhang 等提出了一種新充電點模型，即單輸出多電纜充電點（single output multiple cables charging spots）。Bao 等針對交通網絡擁擠的情況，提出了一種新的充電站定位問題，在有限的建設預算下，找到一組最優的充電站，使所有車輛都能通過沿途一個或多個充電站充電完成行程，最小化網絡上的總旅行成本。文獻[9]對電動汽車用戶充電的搜索行為、導航行為和充電使用模式進行了分析和建模，提出了一種基于貝葉斯推理的充電需求評估方法。Luo 等研究了出行方式、電動汽車駕駛員行為、城市路網、電網與充電站布局之間的相互作用，提出了不同電動汽車滲透率下的多級充電站布局方法。葛少云等針對現有研究沒有考慮車輛空間和時間變化的出行需求問題，提出了一種基于動態交通模擬的高速公路網電動汽車充電站優化規劃技術。本文以武漢市中心區域的充電站網絡為例，構建電動汽車隊列系統，建立充電站最大使用效益模型，通過診斷并消除冗余充電站進行網絡優化，同時識別網絡中充電站擁堵區域，發現布局漏洞，為政府進一步的充電站規劃提供有效建議。

2 電動汽車充電行為分析

2.1 影響充電站網絡布局因素分析

（1）電動汽車充電行為規律

由于電動汽車的動力和續航能力較為中庸，在較長出行旅程中需反復多次進行充電。單個電動汽車充電行為在時空分布上具有較大的隨機性，但是大規模電動汽車群的充電行為表現出了一定的規律性。通過對大型電動汽車群的充電行為進行分析，可以了解電動汽車在各個充電站間的活躍程度和移動方向。并且，基于以上分析，能夠準確識別出電動汽車充電熱點，挖掘電動汽車在城市充電站間的充電移動模式（如星形移動模式），有助于制定更好的充電站網絡優化方案。電動汽車的空間充電熱點，能夠在很大程度上揭示城市電動汽車用戶的充電偏好規律。通常，充電站需覆蓋熱點地區，特別是在人口稠密和交通需求相對較大的地區，然而供需之間不可避免地會存在大量矛盾。特別是在面臨充電高峰時段的電動汽車充電需求量時，需盡可能使充電站網絡布局與電動汽車充電需求分布一致，即布局與電動汽車充電偏好一致，最大限度地滿足電動汽車的充電需求。電動汽車的移動模式則反映出了車流量的流動方式，為后續的優化擴展提供方向指導。

（2）充電站之間的關系

在電動汽車使用過程中，里程焦慮不可避免，它反映出司機對電動汽車是否有足夠的電量到達目的地的一種擔心。一旦電動汽車荷電狀態處于較低水平，電動汽車用戶將會選擇在可接受充電距離范圍D內的充電站進行充電。假設此時電動汽車與充電站間的距離為(→)，與充電站的距離為(→)，若式（1）與式（2）同時成立，則充電站與將會產生競爭關系。

雖然競爭力較強的充電站會吸引更多的電動汽車用戶訪問，但是一旦大部分用戶選擇同一時間段前往同一充電站充電（高峰期），將會導致充電站的溢出，電動汽車充電等待時間將直線上升。這種情況下，通常需要借助附近的充電站來緩解本地充電壓力，從而形成充電站間依賴關系。由此可知，充電站間能夠相互影響彼此。因此，在充電站網絡優化過程中，充電站間的關系是網絡優化過程中必須考慮的一個重要因素，無論是關閉還是新增充電站都將會對網絡中其他充電站產生影響，同時還關系到電動汽車的用戶體驗。

（3）政府規劃部門要求

圖1 顯示了武漢市中心地區一些充電站的局部視圖。站點的大小表示電動汽車的平均到達率。從圖1（a）可以看出，該區域內充電站分布非常密集，存在冗余充電站（綠色）。因此，政府可以考慮關閉其中的一些站點，以減少公共資源的浪費。相反，從圖1（b）可知，大量電動汽車頻繁訪問該區域內的充電站，因此這些充電站的充電等待時間往往較長（紅色），造成一定程度的充電站擁堵。政府可以考慮在附近新增一些充電站來緩解區域內的充電壓力。這些現象顯然反映了目前武漢市充電站網絡布局并不合理。由此可見，需要設計一個基于真實充電站網絡的交互式優化系統，用戶可以根據實際需求設置不同的調優參數，從而診斷和消除網絡中的冗余充電站獲取最佳充電站網絡方案，提高充電站利用率，同時識別網絡中產生充電站擁堵（供不應求）的區域發現布局漏洞。

圖1 充電站局部視圖Fig.1 Local view of charging stations

2.2 電動汽車充電特性

在電動汽車用戶選擇充電服務過程中，考慮到首次抵達的充電站有可能發生溢出，因此有必要保留一部分電量作為安全儲備，而不是首次抵達充電站后就完全耗盡電量。根據比亞迪E6 在城市區域性能可知，100%荷電狀態下的最大行駛距離約為250 km。假設電動汽車具有相同的電池容量，滿荷電狀態記為′，電動汽車在滿電荷狀態下可行駛的最大距離表示為，則電動汽車在荷電狀態為時，可繼續行駛的距離為：

若電動汽車首次抵達充電站后，當前充電站發生溢出（當充電站高峰時期訪問量和平均訪問量與總體充電站的平均訪問量偏差75%時，將該充電站視為溢出站點），電動汽車司機將會選擇其附近其他充電站進行充電。由于過度的放電會縮短蓄電池的使用壽命，電動汽車再次選擇充電的充電站與當前充電站距離不能大于D。值得注意的是，電動汽車用戶在選擇范圍D內的充電站充電的偏好會有所差異。越受歡迎的充電站，電動汽車選擇在該充電站充電的可能性也就越大。因此，給定不同充電站的平均訪問頻率(s)，可以將訪問頻率作為充電站的權重：

如圖2 所示，空心圓圈代表充電站，當電動汽車首次抵達充電站時，會發生兩種情況：（1）充電站沒有發生溢出，電動汽車正常充電；（2）充電站發生溢出，電動汽車無法正常充電，轉向附近其他充電站進行充電。本文主要探討研究第二種情形。充電站的溢出狀態分別用0 或1 表示，其中1 表示充電站溢出，0 表示充電站沒有發生溢出。假設電動汽車司機在選擇二次充電過程中會傾向選擇距離充電站最近的充電站充電，降低充電訪問成本，因此距離同樣會影響司機對充電站的選擇。 D為電動汽車首次抵達充電站后并未充電而再次改變充電站的最大可接受充電距離，l表示充電站到充電站s的距離，(s) 表示充電站s的權重。由圖2 可知，當l＜D時，在充電站的電動汽車二次充電才有可能選擇s作為充電點。當d＞D時，電動汽車剩余電量無法抵達充電站s，因此充電站s并不在司機考慮改變充電位置的范圍內。

圖2 充電站的選擇Fig.2 Choice of charging station

2.3 電動汽車充電熱點和移動模式

電動汽車進入充電站充電具有很大的隨機性，文獻[12]表明該過程符合M/M/排隊論模型，第一個M 表示電動汽車一定時間內到達充電站充電過程滿足泊松分布；第二個M 表示各個充電樁的服務時間服從負指數分布；代表充電站內充電樁的數量，則存在以下恒定等式：

電動汽車訪問充電站的次數越多，充電站越繁忙，在該區域越處于重要地位，可以有效服務更多電動汽車用戶，進而形成電動汽車充電熱點。圖3 給出了某區域的充電熱點，其位于一個比較受歡迎的購物中心內。進一步觀察發現，電動汽車在熱點完成充電后的出行模式呈現出星形移動模式，即電動汽車會從相同的起點出發，到達不同的目的地，如圖3中的紅色箭頭所示。

圖3 充電熱點和星形移動模式Fig.3 Charging hot spot and star-shaped mobility pattern

3 使用效益評分函數

本文將優先被選入最佳網絡的充電站視為父級充電站（parent charging station,PS），未擴展或后擴展的充電站稱為子級充電站（child charging station,CS）。給定父級充電站，并基于充電站間的訪問權重、距離關系和競爭關系計算充電站網絡中其他未被選擇的子級充電站使用效益分數，計算方法如下：

4 充電站網絡優化方法

問題定義：給定一個具有溢出狀態的充電站集合={,,…,s}，溢出狀態集合，訪問權重集合，充電站間最短路徑距離矩陣∈R，個充電熱點和調優參數。充電站網絡優化目標是發現冗余充電站集合?和獲得最佳充電站集合′?，目標遵循最大化充電站使用效益，函數形式如下：

其中，(s)表示充電站s的使用效益評分。

4.1 基于充電熱點的網絡擴展算法

充電站網絡擴展算法的基本思想是以個電動汽車充電熱點作為網絡擴展的起始站點，并不斷向最佳站點（即使用效益最高的充電站）擴展，形成一個新的充電站網絡。實現算法分為初始化階段、網絡拓展階段和終止階段。算法1給出了相應的偽代碼。

基于充電熱點的網絡擴展算法

輸入：充電站集合，溢出狀態集合，充電站訪問權重集合，最短路徑距離矩陣，充電熱點，調優參數。

輸出：最佳充電站網絡′，冗余充電站集合。

初始化階段：第1～4 行，算法首先選擇個電動汽車充電熱點插入結果集′中，成為父級充電站，并將與父級充電站對應的未被選擇的子級充電站插入候選集合，通過-′更新充電站集合。

網絡擴展階段：在每次網絡擴展迭代中，當!=?時，遍歷結果集′的父級充電站，判斷是否存在溢出站點，對應兩種情況的處理方法如下：

（1）如果結果集′中存在溢出充電站，把溢出站點相應的所有未被選擇的子級充電站插入候選集′,并基于所有溢出的父級充電站計算集合′中的子級充電站的使用效益分數，計算方法為式（6），并把計算結果插入列表（第7～10 行）。遍歷列表并將最佳子級充電站（即使用效益評分最高的站點）擴展到網絡，接著將插入到結果集′，然后將未被選擇的子級充電站插入候選集合（第8～13 行）。接著，算法將父級站點溢出部分用戶和在的D范圍內未被擴展的充電站充電的用戶重新分配給新站點，并重新計算新站點的溢出狀態。第14～17 行，若沒有發生溢出，表示新站點能夠覆蓋其D范圍內的未被選擇的充電站，并解決其父級充電站的溢出問題。這表明了新站點的D范圍內未被擴展的子級充電站皆為冗余充電站，這類充電站的產生往往是因為缺乏對電動汽車充電需求的合理的分析。因此，把這些可被覆蓋的充電站插入冗余站點集合中，并更新父級充電站的溢出狀態為0，通過--更新。第18～21行，若重新分配用戶后，新站點發生溢出，則表明無法覆蓋其D范圍內未被選擇的充電站，通過-更新。再次計算父級充電站溢出部分用戶重新分配給新站點是否會導致的溢出。若新站點沒有發生溢出，表明新站點能夠解決其父級充電站的溢出問題，并將父級充電站溢出狀態更新為0。

（2）如果結果集′中充電站不存在溢出，算法直接計算候選集合中的所有子級充電站的使用效益分數，并將最大使用效益的子級充電站擴展到網絡中。然后，將新被擴展的充電站未被選擇的子級充電站插入候選集中成為新的候選站點（第22～26 行）。算法將在新站點的D范圍內未被選擇的充電站充電的用戶重新分配給新站點，并重新計算的溢出狀態。第27～29 行，若沒有發生溢出，表示新站點能夠覆蓋其D范圍內未被選擇的充電站，并把這些充電站插入冗余站點集合，通過--更新。第30～31 行，若重新分配用戶后，發生溢出，則表明無法覆蓋其D范圍內的未被選擇的充電站，通過-更新。

終止階段：第33 行，當=?時，即遍歷完所有充電站時，算法終止擴展循環，返回包含溢出狀態的最佳充電站網絡方案′和冗余充電站集合。

4.2 初始化方法

算法1 的最終結果′的性能很大程度上取決于初始充電站的選擇，因此如何選擇有效的初始化方法成為網絡擴展算法的關鍵。以下提出了兩種不同的初始化方法：

（1）基于top-的初始化。網絡擴展中最直接的初始化方法是top-初始化，其本質是選擇電動汽車訪問率最高的充電站（即充電熱點）作為網絡擴展的起始站點。因為優化方案中應該始終包含電動汽車充電熱點，確保算法不會遺漏任何使用效益最高的充電站，方法的本質是為了覆蓋更多的用戶。然而，大部分訪問率高的充電站在空間分布上非常接近，特別是當充電站的數量較少的時候會導致網絡擴展過程中有可能遺漏一些重要的區域。

（2）基于聚類的初始化。為了在初始化階段包含更多空間多樣性的起始站點，以及在充電站數量較少時網絡擴展更有效，提出了基于空間聚類的方法來選擇網絡擴展的起始站點。采用基于空間聚類的初始化方法的原因來自對電動汽車充電熱圖的觀察（如圖4 所示）。從熱力圖可以看出，在空間上電動汽車充電行為的分布已具有一些可視化的集群，本文采用的是基于層次聚類的聚類方法產生集群。最后，選擇每個集群中訪問率最高的充電站作為起始站點。

圖4 電動汽車充電行為空間分布Fig.4 Spatial distribution of charging behavior of electric vehicles

5 實驗及結果分析

實驗數據采用武漢市中心區域的充電站網絡，區域內共有156 個充電站（實心圓表示），充電站的空間分布如圖5 所示。網絡中充電站的平均使用效益約為61.04%，共有32 個溢出站點（紅色實心圓表示）。將網絡中充電站按照到達率大小進行排序，選擇前20%的充電站作為城市電動汽車的充電熱點。

圖5 武漢市中心區域的充電站網絡Fig.5 Charging stations network of central area of Wuhan

5.1 參數設置

（1）不同值的影響。實驗將值分別設置為{5,10,15,20,25}來觀察網絡擴展算法起始站點個數的不同對充電站網絡優化的影響。圖6（a）為對充電站網絡上進行不同值優化，采用top-方法和聚類法的用戶覆蓋率結果對比圖。如圖所示，兩種初始化方法在5 ≤≤10 時，用戶覆蓋率相同。原因是在這個范圍內兩種初始化方法的起始站點是相同的，所得到的優化方案一致。然而，在大多數情況下top-方法具有更高的用戶覆蓋率和更低的充電站溢出率（如圖6（b）所示）。實驗結果表明，當5 ≤≤20時，兩種初始化方法溢出率基本保持一致，但top-方法具有更高的用戶覆蓋率，提高約3 個百分點，并且隨著值的增大，用戶覆蓋率持續上升。因此，本文將初始化方法的最佳值設置為25。

圖6 效能評估Fig.6 Effectiveness evaluation

5.2 網絡優化結果分析

充電站利用率是衡量整個充電站網絡使用情況的直觀指標。充電站一天內（24 h）平均利用率的計算公式如下：

如表1 所示，優化后得到的最佳充電站網絡的充電站平均利用率比原網絡提高了約7.72 個百分點，用戶覆蓋率高達97.63%，并且溢出站點數量減少了21，原因是網絡中部分充電站的溢出主要由用戶充電習慣所導致，并非真正的溢出，可以通過區域內其他充電站平衡充電壓力。然而，在部分區域內充電站整體缺樁情況下，政府部門只能通過新增站點來緩解本地的充電壓力（如圖7 所示的C 區、D 區、E 區、G 區和F 區）。這些區域主要由大量高訪問率的充電站和溢出充電站構成。從優化結果可知，原充電站網絡存在大量冗余充電站（充電站ID 分別為15、62、81、82、84、93、100、109、131、139、144 和148），空間分布如圖7 黑色實心圓所示。在網絡優化過程中，逐一將冗余充電站從網絡中移除來優化充電站網絡，減少公共資源的浪費，并在一定程度上提高充電站利用率。

圖7 武漢市中心區域最佳充電站網絡Fig.7 Optimal charging station network for Wuhan central area

表1 優化結果Table 1 Optimization results

6 結束語

本文分析了影響充電站網絡優化的相關因素，建立了以充電站使用效益最大化為目標函數的優化模型。在充電站網絡優化過程中，兼顧充電站溢出、充電站相互作用和電動汽車偏好，并以最大使用效益為指標選擇最佳充電站位置。最后，以武漢市中心區域充電站網絡為例進行研究，發現武漢市中心區域的充電站網絡出現了兩種極端現象：充電站供不應求和供過于求。原因是因為充電站分布與電動汽車充電需求分布不一致，缺乏對現實充電站網絡布局的合理性分析。實驗結果表明，本文方法和模型不僅能夠有效診斷并消除充電站網絡中的冗余充電站，提高充電站的利用率，減少公共資源的浪費，還能識別網絡中的充電站擁堵區域，發現布局漏洞，為政府進一步解決電動汽車充電難問題提供參考。后續研究中，將進一步考慮如何精確地在充電站擁堵區域新增站點，解決充電難問題。