基于免疫算法的共享電動汽車網點選址研究

李偉斌，吳 芳，張 燕

(蘭州交通大學 交通運輸學院，蘭州 730070)

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

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

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

1 問題描述

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

1)假設各個備選網點的位置、企業計劃投入的車輛數、土地價格、汽車購置費、單位距離調度單價均已知；

2)假設所有共享網點的電動汽車只有一類汽車，充滿電的行駛里程能達到100%發揮，電池不發生電量損耗；

3)假設在運營中，共享電動汽車企業總能通過車輛調度滿足顧客的需求，完全覆蓋距離內不產生懲罰成本；

4)本文為了計算更加簡潔明了，暫不考慮共享電動汽車續航里程、電池電量、網點充電樁數量等諸多因素.

2 模型建立

2.1 選址過程分析

本文共享電動汽車網點選址方案的選擇應滿足以下要求，保證企業的利潤，盡量增大企業的收益以及減少企業的運營成本；其次為了更好地保證顧客的需求，本文在構建共享電動汽車網點選址模型時追求所有網點與到相應需求點的距離成本最小.各目標函數如下：

1)企業總運營收益最大.

maxf1=NLM;

(1)

2)網點的固定成本和企業經營成本.

(2)

3)各網點與到相應需求點的距離成本.

(3)

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

2.2 數學模型

本文最后衡量結果需要將多目標函數歸一化處理為單目標函數，所以本文通過線性加權方法把三個多目標函數歸一化處理為最大化的單目標函數.本文構建的共享電動汽車網點選址優化模型如下.

目標函數為：

(4)

式中：f為目標函數值；W1為企業總運營收益權重系數；W2為固定成本和經營成本權重系數；W3為距離成本權重系數；C取一個趨近于正無窮的數;

(5)

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

約束條件為：

(6)

(7)

(8)

(9)

(10)

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

(11)

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

(12)

(13)

(14)

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

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

3 算法設計

本文考慮該網點選址問題的約束條件和目標函數，結合問題設計算法步驟，通過求解模型可得出研究區域網點的布設方案，文中算法流程如圖1所示.

圖1 算法流程

3.1 染色體結構設計

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

3.2 解的評價

3.2.1 抗體濃度

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

(15)

式中：M為種群數，

(16)

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

3.2.2 期待繁殖概率

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

(17)

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

3.3 種群更新

3.3.1 選擇

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

3.3.2 交叉

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

圖2 抗體交叉示意圖

3.3.3 變異

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

圖3 抗體變異示意圖

4 案例及結果分析

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

圖4 候選網點分布圖

表1 部分候選點屬性

表2 模型相關參數

表3 模型參數設置

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

當n取值不同時，計算得到不同的網點選址方案，目標函數值、各需求點到相應網點的總距離和平均覆蓋度率也會隨之變化.不同網點數求解結果如表4所列.當n=8時，目標函數值達到最優值，因為本文重要考慮企業收益，故將選取8個租賃點的選址方案.

表4 不同網點數求解結果

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

圖5 免疫優化算法收斂曲線

表5 模型求解結果

5 結論

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