電動(dòng)自行車充電樁安裝優(yōu)化分配方法研究

楊玉林 肖磊 楊麗 李世隆 高黨尋 秦海鵬

（1.江蘇師范大學(xué)電氣工程及自動(dòng)化學(xué)院，江蘇徐州 221116；2.中國自行車協(xié)會(huì)，北京 100079；3.清華大學(xué)基礎(chǔ)工業(yè)訓(xùn)練中心，北京 100084）

為了充電安全，保證電動(dòng)自行車不在室內(nèi)充電，很多地方在室外安裝了充電樁，但是在使用的過程中，出現(xiàn)了諸多問題，比如，部分充電樁使用率低，充電樁安裝的數(shù)量過多或者過少，導(dǎo)致資源浪費(fèi)或不足等。這些問題多是由充電樁安裝初期評估不到位，安裝位置和安裝數(shù)量沒有進(jìn)行合理評價(jià)而導(dǎo)致的。因此，為了提高使用率，有必要針對電動(dòng)自行車充電樁的安裝進(jìn)行優(yōu)化分配，保證成本和用戶滿意度最大化。

用戶的使用率最高，成本使用最低，以及用戶滿意度最大化，對上述三個(gè)指標(biāo)求其最值，這本身就是一個(gè)優(yōu)化問題，需要給出滿足上述指標(biāo)的最優(yōu)方案。因此，建立上述問題的數(shù)學(xué)模型，然后基于該模型進(jìn)行優(yōu)化求解，從而給出一個(gè)較優(yōu)的充電樁安裝方案。

1 充電樁安裝數(shù)學(xué)模型

為了獲得充電樁安裝的最優(yōu)方案，首先需要對問題進(jìn)行建模，也即，將上述三個(gè)指標(biāo)采用數(shù)學(xué)公式表述出來。為了方便建模，以圖1 的安裝場景為例，假設(shè)充電樁的位置（取該充電樁的中心位置）為(xi,yi)，若有N 個(gè)充電樁，則所有N個(gè)的充電樁位置可以表示為Pos={(x1,y1),(x2,y2),…,(xN,yN)}，這N個(gè)充電樁的個(gè)數(shù)可以分別表示為Num={S1,S2,…,SN}，那么，本文需要解決的問題是，在已知環(huán)境周圍有的充電樁信息，進(jìn)一步安裝新的充電樁，給出新的充電樁位置和數(shù)量，從而保證成本最低，利用率最高，從而保證用戶滿意度最大化。

圖1 充電樁安裝環(huán)境

1.1 充電樁數(shù)量確定

為了簡化求解過程，首先確定充電樁的個(gè)數(shù)，然后進(jìn)一步確定充電樁的位置。容易知道，充電樁的多少，和人流量以及電動(dòng)自行車的數(shù)量有關(guān)，甚至和周圍的岔路口的數(shù)量有關(guān)，更重要的是，還和周圍充電樁的數(shù)量有關(guān)?；诖?，本文考慮上述因素，構(gòu)造關(guān)于充電樁數(shù)量的計(jì)算公式，具體如公式（1）所示。

其中，f1(person)表示與人流量相關(guān)的函數(shù)，f2(Ebike)表示與電動(dòng)車總數(shù)的函數(shù)，上述兩項(xiàng)的計(jì)算則需要根據(jù)歷史數(shù)據(jù)采用預(yù)測的方法來求?。坏谌?xiàng)表示限定的周圍環(huán)境中充電樁的平均個(gè)數(shù)；ε、ρ為一個(gè)[0,1]之間的參數(shù)，兩個(gè)參數(shù)的值均需根據(jù)實(shí)際情況和經(jīng)驗(yàn)確定；NC表示岔路口的個(gè)數(shù)。

充電樁的個(gè)數(shù)與安裝成本成正比，因此，為了獲取安裝成本最低的方案，則需要求取F1的最小值。

1.2 充電樁位置的確定

為了求取滿足上述三個(gè)指標(biāo)的充電樁安裝位置，設(shè)充電樁的安裝位置為(x,y)，為了滿足充電的利用率最高，則需要綜合考慮周邊所有充電樁的位置和數(shù)量，因此，本文中的充電樁利用率采用公式（2）來表示，具體如下：

其中，Num+1 表示限定區(qū)域中所有充電樁的個(gè)數(shù)，dj(x,y)表示需要安裝的充電樁到第j個(gè)已安裝充電樁的距離，j=1,2,…,Num。

充電樁的安裝位置選定的主要因素是均衡化充電樁的利用率，從而避免利用率太低或者太高的情況，從而提高用戶滿意度，因此，本文中需要求取F2的最大值。

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

考慮到上述兩個(gè)因素，因此，構(gòu)建本文所求問題的數(shù)學(xué)模型如公式（3）所示：

其中，第一個(gè)函數(shù)采用100 減去F1，其原因是一次充電樁安裝的最大個(gè)數(shù)不會(huì)超過20 個(gè)，且上述操作是為了方便求取兩個(gè)值的最大值。

2 求解方法

上述問題是一個(gè)多目標(biāo)優(yōu)化問題，本文采用加權(quán)的方式將其轉(zhuǎn)化為一個(gè)單目標(biāo)問題，如公式（4）所示：

其中，a與b為權(quán)重，且a+b=1。

針對上述問題也產(chǎn)生了許多求解方法，如窮舉法、分支定界法，割平面法、啟發(fā)式算法等。啟發(fā)式算法目前是運(yùn)用最為廣泛的一類求解方法，這類算法雖然不一定能求到最優(yōu)解，但可以在較短的時(shí)間內(nèi)得到令人滿意的次優(yōu)解。因此，本文所求的模型，可以采用諸如微粒群優(yōu)化算法（PSO）[1-2]、遺傳算法（GA）[3]、蟻群算法（ACO）[4]、模擬退火算法（SA）[5]、自適應(yīng)大規(guī)模鄰域搜索算法（ALNS）[6]等方法來求解。其中較為常用的是PSO，GA 以及ALNS 算法。

微粒群優(yōu)化算法是一種基于種群的隨機(jī)優(yōu)化技術(shù)，1995 年由R.C.Eberhart 和J.Kennedy 二人共同提出[7]。算法的靈感來源于一群覓食的飛鳥，所有飛鳥都不知道食物的具體位置，但是可以根據(jù)自己的判斷獲取和食物之間的距離。整個(gè)鳥群可以共享各自與食物之間的距離信息，從而向距離食物最近鳥的周邊區(qū)域進(jìn)行搜尋，最終找到食物。PSO 算法根據(jù)上述方式來尋找最優(yōu)解，其計(jì)算流程如圖2 所示。

圖2 PSO 算法流程

遺傳算法的原理是以一個(gè)種群中的所有個(gè)體為對象，每個(gè)個(gè)體之間的差異化主要體現(xiàn)在對應(yīng)的染色體編碼的不同。在產(chǎn)生了初始種群之后，根據(jù)適者生存，優(yōu)勝劣汰的原則，種群會(huì)不斷地演化繁衍并趨向于更優(yōu)的解。該算法主要的步驟是：在每一代種群中，根據(jù)個(gè)體適應(yīng)度大小選出相應(yīng)的個(gè)體進(jìn)行下一步操作。然后借助自然遺傳學(xué)中的遺傳算子進(jìn)行交叉和變異，產(chǎn)生新的個(gè)體。適應(yīng)度高的個(gè)體，對應(yīng)更優(yōu)的解。這個(gè)過程同種群自然進(jìn)化一樣，后代種群比前一代或幾代種群適應(yīng)環(huán)境的能力更強(qiáng)。因此，迭代結(jié)束后種群中的最優(yōu)個(gè)體經(jīng)過解碼后，可以視作問題的最優(yōu)解。GA 算法具體的算法步驟如圖3 所示。

圖3 GA 算法流程

ALNS 算法的實(shí)質(zhì)是在每一次鄰域搜索的時(shí)候都會(huì)變換鄰域，從而增加搜索空間的廣度。ALNS 算法將單一的移除和插入算子拓展成一組移除算子和一組插入算子集合。第一次迭代計(jì)算的時(shí)候，隨機(jī)選擇一個(gè)移除算子和插入算子來進(jìn)行鄰域搜索。在每一次的迭代計(jì)算結(jié)束后都會(huì)根據(jù)產(chǎn)生解的質(zhì)量來給當(dāng)前移除和插入算子進(jìn)行評分。在隨后的迭代計(jì)算中，移除和插入算子被選中的概率由其在之前的計(jì)算中累積的分?jǐn)?shù)來決定。ALNS 算法會(huì)根據(jù)鄰域解的優(yōu)劣，自行調(diào)整鄰域搜索操作。當(dāng)獲得了較優(yōu)的鄰域解后，算法會(huì)采取一定的策略接受該鄰域解，如禁忌搜索接受準(zhǔn)則[8]、模擬退火接受準(zhǔn)則[9]、貪心接受準(zhǔn)則[10]等。基本ALNS 算法的步驟如圖4 所示。

圖4 ALNS 算法流程

采用上述三種方法，人為確定公式（4）中參數(shù)，則可以得到充電樁安裝的數(shù)量和位置。

3 結(jié)束語

本文給出了電動(dòng)自行車充電樁安裝優(yōu)化分配的數(shù)學(xué)模型，并給出三種方法來求解構(gòu)建的數(shù)學(xué)模型。但是上述方法還存在需要改進(jìn)的地方，比如，人流量和車流量的預(yù)測，需要根據(jù)大數(shù)據(jù)歷史信息來進(jìn)行預(yù)測，從而來保證模型的精確性；本文將雙目標(biāo)改成單目標(biāo)，對權(quán)重的設(shè)置還需要人為來調(diào)參，有必要給出雙目標(biāo)求解方法，這些都是本文作者后期需要解決的問題。此外，將人工神經(jīng)網(wǎng)絡(luò)融入到本文問題的求解，也是一個(gè)需要考慮的研究方向。