基于免疫算法的電動自行車充電樁選址研究

楊佳奇 陳志濤 劉育源 肖靜瑩 王潔 熊 焱

（遼寧科技大學理學院，遼寧 鞍山 114051）

1 引言

因價格便宜，使用方便，電動自行車作為短途交通的代步工具深受人們的喜愛。截至2021年，我國電動自行車年銷售量為3000萬輛，社會保有量達3億輛，并按每年30%的速度快速增長。伴隨而來的不規范電引發的火災等安全事故也屢見不鮮，因此建立社區內公共充電樁滿足刻不容緩。如何合理對公共充電樁選址布局，滿足居民充電需求，實現區域電動自行車的安全集中停放和充電，是社區、消防等部門急需解決的社會問題。

電動車充電問題不僅直接關系到使用者的安全、滿意度，還與環保、節能等社會問題相關。目前針對電動汽車充電站選址問題研究比較充分，主要從使用者角度如距離滿意度[1,2]、覆蓋需求等[3]，從投資者角度如建設成本、用戶用電成本等[4]，或者從決策評價角度[5,6]進行研究。電動自行車方面研究主要集中在共享單車停靠選址研究。Saharidis等[7]在考慮投資預算約束下，以最小化用戶行走時間和未滿足的停、取車需求為目標，建立公共自行車停車點選址和車輛及停車樁配置決策的多時段優化模型。由于電動自行車和電動汽車、共享單車停靠環境和充電方式等方面的差異，不能直接搬運套用適用于電動汽車的充電樁選址問題的研究成果，需要結合電動自行車充電實際進行研究。選址問題是一個組合優化問題，屬于NP-hard問題，其求解方法主要有如遺傳算法[8]、粒子群算法[9]等。免疫算法是（Immune Algorithm，IA）作為一種具有全局搜索能力的智能算法，能夠解決進化過程中出現的局部最優解的問題，被廣泛應用在經典優化問題中[10]。結合區域電動自行車分布情況，考慮充電站的覆蓋率和電動自行車實際充電特點，本文建立了在滿足居民充電距離和頻次約束下的以建設總成本最小為目標的電動自行車充電站選址模型，并采用免疫算法對其求解，仿真結果表明方法是可行有效的。

2 模型建立

2.1 需求分析

通過對居民的電動自行車充電需求的問卷調研，可知我國南方大部分區域每個家庭大多會配備1到2輛電動自行車，且電動自行車每次充電時長與車輛行駛距離、電池容量等因素有關，每天充電的電動自行車數量相對固定，使用者通常會選擇距離500米范圍內公共充電站。

2.2 模型假設

同一需求點的所有車輛在同一時間段同時充電的概率很小，為保證同一需求點需要充電車輛在一天內都可以充電，引入充電需求滿足系數a。定義為ti表示第i個需求點車輛平均充電時間（小時），0≤a≤1。在調研基礎上，依據居民電動自行車充電最大服務距離、頻次需求和區域場地條件，將整個服務區域劃分為若干個需求點和備選點，并假設滿足如下條件：

(1)每個需求點都可以成為建站點；

(2)每個備選點都滿足居民充電需求且符合建設安全要求；

(3)不考慮充電站的建設等級，每個充電站的充電樁規格相同，服務能力無差異；

(4)需求點也是建站備選點，若第i個需求點建站，則該需求點的用戶到站距離為0；

(5)若第i個需求點未被選址，則其用戶可由與其距離小于可接受距離的另一個建站點j服務。

2.3 模型建立

其中m：需求點的個數；n：實際充電樁安裝數量；dij：表示車輛從充電站i到充電站j的距離；Dj：表示需求點i可接受的最大服務距離；Ni：在第i個充點電服務的車輛數量；Xi：0-1決策變量，Xi=1表示第i個候選充電站投入建設；Xi=0表示第i個候選充電站不投入建設；pi：充電站i安裝充電樁的個數；Ci:第i個充電站基礎設施建設成本；C：單位充電樁安裝、維護成本；(1)式為目標函數表示充電站總成本最小，第一個表達式表示基礎建設總成本；第二個表達式表示充電樁安裝、維護成本；(2)(3)式為約束條件，(2)式表示每個需求點在可接受距離范圍內至少有一個充電站為其服務；(3)式表示在第i個充電站接收服務的車輛都能滿足充電需求。

3 基于免疫算法求解模型

免疫算法是根據人體免疫系統的作用機理而形成的一種新型的智能優化算法[10]，具有并行性、全局收斂性、自適應性等特點。

3.1 編碼方式

每個抗體代表一個可行的電動自行車充電站選址方案，根據本文建模特點，采用字符編碼方式，如有6個電動自行車需求點建立充電站的問題，1，2，…，6表示需求點序號，從中選出4個需求點建設充電站，抗體v=[6 4 3 1]表示在第6、4、3、1需求點建電動自行車充電站。

3.2 多樣性評價

(1)抗體v-抗原親和力：，當抗體v滿足約束條件時，其親和力Fv等于該抗體對應的充電站總成本，即對應的(1)式的值，否則等于一個很大的數C，本文中為2*e+5；

(2)抗體v-抗體t的親和力：，其中kv,t表示抗體v-抗體t中相同的數字的個數，即可行解v,t中有幾個相同的電動自行車充電站建站點，L表示抗體的長度；

(4)抗體v的期望繁殖率pv：由抗體與抗原之間的親和力和抗體間的濃度共同決定，即

β為多樣性評價參數。

3.3 免疫操作

(1)采用輪盤賭選擇機制進行選擇操作，選擇概率即為（4）式計算得出的期望繁殖概率；

(2)采用單點交叉進行交叉操作；

(3)隨機選擇變異位變異。

免疫算法具體操作步驟如表1所示。

表1 免疫算法

4 仿真實驗與分析

實驗數據來源于江西省上饒市某封閉小區。該小區占地面積約為16萬平方米，包括多層、小高層及高層住宅，約有1000戶居民。根據調研該小區的每天需要充電電動自行車車數量、分布、充電站所含充電樁個數等信息由表2給出。

表2 需求點信息

根據本文提出的選址模型，按照免疫算法進行仿真求解。實驗環境為Intel(R)Core i5-8400 CPU@2.80GH在，16GB內存，操作系統為64位Windows 10，使用Matlab2016b進行編程。算法參數分別為：種群規模100，記憶庫容量20，迭代次數Maxgen=100，交叉概率0.1，變異概率0.4，多樣性評價參數0.95，c=500元。

最大服務距離為500米、滿足系數α=0.125時，免疫算法的收斂曲線如圖1所示。

圖1 免疫算法收斂曲線圖

從圖1可以看出，免疫算法在求解本模型整體來說是收斂的，此時最小成本為133500元。此時在1、5、6號需求點建站，使用者共有兩種充電選擇，第一種如圖2所示：1號需求點建站，只對自己服務，4、7、8需求點在5號需求點接收服務，2、3需求點在6號站點接收服務；第二種：1號仍只為自己服務，2、4、7號需求點在5號需求的服務，6號還為3、8號需求點服務。也就是說對2、8號需求點來說，與5、6號充電站距離都在最大服務距離范圍內，可選擇性更多，被服務機會更大。

圖2 選址充電方式一

圖3 選址充電方式二

當最大服務距離為500米，α=0.1時，免疫算法的收斂曲線及得選址充電方式如圖4和圖5所示。

圖4 免疫算法收斂曲線

圖5 選址充電方式

此時最小成本為109000元，從圖5可以看出建站點為1、7、6需求點，其1，2需求點同時在1號站接收服務，3、5、6在6號站接收服務，其余的在7號站接收服務。

上述仿真結果表明：免疫算法在求解模型時收斂，而且能夠較快地收斂到最優解。當最大距離不變時，充電需求滿足系數α越小，即電動自行車充電時間越短，充電樁利用率越高，企業成本越小。在滿足約束條件下，在含有充電樁個數多的需求點建站的可能性大一些。

5 結語

針對電動自行車實際充電情況，引入了充電需求滿足系數α，建立了以滿足充電需求條件下，企業最小成本為目標的數學模型，并利用基本免疫算法對所提模型進行求解，仿真實驗表明本文建立的數學模型，能夠客觀描述電動自行車充電特點，設計的算法較為簡單，具有很好的收斂性。對企業來說，適當增加充電插頭，可以降低成本，提高利潤。