張軼倫 黃劍秋 戴佳煒

(上海交通大學機械與動力工程學院， 上海 200240)

1 引言與文獻綜述

眾多學者對電動汽車充電站選址定容問題從多個角度展開了研究，此類問題的主要研究方法分為聚類方法、啟發(fā)式方法和優(yōu)化類方法。

在聚類方法方面，馮瑛敏等基于給出的上下限，通過層次聚類、中心聚類等方法直接得到選址決策[1]。趙書強等采用Voronoi 圖劃分每個充電站所服務的負荷區(qū)[2]；同時，也提出了啟發(fā)式方法進行充電站選址。作者認為用戶可根據(jù)最短路計算結果進行就近選擇，并在此基礎上采用差分進化粒子群方法得到布局規(guī)劃結果[3]。類似地，Bai X 等以最小化客戶行駛和充電時間成本為目標，考慮客戶需求在不同站點的分流規(guī)律，設計基于NSGA-II和鄰域搜索的啟發(fā)式方法對問題進行求解[4]。

在優(yōu)化類方法中，熊虎等基于Voronoi 圖和排隊論，考慮快充站點能力和需求的隨機性，分析了電動汽車公共充電站布局規(guī)劃問題[5]。劉文霞以減少客戶等待時間和降低充電站投資成本為目標，建立排隊論模型對擁堵地區(qū)客戶平均隊列長度及等待時間進行了分析，提出了快充站點設備優(yōu)化和容量調整方法[6]。Xie F等同時考慮每個OD(Origin-Destination)對路徑和站點的匹配，以及充電的起止點；用排隊論描述隨機的充電行為，并采用基于仿真的優(yōu)化框架設計遺傳算法[7]。對于此類隨機性問題，部分學者采用魯棒優(yōu)化方法進行求解[8]。同時，也有學者從多層規(guī)劃的角度進行建模。段豪翔等采用雙層規(guī)劃方法開展研究，以體現(xiàn)充電站與配電網(wǎng)規(guī)劃的協(xié)同性[9]。Liu H和Wang D Z W建立了三層規(guī)劃模型，第一層是根據(jù)成本來定位；第二是客戶根據(jù)去充電的金錢成本、時間成本和距離成本，按概率篩選；第三，多客戶的均衡[10]。

在建模時有以下幾個重要因素值得考慮：成本、客戶選擇、服務水平。成本的定義是多元化的，主要包括時間和空間等角度[11-12]。例如，Arslan O和Karaan O E同時考慮城區(qū)內和道路上的充電站布局問題，以距離成本為目標，建立數(shù)學模型并進行求解[13]?？蛻暨x擇方面，主要通過建立效用函數(shù)來衡量客戶選擇偏好[14]。Li J 等認為，客戶的行為包括搜索行為和充電行為。在此基礎上，利用貝葉斯推測的方法來預測需求[15]。Yang W 采取了基于OD的需求建模方式，并以此為基礎來衡量客戶的選擇情況[16]。Cavadas J 等定義了與距離負相關的效用值，并認為客戶選擇的依據(jù)是以需求和該效用值相乘，在此基礎上建立了靜態(tài)需求下的選址定容模型[17]。服務水平方面，一類比較常見的方式是以平均充電距離來衡量[18]。

通過上述分析不難看出，目前學界對于該領域問題的研究主要依賴傳統(tǒng)的優(yōu)化方法，缺少從數(shù)據(jù)中提煉的規(guī)律。建模過程中一般假設需求遵循某已知統(tǒng)計分布，進行求解隨機規(guī)劃問題。此外，現(xiàn)有文獻較少對客戶的特點和行為偏好做全面的刻畫，即客戶畫像；更缺乏基于客戶細分的決策優(yōu)化過程。

因此，本文相比于當前其他研究，將主要在客戶行為偏好方面進行探究，并將數(shù)據(jù)中體現(xiàn)的規(guī)律與傳統(tǒng)優(yōu)化模型相融合。首先，對客戶進行聚類，基于客戶細分來描述不同類型客戶的偏好和充電行為規(guī)律。在此基礎上，發(fā)現(xiàn)客戶在充電結束后均對充電樁有不同程度的占用，因此提出“能力折扣”的概念，更加貼近現(xiàn)實情況。此外，定義供需比作為給定站點、充電樁種類和時段后的服務水平，方便政府決策者在充電站布局規(guī)劃時進行參考。本研究以最小化充電站建設成本和最小化客戶充電成本為目標，考慮客戶細分、能力折扣、樁選擇偏好、預算限制、容量限制、服務水平限制等因素，建立混合整數(shù)線性規(guī)劃模型，對單階段選址定容問題加以求解，得出各備選站點各種充電樁的建設容量。

2 數(shù)據(jù)分析

由于本文基于實際數(shù)據(jù)進行研究，故需先對數(shù)據(jù)集進行探索分析，以此為數(shù)學建模提供參考依據(jù)。

由于公共類充電站數(shù)量遠高于其他類別充電站數(shù)量(如圖1所示)，故為方便起見，本研究只關注公共類充電站。

圖1 上海市公共類充電站分布圖Fig.1 Distribution of public charging stations in Shanghai

而后進行三方面的數(shù)據(jù)分析：充電設施布局情況、充電站利用率情況、充電行為分析等，下文將分別加以描述。

2.1 充電設施布局情況

主要按行政區(qū)對各區(qū)域的充電站分布情況進行分析評判。由于浦東新區(qū)網(wǎng)點布局規(guī)劃最為合理和成熟(如圖2所示)，故這里以浦東新區(qū)為例進行展示。

圖2 浦東新區(qū)充電站分布圖Fig.2 Distribution of charging stations of Pudong District

2.2 充電站利用率情況

以某個充電站內每天每根樁的充電次數(shù)和充電工作時間這兩個指標，來衡量該充電站的利用率情況，大部分充電站不存在排隊等待情況，因為其利用率不高。這里展示利用率較高和較低的實例，如表1所示。

表1 站點利用率實例Table 1 Charging station utilization

由此可知，需要考慮站點(或充電樁)的服務水平，該指標應與充電站服務能力和充電需求的比值相關。設置服務水平限制，以避免部分站(或樁)的服務能力在某個時段不滿足需求。

2.3 充電行為分析

車輛行駛和充電記錄中給出了充電開始時間、充電結束時間、初始SOC、結束SOC、充電量、充電時長；并可以在此基礎上計算距離上次充電完成的時間和距離、最大功率、平均功率、所使用的充電樁種類(快充或慢充)。這些特征共同描述了充電行為規(guī)律，并可對后續(xù)建模提供相關參考和依據(jù)。

2.3.1 時段劃分

由于需求呈現(xiàn)時變性，則選址定容模型必須考慮時間這個維度。本問題中，以開始充電時間為依據(jù)對時段進行劃分。為保證使得各時段之間區(qū)別較為明顯，根據(jù)對各個車輛的開始充電時間的頻數(shù)分布統(tǒng)計，劃定時段為：t=1, 22:00-4:00;t=2, 4:00-10:00;t=3, 10:00-16:00;t=4, 16:00-22:00。

2.3.2 能力折扣

對比車輛行駛和充電記錄中的充電時長，和充電站使用記錄中的充電樁占用時長，可以發(fā)現(xiàn)存在充電樁無效占用的情況，即沒有充電但是車仍然停放在充電位上。這會嚴重影響充電站的服務能力，在設計模型時必須對“能力折扣”的現(xiàn)象引起重視。其中，充電樁理論充電能力打折的程度用一個系數(shù)表示，定義為有效工作時間/總占用時間。

2.3.3 客戶聚類

使用層次聚類方法對純電動車和混動車分別進行聚類，每類車(客戶)的輸入特征包括：充電開始時間處于4個時段的頻率，初始SOC平均值，使用快充樁頻率，充電電量平均值、方差、四分位點，充電時間平均值、方差、四分位點，距離下次充電時間的平均值、最大值，距離下次充電距離的平均值和最大值。層次聚類方法示意如圖3所示。

圖3 層次聚類示意圖Fig.3 Hierarchical clustering

為方便計算，同時保證各類之間的差異性，本研究中純電車和混動車分別各自聚成4類，聚類結果和數(shù)值特征如圖4、表2和表3所示。

表3 各類客戶數(shù)值特征Table 3 Numerical characteristics

圖4 客戶聚類結果Fig.4 Customer segmentation result

表2 客戶聚類結果Table 2 Customer segmentation result

完成客戶聚類后，在數(shù)學建模過程中和參數(shù)計算時，都應注重各類客戶之間的區(qū)別，這也是對客戶偏好的考慮。

3 數(shù)學模型

本章將在文獻綜述和數(shù)據(jù)分析的基礎上，對充電樁選址定容問題進行具體描述，并介紹數(shù)學模型。

3.1 模型參數(shù)

首先給出數(shù)學模型中所需的各項索引。對于一個給定的區(qū)域，根據(jù)地理信息劃分I個客戶聚集區(qū)，每個聚集區(qū)用i標識，其中i=1, 2, …,I。該區(qū)域內有J個備選的站點位置，備選站用j標識，其中j=1, 2, …,J。在任何一個客戶聚集區(qū)，都可能存在最多K類客戶，下標用k標識，其中k=1, 2,…,K。如前文所述，客戶類別根據(jù)充電行為偏好進行聚類得到；同時所有k組成的集合又可按照純電車和混動車分為兩個子集，分別是Uelectricty和Uhybrid。提供Q種充電樁供客戶選擇，下標用q標識，其中q=1, 2, …,Q；根據(jù)實際情況，僅考慮兩種充電樁，q=1表示慢充，q=2表示快充。由于需求具有時變性，故需要引入時段的概念，以下標t標識，其中t=1, 2, …,T。

而后，定義如下參數(shù)，如表4所示。

表4 模型參數(shù)表Table 4 Model parameters

3.2 決策變量、目標和約束

3.2.1 決策變量

Njq為非負整數(shù)，表示第j個備選站中第q種充電樁的數(shù)量。同時定義輔助變量Pijkt和Yijk。其中Pijkt為取值為[0,1]的連續(xù)變量，表示第t時段第k類客戶從聚集區(qū)i到備選位置j充電需求，占第t時段在聚集區(qū)i的第k類客戶充電總需求的比例。Yijk具體定義如下：

3.2.2 目標函數(shù)

(1) 充電站建設成本

成本包括在備選位置j建站的固定成本，和充電站中設置不同種類充電樁的可變成本。

(2) 客戶充電成本

本模型中的客戶充電成本只和距離相關，該目標具體表示如下：

綜上，最終目標表達式為：

3.2.3 約束條件

(1)Njq與Xj的關系

如果某個位置建設任意一種充電樁，則該地一定建設充電站。反之，如兩種充電樁均未建設，則說明此地不建設充電站。

(2)Yijk與Xj的關系

如果對于所有聚集區(qū)的各類客戶，都沒有被分配到某個備選站，則該地不建設充電站；否則，需要建設充電站。

(3)Yijk與Njq的關系

從數(shù)據(jù)中可以發(fā)現(xiàn)，混動車只能使用慢充，因此如果一個站點沒有慢充樁，則不能為混動車提供服務。

(4)Pijkt與Yijk的關系

指定某個聚集區(qū)和客戶類型，如果在每個時段都沒有需求被分配到備選站j，則說明該聚集區(qū)的該類客戶不會由備選站j服務，反之亦然。

(5)Pijkt歸一化

根據(jù)Pijkt定義，需要保證任意時段、某類聚集區(qū)的某類客戶，被分配到各個備選站的需求比例和為1，即需求總會被分配到充電站。

(6) 服務水平要求

由于在建設規(guī)劃不是一步到位的，因此在初期不可能滿足所有充電需求，因此需對充電能力和充電需求的相對大小關系進行限制，即服務水平要求。

(7) 預算限制

考慮到充電網(wǎng)絡布局規(guī)劃時的經費要求，需設置預算限制，具體如下：

(8) 充電樁容量限制

考慮到城區(qū)規(guī)劃要求、地區(qū)面積、電力配套設施和功率上限等方面的要求，應對不同區(qū)域不同種類的充電樁的數(shù)量加以限制，具體表示如下：

Njq≤capjqfor ?j,q

(9) 客戶聚集區(qū)與充電站的最大距離限制

考慮到車輛續(xù)航、服務半徑要求，和城市基礎設施建設對生活質量的影響，有必要限制每個聚集區(qū)的客戶到充電站的最遠距離，具體表示如下：

Yijkdisij≤Maxdiskfor ?i,j,k

3.3 模型總結

綜上所述，建立混合整數(shù)線性規(guī)劃(MILP)模型對充電樁選址定容問題進行建模，數(shù)學模型如下：

s.t.

Njq≤capjqfor ?j,q

Yijkdisij≤Maxdiskfor ?i,j,k

4 數(shù)值實驗

選取浦東新區(qū)某一地塊進行數(shù)值實驗，如圖5所示。其中，藍色或紅色邊框的為客戶聚集區(qū)，共11個；紅綠色同心圓為現(xiàn)有充電站，共11個；藍色圖標為其他備選站址，共38個。注意，在本實驗中，備選站址包括現(xiàn)有充電站位置，共計49個，排序為未建站在前、已建站在后。

將隨機生成的所有數(shù)據(jù)輸入Gurobi求解器得到全局最優(yōu)解，實際建設成本為1060.33萬元，充電成本為24844米。表5給出了建站位置對應的充電樁數(shù)量。

表6給出每個地區(qū)每類客戶和充電站的對應關系，即Yijk；表7更細致的給出了對應的Pijkt。

表7 每個地區(qū)每類客戶和充電站的時間分配關系Table 7 Time distribution relationship between customers and charging stations

圖6中，其中標紅的是原來已有站點，標藍的是未建站點(備選站址)。帶橙色和黑色同心圓的表示本次規(guī)劃中建站的地方，橙色圈的半徑表示慢充樁的個數(shù)，黑色圈的半徑表示快充樁的個數(shù)。

圖6 布局規(guī)劃結果Fig.6 Layout planning result

每個聚集區(qū)內的各類客戶和充電站對應關系如圖7所示。

1

從中可以發(fā)現(xiàn)，快充樁建設數(shù)量很少，這是因為快充樁選擇比例較低，且需求總量較低導致的。為印證這一點，人為增加快充樁選擇比例，保證大多數(shù)人愿意選擇快充樁這個事實，同時將需求總量擴大(考慮五年后的需求)，即可得到完全不一樣的選址定容結果，如表8-10和圖8-9所示。

表8 建站容量Table 8 Capacity of charging stations

表9 每個地區(qū)每類客戶和充電站對應關系Table 9 Mapping relationship with customers and charging stations

表10 每個地區(qū)每類客戶和充電站的時間分配關系Table 10 Time distribution relationship between customers and charging stations

圖8 布局規(guī)劃結果Fig.8 Layout planning result

1

5 總結與討論

本研究針對新能源汽車充電站選址定容問題展開研究，以最小化充電站建設成本和最小化客戶充電成本為目標，考慮客戶細分、能力折扣、樁選擇偏好、預算限制、容量限制、服務水平限制等因素。由數(shù)值實驗可以發(fā)現(xiàn)，在保證服務水平的前提下最大限度的減少了開銷，這也體現(xiàn)了在未來實踐中的重要價值。此外，本模型具有較好的擴展性，未來可以在多階段布局規(guī)劃、考慮隨機性的選址定容問題等方面進行更深入的研究，求解更加復雜和多樣的選址定容問題。