基于空間語(yǔ)義和個(gè)體活動(dòng)的電動(dòng)汽車充電站選址方法

郭茂祖，張雅喆，趙玲玲

（1.北京建筑大學(xué) 電氣與信息工程學(xué)院，北京 100044；2.建筑大數(shù)據(jù)智能處理方法研究北京市重點(diǎn)實(shí)驗(yàn)室（北京建筑大學(xué)），北京 100044；3.哈爾濱工業(yè)大學(xué) 計(jì)算學(xué)部，哈爾濱 150001）

0 引言

作為電動(dòng)汽車（Electric Vehicle，EV）的能源提供方，公共充電站（Charging Station，CS）的選址規(guī)劃具有重要意義。從用戶需求出發(fā)，建立一個(gè)優(yōu)化的充電站網(wǎng)絡(luò)，有利于減輕電動(dòng)汽車用戶的距離焦慮。合理的電動(dòng)汽車充電站（Electric Vehicle Charging Station，EVCS）選址規(guī)劃同樣有利于提升現(xiàn)有充電設(shè)施的服務(wù)質(zhì)量和運(yùn)行效率［1-2］。

相關(guān)學(xué)者針對(duì)EVCS 選址規(guī)劃的不同問題進(jìn)行了研究：Zhang 等［3］考慮了外部環(huán)境和交通擁堵對(duì)EV 出行的影響，針對(duì)EV 用戶的充電行為，建立了以用戶軌跡數(shù)據(jù)為驅(qū)動(dòng)的充電網(wǎng)絡(luò)，并對(duì)規(guī)劃精度和效率進(jìn)行了均衡；Zhou 等［4］針對(duì)用戶行為的不確定性，開發(fā)了EV 充放電行為預(yù)測(cè)模型，并在2020 年英國(guó)電車行為數(shù)據(jù)集上對(duì)模型進(jìn)行了驗(yàn)證，該模型中采用的充電事件來(lái)源于實(shí)際調(diào)查以及基于數(shù)據(jù)驅(qū)動(dòng)的事件提取過程［5］；文獻(xiàn)［6］中基于深圳市BEV（Battery Electric Vehicle）出租車軌跡數(shù)據(jù)集，規(guī)劃了最佳EVCS 選址方案。以上研究可以找到理論上滿足用戶需求的最優(yōu)規(guī)劃方案，但忽略了實(shí)際場(chǎng)景下的充電站選址合理性。

大多數(shù)學(xué)者通過啟發(fā)式算法對(duì)EVCS 選址問題進(jìn)行求解。Pan 等［7］針 對(duì)HC（Home Charger）和NHC（No Home Charger）充電選擇行為，以最小化出行代價(jià)為目標(biāo)，使用遺傳算法搜索EVCS 的最佳位置；Jordán 等［8］考慮了社交網(wǎng)絡(luò)活動(dòng)和移動(dòng)信息，引入多代理系統(tǒng)理論和遺傳交叉算法，對(duì)多源數(shù)據(jù)進(jìn)行最佳配置估計(jì)，以啟發(fā)EVCS 選址過程；臧海祥等［9］探索了集充電站、EV 用戶與配電網(wǎng)的多重利益于一體的快速EVCS 模型，設(shè)計(jì)考慮充電需求空間分布的改進(jìn)自適應(yīng)遺傳算法進(jìn)行求解；夏敏浩等［10］綜合充電站建設(shè)、運(yùn)營(yíng)、維護(hù)的成本與用戶充電耗時(shí)成本為社會(huì)綜合成本函數(shù)，利用粒子群改進(jìn)算法和Voronio 圖規(guī)劃EVCS 的位置。啟發(fā)式算法的優(yōu)勢(shì)在于能夠快速獲得問題的可行解，但不能保證解的質(zhì)量。

基于用戶與目的地的出行分布預(yù)測(cè)可以有效分析充電需求與水平，從而為EVCS 提供依據(jù)。目前針對(duì)電動(dòng)汽車出行分布的預(yù)測(cè)方法如下：Pagany 等［11］基于用戶-目的充電需求定位（Electric Charging Demand Location，ECDL）模型，分析用戶在潛在興趣點(diǎn)（Point Of Interest，POI）的停留時(shí)間和訪問頻率，確定了充電站（CS）需求最高的地點(diǎn)，從而規(guī)劃能覆蓋充電需求的EVCS 選址方案。Chen 等［12］建立了一種考慮時(shí)空特性的DG-EV（Distributed Generation and Electric Vehicle）充電站模型：首先，監(jiān)控路網(wǎng)交通，構(gòu)建出行概率矩陣，描述用戶出行特征；然后，考慮充電網(wǎng)絡(luò)的綜合效益、系統(tǒng)負(fù)荷波動(dòng)和充電耗時(shí)成本，采用多目標(biāo)優(yōu)化方法規(guī)劃EVCS 網(wǎng)絡(luò)。

上述研究針對(duì)不同的EVCS 選址規(guī)劃目標(biāo)和影響因素構(gòu)建了任務(wù)模型，如提高EV 覆蓋率［13］、最大化基礎(chǔ)設(shè)施的利用率［14］。大部分現(xiàn)有的EVCS 選址規(guī)劃方法在充電需求分析時(shí)采用的車輛運(yùn)行數(shù)據(jù)不夠詳細(xì)精準(zhǔn)，且未充分考慮已建成充電站以及POI 對(duì)規(guī)劃的影響［15］。已建成充電站和POI的數(shù)據(jù)方便獲取，且對(duì)研究充電設(shè)施布局及周邊的路網(wǎng)交通具有重要的意義與價(jià)值。

針對(duì)以上問題，本文基于真實(shí)EV 軌跡數(shù)據(jù)與地理語(yǔ)義信息POI，進(jìn)一步對(duì)區(qū)域內(nèi)個(gè)體行為模式進(jìn)行分析，提出了一種EVCS 選址規(guī)劃方法。軌跡數(shù)據(jù)是時(shí)序數(shù)據(jù)的一種，除了有時(shí)間維度的依賴性還有空間維度的相關(guān)性。POI 數(shù)據(jù)為城市充電站研究提供了大量的地理語(yǔ)義信息，包括名稱、地址、功能、經(jīng)緯度等。本文結(jié)合EVCS 設(shè)施覆蓋范圍和分布特性，考慮候選EVCS 服務(wù)范圍和用戶的充電需求進(jìn)行時(shí)空分布預(yù)測(cè)，將無(wú)監(jiān)督學(xué)習(xí)與受約束的雙存檔進(jìn)化算法（Constrained Two-Archive Evolutionary Algorithm，CTAEA）相結(jié)合，構(gòu)建選址模型，更準(zhǔn)確地指導(dǎo)搜索方向，優(yōu)化模型性能，探索解決EVCS 部署問題的新途徑。

1 問題描述

EVCS 選址規(guī)劃是一個(gè)復(fù)雜的多約束多目標(biāo)優(yōu)化問題，通過合理的EVCS 布局，在既有EVCS 分布基礎(chǔ)上，最大限度地滿足用戶的充電需求；同時(shí)保證新的充電站建設(shè)成本最小。需要考慮的因素包括：1）現(xiàn)有EVCS 分布；2）EVCS 數(shù)量；3）充電需求；4）城市規(guī)劃的服務(wù)范圍和用戶需求。

EVCS 數(shù)量與現(xiàn)有充電站分布、城市規(guī)劃要求等密切相關(guān)，本文根據(jù)既有充電站分布和城市POI 分布，采用無(wú)監(jiān)督學(xué)習(xí)方法規(guī)劃EVCS 數(shù)量和初始布局。

此外，城市充電需求也與EV 用戶的出行密切相關(guān)。為此，本文在EV 的全球定位系統(tǒng)（Global Positioning System，GPS）軌跡數(shù)據(jù)中采用DBSCAN（Density-Based Spatial Clustering of Applications with Noise）［16］聚類挖掘潛在的充電需求，并建立充電需求估計(jì)和EVCS 選擇兩個(gè)模型，用于衡量充電需求滿足程度這一優(yōu)化指標(biāo)，方法整體框架如圖1所示。

圖1 基于無(wú)監(jiān)督學(xué)習(xí)的多目標(biāo)優(yōu)化方法框架Fig.1 Framework of unsupervised learning based multi-objective optimization method

1.1 基于無(wú)監(jiān)督學(xué)習(xí)的新建充電站數(shù)量估計(jì)方法

城市服務(wù)業(yè)的POI 數(shù)據(jù)能夠很好地反映地理空間中人的活動(dòng)布局和設(shè)施的分布情況，對(duì)社會(huì)公共服務(wù)領(lǐng)域有著重要的意義［17］。由于城市中的POI 的數(shù)量不定，分布不均勻，且受地理、地形、城市建設(shè)等因素的影響，聚類分析能夠從數(shù)據(jù)集中發(fā)現(xiàn)數(shù)據(jù)元素間的多維度聯(lián)系。因此，本文采用DBSCAN［16］算法挖掘POI 數(shù)據(jù)的集群分布與空間特征。

1.1.1 DBSCAN算法

DBSCAN 算法基于一組鄰域參數(shù)（?，MinPts）描述樣本點(diǎn)之間的連通關(guān)系，?是點(diǎn)的鄰域半徑，MinPts是簇內(nèi)點(diǎn)的最小閾值。對(duì)于未被訪問的點(diǎn)，如果鄰域內(nèi)點(diǎn)個(gè)數(shù)小于預(yù)定閾值，該點(diǎn)為噪聲點(diǎn)。DBSCAN 基于密度來(lái)連接和擴(kuò)散集群，定義密度聚類簇為“密度連通”區(qū)域，因此，形狀不規(guī)則的數(shù)據(jù)中也可以找到任意形狀的簇。

對(duì)整個(gè)數(shù)據(jù)集使用同一組鄰域參數(shù)求解，在密度分布不均勻時(shí)效果較差，所以本文采用分密度層次進(jìn)行聚類?；径x如下：

1）密度直達(dá)與可達(dá)。直達(dá)即為點(diǎn)xj位于點(diǎn)xi的?-鄰域內(nèi)?？蛇_(dá)是存在一個(gè)樣本序列H=h1，h2，…，hn，xj到h1是直達(dá)的，h1到h2是直達(dá)的，以此類推，xj可以間接連通到xi鄰域內(nèi)，此時(shí)則稱xj與xi密度可達(dá)。

2）密度相連。兩個(gè)樣本點(diǎn)xi、xj之間通過一個(gè)樣本點(diǎn)xl作為鏈接密度可達(dá)，則稱xi和xj密度相連，如圖2 所示。

圖2 DBSCAN連通圖Fig.2 DBSCAN connected graph

1.1.2 基于DBSCAN的POI聚類算法

根據(jù)城市規(guī)劃的標(biāo)準(zhǔn)，將已有EVCS 的半徑R范圍內(nèi)的POI 視為已滿足的充電需求，篩選出未被覆蓋的POI 視為待滿足的需求，將它作為選址因素進(jìn)行聚類，提取它的分布的關(guān)鍵特征，具體流程如算法1 所示，技術(shù)路線如圖3 所示。

圖3 本文算法的技術(shù)路線圖Fig.3 Technology roadmap of the proposed algorithm

算法1 基于DBSCAN 的POI 聚類算法。

輸入 數(shù)據(jù)集中未被覆蓋的POI 點(diǎn)D；半徑參數(shù)?；密度閾值MinPts；

輸出 基于密度的聚集集群。

第1）～6）行檢查數(shù)據(jù)集中尚未檢查過的對(duì)象p，符合鄰域參數(shù)建立新簇C；第7）～18）行建立候選集合N，繼續(xù)檢查N中的對(duì)象p'直至N為空；重復(fù)第1）～18）行直到所有對(duì)象都?xì)w入了某個(gè)簇或標(biāo)記為噪聲。

本文在聚類過程中進(jìn)行了三個(gè)層次的聚類，對(duì)不同層次的樣本點(diǎn)設(shè)定不同的（?，MinPts）進(jìn)行局部聚類：在密度高的區(qū)域，設(shè)置較小的?和較大的MinPts；在密度低的區(qū)域，則設(shè)置略大的?和略小MinPts；在密度均勻區(qū)域，則設(shè)置為高低密度參數(shù)的中間值，以保證最終選址的全區(qū)域覆蓋，避免出現(xiàn)充電供給空白。

1.2 基于電動(dòng)汽車軌跡數(shù)據(jù)的充電需求估計(jì)模型

本文采用成都二環(huán)路區(qū)域的相關(guān)數(shù)據(jù)，城市充電的需求較難度量，可以采用POI 分布間接表達(dá)充電需求的靜態(tài)關(guān)聯(lián)關(guān)系，實(shí)際充電需求還能由用戶的出行行為動(dòng)態(tài)衡量。EV軌跡數(shù)據(jù)代表個(gè)體行為模式，本文采用EV 的歷史行駛軌跡推斷可能的充電需求，并基于距離優(yōu)先規(guī)則構(gòu)建EVCS 選擇模型來(lái)量化充電需求的滿足情況。

基于EV 軌跡數(shù)據(jù)，即輸入時(shí)間、經(jīng)緯度和司機(jī)ID 的基本信息，得到司機(jī)需求和研究區(qū)域。潛在充電需求估計(jì)模型如下：首先，每10 min 統(tǒng)計(jì)一次網(wǎng)絡(luò)方格單元中的車流量，根據(jù)網(wǎng)絡(luò)中行駛車輛的GPS 軌跡數(shù)據(jù)獲得的平均車輛行駛速度vi；其次，計(jì)算出每個(gè)單元中的車輛數(shù)量fi；然后，通過電動(dòng)汽車普及率α、充電率β和每個(gè)電池中估計(jì)的車輛數(shù)的乘積估計(jì)單元i的充電需求。單元i的充電需求如式（1）所示；

其中：ρi（km/km2）是單元i中道路網(wǎng)的密度，μi（km2）是單元i的面積，ρi和μi的乘積是單元i中道路的長(zhǎng)度；α表示電動(dòng)汽車在全部機(jī)動(dòng)車輛中的比例；β表示移動(dòng)電動(dòng)汽車產(chǎn)生充電需求的概率。根據(jù)多網(wǎng)格區(qū)域的平均速度方程g（vi）估算單元i的流量密度。充電需求di根據(jù)城市新能源汽車普及率α=4%和某時(shí)刻產(chǎn)生充電需求率β=50%以及單元格內(nèi)車輛總數(shù)，隨機(jī)產(chǎn)生有充電需求的司機(jī)信息，供后續(xù)尋找最近充電站使用。

1.3 充電站的建設(shè)成本估計(jì)

充電站建設(shè)成本主要包括設(shè)備成本和運(yùn)營(yíng)成本，它們直接影響充電站建設(shè)的等級(jí)和位置［18］。

1）設(shè)備成本。

設(shè)備成本主要包括基礎(chǔ)設(shè)施成本、配電設(shè)施成本以及土建施工成本。不同地段地價(jià)差別不大，土地成本不直接影響選址方案的選取。因此，在固定的時(shí)期，單個(gè)EVCS 設(shè)備成本可以認(rèn)為是固定值，設(shè)備成本的計(jì)算公式如下：

其中：fa為單設(shè)備成本；n為新建充電站的設(shè)備數(shù)量。

2）運(yùn)營(yíng)成本。

運(yùn)營(yíng)成本主要包括員工費(fèi)用、站內(nèi)設(shè)備維護(hù)費(fèi)用等。年均維護(hù)費(fèi)用為初始投資的3%，年均運(yùn)營(yíng)與人工費(fèi)用為初始投資的6%。設(shè)備折舊年限為10 年，電動(dòng)汽車充電樁使用商業(yè)用電，電費(fèi)為0.70 元/kW·h（含稅及6%電損），收取充電服務(wù)費(fèi)為0.60 元/kW·h，合計(jì)每次充電為1.3 元/kW·h。具體計(jì)算公式如下：

其中：Fb為每小時(shí)每次充電的利潤(rùn)；T為一段時(shí)間內(nèi)總充電次數(shù)；Ea為單次充電費(fèi)用；Eb為商業(yè)用電價(jià)格；Fc為總投入成本；Sa和Sb分別為年均維護(hù)費(fèi)用與人工費(fèi)用占初始投資的百分比；Y是最大使用年限。

2 EVCS選址的多目標(biāo)優(yōu)化模型算法

為了方便周邊的POI，對(duì)新充電站位置進(jìn)行分析。為此，可以通過未覆蓋到的POI 估計(jì)充電規(guī)模。新充電站的位置應(yīng)遠(yuǎn)離現(xiàn)有充電站和其他新充電站的覆蓋區(qū)域，以減少重疊。在上述2 個(gè)獨(dú)立的約束基礎(chǔ)上，將EVCS 選址規(guī)劃問題定義為：

其中：F是構(gòu)成相互沖突的m個(gè)目標(biāo)的優(yōu)化函數(shù)；x是候選解矩陣；Ω被定義為搜索或決策變量空間；gj(x)和hj(x)是不等式約束和等式約束；aj表示第j個(gè)新充電站，bj表示需求點(diǎn)是否被覆蓋，若需求點(diǎn)被覆蓋則bj＝1，否則為0。

約束方程cj(x)的計(jì)算方式如下：

其中：?是用于將等式約束放松為不等式約束的足夠小的公差項(xiàng)（如?=10-6）。如果約束方程的值大于等于0 則返回0；否則返回該值的負(fù)值。x的約束違反值計(jì)算為：

1）最大化覆蓋POI 數(shù)量。

對(duì)于每個(gè)潛在的新建充電站位置X，計(jì)算到地圖上所有充電服務(wù)半徑Y(jié)內(nèi)的POI 的歐氏距離。

其中：n表示設(shè)施備選點(diǎn)數(shù)量；Si表示是否在設(shè)施備選點(diǎn)處選址的0-1 變量，若在設(shè)施備選點(diǎn)選址為1，否則為0；aij表示如果在設(shè)施備選點(diǎn)的范圍能覆蓋到興趣點(diǎn)，aij＝1，否則aij=0；m表示未覆蓋的POI 數(shù)量。

2）最大化與現(xiàn)有充電站之間的距離。

構(gòu)建潛在的新充電站位置與現(xiàn)有充電站位置之間的距離矩陣，并且建立一個(gè)新充電站位置矩陣，根據(jù)充電服務(wù)半徑設(shè)置距離閾值，要求向量之間距離小于閾值，并考慮所有可能的位置，將歐氏距離公式推廣到整個(gè)距離矩陣，以最大化現(xiàn)有EVCS與新EVCS 之間的距離。

其中：P為候選充電站位置；C為現(xiàn)有充電站位置；PM和CN分別代表第M個(gè)和第N個(gè)充電站；A代表歐氏距離矩陣，相鄰兩個(gè)充電站之間的距離不大于充電站服務(wù)半徑S的兩倍，Aˉ代表增廣矩陣表示法；Ti和Ti+1代表充電站與相鄰充電站；RS表示充電站覆蓋服務(wù)半徑；D表示充電站圓心。

3）最小化與需求司機(jī)的距離。

當(dāng)產(chǎn)生新充電站位置后，根據(jù)隨機(jī)產(chǎn)生的有充電需求的司機(jī)的經(jīng)緯度坐標(biāo)，利用曼哈頓距離計(jì)算距離司機(jī)最近的充電站，并統(tǒng)計(jì)新建充電站被選擇次數(shù)以及與需求司機(jī)的距離之和。

其中：n表示設(shè)施備選點(diǎn)數(shù)量；m表示未覆蓋的POI 數(shù)量；P為設(shè)施建設(shè)總數(shù)；ai表示第i個(gè)需求充電司機(jī)；dij為需求點(diǎn)到設(shè)施備選點(diǎn)的距離；Xj表示是否在設(shè)施備選點(diǎn)處選址的邏輯變量，若在備選點(diǎn)選址為1，否則為0；Xij表示全部需求點(diǎn)i被分配到設(shè)施備選點(diǎn)j；Sij表示需求點(diǎn)i是否分配到設(shè)施備選點(diǎn)j的邏輯變量，若分配到設(shè)施備選點(diǎn)為1，否則為0。

目標(biāo)函數(shù)f4為設(shè)施與需求點(diǎn)之間的距離總和最小，即就近原則，約束X=P為設(shè)施建設(shè)數(shù)量限制，可根據(jù)規(guī)劃部門的年度計(jì)劃確定。

3 基于CTAEA的模型求解

受約束的雙存檔進(jìn)化算法CTAEA 擁有兩個(gè)協(xié)作檔案CA（Convergence-oriented Archive）和DA（Diversity-oriented Archive）。當(dāng)DA 探索了尚未被CA 開發(fā)的區(qū)域，有助于跳過局部最優(yōu)區(qū)域或局部可行區(qū)域［19］。原始模型（未加約束條件的模型）存在難收斂、訓(xùn)練難以及模型自由不可控等問題［20］，本文利用協(xié)作檔案的互補(bǔ)效應(yīng)和精英信息，在繁殖過程中根據(jù)需求覆蓋模型評(píng)估親本和后代種群，從CA 和DA中分別選擇交配雙親；然后根據(jù)選擇機(jī)制（CA 基于種群，DA基于帕累托）更新CA 和DA，通過這兩個(gè)文件，引導(dǎo)模型選擇樣本，提高模型的搜索精度和速度，增強(qiáng)進(jìn)化過程的收斂性和多樣性，如算法2 所示。

算法2 基于CTAEA 的多目標(biāo)求解模型。

輸入 無(wú)監(jiān)督學(xué)習(xí)得到的候選充電站個(gè)數(shù)及時(shí)空數(shù)據(jù)；

輸出 最優(yōu)決策方案。

1）初始化。根據(jù)選址模型的約束條件構(gòu)建初始種群，設(shè)定閾值。

2）多樣性。設(shè)置交叉概率和變異概率，種群朝不同方向進(jìn)化。

3）評(píng)估。基于候選站點(diǎn)服務(wù)范圍和用戶需求評(píng)估并更新種群。

4）選擇。根據(jù)有限的交配機(jī)制自適應(yīng)地選擇合適親本，并通過適應(yīng)度函數(shù)評(píng)估。

5）迭代。判斷服務(wù)覆蓋范圍RS是否滿足相鄰充電站距離不大于服務(wù)充電站半徑的2 倍，滿足則輸出選址方案，不滿足則跳轉(zhuǎn)至3）。

6）驗(yàn)證?；谟行枨蟮乃緳C(jī)設(shè)計(jì)選擇函數(shù)，分析候選站點(diǎn)被選擇次數(shù)，驗(yàn)證模型的有效性。

3.1 密度估計(jì)

為了便于密度估計(jì)，將目標(biāo)空間分為N個(gè)子區(qū)域，每個(gè)子區(qū)域由唯一權(quán)重向量表示。對(duì)一組均勻分布的權(quán)重向量進(jìn)行采樣，即W=(w1，w2，…，wn)，子區(qū)域i∈{1，2，…，N}，m為目標(biāo)數(shù)量。目標(biāo)空間的第i個(gè)子區(qū)域表示如下：

其中：j∈{1，2，…，N}；（F（x），W）為F（x）和W之間的銳角角度；Wi、Wj表示均勻分布的第i和j個(gè)權(quán)重向量。在建立子區(qū)域后，每一個(gè)解xi都與唯一子區(qū)域相關(guān)聯(lián)，它的索引被確定為：

將解與子區(qū)域關(guān)聯(lián)后，子區(qū)域的密度化簡(jiǎn)為區(qū)域關(guān)聯(lián)解的數(shù)量。

3.2 更新CA

首先生成一個(gè)雜交種群H、CA 和后代群體Q 的組合。首先，計(jì)算i中的每個(gè)解x與它最近的鄰居之間的距離；然后，在H中選擇可行的解決方案，存儲(chǔ)到St，后續(xù)程序取決于St的大小，最壞解決方案xw定義為：

其中：z*表示解集中的理想點(diǎn)表示第j個(gè)子問題尋找當(dāng)前種群的最優(yōu)值，利用目標(biāo)函數(shù)最大值逼近，不斷更新再將它們組合成新的理想點(diǎn)；gtch為臨時(shí)存儲(chǔ)器中可行解的最大值，用于調(diào)整存儲(chǔ)器的大小，保證種群的多樣性；為第j個(gè)目標(biāo)函數(shù)的第i個(gè)權(quán)重向量；fj(x)為第j個(gè)目標(biāo)函數(shù)。

如果種群中的可行解不存入新的CA，則構(gòu)造一個(gè)新的雙目標(biāo)優(yōu)化問題：

通過約束計(jì)算所有充電服務(wù)半徑內(nèi)的POI 與EVCS 的歐氏距離進(jìn)行排序并更新現(xiàn)有種群輸出到DA，以進(jìn)一步平衡收斂性、多樣性和可行性。

3.3 更新DA

CA 與DA 有著相同的POI 覆蓋率更新方法。與CA 不同的是，DA 的目標(biāo)是提高解決方案的多樣性。在非支配解集Oi中最優(yōu)解xb定義為：

算法重復(fù)迭代直到DA 空間被占滿。算法流程如算法3所示。

算法3 更新CA 和DA。

輸入 具有相同大小為N的兩個(gè)檔案CA 和DA 的子代；非支配解集O；

輸出 CA 和DA 的更新種群。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 數(shù)據(jù)說(shuō)明

實(shí)驗(yàn)運(yùn)行環(huán)境是Windows10 操作系統(tǒng)，AMD Ryzen 7 5800H CPU @3.20 GHz，16 GB 內(nèi)存，Python 3.6?；诘蔚纬鲂泄締?dòng)的蓋亞數(shù)據(jù)開放計(jì)劃，采集成都部分區(qū)域2016 年11 月的4 416 輛出租車的原始軌跡數(shù)據(jù)，數(shù)據(jù)集信息與司機(jī)軌跡數(shù)據(jù)如表1～2 所示。實(shí)驗(yàn)道路地圖數(shù)據(jù)來(lái)源于開源的地圖平臺(tái)OpenStreetMap（www.openstreetmap.org）。根據(jù)當(dāng)前和潛在的EV 用戶的訪問地點(diǎn)、頻率和時(shí)長(zhǎng)，將工作、商業(yè)、購(gòu)物、私人事務(wù)和休閑作為主要出行目的，確定了8 種POI 類別，分別是購(gòu)物中心、酒店、停車場(chǎng)、政府機(jī)構(gòu)、寫字樓、醫(yī)院、以公共交通為目的的火車站和飛機(jī)場(chǎng)，接待游客為目的的公園名勝古跡，總量共計(jì)20 000 余條。

表1 數(shù)據(jù)集信息Tab.1 Information of dataset

表2 司機(jī)軌跡數(shù)據(jù)示例Tab.2 Examples of driver trajectory data

根據(jù)充電需求式（1），得到隨機(jī)充電需求司機(jī)的具體信息。將隨機(jī)產(chǎn)生充電需求的車輛經(jīng)緯度坐標(biāo)與成都二環(huán)充電站坐標(biāo)進(jìn)行比對(duì)，計(jì)算離司機(jī)距離最近的充電站的坐標(biāo)，匹配結(jié)果如表3 所示。

表3 匹配有需求司機(jī)最近充電站Tab.3 Matching drivers with demand to the nearest charging station

4.2 算例分析

4.2.1 規(guī)劃區(qū)域及參數(shù)設(shè)置

根據(jù)1.1 節(jié)和1.2 節(jié)提出的充電需求模型，將計(jì)算得到的9 100 余個(gè)興趣點(diǎn)和5 100 余名司機(jī)數(shù)據(jù)進(jìn)行融合。為了更好地描述實(shí)驗(yàn)結(jié)果，選取坐標(biāo)范圍（104°01'E～104°12'E，30°62'N～30°69'N）內(nèi)的數(shù)據(jù)進(jìn)行展示。鄰域參數(shù)設(shè)置分別為（10，10）、（20，9）、（30，8）。采用本文提出的CTAEA，由初始種群經(jīng)過交叉變異迭代出15 個(gè)最優(yōu)候選充電站經(jīng)緯度，根據(jù)密度聚類參數(shù)得到實(shí)驗(yàn)結(jié)果示例如圖4 所示，將選址的結(jié)果標(biāo)記在路網(wǎng)上面。

圖4 高、中、低密度聚類效果Fig.4 Effects of high，medium and low density clustering

圖5 為成都二環(huán)車輛軌跡分布，由于原始數(shù)據(jù)中軌跡數(shù)量龐大，此處只對(duì)軌跡數(shù)據(jù)進(jìn)行隨機(jī)采樣。圖5 中，綠色軌跡顏色越亮，則車輛軌跡越多。圖6 展示了成都市POI 的分布情況。圖7 統(tǒng)計(jì)了二環(huán)網(wǎng)絡(luò)方格中的車流量情況。

圖5 成都二環(huán)車輛軌跡分布圖Fig.5 Vehicle trajectory distribution map of Chengdu

圖6 成都市POI的分布情況Fig.6 Distribution of POIs in Chengdu

圖7 成都市二環(huán)車流量統(tǒng)計(jì)Fig.7 Traffic flow statistics of second-ring road in Chengdu

成都市二環(huán)現(xiàn)有21 個(gè)充電站，每個(gè)充電站將覆蓋半徑為R=1 km 的服務(wù)區(qū)域。將三個(gè)層次的聚類結(jié)果合并取均值確定新建充電站個(gè)數(shù)（15），根據(jù)出租車的軌跡數(shù)據(jù)以及興趣點(diǎn)得出了15 個(gè)充電站的選址方案，并將候選充電站用“+”號(hào)標(biāo)記出來(lái)，以1 km 服務(wù)半徑為覆蓋范圍。

4.2.2 結(jié)果分析

根據(jù)本文模型得出如圖8 所示的新建充電站方案。研究區(qū)域內(nèi)興趣點(diǎn)數(shù)量為9 110，未建新充電站之前，區(qū)域內(nèi)POI 覆蓋數(shù)為4 488，覆蓋率為49.3%；新建15 個(gè)充電站后，區(qū)域內(nèi)所有的被覆蓋興趣點(diǎn)數(shù)為6 632，覆蓋率為72.8%。

圖8 需求區(qū)域新建充電站Fig.8 New charging stations in demand area

為了驗(yàn)證本文方法的有效性，依據(jù)城市新能源汽車普及率及單位時(shí)間內(nèi)充電需求率，在研究區(qū)域內(nèi)隨機(jī)篩選有充電需求的電動(dòng)車5 109 輛，充電站被選擇情況如表4 所示。選擇原有充電站次數(shù)為2 466，選擇率為48.3%，平均每個(gè)原有充電站被選擇率為2.29%；選擇新建充電站次數(shù)為2 488，選擇率為48.7%，平均每個(gè)新建充電站被選擇率為3.25%。通過以上數(shù)據(jù)可以看出，當(dāng)前新能源汽車產(chǎn)業(yè)發(fā)展迅猛。充電站被選中率高也從側(cè)面反映了周邊配套設(shè)施完善，電力需求穩(wěn)定以及用戶需求達(dá)標(biāo)。進(jìn)一步驗(yàn)證了選擇率對(duì)評(píng)估選址方案的合理性，對(duì)做好電動(dòng)汽車的充電站建設(shè)工作提供了可行性。

表4 新建充電站被選擇次數(shù)Tab.4 Number of selected times of new charging stations

選址方案中的充電站主要集中于二環(huán)周邊以及春熙路、寬窄巷子等地，覆蓋了人流量大打車需求高的區(qū)域，為電動(dòng)出租車提供充電服務(wù)的頻率較高。根據(jù)雙存檔進(jìn)化模型對(duì)充電站進(jìn)行選址優(yōu)化候選充電站選擇率為48.7%，基本滿足司機(jī)充電需求。

4.2.3 對(duì)比分析

將NSGA2（Non-dominated Sorting Genetic Algorithm 2）［21］、SPEA2（Strength Pareto Evolutionary Algorithm 2）［22］作為對(duì)比的優(yōu)化算法，以設(shè)備成本、運(yùn)營(yíng)成本為建設(shè)運(yùn)營(yíng)成本，研究區(qū)域充電需求以及前往充電站距離和等構(gòu)成優(yōu)化算法的目標(biāo)函數(shù)，以相鄰充電站的間隔距離、POI 最大服務(wù)范圍為約束條件進(jìn)行選址，這兩種算法的候選充電站分布如圖9 所示。

圖9 不同算法的候選充電站分布情況Fig.9 Distribution of candidate charging stations of different algorithms

從候選充電站的分布可以看出，本文方法選址范圍大多均勻分布在二環(huán)周圍，而優(yōu)化算法的選址范圍則密集分布于二環(huán)內(nèi)的部分區(qū)域。由于出租車的主要收入是人流聚集的二環(huán)內(nèi)，所以在營(yíng)業(yè)過程中就餐、購(gòu)物、辦公等興趣點(diǎn)也主要集中在二環(huán)以內(nèi)，以興趣點(diǎn)密集區(qū)域作為站址，司機(jī)選擇次數(shù)相應(yīng)也會(huì)較高，所以充電站站址在二環(huán)以內(nèi)及周邊會(huì)相對(duì)較多?？紤]到選址過程中以研究區(qū)域車輛到達(dá)區(qū)域作為選址參考，因此站址的分布要全面但也相對(duì)分散，由于可能存在部分站址需求量較小或隨機(jī)不穩(wěn)定的情況，從而導(dǎo)致充電站分布較為密集。

假設(shè)研究區(qū)域內(nèi)興趣點(diǎn)和有需求司機(jī)數(shù)不變，不同算法在數(shù)據(jù)集上的性能對(duì)比結(jié)果和司機(jī)選擇距離的成本對(duì)比如表5～6 所示?？梢钥吹剑?/p>

表5 建站前后不同算法的性能對(duì)比Tab.5 Performance comparison of different algorithms before and after station construction

1）從表5 可知，相較于NSGA2 和SPEA2，CTAEA 在POI覆蓋率指標(biāo)上分別提高了22.9 個(gè)百分點(diǎn)和20.6 個(gè)百分點(diǎn)，選擇的新建充電站位置比其他算法的候選位置分布更均勻，且重復(fù)區(qū)域小、利用率高。

2）在需求司機(jī)數(shù)一定的情況下，根據(jù)曼哈頓距離得出司機(jī)選擇最近充電站的最小距離和，如表6 所示。基于CTAEA的司機(jī)選擇的距離和最小，平均選擇距離更短，能更方便快捷地幫助司機(jī)找到充電站。對(duì)于建站后覆蓋率和平均選擇率，NSGA2 和SPEA2 表現(xiàn)出了嚴(yán)重的性能下降，對(duì)新空間的探索能力有限，導(dǎo)致收斂到局部最優(yōu)解。

表6 不同算法的司機(jī)選擇距離成本Tab.6 Driver’s selected distance cost of different algorithms

3）從表5 中的新建充電站平均選擇率來(lái)看，進(jìn)化算法CTAEA、NSGA2 明顯優(yōu)于經(jīng)典遺傳算法SPEA2。從表6 可知，CTAEA 的平均選擇距離相較于現(xiàn)有充電站縮短了61.1%，相較于NSGA2 和SPEA2 分別縮小了18.9% 和25.5%，充電便利性有所提高。

CTAEA 取得了整體最佳的地理空間語(yǔ)義覆蓋率與候選充電站選擇率，進(jìn)一步說(shuō)明了本文方法的合理性與有效性。

4.3 充電站經(jīng)濟(jì)性

充電站選址以充電站與電動(dòng)車為對(duì)象，以充電站建設(shè)運(yùn)營(yíng)的經(jīng)濟(jì)性與電動(dòng)車充電的便利性為目標(biāo)優(yōu)化選址。充電站經(jīng)濟(jì)性主要由充電站建設(shè)運(yùn)營(yíng)成本與營(yíng)收兩個(gè)因素決定，建設(shè)成本主要由充電設(shè)備、土建施工與其他輔助成本構(gòu)成，運(yùn)營(yíng)成本主要由設(shè)備運(yùn)維費(fèi)用、電費(fèi)、工作人員工資構(gòu)成，營(yíng)收為車輛使用充電設(shè)備的充電服務(wù)費(fèi)。

本文研究成本最小化即日均盈利最大化。假設(shè)新建充電站15 個(gè)，研究區(qū)域內(nèi)市場(chǎng)上充電站有21 個(gè)，電動(dòng)出租車北汽型號(hào)：EV200，電池容量30.4 kW·h。

4.3.1 出租車充電站收益分析

假設(shè)一個(gè)純電動(dòng)汽車充電站，有以下特點(diǎn)：

1）充電站備有32 個(gè)快充和12 個(gè)慢充充電樁；

2）充電站設(shè)備保養(yǎng)由各供商提供服務(wù)，服務(wù)費(fèi)用包含在電價(jià)格當(dāng)中；

3）假設(shè)每次充電31 kW·h 供電動(dòng)出租車平均行駛200 km；

4）年均維護(hù)費(fèi)用為固定投資的3%、年均運(yùn)營(yíng)與人工費(fèi)用為固定投資的6%，設(shè)備折舊年限約為10 年；

5）普通轎車的油耗為10 L/100 km，油價(jià)9.0 元/L，運(yùn)行成本為90 元；電動(dòng)轎車行駛100 km 耗電15～20 kW·h，若要運(yùn)行成本與燃油車相當(dāng)，電價(jià)約為5.2 元/kW·h。

出租車充電站固定成本（充電設(shè)備+配電設(shè)備+土建施工）約為2 491.5 萬(wàn)元，每年運(yùn)營(yíng)成本（員工費(fèi)用+設(shè)備維護(hù)）約為224.2 萬(wàn)元。

4.3.2 收入分析

根據(jù)假設(shè)，電動(dòng)轎車平均行駛200 km 充電一次，充電站每天被選擇次數(shù)為2 488，每次為電池充電31 kW·h，則充電站每天收入約為3.33 萬(wàn)，每年收入約為1 215 萬(wàn)，充電站全壽命期內(nèi)充電站收入1 215×10=12 150 萬(wàn)，總支出4 734 萬(wàn)，收入7 416 萬(wàn)，每年收入741.6 萬(wàn)。

4.3.3 收益分析

根據(jù)成本及收入分析，充電站在使用期內(nèi)的總支出約為4 734 萬(wàn)，在充電站有效使用期內(nèi)的總收入約為12 150 萬(wàn)，則充電站使用期內(nèi)的收益為7 416 萬(wàn)，平均年收益為741.6 萬(wàn)?？梢钥闯霰疚姆椒ㄊ钩潆娬窘ㄔO(shè)投資效益得到顯著提升，更有效地融入社會(huì)各方面的資金和力量，使充電站建設(shè)實(shí)現(xiàn)更加良好的發(fā)展，從而充分確保電動(dòng)汽車能夠?qū)崿F(xiàn)進(jìn)一步的普及和應(yīng)用。

5 結(jié)語(yǔ)

本文提出了一種基于時(shí)空數(shù)據(jù)的多目標(biāo)充電站選址規(guī)劃方法，采用基于密度的聚類算法得出研究區(qū)域內(nèi)興趣點(diǎn)的分布，根據(jù)城市規(guī)劃對(duì)非服務(wù)半徑內(nèi)POI 進(jìn)行地圖匹配，得到POI 密集區(qū)域并將它作為充電站候選區(qū)域，根據(jù)POI 聚類結(jié)果確定新建充電站個(gè)數(shù)；構(gòu)建雙存檔進(jìn)化算法對(duì)密集區(qū)域進(jìn)一步約束以得到充電站站址分布；在站間距最大化以及新充電站覆蓋需求POI 最多的多目標(biāo)約束下，得到電動(dòng)汽車選址優(yōu)化方案。實(shí)驗(yàn)結(jié)果與評(píng)價(jià)函數(shù)表明：

1）有需求興趣點(diǎn)的密集區(qū)域主要集中在車站、學(xué)校、醫(yī)院以及旅游景點(diǎn)。從實(shí)驗(yàn)結(jié)果可以看出，新充電站的候選位置多集中在離市中心稍遠(yuǎn)的位置，說(shuō)明未滿足充電需求的區(qū)域已被分配了新的充電站。

2）隨機(jī)采樣成都二環(huán)司機(jī)軌跡數(shù)據(jù)，合并新舊充電站并匹配其最近充電站，新充電站的選擇次數(shù)高達(dá)48.7%，滿足司機(jī)的充電需求。

3）在司機(jī)選擇距離成本上，本文算法雖有效平衡了收斂性和多樣性，降低距離成本，但對(duì)于成都市1 km 之內(nèi)的覆蓋范圍仍相差110 m，綜合考慮可能是因?yàn)檠芯繀^(qū)域較為固定且司機(jī)基數(shù)大，而新建充電站個(gè)數(shù)與司機(jī)未達(dá)到飽和，后續(xù)將在該方面深入研究。

最后，以成都市的POI 經(jīng)緯度和2016 年11 月成都二環(huán)司機(jī)GPS 軌跡數(shù)據(jù)為實(shí)驗(yàn)樣本得出了15 個(gè)充電站的選址方案，根據(jù)司機(jī)的充電便利性與充電站的經(jīng)濟(jì)性進(jìn)行合理性分析。結(jié)果表明了本文方法的適用性和有效性，既考慮了車主的便利性，又考慮了充電站的盈利。