李默涵，毛李帆，鄭從鎮(zhèn)，石進永，汪映輝

(1.海南電網(wǎng)有限責任公司，海南 海口 570100；2.國電南瑞科技股份有限公司，江蘇 南京 211106)

在空氣污染和能源短缺的雙重壓力下，電動汽車作為代替燃油車的交通工具應運而生。近年來，國家出臺了大量優(yōu)惠政策，電動汽車得以迅速發(fā)展，一些物流公司也開始使用電動汽車來進行貨物配送服務，而配送時選擇合適的行駛路線可以有效降低配送成本[1]。1959年，Dantzing和Ramser首次提出車輛路徑問題(vehicle routing problem，VRP)的概念——通過設計車輛行駛路線來完成在配送中心和客戶之間運輸貨物的目的，同時追求行程短、耗時少、成本低等目標。1988年，Solomon通過在基礎VRP模型中添加時間窗約束，首次構建了帶時間窗的車輛路徑問題(vehicle routing problem with time windows，VRPTW)模型[2]。隨著電動汽車的快速發(fā)展，電動汽車的路徑問題隨之而生。相較于燃油車的路徑問題，電動汽車的路徑問題需要考慮電動汽車的電池續(xù)航及充電站位置等因素。Jun Yang等人提出了考慮載重量的電動汽車路徑問題，采用快速充電且允許多次充電的方式，但未考慮客戶服務時間窗[3]。2014年，Schneider等人提出了帶時間窗的電動汽車路徑問題，添加了時間窗約束條件，要求車輛在規(guī)定時間內(nèi)到達目的地[4]，具有現(xiàn)實意義。近年來，國內(nèi)外對VRP及其衍生問題進行了研究，提出了許多優(yōu)秀的解決方案，但現(xiàn)有對電動汽車路徑問題的研究均未考慮到充電站對電動汽車的容納量，即認為充電站的容納量是無限大的，所有電動汽車到達充電站后都可以立即充電。然而，由于電動汽車保有量日漸增大，充電站內(nèi)經(jīng)常會出現(xiàn)排隊等待充電的情況，這使得將現(xiàn)有文獻的解決方案運用于實際時會出現(xiàn)或大或小的偏差。

為了研究排隊等待對路徑問題解造成的影響，并完善電動汽車路徑問題的解決方案，本文基于現(xiàn)有文獻，通過分析時間窗、電動汽車容量、充電站排隊時間、充電站位置、電動汽車充電曲線、電池荷電狀態(tài)(state of charge，SOC)等約束條件，建立考慮充電等待時間的帶時間窗的電動汽車路徑問題模型，并采用自適應大規(guī)模鄰域搜索(adaptive large neighborhood search，ALNS)算法對路徑問題模型進行求解，最后通過物流電動汽車運行算例驗證所提模型的有效性。

1 問題描述

考慮到電動汽車電池容量及充電站位置的約束，在保持時間和能源可行性的同時，需挖掘1套經(jīng)過所有客戶點的行駛路徑，同時該路徑需要滿足充電需求和軟時間窗[5]。路徑中設有充電站供電動汽車充電，站內(nèi)假定只配備1臺充電設施，因此到達充電站的電動汽車可能需要排隊等待充電?？蛻粲蟹諘r間窗的要求：如果電動汽車在客戶要求的最早服務時間前到達客戶點，就會產(chǎn)生等待時間成本；如果電動汽車晚于客戶要求的最晚服務時間到達客戶點，則會產(chǎn)生遲到懲罰成本。此外，還需考慮電動汽車的固定購置成本及電動汽車司機的薪酬成本。問題的目標是確定滿足所有約束條件的最低成本路線。

假設每個充電站只配有1個充電設施，且電動汽車到達充電站符合平均值為λ的泊松分布。每個充電站都可以作為1個排隊系統(tǒng)，電動汽車為排隊實體。當電動汽車在充電設施空閑時到達充電站，立即進行充電；如果電動汽車在充電設施工作時到達充電站，則必須等待較早到達充電站的車輛完成充電后，才能進行充電。由于充電站是公共開放的，沒有關于隊列狀態(tài)的預先信息，很難確定服務時間分布函數(shù)[6-7]；因此，服務時間可以從已知均值和標準差的車輛到達率的分布中提取。由于這是具有泊松到達和一般分布服務時間的單個服務器的情況，符合M/G/1排隊系統(tǒng)的特征。

在M/G/1中，字母“M”表示指數(shù)分布的無記憶性。由于電動汽車到達充電站符合泊松分布，連續(xù)2輛電動汽車到達充電站的間隔時間服從參數(shù)為λ的指數(shù)分布。服務時間不屬于特定的分布情況，字母“G”代表服務時間的一般分布；數(shù)字“1”表示排隊系統(tǒng)中只有1臺服務器。設充電時間為Tc，其均值為E(Tc)，方差為D(Tc)。為了滿足系統(tǒng)穩(wěn)定性，充電器的利用率ρ=λE(Tc)應該小于1。

將時間離散化為一系列時間段，用以處理等待時間問題，即用[tm,tm+1]表示開始和結束時間分別為tm和tm+1的時間段m。由于交通密度會隨時間的變化而變化，車輛到達充電站的到達率是一個關于時間的函數(shù)，且由于充電站的地理位置不同，各個充電站的到達率也有所不同[8]。在圖1中，將1 d分為5個時間段，并且展示了充電站S的車輛到達率分布情況。在現(xiàn)實生活中，車輛到達率如圖1中的光滑函數(shù)曲線。

圖1 充電站車輛到達率的時間曲線Fig.1 Time curve of charging station vehicle arrival rate

為了方便建立數(shù)學模型，將時間離散化并通過分段線性函數(shù)來獲得近似的車輛到達率曲線，如圖2所示。同時，為了保持先進先出的特性，在不同時間段之間加入1個短時間的過渡區(qū)，保證較晚到達充電站的車輛不能先于較早到達的車輛離開充電站。

圖2 充電站車輛到達率的分段線性近似曲線Fig.2 Piecewise linear approximate curve of charging station vehicle arrival rate

對于t時刻到達充電站S的電動汽車，隊列中的期望等待時間E(WS(t))可以用M/G/1排隊系統(tǒng)的穩(wěn)態(tài)方程計算，即

(1)

其中

(2)

式中下標S表示充電站。

顯然，E(WS(t))在過渡區(qū)是非線性的，這里采用線性函數(shù)對其進行近似表示[9]，如圖3所示。每一段曲線的等待時間由斜率k和截距g表示，如果電動汽車在時間段m內(nèi)的t時刻到達充電站，則等待時間為g+k(t-tm)。本文假設所有電動汽車均運行于電池SOC為10%～90%的狀態(tài)下，且充電傳輸?shù)哪芰吭?～0.8q之間呈均勻分布，其中q為電池容量；因此，期望充電時間E(Tc)=(0.8q×r)/2=0.4q×r，其中r為充電率。同樣，服務時間的方差為D(Tc)=(0.8q×r)2/12。

圖3 充電站等待時間的分段線性近似曲線Fig.3 Piecewise linear approximate curve of charging station waiting time

2 最小化電動汽車路線成本模型

2.1 電池充電時間函數(shù)

電池充電函數(shù)是一個非線性的連續(xù)凹函數(shù)，為了方便建模，采用1個分段線性曲線函數(shù)來近似表達充電函數(shù)[10]，如圖4所示。圖4中分段點l對應的時間為tl，al表示電池SOC，其中l(wèi)∈B={0,…,b}，B為分段點集合。本文假設所有充電站配備相同的充電設備，即所有電動汽車的充電情況均符合近似充電函數(shù)。

圖4 電池充電過程的分段線性近似曲線Fig.4 Piecewise linear approximate curves in process of battery charging

2.2 問題假設

本文構建模型的目標是使電動汽車行程的總成本最低，為了簡化問題，做出以下假設：

a)行駛過程中，電動汽車電量不足時可以進入充電站充電；

b)每個充電站只有1臺充電設施，電動汽車進入充電站充電可能需要排隊等待；

c)每個客戶都有服務時間窗，電動汽車可以在時間窗外到達客戶點，但早于客戶要求的最早服務時間到達服務點會產(chǎn)生等待成本，晚于客戶要求的最晚服務時間到達客戶點會產(chǎn)生超時懲罰成本[11]；

d)車輛行駛終點具有時間窗特征，晚于要求的最晚到達時間需要向司機支付加班費；

e)每輛電動汽車有一定的載重量，電動汽車所承載的貨物量應在限制載重量之內(nèi)；

f)電動汽車的電池SOC均在10%～90%之間，充入的電能最大為電池容量的80%[12]。

2.3 模型建立

根據(jù)上述定義，建立考慮充電時間的帶時間窗的電動汽車路徑規(guī)劃問題的數(shù)學模型為

(3)

(4)

目標函數(shù)表示為最小化總成本，目標函數(shù)中第1項為電動汽車行駛的電能消耗，與行駛距離有關；第2項為違反客戶時間窗的懲罰成本；第3項為違反行駛終點時間窗的懲罰成本；第4項為電動汽車自身的固定成本；第5項為司機的酬薪成本。

約束條件如下：

a)每個客戶點只能被訪問1次：

(5)

b)充電站最多被訪問1次：

(6)

c)電動汽車均由行駛終點離開并最終返回出發(fā)點：

(7)

d)分別跟蹤離開客戶點和充電站后下個節(jié)點的到達時間：

(8)

式中：ti,0為客戶點i的服務開始時間；tij為節(jié)點i到節(jié)點j的行駛時間；ti,s為客戶點i的服務時間；Tmax為電動汽車行程時間最大限制；S′為充電站及其副本的集合；V0為客戶點和出發(fā)點集合。

tij- (Tmax+tc,max+tw,max+tmax)×

(9)

式中：ril,d為電動汽車離開充電站i時，充電時間曲線分段點l的系數(shù)；ril,a為電動汽車到達充電站i時，充電時間曲線分段點l的系數(shù)；tl為充電時間函數(shù)上分段點l對應的時間；ti,w為電動汽車在充電站i的等待時間；tc,max為將電動汽車電池從10%充電至90%所用的時間；tmax為所有路線中用時最長的時間；tw,max為最長等待時間。

e)分別跟蹤上一節(jié)點為客戶點和充電站的路線總用時：

(10)

式中：ti,N+1為節(jié)點i到行駛終點行駛時間；xi,N+1,m為決策變量，具體描述為

(11)

ti,N+1- (Tmax+tc,max+tw,max+tmax)×

(12)

f)離開節(jié)點i和到達節(jié)點j需要在同一時間段內(nèi)：

(13)

(14)

g)保證返回行駛終點的時間在同一時間段內(nèi)：

tmxi,N+1,m≤fi≤tm+1+Tmax(1-

xi,N+1,m),i∈V′,m∈M.

(15)

h)客戶點服務時間不能早于客戶要求最早服務時間：

ti,e≤ti,0,i∈V.

(16)

式中ti,e為客戶點i要求的最早服務時間。

i)晚于客戶要求最晚服務到達時間到達客戶點時，遲到時間為正值：

ti,v≥(ti,0-ti,z),i∈V.

(17)

式中ti,z為客戶點i要求的最晚服務時間。

j)電動汽車總行程時間需要小于最大時間限制：

ti,t≤Tmax,i∈V′.

(18)

k)晚于行駛終點要求最晚返回時間時，遲到時間為正值：

tN+1,i≥(ti,t-tgb),i∈V′.

(19)

式中tgb為行駛終點時間窗關閉時間。

l)將等待時間與決策變量xij,m建立聯(lián)系：

ti,w(tj,0)≥bj,m+kj,m(tj,0-tm)-tw,max(1-

xij,m),i∈V0,j∈S′,m∈M.

(20)

式中：bj,m為時間段m下充電站j的等待時間函數(shù)的截距；kj,m為時間段m下充電站j的等待時間函數(shù)的斜率。

m)判斷到達和離開充電站i時電動汽車的電池SOC：

(21)

式中ai,a為到達充電站i時的電池SOC。

(22)

式中ai,d為離開充電站i時的電池SOC。

n)分別跟蹤離開充電站和離開客戶或行駛終點的電動汽車電池SOC：

(23)

式中：h為耗電系數(shù)；Vcom為i，j組合的集合。

(24)

o)所有電動汽車電池SOC均在10%到90%之間：

(25)

(26)

p)跟蹤電動汽車的載重量并保證載重量在限制內(nèi)：

0≤u0≤uev.

(27)

式中：u0為電動汽車始發(fā)時的載重量；uev為電動汽車的最大載重量。

(28)

式中：ui為到達節(jié)點i時電動汽車剩余的載重量；uj為到達節(jié)點j時電動汽車剩余的載重量。

q)建立變量zil和yil的關系及電動汽車到達充電站i時的充電時間曲線分段點l的系數(shù)：

(29)

式中zil為決策變量，具體描述為

(30)

(31)

式中yil為決策變量，具體描述為

(32)

r)確保近似充電函數(shù)系數(shù)取值正確：

ri0,a≤zi1,i∈S′.

(33)

ril,a≤zil+zi,l+1,i∈S′，l∈B{0，b}.

(34)

rib,a≤zib,i∈S′.

(35)

ri0,d≤yil,i∈S′.

(36)

ril,d≤yil+yi,l+1,i∈S′，l∈B{0，b}.

(37)

rib,d≤yib,i∈S′.

(38)

s)確保電動汽車不會連續(xù)訪問充電站點：

(39)

t)規(guī)定決策變量的取值范圍：

(40)

zij,m≥0,i∈S′,j∈VN+1,m∈M.

(41)

yib,zib∈{0,1},i∈S′，b∈B.

(42)

ai,a,ai,d,ti,w≥0,i∈S′.

(43)

ti,v≥0,i∈V.

(44)

ti,0,ti,t,tN+1,i≥0,i∈V′.

(45)

ril,a,ril,d≥0,i∈S′,l∈B.

(46)

3 自適應大規(guī)模鄰域搜索算法

ALNS是鄰域搜索算法的衍生算法，可以破壞和修復當前解并產(chǎn)生新的解[13]，將新解與當前解比較以決定是否將新解作為局部最優(yōu)解；同時算法本身可以根據(jù)鄰域解的質量，自主選擇合適的破壞和修復算法來進行鄰域搜索，最終得到整體最優(yōu)解。ALNS算法的基本步驟為：構建初始解和自適應大規(guī)模鄰域搜索。

3.1 構建初始解

初始解可以由構建1個可行的路線來產(chǎn)生。構建可行路線由距出發(fā)點最近的客戶開始，接著計算所有未分配的客戶點，并按照時間窗的要求插入路線中可行點中的成本，然后執(zhí)行成本最低的插入操作[14]。如果由于電動汽車電量不足，無法將客戶點插入路徑中，就將客戶和充電站一起插入到路徑中；如果由于不滿足時間窗或電動汽車載重量滿載的要求，而導致無法將客戶點插入到路線中，則放棄此路線并重復構建過程，直到所有客戶點都被插入到路線當中。由此構建出1條包含所有客戶點并且滿足時間窗的路線，以此作為初始解。

3.2 自適應大規(guī)模鄰域搜索

構建出初始解后，ALNS算法開始迭代改進解，直到滿足停止條件。在迭代過程中，首先執(zhí)行破壞操作，將當前解中的部分客戶點和充電站節(jié)點移除?？蛻酎c的移除數(shù)量γ是均勻分布于客戶點移除最小數(shù)量nc,min和最大數(shù)量nc,max之間的隨機數(shù)?？蛻酎c的移除方式有4種：

a)隨機移除γ個客戶點產(chǎn)生新的路線方案；

b)計算路線中所有中間有1個客戶點的節(jié)點對之間的路線距離，選擇距離最長的γ個節(jié)點對之間的客戶點進行移除操作；

c)計算路線中所有中間有1個客戶點的節(jié)點對之間的路線行駛時長，選擇用時最長的γ個節(jié)點對之間的客戶點進行移除操作[15]；

d)選擇所有與充電站點相鄰的客戶點，計算在這些客戶點于其相鄰的充電站點之間行駛消耗的成本，選擇成本最大的γ個客戶點移除[16]。

在移除了部分客戶點后，可能會出現(xiàn)不再需要部分充電站的情況；計算移除這些不再必需的充電站點目標函數(shù)的減少量，選擇目標函數(shù)減小量最大的充電站點移除；重復這一過程直到路線中不再存在非必需的充電站點[17]。至此，算法迭代一次的破壞操作完成。

破壞操作完成后執(zhí)行修復操作，將移除掉的節(jié)點插入到路線中來嘗試得到更好的路線方案[18]?？蛻酎c的修復操作有2種方式：

a)計算在所有可行節(jié)點對之間插入客戶點而造成的成本增加量，選擇成本增加量最小的節(jié)點對插入客戶點；

b)計算插入客戶點后路線總用時間，選擇總時長最短的位置插入客戶點[19]。

完成客戶點插入后，再進行充電站點的修復操作，通過計算找出電動汽車以負值電量到達的客戶點，并在此客戶點與上一個客戶點之間插入1個對路線距離增加量最小的充電站點[20]。待所有被破壞操作移除的節(jié)點被修復操作插入回路線后，算法完成1次迭代，形成1個新的解。通過比較迭代得到的新解與當前解的目標函數(shù)值來決定是否將新解作為新的局部最優(yōu)解，以及對迭代過程中采用的破壞操作和修復操作進行權重更新。

破壞和修復操作有很多種，每個操作o都有對應的權重ωo和分值πo，較高的分值表示操作的高性能，應該具有更高的選擇幾率。最初所有算法具有相同的權重和同為0的分值，在迭代過程中，如果產(chǎn)生了新的局部最優(yōu)解，本次迭代中采用的破壞和修復操作的分值會增加σ1；如果迭代產(chǎn)生的新解優(yōu)于當前解但不是最優(yōu)解，本次迭代采用的破壞和修復操作的分值會增加σ2；如果迭代產(chǎn)生的新解比當前解要差，則本次迭代采用的破壞和修復操作的分值會增加σ3[21]。每次迭代開始時，每個破壞和修復操作的權重更新為ωo=ωo(1-p)+pπo/θ；其中p為區(qū)間(0,1)之間的隨機數(shù)，θ為自上次分值更新以來操作被使用的次數(shù)[22]。操作的選擇幾率為

ωo/∑k∈Oωk,

(47)

式中O為操作的集合。

4 算例測試與分析

本文采用EVRPTW問題經(jīng)典Benchmark例子[23]，以物流電動汽車為例進行實驗。對上文提出的模型及算法采用Java語言編程，所有實驗運行在英特爾Xeon E5 2.10 GHz處理器16 GB內(nèi)存的虛擬機上。算例中的客戶點有3種分布情況：集中分布(C)、隨機分布(R)和集中隨機分布(RC)。

4.1 實驗設計

本文采用與EVRPTW問題標準集的固定充電速率不同的非線性充電函數(shù)，并用三段線性函數(shù)近似表示，這意味著需要3種不同的充電速率。

實驗將1 d分為5個時間段，并遵照“先進先出”的原則加入過渡區(qū)。假設從交通不擁擠時段過渡到擁擠時段需30 min，由于到達率的增加是外部因素，可以確定到達率增加可以在30 min內(nèi)完成[24]。從交通擁擠時段過渡到交通不擁擠時段，由于充電站排隊等待時間的存在，過渡過程可能會超過30 min。同時，電動汽車在早晨08：00離開配送中心，且必須在晚上20：00前回到配送中心，如果電動汽車在18：00后才回到配送中心，需要支付超時工作成本。等待時間曲線如圖5所示，顯示了1 d內(nèi)不同時刻下的平均排隊等待時間，其中橫坐標表示時刻，縱坐標表示表示等待時間，單位為min。用于對比，實驗中還設計了另一種時不變等待時間的場景，這種場景下，全天各時段的等待時間均相同。

圖5 時變等待時間曲線Fig.5 Time-dependent waiting time curves

模型中的參數(shù)設定為：ce=0.4，cp=1，cf=1 200，cd=1，co=11/6?？蛻酎c移除數(shù)量的參數(shù)設定為：nc,min=min{0.1|N|,30}，nc,max=min{0.4|N|,60}，其中N為算例中客戶點的數(shù)量。

4.2 結果分析

對問題集C、R、RC分別進行等待時間場景及不考慮等待時間場景實驗，得出電動汽車規(guī)劃路徑和成本等數(shù)據(jù)。表1為不同等待時間場景下對目標函數(shù)成本值的影響，其中表格中的數(shù)值為當前場景下的目標函數(shù)成本與不考慮等待時間時的目標函數(shù)成本之比。

由表1可以看出：等待時間會在一定程度上造成成本增加，且時變等待時間造成的成本增加量比時不變等待時間造成的成本增加量要多。此外，在R和RC場景下，等待時間對成本的影響要比在C場景下的影響要大，主要原因是在客戶隨機分布的情況下由于路徑總路程更長而導致更多次的充電，圖6反映了這一情況。

圖6 不同場景下的平均充電次數(shù)Fig.6 Average charging times in different scenarios

表1 不同場景下成本情況Tab.1 Cost situation in different scenarios

圖 7所示為不同場景下各種成本與不考慮等待時間場景下各種成本比值的情況。

由圖7(a)—(c)可以看出：等待時間對總成本、電動汽車固定成本和司機薪酬成本有近似的影響。圖7(d)—(e)可以看出：超時工作的加班費成本和客戶點遲到的懲罰成本的增加量在客戶點集中分布的情況下比較多，這主要是因為在客戶點集中分布的情況下電動汽車數(shù)量沒有大規(guī)模增加而車輛會行駛更長的距離，這就導致會出現(xiàn)更多的客戶點遲到的情況。圖7(f)表明：電能成本相比與其他類型的成本較穩(wěn)定，波動較小。同時，在客戶點集中分布的情況下的電能成本水平非常小。規(guī)劃通過增加電動汽車數(shù)量來避免頻繁充電減少等待時間，這就使得解路線更加緊湊，一輛車訪問不同區(qū)域的客戶點的次數(shù)降低，因此減少了路線總距離，降低了電能成本。

圖7 不同場景的各種成本比較Fig.7 Comparison of various costs in different scenarios

為了探究充電排隊等待對路徑問題決策及成本的影響，圖8所示為各場景下算例的時間段分析。

圖8(a)表明車輛在早上和晚上的充電量較少，結果符合車輛早上充滿電開始配送而晚上配送服務量較少的現(xiàn)實情況。圖8(b)同樣表明了這一行為。為了避免較長的排隊等待時間，以及減少因遲到而導致的成本，算法更傾向于為車隊增加更多的車輛，這就使得完成配送任務所需要的充電次數(shù)和充電量都相對減少。圖8(c)表明充電排隊情況越嚴重，因遲到而導致的成本越高；且由于在早晨充電行為較少，在這一時間段內(nèi)幾乎沒有出現(xiàn)遲到情況，但是到了中午和下午，遲到情況會明顯增多。圖8(d)展示了每種場景下的總能耗，可以看出各場景的總能耗基本一致，這表明路線行駛的總距離不受等待時間的影響，其影響表現(xiàn)在路徑方案在車輛數(shù)量和充電時間上有所不同。

圖8 充電決策和成本的時間分析Fig.8 Temporal analysis of recharging decisions and costs

5 結束語

本文介紹了考慮等待時間的帶時間窗的電動汽車路徑規(guī)劃問題，并針對該問題建立了數(shù)學模型。采用ALNS算法對模型進行求解，從電動汽車行駛終點時間窗角度分析了充電站排隊等待時間對路徑成本的影響?，F(xiàn)實的路徑規(guī)劃問題中，充電站一定會有排隊的情況出現(xiàn)，本文提出的基于M/G/1排隊系統(tǒng)的等待時間建模具有一定的實用性，也為路徑規(guī)劃問題提出了一種有效的解決方法；但也存在一定的不足，即未考慮電動汽車行駛過程中的不確定性情況，如路況、充電站配置情況、電動汽車電池的充放電特性等。針對這些問題，可結合問題情況提出更實用的解決方法。