考慮速度與能量消耗的電動車輛路徑規(guī)劃

邢思遠(yuǎn)（中國礦業(yè)大學(xué) 礦業(yè)工程學(xué)院，江蘇 徐州 221116）

0 引言

國際社會普遍認(rèn)為，引起氣候變化的重要因素是由于溫室氣體的過度排放。物流運輸業(yè)作為消耗石油能源的重要行業(yè)，也成為溫室氣體的顯著排放源[1]。隨著“碳排放，碳中和”、綠色物流、新能源汽車政策的提出，以及純電動新能源汽車相比燃油車所具有無直接碳排放的優(yōu)勢，可以預(yù)見電動汽車將會成為物流運輸?shù)闹匾煌üぞ遊2]。現(xiàn)階段電動汽車自身仍然存在較為明顯的劣勢：續(xù)航能力較差，遠(yuǎn)距離行駛能力較弱以及行駛過程中充電不方便等[3]。本研究根據(jù)電動汽車自身特性，研究以傳統(tǒng)車輛路徑問題（Vehicle Routing Problems，VRP）為基礎(chǔ)的帶時間窗的電動車路徑規(guī)劃（Electric Vehicle Routing Problem with Time Windows，EVRPTW）。文中對電動車輛能耗量以及行駛速度作為新的影響因素，進(jìn)行了配送過程中能耗計算及速度對能耗影響的研究。

EVRPTW 是VRP 的變體問題，二者同屬于NP-hard 問題，求解方法主要以遺傳算法（Genetic Algorithm，GA）、禁忌搜索算法（Tabu Search，TS）、模擬退火算法（Simulated Annealing，SA）等智能優(yōu)化算法為主。Schneider 等人[4]使用混合禁忌搜索和可變鄰域搜索解決考慮充電站的EVRPTW，提出了一個數(shù)學(xué)模型，同時驗證了算法的有效性。葛顯龍和竹自強[5]設(shè)計并改進(jìn)的禁忌搜索算法來解決基于換電策略的EVRPTW。賈永基等人[6]使用模擬退火算法結(jié)合變鄰域的混合啟發(fā)式算法來解決考慮時變速度和動態(tài)需求的EVRPTW。以上研究表明智能優(yōu)化算法能夠有效的解決EVRPTW 問題，因此本研究也使用智能優(yōu)化算法來解決EVRPTW 問題。

因為電動車輛具有明顯的“里程焦慮”，因此研究中考慮電量消耗變得十分必要。當(dāng)前在EVRPTW 中考慮電量消耗的研究較少，大多EVRPTW 的研究重點考慮充電策略對路徑規(guī)劃的影響。針對電動車?yán)m(xù)航問題，李進(jìn)[7]提出一種基于換電模式的EVRP，建立了考慮電動車使用成本以及能量消耗成本的規(guī)劃模型，同時使用改進(jìn)的遺傳算法來求解對應(yīng)模型。針對電動汽車路徑規(guī)劃問題，學(xué)者李嘉等人[8]將載重和車輛旅行距離作為電動汽車能耗影響因素來進(jìn)行研究，通過基于模擬退火和變鄰域搜索的混合啟發(fā)式算法來求解問題。Desaulniers 等人[9]研究了不同充電策略對電動送貨卡車在有軟時間窗限制的情況下向客戶配送貨物的總成本影響。楊珺等[10]在忽略載重速度對能量消耗影響的條件下，同時考慮物流配送系統(tǒng)中充電站選址與路徑優(yōu)化問題，建立相應(yīng)模型，通過禁忌搜索與改進(jìn)Clarke-Wright 節(jié)約的多階段算法來求解問題模型。對于電動汽車能耗問題，甘俊偉等人[11]在對生鮮背景下EVRPTW 的研究中建立能耗估算模型，通過使用貪心算法來求得模型的最優(yōu)解。Zou 等人[12]在考慮速度與載重的因素下，建立了以行駛速度為決策變量的數(shù)學(xué)模型，通過啟發(fā)式算法對問題進(jìn)行求解。

通過Fetene 等人[13]的研究可知，電動車量的電量消耗與車輛的載重、速度、行駛距離有關(guān)。對行駛速度進(jìn)行優(yōu)化能夠減少車輛電量的消耗，傳統(tǒng)的EVRPTW 的研究通常假設(shè)車輛速度是固定的常量，不考慮速度變化對能量消耗的影響，同時車輛的行駛速度在實際運輸過程中是允許被調(diào)節(jié)的。因此本研究在EVRPTW 背景下對行駛速度以及能量消耗進(jìn)行了綜合考慮。

1 模型構(gòu)建

1.1 問題描述

本研究以完全圖G (N,A)來表示行駛網(wǎng)絡(luò)，N={0,1,2,…,n}為位置點集合，C={1,2,…,n}為需求客戶集合，A={(i,j);i,j∈A}為兩位置點之間弧的集合，0 為倉庫，即配送中心，D=(dij)為任意兩點之間的距離集合，研究車輛為同質(zhì)車輛，K={1,2,…,m}代表車輛集合，m 為車輛允許的最大使用數(shù)，車輛裝載量為Q。初始電量為B，bij表示弧(i,j)消耗電量vij表示在弧(i,j)上的行駛速度,]表示弧(i,j)行駛速度的范圍，為行駛速度的下限，為行駛速度的上線，行駛速度范圍通過時間窗約束與道路允許速度范圍進(jìn)行確認(rèn)。[ei,li]表示行駛網(wǎng)絡(luò)中各個地點的允許服務(wù)的時間窗口，ei為地點i 最早允許服務(wù)時間，li為地點i最遲允許服務(wù)時間。時間窗口為硬窗口，即不允許晚點開始服務(wù)，但可以在提前到達(dá)的情況下等待。ai表示車輛到達(dá)顧客點i的時刻，si為車輛在顧客點i 的服務(wù)時間。qi表示顧客點i 的需求量。決策變量為vij和Xijk。

不同于傳統(tǒng)的EVRP，本研究在滿足約束條件的情況下將對兩點間弧的行駛速度進(jìn)行優(yōu)化，以達(dá)到總成本最優(yōu)。本研究的目標(biāo)就是尋找最優(yōu)的車輛、路線和路線上的速度，使得在滿足約束的條件下達(dá)到總成本最小化。為了便于模型建立，研究假設(shè)路況與道路狀態(tài)良好。

本研究設(shè)定的約束條件如下：車輛從倉庫出發(fā)服務(wù)需求客戶配送，服務(wù)完所有需求客戶后返回配送中心；每個需求顧客點都需被訪問并且僅允許訪問一次；每條配送路線的顧客總需求不允許超過車載量Q；每條配送路線的顧客總電量消耗不大于B。車輛在每個弧段的行駛速度必須滿足行駛速度范圍約束。

1.2 電動汽車能量消耗模型

多數(shù)關(guān)于EVRP 的研究將汽車的能量消耗建模為行駛距離或者速度的線性函數(shù)。將速度與能耗關(guān)系簡化為線性關(guān)系，在一定程度上影響車輛能耗的準(zhǔn)確性。本文采用Goeke 和Schneider[14]研究中開發(fā)的模型來計算電池能量的消耗，該能耗估算方法分為三個步驟。首先根據(jù)Bektas 和Laporte[15]所提出的模型確定車輛機(jī)械功率PM，機(jī)械效率需要克服滾動阻力和空氣動力阻力，并且受到重力影響。其中：W 表示車輛自重，U 表示車輛載重，a 表示加速度，本研究不考慮加速與制動過程，因此a=0。cd表示空氣阻力常數(shù)，ρ 表示空氣密度，A 表示車輛前方最大表面積，g 為重力常數(shù)，z 表示坡度角，cr為行駛摩擦系數(shù)。

根據(jù)Goeke 和Schneider 研究中發(fā)現(xiàn)的關(guān)系，將PM被轉(zhuǎn)換成電機(jī)需要提供所需機(jī)械功率的電能PE。如公式（2）所示，其中φ 是通過將y 軸為零的齊次線形回歸線擬合到一組觀測值得到的回歸系數(shù)。

在不考慮環(huán)境溫度以及電池當(dāng)前充電水平的情況下，使用電池電能PE與電池能PE的轉(zhuǎn)換關(guān)系如公式（3）所示。其中φ 代表電池效率的回歸系數(shù)。

通過以上三個步驟以及每條兩點間的行駛時間tij確定的情況下，可以得出電動汽車每兩點間的電池能耗bij的計算公式（4），其中Pij為弧(i,j)的機(jī)械效率PM：

由式（5）可以確定電池能耗與速度、載重和行駛距離有重要關(guān)系，其中電量消耗與速度呈非線性關(guān)系。同時在具有時間窗約束以及載重距離確定的條件下，存在一個最優(yōu)速度使得電量消耗達(dá)到最小。

電能消耗公式有關(guān)參數(shù)設(shè)置：引力常數(shù)g 為9.81m/s2，摩擦系數(shù)cr為0.1，阻力系數(shù)cd為0.7，密度ρ 為1.204 1kg/m3，電動車電量能耗效率回歸系數(shù)φ 為1.184 692，放電模式下電池效率的回歸系數(shù)φ 為1.112 434。

1.3 建立成本優(yōu)化模型

基于以上描述，建立的成本優(yōu)化模型如公式（6）至公式（16）。

目標(biāo)函數(shù)式（6）表示求解最小總成本，包括啟動車輛成本、能量消耗成本、里程成本（司機(jī)成本、其他路費）以及不滿足時間窗約束、載重約束、電量約束的懲罰成本；式（7）與式（8）表示每個客戶點必須被訪問且僅被訪問一次的約束；式（9）為配送中心約束，即所有車輛均從配送中心出發(fā)，服務(wù)結(jié)束后返回配送中心；式（10）表示每輛車的容量約束；式（11）表示每輛車的電量約束；式（12）與式（13）為需求客戶的時間窗約束，M 為足夠大的整數(shù)；式（14）與式（15）為到達(dá)時間、等待服務(wù)時間的約束條件；式（16）表示決策變量的約束條件。符號定義如表1 所示。

表1 符號含義

2 兩階段啟發(fā)式算法

EVRPTW 是一種顯著的NP 難問題，本研究中將速度作為決策變量，采用一種兩階段算法進(jìn)行路徑與速度優(yōu)化。算法基本思想：第一階段，通過使用模擬退火算法來優(yōu)化不同固定速度v*下的路徑，通過目標(biāo)函數(shù)來判斷不同固定速度v*下的最優(yōu)路徑，選擇其中最優(yōu)固定速度v*和路徑信息作為第一階段的解。

第二階段，通過第一階段所得速度以及路徑信息，確定各弧段允許的速度范圍，具體方式為：通過客戶時間窗確定時間窗約束下的速度范圍，其中最小速度不能小于道路允許速度，為了避免局部優(yōu)化破壞全局優(yōu)化，因此弧段最大速度為第一階段全局最優(yōu)速度。接著利用遺傳算法對路徑中各弧速段度進(jìn)行優(yōu)化改進(jìn)，同時計算總成本。

具體步驟如下：

（9）讀取路徑信息，確定客戶點配送順序，根據(jù)確定客戶時間窗與道路允許速度確定弧段速度上下限，生成初始種群。

（10）計算初始種群中各個個體適應(yīng)度，將初始種群中最優(yōu)個體設(shè)置為bestV，接著進(jìn)行選擇、交叉、變異操作產(chǎn)生新的子種群newV。

（11）計算所得新種群的適應(yīng)度，若滿足f (newV)

（12）判斷迭代次數(shù)是否達(dá)到終止循環(huán)的次數(shù)。若達(dá)到則輸出最優(yōu)速度，否則繼續(xù)（9）—（11）步驟。

（13）更新全局能耗量、總時間、總成本并輸出結(jié)果，算法結(jié)束。

3 數(shù)值實驗

3.1 實驗算例構(gòu)造

本研究算法使用MatlabR2020b 實現(xiàn)，運行在Intel i5-6200U、內(nèi)存8G 的筆記本電腦上。利用Solomon's 標(biāo)準(zhǔn)算例（R1、R2、C1、C2、RC1 和RC2）進(jìn)行數(shù)值實驗。該算例根據(jù)客戶地理分布規(guī)律，被分為隨機(jī)分布（R1、R2）、集群分布（C1、C2）和二者混合分布（RC1、RC2），分別選取客戶數(shù)為25，50，100 的算例，對每組測試實例進(jìn)行10 次計算，取運算所得的最優(yōu)解作為該組測試實例的實驗結(jié)果。

算法參數(shù)設(shè)置如下：道路允許速度范圍設(shè)為[40,80]km/h，速度搜索步長6，SA 算法T0為1 000，λ 為0.9，最低溫度為0.000 1，當(dāng)前溫度下的鏈長L0=100。電動汽車電池容量B=50kWh，車輛自重為500kg。GA 算法種群大小，最大遺傳代數(shù)和個體長度分別為40,20 和20，選擇概率，交叉概率和變異概率分別為0.95,0.7 和0.01。

與費用有關(guān)的參數(shù)設(shè)置：車輛啟動成本c1為200 元/輛，能耗成本c2為2 元/千瓦時，行駛里程成本c3為1.5 元/千米。車輛早于允許服務(wù)時間的懲罰系數(shù)為0，車輛晚于允許服務(wù)時間的懲罰系數(shù)為1 000。車輛負(fù)荷過載懲罰系數(shù)為10 000，電量約束系數(shù)為10 000。

3.2 運行結(jié)果分析

使用本研究提出的兩階段啟發(fā)式算法得到的計算結(jié)果如表2 所示，固定速度V*為第一階段優(yōu)化所得。表2 中C、T、W、B分別代表配送過程所需總成本、總時間、等待時間以及配送過程中的能耗量。通過表2 可以得出，隨著算例的類型以及規(guī)模發(fā)生變化，算法第一階段得到的全局最優(yōu)速度也會發(fā)生變化，速度變化范圍為54～66km/h。對比不同類型的算例可以得出，在同等客戶點數(shù)條件下，隨機(jī)分布（R1、R2）算例相較于集群分布（C1、C2）算例所需成本更高，二者混合分布（RC1、RC2）算例所需成本處于隨機(jī)分布與集群分布之間。同時可以看出在同等客戶數(shù)條件下，不同分布類型所需配送時間，等待時間以及能量消耗是不同的，相較于其他兩種分布類型，集群分布（C1、C2）算例在相同客戶數(shù)條件下所需配送時間，等待時間更多，能量消耗更少。

表2 兩階段啟發(fā)式算法計算結(jié)果

表3 為第一階段固定速度與第二階段弧段優(yōu)化速度對比結(jié)果，其中ΔC 表示兩階段成本差，ΔT 表示兩階段時間差，ΔW 代表兩階段等待時間差，ΔB 代表兩階段能耗量之差。

表3 兩個階段計算結(jié)果對比

對比第一階段與第二階段所得結(jié)果，弧段速度優(yōu)化下所得到的時間結(jié)果相對于第一階段固定速度下得到的行駛時間只有輕微變化，行駛時間變化在-0.2～0.2 之間。但不同優(yōu)化策略下的等待時間卻有明顯變化，第二階段所得結(jié)果相較于第一階段等待時間平均減少2.93%。電量消耗結(jié)果也有明顯變化，第二階段所得結(jié)果相較于第一階段電量消耗平均減少12.6%。配送過程所需總成本也有變化，第二階段所得結(jié)果相較于第一階段配送總成本平均減少1.5%。

上述內(nèi)容說明算法第二階段對弧段速度進(jìn)行優(yōu)化能夠改進(jìn)一階段解得質(zhì)量。同時表3 結(jié)果表明，針對相同類型的不同客戶數(shù)的算例，客戶數(shù)量越多，兩階段啟發(fā)式算法所減少的電量消耗，等待時間以及總成本越顯著。

4 結(jié)論

本研究在EVRPTW 模型的基礎(chǔ)上，采用考慮速度與載重的電量消耗計算方法，將速度作為目標(biāo)函數(shù)的決策變量，建立了考慮速度、載重與能耗的帶時間窗的EVRP 模型。通過使用兩階段啟發(fā)式算法來求解所建模型，首先使用SA 算法進(jìn)行全局速度與路徑優(yōu)化，得到滿足約束條件的最優(yōu)路徑以及全局最優(yōu)速度；其次使用GA 算法對弧段速度進(jìn)行優(yōu)化，從而得到考慮能耗與速度的最優(yōu)總成本。

為了證明模型以及算法的有效性，通過Solomon 標(biāo)準(zhǔn)算例構(gòu)建不同類型的EVRPTW 測試算例。實驗結(jié)果表明在載重距離固定的條件下，不同類型、不同數(shù)量的算例的全局最優(yōu)速度會存在差異；在本研究的模型下，考慮弧段速度優(yōu)化的路徑規(guī)劃比全局固定速度下的路徑規(guī)劃能夠更加有效地減少電量消耗，降低總成本。綜上所述，考慮速度優(yōu)化的路徑規(guī)劃能夠更合理的使用能量，減少車輛使用數(shù)目，降低總成本。