考慮電池壽命的電動物流車充電樁選址－路徑優化

文/王彥冬

電動汽車作為一種新能源交通工具，已經被廣泛地應用于各種物流場景。但是，現在仍有許多問題制約著電動汽車在物流配送領域的發展。多數學者是在有限地電池續航里程內進行路徑優化或設施位置布局研究，或同時考慮兩者。同時基于傳統車輛路徑問題研究的基礎上，對EVRP進行了擴展，例如：考慮了容量加載約束[1]、客戶滿意度[2]、多車型電動汽車[3]、多車場、換電池模式、多類型充電樁、充電樁選址[4]等?，F有研究旨在優化電動車輛的路徑或是充電樁的選址，有學者對選址路徑優化聯合研究也沒有考慮到電動車電池壽命對成本的影響。因此，針對電動物流車充電樁的選址－路徑優化問題，本文將影響電池壽命的參數加入模型當中，提出了考慮電池壽命的電動物流車充電樁選址－路徑優化問題，建立了該問題的整數規劃模型，并設計帶鄰域搜索的遺傳算法對其求解。最后，通過一個算例對模型和算法進行了測試和分析，證明了其有效性。

1.問題描述

本節構建了考慮電池壽命的電動物流車充電設施選址路徑優化模型。具體問題可描述如下：某一物流企業有一個物流中心，需要使用電動物流車給N個客戶配送貨物，對于每個客戶i都有對應的需求量qi和要求到達、離開的時間窗[ei，li]。如果電動物流車早于時間窗到達或者晚于時間窗離開都會支付相應的損失成本。每輛車均從配送中心出發，完成配送任務后返回配送中心。電動物流車的電池電量有限，在剩余電量不能到達下一個客戶點時會選擇相應的充電樁進行充電，同時，電動物流車在充電和行駛的過程中都會對電池造成損耗，降低電池壽命，增加成本。因此，要選擇合適的位置建設充電樁并且規劃電動物流車輛路徑，使車輛能夠完成配送任務并且讓物流企業的總運營成本最小。本文考慮的客戶點都是比較固定的，因此本文的充電樁選址是物流企業的長期決策。

2.模型建立

2.1 符號定義

充電樁選址－路徑優化問題的變量定義如表2-1所示。

表2 -1 符號定義

2.2 模型構建

式（1）表示物流企業的總運營成本的最小值，包括：電動物流車的行駛成本、充電電池損耗成本、放電電池損耗成本、充電時間成本、電動物流車固定成本、充電樁購買成本和時間窗成本；式（2）表示充電造成的電池損耗成本；式（3）表示放電造成的電池損耗成本；約束（4）表示每個客戶都被服務只被服務一次；約束（5）表示每輛車只使用一次；約束（6）表示保證了每輛車到達節點的次數與離開該節點的次數相同；約束（7）表示每輛車從配送中心出發完成任務后回到配送中心；約束（8）表示使用的電動物流車數量小于物流企業擁有的電動物流車數量；約束（9）表示電動物流車剩余的載貨量；約束（10）表示電動物流車的最大載貨量滿足每條路徑的需求量之和；約束（11）表示電動物流車在各點的電量；約束（12）表示電動物流車駛離充電樁后的車輛剩余電量；約束（13）表示電動物流車在充電樁的充電量為非負數，且充電后的電量小于等于電池最大容量；約束（14）表示電動物流車從配送中心出發時是滿電狀態；約束（15）表示電動物流車到達客戶點和離開客戶點時的電量不變；約束（16）表示電動物流車的電量能夠滿足剩余的配送任務；約束（17）表示如果電動物流車早于時間窗到達客戶點時的等待時間；約束（18-20）表示電動物流車從離開節點到離開節點所使用的時間；約束（21）表示造成電池壽命降低的損耗歷程所消耗的電量；約束（22）表示變量屬性。

3.算法設計

針對電動物流車充電樁選址－路徑優化問題，設計帶領域搜索的遺傳算法進行求解。算法具體流程如下：

3.1 編碼設計。本文采用在遺傳算法中加入變鄰域搜索操作進行問題求解，應用混合整數編碼的方式將一個可行解用客戶、配送中心和充電樁共同編碼來表示。

3.2 種群初始化。本文通過隨機生成數列作為初始染色體，然后根據車輛負載和電池剩余容量等約束，使用插入充電樁等方式，對初始染色體分配車輛，生成一條符合配送需求的染色體。

3.3 適應度函數。適應度函數是用來計算染色體個體的適應度值，來判斷個體的優劣。具體的計算公式如（23）所示

3.4 遺傳操作

3.4.1 選擇操作。本文根據初始種群中的每個個體的適應度值的大小，采用錦標賽策略進行父代個體的選擇。使用錦標賽策略的優勢在于，適應度值最大的個體，肯定會被選擇成為父代，而適應度值越大的個體，被選中的概率就越大。

3.4.2 交叉操作。本文采用了子路徑交叉的方式對染色體進行操作，表現為隨機選擇兩個優秀的父代個體進行兩兩交叉。

3.4.3 變異操作。本文中的變異是采用Insert插入的方式來實現。具體操作如下：選擇一個待變異的父代個體，隨機生成兩個染色體基因內的自然數x1和x2，在父代個體中刪除x1，在x2+1的位置放入x1，形成新的子代。

3.4.4 VND鄰域搜索。因為遺傳算法本身具有良好的全局搜索能力，但是局部搜索能力較差，這就造成了其大多數情況下只能確定局部最優但是很少情況下會達到全局最優。所以本文在遺傳算法的基礎上，引入鄰域搜索算法，鄰域搜索算法的優點就是避免種群陷入局部最優，在達到局部最優時進行跳躍，在新的領域中生成后代，尋找全局最優解。本文引入了三種鄰域搜索算子，分別是swap算子、2-opt算子和or-opt算子。這里只介紹2-opt算子。2-opt算子的操作如下：在遺傳算法完成一次迭代后，取出此次迭代的最優個體，在個體中隨機選擇兩個基因，將兩個基因內的染色體順序進行調換，形成新的染色體。比較新舊染色體的個體適應度值，保存適應度值較小的個體。

3.5 終止條件。當條件滿足循環代數等于maxgen或滿足連續30代種群中最優個體不變則終止遺傳循環。

4.算例及結果分析

4.1 算例數據。為了驗證本文建立模型的有效性和算法的能力，算例是包含1個配送中心，60個客戶點，6個充電樁備選點，共67個節點的配送系統，有5輛電動物流車可提供配送服務。配送中心坐標為（35，35），具體數據見表4-1，遺傳算法涉及參數設置如下：初始種群為300，迭代次數為500，交叉概率為0.9，變異概率為0.1。

表4-1 節點詳細信息

4.2 電動物流車充電樁選址路徑－優化方案?？紤]電池損耗的情況下，采用帶鄰域搜索的遺傳算法對電動物流車充電樁選址路徑－優化問題進行求解，運算結果如表4-2所示。

表4-2 配送路徑及充電位置

4.3 結果對比分析。由表4-3可知，電動物流車行駛成本、電池損耗成本、充電成本均有所下降，總成本比模型二低了469.2027元?？偝杀竟澕s了14.53%。充電成本節省了128.24%，電池損耗成本節省了141.54%。

表4-3 模型優化結果

結束語

本文在現有研究的基礎上，以物流企業為研究對象，分別考慮了充、放電對電池壽命的影響，針對問題建立了相應的數學模型，統籌安排充電樁的選址位置和電動物流車的行駛路徑，通過不同的優化策略，使得物流企業的總運營成本最低。同時，還設計了一種求解該問題的帶鄰域搜索的遺傳算法。算例結果表明，考慮電池壽命和充電策略的電動物流車充電樁選址路徑優化模型可以大幅降低電動物流車的電池損耗成本和充電時間成本，增加電動物流車電池壽命，達到降低運營成本的目的。