考慮充電策略與電池?fù)p耗的電動(dòng)汽車路徑優(yōu)化問題研究

郭 放，楊 珺，楊 超

(1.鄭州大學(xué)管理工程學(xué)院，河南 鄭州 450001；2.華中科技大學(xué)管理學(xué)院， 湖北 武漢 430074)

1 引言

由電池提供動(dòng)力的電動(dòng)汽車能夠有效地減少尾氣污染節(jié)約環(huán)境治理成本，這一特點(diǎn)促使其在物流配送行業(yè)中得到關(guān)注與應(yīng)用[1]。與此同時(shí)，國家先后出臺(tái)了一系列政策法規(guī)推進(jìn)電動(dòng)汽車產(chǎn)業(yè)和配套服務(wù)設(shè)施快速發(fā)展，為電動(dòng)汽車在物流配送行業(yè)的普及提供了有力保障。不同于傳統(tǒng)燃油車輛，電動(dòng)汽車行駛距離受到電池容量的限制，在行駛途中需要去往充電站點(diǎn)補(bǔ)充電量。其次，充電站點(diǎn)的選擇會(huì)影響電動(dòng)汽車的配送路徑。充電設(shè)施數(shù)量不足經(jīng)常導(dǎo)致電動(dòng)汽車被迫改變行駛線路，繞行前往充電站點(diǎn)。再次，電動(dòng)汽車所需的充電量是動(dòng)態(tài)變化的，與當(dāng)前電池剩余電量和車輛后續(xù)配送線路有關(guān)。電動(dòng)汽車的充電量和電池狀態(tài)直接影響充電時(shí)間。因此，科學(xué)地規(guī)劃電動(dòng)汽車配送路徑，優(yōu)化電動(dòng)汽車物流網(wǎng)絡(luò)成為了近期的研究熱點(diǎn)問題。在實(shí)際生活中電動(dòng)汽車鋰電池的充電方式有兩種：一種是恒流充電，另一種是恒流+恒壓充電。后者的充電效率更高，其過程主要分為兩個(gè)階段：第一階段為恒流快速充電階段，第二階段為恒壓慢速充電階段。當(dāng)電池電量充到電壓閾值(此時(shí)電量一般為總?cè)萘康?0%左右)，充電模式由第一階段轉(zhuǎn)化為第二階段。此外，車載電池的價(jià)格約為整車價(jià)格的1/3，部分車型電池價(jià)格高達(dá)整車價(jià)格的45%[2]。放電深度(電池放電量與儲(chǔ)存電量的比值)過深(超過70%)會(huì)對(duì)電池使用壽命造成損害[3]。為了延緩電池性能退化，應(yīng)避免電池進(jìn)入深度放電狀態(tài)。對(duì)于已經(jīng)深度放電的電池，目前較為先進(jìn)的充電方案對(duì)它們有一個(gè)涓流充電(低壓預(yù)充)階段[4]：電池在快速充電之前有一個(gè)低電流慢充的緩和過程，此過程可以一定程度修復(fù)因深度放電致電壓大幅度下降而造成的電池?fù)p傷。本文結(jié)合電池充、放電特性，在考慮了繞行、充電時(shí)間與電池?fù)p耗等成本的情況下研究了電動(dòng)汽車物流配送路徑問題。

近年來，國內(nèi)外學(xué)者從多方面對(duì)車輛路徑優(yōu)化問題進(jìn)行了研究，取得了豐富的成果。Erdogan和Miller-Hooks[5]提出了綠色車輛路徑問題(Green Vehicle Routing Problem，GVRP)，對(duì)車輛路徑和電動(dòng)汽車充電策略進(jìn)行研究并建立了以行駛距離最小為目標(biāo)的混合整形規(guī)劃模型，運(yùn)用改進(jìn)的節(jié)約算法和基于密度的聚類算法求得近似解。但是該文章把車輛補(bǔ)充燃料的時(shí)間設(shè)為定值且忽略了車輛的載重約束。Schneider等[6]考慮了時(shí)間窗約束，充電時(shí)間取決于充電率和車輛到達(dá)充電站的電量狀況。隨后采用變鄰域搜索和禁忌搜索相結(jié)合的啟發(fā)式算法求得模型的近似解。Yang Jun等[7-8]研究了電動(dòng)汽車物流配送系統(tǒng)的換電站選址和配送路徑優(yōu)化問題，提出了基于禁忌搜索-改進(jìn)節(jié)約算法的兩階段啟發(fā)式算法和基于貪婪算法-自適應(yīng)大鄰域搜索算法的啟發(fā)式算法。符卓等[9]針對(duì)帶軟時(shí)間窗的需求依訂單拆分車輛路徑問題及其優(yōu)化算法進(jìn)行研究。李進(jìn)等[10]研究了低碳環(huán)境下由第三方提供運(yùn)輸服務(wù)的車輛路徑問題。在安排車輛路徑時(shí)，同時(shí)考慮了能耗、碳排放和租車費(fèi)用。揭婉晨等[11]研究了含時(shí)間窗的多車型電動(dòng)汽車車輛路徑問題，采用分支定價(jià)算法求其最優(yōu)解。

以上文獻(xiàn)均關(guān)注的是車輛行駛距離最小化問題，并未涉及電動(dòng)汽車充電策略。近期有一些文獻(xiàn)考慮了充電策略，F(xiàn)elipe等[12]在GVRP問題的基礎(chǔ)上加入充電量。Desaulniers等[13]提出了4種充電策略(single-FR，single-PR，multiple-FR，and multiple-PR)，使用啟發(fā)式算法對(duì)充電策略的結(jié)果進(jìn)行比較。Keskin和Catay[14]在(1)電動(dòng)汽車離開倉庫時(shí)為滿電量；(2)電動(dòng)汽車回到倉庫時(shí)恰好將電量耗盡；(3)充電速率為恒定值的假設(shè)下，研究了如何根據(jù)實(shí)際需求來確定充電策略。Bruglieri等[15]采用變鄰域搜索的方法來求解帶時(shí)間窗的電動(dòng)汽車貨物配送路徑問題，該研究允許車輛在途充電且充電速率恒定。Penna等[16]對(duì)混合迭代局部搜索算法在電動(dòng)汽車車輛路徑與車隊(duì)規(guī)模問題中的運(yùn)用進(jìn)行了探索，該研究考慮了由多種不同類型電動(dòng)汽車組成的車隊(duì)的貨物配送策略，允許車輛在途充電，每次充滿且充電速率恒定。

綜合來看，(1)多數(shù)研究車輛路徑問題的文獻(xiàn)關(guān)注于路線長(zhǎng)度的最小化，沒有將充電策略納入考慮范圍。(2)考慮了充電策略的文獻(xiàn)也僅僅關(guān)注于充電量，沒有根據(jù)電池本身的充電特性刻畫模型來考慮充電模式與成本。鑒于此，本文建立基于電動(dòng)汽車運(yùn)營(yíng)成本最小化的允許在途充電的電動(dòng)汽車車輛路徑?jīng)Q策模型，與已有研究主要區(qū)別如下：(1)首次將電池?fù)p耗成本加入車輛路徑優(yōu)化問題中，將車輛深度放電狀態(tài)下行駛的距離作為優(yōu)化對(duì)象；(2)電池的充電速率不再是恒定值，而是跟電池當(dāng)前狀態(tài)相關(guān)的函數(shù)；(3)充電時(shí)間不僅取決于車輛到達(dá)充電站時(shí)電池的電量狀況和車輛接下來的配送任務(wù)安排，還需要在充電時(shí)間成本以及深度放電行駛的機(jī)會(huì)成本之間進(jìn)行權(quán)衡。

2 問題描述及數(shù)學(xué)模型

2.1 問題描述

物流配送網(wǎng)絡(luò)G=(V,E)，其中V={v1,v2,…,vn}表示頂點(diǎn)集合，它由顧客集合I、充電站集合J、配送中心o和虛擬配送中心o′共同組成，V=I∪J∪{o}∪{o′}。E={(vi,vj):vi,vj∈V,vi≠vj}表示弧的集合。集合I∪J中每個(gè)節(jié)點(diǎn)i都具有需求量參數(shù)qi，qi表示點(diǎn)i所需配送的貨物數(shù)量。對(duì)于集合J中的節(jié)點(diǎn)i，qi=0。集合E中每條弧都包含非負(fù)參數(shù)dij，dij表示節(jié)點(diǎn)i和j之間的距離。K={k1,k2,…,km}表示配送車輛集合。集合K中每一輛車k都包含兩個(gè)非負(fù)參數(shù)，即車輛k的最大載重Uk和滿電量狀態(tài)下最長(zhǎng)行駛里程Q。集合R={r1,r2,…,rz}是配送路徑的集合，每條路徑由一輛車負(fù)責(zé)配送。本文需要解決的問題可以描述為：創(chuàng)造不超過|K|條路徑為N位顧客提供貨物配送服務(wù)，使得(1)配送車輛從配送中心o點(diǎn)出發(fā)，服務(wù)若干顧客后返回到配送中心；(2)每個(gè)顧客只被服務(wù)一次；(3)路徑rk的配送總重量不能超過車輛最大載重Uk；(4) 車輛在配送途中剩余電量必須為非負(fù)值，允許車輛在執(zhí)行配送任務(wù)途中前往站點(diǎn)充電；(5)整體運(yùn)營(yíng)成本最低。

2.2 定義變量

圖1 充滿電池所需時(shí)間

T=

(1)

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

基于上述條件，數(shù)學(xué)模型如下：

(2)

s.t.

(3)

?h∈V{o,o′},k∈K

(4)

(5)

(6)

(7)

uhk≤ugk-qhxghk+Uk(1-xghk)

?h∈V{o},g∈V{o′},g≠h,k∈K

(8)

uok≤Uk?k∈K

(9)

uhk≥0 ?k∈K,h∈V{o′}

(10)

?h∈V{o},g∈V{o′},g≠h,k∈K

(11)

(12)

(13)

(14)

(15)

(16)

xghk∈{0,1} ?h∈V{o},g∈V{o′},k∈K

(17)

上述模型中，目標(biāo)函數(shù)(2)表示最小化運(yùn)營(yíng)成本。式(3)表示每個(gè)顧客點(diǎn)只被服務(wù)一次。式(4)表示各點(diǎn)車流量平衡。式(5)表示配送車輛從配送中心出發(fā)，服務(wù)若干顧客點(diǎn)后最終回到出發(fā)點(diǎn)。式(6)表示每輛車最多服務(wù)一條路徑。式(7)表示參與配送任務(wù)的車輛數(shù)目不能超過擁有的車輛總數(shù)。式(8)表示配送車輛按照路徑途經(jīng)各點(diǎn)的剩余貨物量。式(9)確保任何一條路徑中的顧客總需求量不能超過提供服務(wù)的車輛的最大載重量。式(10)表示剩余貨物量為非負(fù)。式(11)表示配送車輛按照路徑途經(jīng)各點(diǎn)的剩余電量。式(12)表示車輛離開充電站點(diǎn)后的剩余電量。式(13)表示充電量為非負(fù)數(shù)，且充電后的電量不能超過電池容量。式(14)表示車輛離開配送中心時(shí)電池是滿電量狀態(tài)。式(15)表示車輛剩余電量在顧客點(diǎn)無變化。式(16)確保車輛有充足的電量完成預(yù)定線路的配送任務(wù)。式(17)表示變量屬性。

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

k∈K,j∈J,i∈{1,2},n∈{1,2,3}

(27)

(28)

3 啟發(fā)式算法MCWIGALNS

本章采用啟發(fā)式算法MCWIGALNS解決電動(dòng)汽車配送路徑與充電策略問題。MCWIGALNS分為三部分：首先采用Erdogan等[5]提出的改進(jìn)節(jié)約算法求得初始路徑集合，將其作為當(dāng)前路徑集合代入充電策略子問題階段。然后，迭代貪婪算法為服務(wù)路徑在合適的位置加入站點(diǎn)，電動(dòng)汽車在站點(diǎn)的充電量取決于當(dāng)前電池狀態(tài)和車輛后續(xù)配送任務(wù)。隨后，將充電策略子問題選擇的充電站點(diǎn)集合作為輸入?yún)?shù)代入到路徑子問題階段，采用自適應(yīng)大鄰域搜索算法搜尋最優(yōu)路徑集合并將其反向傳遞給充電策略子問題階段。算法通過多次迭代使可行解逐漸向最優(yōu)解靠近。圖2給出了MCWIGALNS算法流程圖。

圖2 MCWIGALNS算法流程圖

3.1 改進(jìn)節(jié)約算法

初始化階段電動(dòng)汽車行駛里程約束被松弛。

步驟1：顧客點(diǎn)i∈I生成服務(wù)線路(o-i-o)。

步驟2：計(jì)算合并兩條路徑的節(jié)省成本。

步驟3：根據(jù)步驟2的計(jì)算結(jié)果，按照節(jié)省成本由高到低合并路徑。檢查車輛容量約束是否滿足新路徑的服務(wù)要求。如果不滿足，則取消這兩條路徑的合并，繼續(xù)合并其余路徑。如果滿足，保存新路徑后繼續(xù)合并剩余路徑。

步驟4：如果新路徑滿足繼續(xù)合并的條件，返回步驟2。否則，輸出路徑的初始解。

3.2 迭代貪婪算法

本節(jié)采用迭代貪婪算法為路徑選擇合適的充電站點(diǎn)使得完成所有配送任務(wù)所需付出的成本最低。

(1)安置成本分析：算法首先刪除掉路徑中存在的充電站點(diǎn)，根據(jù)安置成本的高低為路徑重新選擇充電站點(diǎn)。

(c)充電時(shí)間：車輛到達(dá)充電站i后，首先將電量充到恰好能到達(dá)終點(diǎn)或者下一個(gè)站點(diǎn)(充電量上限為充滿)得到初始充電時(shí)間，如果充滿后仍不足以到達(dá)終點(diǎn)或者下一個(gè)站點(diǎn)，則令該充電時(shí)間為一個(gè)極大值；其次，檢查車輛電池狀態(tài)(SOC)，如果電池電量低于0.8Q且該路徑在點(diǎn)i之后還安排有其余充電站點(diǎn)，則將這部分電池的電量充至0.8Q，更新充電時(shí)間和SOC。如果電動(dòng)汽車以當(dāng)前電量行駛到終點(diǎn)或下一站點(diǎn)的剩余電量低于ηQ，則比較繼續(xù)慢充的時(shí)間成本與深度放電的電池?fù)p耗成本，計(jì)算出最佳的充電量。

j∈J,v∈V,rk∈R

(29)

β1+β2+β3+β4+β5=1,β1,β2,β3,β4,β5≥0

(30)

(31)

(32)

(33)

(34)

(35)

(2)本環(huán)節(jié)包括三個(gè)階段：可行度分析階段、站點(diǎn)加入階段以及優(yōu)化階段。

(a)可行度分析階段

步驟1：設(shè)置當(dāng)前解為不可行解；

步驟2：刪除當(dāng)前解路徑中所有的充電站點(diǎn)；

步驟3：將刪除站點(diǎn)后的路徑集合作為當(dāng)前解；

步驟4：計(jì)算顧客點(diǎn)可達(dá)性參數(shù)，判斷當(dāng)前路徑是否可行，將不可行路徑送入下一階段。

(b)站點(diǎn)加入階段

步驟5：對(duì)于不可行路徑rk，將其第一個(gè)斷點(diǎn)前面顧客點(diǎn)依次加入備選集合Bk，直到遇到充電站點(diǎn)或者回到起點(diǎn)為止。

步驟9：更新各個(gè)點(diǎn)的可達(dá)性參數(shù)，判斷路徑的可行性。如果全部路徑都可行，將當(dāng)前解送入下一階段。否則，將不可行路徑返回步驟5。

(c)優(yōu)化階段

本階段通過交換和移動(dòng)充電站點(diǎn)的位置進(jìn)一步優(yōu)化當(dāng)前可行解，如果優(yōu)化后仍為可行解且目標(biāo)值更優(yōu)，則更新當(dāng)前解和相應(yīng)充電策略。

算法通過交換充電策略和路徑策略的信息，使可行解在迭代過程中逐漸向最優(yōu)解靠近。迭代貪婪算法安排安置成本最低的充電策略。新的充電策略作用于路徑策略。路徑策略通過自適應(yīng)大鄰域搜索來完成。

3.3 自適應(yīng)大鄰域搜索

自適應(yīng)大鄰域搜索由Ropke和Pisinger[17]提出，此算法的主要思想是通過從當(dāng)前路徑中刪除一部分顧客點(diǎn)并將其重新放入路徑這一過程的反復(fù)迭代，到達(dá)在更大鄰域范圍內(nèi)搜索新解的目的。

3.3.1 定義闡述

(a)大鄰域：算法通過刪除策略刪除nq個(gè)顧客并將其暫存在顧客等待集合(RB)。隨后通過插入策略將RB中顧客重新放回路徑中從而得出新的解。

(b)刪除和插入算子：上文提及的刪除和插入策略即為算子。

(d)懲罰函數(shù)：本文對(duì)解的搜索范圍進(jìn)行適當(dāng)延展。對(duì)于違反行駛里程的解，其目標(biāo)函數(shù)值中需加入懲罰值：

(36)

M是極大值，qvk是前一階段顧客點(diǎn)可達(dá)性。

(e)終止標(biāo)準(zhǔn)：采用Adulyasak等[18]提出的基于模擬退火的終止標(biāo)準(zhǔn)。如果鄰域解s′優(yōu)于當(dāng)前解s則保留鄰域解，否則鄰域解被保留的概率為e-(z(s′)-z(s))/T。初始溫度T0=10000，Tn=cTn-1，冷卻速率c=0.995。當(dāng)?shù)螖?shù)達(dá)到給定的最大次數(shù)時(shí)，整個(gè)搜索過程結(jié)束。

3.3.2 自適應(yīng)大鄰域搜索流程

步驟1：將迭代貪婪的結(jié)果作為初始解s0，初始解賦值給當(dāng)前解s和最優(yōu)解s*，進(jìn)入第一次迭代；

步驟2：在迭代次數(shù)小于給定的最大次數(shù)時(shí)，選擇一對(duì)刪除和插入算子，將當(dāng)前解s賦值給鄰域解s′。如果迭代次數(shù)達(dá)到給定的最大次數(shù)搜索結(jié)束；

步驟3：使用選擇的刪除算子處理s′；

步驟4：使用選擇的插入算子處理s′；

步驟5：如果此時(shí)s′滿足接受標(biāo)準(zhǔn)，則將s′賦值給當(dāng)前解s，否則放棄；

步驟6：如果z(s)

步驟7：更新各項(xiàng)算子的得分和權(quán)重，迭代次數(shù)+1，返回步驟2。

3.3.3 刪除算子

Random removal(RaR)：從當(dāng)前解中隨機(jī)刪除nq個(gè)顧客點(diǎn)并將其存入等待集合(RB)。

Related removal(ReR)：從當(dāng)前解中挑選出跟指定顧客點(diǎn)i相似的顧客點(diǎn)，將它們和i點(diǎn)一同刪除并存入集合RB[20]。隨機(jī)選擇一個(gè)顧客點(diǎn)i，通過參數(shù)Iden(i,j)=α1dij+α2|qi-qj|+ηij來判斷i和j的相似度。其中α1和α2是權(quán)重系數(shù)，α1+α2=1。dij是兩點(diǎn)之間的距離，|qi-qj|是兩點(diǎn)需求量的差值。如果i和j屬于同一條路徑，ηij=1，否則ηij=0。類似于BWR，被挑選出來的顧客點(diǎn)會(huì)以一定的概率被刪除，概率由參數(shù)ρr。

Request graph removal(RGR)：由Pisinger和Ropke[21]提出，圖中邊的權(quán)重為這條邊在最優(yōu)解中被車輛經(jīng)過的次數(shù)，兩個(gè)權(quán)重最大的顧客點(diǎn)被認(rèn)定為最相似的點(diǎn)。RGR的刪除機(jī)制類似于ReR。

Station-based removal(SBR)：隨機(jī)選擇一個(gè)站點(diǎn)，刪除與之相連的顧客點(diǎn)。

Single point removal(SPR)：兩個(gè)充電站點(diǎn)或者充電站點(diǎn)和o點(diǎn)之間的區(qū)域?yàn)橐粋€(gè)服務(wù)區(qū)域。SPR的目的是破壞一個(gè)現(xiàn)有的服務(wù)區(qū)域構(gòu)建新的車輛路徑。在路徑中隨機(jī)選擇一個(gè)操作點(diǎn)，刪除該點(diǎn)到它相鄰充電站點(diǎn)(或o點(diǎn))之間的所有顧客點(diǎn)。

Binary removal(BiR)：BiR是SBR的一種特殊情況，區(qū)別在于BiR選擇路徑的中間點(diǎn)為操作點(diǎn)。

3.3.4 插入算子

3.4 優(yōu)化最新解

步驟1：按順序刪除路徑rk中充電站點(diǎn)。如果刪除操作導(dǎo)致路徑不可行，進(jìn)行步驟2；

步驟2：選擇增加成本最低的點(diǎn)作為路徑分裂點(diǎn)，將rk分為兩條新的路徑rk1和rk2。增加成本計(jì)算方法類似于ΔZik；

步驟3：如果最新解更優(yōu)，則更新當(dāng)前解。返回步驟1，直到路徑數(shù)到達(dá)指定的最大可用車輛數(shù)或者當(dāng)前解不能再被進(jìn)一步優(yōu)化。

4 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)的計(jì)算機(jī)參數(shù)配置為Intel(R) I5-4460，3.20GHz，8GB RAM。算法在JAVA實(shí)現(xiàn)為單線程代碼。

4.1 測(cè)試用例

數(shù)據(jù)來源于三部分，一部分是Augerat等[22]、Taillard[23]和Golden等[24]提出的3組不同規(guī)模算例，算例可從網(wǎng)站http://neo.lcc.uma.es/vrp/vrp-instances/ 獲取。一部分是Yang Jun和Sun Hao[7]的實(shí)驗(yàn)參數(shù)，表1對(duì)算法中部分參數(shù)的取值進(jìn)行了介紹。其余數(shù)據(jù)參考相關(guān)專業(yè)網(wǎng)站，如工資標(biāo)準(zhǔn)、電動(dòng)貨車售價(jià)以及充電樁充電速率等。算例將貨車司機(jī)的時(shí)薪作為充電時(shí)間的單位成本。以最有可能率先大規(guī)模使用電動(dòng)物流車輛的發(fā)達(dá)地區(qū)為例，北上廣三地的最低工資標(biāo)準(zhǔn)分別是21、19和18.3元/小時(shí)，本文折中選取20元作為單位時(shí)間成本。以某款由鋰電池提供動(dòng)力的電動(dòng)貨車A為例，其售價(jià)330000元，最大行駛里155km(40km/h 勻速法測(cè)量)?？紤]到實(shí)際工作環(huán)境，本文假設(shè)其最大行駛里程100km。根據(jù)Green Car Report[2]的研究結(jié)果，電池約占電動(dòng)汽車成本的1/3，估算A的電池成本約為100000元。鋰電池可以重復(fù)充電600—1000余次，即電池最多可以支持車輛行駛100000km，平均每公里電池成本1元。電池使用壽命與諸多因素有關(guān)，本文僅考慮深度放電對(duì)其的影響。長(zhǎng)時(shí)間深度放電會(huì)導(dǎo)致電池壽命下降30% —50%，據(jù)此計(jì)算深度放電行駛的機(jī)會(huì)成本為每公里1.4-2元，本文選擇2元作為深度放電行駛的單位成本。充電速率取值參考國家電網(wǎng)充電樁實(shí)際參數(shù)，直流快充樁2小時(shí)能將一輛電動(dòng)汽車的電量從0充到80%，慢充樁每小時(shí)為車輛充入10% 的電量。

表1 參數(shù)賦值

4.2 鄰域搜索配置

本節(jié)對(duì)上述算子的尋優(yōu)能力進(jìn)行比較，挑選出優(yōu)秀的算子組合以到達(dá)提高算法效率的目的。算子入選的評(píng)價(jià)機(jī)制如下：算子在至少一半的算例中被使用次數(shù)高于所有算子被使用次數(shù)的平均值。考慮到算法中包含隨機(jī)參數(shù)，算例皆采用默認(rèn)參數(shù)運(yùn)行10次，取其平均值作為最后結(jié)果。表2展示了刪除算子的比較結(jié)果。根據(jù)上述入選評(píng)價(jià)機(jī)制選擇了RaR、RGR、ReR、SPR和BiR。插入算子的比較結(jié)果見表3所示，BR2I、BR3I、AR2I和AR3I滿足要求。但是，RkI比AGI 的計(jì)算效率低，尤其是Ropke和Pisinger[17]對(duì)算法計(jì)算效率的影響較為明顯。AGI能夠在更短的計(jì)算時(shí)間內(nèi)得到與BR3I較為接近的解，本文在權(quán)衡解的精確性和運(yùn)算效率之后采用AGI替代BR3I。表2-3中“*”表示被挑選出來，在下面的實(shí)驗(yàn)中會(huì)用到的算子。

表2 刪除算子的性能比較

表3 插入算子的性能比較

4.3 實(shí)驗(yàn)結(jié)果分析

4.3.1 模型與算法的驗(yàn)證分析

為了評(píng)估模型的準(zhǔn)確性以及算法的尋優(yōu)能力，本文使用能被CPLEX12.6求解的小規(guī)模算例進(jìn)行計(jì)算。為保證實(shí)驗(yàn)的一般性，在Augerat等[22]算例P-n16-k8中選擇5組實(shí)例數(shù)據(jù)，實(shí)例數(shù)據(jù)只選用了初始算例的最后n個(gè)顧客點(diǎn)。每組實(shí)例包含的顧客數(shù)與可用車輛數(shù)目不同。設(shè)定CPLEX運(yùn)行時(shí)間的上限為3 小時(shí)(10800s)?！?”表示此解是CPLEX運(yùn)行3小時(shí)得到的可行解?！?”表示CPLEX未能在規(guī)定時(shí)間內(nèi)找到可行解。測(cè)試結(jié)果整理如表4所示。第2列和第3列分別是算例包含的顧客點(diǎn)數(shù)目和可調(diào)配的車輛數(shù)。第4列到第7列依次為CPLEX求得的最優(yōu)解、最優(yōu)解的充電時(shí)間、深度放電行駛距離、求解時(shí)間(s)。第8列到第11列是MCWIGALNS的求解結(jié)果。第12列是算法與CPLEX最優(yōu)解的相對(duì)差值(Gap)：(算法的最優(yōu)解-CPLEX求出的最優(yōu)解)/CPLEX求出的最優(yōu)解。通過表4可以看出兩者的結(jié)果非常接近，MCWIGALNS的求解效率較高，驗(yàn)證了本文提出的模型和算法的正確性。

表4 實(shí)驗(yàn)結(jié)果對(duì)比

4.3.2 運(yùn)營(yíng)成本影響性分析

本節(jié)將考慮充電時(shí)間與電池?fù)p耗的VRP模型與傳統(tǒng)VRP模型進(jìn)行對(duì)比研究。從Augerat等[22]和Taillard[23]兩大類數(shù)據(jù)集中分別選取4組和3組實(shí)例，比較算例在兩種數(shù)學(xué)模型下的最優(yōu)運(yùn)營(yíng)成本。圖3對(duì)兩種模型在不同案例中行駛路徑總長(zhǎng)進(jìn)行比較。圖3表明兩種模型在不同算例中的行駛距離非常接近，模型二的距離略短于模型一。圖4對(duì)比了兩種模型在不同案例中運(yùn)營(yíng)成本。其中，模型二在得出最優(yōu)解后，根據(jù)最優(yōu)解的路徑計(jì)算其相應(yīng)的充電時(shí)間與深度放電行駛成本并加入到總成本中。由圖4可以看出，模型一在所有算例中的運(yùn)營(yíng)成本皆低于模型二?？晒?jié)約成本((成本1-成本2)/成本2)的均值為22.89%。在圖5-6充電時(shí)間和深度放電行駛成本的比較中可以看出，模型一的表現(xiàn)更好，該模型在所有算例中的充電時(shí)間和深度放電行駛成本全部低于模型二。模型一可以在總路徑略微增加的情況下，通過改變路徑策略來減少充電時(shí)間和深度放電行駛路程，最終到達(dá)降低運(yùn)營(yíng)成本的目的。

4.3.3 算法尋優(yōu)能力對(duì)比分析

下文采用三組不同規(guī)模算例驗(yàn)證MCWIGALNS的路徑優(yōu)化能力，并與傳統(tǒng)禁忌算法TSMCWS和自適應(yīng)大鄰域搜索SIGALNS進(jìn)行對(duì)比。實(shí)驗(yàn)算例從Augerat等[22]、Taillard[23]和Golden等[24]中分別選取10組、12組和2組，算例包含的顧客點(diǎn)數(shù)目從16到480不等，可調(diào)配車輛數(shù)從8輛到38輛不等。對(duì)照算法的實(shí)驗(yàn)數(shù)據(jù)來自于Yang Jun和San Hao[7]的研究成果。為增強(qiáng)對(duì)比結(jié)果的公正性，需要使算法目標(biāo)函數(shù)保持一致。本節(jié)實(shí)驗(yàn)中MCWIGALNS松弛了充電時(shí)間和深度放電的懲罰并賦予被選擇的充電站點(diǎn)相應(yīng)的建設(shè)成本。算法運(yùn)行10次并將最優(yōu)解記錄到表5。表5第3列和第4列分別是算例包含的顧客點(diǎn)數(shù)目和可調(diào)配的車輛數(shù)。第5列到第7列依次為TSMCWS、SIGALNS和MCWIGALNS的最優(yōu)解，第8列是MCWIGALNS求解時(shí)間(s)。第9列和第10列分別是TSMCWS和SIGALNS的最優(yōu)解與MCWIGALNS最優(yōu)解的相對(duì)差距。由表5可知，MCWIGALNS與兩種算法第一組算例最優(yōu)解的相對(duì)差距最大分別達(dá)到了11.1%和3.4%，只有在算例1中，SIGALNS得到了最優(yōu)值。在第二組和第三組算例中，TSMCWS在算例17和24得到了最優(yōu)解，根據(jù)Ropke和Pisinger[17]的研究結(jié)論解釋為個(gè)別特殊顧客點(diǎn)的空間分布對(duì)自適應(yīng)的大鄰域算法的可行解產(chǎn)生了不良影響。通過比較可知，MCWIGALNS搜索能力優(yōu)于其余兩種算法。此外，實(shí)驗(yàn)結(jié)果顯示對(duì)不同的算例，MCWIGALNS的求解時(shí)間大相近庭，同類實(shí)例求解時(shí)間隨模型規(guī)模呈現(xiàn)出上升趨勢(shì)。規(guī)模相近的不同類型實(shí)例的求解時(shí)間也有較大差異。這表明該算法的性能同時(shí)受到問題規(guī)模和數(shù)據(jù)自身特性的影響?？傮w來說，計(jì)算時(shí)間在企業(yè)可接受的時(shí)間范圍內(nèi)，不影響算法的一般實(shí)用性。

圖3 配送距離對(duì)比

圖4 運(yùn)營(yíng)成本對(duì)比

圖5 充電時(shí)間對(duì)比

圖6 深度放電行駛距離對(duì)比

圖7 算法最優(yōu)解平均值對(duì)比

圖8 算法最優(yōu)值與均值差異對(duì)比

表5 算法結(jié)果對(duì)比

圖7展示了對(duì)照算法平均解與MCWIGALNS的平均解的相對(duì)差距。其計(jì)算方式為(對(duì)照算法平均解—MCWIGALNS的平均解)/MCWIGALNS的平均解。圖7展示了算例平均值的相對(duì)差值為正數(shù)表明MCWIGALNS的平均解小于與其進(jìn)行對(duì)比的算法。由此可見，表5展示的各算例結(jié)果中MCWIGALNS的解更優(yōu)并非偶然，其平均值也優(yōu)于其余兩種算法。圖8展示了SIGALN和MCWIGALNS計(jì)算結(jié)果的平均值與最優(yōu)值的相對(duì)差值，可以看出MCWIGALNS的最優(yōu)解與解的平均值差值波動(dòng)小于SIGALNS，MCWIGALNS求解的穩(wěn)定性優(yōu)于SIGALNS。

5 結(jié)語

本文在允許在途充電的電動(dòng)汽車的配送車輛路徑問題的基礎(chǔ)上引入了兩個(gè)重要概念：充電時(shí)間函數(shù)和深度放電行駛距離。將車輛在配送貨物途中的充電時(shí)間和電池?fù)p耗成本納入求解的目標(biāo)函數(shù)并建立了它的線性規(guī)劃數(shù)學(xué)模型，統(tǒng)籌安排車輛的行駛路徑和充電策略使得物流企業(yè)運(yùn)營(yíng)成本最低。此外，還設(shè)計(jì)了一種求解該問題的改進(jìn)型算法MCWIGALNS。實(shí)驗(yàn)結(jié)果表明，考慮充電時(shí)間與深度放電成本的模型可以在略微增加配送距離的情況下，較大幅度壓縮時(shí)間與電池?fù)p耗成本，到達(dá)降低運(yùn)營(yíng)成本的目的。算法MCWIGALNS對(duì)VRP有出色的求解能力，提升了該問題理論成果的實(shí)用性。

以下幾方面還有待進(jìn)一步研究，本文所考慮的充電速率仍為確定性分段線性函數(shù)形式，深度放電過程中也僅考慮了行駛距離，并未考慮深度放電過程對(duì)電池?fù)p耗的非線性變化；其次，設(shè)計(jì)更加高效的策略將是未來工作的一個(gè)重點(diǎn)。