新能源貨車充電站規劃選址方法研究

四川中電啟明星信息技術有限公司 徐小云 李歡歡 王紅蕾

1 引言

當下充電站選址問題受到國內外學者的廣泛關注，研究已涉及交通、能源、電力工程、計算機科學、管理科學等多個領域，從不同角度研究充電站選址的影響因素、選址方法、算法優化等。文獻[1]以充電站投資運行成本最小為目標構建充電站選址兩步法。文獻[2]建立路徑選擇模型和交通滿意度評價模型，考慮充電站定容選址對配電網了和交通網絡的影響。文獻[3]基于博弈論提出博弈優化模型和算法，對充電站選址方案進行評價。依據目前電動車司機的充電習慣來決定充電站的分布，以最大化滿足現有用戶的充電需求。分析認為用戶充電習慣為在路途起點和終點充電，而非路途中間，并且使用遺傳算法最大化充電樁數量，并在不同區域提供不同類型充電樁。

目前，大部分研究沒有考慮到車輛使用屬性和競爭因素對充電站選址的影響。因此本文針對新能源貨車的特點，結合聚類算法對相關POI 數據進行聚類分析，并考慮已有充電站對選址建站的影響，對貨車充電站展開規劃選址。

2 方法概述

聚類算法目前在選址和區域劃分中運用較多，比如常用K-means 算法具有快速高效、易于理解、理論可靠的優勢，但也有一些問題，如聚類數目需預先確定、離群點影響大、容易形成局部最優解等。針對K-means 的缺陷，國內外學者從不同角度對傳統聚類算法進行了改進。文獻提出了初始k 值選取方法，比如基于圖像分割的思想使用分水嶺算法，或基于層次聚類的思想對傳統算法改進等；文獻提出了初始聚類中心點的選取方法，比如選取密度最大的對象，或首選距離最大的兩點作為初始聚類中心等；文獻提出了離群點的檢測和去除方法，比如使用LOF 算法來篩出，或基于網格密度對傳統算法改進等。

本文針對新能源貨車充電站選址進行研究，根據實際選址需求，考慮充電需求與競爭選址，結合改進后的聚類算法，構建出新能源貨車充電站規劃選址方法，整體思路如圖1所示。首先，將規劃選址區域進行網格劃分，分析配送點和競爭場站在網格中的空間分布；其次，根據網格中配送點的空間分布計算柵格充電需求指數，并根據網格中競爭場站的空間分布計算柵格充電供給指數；然后，優化傳統聚類算法，避免離群點對聚類的影響與局部最優問題；最后，使用優化的聚類算法結合充電需求指數和充電供給指數對選址區域的柵格進行聚類，得到規劃選址站址。

圖1 貨車充電站的規劃選址方法

3 新能源貨車建站需求的空間分析

充電需求一般分兩類，一類是路途中需求，常存在于長途行程中途補充電量的情況；另一類是始末點需求，由于電動車充電時長較長，因此多選擇在路途起點或終點休息時進行充電。本文主要針對新能源貨車的選址，據調查顯示，由于當前電池技術與配套設施的限制，目前新能源貨車多用于城市配送服務。由于路程較短，因此較多考慮始末點需求，即在配送起點或終點進行充電。本文從城市配送相關POI 出發，結合競爭場站信息，分析區域內新能源貨車的建站需求空間分布。

3.1 選址區域分析

整個選址規劃區域Q 經度區間為[LOmin,LOmax]，緯度區間為[LAmin,LAmax]，按經緯度將區間劃分為(M×N)個方格網格，假設至少在長寬三公里方形柵格范圍內能找到合適的建站位置，因此滿足式（1），網格空間，規劃區域內任意一點qij有唯一對應的網格gmn，使得qij∈gmn。

3.2 城市配送POI 分析

表1為城市配送點POI 數據，配送點包含兩大類，一類是配送起點，如下表中物流倉儲等；一類是配送終點，如下表中超市、市場等。新能源貨車在配送起點裝載貨物后，運送到一個或多個配送終點。

表1 城市配送POI

圖2為配送點分布圖，從配送點分布圖可看出，存在一些配送點遠離其他配送點，如果在這些離群配送點附近建站，則會降低建站效益。因此在聚類過程中，需考慮離群點對聚類規劃選址的影響。

圖2 配送點分布圖

配送點集合W={w1,w2,…,wn}，集合中每個元素包含該配送點的經緯度wi=(loi,lai)。根據3.1劃分的網格空間和配送點位置信息，可得配送點網格熱度矩陣如式（2），元素aNM表示第n 行m 列的網格區域內的配送點的熱力值，熱力值越高的區域代表配送點越密集，相對充電需求越大，建站需求也就越大。

3.3 已有場站分析

目前區域內存在已建充電站，如表2所示為充電站名稱、地理位置、充電樁數等信息。對新建站的選址規劃應考慮已有場站帶來的影響。已有充電站主要有以下幾種類型：在原露天停車場增配充電樁、路邊停車位增配充電樁、地下停車場增配充電樁、新建專用充電站。對于在原有停車場和停車位上增配充電樁的方式，由于停車位大小有限，因此對充電車輛大小有所限制。由于本文是針對貨車充電站的選址，貨車所需停車位比普通車位大，因此主要依靠新修的貨車充電站為其提供充電服務，在競爭選址上也主要考慮單獨修建的可供貨車充電的充電站對規劃選址的影響。

表2 充電站信息

篩選出貨車充電場站的集合V={v1,v2,…,vn}，集合中每個元素包含該配送點的經緯度和充電樁數量vi=(loi,lai,ci)。根據3.1劃分的網格空間和充電站分布，得到已有場站網格熱力矩陣如式（3），元素bnm表示第n 行m 列網格的已有場站熱力值，熱力值越高的區域表示已有場站越密集，對應充電供給也越充足，建站需求就越少。

4 基于改進的聚類規劃選址方法

4.1 競爭選址下的建站需求

充電站市場是一個競爭市場，后進入市場的場站規劃選址是在競爭環境下的選址問題。競爭選址問題上，影響的因素有很多，比如：競爭設施的位置距離越近影響越大；市場需求越大設施搶奪的市場份額也越大；競爭設施區域大小等原因造成的最大容量限制了搶奪的市場份額；由集群效應中造成設施之間既是競爭關系也是合作關系。

因此，本文考慮競爭選址，既可以考慮周邊已有場站的距離因素對規劃選址的影響，同時也可以考慮周邊場站的容量對規劃選址的影響。本文提出充電供給指數，結合周邊充電站位置信息及其充電樁數量的信息，公式（4）計算出每個網格的充電供給指數ES，指數范圍為[0,1]，指數越大表示該網格充電供給越多，建站需求越低。

d(·)是由公式（5）計算兩點的曼哈頓距離；p為某網格中心點地理位置；(xi,yi)和(xj,yj)為兩點坐標值；si為第i 個充電站地理位置；Ci為該充電站的充電樁數量；k 為充電站數量；R 為充電站服務距離。城市道路中汽車的平均時速為[20,50]km/h，汽車前往充電站的路程時長為半小時以內較合理，因此充電站服務距離R 設置為10km。根據公式（4）計算出所有柵格的充電供給指數后，考慮建站成本，若該網格充電供給大于0，則不考慮在該網格建站。根據充電供給指數，得到建站需求矩陣C 如式（6）所示，cnm 值為0或1，表示考慮競爭場站的影響下，是否可在該網格建站，1為可考慮建站，0為不考慮建站：

4.2 離群配送點

傳統K-means 算法中，離群點會影響聚類的準確性。并且，考慮在離群配送點周邊建站對建站效益的影響，本文在K-means 算法中結合密度聚類，分離遠離其他簇的小簇，從而減少離群點對聚類選址的影響。具體操作步驟如下：

（1）對配送點集合W 中的任意兩點x 和y，按照式(7)計算樣本點兩兩間歐式距離d；

（2）設置距離閾值θ。為避免在離群點周邊建站，考慮配送點車輛前往離群配送點周邊行駛時間不超過半小時較合理，因此距離閾值為行駛時間半小時的路程，由于城市道路汽車的平均時速為[20,50]km/h，即曼哈頓距離10km 的路程，相對應的歐式距離為km，因此距離閾值θ 設置為10km；

（3）將步驟（2）獲取的距離閾值θ 作為鄰域閾值Eps，由于此處用密度聚類尋找離群點，因此minPts 為1，即一個點即可構成一個簇，使用DBSCAN 對樣本進行密度聚類；

（4）根據步驟（3）得到的密度聚類結果，得到遠離其他簇的小簇且簇中元素個數小于等于2，將這樣的簇中的點視為離群點；

（5）從配送點集合W 中將離群點剔除得到新的集合W’。

4.3 改進的聚類算法

傳統K-means 算法需要預先確定聚類個數k，k 值選取的不同會影響聚類中心的變化，得到的結果為局部最優。因此，本文在傳統K-means 算法上作改進，引入核密度估計，優化局部最優問題，避免隨機確定初始聚類中心引起的局部最優解。具體操作步驟如下：

（1）根據3.1所述，將選址規劃區域劃分為(m×n)個格點，每個格點中心為一樣本點，所有樣本點構成預選點集合G；

（2）考慮競選址的因素，根據4.1中的建站需求矩陣，把預選點集合G 中cnm 值為0的網格從預選點合集中去除得到新的預選點集合G’。

（3）根據分離離群點后的配送點集合W’的空間分布，利用高斯核密度估計計算每個柵格樣本點的核密度估計值，如式（8）。其中k(·)是核函數；h 是帶寬，表示在x 的鄰域[x-h,x+h]計算x 的密度函數；n 是帶寬范圍內觀測點的數量，i=1,…,n。本文采用的核平滑函數是高斯核函數，如式（9），其中σ 是帶寬，控制高斯核函數的局部作用范圍。

（4）根據每個柵格的核密度估計值，根據公式（10）計算出每個柵格的充電需求指數。

（5）選擇預選點G’中充電需求指數最高的點，作為一個聚類中心點p，將其放入集合P，并根據該點創建一個新類簇c，將其放入集合C；

（6）根據步驟（5）中選出的聚類中心點p，設置建站距離R 代表場站之間最短距離，將p 和其服務半徑R 內的點從預選點集合G’中去除，得到新的預選點集合G’；

（7）重復步驟（5）（6），直到所有配送點到最近充電站的行駛路程最多半小時即曼哈頓距離10km，得到聚類分析的結果。

4.4 充電站規劃選址方法實現

本文以成都為例，運用改進的聚類算法構建的選址方法，進行成都市貨車充電站規劃選址，確保成都市內新能源貨車充電便利性的同時，最小化建站成本，最大化充電站潛在效益。新能源貨車充電站規劃選址方法，是考慮充電需求與競爭選址，使用改進的聚類算法進行規劃選址，該改進后的算法能減少離群點對聚類效果的影響，并避免聚類局部最優問題。方法實現流程如下：

（1）數據收集及預處理。本文以成都為例，爬取成都市區域內各配送點信息，以及已有充電站信息，并對數據進行特征值篩選、數據去重、空值處理等預處理操作。如表3、表4為數據預處理后的數據，表3為物流商圈位置信息，表4為已有貨車充電站位置信息和充電樁數量。

表3 成都市物流商圈位置信息

表4 成都市貨車充電站位置及充電樁數量

（2）競爭選址。根據收集到的已有貨車充電站的位置和充電樁數量信息，計算每個柵格的充電供給指數，畫出充電供給熱力圖如圖3，顏色越深代表充電供給越充足。本文4.1中設定，若該網格充電供給大于0，則不考慮在該網格建站，因此只考慮在白色區域建站。

圖3 充電供給熱力圖

（3）利用密度聚類分離離群點。由文中4.2，設定鄰域閾值為10km，點數閾值為1，利用DBSCAN尋找出離群點并剔除。如圖4所示，一個點代表一個配送點，通過密度聚類為10個簇，相同顏色的點屬于同一簇。如圖5所示，為簇的元素數量柱狀圖，將元素個數少于10的簇中的點視為離群配送點，將其剔除。

圖4 DBSCAN 聚類尋找離群點

圖5 DBSCAN 密度聚類分布圖

（4）根據改進后的聚類算法計算出聚類中心。將成都區域劃分為3km 長度的正方形小網格，即41×26個格點，根據物流商圈分布，計算出每個格點樣本的充電需求指數，得到充電需求指數熱力圖如圖6所示。此示例假設建站距離為9km，使用改進后的聚類算法算出多個聚類中心，該聚類中心所在網格即為場站選址推薦點，如圖7所示，紅點所在網格即代表規劃選址推薦點。

圖6 成都市充電需求指數熱力圖

圖7 改進后的聚類規劃選址結果

5 結果評估

5.1 評估模型建立

5.1.1 平均充電路程

充電站選址的目標之一為考慮貨車充電的便利性。本文通過貨車前往充電站的距離為評估模型，在構建評估模型前，明確如下假設：物流商圈中的貨車的優先考慮距離最近的五個充電站，并且路程距離假設為兩點間的曼哈頓距離。

式中：d(·)是由公式（11）計算的曼哈頓距離；p 為某配送點；si為距離該配送點最近的五個充電站之一。

5.1.2 平均周邊配送點的數量

充電站選址的另一目標是充電站效益。本文通過充電站周邊商圈數量為評估模型，在構建評估模型前，明確如下假設：充電站的主要充電車輛來源于周邊半小時路程內即十公里范圍內的物流商圈，并且物流車數量與物流園區數量呈正相關。

5.2 結果評估

設置建站距離分別為3km 至10km，當建站距離大于10km，配送點到最近充電站路程大于10km，因此最大考慮建站距離10km。建站個數、平均充電路程和平均周邊商圈個數的結果如下表5所示，走勢圖如圖7所示。通過對比可看出，隨著建站距離的增加，建站個數先大幅降低，7km 后逐漸趨于平滑；平均充電路程緩慢增加；平均周邊商圈的數量先增加，9km 后小幅降低。因此，考慮建站成本則距離越大越有利，考慮建站平均收益則距離越大越有利，考慮充電便利性則距離越小越有利，綜合考慮以上三點因素，可選擇建站距離7km 至8km，此時可較好的平衡建站成本、充電便利性與建站收益。

表5 選址結果對比

圖8 選址結果趨勢圖