楊佳俊，陳紅，段美琪，亓曙光

（1.國(guó)網(wǎng)山東省電力公司萊蕪供電公司，山東萊蕪271100；2.山東送變電工程公司，濟(jì)南250118）

電動(dòng)汽車(chē)充電站多階段規(guī)劃研究

楊佳俊1，陳紅2，段美琪1，亓曙光1

（1.國(guó)網(wǎng)山東省電力公司萊蕪供電公司，山東萊蕪271100；2.山東送變電工程公司，濟(jì)南250118）

充電站作為電動(dòng)汽車(chē)運(yùn)營(yíng)所必須的配套設(shè)施，其建設(shè)時(shí)間、位置與規(guī)模對(duì)電動(dòng)汽車(chē)的推廣有著重要的意義。但現(xiàn)有的研究將充電站的規(guī)劃選址作為靜態(tài)規(guī)劃問(wèn)題來(lái)處理，忽視了充電站建設(shè)的時(shí)間問(wèn)題，為此提出了充電站選址的多階段規(guī)劃模型，并應(yīng)用偽動(dòng)態(tài)規(guī)劃的思想求解該模型。結(jié)合專(zhuān)家意見(jiàn)，在準(zhǔn)確預(yù)測(cè)各階段充電需求的基礎(chǔ)上，應(yīng)用遺傳算法確定目標(biāo)年的規(guī)劃方案，最終通過(guò)動(dòng)態(tài)規(guī)劃逆序解法獲得各階段的規(guī)劃方案。

充電站；選址；多階段；遺傳算法；動(dòng)態(tài)規(guī)劃

0 引言

隨著全球能源危機(jī)和環(huán)境的持續(xù)惡化，電動(dòng)汽車(chē)這種低污染、零排放的交通工具越來(lái)越受到大家的青睞。電動(dòng)汽車(chē)充電站是電動(dòng)汽車(chē)的能源供給基礎(chǔ)設(shè)施，是電動(dòng)汽車(chē)規(guī)模化運(yùn)營(yíng)的必要條件，其選址布局，定容規(guī)劃對(duì)區(qū)域內(nèi)電動(dòng)汽車(chē)的應(yīng)用推廣有著重要影響。針對(duì)電動(dòng)汽車(chē)充電站的選址、定容規(guī)劃，國(guó)內(nèi)外學(xué)者作了大量的研究。文獻(xiàn)［1］綜合考慮建設(shè)成本和用戶(hù)充電成本，提出了一個(gè)多等級(jí)充電站的規(guī)劃模型并通過(guò)改進(jìn)的禁忌搜索算法，實(shí)現(xiàn)站址、站容的優(yōu)選。文獻(xiàn)［2］綜合考慮充電站作為普通用電設(shè)施和公共服務(wù)設(shè)施的特性，通過(guò)建立多目標(biāo)規(guī)劃模型，完成充電站的最優(yōu)選址。文獻(xiàn)［3］通過(guò)粒子群算法和加權(quán)伏羅諾伊圖實(shí)現(xiàn)了充電站選址定容和服務(wù)區(qū)域劃分的最優(yōu)。文獻(xiàn)［4］提出了能夠計(jì)及充電站服務(wù)半徑和地理因素的兩步篩選法，建立了規(guī)劃期內(nèi)充電站建設(shè)總成本和網(wǎng)損費(fèi)用之和最小的目標(biāo)函數(shù)，通過(guò)改進(jìn)的原對(duì)偶內(nèi)點(diǎn)法，實(shí)現(xiàn)了問(wèn)題的最優(yōu)求解。

但現(xiàn)有的文獻(xiàn)［1-5］均將充電站的規(guī)劃選址作為靜態(tài)規(guī)劃問(wèn)題來(lái)處理，忽視了充電站建設(shè)的時(shí)間問(wèn)題。充電站作為重要的基礎(chǔ)設(shè)施，其建設(shè)時(shí)間和規(guī)模應(yīng)遵循與城鎮(zhèn)的發(fā)展相協(xié)調(diào)，結(jié)合現(xiàn)有電動(dòng)汽車(chē)的充電需求，并適當(dāng)超前的原則［2］，充電站的選址布局，定容規(guī)劃具有多階段，多變量的特征。文獻(xiàn)［6］首先求解所建變電站的數(shù)量和總?cè)萘浚谟肏opfield神經(jīng)網(wǎng)絡(luò)算法求解所建變電站的位置和供電范圍問(wèn)題，取得較好效果；文獻(xiàn)［7］考慮了地理因素和服務(wù)半徑的兩步篩選法確定充電站的候選地址，并建立了以充電站的投資、運(yùn)行和維護(hù)成本最小的求解模型；文獻(xiàn)［8］從電動(dòng)汽車(chē)充電站運(yùn)營(yíng)者和電動(dòng)汽車(chē)用戶(hù)雙方的利益出發(fā)建立全社會(huì)成本最小化的優(yōu)化模型，所提方案對(duì)于城市區(qū)域充電站規(guī)劃有一定的意義。動(dòng)態(tài)規(guī)劃算法是解決多階段問(wèn)題的經(jīng)典算法，但隨著優(yōu)化問(wèn)題規(guī)模和維數(shù)的增大，動(dòng)態(tài)規(guī)劃算法容易出現(xiàn)“組合爆炸”和“維數(shù)災(zāi)難”，因此采用偽動(dòng)態(tài)規(guī)劃的思想，通過(guò)遺傳算法計(jì)算出規(guī)劃期末的最優(yōu)規(guī)劃方案，將優(yōu)化問(wèn)題轉(zhuǎn)化為固定始端和終端的多階段規(guī)劃問(wèn)題，進(jìn)而通過(guò)動(dòng)態(tài)規(guī)劃逆序算法求解各個(gè)規(guī)劃階段的充電站建設(shè)方案。

1 多階段充電站規(guī)劃的數(shù)學(xué)模型

1.1 模型假設(shè)

充電站的候選點(diǎn)經(jīng)過(guò)初步分析論證，應(yīng)計(jì)及需求點(diǎn)及需求量分布，符合充電站選址原則、環(huán)境條件和安全條件。

需求點(diǎn)代表一個(gè)小型的地理區(qū)域，不同地理區(qū)域內(nèi)可能有不同的電動(dòng)汽車(chē)密度，各需求點(diǎn)處的充電需求量為該點(diǎn)代表的小型地理區(qū)域內(nèi)有充電需求的電動(dòng)汽車(chē)總數(shù)量。

每個(gè)需求點(diǎn)處的所有電動(dòng)汽車(chē)用戶(hù)，其每次充電過(guò)程自始至終只能在同一個(gè)充電站進(jìn)行。

電動(dòng)汽車(chē)用戶(hù)的充電成本與距離成簡(jiǎn)單的線(xiàn)性關(guān)系，且距離為歐氏距離。

1.2 目標(biāo)函數(shù)

綜合考慮各階段充電站的投資成本、運(yùn)行維護(hù)成本以及用戶(hù)的充電損耗費(fèi)用，并假設(shè)不拆除已經(jīng)建成的充電站，以各階段的綜合成本之和最小為目標(biāo)建立模型為

式中：N為規(guī)劃階段數(shù)；CT（k）為各階段的投資成本；CS（k）為各階段的運(yùn)行維護(hù)成本；CY（k）為各階段用戶(hù)的充電成本。

其中，

式中：n為目標(biāo)年充電站個(gè)數(shù)；f（Si，k）為第i號(hào)充電站在階段k的投資費(fèi)用（計(jì)及土地費(fèi)用）；y（k）為階段k的起始年份數(shù)；r為貼現(xiàn)率；u（Si，k）為第i號(hào)充電站在階段k的年運(yùn)行維護(hù)費(fèi)用；Ji（k）為第i號(hào)充電站在階段k所供負(fù)荷點(diǎn)的集合；t為道路曲折系數(shù)；η為道路暢通系數(shù)；ω為每輛車(chē)的平均充電次數(shù)；z為折返系數(shù)；gij為表示第j號(hào)需求點(diǎn)是否到第i號(hào)充電站充電的參數(shù)；l為單位距離折損系數(shù)；dij為第i個(gè)充電站到第j個(gè)充電需求點(diǎn)的距離。

1.3 每個(gè)階段的約束條件

式（5）表示充電站需滿(mǎn)足的容量約束，式（6）表示充電站的充電半徑約束，式（7）表示各充電需求點(diǎn)只能到一個(gè)充電站充電，式（8）表示充電站的等級(jí)約束。

式中：Wj（k）為第j號(hào)充電需求點(diǎn)在階段k的充電需求預(yù)測(cè)值；Si（k）為第i號(hào)充電站在階段k的容量；e（Si（k））為第i號(hào)充電站在階段k的運(yùn)行率；cosφ為充電效率；Ri（k）為第i個(gè)充電站在階段k的充電服務(wù)半徑。

1.4 多階段約束

式（9）表示下一階段的容量需建立在上一階段的基礎(chǔ)之上，因?yàn)橐呀ǔ傻某潆娬静豢赡懿鸪?，故只能在原有的基礎(chǔ)上擴(kuò)建或者保持原樣。

本文方法如圖1所示。

圖1 充電站多階段規(guī)劃算法

2 遺傳算法求解規(guī)劃期末的規(guī)劃方案

規(guī)劃期末的規(guī)劃方案是在預(yù)測(cè)規(guī)劃期末充電需求的基礎(chǔ)上，從給定的備選站址中優(yōu)選出本階段的最優(yōu)規(guī)劃，屬于靜態(tài)組合優(yōu)化問(wèn)題。遺傳算法適合求解大規(guī)模的組合優(yōu)化問(wèn)題，故通過(guò)遺傳算法求解最終的規(guī)劃方案。

編碼策略直接影響個(gè)體被GA算子操作時(shí)變形特性以及個(gè)體解碼時(shí)從基因型空間到表現(xiàn)型空間的映射性質(zhì)，對(duì)于事先給定待選站址的充電站規(guī)劃方法，一般使用傳統(tǒng)的二進(jìn)制編碼，即由二進(jìn)制符號(hào)0和1表示當(dāng)前待選站是否被選中，但為了同時(shí)計(jì)算出站址和站容，選址變量采用十進(jìn)制編碼，Xi=0表示不在i處建設(shè)充電站，Xi=1表示在i處建設(shè)1級(jí)充電站，Xi=2表示在i處建設(shè)2級(jí)充電站，Xi=3表示在i處建設(shè)3級(jí)充電站，Xi=4表示在i處建設(shè)4級(jí)充電站。根據(jù)本文的編碼方法可知編碼長(zhǎng)度為I（備選站址的個(gè)數(shù)），非零染色體的個(gè)數(shù)為P（P≤M，M為規(guī)劃充電站的個(gè)數(shù)）。

編碼僅確定了充電站的站址和站容，并未涉及各充電負(fù)荷的分配問(wèn)題，因此設(shè)計(jì)“聚類(lèi)”操作，完成充電需求的分配。即針對(duì)不同的n，根據(jù)染色體的編碼，按照就近原則把充電負(fù)荷分配到各個(gè)充電站；當(dāng)距離某個(gè)充電負(fù)荷最近的充電站容量達(dá)到該充電站編碼表示的容量上限時(shí)，則將該充電負(fù)荷分配到次近的充電站，直到分配結(jié)束。

3 動(dòng)態(tài)規(guī)劃逆序算法求解各階段的規(guī)劃方案

通過(guò)第一階段的遺傳算法計(jì)算出規(guī)劃期末的最優(yōu)規(guī)劃方案，應(yīng)用文獻(xiàn)［9-10］提出的動(dòng)態(tài)規(guī)劃思想，從而使問(wèn)題優(yōu)化成圖2所示的一個(gè)固定始端和終端的多階段規(guī)劃問(wèn)題，通過(guò)動(dòng)態(tài)規(guī)劃逆序算法可以很輕松的計(jì)算出各個(gè)規(guī)劃階段的充電站建設(shè)方案。

圖2 狀態(tài)轉(zhuǎn)移圖

4 實(shí)例分析

以某市開(kāi)發(fā)區(qū)的充電站選址定容為例。該開(kāi)發(fā)區(qū)總面積30 km2，東西長(zhǎng)5 km，南北長(zhǎng)6 km。需求點(diǎn)代表一定范圍的地理區(qū)域，不同地理區(qū)域內(nèi)可能有不同的電動(dòng)汽車(chē)密度，各需求點(diǎn)處的充電需求量為該點(diǎn)代表的地理區(qū)域內(nèi)有充電需求的電動(dòng)汽車(chē)總數(shù)量，根據(jù)區(qū)域內(nèi)電動(dòng)汽車(chē)的分布密度，采用聚合方法將該開(kāi)發(fā)區(qū)等效為30個(gè)充電需求點(diǎn)，各個(gè)需求點(diǎn)的服務(wù)半徑需求均設(shè)定為10 km，如表1所示，等效過(guò)程在本文中不做詳細(xì)討論；經(jīng)過(guò)專(zhuān)家初步分析論證，計(jì)及了需求點(diǎn)及需求量分布，符合充電站選址原則、環(huán)境條件和安全條件得出10個(gè)充電站候選點(diǎn)，如表2所示。參照北京市出臺(tái)的標(biāo)準(zhǔn)文件《電動(dòng)汽車(chē)電能供給與保障技術(shù)規(guī)范：充電站》，在本算例中，規(guī)定4種等級(jí)的充電站，根據(jù)具體的工程預(yù)算假設(shè)各自的服務(wù)能力及相應(yīng)建設(shè)成本如表3所示；假設(shè)充電站經(jīng)濟(jì)使用年限為20年，各規(guī)劃階段的間隔年份為5年。規(guī)劃的目的是從10個(gè)候選站址中選擇若干站點(diǎn)分階段建設(shè)充電站，并規(guī)劃出各階段充電站的建設(shè)方案。

表1 部分需求點(diǎn)位置及對(duì)應(yīng)需求量

表2 候選點(diǎn)的位置

表3 充電站的等級(jí)及相應(yīng)建設(shè)成本

根據(jù)以上設(shè)計(jì)的算法，利用Matlab進(jìn)行編程，其中的參數(shù)設(shè)置為：種群規(guī)模為50；迭代次數(shù)為300；對(duì)該假設(shè)算例獨(dú)立運(yùn)行20次，得出規(guī)劃期末的規(guī)劃方案：選擇在備選站址2、5、7、8、9分別建立等級(jí)為3、4、1、1、3的充電站，通過(guò)動(dòng)態(tài)規(guī)劃逆序算法求得的各階段的規(guī)劃方案如表4所示，各階段規(guī)劃方案對(duì)應(yīng)的累計(jì)建設(shè)成本及服務(wù)能力如表5及表6所示。各階段建站位置及需求點(diǎn)的分配如圖3所示。

表4 各階段規(guī)劃方案

表5 各階段規(guī)劃累計(jì)建設(shè)成本

通過(guò)表4～表5可以看出，截至第一階段末建設(shè)有1個(gè)一級(jí)充電站和1個(gè)二級(jí)充電站，建設(shè)成本累計(jì)750萬(wàn)；截至第二階段末建設(shè)有2個(gè)一級(jí)充電站、1個(gè)二級(jí)充電站及1個(gè)四級(jí)充電站，建設(shè)成本累計(jì)1 750萬(wàn)；截至第三階段末建設(shè)有2個(gè)一級(jí)充電站、2個(gè)二級(jí)充電站及1個(gè)四級(jí)充電站，建設(shè)成本累計(jì)2 150萬(wàn)；截至第四階段末建設(shè)有2個(gè)一級(jí)充電站、2個(gè)三級(jí)充電站及1個(gè)四級(jí)充電站，建設(shè)成本累計(jì)2 150萬(wàn)。

表6 各階段規(guī)劃充電服務(wù)能力

通過(guò)表6可以看出，截至第一階段末充電服務(wù)能力累計(jì)180輛；截至第二階段末充電服務(wù)能力累計(jì)600輛；截至第三階段末充電服務(wù)能力累計(jì)）710輛；截至第四階段末充電服務(wù)能力累計(jì)990輛。

圖3 各階段充電負(fù)荷分配

在開(kāi)始階段，由于電動(dòng)汽車(chē)的充電需求較少，充電站的建設(shè)費(fèi)用在總費(fèi)用中占據(jù)較大的部分，故而充電站的建設(shè)較少，各充電負(fù)荷的分配不均勻，充電站并不完全處于負(fù)荷的重心處，隨著充電負(fù)荷的增加，用戶(hù)的充電成本在總成本的比重增大，此時(shí)各個(gè)充電站逐步趨向于其所分配負(fù)荷的重心處，各充電站的負(fù)荷分配更加均衡合理。

5 結(jié)語(yǔ)

建立充電站多階段規(guī)劃數(shù)學(xué)模型，并采用偽動(dòng)態(tài)規(guī)劃思想求出了在整個(gè)規(guī)劃期間最優(yōu)的充電站建設(shè)方案。實(shí)際算例結(jié)果證明所提出的充電站多階段規(guī)劃模型和優(yōu)化方法能夠在達(dá)到整個(gè)規(guī)劃期間經(jīng)濟(jì)成本較小的目標(biāo)基礎(chǔ)上滿(mǎn)足各階段充電站優(yōu)化規(guī)劃的技術(shù)要求，對(duì)相關(guān)實(shí)踐有一定參考價(jià)值。

［1］張國(guó)亮，李波，王運(yùn)發(fā)，等.多等級(jí)電動(dòng)汽車(chē)充電站的選址與算法［J］.山東大學(xué)學(xué)報(bào)：工學(xué)版，2011，41（6）：136-142.

［2］劉志鵬，文福拴，薛禹勝，等.電動(dòng)汽車(chē)充電站的最優(yōu)選址和定容［J］.電力系統(tǒng)自動(dòng)化，2012，36（3）：54-59.

［3］唐現(xiàn)剛，劉俊勇，劉友波，等.基于計(jì)算幾何方法的電動(dòng)汽車(chē)充電站規(guī)劃［J］.電力系統(tǒng)自動(dòng)化，2012，36（8）：24-30.

［4］王輝，王貴斌，趙俊華，等.考慮交通網(wǎng)絡(luò)流量的電動(dòng)汽車(chē)充電站規(guī)劃［J］.電力系統(tǒng)自動(dòng)化，2013，37（13）：63-69，98.

［5］劉自發(fā)，張偉，王澤黎，等.基于量子粒子群優(yōu)化算法的城市電動(dòng)汽車(chē)充電站優(yōu)化布局［J］.中國(guó)電機(jī)工程學(xué)報(bào)，2012，32（22）：39-45.

［6］高煒欣，羅先覺(jué).基于Hopfield神經(jīng)網(wǎng)絡(luò)的多階段配電變電站的規(guī)劃優(yōu)化［J］.電工技術(shù)學(xué)報(bào)，2005，20（5）：58-64.

［7］劉志鵬，文福拴，薛禹勝，等.電動(dòng)汽車(chē)充電站的最優(yōu)選址和定容［J］.電力系統(tǒng)自動(dòng)化，2012，36（3）：54-59.

［8］葛少云，馮亮，劉洪，等.電動(dòng)汽車(chē)充電站規(guī)劃布局與選址方案的優(yōu)化方法［J］.中國(guó)電力，2012，45（11）：96-101.

［9］楊超，張步涵，陶芬，等.電力系統(tǒng)多時(shí)段無(wú)功電壓控制的兩階段優(yōu)化法［J］.高電壓技術(shù)，2007，33（9）：104-109.

［10］王成山，康曉莉，余貽鑫，等.城市高中壓電網(wǎng)無(wú)功功率優(yōu)化規(guī)劃［J］.電網(wǎng)技術(shù)，1998，22（8）：23-26.

Multi-stage Planning Optimization for Electric Vehicles Charging Station

YANG Jiajun1，CHEN Hong2，DUAN Meiqi1,QI Shuguang1
（1.State Grid Laiwu Power Supply Company，Laiwu 271100，China；2.Shandong Electric Power Transmission and Transformation Engineering Company，Jinan 250118，China）

Charging stations serve as necessary supporting facilities for electric vehicles.The construction time，location and scale has important significance for the promotion of electric vehicles.At present，researches carried out so far tend to regard the planning of charging station location as static programming problem to deal with，ignoring the problem of construction time.We put forward the multi-stage planning model of the charging station's location，and pseudo dynamic programming ideas have been applied to solve the model.With expert opinions taken into account，genetic algorithm is used to determine the planning of the target year.Optimal planning scheme of each stage is ultimately achieved through dynamic programming.

charging station；site selection；multi-stage；genetic algorithm；dynamic programming

TM732；TM614

B

1007－9904（2015）08－0018－05

2015-04-10

楊佳?。?986），男，從事電力系統(tǒng)運(yùn)行與控制、繼電保護(hù)相關(guān)工作；

陳紅（1987），女，工程師，從事繼電保護(hù)調(diào)試工作；

段美琪（1992），女，從事繼電保護(hù)工作；

亓曙光（1989），男，從事調(diào)度工作。