李偉斌，吳 芳，張 燕

(蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，蘭州 730070)

近年來，隨著大數(shù)據(jù)、云計(jì)算、人工智能等高科技的快速進(jìn)步，共享經(jīng)濟(jì)給中國的經(jīng)濟(jì)發(fā)展注入了新鮮的血液.共享電動(dòng)汽車推動(dòng)著共享經(jīng)濟(jì)的高速發(fā)展，共享電動(dòng)汽車對于緩解大城市交通擁堵、保護(hù)環(huán)境、節(jié)約能源方面有著重要意義.但在其發(fā)展中面臨著如下問題，共享汽車基礎(chǔ)設(shè)施不足，租賃網(wǎng)點(diǎn)較少且布局不合理，無法滿足顧客租車需求.本文將通過優(yōu)化網(wǎng)點(diǎn)布局，在規(guī)劃建設(shè)階段制定更優(yōu)可選擇方案，從而實(shí)現(xiàn)共享電動(dòng)汽車系統(tǒng)資源的合理開發(fā)和使用.

國內(nèi)外部分學(xué)者對電動(dòng)汽車選址進(jìn)行研究，并取得了一定的成果，如Erdogan等[1]提出了一種建設(shè)性的基于中值定理的精確分支切割算法，用于優(yōu)化處理選址問題.Correia等[2]基于混合整數(shù)規(guī)劃模型，考慮所有收入和成本的情況下使共享汽車企業(yè)的利潤最大化.鄭建國等[3]基于混合整數(shù)規(guī)劃模型提出了一種充電站的容量和服務(wù)范圍內(nèi)的需求量相適應(yīng)的方法，并進(jìn)行了模擬仿真測試方法的松弛度和性能.以上學(xué)者采用了精確求解算法求解選址問題.Frade等[4]構(gòu)造了最大化滿足顧客需求的選址模型，以可用預(yù)算為約束條件，利用優(yōu)化算法求解租賃系統(tǒng)的選址問題.Avella等[5]通過提出拉格朗日定理的P中值模型的新啟發(fā)式算法實(shí)現(xiàn)達(dá)到盡量減少設(shè)施數(shù)量的目的.馬作浩[6]引入共享電動(dòng)汽車低碳和懲罰的市場特征網(wǎng)點(diǎn)前期選址的相關(guān)決策因素，基于P中值思想設(shè)計(jì)了多目標(biāo)模型.楊宇[7]構(gòu)建基于P中值的組合分配模型，對基于需求的單一判斷模型和基于成本的分配模型結(jié)合后求解，得出車輛分配方案.馬群[8]采用遺傳算法進(jìn)行求解租賃網(wǎng)點(diǎn)布設(shè)方案和車輛投放方案.創(chuàng)新地開發(fā)了網(wǎng)點(diǎn)布設(shè)仿真系統(tǒng)，輸入?yún)?shù)可直接求解出網(wǎng)點(diǎn)的布設(shè)和投放方案.盧婷等[9]從三個(gè)角度考慮了網(wǎng)點(diǎn)選址影響因素，考慮相關(guān)約束條件情況下，利用遺傳算法進(jìn)行求解多目標(biāo)多約束的網(wǎng)點(diǎn)選址模型.吳陽等[10]以居民出行距離最短和網(wǎng)點(diǎn)數(shù)量較少為目標(biāo)函數(shù)，并以網(wǎng)點(diǎn)的覆蓋范圍、行駛距離等作為約束條件，建立了網(wǎng)點(diǎn)布局優(yōu)化模型，利用改進(jìn)遺傳算法對模型進(jìn)行求解.楊新渥等[11]建立考慮用戶利益和社會(huì)投資的雙層規(guī)劃模型，采用了模擬退火算法求出最優(yōu)解.閆天澤等[12]建立了車流信息及用戶成本的電動(dòng)汽車充電站最優(yōu)規(guī)劃模型，對傳統(tǒng)粒子群算法引入模擬退火思想求解模型.

從研究現(xiàn)狀可知，其主要使用精確求解算法和啟發(fā)式算法模型求解的理論和方法.精確求解算法需遍歷出所有可行解，計(jì)算量大且效率較低；啟發(fā)式算法中傳統(tǒng)遺傳算法具備快速隨機(jī)搜索能力，但是傳統(tǒng)遺傳算法有易早熟、局部搜索能力差問題.而免疫優(yōu)化算法通過其維持機(jī)制和多樣性產(chǎn)生的特點(diǎn)來保證群體的多樣性，能夠解決多數(shù)尋優(yōu)過程尤其是多峰函數(shù)尋優(yōu)過程中的“早熟”問題，最終求得全局最優(yōu)解；免疫算法對抗體的評(píng)價(jià)較為全面，其選擇抗體的方式也更加合理；免疫算法中還對抗體產(chǎn)生鼓勵(lì)或者抑制作用，體現(xiàn)免疫算法的良好自我調(diào)節(jié)功能，從而保證種群的多樣性.基于以上優(yōu)勢，結(jié)合具體問題對算法步驟進(jìn)行設(shè)計(jì)，可得出研究區(qū)域網(wǎng)點(diǎn)的布設(shè)方案，為企業(yè)提供系統(tǒng)的規(guī)劃時(shí)期建議.

1 問題描述

共享電動(dòng)汽車網(wǎng)點(diǎn)選址是解決從多個(gè)候選網(wǎng)點(diǎn)中選擇合適的網(wǎng)點(diǎn)，使得企業(yè)收益最大、出行總距離最少、運(yùn)營成本花費(fèi)最少.由于共享電動(dòng)汽車網(wǎng)點(diǎn)選址過程中有共享電動(dòng)汽車的保有量、站點(diǎn)之間的距離等主要的決策影響因素，為了方便研究科學(xué)性，對模型預(yù)先進(jìn)行如下假設(shè).

1)假設(shè)各個(gè)備選網(wǎng)點(diǎn)的位置、企業(yè)計(jì)劃投入的車輛數(shù)、土地價(jià)格、汽車購置費(fèi)、單位距離調(diào)度單價(jià)均已知；

2)假設(shè)所有共享網(wǎng)點(diǎn)的電動(dòng)汽車只有一類汽車，充滿電的行駛里程能達(dá)到100%發(fā)揮，電池不發(fā)生電量損耗；

3)假設(shè)在運(yùn)營中，共享電動(dòng)汽車企業(yè)總能通過車輛調(diào)度滿足顧客的需求，完全覆蓋距離內(nèi)不產(chǎn)生懲罰成本；

4)本文為了計(jì)算更加簡潔明了，暫不考慮共享電動(dòng)汽車?yán)m(xù)航里程、電池電量、網(wǎng)點(diǎn)充電樁數(shù)量等諸多因素.

2 模型建立

2.1 選址過程分析

本文共享電動(dòng)汽車網(wǎng)點(diǎn)選址方案的選擇應(yīng)滿足以下要求，保證企業(yè)的利潤，盡量增大企業(yè)的收益以及減少企業(yè)的運(yùn)營成本；其次為了更好地保證顧客的需求，本文在構(gòu)建共享電動(dòng)汽車網(wǎng)點(diǎn)選址模型時(shí)追求所有網(wǎng)點(diǎn)與到相應(yīng)需求點(diǎn)的距離成本最小.各目標(biāo)函數(shù)如下：

1)企業(yè)總運(yùn)營收益最大.

maxf1=NLM;

(1)

2)網(wǎng)點(diǎn)的固定成本和企業(yè)經(jīng)營成本.

(2)

3)各網(wǎng)點(diǎn)與到相應(yīng)需求點(diǎn)的距離成本.

(3)

式中：f1為總運(yùn)營收益，元；f2為網(wǎng)點(diǎn)的固定成本和經(jīng)營成本，元；f3為各個(gè)網(wǎng)點(diǎn)與到相應(yīng)需求點(diǎn)的距離成本，元；N為一年中運(yùn)營天數(shù)，d；L為企業(yè)計(jì)劃投入共享電動(dòng)汽車數(shù)，輛；M為一輛共享電動(dòng)汽車的日收益，元；a1為網(wǎng)點(diǎn)建設(shè)土地費(fèi)用，元；a2為企業(yè)購置單位共享電動(dòng)汽車費(fèi)用，元；a3為企業(yè)的調(diào)度費(fèi)用，元；a4為企業(yè)的充電費(fèi)用，元；n1為土地建設(shè)費(fèi)用計(jì)費(fèi)周期，a；n2為企業(yè)購置汽車費(fèi)用計(jì)費(fèi)周期，a；μ為單位距離懲罰費(fèi)用，元.

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

本文最后衡量結(jié)果需要將多目標(biāo)函數(shù)歸一化處理為單目標(biāo)函數(shù)，所以本文通過線性加權(quán)方法把三個(gè)多目標(biāo)函數(shù)歸一化處理為最大化的單目標(biāo)函數(shù).本文構(gòu)建的共享電動(dòng)汽車網(wǎng)點(diǎn)選址優(yōu)化模型如下.

目標(biāo)函數(shù)為：

(4)

式中：f為目標(biāo)函數(shù)值；W1為企業(yè)總運(yùn)營收益權(quán)重系數(shù)；W2為固定成本和經(jīng)營成本權(quán)重系數(shù)；W3為距離成本權(quán)重系數(shù)；C取一個(gè)趨近于正無窮的數(shù);

(5)

為懲罰函數(shù)，對于違反距離約束的解給予懲罰.

約束條件為：

(6)

(7)

(8)

(9)

(10)

yij≤xj,i∈I,j∈J;

(11)

xj1·xj2·dj1j2≥d1,j∈J;

(12)

(13)

(14)

式中：n為計(jì)劃建設(shè)網(wǎng)點(diǎn)的數(shù)量；φ為網(wǎng)點(diǎn)最大服務(wù)覆蓋率，%；d1為網(wǎng)點(diǎn)間最小距離，m；d2為網(wǎng)點(diǎn)最大服務(wù)距離，m；dij為網(wǎng)點(diǎn)j到需求點(diǎn)i的距離，m；wij為網(wǎng)點(diǎn)j對需求點(diǎn)i覆蓋程度.

式(4)為模型的目標(biāo)函數(shù)；式(6)～式(14)均為模型的約束條件.其中式(6)表示網(wǎng)點(diǎn)位置選擇的0-1變量；式(7)表示需求點(diǎn)i是否與網(wǎng)點(diǎn)j相連的0-1變量；式(8)保證網(wǎng)點(diǎn)個(gè)數(shù)為n個(gè)；式(9)保證選擇的網(wǎng)點(diǎn)個(gè)數(shù)至少5個(gè)，最多15個(gè)；式(10)保證每個(gè)需求點(diǎn)僅有一個(gè)網(wǎng)點(diǎn)為其服務(wù)；式(11)保證每個(gè)需求點(diǎn)都有相對應(yīng)的網(wǎng)點(diǎn)為其服務(wù)；式(12)保證網(wǎng)點(diǎn)之間的距離必須大于等于d1；式(13)保證網(wǎng)點(diǎn)與其服務(wù)的需求點(diǎn)間的距離必須小于等于d2；式(14)保證網(wǎng)點(diǎn)對其服務(wù)的需求點(diǎn)覆蓋程度不低于預(yù)設(shè)數(shù)值.

3 算法設(shè)計(jì)

本文考慮該網(wǎng)點(diǎn)選址問題的約束條件和目標(biāo)函數(shù)，結(jié)合問題設(shè)計(jì)算法步驟，通過求解模型可得出研究區(qū)域網(wǎng)點(diǎn)的布設(shè)方案，文中算法流程如圖1所示.

圖1 算法流程

3.1 染色體結(jié)構(gòu)設(shè)計(jì)

考慮本文模型特點(diǎn)，對網(wǎng)點(diǎn)選擇采用實(shí)數(shù)編碼.每一個(gè)選址方案可生成一條長度為n的抗體，其中n為網(wǎng)點(diǎn)的個(gè)數(shù)，每個(gè)抗體表示被選為網(wǎng)點(diǎn)的序列.假設(shè)考慮從30個(gè)候選網(wǎng)點(diǎn)中選出8個(gè)網(wǎng)點(diǎn)，則種群中的其中一條抗體[4,15,11,23,2,27,6,19]表示在候選網(wǎng)點(diǎn)4,15,11,23,2,27,6,19處建設(shè)網(wǎng)點(diǎn).

3.2 解的評(píng)價(jià)

3.2.1 抗體濃度

抗體濃度Cν為種群中的相似抗體所占比例，即

(15)

式中：M為種群數(shù)，

(16)

式中：kν,s為抗體ν與抗體s中相同的位數(shù)；L1為抗體的長度.例如，兩個(gè)抗體為[2,5,23,15,14,25,11,3]、[2,11,16,9,7,21,15,25]，其中有4個(gè)相同的值，經(jīng)計(jì)算他們的親和度為0.5，T為預(yù)設(shè)的一個(gè)親和度閾值.

3.2.2 期待繁殖概率

在種群中，每個(gè)抗體的期望繁殖概率P由適應(yīng)度值(即目標(biāo)函數(shù)值f)和抗體濃度Cν兩部分共同決定，其中α為0.95，即

(17)

免疫算法在抑制高濃度抗體時(shí)，適應(yīng)度最高的抗體可能會(huì)因其濃度高受到抑制，從而導(dǎo)致丟失已求得的最優(yōu)值，所以本文采用了精英保留策略，在每次更新種群時(shí)，先將適應(yīng)度最高的若干個(gè)抗體存入記憶庫，再根據(jù)期望繁殖概率將剩余抗體存入記憶庫[13].

3.3 種群更新

3.3.1 選擇

本文采用輪盤賭的選擇機(jī)制進(jìn)行選擇操作，由公式(17)可知，抗體適應(yīng)度的越高，期望繁殖概率越大，則抗體被選擇的概率越大；個(gè)體濃度越大，期望繁殖概率越小，則抗體被選擇的概率越小.這種方法不僅鼓勵(lì)了適應(yīng)度高的抗體，也抑制濃度高的抗體，保證了種群的多樣性.

3.3.2 交叉

本文采用部分匹配交叉(PMX重組)方式，即在種群中隨機(jī)選取一對抗體A和B(父代)，兩個(gè)抗體隨機(jī)選擇一個(gè)相同的交叉點(diǎn)，交換交叉點(diǎn)后兩組基因的位置，得到A1和B1(子代)，抗體交叉過程示意圖如圖2(a)所示.最后進(jìn)行基因沖突檢測，根據(jù)交換的兩組基因建立一個(gè)映射關(guān)系如圖2(b)所示，以6-16-26這一映射關(guān)系為例，可以看到子代A1有相同的基因26，通過映射關(guān)系將交叉點(diǎn)前的基因26轉(zhuǎn)變?yōu)榛?，以此類推至沒有沖突為止.對抗體B1同樣處理，即可得到抗體A2和B2(子代)[14].

圖2 抗體交叉示意圖

3.3.3 變異

本文中免疫算法的抗體變異采用常規(guī)的變異方法，即在基因長度和數(shù)值的取值范圍內(nèi)，隨機(jī)生成1個(gè)變異位置，并隨機(jī)生成一個(gè)基因.然后對抗體進(jìn)行基因沖突操作，若抗體中出現(xiàn)重復(fù)基因，則在原變異位置，重新隨機(jī)生成一個(gè)基因，直到抗體中無重復(fù)的基因，變異操作即可結(jié)束，抗體變異示意圖如圖3所示.

圖3 抗體變異示意圖

4 案例及結(jié)果分析

依據(jù)ArcGIS軟件，找到安寧區(qū)部分學(xué)校、居民小區(qū)、商場、旅游景區(qū)、地鐵站點(diǎn)等共計(jì)30個(gè)共享汽車候選網(wǎng)點(diǎn)，候選網(wǎng)點(diǎn)分布圖如圖4所示.同時(shí)根據(jù)《中國主要城市土地交易情報(bào)》文件，獲取到每個(gè)候選網(wǎng)點(diǎn)2020年的地皮單價(jià)，部分候選點(diǎn)屬性如表1所列.為了方便計(jì)算距離矩陣dij，需要將候選網(wǎng)點(diǎn)的經(jīng)緯度坐標(biāo)轉(zhuǎn)換為二維平面坐標(biāo).模型中網(wǎng)點(diǎn)間最小間距d1為3 km，網(wǎng)點(diǎn)最大服務(wù)距離d2為2 km，網(wǎng)點(diǎn)覆蓋程度預(yù)設(shè)數(shù)值φ為45.0%.通過專家分析法和層次分析法確定的目標(biāo)函數(shù)權(quán)重W1為0.4、W2為0.25和W3為0.35.模型中相關(guān)參數(shù)如表2所列.網(wǎng)點(diǎn)選址過程中的各項(xiàng)成本如表3所列.

圖4 候選網(wǎng)點(diǎn)分布圖

表1 部分候選點(diǎn)屬性

表2 模型相關(guān)參數(shù)

表3 模型參數(shù)設(shè)置

免疫算法相關(guān)參數(shù)為：迭代次數(shù)為100，種群大小為100，記憶庫容量為10，交叉概率為0.5，變異概率為0.4.為了分析不同網(wǎng)點(diǎn)數(shù)對網(wǎng)點(diǎn)選址方案的影響，分別求解n取6、7、8、9和10時(shí)的網(wǎng)點(diǎn)選址優(yōu)化方案.本文在選取不同網(wǎng)點(diǎn)數(shù)的情況下，分別運(yùn)行10次，從10次運(yùn)行結(jié)果中選取目標(biāo)函數(shù)值最大的最優(yōu)解.

當(dāng)n取值不同時(shí)，計(jì)算得到不同的網(wǎng)點(diǎn)選址方案，目標(biāo)函數(shù)值、各需求點(diǎn)到相應(yīng)網(wǎng)點(diǎn)的總距離和平均覆蓋度率也會(huì)隨之變化.不同網(wǎng)點(diǎn)數(shù)求解結(jié)果如表4所列.當(dāng)n=8時(shí)，目標(biāo)函數(shù)值達(dá)到最優(yōu)值，因?yàn)楸疚闹匾紤]企業(yè)收益，故將選取8個(gè)租賃點(diǎn)的選址方案.

表4 不同網(wǎng)點(diǎn)數(shù)求解結(jié)果

經(jīng)過計(jì)算，本文利用免疫優(yōu)化算法對模型進(jìn)行求解，算法在迭代了51次后收斂到最優(yōu)解，免疫優(yōu)化算法收斂圖如圖5所示.算法得出的選址方案為1、2、3、4、6、9、17、18，即在甘肅高級(jí)人民法院、中海廣場、蘭州植物園、桃海市場、金水灣2號(hào)院、培黎廣場、金河麗園和華泰佳苑處計(jì)劃建設(shè)網(wǎng)點(diǎn).此時(shí)該選址模型最優(yōu)解為1 301 678.53，各需求點(diǎn)到相應(yīng)網(wǎng)點(diǎn)的總距離為21 745.26 m，平均覆蓋度率為79.3%，模型求解結(jié)果如表5所列.

圖5 免疫優(yōu)化算法收斂曲線

表5 模型求解結(jié)果

5 結(jié)論

本文首先論述了共享電動(dòng)汽車網(wǎng)點(diǎn)選址問題，構(gòu)建了網(wǎng)點(diǎn)選址優(yōu)化模型，通過設(shè)置合理的目標(biāo)函數(shù)與約束條件，保證了企業(yè)總收入最大、運(yùn)營成本最小和出行總距離最短的目標(biāo).采用了免疫優(yōu)化算法求解出該模型中共享電動(dòng)汽車網(wǎng)點(diǎn)選址的最佳方案，最后結(jié)合實(shí)際算例，計(jì)算出最佳網(wǎng)點(diǎn)選址結(jié)果，驗(yàn)證了該模型和算法的有效性和正確性.通過對比研究發(fā)現(xiàn)，求解不同網(wǎng)點(diǎn)數(shù)下的選址方案，發(fā)現(xiàn)隨著選取網(wǎng)點(diǎn)數(shù)的變化，最優(yōu)方案會(huì)發(fā)生變化，出行總距離及平均覆蓋率也隨之變化；在滿足相關(guān)約束的前提下，選取適當(dāng)?shù)木W(wǎng)點(diǎn)數(shù)，在一定程度上能增加企業(yè)的利潤.但本文只研究了共享電動(dòng)汽車網(wǎng)點(diǎn)選址問題，而共享電動(dòng)汽車系統(tǒng)實(shí)際運(yùn)營中，調(diào)度、充電以及顧客的需求都是動(dòng)態(tài)變化的.如何根據(jù)實(shí)際的動(dòng)態(tài)要求，對運(yùn)營中的共享電動(dòng)汽車進(jìn)行合理的調(diào)度、將是今后進(jìn)一步研究的內(nèi)容.