基于引入模擬退火思想的改進(jìn)粒子群算法的電動(dòng)汽車充電站最優(yōu)規(guī)劃*

閆天澤，邱曉燕，劉延博，唐可，萬成江

（四川大學(xué)智能電網(wǎng)四川省重點(diǎn)實(shí)驗(yàn)室，成都610065）

0 引 言

隨著化石燃料的日益枯竭，以及全球環(huán)境問題的日益惡化，新能源產(chǎn)業(yè)成為了替代傳統(tǒng)化石燃料解決能源危機(jī)的重要舉措，受到了各個(gè)國家的大力扶持。隨著電動(dòng)汽車技術(shù)，特別是電池技術(shù)的發(fā)展，以及一些國家在政策上的大力支持，電動(dòng)汽車在過去的十多年間得到了快速發(fā)展［1］。

電動(dòng)汽車充電站可以為電動(dòng)汽車提供充電、維修等多項(xiàng)服務(wù)，是未來電動(dòng)汽車產(chǎn)業(yè)發(fā)展所需要的重要基礎(chǔ)設(shè)施。目前，國內(nèi)外學(xué)者對(duì)電動(dòng)汽車的充放電行為和充電站的選址和定容方面做了大量的研究。文獻(xiàn)［2-4］研究了電動(dòng)汽車大規(guī)模接入電網(wǎng)對(duì)電網(wǎng)造成的影響。文獻(xiàn)［5-7］研究了電動(dòng)汽車的負(fù)荷特性，并分別提出了不同的模型和計(jì)算方法。文獻(xiàn)［8］提出了基于分時(shí)電價(jià)的電動(dòng)汽車有序充電策略，達(dá)到了削峰填谷的目的。文獻(xiàn)［9］以博弈的思想采用全局最優(yōu)的定價(jià)策略，使充電商和用戶達(dá)到利益最大化。文獻(xiàn)［10］分析電動(dòng)汽車充電站的接入方式和影響充電站規(guī)模的相關(guān)因素。文獻(xiàn)［11］采用分層遞進(jìn)的方法對(duì)充電站的規(guī)劃求解。然而這些方法都沒有將一些影響充電站規(guī)劃的實(shí)際因素（尤其是交通信息）納入規(guī)劃模型中。并且電動(dòng)汽車負(fù)荷具有分布不均和流動(dòng)性大的特點(diǎn)，因此服務(wù)區(qū)的劃分尤為重要。

文章將交通信息和用戶的充電成本納入到規(guī)劃的數(shù)學(xué)模型中。對(duì)原始粒子群算法做出改進(jìn)，提高算法準(zhǔn)確率與效率。用加權(quán)Voronoi圖和引入模擬退火思想的改進(jìn)粒子群算法聯(lián)合求解，很好地解決了待規(guī)劃區(qū)域服務(wù)區(qū)劃分、充電站的選址和定容問題。

1 數(shù)學(xué)模型

1.1 選址模型

電動(dòng)汽車充電站的建設(shè)成本不僅要考慮建站的征用土地、基礎(chǔ)建設(shè)、購買充電設(shè)備等費(fèi)用，還需要考慮充電站每年設(shè)備維護(hù)成本。以往的文獻(xiàn)在對(duì)充電站規(guī)劃問題只考慮充電商的利益。因此，文章在進(jìn)行電動(dòng)汽車充電站優(yōu)化規(guī)劃時(shí)，創(chuàng)新性地不僅考慮了電動(dòng)汽車充電站建設(shè)運(yùn)行的成本，還將用戶的充電成本納入模型中，形成全社會(huì)總成本。

（1）平均每年電動(dòng)汽車充電站j的投資費(fèi)用為：

式中fCSj表示電動(dòng)汽車充電站j折算到每年的投資費(fèi)用；C表示修建充電站所需征用土地和基礎(chǔ)建設(shè)的固定投資成本；a是包含購買充電機(jī)、配電變壓器修建成本和鋪設(shè)輸電線路等有關(guān)的等效投資系數(shù)；b為充電機(jī)的單價(jià)；Nchrg為充電站j所需安裝充電機(jī)數(shù)量；r0為貼現(xiàn)率；Y為運(yùn)行年限。

（2）電動(dòng)汽車充電站j每年的運(yùn)行維護(hù)費(fèi)用主要包括設(shè)備維修、折舊費(fèi)用，員工工資等，可以按初期投資的百分比進(jìn)行計(jì)算，表達(dá)式如下：

式中frj表示電動(dòng)汽車充電站j的每年運(yùn)行投資費(fèi)用；σ代表比例系數(shù)。

（3）用戶的充電成本指用戶有充電需求時(shí)候，從充電需求點(diǎn)駛?cè)氤潆娬镜目振傠娏肯馁M(fèi)用，以及用戶的排隊(duì)等待費(fèi)用。其表達(dá)式為：

式中fcoustomerj表示平均每年電動(dòng)汽車充電站j的服務(wù)

式中F表示充電站規(guī)劃方案折算到每年的全社會(huì)總成本；N表示需要修建的電動(dòng)汽車充電站的數(shù)量。如今隨著經(jīng)濟(jì)的發(fā)展，土地征用等費(fèi)用越來越昂貴，充電站的初期投資成本過大。以往的文獻(xiàn)沒有考慮初期投資對(duì)總成本的影響。因此文章引入投資權(quán)重系數(shù)概念，用φ表示充電站初期投資權(quán)重，ψ表示運(yùn)行成本權(quán)重，τ表示用戶成本權(quán)重。文章設(shè)定φ＝0.5，ψ＝0.2，τ＝0.3。

1.2 基于M/M/s排隊(duì)理論的定容模型

電動(dòng)汽車的充電需求是隨機(jī)的。文獻(xiàn)［13-14］用排隊(duì)論中的M/M/s模型模擬電動(dòng)汽車駛?cè)氤潆娬镜某潆娦袨?。文獻(xiàn)［15］指出在相同服務(wù)速率下，采用單隊(duì)列排隊(duì)方式的等待時(shí)間較采用多隊(duì)列排隊(duì)方式的等待時(shí)間大幅降低。一般情況下，雖然電動(dòng)汽車車主非常關(guān)心排隊(duì)等待時(shí)間，但在電動(dòng)汽車數(shù)量一定的時(shí)候，排隊(duì)等待時(shí)間會(huì)隨著充電站所安裝的充電機(jī)數(shù)量的增加而減少，因此電動(dòng)汽車充電站的充電機(jī)數(shù)量應(yīng)該基于排隊(duì)等待時(shí)間的期望下進(jìn)行配置。電動(dòng)汽車排隊(duì)等待時(shí)間期望的數(shù)學(xué)模型為：區(qū)域內(nèi)電動(dòng)汽車用戶在充電路途中所消耗的費(fèi)用。fDT表示用戶有充電需求時(shí)的空駛損耗成本；fQT表示用戶排隊(duì)等待成本；ζ表示城市出行時(shí)間成本；β表示城市道路曲折系數(shù)，為城市中兩點(diǎn)的實(shí)際距離和直線距離的比值，文獻(xiàn)［12］歸納了常見交通網(wǎng)絡(luò)結(jié)構(gòu)中4種典型的曲折系數(shù)；Eij表示充電需求點(diǎn)i到所屬充電站j的歐幾里德距離；nev為每個(gè)交通節(jié)點(diǎn)平均每天有充電需求的電動(dòng)汽車數(shù)量；E1km為電動(dòng)汽車單位耗電量；pe為電價(jià)；Wqj表示各個(gè)充電站的排隊(duì)等待時(shí)間期望。

因此得到全社會(huì)總成本優(yōu)化模型的具體數(shù)學(xué)表達(dá)式如下：

式中Wt為電動(dòng)汽車排隊(duì)等待時(shí)間；λ表示在單位時(shí)間內(nèi)，服從泊松分布的電動(dòng)汽車到達(dá)充電站的數(shù)量；μ表示充電機(jī)的充電速率；ρ＝λ/μ表示充電機(jī)的平均服務(wù)效率。

如果排隊(duì)等待時(shí)間期望Wt不超過最大排隊(duì)等待時(shí)間期望Wmax，通過對(duì)式（5）求反函數(shù)來求得充電機(jī)數(shù)量Nchrg很困難。因此文章采用遍歷法求充電機(jī)數(shù)量Nchrg，設(shè)定一個(gè)最大期望時(shí)間Wmax，充電機(jī)數(shù)量的初值為Nchrg＝fceil（ρ），之后逐步增加充電機(jī)數(shù)量，直至使期望時(shí)間小于最大期望時(shí)間，則充電機(jī)數(shù)量Nchrg即為所求。經(jīng)試驗(yàn)證明，期望時(shí)間會(huì)隨著充電機(jī)數(shù)量的增加而快速減小。

1.3 約束條件

（1）系統(tǒng)潮流約束

（2）節(jié)點(diǎn)電壓約束

式中NCS表示待規(guī)劃區(qū)的所要修建的電動(dòng)汽車充電站個(gè)數(shù)；Ptotal表示待規(guī)劃地區(qū)的充電總需求量；Smax，Smin分別代表電動(dòng)汽車充電站的容量上限和容量下限；fceil函數(shù)表示求不小于給定實(shí)數(shù)的最小整數(shù)。

2 加權(quán)Voronoi圖和改進(jìn)粒子群算法相結(jié)合的聯(lián)合求解方法

2.1 加權(quán)Voronoi圖

Voronoi圖（又稱為V圖）又稱泰森多邊形，憑借著其具備最臨近特性，近些年來被廣泛應(yīng)用于測繪、考古等領(lǐng)域，尤其廣泛應(yīng)用于地理設(shè)施選址方面［16］。V圖在電力系統(tǒng)也應(yīng)用于變電站的規(guī)劃當(dāng)中［17］。設(shè)P＝{P1，P2，……，PN}∈R2（2≤n≤∞）是平面上 n個(gè)互不相同的點(diǎn)的集合，d（p，Pi）表示平面中任意一點(diǎn)p到Pi的直線距離，則Voronoi圖可以定義為：

式中 j＝1，2，…，n，且 j≠i。

設(shè) ηi（i＝1，2，…，n）為一組給定的正實(shí)數(shù)，分別代表平面上n個(gè)點(diǎn)的權(quán)重，則加權(quán)Voronoi圖可以定義為：

常規(guī)的V圖不能反映交通流量對(duì)充電站規(guī)劃的影響，因此文章采用加權(quán)V圖來反映交通流量對(duì)充電站規(guī)劃的影響。按式（13）計(jì)算每個(gè)服務(wù)區(qū)域的權(quán)重，生成加權(quán)V圖。然而V圖缺乏全局尋優(yōu)能力，文章用加權(quán)V圖借助粒子群算法的全局尋優(yōu)能力進(jìn)行全局優(yōu)化。

加權(quán)V圖權(quán)重計(jì)算方法：

式中ωi表示各個(gè)服務(wù)分區(qū)的權(quán)重；Sck為參考容量；P∑為各個(gè)服務(wù)分區(qū)的充電需求。

2.2 改進(jìn)粒子群算法

粒子群算法（PSO）在求解優(yōu)化問題的初期具有很快的收斂速度，然而后期由于所有粒子都向最優(yōu)粒子靠近，整個(gè)種群喪失了多樣性，粒子容易陷入局部最優(yōu)解［18］。因此文章對(duì)傳統(tǒng)粒子群算法［19］做出如下改進(jìn)，并根據(jù)模擬退火算法（SA）的特性提出了一種引入模擬退火思想的改進(jìn)粒子群算法（PSOSA）：

（1）改進(jìn)慣性權(quán)重更新機(jī)制

粒子群算法的慣性權(quán)重是影響算法收斂速度和尋優(yōu)結(jié)果的一個(gè)重要因素［20］。當(dāng)慣性權(quán)重取較大的值時(shí)，算法具有較好的全局搜索能力；當(dāng)慣性權(quán)重取較小的值時(shí)，算法具有較好的局部尋優(yōu)能力。因此，在整個(gè)算法的迭代過程中，首先將慣性權(quán)重賦予一個(gè)較大的值，使算法在快速地在全局范圍內(nèi)搜尋那個(gè)最優(yōu)解所在的區(qū)域，之后隨著迭代過程的進(jìn)行，慣性權(quán)重逐漸縮小，使得算法在更小的范圍內(nèi)尋找最優(yōu)值。因此文章對(duì)慣性權(quán)重做出如下改進(jìn)：

式中m是為了保證 ω的取值在［ωmin，ωmax］之間；k的取值影響慣性權(quán)重的減小速度；d表示當(dāng)前的迭代次數(shù)；n表示總的迭代次數(shù)。

（2）引入模擬退火思想

原始粒子群算法中，對(duì)每個(gè)粒子的飛行速度控制在一定范圍內(nèi)可以防止粒子產(chǎn)生較大的偏移對(duì)整個(gè)種群的尋優(yōu)結(jié)果和收斂速度產(chǎn)生影響。但原始粒子群算法沒有對(duì)每個(gè)粒子的位置加以限制。如果一個(gè)粒子移動(dòng)到相比于當(dāng)前位置較優(yōu)的位置，并且對(duì)全局來說是一個(gè)最優(yōu)位置時(shí)，以后的若干次迭代求解都將在該位置的基礎(chǔ)上進(jìn)行，這樣會(huì)影響算法的性能，使算法很容易陷入局部最優(yōu)位置。為了使算法跳出可能的局部最優(yōu)位置，文章將模擬退火思想引入到算法中。

每個(gè)粒子運(yùn)動(dòng)到新位置后，計(jì)算其適應(yīng)度，若適應(yīng)度的值優(yōu)于當(dāng)前位置，則粒子移動(dòng)到新位置，如果適應(yīng)度沒有優(yōu)于當(dāng)前位置，計(jì)算適應(yīng)度變化值Δe，如果 exp（Δe/t）＞rand（0，1），則粒子移動(dòng)到新的位置，完成退火操作。其中，t表示當(dāng)前溫度rand（0，1），表示［0，1］之間的一個(gè)隨機(jī)數(shù)。溫度按照 ti＋1＝tδi衰減，δ表示退火速度。

這樣每一個(gè)粒子都會(huì)經(jīng)過一個(gè)退火的過程，粒子更新位置不僅按照粒子群優(yōu)化公式移動(dòng)，還遵循一定概率選擇更新位置，從而避免粒子在整個(gè)迭代過程中陷于局部最優(yōu)解，提高整個(gè)種群的尋優(yōu)能力。

3 求解過程

文章的規(guī)劃過程是：

（1）由電動(dòng)汽車充電站的最大容量Smax和最小容量Smax，參照式（10）來估計(jì)待規(guī)劃地區(qū)所需修建的充電站最大個(gè)數(shù)Nmax和最小個(gè)數(shù)Nmin；

（2）設(shè)置充電站個(gè)數(shù)的循環(huán)變量N，對(duì)于每一個(gè)N，按照坐標(biāo)幾何法生成初始站址，并利用加權(quán)V圖實(shí)現(xiàn)待規(guī)劃地區(qū)的各個(gè)充電站的服務(wù)區(qū)域的劃分；

（3）根據(jù)式（5）和式（6）用遍歷法求解每個(gè)服務(wù)分區(qū)內(nèi)需要安裝的充電機(jī)數(shù)量；

（4）在各個(gè)服務(wù)分區(qū)內(nèi)利用改進(jìn)粒子群算法，以全社會(huì)成本最小為目標(biāo)進(jìn)行優(yōu)化選址定容，從而得到每一種N對(duì)應(yīng)的充電站最優(yōu)規(guī)劃方案；

（5）對(duì)所有規(guī)劃方案排序，選取成本最小的方案作為待規(guī)劃地區(qū)的最優(yōu)規(guī)劃方案。具體規(guī)劃流程見圖1。

4 算例分析

4.1 算例模型

文章以南方某市經(jīng)濟(jì)開發(fā)區(qū)的電動(dòng)汽車充電站規(guī)劃為例。該經(jīng)濟(jì)開發(fā)區(qū)共有交通節(jié)點(diǎn)25個(gè)，規(guī)劃區(qū)面積為36 km2，該規(guī)劃區(qū)域的交通結(jié)構(gòu)如圖2所示。各個(gè)交通節(jié)點(diǎn)的交通流量如表1所示。

到規(guī)劃年預(yù)計(jì)電動(dòng)汽車所占比例為15%，充電率為10%。

文章假定每座充電站的固定投資成本C取值100萬元；與充電機(jī)數(shù)量有關(guān)的等效投資系數(shù)a取2萬元/臺(tái)2；充電機(jī)的單價(jià)b取10萬元/每臺(tái)；貼現(xiàn)率r0取0.08；運(yùn)行年限為20年。城市道路曲折系數(shù)β取1.3；電價(jià)為0.7元/kW·h；電動(dòng)汽車平均每公里耗電量E1km取0.15 kW·h/km；該地區(qū)用戶出行成本為20元/h；單臺(tái)充電機(jī)的功率為96 kW；充電站最大容量配置為25臺(tái)充電機(jī)，最小容量配置為6臺(tái)充電機(jī)；充電機(jī)的充電效率為90%，同時(shí)率為85%。

圖1 規(guī)劃流程Flg.1 Planning process

圖2 規(guī)劃區(qū)交通結(jié)構(gòu)示意圖Fig.2 Schematic diagram of traffic structure in planning area

表1 各節(jié)點(diǎn)坐標(biāo)和交通流量Tab.1 Coordinates and traffic flow of each node

4.2 計(jì)算結(jié)果與分析

根據(jù)式（10）預(yù)估該地區(qū)充電站個(gè)數(shù)范圍為Nmin＝2，Nmax＝7；按照?qǐng)D1所示的流程，以及所提出的規(guī)劃方法，配置粒子群算法計(jì)算得到各種方案的全社會(huì)總成本和充電站具體規(guī)劃結(jié)果，全社會(huì)總成本計(jì)算結(jié)果如圖3所示。

圖3 充電站全社會(huì)年成本曲線Fig.3 Social annual total cost curve of charging stations

由圖3可以看出，當(dāng)該地區(qū)修建4座充電站時(shí)全社會(huì)的成本最小，為585.29萬元。針對(duì)充電站數(shù)量為4座時(shí)的最優(yōu)規(guī)劃方案，得到具體的充電站配置如表2所示，最優(yōu)規(guī)劃的服務(wù)區(qū)劃分如圖4所示。

表2 充電站最優(yōu)配置Tab.2 Optimal configuration of charging stations

圖4 充電站服務(wù)區(qū)劃分及選址結(jié)果Fig.4 Result of charging stations services division and location

5 結(jié)束語

文章研究了考慮交通流量和用戶充電成本的電動(dòng)汽車充電站規(guī)劃問題，以最小化的全社會(huì)總成本為目標(biāo)，建立了充電站的選址和定容模型，通過對(duì)算例用加權(quán)V圖和引入模擬退火思想的改進(jìn)粒子群算法聯(lián)合求解，得出的主要結(jié)論如下：

（1）計(jì)及交通流量和用戶充電成本的模型適用于電動(dòng)汽車充電站規(guī)劃問題，得出的結(jié)論符合實(shí)際情況。對(duì)未來電動(dòng)汽車充電站規(guī)劃具有一定的指導(dǎo)意義；

（2）改進(jìn)慣性權(quán)重更新機(jī)制和引入模擬退火思想的改進(jìn)粒子群算法在求解效率上更高，可以有效避免陷入局部最優(yōu)問題。

在文章研究的基礎(chǔ)上，未來還應(yīng)考慮土地價(jià)格，地區(qū)種類，用戶充電習(xí)慣，電動(dòng)汽車類型等實(shí)際因素，以使模型更貼近實(shí)際情況。