基于滿意優化的電動汽車充電站選址

賈永基， 邢芳芳

(東華大學 旭日工商管理學院， 上海 200051)

基于滿意優化的電動汽車充電站選址

賈永基， 邢芳芳

(東華大學 旭日工商管理學院， 上海 200051)

充電站選址是當前電動汽車推廣中面臨的首要問題. 基于滿意優化理論，提出了電動汽車用戶滿意度評價函數；通過引入充電站等級概念，以平均電動汽車用戶滿意度最大為目標函數，建立了多等級電動汽車充電站選址的混合整數規劃模型，并提出了基于免疫算法的模型求解算法. 測試結果表明，該模型可以有效地確定充電站的位置、等級及服務區域，并且其求解算法是快速、有效的.

滿意優化； 電動汽車； 充電站選址； 免疫算法

受能源危機和環境壓力的雙重影響，具有能源利用效率高、零污染、低噪聲等優點的電動汽車，正在受到世界各國的廣泛關注.然而，電動汽車充電站網絡的建設遠遠滯后于電動汽車的發展.雖然國內已經建成較多充電樁，但大都處于居民小區內部，充電速度慢，且僅服務于單個電動汽車用戶；現有的部分公共充電站，也處于技術驗證及示范階段，無法滿足電動汽車用戶的日常充電需求，從而降低電動汽車潛在用戶的購買意愿.充電站選址問題已經成為制約我國電動汽車普及的關鍵因素之一.

目前，電動汽車充電站選址問題已經成為一項研究熱點.文獻[1]根據區域交通流量守恒定理，研究了電動汽車充電站的布局和定容問題，建立了綜合費用最小模型，并對成都市充電站建設提出了解決方案.文獻[2]考慮了地理環境和服務半徑兩個因素，構造了電動汽車充電站最優規劃的數學模型，并采用改進的原對偶點法來求解.文獻[3]考慮了充電站具有城市交通公共服務設施以及普通用電設施的雙重屬性，以俘獲的交通流量最大、配電系統網絡損耗最小以及節點電壓偏移最小為目標，建立了充電站選址的多目標決策模型.文獻[4-6]對臺灣澎湖列島旅游景區內的電動汽車充電站布局問題進行了一系列研究，從單目標集合覆蓋問題到最大覆蓋問題逐步深入研究，建立了多目標混合整數規劃模型，并對結果進行了靈敏度分析，研究表明，使用多等級混合充電站可實現最佳布局.文獻[7]構建了預算費用限制下的最大覆蓋模型，并提出了混合啟發式算法，用以確定充電站的位置和類型.文獻[8]綜合考慮了充電站建設運營成本和顧客充電成本，針對充電站規劃的多目標性，提出了一種新的多種群混合遺傳算法.文獻[9]探討了帶容量限制的電動汽車電池交換站選址-路徑問題，同時確定電池交換站的選址策略和電動汽車的最優行駛路徑，并提出兩個啟發式算法(SIGALNS和TS-MCWS)用于求解該問題.

免疫算法是通過模擬生物免疫系統的智能行為而提出的仿生算法，是一種確定性和隨機性相結合的啟發式算法.自文獻[10]于1974年首次提出免疫系統的模型之后，免疫算法已成為繼遺傳算法和神經網絡之后的一個研究熱點，其研究成果已經廣泛應用于車輛調度、機器學習、圖像處理和設施選址等諸多領域.文獻[11]將免疫算法與遺傳算法相結合，提出了一種新的免疫遺傳算法并用于求解具有75個城市的旅行商問題，仿真結果表明，該算法的收斂速度顯著提高.文獻[12]概述了免疫算法的產生、發展和作用機理，比較了不同免疫算法的設計方法及其優劣.文獻[13]討論了幾種典型的免疫算法及其應用情況，展望了今后的研究重點和發展趨勢.文獻[14]綜述了免疫算法的基本模型、原理，并討論了免疫算法的種類及最新應用成果.文獻[15]將免疫算法用于分布式電源選址與定容問題的求解.文獻[16]提出了多目標優化量子免疫算法，并用于通信基站選址問題的求解.文獻[17]將免疫算法用于帶權值的物流配送中心選址問題的求解.

由于電動汽車用戶需求分布不均勻，單一等級的充電站網絡不能低成本地滿足所有用戶的充電需求，因此，建立不同等級和不同服務能力的充電站網絡可以提高充電站運營商和電動汽車用戶的整體利益.2010年7月，標準化指導性技術文件——《電動汽車充電站電能供給與保障技術規范：充電站》出臺，該文件將電動汽車充電站分為4個等級，各等級充電站動力蓄電池存儲能、單路配電容量、日服務車輛數目等各不相同，如表1所示.

表1 電動汽車充電站等級Table 1 Glades of electric vehicle recharging stations

目前，對電動汽車充電站選址問題的優化主要是從充電站的運營成本、建設成本或充電服務獲利的角度考慮，很少考慮電動汽車用戶對充電服務的滿意度問題. 電動汽車現在正處于推廣階段，政府出臺了一系列促進充電站建設的補貼政策.為了迅速提高電動汽車使用的便利性，促進更多潛在用戶購買電動汽車，成本不再是建設充電站的首要考慮因素，而用戶充電的便利性，即用戶對充電服務的滿意度，已經成為充電站建設的首要目標. 因此，在當前推廣階段，應該從電動汽車用戶滿意度的角度考慮充電站的選址問題，通過不同等級充電站的合理布局，使得電動汽車用戶的充電需求得到最大可能的滿足，從而推動電動汽車的廣泛普及.

本文首先建立了一個多等級電動汽車充電站選址問題的混合整數規劃模型，該模型可以決策充電站的建站位置、等級及服務區域等問題；然后，提出了求解該模型的改進免疫算法，并通過一個算例來說明模型和算法的有效性.

1 電動汽車用戶滿意度評價函數

電動汽車用戶滿意度評價函數是一個反映用戶實際體驗的變量取值(客觀)與用戶心理狀態(主觀)之間關系的數學函數. 現有文獻中的充電站選址模型主要是通過優化充電站的位置，使電動汽車用戶與充電站之間的距離之和最短，沒有考慮電動汽車用戶充電的滿意度，也可以認為電動汽車用戶滿意度是恒定不變的，跟抵達充電站的行駛距離無關，如圖1(a)所示. 但在許多實際問題中，電動汽車用戶滿意度隨著需求點與充電站的距離變大而降低，因為用戶更加愿意充電站建設在自己的“家門口”，如圖1(b)所示的用戶滿意度曲線，可以很好地表達電動汽車用戶的這種偏好.

(a) 恒定的用戶滿意度 (b) 變化的用戶滿意度 圖1 用戶滿意度曲線Fig.1 Curves of customer satisfaction

式(1)是圖1(b)所示的電動汽車用戶滿意度函數的數學表達[18].

(1)

式中：dij為需求點i到充電站j的距離；F(dij)為需求點i的電動汽車用戶的充電滿意度；Li和Ui為需求點i的用戶滿意度變化的臨界值，用戶滿意度在臨界值Li和Ui附近的變化較小，在曲線中間部分的變化較大.F(dij)與dij的關系如下：

(1)dij在區間[0，Li]時，用戶滿意度最大為100%；

(2)dij在區間(Li，Ui]時，用戶滿意度為0到100%的非負數；

(3)dij在區間(Ui， +∞)時，用戶不能接受，滿意度為0.

2 電動汽車充電站選址模型

2.1 基本假設

基于滿意優化的電動汽車充電站選址模型的基本假設如下：

(1) 每個需求點代表一個小型區域，其需求量是在該區域內有充電需求的電動汽車用戶的總和；

(2) 每個需求點處的電動汽車用戶只能到同一個充電站進行充電；

(3) 電動汽車行駛速度不受路況影響，保持恒定；

(4) 車輛類型、電池類型均相同.

2.2 符號說明

假設i為電動汽車用戶所在的需求點，其數量為n，I為需求點的集合，i∈I；j為充電站候選點，其數量為m，J為候選點的集合，j∈J；hi為需求點i的需求量，即需要充電的電動汽車數量；k={1， 2， 3， 4}為電動汽車充電站等級；sk為k等級充電站的服務能力；p為需要建設的充電站數量；dij為需求點i到候選點j的距離.

Xjk為0-1決策變量，如果在候選點j處建立等級為k的充電站時，取值為1；其他情況取值為0.Yij也為0-1決策變量，如果需求點i的用戶到候選點j處充電，取值為1；其他情況取值為0.

2.3 目標函數與約束條件

目標函數(式(2))表示電動汽車用戶平均滿意度最大；式(3)表示任一需求點的電動汽車用戶只能到一個充電站接受服務；式(4)表示在一個候選點至多只能建設一個充電站；式(5)表示只有在候選點處建設了充電站，用戶才能到該充電站接受服務；式(6)表示充電站等級必須滿足所分配的所有需求點的充電需求；式(7)表示需要建設充電站的總數量；式(8)和(9)表示0-1決策變量.

(2)

(3)

(4)

(5)

(6)

(7)

Xjk∈{0， 1} ?j∈J

(8)

Yij∈{0， 1} ?i∈I，j∈J

(9)

3 基于免疫算法的模型求解算法

電動汽車充電站選址問題屬于NP(non-deterministic polynomial)難問題，無法得到精確的最優解，因而只有采用啟發式算法來求得滿意解[19-22].

近年來，隨著免疫算法研究的不斷深入，人們逐漸認識到免疫算法具有保持解群分布多樣性的特征，從而克服了一般尋優過程易陷入局部最優解的缺點. 在抗原的選擇下，抗體與抗原的親和力呈現不斷增加的趨勢，最終能夠產生對付抗原的最有效的抗體. 從問題求解的角度而言，如果將抗體看作問題的解，免疫優化的過程就是一個不斷尋求最大親和力解的過程. 免疫算法被大量應用于求解各類選址問題[15-17]，但還沒有將其應用于求解電動汽車充電站選址問題.

本文引入免疫算法思想并加以改進，使其適合電動汽車充電站選址問題的求解，算法流程圖如圖2所示. 如果將免疫算法與電動汽車充電站選址問題的一般搜索算法相比較，那么抗原、抗體、抗原和抗體的親和力分別對應于目標函數和約束、可行解、可行解與目標函數的匹配度.

圖2 改進免疫算法流程圖Fig.2 Flow chart of improved immune algorithm

3.1 編碼與初始抗體產生

每個選址方案可形成一個長度為p的抗體，每個抗體代表被選為充電站的候選點序列. 例如，考慮m個候選點選取p個點的充電站選址問題，假設1， 2， …，m代表候選點的序號，那么抗體[i1，i2， …，ip]代表一個可行選址方案，它表示[i1，i2， …，ip]被選為充電站，其中i1，i2， …，ip代表1， 2， …，n中不重復的p個序號.為增加抗體的多樣性，初始抗體通過洗牌方式隨機產生.

3.2 親和力計算

親和力包括抗體與抗原的親和力Av以及抗體與抗體的親和力Sv， s.

(1) 抗體與抗原親和力Av表示抗體與抗原的匹配程度. 對于電動汽車充電站選址問題而言：

(10)

式中：Fv為目標函數，其取值范圍為[0， 1]，因此Av的取值范圍也為[0， 1].Av值越小，抗體與抗原的匹配程度越高；反之，Av值越大，抗體與抗原的匹配程度越低.

(2) 抗體與抗體的親和力Sv， s表示抗體之間的相似程度，以百分比表示. 對電動汽車充電站選址問題來而言

(11)

式中：kv， s為抗體v和抗體s中相同候選點的個數；p為抗體長度.

3.3 抗體濃度計算與記憶細胞庫更新

抗體濃度cv是指群體中相似抗體所占的百分數，即

(12)

在計算過程中，當一種抗體的濃度cv超過設定的閾值T時，表明該抗體在群體中占據了較大優勢，到達了一個局部最優解，這時生成一個記憶細胞來記錄此局部最優解. 如果記憶細胞庫已滿，則與抗原親和力最低的記憶細胞被新產生的具有較高親和力的記憶細胞取代. 記憶細胞同時也是抑制細胞，對那些與記憶細胞有較高親和力的抗體產生抑制作用，使其生存力降低，以保證免疫算法不會陷入局部最優解.

3.4 期望繁殖概率計算

抗體與抗原間親和力Av和抗體濃度cv共同決定了種群中每個個體的期望繁殖概率，即

(13)

其中，a為[0， 1]之間的常數.式(13)說明，個體親和力越高、濃度越低，則被選擇繁殖的概率越大；反之，個體親和力越低、濃度越高，則被選擇繁殖的概率越小.

3.5 變異算子

與標準免疫算法不同，變異算子是改進免疫算法的核心算子. 本文設計了兩個變異算子：變異算子1和2.

圖3 變異算子1Fig.3 Mutation operator 1

圖4 變異算子2Fig.4 Mutation operator 2

4 測試與分析

4.1 測試實例

本文設計了電動汽車充電站選址問題的測試實例. 所有需求點的位置在[0， 50 km]×[0， 50 km]的平面內隨機產生，其具體坐標和充電需求量如表2所示.其中，需求點的數量是60個，可以建設充電站的候選點的數量為55個. 現實中的充電站選址，除了考慮用戶充電需求之外，還要考慮實施條件的可能性，例如，符合城市總體規劃和路網規劃、足夠面積的可用土地以及電力負荷等，因此不可能所有候選點都適合建設充電站.為了使測試實例更符合現實情況，從60個需求點中隨機產生5個不適宜建設充電站的點，即坐標(8.13， 26.99)、 (20.87， 41.78)、 (29.10， 30.69)、 (25.66， 28.79)和(25.99， 17.03).要求從候選點中選擇p個點建設充電站，以滿足所有需求點的充電需求，并確定充電站的等級和服務區域.

表2 測試實例數據Table 2 Data of test instance

(續 表)

4.2 測試結果分析

利用Matlab 2014a編寫改進免疫算法來求解電動汽車充電站選址測試實例.參數設置：種群規模為50，迭代次數為100次，變異概率為0.5，電動汽車用戶滿意度臨界值Li=3，Ui=15，親和力閾值T=70%.對每個測試結果都是獨立運行30次，取平均值.

不同充電站建設數量對電動汽車用戶平均滿意度的影響如表3所示.從表3中可以看出，隨著充電站建設數量的增加，平均用戶滿意度也在增加，當然充電站的建設成本也會隨著增加.選擇合適的充電站數量，需要同時考慮財政預算和用戶滿意度，不同的決策者會得出不同的結論.本文中，選擇建設9個電動汽車充電站，此時的平均用戶滿意度是85.25%， 充電站建站位置、等級及服務區域如表4和圖5所示.

表3 充電站數量與平均用戶滿意度Table 3 Quantity of recharging stations and the average users’ satisfaction

表4 充電站建站位置、等級及服務區域Table 4 Locations， grades and service regions of recharging stations

圖5 充電站建站位置及服務區域Fig.5 Locations and service regions of recharging stations

標準免疫算法和改進免疫算法的收斂曲線圖如圖6所示.從圖6可以看出，改進免疫算法優于標準免疫算法.標準免疫算法在60次迭代之后才收斂到最優解，而改進免疫算法在30多次迭代之后就收斂到最優解，且收斂結果更好.對比結果表明，改進免疫算法既保持了標準免疫算法全局搜索性的特點，又增加了局部搜索能力，使其能夠更好、更快地找到最優解.

(a) 標準免疫算法

(b) 改進免疫算法 圖6 標準免疫算法和改進免疫算法收斂曲線Fig.6 Convergent curves based on immune algorithm and improved immune algorithm

5 結 語

本文研究了基于滿意優化的電動汽車充電站選址問題，引入了充電站等級概念，提出了電動汽車用戶滿意度評價函數，建立了以用戶滿意度為目標函數的電動汽車充電站選址問題的混合整數規劃模型. 為了求解該模型，提出了基于免疫算法的求解算法，設計了新的變異算子，既可以使解群中優勢個體得以保留并快速收斂于最優解，又可以產生差異較大的新個體，保持解群中的個體多樣性，防止出現早熟現象. 測試結果表明，本文提出的模型求解算法具有良好的尋優能力及收斂性能，能夠滿足實際電動汽車充電站選址問題的應用需求.

[1] WANG H， HUANG Q， ZHANG C， et al. A novel approach for the layout of electric vehicle charging station[C]// International Conference on Apperceiving Computing and Intelligence Analysis. IEEE， 2010：64-70.

[2] 劉志鵬，文福拴，薛禹勝，等.電動汽車充電站的最優選址和定容[J].電力系統自動化，2012， 36(3)：54-59.

[3] 王輝，王貴斌，趙俊華，等.考慮交通網絡流量的電動汽車充電站規劃[J].電力系統自動化，2013，37(13)：63-69.

[4] WANG Y W， WANG C R. Locating passenger vehicle refueling stations[J]. Transportation Research Part E， 2010， 46(5)：791-801.

[5] WANG Y W. Locating flow-recharging stations at tourist destinations to serve recreational travelers[J]. International Journal of Sustainable Transportation， 2011， 5(3)：153-171.

[6] WANG Y W， LIN C C. Locating multiple types of recharging stations for battery-powered electric vehicle transport[J]. Transportation Research Part E：Logistics and Transportation Review， 2013， 58(16)：76-87.

[7] YOU P S， HSIEH Y C. A hybrid heuristic approach to the problem of the location of vehicle charging stations[J]. Computers & Industrial Engineering， 2014，70(2)：195-204.

[8] 馮超，周步祥，林楠，等.電動汽車充電站規劃的多種群混合遺傳算法[J].電力系統及其自動化學報，2013，25(6)：123-129.

[9] YANG J， SUN H. Battery swap station location-routing problem with capacitated electric vehicles[J]. Computers & Operations Research， 2015， 55：217-232.

[10] JERNE N K. Towards a network theory of the immune system[J]. Annual Immunology， 1974， 125(1/2)：373-389.

[11] 王磊，潘進，焦李成.免疫算法[J].電子學報，2000，28(7)：74-78.

[12] 蔡自興，龔濤.免疫算法研究的進展[J].控制與決策，2004，19(8)：841-846.

[13] 謝克明，郭紅波，謝剛，等.人工免疫算法及其應用[J].計算機工程與應用，2005，41(20)：77-80.

[14] DASGUPTA D， YU S H， NINO F. Recent advances in artificial immune systems： models and applications[J]. Applied Soft Computing， 2011(11)：1574-1587.

[15] MA J J， WANG Y L， LIU Y. Size and location of distributed generation in distribution system based on immune algorithm[J]. Systems Engineering Procedia， 2012(4)： 124-132.

[16] 朱思峰，陳國強，張新剛，等.多目標優化量子免疫算法求解基站選址問題[J].華中科技大學學報(自然科學版)，2012，40(1)：49-53.

[17] 淦艷，魏延，楊有.免疫算法在帶權值的物流配送中心選址中的應用[J].重慶師范大學學報(自然科學版)，2015，32(5)：107-113.

[18] 馬云峰，楊超，張敏，等.基于時間滿意的最大覆蓋選址問題[J].中國管理科學，2006，14(2)：45-51.

[19] 李菱，李燕青，姚玉海，等.基于遺傳算法的電動汽車充電站的布局規劃[J].華東電力，2011，39(6)：1004-1006.

[20] 劉自發，張偉，王澤黎.基于量子粒子群優化算法的城市電動汽車充電站優化布局[J].中國電機工程學報，2012， 32(22)：39-45.

[21] 加鶴萍，謝勝利，邵翔，等.基于模擬退火算法的城市電動汽車充電站優化布局[J].山西電子技術，2013(3)：26-27.

[22] 趙書強，李志偉.基于差分進化粒子群算法的城市電動汽車充電站最優規劃[J].華北電力大學學報(自然科學版)，2015，42(2)：1-7.

LocationofElectricVehicleRechargingStationsBasedonSatisfactoryOptimization

JIAYongji，XINGFangfang

(Glorious Sun School of Business and Management， Donghua University， Shanghai 200051， China)

Location of electric vehicle recharging stations is the primary issue to promote the usage of electric vehicles. Based on satisfactory optimization theory， the evaluation function of electric vehicle users’ satisfaction is proposed. By introducing the conception of multi-grade of recharging stations， a mixed integer programming model on location of multi-grade electric vehicle recharging stations is developed， and its objective function is to maximize the average electric vehicle users’ satisfaction. And an algorithm based on immune algorithm is proposed to solve this model. The test results show that the proposed model can effectively determine the locations， grades and the service regions of the recharging stations， and the algorithm is quick and effective.

satisfactory optimization； electric vehicle； recharging stations location； immune algorithm

1671-0444(2017)05-0739-07

2016-06-29

國家自然科學基金資助項目(71371045)；教育部人文社科青年基金資助項目(13YJC630159)；中央高校基本科研業務費專項資金資助項目(16D110815)

賈永基(1976—)，男，山東煙臺人，副教授，博士，研究方向為物流系統建模與優化.E-mail：yjjia@dhu.edu.cn

U 469.72

A

(責任編輯：楊靜)