基于遺傳算法的電動(dòng)汽車充電站布局的最優(yōu)規(guī)劃

劉　飛

(北京物資學(xué)院，北京101149)

基于遺傳算法的電動(dòng)汽車充電站布局的最優(yōu)規(guī)劃

劉飛

(北京物資學(xué)院，北京101149)

摘要：電動(dòng)汽車充電站是電動(dòng)汽車市場化、產(chǎn)業(yè)化的重要支撐系統(tǒng)，對電動(dòng)汽車充電站的布局規(guī)劃進(jìn)行研究，構(gòu)建完善的充電服務(wù)網(wǎng)絡(luò)，有利于電動(dòng)汽車的推廣。首先分析了電動(dòng)汽車充電站布局規(guī)劃相關(guān)研究現(xiàn)狀，總結(jié)了目前充電站布局規(guī)劃存在的問題，根據(jù)區(qū)域交通流量守恒原理對所要規(guī)劃的區(qū)域進(jìn)行充電需求小區(qū)的劃分，并對其劃分原則和可行性進(jìn)行了探討。然后利用單目標(biāo)非線性規(guī)劃建立了充電站投資成本、運(yùn)行及維護(hù)成本的最小化的布局規(guī)劃模型。在模型的優(yōu)化求解方面，傳統(tǒng)的優(yōu)化算法很難求解這樣復(fù)雜的問題，選擇了遺傳算法求得模型的最優(yōu)解，確定了充電站的位置和容量，并用實(shí)例得出了優(yōu)化后的充電站及其服務(wù)范圍，驗(yàn)證了模型的準(zhǔn)確性和有效性，為充電站布局規(guī)劃工作提供了一定的經(jīng)驗(yàn)。

關(guān)鍵詞：電動(dòng)汽車充電站；布局規(guī)劃；遺傳算法；服務(wù)網(wǎng)絡(luò)成本最小

中圖分類號：TM715

文獻(xiàn)標(biāo)識碼:A

DOI:10.3969/j.issn.1672-0792.2015.08.007

收稿日期：2015-05-28。

作者簡介：劉飛(1991-),男，碩士研究生，研究方向?yàn)槲锪飨到y(tǒng)規(guī)劃，E-mail:liuxinye121@126.com。

Abstract：Electric vehicle charging stations are important support system for electric vehicle marketization and industrialization. To study the electric vehicle charging stations’ layout planning and building a sound network of services are in favor of the promotion of electric vehicles. This paper first analyzes the layout planning related research status of electric vehicle charging stations, summarizes the current problems of the charging station layout planning, according to the regional traffic flow conservation principle to divide the area into charging requirements cell, and its principles and feasible division nature were discussed. Then use the single nonlinear objective programming to establish a layout planning model whose charging stations investment costs, operation and maintenance costs are minimum. In terms of the model optimal solution, the traditional optimization algorithm is difficult to solve such a complex problem, the article choose to use the genetic algorithm to obtain the optimal solution of the model, in order to determine the location and capacity of the charging station, and the use of the example verify the accuracy and validity of the model. Finally, this article obtains charging stations and services which are optimized with examples, to verify the accuracy and validity of the model, and provide some experience for the charging station layout planning.

Keywords：electric vehicle charging station; layout; genetic algorithm; network cost minimization

0引言

汽車在城市的發(fā)展中起了不可忽視的作用，但是傳統(tǒng)的汽車使用的能源多是油氣，這樣不僅大量有污染性的氣體被排放到環(huán)境中，而且還使不能再生資源供應(yīng)加劇緊張?！禕P年世界能源統(tǒng)計(jì)年鑒2014》顯示2013年中國已成為僅次于美國石油消費(fèi)量第二的國家，天然氣消費(fèi)增速達(dá)到10.8%，為當(dāng)年天然氣消費(fèi)量最大的國家[1]。其中車用油氣是這些能源大幅度增長的原因之一，而且還有擴(kuò)張的趨勢。

就汽車行業(yè)本身來說，解決油氣短缺限制發(fā)展的問題，現(xiàn)實(shí)的選擇是從節(jié)約使用和替代兩個(gè)方面入手，即發(fā)展新能源汽車[2]。作為新能源汽車之一，電動(dòng)汽車使用的電能來源主要是太陽能、風(fēng)力、燃料、水力，一般沒有直接排放的污染物，對環(huán)境污染甚小。建設(shè)和發(fā)展電動(dòng)汽車充電設(shè)施有利于電動(dòng)汽車產(chǎn)業(yè)的推廣。充電設(shè)施是電動(dòng)汽車商業(yè)化、產(chǎn)業(yè)化過程中的重要因素，主要包括交流充電樁、充電站、電池更換站3種類型[3]。近年來，隨著車用電池技術(shù)的不斷突破，以及政府的大力支持，電動(dòng)汽車在各國、各城市得到了廣泛的推廣應(yīng)用[4，5]，純電動(dòng)汽車和可插電外充的混合動(dòng)力電動(dòng)汽車主要以集團(tuán)化用車為主，已在許多國家和地區(qū)示范應(yīng)用，充電基礎(chǔ)設(shè)施也正在加緊建設(shè)中[6]。

由于電動(dòng)汽車越來越多的優(yōu)勢被人熟知，電動(dòng)汽車保有量的不斷加大帶來了充電需求的加大，這時(shí)候充電需求就需要量化。王飛龍等[7]根據(jù)用戶的數(shù)量，考慮充電時(shí)間等因素，利用多元線性回歸和Bass擴(kuò)散模型對充電需求進(jìn)行了預(yù)測。量化了充電需求，就要對充電站布局規(guī)劃，鑒于目前落后的現(xiàn)狀，充電站的布局規(guī)劃也就成了國內(nèi)外學(xué)者研究的熱點(diǎn)。張成等[8]用網(wǎng)格法確定規(guī)劃區(qū)充電站站址，并提出了負(fù)荷率控制系數(shù)和充電負(fù)荷密集區(qū)等概念，接著建立了充電站規(guī)劃模型和充電站盈利模型。王澤黎等[9]應(yīng)用混沌粒子群算法優(yōu)化了充電站的布局。葛少云等[10]在充分考慮路網(wǎng)結(jié)構(gòu)、車流信息和用戶路程損耗等因素的情況下提出充電站選址定容的優(yōu)化方法，并利用加權(quán)Voronoi圖來實(shí)現(xiàn)充電站服務(wù)范圍的自動(dòng)劃分，然后以全社會成本最小為目標(biāo)從多種規(guī)劃方案中選擇最優(yōu)的方案。孫小慧[11]從燃料需求的空間分布角度出發(fā)，解決了需求點(diǎn)與供應(yīng)站之間的總距離最小、供應(yīng)站服務(wù)的需求量最大、以及基于此兩類目標(biāo)的多目標(biāo)優(yōu)化問題。林琳等[12]分析了電動(dòng)汽車的充電行為，然后建立了充電服務(wù)系統(tǒng)的排隊(duì)模型，旨在尋求顧客與充電站服務(wù)設(shè)置之間的平衡，保證充電站最佳服務(wù)能力和最合理配置。雖然這些文獻(xiàn)考慮到布局規(guī)劃的影響因素并構(gòu)建了數(shù)學(xué)模型，但是并沒有充分考慮充電用戶的充電需求，沒有讓資源得到充分利用，做到充電站服務(wù)網(wǎng)絡(luò)總成本最小。本文首先最大化的考慮用戶的充電需求，然后構(gòu)建了充電站布局的最優(yōu)規(guī)劃模型，通過模型的優(yōu)化求解，確定了充電站站址和規(guī)模。

1電動(dòng)汽車充電站布局規(guī)劃的數(shù)學(xué)模型

首先在選定的規(guī)劃區(qū)域內(nèi)劃分充電需求小區(qū)，然后構(gòu)建總成本最小化的目標(biāo)函數(shù)，通過優(yōu)化求解確定充電站的規(guī)模和位置。因?yàn)殡妱?dòng)公交車、環(huán)衛(wèi)電動(dòng)汽車等集團(tuán)用車具有特定的停車場所和幾乎不改變的路線，所以它們的充電站的布局規(guī)劃可以采取固定的模式。但是電動(dòng)出租車等乘用車行駛自由，沒有固定的模式，建立充電需求小區(qū)可以將問題簡化，本文的研究對象設(shè)定為集中公用充電站，服務(wù)車輛為出租車和私家車。

1.1　充電需求小區(qū)的劃分

充電需求小區(qū)法是把電動(dòng)汽車的充電需求不規(guī)則的劃分為若干個(gè)充電小區(qū)，每一個(gè)充電小區(qū)的充電需求在其幾何中心，并且建立投資成本、運(yùn)行及維護(hù)成本的優(yōu)化函數(shù)來確定充電站的位置和容量[13]。

(1)可行性

需求小區(qū)的重心和電動(dòng)汽車的數(shù)量在一定的時(shí)期內(nèi)不變，這樣就可以把具有充電需求的電動(dòng)汽車看成是位于這個(gè)區(qū)域重心位置的負(fù)荷點(diǎn)。另外，在充電站的建設(shè)初期，建設(shè)單位為了統(tǒng)一協(xié)調(diào)供電，以便發(fā)揮供需雙方最大的經(jīng)濟(jì)效益，會指導(dǎo)充電的用戶到附近的充電站進(jìn)行充電，這樣充電用戶就會固定在某處充電，使得充電需求小區(qū)更符合實(shí)際。另外根據(jù)區(qū)域交通流量守恒原理，單位時(shí)間內(nèi)，某一區(qū)域內(nèi)的電動(dòng)汽車進(jìn)出數(shù)量是一致的，區(qū)域內(nèi)的電動(dòng)車數(shù)量是一定的。所以某充電站需要提供的充電服務(wù)次數(shù)需求可以參照某一區(qū)域內(nèi)電動(dòng)汽車的數(shù)量。

(2)劃分原則

充電需求小區(qū)的劃分要做到科學(xué)、合理，應(yīng)充分考慮各種影響因素，目前充電需求小區(qū)的劃分遵循下列幾點(diǎn)：

1)由于充電安全和征地成本較高的原因，充電站不宜設(shè)在城市中心區(qū)域，因此劃分時(shí)排除中心區(qū)域；

2)充電需求小區(qū)應(yīng)充分把電動(dòng)汽車的續(xù)航里程考慮在內(nèi)，在充電需求比較集中的地方向周圍輻射，選擇的區(qū)域適當(dāng)小，控制在合理范圍內(nèi)；

3)盡量把用戶少的需求點(diǎn)放在充電小區(qū)邊緣，適當(dāng)考慮城市的自然分界和街道路網(wǎng)結(jié)構(gòu)；

4)考慮區(qū)域用地性質(zhì)。

總之，充電需求小區(qū)的劃分既要符合實(shí)際的充電服務(wù)網(wǎng)絡(luò)又要達(dá)到簡化問題的目的[14]。

1.2　數(shù)學(xué)模型的建立

科學(xué)、合理、可行的充電服務(wù)網(wǎng)絡(luò)，不僅能夠推進(jìn)電動(dòng)汽車市場化，而且還能夠兼顧充電需求和資源利用，既能使電動(dòng)汽車的充電需求得到滿足，方便電動(dòng)汽車用戶充電，還能夠合理利用資源，減少資源的浪費(fèi)[15]?？紤]到充電站布局規(guī)劃的基本原則和影響因素，在此基礎(chǔ)上建立充電成本最小化的電動(dòng)汽車充電站布局規(guī)劃模型。其數(shù)學(xué)模型描述如下：

(1)

(2)

(3)

(4)

式中：Z1表示充電站建設(shè)的投資的固定成本；Z2表示充電站運(yùn)行和維護(hù)的成本；Z3表示充電用戶的充電成本。m表示建設(shè)的充電站的數(shù)量；Cj表示充電站的建設(shè)成本；z表示貼現(xiàn)率；n表示投資回收年限；kj表示0～1變量，如果kj=1則表示第j個(gè)候選站被選中，否則kj=0；δ表示折算系數(shù)；c0表示單位車輛單位距離的損耗費(fèi)用；Ny表示每年的天數(shù)；Td表示平均每個(gè)充電用戶的日充電次數(shù)。

(5)

其中：h1表示電動(dòng)汽車百公里耗電；h2為電動(dòng)汽車平均日行駛路程；q表示電動(dòng)汽車電池的容量。Ij表示充電小區(qū)i內(nèi)的充電用戶到充電站j充電的集合。gij為0～1變量，約束充電需求小區(qū)i內(nèi)的充電用戶在某時(shí)段只到第j個(gè)充電站進(jìn)行充電。gij=1代表充電需求小區(qū)i內(nèi)的充電用戶到充電站j充電。gij=0 代表充電需求小區(qū)i內(nèi)的充電用戶不到充電站j充電。

(6)

Dij充電需求小區(qū)i的集合中心到候選站j的距離；ηij表示路況系數(shù)；Wi表示充電小區(qū)i內(nèi)電動(dòng)汽車的保有量。

1.3　約束條件

考慮到實(shí)際情況，比如充電容量和用戶的方便性，充電站布局規(guī)劃模型還需要加入以下約束條件。

(1)充電站充電容量約束

(7)

(8)

式中：Sj表示第j個(gè)充電站的配電量；P表示單個(gè)電動(dòng)汽車的充電功率；Ti表示每日第i種充電模式下的充電時(shí)間；η表示充電的效率；f表示充電機(jī)的需用系數(shù)；e(Sj)表示充電站的負(fù)載率；cosφj表示充電站的功率因數(shù)。

(2)充電站服務(wù)半徑約束

(9)

式中：充電站的服務(wù)半徑約束用R表示。

聯(lián)合公式(1)、(5)、(6)、(9)，構(gòu)建充電站布局最優(yōu)規(guī)劃的數(shù)學(xué)模型，其中構(gòu)建的模型中有很多的變量，包括電動(dòng)汽車充電用戶組成的離散變量、充電站需求量等整數(shù)變量。傳統(tǒng)的優(yōu)化算法很難求解這樣復(fù)雜的問題，本文選擇遺傳算法進(jìn)行求解。

2遺傳算法的應(yīng)用

遺傳算法是模擬生物在自然環(huán)境中優(yōu)勝劣汰、適者生存的遺傳和進(jìn)化過程而形成的一種自適應(yīng)能力的、全局性的概率搜索算法[16]。通過模擬生物進(jìn)化中優(yōu)勝劣汰、適者生存的原理，進(jìn)行編碼與進(jìn)化尋優(yōu)，末代種群中的最優(yōu)個(gè)體經(jīng)過解碼可以作為問題的近似最優(yōu)解[16]。遺傳算法沒有連續(xù)和導(dǎo)數(shù)存在的要求，搜索空間沒有限制。

2.1　染色體編碼

采用二進(jìn)制為染色體編碼，編碼串為A={aj,i=1,2,…,n}，A為維實(shí)向量，n為充電需求小區(qū)的個(gè)數(shù)，aj=gijj(j=1,2,… ,m)，m為充電站的個(gè)數(shù)，gij為0～1變量，約束充電需求小區(qū)i內(nèi)的充電用戶在某時(shí)段只到第j個(gè)充電站進(jìn)行充電，則充電站的個(gè)數(shù)為

(10)

式中：f1表示充電站的同時(shí)率；[]表示取整數(shù)。

2.2　適應(yīng)度函數(shù)

適應(yīng)度函數(shù)也叫評價(jià)函數(shù)，根據(jù)目標(biāo)函數(shù)可以確定適應(yīng)度函數(shù)[17]。遺傳算法常常將目標(biāo)函數(shù)直接作為適應(yīng)度函數(shù)，但是由于在執(zhí)行操作時(shí)，它要求與個(gè)體適應(yīng)度成正比的概率來決定當(dāng)前群體中每個(gè)個(gè)體遺傳到下一代群體中的概率，要正確計(jì)算概率，要求所有個(gè)體適應(yīng)度函數(shù)值必須非負(fù)[18]。把目標(biāo)函數(shù)當(dāng)作適應(yīng)度函數(shù)，不用再進(jìn)行求導(dǎo)等數(shù)學(xué)運(yùn)算，由以上可知，本文的目標(biāo)函數(shù)就是最小化問題，可以進(jìn)行適當(dāng)?shù)霓D(zhuǎn)化，即Fit(Z)=-Z。

則適應(yīng)度函數(shù)為：

(11)

式中：cmax為Z的最大估計(jì)值。

3遺傳算法的終止原則和最優(yōu)解的確定

3.1　終止原則

考慮到充電站布局規(guī)劃的模型的情況，關(guān)于遺傳算法有3種終止原則：

(1)如果在事先選擇的最大迭代次數(shù)之內(nèi)獲得最優(yōu)解，就停止迭代；

(2)如果到了事先選擇的最大的迭代次數(shù)即停止迭代；

(3)在可能得不到最優(yōu)解的情況下，滿足以下收斂準(zhǔn)則就停止運(yùn)行。

通常收斂準(zhǔn)則可以定義為：

(12)

式中：第G代最優(yōu)個(gè)體的適應(yīng)度用u*(G)表示。

3.2　確定最優(yōu)解的方法

遵循上面遺傳算法的終止原則，相應(yīng)確定最優(yōu)解可以參照以下標(biāo)準(zhǔn)：

(1)群體中最好的為最優(yōu)解。

(2)最優(yōu)解可以是在群體中挑選出的最好的。

(3)最優(yōu)解可以是滿足條件的那個(gè)。

還有一種情況就是得到很多個(gè)最優(yōu)解或者滿意解，這個(gè)時(shí)候就要根據(jù)實(shí)際情況選擇。

算法流程如圖1。

4算例分析

某規(guī)劃區(qū)的面積為10.5 km2，在規(guī)劃的時(shí)間范圍內(nèi)電動(dòng)汽車的保有量是2 190輛，目前已知的是規(guī)劃區(qū)已經(jīng)按照用地性質(zhì)、道路等因素劃分了20個(gè)充電需求小區(qū)。充電需求小區(qū)內(nèi)幾何中心的坐標(biāo)和電動(dòng)汽車的數(shù)量如表1所示。先假設(shè)在充電站規(guī)劃這段時(shí)間之內(nèi)電動(dòng)汽車的數(shù)量恒定，每天快速充電的用戶比例是80%，常規(guī)充電的用戶的比例是20%，充電功率設(shè)定為20 kW，平均每輛電動(dòng)汽車兩天充一次電?，F(xiàn)在規(guī)劃區(qū)域內(nèi)計(jì)劃建設(shè)5個(gè)充電站，已經(jīng)考慮了所有的情況，候選站址的具體位置見表2。

圖1　遺傳算法流程圖

表1　電動(dòng)汽車保有量和小區(qū)的幾何中心　km

表2　候選站址的地理位置　km

電動(dòng)汽車充電需求小區(qū)和候選充電站分布如圖2。

參數(shù)取值如表3。

初步搜索尋優(yōu)以式(1)為目標(biāo)函數(shù)，式(6)～(9)為約束條件進(jìn)行遺傳編碼，采用Matlab編寫程序，最后運(yùn)行得到模型的優(yōu)化結(jié)果，候選站址和其服務(wù)范圍見表4。

圖2　電動(dòng)汽車充電需求小區(qū)和候選充電站分布圖

優(yōu)化后的充電站及其服務(wù)的充電需求小區(qū)見圖3。

從表4可以得出，充電需求小區(qū)內(nèi)的幾何中心基本上可以代表充電站的站址，規(guī)劃區(qū)域內(nèi)的2 190輛電動(dòng)汽車的充電需求可以用這5座充電站來滿足，總年費(fèi)用為1 122.27萬元。從表中的數(shù)據(jù)也可以看出，每個(gè)充電站服務(wù)的車輛并不相同，所以規(guī)劃的充電站的容量也不一樣，這樣建設(shè)的充電站科學(xué)合理。

表3　參數(shù)取值表

表4　優(yōu)化后的站址及其服務(wù)范圍　km

圖3　優(yōu)化后的充電站及其服務(wù)的充電需求小區(qū)

5結(jié)論

充電站的布局規(guī)劃涉及很多的部門，工程量非常大，所以在建設(shè)的過程中要考慮建設(shè)的成本，站在方便用戶的角度，通過科學(xué)規(guī)劃可以做到節(jié)約資源。本文基于電動(dòng)汽車充電站布局規(guī)劃相關(guān)研究現(xiàn)狀，對所要規(guī)劃的區(qū)域進(jìn)行充電需求小區(qū)的劃分，建立年費(fèi)用函數(shù)最小模型，利用遺傳算法求得滿意解，使規(guī)劃區(qū)域內(nèi)電動(dòng)汽車充電用戶充電需求都得到了滿足。從算例分析得出，本文采用的方法和模型是有一定的科學(xué)性的。但是充電站布局規(guī)劃涉及的面很廣，還需要在實(shí)際布局規(guī)劃過程中根據(jù)實(shí)際情況合理確定充電站的規(guī)模和站址。

參考文獻(xiàn):

[1]Ruhl C. BP世界能源統(tǒng)計(jì)年鑒2014 [M] .英國石油公司, 2014.

[2]趙玲.濟(jì)南市車用天然氣需求預(yù)測及加氣站選址研究[D] .濟(jì)南：山東大學(xué)，2008.

[3]Q/GDW478-2010,電動(dòng)汽車充電設(shè)施建設(shè)技術(shù)導(dǎo)則[S] .

[4]胡天嬌，甄翠敏.國內(nèi)外電動(dòng)汽車基礎(chǔ)設(shè)施建設(shè)運(yùn)營[J] .河北聯(lián)合大學(xué)學(xué)報(bào)(社會科學(xué)版)，2014，14(1)：54-56.

[5]王輝.電動(dòng)汽車充電站規(guī)劃與運(yùn)營研究[D].杭州：浙江大學(xué)，2013.

[6]王陽.純電動(dòng)公交車充電需求特性及充電設(shè)施規(guī)劃方法的研究[D] .北京：華北電力大學(xué)，2012.

[7]王飛龍，孫凱航，李燕青.基于用戶分類的電動(dòng)汽車充電站需求預(yù)測[J] .黑龍江電力，2013，35(2)：132-134.

[8]張成，滕歡.電動(dòng)汽車充電站規(guī)劃模型及評價(jià)方法[J].電力系統(tǒng)及其自動(dòng)化學(xué)報(bào)，2014，28(1)：49-52.

[9]王澤黎，齊燦.電動(dòng)汽車充電站最優(yōu)規(guī)模和布局[J] .電力建設(shè)，2014，35(4)：132-136.

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

[11]孫小慧.考慮時(shí)空限制的電動(dòng)汽車充電站布局模型[D] .大連：大連理工大學(xué)，2012.

[12]林琳，高亞靜.基于排隊(duì)理論的充電站最優(yōu)配置[J].電力科學(xué)與工程，2014,30(4):33-37.

[13]吳春陽.電動(dòng)汽車充電設(shè)施規(guī)劃、接入及智能響應(yīng)[D] .鄭州：鄭州大學(xué)，2011.

[14]何戰(zhàn)勇.電動(dòng)汽車充電站規(guī)劃方法及運(yùn)營模式研究[D] .北京：北京交通大學(xué)，2012.

[15]熊虎，向鐵元，祝勇剛，等.電動(dòng)汽車公用充電站布局的最優(yōu)規(guī)劃[J] .電力系統(tǒng)自動(dòng)化，2012，(23):65-70.

[16]邊霞，米良.遺傳算法理論及其應(yīng)用研究進(jìn)展[J] .計(jì)算機(jī)應(yīng)用研究，2010，27(7)：2425-2429.

[17]王進(jìn)強(qiáng)，陳少華.基于改進(jìn)遺傳算法的含分布式電源的配電網(wǎng)故障定位[J].電力科學(xué)與工程，2013，29(12)：13-17.

[18]唐連生，李思寰，張雷.物流系統(tǒng)優(yōu)化與仿真[M] .北京：中國物資出版社，2013.

Based on Genetic Algorithm Optimal Layout of Electric Vehicle Charging Station

Liu Fei

(Beijing Wuzi University，Beijing 101149，China)