考慮充電策略與電池損耗的電動汽車路徑優化問題研究

郭 放，楊 珺，楊 超

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

1 引言

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

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

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

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

2 問題描述及數學模型

2.1 問題描述

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

2.2 定義變量

圖1 充滿電池所需時間

T=

(1)

2.2 數學模型

基于上述條件，數學模型如下：

(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)

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

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

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

(27)

(28)

3 啟發式算法MCWIGALNS

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

圖2 MCWIGALNS算法流程圖

3.1 改進節約算法

初始化階段電動汽車行駛里程約束被松弛。

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

步驟2：計算合并兩條路徑的節省成本。

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

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

3.2 迭代貪婪算法

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

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

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

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)本環節包括三個階段：可行度分析階段、站點加入階段以及優化階段。

(a)可行度分析階段

步驟1：設置當前解為不可行解；

步驟2：刪除當前解路徑中所有的充電站點；

步驟3：將刪除站點后的路徑集合作為當前解；

步驟4：計算顧客點可達性參數，判斷當前路徑是否可行，將不可行路徑送入下一階段。

(b)站點加入階段

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

步驟9：更新各個點的可達性參數，判斷路徑的可行性。如果全部路徑都可行，將當前解送入下一階段。否則，將不可行路徑返回步驟5。

(c)優化階段

本階段通過交換和移動充電站點的位置進一步優化當前可行解，如果優化后仍為可行解且目標值更優，則更新當前解和相應充電策略。

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

3.3 自適應大鄰域搜索

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

3.3.1 定義闡述

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

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

(d)懲罰函數：本文對解的搜索范圍進行適當延展。對于違反行駛里程的解，其目標函數值中需加入懲罰值：

(36)

M是極大值，qvk是前一階段顧客點可達性。

(e)終止標準：采用Adulyasak等[18]提出的基于模擬退火的終止標準。如果鄰域解s′優于當前解s則保留鄰域解，否則鄰域解被保留的概率為e-(z(s′)-z(s))/T。初始溫度T0=10000，Tn=cTn-1，冷卻速率c=0.995。當迭代次數達到給定的最大次數時，整個搜索過程結束。

3.3.2 自適應大鄰域搜索流程

步驟1：將迭代貪婪的結果作為初始解s0，初始解賦值給當前解s和最優解s*，進入第一次迭代；

步驟2：在迭代次數小于給定的最大次數時，選擇一對刪除和插入算子，將當前解s賦值給鄰域解s′。如果迭代次數達到給定的最大次數搜索結束；

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

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

步驟5：如果此時s′滿足接受標準，則將s′賦值給當前解s，否則放棄；

步驟6：如果z(s)

步驟7：更新各項算子的得分和權重，迭代次數+1，返回步驟2。

3.3.3 刪除算子

Random removal(RaR)：從當前解中隨機刪除nq個顧客點并將其存入等待集合(RB)。

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

Request graph removal(RGR)：由Pisinger和Ropke[21]提出，圖中邊的權重為這條邊在最優解中被車輛經過的次數，兩個權重最大的顧客點被認定為最相似的點。RGR的刪除機制類似于ReR。

Station-based removal(SBR)：隨機選擇一個站點，刪除與之相連的顧客點。

Single point removal(SPR)：兩個充電站點或者充電站點和o點之間的區域為一個服務區域。SPR的目的是破壞一個現有的服務區域構建新的車輛路徑。在路徑中隨機選擇一個操作點，刪除該點到它相鄰充電站點(或o點)之間的所有顧客點。

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

3.3.4 插入算子

3.4 優化最新解

步驟1：按順序刪除路徑rk中充電站點。如果刪除操作導致路徑不可行，進行步驟2；

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

步驟3：如果最新解更優，則更新當前解。返回步驟1，直到路徑數到達指定的最大可用車輛數或者當前解不能再被進一步優化。

4 實驗結果及分析

實驗的計算機參數配置為Intel(R) I5-4460，3.20GHz，8GB RAM。算法在JAVA實現為單線程代碼。

4.1 測試用例

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

表1 參數賦值

4.2 鄰域搜索配置

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

表2 刪除算子的性能比較

表3 插入算子的性能比較

4.3 實驗結果分析

4.3.1 模型與算法的驗證分析

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

表4 實驗結果對比

4.3.2 運營成本影響性分析

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

4.3.3 算法尋優能力對比分析

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

圖3 配送距離對比

圖4 運營成本對比

圖5 充電時間對比

圖6 深度放電行駛距離對比

圖7 算法最優解平均值對比

圖8 算法最優值與均值差異對比

表5 算法結果對比

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

5 結語

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

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