何 方，羅志雄，楊艷妮，李 萌

(1.清華大學a.工業(yè)工程系，b.土木工程系，北京100084；2.首都經(jīng)濟貿(mào)易大學管理工程學院，北京100070)

0 引言

為緩解傳統(tǒng)機動車尾氣排放所引起的環(huán)境污染問題，政府采取補貼或優(yōu)惠方式鼓勵人們購買新能源汽車，即純電動汽車(EV)或者插入式混合動力汽車(PHEV).EV作為一種完全用電能取代燃油，將污染氣體排放降至0的新型汽車更加受到民眾青睞.受限于電池技術(shù)的發(fā)展，EV在出行過程中存在里程焦慮和充電時間過長等問題[1].此外，現(xiàn)階段路網(wǎng)中所布設的充電站數(shù)量非常有限，在長途出行中難免存在EV繞路充電、排隊充電的現(xiàn)象.

尋找最佳路徑是經(jīng)典的交通網(wǎng)絡優(yōu)化問題之一，在給定的OD對間找到的滿足某些目標函數(shù)(如最小化旅行時間或距離)的路徑被視為最佳路徑，一般用Dijkstra等算法進行求解[2].電動汽車的電池容量有限，在出行過程中涉及充電或更換電池等行為，且耗時較長，傳統(tǒng)模型和算法很難應用于尋求電動汽車的最佳路徑.He等[3-4]考慮電動汽車的充電行為和電量守恒約束，建立以出行花費時間最少為目標的電動汽車最短路徑模型，在此基礎上構(gòu)建電動汽車的網(wǎng)絡均衡模型，并對充電站布設進行優(yōu)化.Zündorf[5]考慮多種類型的充電站，假設充電過程為分段線性函數(shù)，建立電動汽車最短出行時間目標下的路徑規(guī)劃模型.Montoya等[6]建立的電動汽車最短路徑模型中將電池充電水平視為充電時間的曲線函數(shù)，提出基于分段非線性充電函數(shù)的可行路徑求解方法.還有一些研究以能源消耗最少為目標，進行電動汽車最佳路徑規(guī)劃，如Storandt[7]提出一種將電池交換站視為充電的方法.利用預先計算的輔助圖來獲得能源消耗最少目標下的最短路徑.國內(nèi)學者很少對電動汽車最短路徑問題進行專題研究，張建寰等[8]針對不同道路交通狀況下電動汽車充電路徑選擇問題，提出一種路況信息影響下的電動汽車充電路徑規(guī)劃方法；郭放等[9]提出考慮貨物分類需求的電動汽車路徑優(yōu)化與換電策略問題，并建立了該問題的整數(shù)規(guī)劃數(shù)學模型.

本文在He等[3]建立的EV最短路徑模型的基礎上，考慮EV長途出行中存在的繞路充電、排隊充電等行為，基于重構(gòu)路網(wǎng)的方法，建立考慮回路因素的電動汽車最短路徑混合整數(shù)規(guī)劃模型.并基于動態(tài)規(guī)劃思想，提出改進后的標簽設置算法，以提高該問題在大規(guī)模路網(wǎng)中的求解效率.

1 路網(wǎng)重構(gòu)和模型假設

1.1 路網(wǎng)重構(gòu)

以圖1所示案例說明路網(wǎng)重構(gòu)的過程.假設車輛最大旅行距離為12，各充電站單位充電成本相等，各路段的旅行時間和耗電量數(shù)值相等，如圖1(a)所示.以初始電量(起點)或最大電量(充電站)出發(fā)不經(jīng)過充電即可到達其他充電站或終點的路徑定義為可行路徑.對于起終點相同的路徑1和路徑2，假設其旅行時間分別是t1和t2，電量消耗分別是e1和e2，如果t2≥t1，e2＞e1或t2＞t1，e2≥e1，則稱路徑2不占優(yōu).路網(wǎng)重構(gòu)步驟如下：

(1)求出起點到各充電站，不同充電站之間，起點至終點，以及各充電站到終點的所有可行路徑.

(2)剔除步驟(1)中不占優(yōu)的路徑，將起、終點和充電站視為路網(wǎng)節(jié)點，對應路徑視為路段，形成初步重構(gòu)后的路網(wǎng)，如圖1(b)所示.

(3)將步驟(2)所形成路網(wǎng)中連接兩個節(jié)點的不同路段等效為一條廣義路段，形成最終的重構(gòu)路網(wǎng)，如圖1(c)所示.

圖1(a)原路網(wǎng)中，電動汽車從起點到終點的最短路為1-3-4-5-9-10-15-14-15-22-20，繞路充電表現(xiàn)為“15-14-15”.傳統(tǒng)建模中，每一個節(jié)點的電量僅由一個變量表示，無法刻畫出該繞路充電行為.在重構(gòu)路網(wǎng)中，電動汽車不可能在同一個充電站進行兩次及以上充電，故可以用于繞路充電行為下的最短路徑建模.如圖1(c)重構(gòu)路網(wǎng)所示，最短路變化為1-5-14-20.

1.2 模型假設

基于重構(gòu)的路網(wǎng)構(gòu)造，考慮回路因素的電動汽車最短路問題的基本假設如下：

①駕駛員以總出行時間消耗最少為目標進行路徑選擇和充電站選擇.總時間成本包括行駛過程經(jīng)過各個路段的旅行時間與在各個充電站的充電時間之和.

②電動汽車的電量必須保持在安全電量以上.電動汽車在行駛至下一個充電站之前，需要選擇可行的路段保證其電量不低于安全電量.電動汽車旅途中會經(jīng)過數(shù)個充電站，不同類型充電站的排隊時間和充電速度存在差異，駕駛員在已知這些信息的情況下進行充電站及充電量的決策.

2 混合整數(shù)規(guī)劃模型的建立

基于上述模型假設和重構(gòu)路網(wǎng)，建立一個混合整數(shù)規(guī)劃模型描述存在回路的電動汽車最短路徑問題.假設重構(gòu)路網(wǎng)為G(N′),A′，N′表示路網(wǎng)中所有節(jié)點n的集合，N′c代表所有充電站的集合，A′表示所有廣義路段a集合，Ka表示組成廣義路段a的實際路段總數(shù).在已知特定旅程起終點分別為o和d的前提下，該混合整數(shù)規(guī)劃模型可以刻畫出行者如何選擇行駛路段、充電站及充電量，最終生成一個總旅途時間最小的行駛路徑.模型具體形式為

圖1 路網(wǎng)重構(gòu)示例Fig.1 Road network restruction example

式中：xa為0-1變量，如果廣義路段a被使用，則xa=1，否則xa=0；為0-1變量，如果廣義路段a中的第k條路段被使用，則為0-1變量，充電站n被選擇進行充電，則xn=1，否則xn=0；yn為在充電站n的充電量；Ln為離開節(jié)點n時的電量；分別為廣義路段a中第k條路段上的旅行時間，充電站n的排隊等待時間、單位充電時長；Δ為節(jié)點路段連接矩陣；H(o,d)為起點對應值為1，終點對應值為 -1，其他元素均為零的向量；Li和Lj分別為廣義路段a=i→j起點和終點的電量；yj為在節(jié)點j的充電量；e(k)a為廣義路段a中第k條路段上的耗電量；Lo表示電動車在起點時電量值；Einitial表示初始電量；M是一個足夠大的數(shù)，取M=Emax-Esafe，其中，Emax為最大電量，Esafe為安全電量.和Ln為決策變量，均為已知參數(shù).

目標函數(shù)為最小化道路旅行時間、充電等待時間和充電時間之和.約束條件：式(1)為道路流量守恒約束；式(2)表示若廣義路段a被使用，則只使用其中一條路段，否則該廣義路段中的所有路段均不會被使用；式(3)表示每一條廣義路段上的電量守恒，當廣義路段a被使用時，，否則無約束；式(4)保證電動汽車能夠順利通過廣義路段a=i→j；式(5)保證電動汽車的電量不超過電池的最大值；式(6)表示起點時的電量等于初始電量；式(7)為充電電量約束；式(8)和式(9)均為0-1變量約束；式(10)表示非充電站的節(jié)點不能選擇充電.

上述混合整數(shù)規(guī)劃模型可使用商業(yè)規(guī)劃求解軟件進行求解.但當自變量很多，且應用于大型路網(wǎng)時，求解速度很慢，這是因為充電站和起終點間可行占優(yōu)路徑的枚舉極其耗費計算資源.受動態(tài)規(guī)劃思想的啟發(fā)，提出改進的標簽設置算法(Revised Label-setting Algorithm)進行求解.

3 改進的標簽設置算法

該算法既適用于原始路網(wǎng)，也適用于重構(gòu)路網(wǎng).以原始路網(wǎng)為例，給出算法流程.為簡單起見，將電動汽車電量的單位設為km，充電成本單位設為min.定義一個標簽為一個向量，即其中：Nc代表當前節(jié)點，Np為之前節(jié)點，若Nc為起點，則Np=0；Tc,Ec,Wc,Sc分別表示從起點到達上一個進行充電的充電站的時間成本、電量消耗，以及該充電站的排隊時長、單位充電成本(min/km)；tc,ec分別表示從上一個進行充電的充電站出發(fā)后，到達當前節(jié)點的時間成本、電量消耗.如果汽車到達當前節(jié)點之前沒有充電，則Tc,Ec,Wc,Sc均為0，tc,ec表示從起點出發(fā)到達當前節(jié)點的時間成本和電量消耗.算法具體步驟如表1所示.

表 1 改進的標簽設置算法步驟Table 1 Steps of revised label-setting algorithm

3.1 標簽生成規(guī)則

Step 1中，對于起點，標簽為lo=如果起點是電站，多生成一個標簽，代表在起點充電的選擇，其中，Wo，So分別代表起點充電站的排隊時長、單位充電成本.

Step 2中，為不失一般性，以?1中的一個標簽lc=[Np,Nc,Tc,Ec,Wc,Sc,tc,ec]和其直接相連的下一個節(jié)點Ns進行說明.令a代表路段(Nc,Ns)，并令ea代表該路段的電量消耗.若Emax-(ea+ec)≥Esafe，則電動汽車能夠到達Ns(當Tc=Ec=Wc=Sc=0，條件為Einital-(ea+ec)≥Esafe).若電動汽車能夠到達Ns，根據(jù)以下4種情形，生成對應的標簽，如表2所示.

情形1Ns不是充電站，生成標簽ls,1.

情形2Ns為充電站，且是第1次充電，生成標簽ls,1和ls,2.

情形 3Ns為充電站，非第1次充電，且Ss≤Sc，生成標簽ls,1和ls,3.

情形 4Ns為充電站，非第1次充電，且Ss＞Sc，生成標簽ls,1和ls,4.

表2 標簽構(gòu)造結(jié)果Table 2 Labels' formulation

標簽生成中，上一次充電的最優(yōu)電量(情形3和4)滿足“高少低多”原則，即如果上一次充電的充電站的充電成本高于或等于當前充電站，則在上個充電站充剛好到達當前充電站的電量，否則在上個充電站選擇充滿.

3.2 標簽占優(yōu)性規(guī)則

對于路徑中的任何節(jié)點Nc，標簽將會比lc占優(yōu)，如果終點時，對于任何源于lc的標簽，都存在一個源于且成本更低或相等的標簽.顯然，在標簽設置算法中(Step 3)，剔除一些不占優(yōu)的標簽也不會失去最優(yōu)選擇.標簽的占優(yōu)性測試方法如下.

推論1如果同時成立，則標簽占優(yōu).

證明若lc代表的任一選擇在到達Nc時，旅行成本為TNc，剩余電量為ENc，總存在對應的一種選擇，其具有旅行成本則標簽會比lc占優(yōu)，即下述不等式成立.

式中：yc和是上一次充電量.對于任何yc，令，則可推導推論1中的占優(yōu)測試條件.

標簽生成規(guī)則能夠生成最優(yōu)選擇，最優(yōu)選擇對應的各個標簽是占優(yōu)的，不會被刪除掉.由此，算法能夠生成最優(yōu)路徑選擇結(jié)果.該算法總標簽數(shù)為O(2CN2)，其中，C為充電站數(shù)量，N為路網(wǎng)節(jié)點數(shù)量.若充電站數(shù)量已知，該算法為多項式時間算法.

4 算例分析

4.1 與傳統(tǒng)模型對比

將所建立的EV最短路模型與傳統(tǒng)模型，即He等[3]建立的EV最短路徑模型，進行對比分析.實驗路網(wǎng)為Sioux-Falls路網(wǎng)，如圖2所示，圖中各雙向?qū)ΨQ路段括號內(nèi)兩個數(shù)值分別表示旅行時間(min)和路段長度(km).充電站分別設置在節(jié)點11和16，等待時間分別2 min和14 min.測試OD對及初始里程分別為：(1，13)，55 km；(5，24)，45 km；(7，20)，35 km.

圖2 Sioux Falls路網(wǎng)Fig.2 Sioux Falls network

本算例假設：電動汽車的最大電池容量為30 kWh，充電速度為2 min/kWh；電動汽車每kWh電量平均行駛里程為5 km，電動汽車里程焦慮值為25 km，對應電量為5 kWh.通過換算，電動汽車每分鐘補充里程為2.5 km，最大里程為150 km.運用兩個不同的模型求解電動汽車最短路徑，結(jié)果如圖3所示.可以看出：由于OD對(1，13)初始里程較高，在此過程中無需充電，兩個模型求解結(jié)果相同；OD對(5，24)行程較遠，需要在途中充電，但無須繞路充電，兩種模型最終選擇結(jié)果均一致；OD對(7，20)，考慮到18～20為城市快速路網(wǎng)，旅行時間較短，選擇路徑1(7-18-16-18-20，時間成本為33.04 min，充電里程為11.6 km)比路徑2(7-18-16-17-19-20，時間成本為34.96 min，充電里程為13.4 km)總成本更少，故選擇路徑1更有優(yōu)勢.算例結(jié)果表明，本文基于路網(wǎng)重構(gòu)所提出的模型能夠求解出存在回路的路徑，克服了傳統(tǒng)模型的缺點.

圖3 兩種模型對比結(jié)果Fig.3 Comparing results of two models

4.2 算法求解速度對比

本算例仍基于Sioux Falls路網(wǎng)，從已有研究的數(shù)據(jù)中選取了76個OD對[10]，并設定初始里程均為35 km.為比較不同模型及算法求解速度的差異：首先，通過Matlab調(diào)用商業(yè)規(guī)劃軟件(Cplex12.8)直接求解傳統(tǒng)模型和考慮繞路因素的新模型；然后，與改進后的標簽設置算法求解速度進行對比.求解平均耗時結(jié)果如表3所示，針對76個OD對求解的時間分布圖如圖4所示.

求解效率方面，運用商業(yè)規(guī)劃軟件求解所提的新模型稍快于求解傳統(tǒng)模型，耗時離散程度較小，這是由于新模型是基于重構(gòu)路網(wǎng)建立的，與原始路網(wǎng)相比，節(jié)點和路段數(shù)量明顯縮減，使新模型的求解速度較快.此外，運用所提的改進的標簽設置算法進行求解的效率顯著高于商業(yè)規(guī)劃軟件，且耗時離散程度大幅減小，證明該算法能夠高效求解存在回路的大規(guī)模路網(wǎng)中出行需求旺盛時的電動汽車最短路徑問題，為快速求解電動汽車的交通均衡問題奠定了重要基礎.

表 3 不同求解算法的平均耗時Table 3 Average solving time of different algorithm

圖4 不同模型算法求解時間分布圖Fig.4 Solving time distribution under different model and algorithm

5 結(jié)論

本文針對電動汽車繞路充電現(xiàn)象下的最短路徑問題，提出路網(wǎng)重構(gòu)的思想，基于重構(gòu)路網(wǎng)建立混合整數(shù)規(guī)劃模型，克服已有模型無法求解路網(wǎng)中存在回路這一難點.為進一步提高在大規(guī)模路網(wǎng)中的求解效率，提出改進的標簽設置算法.經(jīng)驗證，該算法極大地提高了大規(guī)模路網(wǎng)且存在回路的電動汽車最短路問題的求解速度.實現(xiàn)快速枚舉最短路，為求解電動汽車網(wǎng)絡均衡問題奠定了重要基礎，對于開發(fā)完善的電動汽車路徑導航系統(tǒng)具有一定的參考價值.