基于免疫算法的電動(dòng)自行車充電樁選址研究

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

（遼寧科技大學(xué)理學(xué)院，遼寧 鞍山 114051）

1 引言

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

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

2 模型建立

2.1 需求分析

通過對(duì)居民的電動(dòng)自行車充電需求的問卷調(diào)研，可知我國(guó)南方大部分區(qū)域每個(gè)家庭大多會(huì)配備1到2輛電動(dòng)自行車，且電動(dòng)自行車每次充電時(shí)長(zhǎng)與車輛行駛距離、電池容量等因素有關(guān)，每天充電的電動(dòng)自行車數(shù)量相對(duì)固定，使用者通常會(huì)選擇距離500米范圍內(nèi)公共充電站。

2.2 模型假設(shè)

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

(1)每個(gè)需求點(diǎn)都可以成為建站點(diǎn)；

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

(3)不考慮充電站的建設(shè)等級(jí)，每個(gè)充電站的充電樁規(guī)格相同，服務(wù)能力無差異；

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

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

2.3 模型建立

其中m：需求點(diǎn)的個(gè)數(shù)；n：實(shí)際充電樁安裝數(shù)量；dij：表示車輛從充電站i到充電站j的距離；Dj：表示需求點(diǎn)i可接受的最大服務(wù)距離；Ni：在第i個(gè)充點(diǎn)電服務(wù)的車輛數(shù)量；Xi：0-1決策變量，Xi=1表示第i個(gè)候選充電站投入建設(shè)；Xi=0表示第i個(gè)候選充電站不投入建設(shè)；pi：充電站i安裝充電樁的個(gè)數(shù)；Ci:第i個(gè)充電站基礎(chǔ)設(shè)施建設(shè)成本；C：?jiǎn)挝怀潆姌栋惭b、維護(hù)成本；(1)式為目標(biāo)函數(shù)表示充電站總成本最小，第一個(gè)表達(dá)式表示基礎(chǔ)建設(shè)總成本；第二個(gè)表達(dá)式表示充電樁安裝、維護(hù)成本；(2)(3)式為約束條件，(2)式表示每個(gè)需求點(diǎn)在可接受距離范圍內(nèi)至少有一個(gè)充電站為其服務(wù)；(3)式表示在第i個(gè)充電站接收服務(wù)的車輛都能滿足充電需求。

3 基于免疫算法求解模型

免疫算法是根據(jù)人體免疫系統(tǒng)的作用機(jī)理而形成的一種新型的智能優(yōu)化算法[10]，具有并行性、全局收斂性、自適應(yīng)性等特點(diǎn)。

3.1 編碼方式

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

3.2 多樣性評(píng)價(jià)

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

(2)抗體v-抗體t的親和力：，其中kv,t表示抗體v-抗體t中相同的數(shù)字的個(gè)數(shù)，即可行解v,t中有幾個(gè)相同的電動(dòng)自行車充電站建站點(diǎn)，L表示抗體的長(zhǎng)度；

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

β為多樣性評(píng)價(jià)參數(shù)。

3.3 免疫操作

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

(2)采用單點(diǎn)交叉進(jìn)行交叉操作；

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

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

表1 免疫算法

4 仿真實(shí)驗(yàn)與分析

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

表2 需求點(diǎn)信息

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

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

圖1 免疫算法收斂曲線圖

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

圖2 選址充電方式一

圖3 選址充電方式二

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

圖4 免疫算法收斂曲線

圖5 選址充電方式

此時(shí)最小成本為109000元，從圖5可以看出建站點(diǎn)為1、7、6需求點(diǎn)，其1，2需求點(diǎn)同時(shí)在1號(hào)站接收服務(wù)，3、5、6在6號(hào)站接收服務(wù)，其余的在7號(hào)站接收服務(wù)。

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

5 結(jié)語

針對(duì)電動(dòng)自行車實(shí)際充電情況，引入了充電需求滿足系數(shù)α，建立了以滿足充電需求條件下，企業(yè)最小成本為目標(biāo)的數(shù)學(xué)模型，并利用基本免疫算法對(duì)所提模型進(jìn)行求解，仿真實(shí)驗(yàn)表明本文建立的數(shù)學(xué)模型，能夠客觀描述電動(dòng)自行車充電特點(diǎn)，設(shè)計(jì)的算法較為簡(jiǎn)單，具有很好的收斂性。對(duì)企業(yè)來說，適當(dāng)增加充電插頭，可以降低成本，提高利潤(rùn)。