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

1 引言

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

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

2 方法概述

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

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

圖1 貨車充電站的規(guī)劃選址方法

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

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

3.1 選址區(qū)域分析

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

3.2 城市配送POI 分析

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

表1 城市配送POI

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

圖2 配送點分布圖

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

3.3 已有場站分析

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

表2 充電站信息

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

4 基于改進的聚類規(guī)劃選址方法

4.1 競爭選址下的建站需求

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

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

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

4.2 離群配送點

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

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

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

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

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

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

4.3 改進的聚類算法

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

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

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

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

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

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

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

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

4.4 充電站規(guī)劃選址方法實現(xiàn)

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

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

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

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

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

圖3 充電供給熱力圖

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

圖4 DBSCAN 聚類尋找離群點

圖5 DBSCAN 密度聚類分布圖

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

圖6 成都市充電需求指數(shù)熱力圖

圖7 改進后的聚類規(guī)劃選址結(jié)果

5 結(jié)果評估

5.1 評估模型建立

5.1.1 平均充電路程

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

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

5.1.2 平均周邊配送點的數(shù)量

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

5.2 結(jié)果評估

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

表5 選址結(jié)果對比

圖8 選址結(jié)果趨勢圖