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

文/王彥冬

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

1.問題描述

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

2.模型建立

2.1 符號定義

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

表2 -1 符號定義

2.2 模型構(gòu)建

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

3.算法設(shè)計

針對電動物流車充電樁選址－路徑優(yōu)化問題，設(shè)計帶領(lǐng)域搜索的遺傳算法進(jìn)行求解。算法具體流程如下：

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

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

3.3 適應(yīng)度函數(shù)。適應(yīng)度函數(shù)是用來計算染色體個體的適應(yīng)度值，來判斷個體的優(yōu)劣。具體的計算公式如（23）所示

3.4 遺傳操作

3.4.1 選擇操作。本文根據(jù)初始種群中的每個個體的適應(yīng)度值的大小，采用錦標(biāo)賽策略進(jìn)行父代個體的選擇。使用錦標(biāo)賽策略的優(yōu)勢在于，適應(yīng)度值最大的個體，肯定會被選擇成為父代，而適應(yīng)度值越大的個體，被選中的概率就越大。

3.4.2 交叉操作。本文采用了子路徑交叉的方式對染色體進(jìn)行操作，表現(xiàn)為隨機(jī)選擇兩個優(yōu)秀的父代個體進(jìn)行兩兩交叉。

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

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

3.5 終止條件。當(dāng)條件滿足循環(huán)代數(shù)等于maxgen或滿足連續(xù)30代種群中最優(yōu)個體不變則終止遺傳循環(huán)。

4.算例及結(jié)果分析

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

表4-1 節(jié)點詳細(xì)信息

4.2 電動物流車充電樁選址路徑－優(yōu)化方案。考慮電池?fù)p耗的情況下，采用帶鄰域搜索的遺傳算法對電動物流車充電樁選址路徑－優(yōu)化問題進(jìn)行求解，運算結(jié)果如表4-2所示。

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

4.3 結(jié)果對比分析。由表4-3可知，電動物流車行駛成本、電池?fù)p耗成本、充電成本均有所下降，總成本比模型二低了469.2027元。總成本節(jié)約了14.53%。充電成本節(jié)省了128.24%，電池?fù)p耗成本節(jié)省了141.54%。

表4-3 模型優(yōu)化結(jié)果

結(jié)束語

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