趙書強，李志偉，黨 磊

（華北電力大學(xué) 電氣與電子工程學(xué)院，河北 保定 071003）

0 引言

目前電動汽車產(chǎn)業(yè)發(fā)展迅猛，按照國家新能源汽車的相關(guān)政策和國際上技術(shù)發(fā)展趨勢，10年內(nèi)混合動力汽車和純電動汽車將作為一種比較成熟的交通工具得到規(guī)?；瘧?yīng)用。電動汽車的發(fā)展需要配套充電站發(fā)展作為支撐，布局合理的電動汽車充電站規(guī)劃對電動汽車的普及發(fā)展將起到不可替代的作用［1］。電動汽車充電站的選址和定容需要充分考慮本區(qū)域交通道路狀況及電動汽車發(fā)展規(guī)模。

目前對于城市內(nèi)電動汽車充電站的布局規(guī)劃研究正在起步階段，研究還不完善，還沒有建立起完整的體系。文獻［2］分析了影響電動汽車充電站布局的因素，介紹了充電站規(guī)劃的原則。文獻［3］綜合考慮多個因素，提出兩階段優(yōu)化算法，第一階段先計算出充電需求，第二階段通過優(yōu)化算法確定充電站站址。文獻［4］以居民負荷情況來模擬電動汽車的數(shù)量，利用層次分析法來確定充電站候選站址的權(quán)系數(shù)，利用費用最少來完成充電站的選址定容。文獻［5］運用動態(tài)交通網(wǎng)絡(luò)思想將充電者充電成本和充電站投資成本最小作為優(yōu)化目標(biāo)，建立了基于硬時間窗約束下的充電站布局模型，提出了求解該模型的兩階段啟發(fā)式算法。文獻［6］將電動汽車充電設(shè)施劃分為示范、公益和商業(yè)運行3個階段，并根據(jù)各階段的特點提出了充電設(shè)施規(guī)劃的原則和模型。文獻［7］基于區(qū)域交通流量守恒原理做出了交通總量和分布的預(yù)測，建立了年最小費用模型并運用遺傳算法對實例進行求解。文獻［8］以俘獲的交通流量最大、配電系統(tǒng)網(wǎng)絡(luò)損耗最小以及節(jié)點電壓偏移最小為目標(biāo)，建立了充電站最優(yōu)規(guī)劃的多目標(biāo)決策模型，通過采用改進的二進制粒子群優(yōu)化算法對模型進行了求解。文獻［9］根據(jù)地理因素和服務(wù)半徑來確定充電站的候選站址，以規(guī)劃期內(nèi)的充電站總成本最小為目標(biāo)建立了充電站最優(yōu)規(guī)劃模型，并采用改進的對偶內(nèi)點法進行了求解。文獻［10］運用博弈論對給定的充電站待選方案進行綜合評價，進而篩選出最優(yōu)方案。文獻［11］綜合分析了影響電動汽車充電站規(guī)劃的若干因素，建立了電動汽車充電站規(guī)劃的最大收益模型。文獻［12］以用戶在充電路程中的損耗成本和充電線路投資之和最小為目標(biāo)，進行充電站站址和接入位置的選擇，以全社會成本最小為目標(biāo)進行充電站方案的優(yōu)化。

到目前為止，國內(nèi)外在充電站規(guī)劃方面的研究還處于初級階段，尚未形成完整、系統(tǒng)的模型和方法?，F(xiàn)有模型大多從經(jīng)濟性考慮出發(fā)，優(yōu)化結(jié)果使總費用最?。?3］。充電站屬于服務(wù)性公共場所，建設(shè)充電站需充分考慮城市交通網(wǎng)絡(luò)信息，最大限度地方便電動汽車車主的充電［14］。為此，本文提出基于城市道路信息來確定充電站候選站址，根據(jù)充電站需要服務(wù)的電動汽車的數(shù)量，采用排隊論來確定充電站充電機數(shù)量，進而確定充電站容量的兩步搜索最優(yōu)模型。

1 電動汽車充電站布局最優(yōu)化的數(shù)學(xué)模型

電動汽車充電站的選址將直接影響車主在路上的行駛成本（去往充電站路上的耗時和耗能）。假設(shè)電動汽車在行駛過程中需要充電時，就到最近的充電站進行充電，則充電站的服務(wù)區(qū)域可以用Voronoi圖來進行劃分。當(dāng)充電站數(shù)量較多時，相應(yīng)的充電站服務(wù)區(qū)域Voronoi圖面積就小，車主的行駛成本就小。相反，當(dāng)充電站數(shù)量較少時，相應(yīng)的Voronoi圖面積就大，車主的行駛成本就大。因此，車主的行駛成本與電動汽車充電站的數(shù)量明顯相關(guān)，大量的充電站會減小行駛成本，但同時會增加建設(shè)充電站的成本。因此，需要綜合考慮車主行駛成本與充電站建設(shè)成本，保證車主在城市的任意位置都在不超過某一最大距離l內(nèi)可以找到充電站進行充電，顯然這一距離與電動汽車的續(xù)駛里程L有關(guān)，同時與充電便捷系數(shù)α有關(guān)。它們之間滿足如下關(guān)系：

1.1 電動汽車的續(xù)駛里程

電動汽車的續(xù)駛里程是指電動汽車從動力電池以充滿狀態(tài)開始，到標(biāo)準(zhǔn)規(guī)定的實驗結(jié)束時所走過的里程［15］，它是電動汽車充電站建設(shè)的重要參考指標(biāo)［16］。相鄰兩充電站間的距離必須小于電動汽車的續(xù)駛里程。

1.2 電動汽車充電便捷系數(shù)

電動汽車充電便捷系數(shù)α直接影響城市電動汽車充電站建設(shè)的建設(shè)成本、車主的行駛成本以及車主在充電站的排隊等待成本：α較大時，車主行駛成本和車主在充電站排隊等待成本會增大；α較小時，電動汽車充電站建設(shè)數(shù)量將增多，導(dǎo)致城市充電站建設(shè)成本將升高。α的取值以充電站建設(shè)成本、車主行駛成本以及車主在充電站排隊等待成本之和最小為原則進行確定?？偝杀颈硎救缦拢?/p>

其中，Cc（α）為電動汽車充電站的建設(shè)成本；Cd（α）為電動汽車去充電站途中產(chǎn)生的耗電成本和耗時成本；Cw（α）為電動汽車在充電站排隊充電過程中產(chǎn)生的排隊等待成本。

充電站的建設(shè)成本包括固定投資和運行成本。固定投資主要是土地占用成本及充電機、變壓器和其他輔助設(shè)備投資成本。運行成本主要包括員工工資、設(shè)備維護與檢修、電費等。充電站總成本折算到每天表示如下：

其中，f1（Qi）為第i個充電站與其配置充電機數(shù)Qi有關(guān)的固定投資；f2（Qi）為第i個充電站與其配置充電機數(shù)Qi有關(guān)的年運行成本；m為充電站折舊年限，取 20 a；r0為貼現(xiàn)率，取 0.08；h 為要建設(shè)的充電站的總數(shù)。式（4）表示充電站的充電機個數(shù)是關(guān)于充電便捷系數(shù)α的函數(shù)。

充電站固定投資采用站內(nèi)充電機數(shù)量二階多式模型表示［17］。其中，a1為營業(yè)建筑等固定不變投資，a2為充電機購置成本等與充電機數(shù)量成比例的相關(guān)成本，a3為變壓器、電纜等與充電機數(shù)量平方成比例的相關(guān)成本。年運行費用取固定投資成本的50%。即：

電動汽車的充電行駛成本與其到充電站的距離以及在此期間耗費的時間有關(guān)。

其中為電動汽車到第i個充電站的平均距離，與充電便捷系數(shù)有關(guān)；k1為電動汽車每100 km耗電量；c為電動汽車在充電站充1 kW·h電所繳納的電費；v為電動汽車去往充電站途中的平均速度；β為電動汽車由于耗時所損失的收入；Vi（α）為每天需要到第i個充電站進行充電的電動汽車數(shù)量。

采用常規(guī)充電方式的電動汽車，其車主通常不會在充電站等待。而采用快速充電方式的車主都想盡快完成充電，以繼續(xù)自己的行駛。因此，對于采用快速充電的車主而言，在充電站排隊充電就會產(chǎn)生排隊等待成本。這部分電動汽車在排隊過程中的排隊成本與平均等待時間有關(guān)：

其中，wqi為第i個充電站快速充電的電動汽車等待時長的平均值；γi（α）為每小時到第i個充電站進行快速充電的電動汽車數(shù)量。

假設(shè)電動汽車到達充電站的時間間隔相互獨立，且服從參數(shù)為γ的負指數(shù)分布。假設(shè)電動汽車充電過程的充電時間長短獨立且同分布，服從參數(shù)為μ的負指數(shù)分布。由分析可知，電動汽車到達充電站進行充電的過程是典型的M／M／S等待制排隊模型。由文獻［18］可知系統(tǒng)平穩(wěn)分布時，車主平均等待時間與充電站內(nèi)快速充電機個數(shù)S的關(guān)系如下：

其中，γ為電動汽車的到達率；μ為充電站的平均服務(wù)率；S為充電站內(nèi)快速充電機的個數(shù)；ρ為服務(wù)強度；ρS為服務(wù)臺數(shù)量為S時排隊模型的服務(wù)強度。

采用典型城市數(shù)據(jù)可得充電站建設(shè)成本、充電行駛成本和充電排隊等待成本之和，與充電便捷系數(shù)α的函數(shù)關(guān)系如圖1所示。由圖可見，α取值在0.05～0.12之間總成本處在比較低的水平。因此，充電便捷系數(shù)α的建議取值范圍為［0.05，0.12］。

圖1 總成本與充電便捷系數(shù)函數(shù)關(guān)系圖Fig.1 Curve of total cost vs.convenience coefficient

充電便捷系數(shù)α的取值與城市交通以及經(jīng)濟狀況直接相關(guān)。對于某一具體城市，α可以由其交通狀況、經(jīng)濟狀況，以式（2）所示的總成本最小為原則進行確定。但是每個城市在進行充電站規(guī)劃時，都進行一遍類似計算既不現(xiàn)實也沒必要。一方面，有些城市缺少必要的統(tǒng)計數(shù)據(jù)，無法完成相關(guān)計算；另一方面，城市之間交通以及經(jīng)濟的發(fā)展具有相似性，具有相似性的不同城市α的取值可以相同。這樣便于充電站的標(biāo)準(zhǔn)化建造，縮短充電站設(shè)計時間，節(jié)省充電站設(shè)計費用。

下面采用基于主成分的聚類分析將全國31個省市自治區(qū)進行分類，以便為不同省市自治區(qū)α的取值提供參考。同一類地區(qū)建立充電站，α取值應(yīng)相同或相近。

層次聚類又稱為系統(tǒng)聚類，它把最終的層次看作是一個從數(shù)據(jù)對象到數(shù)據(jù)類的層次映射模型［19］。其方法的思想是將數(shù)據(jù)對象構(gòu)造成一棵聚類樹，離差平方和法在凝聚的類層次法中應(yīng)用比較廣泛。離差平方和法的具體思想是將數(shù)據(jù)各自成一類，然后每次減少一類，這樣離差的平方和就要增大，選擇方差增加最小的2個類合并，直到滿足條件［20］。

設(shè)將g個數(shù)據(jù)對象分成C1、C2、…、Ck共k個類，用xiq表示Cq中的第i個數(shù)據(jù)對象，nq表示Cq中數(shù)據(jù)的個數(shù)表示Cq的重心，則Cq的離差平方和為：

若Ci、Cj合并成新類Ch，類內(nèi)離差平方和變?yōu)椋?/p>

實際問題中遇到的聚類問題多為多因素的問題，且在多數(shù)情況下各因素之間常常存在一定的相關(guān)性。因素較多且各因素之間存在相關(guān)性，增加了聚類問題的復(fù)雜性，為此需要對原始因素進行主成分分析，從多個因素中綜合為少數(shù)幾個有代表性的因素，這幾個因素既能代表原始絕大多數(shù)信息，又互不相關(guān)。

因為α的取值既與區(qū)域交通水平有關(guān)又與區(qū)域經(jīng)濟水平有關(guān)，在對全國31個省市自治區(qū)α取值進行區(qū)域劃分時，選取人均GDP、人口數(shù)、民用汽車擁有量、旅客周轉(zhuǎn)量、貨運周轉(zhuǎn)量、公路面積密度6個反映區(qū)域社會經(jīng)濟與交通發(fā)展水平的評價指標(biāo)［21］。指標(biāo)的原始統(tǒng)計數(shù)據(jù)來自《中國區(qū)域經(jīng)濟統(tǒng)計年鑒》。

通常原始數(shù)據(jù)各因素之間都會有較大的相關(guān)性，在此用相關(guān)系數(shù)來表征各變量之間的相關(guān)性。兩變量x、y之間的相關(guān)系數(shù)計算公式如下：

其中為變量x的平均值為變量y的平均值。

計算各因素之間的相關(guān)系數(shù)矩陣，結(jié)果如表1所示，由結(jié)果可知各因素之間存在著顯著相關(guān)關(guān)系。變量之間直接的相關(guān)性比較強，證明它們存在信息上的重疊。為此，需要對原始指標(biāo)提取主成分。對于原始變量 X=（X1，X2，…，Xp）T存在線性變換，使得新變量Z的任意一行計算如下：

其中，ai=（a1i，a2i，…，api）T表示由原指標(biāo)過渡到新的綜合指標(biāo)的系數(shù)矩陣的列向量。

表1 各因素相關(guān)系數(shù)矩陣Table 1 Correlation between different factors

可以容易知道對于Zi的方差計算如下：

δvar（Zi）越大，表示 Zi包含的信息越多［22］。 主成分分析需要保留盡可能多的信息，即新生成的較少的綜合變量的方差之和盡可能接近原始變量的方差之和。Z1是X的所有線性函數(shù)中方差最大的一個。之后的主成分提取是在與之前已經(jīng)提取出的主成分線性無關(guān)的前提下，以方差最大為原則進行的。由式（14）可知全體主成分的方差為：

由式（15）可得，新提取的各主成分的方差分別為X的協(xié)方差矩陣D（X）的特征值。計算X的協(xié)方差矩陣D（X）的特征值，得每次提取的主成分所能解釋的方差，結(jié)果見表2。

表2 各因素方差解釋表Table 2 Explaination of variance for each factor

由方差解釋表可以看出，前2個公共因子可以解釋總方差的82.9%，即總體多于80%的信息可以由這2個公共因子來解釋。因這2個公共因子基本保留了原來指標(biāo)信息，故可選取這2個因子作為主成分對原始數(shù)據(jù)進行分析。這樣，原來6個指標(biāo)轉(zhuǎn)化為2個新指標(biāo)。對應(yīng)提取的2個主成分的方差，即D（X）的特征值λi，可以計算該特征值對應(yīng)的特征向量Pi，即是各因素的初始載荷矩陣。

計算各因素初始載荷矩陣結(jié)果如表3所示。從表3中可看出，人口數(shù)、民用汽車擁有量、旅客周轉(zhuǎn)量、貨運周轉(zhuǎn)量、公路面積密度在第一主成分上有較高載荷，說明第一主成分基本反映這些指標(biāo)的信息。人均GDP在第二主成分上有較高載荷，說明第二主成分主要反映的是該指標(biāo)的信息。故用這2個新變量來代替原來的6個變量。第一主成分反映的均為交通情況的指標(biāo)，命名為交通指標(biāo)ZF1；第二主成分反映的為經(jīng)濟情況的指標(biāo)，命名為經(jīng)濟指標(biāo)ZF2。

表3 各因素初始載荷矩陣Table 3 Initial loads for different factors

用各因素的初始載荷Pi除以對應(yīng)的特征值λi開平方，便可得到2個主成分中原來每個指標(biāo)所對應(yīng)的系數(shù)［22］。經(jīng)過計算，2個主成分表達式如下：

其中，ZX1、ZX2、ZX3、ZX4、ZX5、ZX6分別為標(biāo)準(zhǔn)化以后的旅客周轉(zhuǎn)量、人口數(shù)、民用汽車擁有量、貨運周轉(zhuǎn)量、公路面積密度、人均 GDP；ZF1、ZF2分別為新的綜合交通情況、經(jīng)濟情況指標(biāo)。

運用ZF1、ZF2作為新的綜合指標(biāo)進行層次聚類分析。首先將每個城市單獨看作一類，利用式（10）計算其離差平方和。嘗試將類Ci和類Cj合并成新類Ch，利用式（11）計算新類的離差平方和Gh。定義類Ci和類Cj之間的平方距離為：

以各類之間相對距離的大小為橫軸，以全國各省市為縱軸，在某距離下若有2類可以合并成一個新類，則將該2類在此距離下用一豎線連接，這樣就可以得出聚類過程樹狀圖。省市聚類結(jié)果樹狀圖如圖2所示。

圖2 層次聚類的系統(tǒng)樹狀圖Fig.2 Dendrogram for hierarchical clustering

根據(jù)樹狀圖可以方便地了解指定聚類個數(shù)的分類結(jié)果。通過樹狀圖看分類結(jié)果，只需在樹狀圖上畫一豎直虛線，將與虛線相交的線斷開，斷線后仍然連接的城市則分為一類，虛線的位置則表示分類的距離尺度。從樹狀圖中可以看出聚類結(jié)果分成3類比較合適，所以用一條豎線將圖中只有3條橫線的地方斷開。斷開后，仍然連接的則分為一類，聚類結(jié)果如表4所示。

表4 聚類結(jié)果Table 4 Results of clustering

從表4所示的聚類結(jié)果中可以看出，可以劃分為如下3類。

第1類：公路交通經(jīng)濟發(fā)達地區(qū)，包括北京、天津、上海3個直轄市。這3個地區(qū)的交通便利，經(jīng)濟發(fā)達，且舉辦政治影響較大的活動，對電動汽車充電站的需求大、對充電的便利性要求較高，α取值應(yīng)在參考建議范圍內(nèi)取較小的值。

第2類：公路交通經(jīng)濟中等發(fā)達地區(qū)，包括河北、山東、江蘇、浙江、廣東、河南、安徽和四川8個省。這些地區(qū)交通較為便利，經(jīng)濟發(fā)展也較快，具有較好的發(fā)展?jié)摿?，但?jīng)濟力量相比于第一類別的地區(qū)略顯薄弱，α取值應(yīng)在參考建議范圍內(nèi)取值適中。

第3類：公路交通經(jīng)濟初等發(fā)達地區(qū)，包括20個省市自治區(qū)。這些地區(qū)有些地方經(jīng)濟薄弱，有些地區(qū)公路交通不發(fā)達。電動汽車充電站設(shè)計規(guī)劃時，考慮經(jīng)濟性多一些，α取值應(yīng)在參考建議范圍內(nèi)取較大的值。也可進一步采用聚類分析的方法，將其進一步細化。

1.3 電動汽車充電站選址的數(shù)學(xué)模型

根據(jù)Voronoi圖原理，將城市的電動汽車負荷全部集中到城市道路的路口。如圖3所示，將標(biāo)號為6的區(qū)域的負荷做集中處理，看成標(biāo)號為6的點的負荷。這樣電動汽車充電的行駛距離就變?yōu)樗趨^(qū)域的交通路口到候選充電站址的距離。

圖3 負荷集中處理Fig.3 Load concentration

為保障電動汽車的行駛能力、滿足電動汽車車主的出行需要，從城市任意位置出發(fā)距最近的充電站的距離應(yīng)小于等于l，這就是集覆蓋問題。集覆蓋問題最早由 Toregas（1971 年）［23］提出，滿足覆蓋所有需求點的前提下，使得總的建設(shè)服務(wù)站個數(shù)最少。集覆蓋問題最早被提出是用于解決消防中心和救護中心的選址問題。

充電站選址直接關(guān)系到充電站建設(shè)成本，所以充電站選址需要在滿足約束的前提下使充電站建設(shè)數(shù)量盡可能少。約束條件為：從每個交通路口出發(fā)到相鄰的最近的充電站的距離d≤l，為了避免資源的浪費，相鄰兩充電站之間距離不能太近，為此相鄰兩充電站距離需滿足：

其中，A為相鄰兩充電站之間的距離；L為電動汽車的續(xù)駛里程。

則充電站建設(shè)選址的模型為：

其中，length（·）表示求集合長度函數(shù)；N為充電站建設(shè)節(jié)點集；M為非充電站的負荷節(jié)點集；L為電動汽車?yán)m(xù)駛里程；dij為任意充電站建設(shè)節(jié)點與非充電站建設(shè)節(jié)點間的距離；dit為任意兩充電站建設(shè)節(jié)點間距離。

前文描述的距離顯然是沿道路實際行駛的距離，而不是地圖上兩點之間的直線距離。為此，需要研究電動汽車去充電過程中在道路行駛的路程。從某一充電負荷節(jié)點出發(fā)，到達某一充電站有多條路徑可供選擇。因此需要計算出對任一充電負荷節(jié)點與備選充電站址之間的最短路徑。Floyd算法可以得到網(wǎng)絡(luò)中不經(jīng)過中間節(jié)點，或者最多允許經(jīng)過2w-1個中間節(jié)點時的最短路徑dij，其中w為網(wǎng)絡(luò)中總的節(jié)點個數(shù)。

選定充電站的位置后，根據(jù)Voronoi圖計算出每個充電站所服務(wù)的充電負荷節(jié)點覆蓋的面積。假設(shè)城市的人口均勻分布，根據(jù)該城市的人口密度和電動汽車的占有率，求得該充電站所服務(wù)的電動汽車的數(shù)量，進而計算出每個充電站所配置充電機的數(shù)量，最后按照所配充電機情況計算充電站配置容量。充電站一般配置常規(guī)充電機和快速充電機2類。常規(guī)充電機一般在5～10 h將電動汽車充滿電，由于充電時間較長，車主一般不會在充電站等待；快速充電一般在10～30 min充滿80%的電量，一般用于應(yīng)急充電，車主一般在充電站等待。由于應(yīng)用場景不同，充電機數(shù)量配置原理也不相同。常規(guī)充電機數(shù)量按照充電時間進行配置，快速充電機的數(shù)量由排隊論的理論來解決。

目前，電動汽車常規(guī)充電以恒流／恒壓兩階段充電方法為主，忽略充電過程中充電起始和結(jié)束階段，將充電過程簡化為恒功率充電。常規(guī)充電機數(shù)量按照下式進行配置：

其中，Ri為第i個充電站配置的常規(guī)充電機的個數(shù)；ncha為每輛車每天平均充電次數(shù)；ωi為每天到第i個充電站進行充電的電動汽車采用常規(guī)充電方式的比例；T為常規(guī)充電方式的平均充電時間；t0為充電站常規(guī)充電機的每日工作時間。

對于快速充電機的數(shù)量配置，從車主的角度考慮，希望充電機越多越好，這樣可以減少等待時間；從充電站的運營方角度看，無條件地增加充電機的數(shù)量會帶來建設(shè)、運行成本的大幅度增長。為此，根據(jù)排隊論的理論對充電站內(nèi)快速充電機的數(shù)量進行優(yōu)化。根據(jù)式（9）計算每個充電站快速充電排隊時長的期望值，用最少的充電機數(shù)量，滿足車主期望排隊等待時間不超過T0的要求。

充電站內(nèi)充電機輸入總?cè)萘繛椋?/p>

其中，S∑為充電站配置的總?cè)萘浚籏為充電機同時系數(shù)；pk、ηk、cos φk分別為第 k 臺充電機的功率、充電效率、功率因數(shù)。

2 算法描述

2.1 最短路徑算法描述

Floyd 算法如下［24］。

第一步，作初始距離矩陣D（0），其中如果從節(jié)點i到節(jié)點j之間有路可達，則為兩點之間的道路長度，否則為無窮，表示兩點之間不直接相通。即：

其中，dij為節(jié)點i與節(jié)點j之間的距離；wij為直接相連的節(jié)點i與節(jié)點j之間的直連距離。

第二步，對于每一對頂點i與j，看是否存在一個頂點r，使得頂點i到頂點r再到頂點j，比已知路徑更短。即構(gòu)造迭代矩陣D（k），其元素為：

第三步，若 D（k+1）=D（k），表明最小距離已經(jīng)找到，則迭代終止；否則，返回第二步。

2.2 充電站位置選取的算法描述

設(shè)為充電站建設(shè)與否的決策變量，取值只有0和1。=1 表示在節(jié)點 i建設(shè)充電站=0表示在節(jié)點i不建設(shè)充電站。

a.初始化=1（i=1，2，…，n；e=1）。

b.=1（k=1），即在節(jié)點 k 處建設(shè)充電站。 則在通過Floyd算法計算出的最短距離矩陣D中距離節(jié)點 k 在 l之內(nèi)（dik＜l（i=1，2，…，n；k=1））的節(jié)點 i將不再建設(shè)充電站，即=0（i=1，2，…，n；i≠k）。

c.若=1（i=1，2，…，n；e=1），則距節(jié)點 i在 l之內(nèi)（dij

d.e=e+1，重新執(zhí)行步驟c，直到e=n。

e.檢驗約束條件l≤A≤L／2是否得到滿足，即min（dij）≤L／2（?Xi=1、Xj=1），若不滿足，則=1（p≠i，e≠j，dip≤S ／2，dpj≤L／2）。

f.記錄X（e），改變初始e的值重新執(zhí)行步驟a—e。

g.選出最小的X（k）即為最優(yōu)備選方案。

下面證明上述算法一定可以得到全局最優(yōu)解。如果上述方法得到的最優(yōu)解0（i≠j≠u），即在節(jié)點 i與節(jié)點 j建設(shè)充電站，而在節(jié)點u不建設(shè)充電站。假設(shè)存在另外一個解X在節(jié)點u需要建設(shè)充電站，而在節(jié)點i與節(jié)點j不需要建設(shè)充電站，其他節(jié)點充電站建設(shè)情況與最優(yōu)解X（k）相同，即 X 滿足 Xu=1，Xi=0，Xj=0，Xm=由步驟b可知，在每次k的循環(huán)中因為 Xu=1，由上述迭代步驟可知，在Xu=1的所有解中X（u）是最優(yōu)解，所以 X 一定不比 X（u）更優(yōu)。 而 X（k）是 X（u）（u=1，2，…，n）中最優(yōu)的，所以 X 一定不比 X（k）更優(yōu)，因此假設(shè)不成立，從而得證X（k）是最優(yōu)解。

2.3 充電站設(shè)計容量計算

計算最優(yōu)備選方案中每個充電站所服務(wù)的小的Voronoi圖的面積：

其中，SVoronoi.j為第j個Voronoi圖的面積。

對于同時可以被多個充電站所服務(wù)的小Voronoi圖，由可以為其提供服務(wù)的充電站將其面積均分。

則第i個充電站所服務(wù)的電動汽車的數(shù)量：

其中，N0為城市汽車總量；ξ為電動汽車保有量，以百分數(shù)表示；Si為第i個電動汽車充電站所服務(wù)的區(qū)域面積。

每輛車平均充電次數(shù)：

其中，k1為電動汽車每100 km綜合損耗；k2為電動汽車平均日行駛里程；q為每輛電動汽車充電量。

根據(jù)式（26）、（27）計算每天到第 i個充電站充電的電動汽車的充電車次，再根據(jù)式（21）計算常規(guī)充電機配置臺數(shù)，根據(jù)式（9）計算滿足等待時間約束的快速充電機的配置臺數(shù)，最后根據(jù)式（22）計算充電站的容量。

3 算例驗證

為驗證本文方法的有效性，采用某市主城區(qū)實際道路系統(tǒng)進行測試。該市主城區(qū)共6個區(qū)：A、B、C、D、E、F，面積 1435km2，城區(qū)人口 332 萬，全市共有 582個路口節(jié)點、982條道路。交通網(wǎng)絡(luò)如圖4所示。

圖4 主城區(qū)交通網(wǎng)絡(luò)示意圖Fig.4 Schematic diagram of main urban traffic network

根據(jù)Voronoi圖原理，將城市充電負荷集中到交通路口點上，結(jié)果如圖5所示。

目前電動汽車動力電池單次充電行駛里程在150～300 km之間，考慮到交通擁堵、電池老化等實際情況，續(xù)駛里程取L=100 km。根據(jù)1.2節(jié)的聚類結(jié)果，該城市處于第3類省市。為了減少充電站的建設(shè)費用，充電便捷系數(shù)取α=0.12。首先根據(jù)2.1節(jié)描述的Floyd算法計算任意兩路口之間的最短距離矩陣，然后按照2.2節(jié)所述的充電站選址算法選取充電站最優(yōu)位置，最優(yōu)充電站分布如圖6所示。

圖5 每個交通路口所服務(wù)的區(qū)域圖Fig.5 Service area for different traffic intersections

圖6 最優(yōu)方案充電站分布圖Fig.6 Optimal allocation of charging stations

從圖中可以明顯看出：所有充電負荷節(jié)點均被覆蓋，某些邊緣節(jié)點只處在一個充電站的服務(wù)半徑內(nèi)，有的充電負荷節(jié)點同時處在2個充電站的服務(wù)半徑之內(nèi)。對于處于2個充電站服務(wù)區(qū)域內(nèi)的充電節(jié)點，車主可以根據(jù)自己出行計劃方便選取充電站點。

確定了充電站的位置后根據(jù)Voronoi圖原理，在假設(shè)電動汽車均勻分布的前提下，計算每個充電站所服務(wù)的電動汽車數(shù)量。根據(jù)服務(wù)的電動汽車數(shù)量和需要采用快速充電的比例，計算每個充電站采用常規(guī)充電和快速充電的電動汽車數(shù)量。常規(guī)充電機的數(shù)目根據(jù)日工作時間需要滿足常規(guī)充電任務(wù)來配置，快速充電機的數(shù)目根據(jù)排隊論理論按滿足排隊時間約束的最小數(shù)量來配置。在得到充電機的數(shù)量后根據(jù)式（22）計算每個充電站的容量。

根據(jù)該市規(guī)劃局、市交通規(guī)劃研究院發(fā)布的《2013年市區(qū)交通發(fā)展年度報告》主城區(qū)私家小車擁有量達到56.3萬輛，按照規(guī)劃年電動汽車保有量達到8%［25］計算，電動汽車將達到5.55萬輛。取電動汽車充電站功率因數(shù)0.9、充電機充電效率0.9、充電機同時系數(shù)1；單臺汽車電池容量q=20 kW·h，綜合電耗k1=0.12 kW·h／km，平均日行駛里程 k2=200 km。 假設(shè)到達充電站的車輛20%采用常規(guī)充電方式，80%采用快速充電方式。快速充電充電機的充電功率100 kW，常規(guī)充電機的充電功率5 kW，采用快速充電方式的車主在充電站排隊時間不超過20 min。每個充電站所在位置、服務(wù)面積和需配置容量如表5所示。

表5 最優(yōu)方案各充電站配置容量Table 5 Optimal size for different charging stations

目前，城市10 kV主干線路選擇240 mm2絕緣導(dǎo)線或者300mm2電纜，負荷電流在400A左右。因此，目前配電網(wǎng)供電能力可以滿足所提充電站設(shè)計方案容量需求，對于容量較大的充電站可以考慮采用專線供電。

4 結(jié)語

針對電動汽車充電站規(guī)劃問題，本文提出一種基于地理信息的電動汽車充電站選址和定容的方法。首先根據(jù)電動汽車的續(xù)航能力和充電便捷系數(shù)確定充電站的服務(wù)范圍，結(jié)合規(guī)劃年服務(wù)的電動汽車的保有量，通過兩步搜索算法確定充電站的最優(yōu)分布和配置容量。算例結(jié)果表明，本文提出的方法可以得到滿足要求的較理想充電站規(guī)劃方案，對電動汽車充電站的選址和定容具有指導(dǎo)意義和應(yīng)用價值。

參考文獻：

［1］趙書強，李志偉.基于差分進化粒子群算法的城市電動汽車充電站最優(yōu)規(guī)劃［J］. 華北電力大學(xué)學(xué)報，2015，42（2）：1-7.ZHAO Shuqiang，LI Zhiwei.Optimal planning of charging station for electric vehicle based on PSODE algorithm［J］.Journal of North China Electric Power University，2015，42（2）：1-7.

［2］徐凡，俞國勤，顧臨峰，等.電動汽車充電站布局規(guī)劃淺析［J］.華東電力，2009，37（10）：1678-1682.XU Fan，YU Guoqin，GU Linfeng，et al.Tentative analysis of layout of electrical vehicle charging stations［J］.East China Electric Power，2009，37（10）：1678-1682.

［3］IP A，F(xiàn)ONG S，LIU E.Optimization for allocating BEV recharing station in urban by using hierarchical clustering［C］∥The 2nd International Conference on Data Mining and Intelligent Infor-mation Technology Applications（ICMIA2010）.Seoul，Korea：［s.n.］，2010：460-465.

［4］寇凌峰，劉自發(fā)，周歡.區(qū)域電動汽車充電站規(guī)劃模型與算法［J］.現(xiàn)代電力，2010，27（4）：44-48.KOU Lingfeng，LIU Zifa，ZHOU Huan.Modelingalgorithm of charging station planning for regional electric vehicle［J］.Modern Electric Power，2010，27（4）：44-48.

［5］任玉瓏，史樂峰，張謙，等.電動汽車充電站最優(yōu)分布和規(guī)模研究［J］. 電力系統(tǒng)自動化，2011，35（14）：53-57.REN Yulong，SHI Lefeng，ZHANG Qian，et al.Optimal distribution and scale of charging stations for electric vehicles［J］.Automation of Electric Power Systems，2011，35（14）：53-57.

［6］吳春陽，黎燦兵，杜力，等.電動汽車充電設(shè)施規(guī)劃方法［J］.電力系統(tǒng)自動化，2010，34（24）：36-39.WU Chunyang，LI Canbing，DU Li，et al.A method for electric charging infrastructure planning［J］.Automation of Electric Power Systems，2010，34（24）：36-39.

［7］李菱，李燕青，姚玉海，等.基于遺傳算法的電動汽車充電站的布局規(guī)劃［J］. 華東電力，2011，39（6）：1004-1006.LI Ling，LI Yanqing，YAO Yuhai，et al.Layout planning of electric vehicle charging stations based on genetic algorithm ［J］.East China Electric Power，2011，39（6）：1004-1006.

［8］王輝，王貴斌，趙俊華，等.考慮交通網(wǎng)絡(luò)流量的電動汽車充電站規(guī)劃［J］. 電力系統(tǒng)自動化，2013，37（5）：1-8.WANG Hui，WANG Guibin，ZHAO Junhua，et al.Optimal planning for electric vehicle charging stationsconsideringtraffic network flows［J］.Automation of Electric Power Systems，2013，37（5）：1-8.

［9］劉志鵬，文福拴，薛禹勝，等.電動汽車充電站的最優(yōu)選址和定容［J］. 電力系統(tǒng)自動化，2012，36（3）：54-59.LIU Zhipeng，WEN Fushuan，XUE Yusheng，et al.Optimal siting and sizing of electric vehicle charging stations［J］.Automation of Electric Power Systems，2012，36（3）：54-59.

［10］葛少云，馮亮，劉洪，等.考慮車流信息與配電網(wǎng)絡(luò)容量約束的充電站規(guī)劃［J］. 電網(wǎng)技術(shù)，2013，37（3）：582-589.GE Shaoyun，F(xiàn)ENG Liang，LIU Hong，et al.Planning of charging stations considering traffic flow and capacity constraints of distribution network［J］.Power System Technology，2013，37（3）：582-589.

［11］唐現(xiàn)剛，劉俊勇，劉友波，等.基于計算幾何方法的電動汽車充電站規(guī)劃［J］. 電力系統(tǒng)自動化，2012，36（8）：24-30.TANG Xiangang，LIU Junyong，LIU Youbo，et al.Electric vehicle charging station planning based on computationalgeometry method［J］.Automation of Electric Power Systems，2012，36（8）：24-30.

［12］周洪超，李海峰.基于博弈論的電動汽車充電站選址優(yōu)化模型研究［J］. 科技和產(chǎn)業(yè)，2011，11（2）：51-54.ZHOU Hongchao，LI Haifeng.Optimization model of electric vehicle charging station siting based on game theory［J］.Science Technology and Industry，2011，11（2）：51-54.

［13］陳靜鵬，艾芊，肖斐.基于用戶出行需求的電動汽車充電站規(guī)劃［J］. 電力自動化設(shè)備，2016，36（6）：34-39.CHEN Jingpeng，AI Qian，XIAO Fei.EV charging station planning based on travel demand［J］.Electric Power Automation Equipment，2016，36（6）：34-39.

［14］黃小慶，楊夯，肖波，等.考慮客戶滿意度的電動汽車充電站運營狀態(tài)評估［J］. 電力自動化設(shè)備，2014，34（10）：96-101.HUANG Xiaoqing，YANG Hang，XIAO Bo，et al.Operating state evaluation considering customer satisfaction for electric vehicle charging station［J］.Electric Power Automation Equipment，2014，34（10）：96-101.

［15］陳清泉，孫逢春，祝嘉光.現(xiàn)代電動汽車技術(shù)［M］.北京：北京理工大學(xué)出版社，2004：18-24.

［16］葛少云，馮亮，劉洪，等.考慮電量分布及行駛里程的高速公路充電站規(guī)劃［J］. 電力自動化設(shè)備，2013，33（7）：111-116.GE Shaoyun，F(xiàn)ENG Liang，LIU Hong，et al.Planning of charging stations on highway considering power distribution and driving mileage［J］.Electric Power Automation Equipment，2013，33（7）：111-116.

［17］熊虎，向鐵元，祝勇剛，等.電動汽車公共充電站布局的最優(yōu)規(guī)劃［J］. 電力系統(tǒng)自動化，2012，36（23）：65-70.XIONG Hu，XIANG Tieyuan，ZHU Yonggang，etal.Electric vehicle public charging stations location optimal planning ［J］.Automation of Electric Power Systems，2012，36（23）：65-70.

［18］薛毅，耿美英.運籌學(xué)與實驗［M］.北京：電子工業(yè)出版社，2008：426-447.

［19］包研科.數(shù)據(jù)分析教程［M］.北京：清華大學(xué)出版社，2011：9.

［20］丁世飛，勒奉祥，趙相偉.現(xiàn)代數(shù)據(jù)分析與信息模式識別［M］.北京：科學(xué)出版社，2012：60-68.

［21］金相郁.中國區(qū)域劃分的層次聚類分析［J］.城市規(guī)劃會刊，2004（2）：23-28.

［22］馬逢時，吳成鷗，蔡霞.基于MATLAB的現(xiàn)代實用統(tǒng)計［M］.北京：中國人民大學(xué)出版社，2013：106-112.

［23］TOREGAS C，SWAIN R，REVELLE C，et al.The location of service facilities［J］.Operation Research，1971，19：1363-1373.

［24］張德全，吾果林.最短路問題的Floyd算法優(yōu)化［J］.許昌學(xué)院學(xué)報，2009，28（2）：10-13.ZHANG Dequan，WU Guolin.Optimization of Floyd algorithmic for shortest path problem［J］.Journal of Xuchang University，2009，28（2）：10-13.

［25］劉煥.電動汽車充電站建設(shè)項目群風(fēng)險研究［D］.重慶：重慶大學(xué)，2009.LIU Huan.Study on the risk of construction projects in the electric vehicle charging stations［D］.Chongqing：Chongqing University，2009.