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

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

1 引言

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

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

2 方法概述

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

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

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

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

充電需求一般分兩類，一類是路途中需求，常存在于長途行程中途補(bǔ)充電量的情況；另一類是始末點(diǎn)需求，由于電動車充電時長較長，因此多選擇在路途起點(diǎn)或終點(diǎn)休息時進(jìn)行充電。本文主要針對新能源貨車的選址，據(jù)調(diào)查顯示，由于當(dāng)前電池技術(shù)與配套設(shè)施的限制，目前新能源貨車多用于城市配送服務(wù)。由于路程較短，因此較多考慮始末點(diǎn)需求，即在配送起點(diǎn)或終點(diǎn)進(jìn)行充電。本文從城市配送相關(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)格，假設(shè)至少在長寬三公里方形柵格范圍內(nèi)能找到合適的建站位置，因此滿足式（1），網(wǎng)格空間，規(guī)劃區(qū)域內(nèi)任意一點(diǎn)qij有唯一對應(yīng)的網(wǎng)格gmn，使得qij∈gmn。

3.2 城市配送POI 分析

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

表1 城市配送POI

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

圖2 配送點(diǎn)分布圖

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

3.3 已有場站分析

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

表2 充電站信息

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

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

4.1 競爭選址下的建站需求

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

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

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

4.2 離群配送點(diǎn)

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

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

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

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

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

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

4.3 改進(jìn)的聚類算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 充電供給熱力圖

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

圖4 DBSCAN 聚類尋找離群點(diǎn)

圖5 DBSCAN 密度聚類分布圖

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

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

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

5 結(jié)果評估

5.1 評估模型建立

5.1.1 平均充電路程

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

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

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

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

5.2 結(jié)果評估

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

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

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