基于成本控制的集合覆蓋模型的充電樁布局優(yōu)化

潘鳴宇，孫緒坤，李香龍，陳海洋，王偉賢，袁小溪，陳振

（1. 國(guó)網(wǎng)北京市電力公司電力科學(xué)研究院，北京市 海淀區(qū) 100085；2. 中國(guó)礦業(yè)大學(xué)(北京)應(yīng)急管理與安全工程學(xué)院，北京市 海淀區(qū) 100083；3. 國(guó)網(wǎng)北京市電力公司，北京市 海淀區(qū) 100085）

0 引言

隨著環(huán)境污染和資源過(guò)度損耗等問(wèn)題的日益突出，人們?cè)桨l(fā)注重清潔能源技術(shù)的開發(fā)與應(yīng)用。電動(dòng)汽車作為清潔能源技術(shù)的代表產(chǎn)物，具有能量密度高、使用壽命長(zhǎng)、對(duì)環(huán)境污染小等優(yōu)點(diǎn)，獲得市場(chǎng)的高度青睞[1]。根據(jù)國(guó)際能源署（IEA）的統(tǒng)計(jì)數(shù)據(jù)，截至2017 年，全球電動(dòng)汽車數(shù)量達(dá)到310 萬(wàn)輛，到2020 年有望突破1000 萬(wàn)輛[2]。但隨著電動(dòng)汽車數(shù)量的日益增加，自身存在的一些缺點(diǎn)也逐漸顯露出來(lái)，例如電動(dòng)汽車普遍存在續(xù)航里程短的問(wèn)題，這在一定程度上限制了電動(dòng)汽車的市場(chǎng)推廣。目前解決電動(dòng)汽車?yán)m(xù)航里程短這一問(wèn)題的方法主要包括兩種：提高動(dòng)力電池容量或增加電動(dòng)汽車充電樁數(shù)量。然而受限于技術(shù)原因，短時(shí)間內(nèi)無(wú)法研發(fā)出價(jià)格低廉且容量滿足要求的動(dòng)力電池[3]。因此，如何在兼顧成本和利用率的基礎(chǔ)上對(duì)充電樁進(jìn)行合理配置成為解決現(xiàn)階段電動(dòng)汽車推廣瓶頸的唯一途徑。

充電樁相當(dāng)于傳統(tǒng)能源供給汽車的“加油站”，但受電動(dòng)汽車?yán)m(xù)航里程限制，其建設(shè)標(biāo)準(zhǔn)更加苛刻[4]。國(guó)內(nèi)外部分學(xué)者針對(duì)充電網(wǎng)絡(luò)的合理規(guī)劃做過(guò)一些研究，Efthymiou[5]將線性規(guī)劃和遺傳算法相結(jié)合，提出了充電樁多目標(biāo)選址規(guī)劃模型；張帝等[6]基于電動(dòng)汽車運(yùn)營(yíng)數(shù)據(jù)，建立電動(dòng)汽車服務(wù)時(shí)間的排隊(duì)論模型，并提出該模型可提高充電站的運(yùn)營(yíng)效率；呂金炳等[2]參考充電樁運(yùn)營(yíng)公司的實(shí)際數(shù)據(jù)，對(duì)充電樁建設(shè)過(guò)程中的關(guān)鍵指標(biāo)進(jìn)行分析，提出了充電樁布局的規(guī)劃建議；趙明宇等[7]綜合考慮各類運(yùn)營(yíng)因素，以最低出行費(fèi)用為目標(biāo)參數(shù)，建立充電樁動(dòng)態(tài)布局模型。綜上可知，目前充電樁配置的研究主要通過(guò)數(shù)據(jù)分析和模型仿真等方法對(duì)其運(yùn)行速度和服務(wù)效率進(jìn)行優(yōu)化，對(duì)利用率改善和成本控制方面的報(bào)道較少。

據(jù)統(tǒng)計(jì)，各地公用充電樁的利用率普遍低于10%，且充電樁的覆蓋范圍分配不均，呈現(xiàn)“有樁無(wú)車，有車無(wú)樁”現(xiàn)象[8]，亟需一種布局優(yōu)化方案，在提高充電樁利用率的同時(shí)控制成本。本文以青島市黃島區(qū)的充電樁和人群流動(dòng)中心為研究對(duì)象，首先，將充電樁最少布置數(shù)量和最低成本費(fèi)用作為目標(biāo)函數(shù)，建立基于成本控制的集合覆蓋模型。然后，利用貪心算法迭代得到多組充電樁合理布局點(diǎn)。最后，以成本費(fèi)用指標(biāo)為依據(jù)，通過(guò)熵權(quán)法賦值對(duì)布局點(diǎn)成本費(fèi)用進(jìn)行定量評(píng)價(jià)，優(yōu)選最佳布局點(diǎn)。在保證布局點(diǎn)利用率的同時(shí)兼顧經(jīng)濟(jì)性，為相關(guān)地區(qū)的充電樁建設(shè)提供參考。

1 考慮成本控制的集合覆蓋模型的構(gòu)建

1.1 模型概述

公共設(shè)施的區(qū)位分配模型主要包括p 中值模型、p 中心模型、最大覆蓋模型以及集合覆蓋模型。其中p 中值模型和p 中心模型分別將需求點(diǎn)和布局點(diǎn)作為優(yōu)化重心，求解目標(biāo)為出行成本的最小化；最大覆蓋模型的優(yōu)化理念為在給定數(shù)量的設(shè)施下，覆蓋盡可能多的點(diǎn)；集合覆蓋模型則是在充分利用現(xiàn)有設(shè)施資源的前提下，實(shí)現(xiàn)布局點(diǎn)對(duì)需求點(diǎn)的有效覆蓋?？紤]到充電樁的布局原則為充分覆蓋和有效利用，集合覆蓋模型更適合充電樁的優(yōu)化布局。其他區(qū)位分配模型在優(yōu)化過(guò)程中會(huì)出現(xiàn)充電樁利用率低、充電距離過(guò)長(zhǎng)的問(wèn)題。

集合覆蓋模型是最優(yōu)化求解方法的一種，適用于離散布局情況下的最優(yōu)選址，其核心是保證代價(jià)最小的前提下將某一集合用若干子集覆蓋[9]。其優(yōu)化思路具體為：設(shè)X={x1,x2,···,xn}為一有限集合，Y={s1,s2,···,sm}為X子集的集合，則稱Y為X的子集族。子集族Y覆蓋了有限集X，表明X中的任意元素至少屬于集合Y中的一個(gè)子集，即X=。對(duì)于Y的一個(gè)子集Z∈Y，若Z中X的子集能夠?qū)做到全覆蓋，即， 則稱集合Z覆蓋了有限集X。而求解目標(biāo)則是確定Z中覆蓋X的最小子集Z*，使得[10]。

由于集合覆蓋模型屬于多項(xiàng)式復(fù)雜程度的非確定性（NPC）問(wèn)題，無(wú)法通過(guò)多項(xiàng)式算法得到它的精確結(jié)果，只能采用啟發(fā)式算法來(lái)求解。啟發(fā)式算法的實(shí)質(zhì)是在可接受范圍內(nèi)給出待解決的組合優(yōu)化問(wèn)題一個(gè)可行解[11]，主要包括蟻群算法、貪心算法和神經(jīng)網(wǎng)絡(luò)等，而貪心算法具有數(shù)據(jù)量小、步驟明確和便于定性定量分析等優(yōu)點(diǎn)，在工程求解領(lǐng)域受到廣泛應(yīng)用。

傳統(tǒng)的集合覆蓋模型在求解過(guò)程中會(huì)出現(xiàn)子集元素相同的情況，導(dǎo)致模型的計(jì)算結(jié)果缺乏唯一性，得不到最優(yōu)解。本文針對(duì)現(xiàn)有模型的限制對(duì)其進(jìn)行改進(jìn)，提出成本控制的集合覆蓋模型，通過(guò)引入費(fèi)用因子，在復(fù)數(shù)計(jì)算結(jié)果的情況下也可進(jìn)一步優(yōu)選。設(shè)M、N分別為候選布局點(diǎn)和充電需求點(diǎn)的集合，則M={1,2,···,m}；N={1,2,···,n}xi代表是否在i點(diǎn)設(shè)置充電樁，即：

使rij代表充電樁i到 充電需求點(diǎn)j的距離，R表示電動(dòng)汽車的報(bào)警行駛距離，yij代表j點(diǎn)是否在i點(diǎn)的覆蓋范圍內(nèi)，即：

令Ni為i點(diǎn) 充電樁覆蓋的需求點(diǎn)數(shù)量，Eij和 λj分 別代表i點(diǎn) 的費(fèi)用j和費(fèi)用j的 權(quán) 重，則i點(diǎn) 的費(fèi)用因子Ci為

基于成本控制的集合覆蓋模型目標(biāo)函數(shù)具體如下：

約束函數(shù)為

1.2 熵權(quán)法定權(quán)

在利用費(fèi)用因子對(duì)布局點(diǎn)進(jìn)行優(yōu)選前，首先需要確定對(duì)應(yīng)指標(biāo)的權(quán)重，考慮到費(fèi)用指標(biāo)以定量表述為主，在此采用熵權(quán)法進(jìn)行賦權(quán)。

熵最初是熱力學(xué)中象征混亂程度的一個(gè)狀態(tài)參量，1948 年，申農(nóng)（C E Shannon）將其引入信息論，建立熵權(quán)法計(jì)算模型。其本質(zhì)是根據(jù)數(shù)據(jù)的不確定性進(jìn)行賦權(quán)，指標(biāo)中信息含量越大，權(quán)重就越高。熵權(quán)法屬于客觀賦權(quán)法，相較于其他賦權(quán)方法，其能有效去除個(gè)人主觀對(duì)結(jié)果的影響，提高分析精度，在優(yōu)化配置、指標(biāo)決策等[12-13]方面具有廣闊的應(yīng)用前景。

熵權(quán)法賦權(quán)模型具體步驟如下[12]：

1）原始數(shù)據(jù)的規(guī)范化。

在具體分析過(guò)程中，令方案集元素為候選布局點(diǎn)，指標(biāo)集元素為充電樁建設(shè)時(shí)的費(fèi)用指標(biāo)，得到原始決策矩陣E， 其中ei j代 表布局點(diǎn)i的費(fèi)用j/萬(wàn)元。

由于指標(biāo)體系中各指標(biāo)值具有不同的量綱，存在數(shù)量級(jí)的巨大差異，為消除不同量綱指標(biāo)產(chǎn)生的不可公度性，需要進(jìn)行歸一化處理原始決策矩陣。

成本型指標(biāo)原始數(shù)據(jù)的標(biāo)準(zhǔn)化公式為

收益型指標(biāo)原始數(shù)據(jù)的標(biāo)準(zhǔn)化公式為：

由公式（7）或（8）對(duì)原始數(shù)據(jù)矩陣進(jìn)行歸一化處理，得到標(biāo)準(zhǔn)決策矩陣E′：

2）費(fèi)用j中布局點(diǎn)i特 征比重值Pij的計(jì)算：

3）費(fèi)用j熵值S j的計(jì)算：

式中：常數(shù)k 與樣本數(shù)n有關(guān)，一般令0 ≤S j≤1，并規(guī)定當(dāng)Pij=0時(shí)，PijlnPij=0。

4）費(fèi)用j熵權(quán) λj的計(jì)算：

1.3 模型求解

成本控制集合覆蓋模型的求解過(guò)程如圖1 所示，首先根據(jù)地區(qū)的需求分布，確定各布局點(diǎn)和需求點(diǎn)的空間位置，得到對(duì)應(yīng)的元素集合。然后按照貪心算法的求解原則，計(jì)算除去最大集合所含元素后最小集合包含的元素?cái)?shù)量Z，當(dāng)Z=0 時(shí)輸出得到多組滿足全覆蓋要求的布局點(diǎn)組合。最后，參考各布局點(diǎn)的成本數(shù)據(jù)對(duì)費(fèi)用指標(biāo)定權(quán)，計(jì)算不同布局點(diǎn)組合的費(fèi)用因子，得到模型的最優(yōu)布局點(diǎn)，求解結(jié)束。

2 算例分析

2.1 區(qū)域內(nèi)充電樁布局現(xiàn)狀分析

黃島區(qū)位于山東省青島市，與青島市區(qū)隔海相望，其東西部受地形限制，以工業(yè)區(qū)和船企為主，各類商業(yè)區(qū)集中在沿海和中部地區(qū)。充電樁作為電動(dòng)汽車的配套設(shè)施，通常會(huì)沿商業(yè)區(qū)布置，選址在人流密度較大的小區(qū)、商場(chǎng)或辦公場(chǎng)所附近[14]。通過(guò)調(diào)研地圖資料和相關(guān)文獻(xiàn)[15]，確定20 處人群流動(dòng)中心，將其作為充電樁的候選布局點(diǎn)和需求點(diǎn)。取電動(dòng)汽車充電預(yù)警后能夠行駛的最大距離為3 km[7]，將其作為充電樁的覆蓋半徑得到圖2。

圖1 模型求解流程圖Fig. 1 Flow chart of model solution

圖2 候選布局點(diǎn)以及現(xiàn)有充電樁分布Fig. 2 The candidate layout point and the distribution of existing charging piles

由圖2 可知，人群流動(dòng)中心的位置符合黃島各區(qū)塊的發(fā)展，且充電樁的布局也是基本隨人群流動(dòng)中心分布。但可以發(fā)現(xiàn)充電樁的覆蓋范圍不全，部分人群流動(dòng)中心處于范圍外，限制了該處人群電動(dòng)汽車的使用，且個(gè)別人群流動(dòng)中心處在大量充電樁的交叉區(qū)域內(nèi)，出現(xiàn)供過(guò)于需的情況。以上兩方面共同導(dǎo)致了“有樁無(wú)車，有車無(wú)樁”現(xiàn)象的出現(xiàn)。

2.2 優(yōu)化布局點(diǎn)的確定

對(duì)圖2 中各候選布局點(diǎn)的位置信息進(jìn)行提取，基于電動(dòng)汽車報(bào)警行駛距離為3 km 得到圖3。

由圖3 可得黃島區(qū)約束函數(shù)公式具體為：

圖3 布局點(diǎn)覆蓋距離關(guān)系Fig. 3 Covering distance of layout point

結(jié)合公式（4）對(duì)約束函數(shù)求解即可得到對(duì)需求點(diǎn)全覆蓋的最少布局點(diǎn)?？紤]到約束函數(shù)計(jì)算量較大，以布局點(diǎn)為橫列，需求點(diǎn)為縱列，將其轉(zhuǎn)化為距離矩陣后借助LINGO 貪心算法求解。以圖3 中的20 個(gè)候選布局點(diǎn)為基礎(chǔ)，得到A-L共12 組充電樁的優(yōu)化布局點(diǎn)：

計(jì)算所得的12 組布局點(diǎn)都可以在避免大量充電樁重疊覆蓋的同時(shí)達(dá)到對(duì)20 個(gè)需求點(diǎn)的全面覆蓋，為了得到最優(yōu)布局點(diǎn)，還需借助費(fèi)用因子Ci對(duì)其進(jìn)行定量?jī)?yōu)化。

2.3 指標(biāo)權(quán)重求解

原始數(shù)據(jù)的規(guī)范化。

對(duì)充電樁布局點(diǎn)的各類費(fèi)用調(diào)研后得到原始決策矩陣E，取3 類費(fèi)用指標(biāo)，分別為地價(jià)、管理費(fèi)和電費(fèi)。經(jīng)公式（11）、（12）、（13）計(jì)算，最后得到地價(jià)、管理費(fèi)和電費(fèi)的權(quán)重分別為λ1=0.33， λ2=0.36， λ3=0.31。

考慮到本文的指標(biāo)屬于成本型指標(biāo)，由公式（8）對(duì)原始數(shù)據(jù)矩陣進(jìn)行歸一化處理，得到標(biāo)準(zhǔn)決策矩陣E′：

2.4 最優(yōu)布局點(diǎn)的篩選

求得的12 組優(yōu)化布局點(diǎn)包括圖3 中的3、4、5、7、13、17、18、19、20，將對(duì)應(yīng)權(quán)重和數(shù)據(jù)代入公式（3）得到各布局點(diǎn)費(fèi)用因子：

將各組布局點(diǎn)的費(fèi)用因子累加，對(duì)結(jié)果從小到大排序：K=0.4797＜G=0.505＜I=0.5152＜C=0.532＜B=0.5573＜A=0.5675＜G=0.6239＜L=0.639＜F=0.6492＜E=0.6594＜D=0.6913＜H=0.7832，即最優(yōu)布局為K組的5、7、13、19 布局點(diǎn)，具體如圖4。

2.5 優(yōu)化效果分析

1）利用率。

充電樁對(duì)布局點(diǎn)的覆蓋能力可作為表征利用率的有效指標(biāo)。令各布局點(diǎn)的利用需求D為1，滿載利用率Dmax為6，充電樁i覆蓋范圍內(nèi)各布局點(diǎn)的重疊覆蓋度為Qz，Z為充電樁覆蓋的需求點(diǎn)集合，則充電樁i的 利用率Di為[16]：

由圖2 可得布局優(yōu)化前的利用率為：

由圖4 可得布局優(yōu)化后的利用率為：

圖4 充電樁布置優(yōu)化結(jié)果Fig. 4 Optimized deployment of charging pile

對(duì)各充電樁的利用率取均值，則優(yōu)化前后的平均利用率分別為0.23 和0.83，充電樁的利用率得到顯著提升。圖4 中優(yōu)化布局點(diǎn)5、7、13、19處設(shè)置的充電樁能夠?qū)崿F(xiàn)充電范圍對(duì)需求點(diǎn)的有效覆蓋，避免了充電范圍覆蓋不足和過(guò)度重疊現(xiàn)象的發(fā)生。

2）成本費(fèi)用。

依據(jù)調(diào)研的各類費(fèi)用數(shù)據(jù)，分別計(jì)算優(yōu)化前各處充電樁的費(fèi)用因子：

現(xiàn)有充電樁的費(fèi)用因子之和為2.9137。由于優(yōu)化后充電樁的設(shè)置數(shù)量明顯減少，且選址都位于費(fèi)用因子較低的布局點(diǎn)處，使模型求解的最優(yōu)布局點(diǎn)費(fèi)用因子降為0.4797，與優(yōu)化前的充電樁成本費(fèi)用相比得到大幅降低。

綜上，該模型的案例優(yōu)化能夠在設(shè)施有效利用的同時(shí)兼顧費(fèi)用指標(biāo)，避免了“有樁無(wú)車，有車無(wú)樁”現(xiàn)象的出現(xiàn)。

3 結(jié)論

本文針對(duì)充電樁利用率低下的問(wèn)題，提出一種改進(jìn)集合覆蓋模型，著重解決電動(dòng)汽車充電樁布局優(yōu)化問(wèn)題，主要研究結(jié)論如下：

1）成本控制集合覆蓋模型在保證充電樁范圍全面覆蓋和避免過(guò)度覆蓋的基礎(chǔ)上考慮布局成本，彌補(bǔ)了傳統(tǒng)集合覆蓋模型最優(yōu)解不唯一的缺點(diǎn)，為布局點(diǎn)的綜合優(yōu)選創(chuàng)造了條件。

2）以人群流動(dòng)中心為依據(jù)，利用本文模型對(duì)實(shí)際案例進(jìn)行分析。與現(xiàn)有布局點(diǎn)相比，求解的最優(yōu)布局點(diǎn)解決了充電范圍覆蓋不均的問(wèn)題，有效提高了充電樁利用率，并通過(guò)費(fèi)用因子篩選，進(jìn)一步降低了充電樁建設(shè)運(yùn)行的成本費(fèi)用，對(duì)推進(jìn)充電樁布局優(yōu)化有一定參考與借鑒意義。