考慮回路因素的電動(dòng)汽車(chē)最短路問(wèn)題研究

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

1.2 模型假設(shè)

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

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

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

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

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

圖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被選擇進(jìn)行充電，則xn=1，否則xn=0；yn為在充電站n的充電量；Ln為離開(kāi)節(jié)點(diǎn)n時(shí)的電量；分別為廣義路段a中第k條路段上的旅行時(shí)間，充電站n的排隊(duì)等待時(shí)間、單位充電時(shí)長(zhǎng)；Δ為節(jié)點(diǎn)路段連接矩陣；H(o,d)為起點(diǎn)對(duì)應(yīng)值為1，終點(diǎn)對(duì)應(yīng)值為 -1，其他元素均為零的向量；Li和Lj分別為廣義路段a=i→j起點(diǎn)和終點(diǎn)的電量；yj為在節(jié)點(diǎn)j的充電量；e(k)a為廣義路段a中第k條路段上的耗電量；Lo表示電動(dòng)車(chē)在起點(diǎn)時(shí)電量值；Einitial表示初始電量；M是一個(gè)足夠大的數(shù)，取M=Emax-Esafe，其中，Emax為最大電量，Esafe為安全電量.和Ln為決策變量，均為已知參數(shù).

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

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

3 改進(jìn)的標(biāo)簽設(shè)置算法

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

表 1 改進(jìn)的標(biāo)簽設(shè)置算法步驟Table 1 Steps of revised label-setting algorithm

3.1 標(biāo)簽生成規(guī)則

Step 1中，對(duì)于起點(diǎn)，標(biāo)簽為lo=如果起點(diǎn)是電站，多生成一個(gè)標(biāo)簽，代表在起點(diǎn)充電的選擇，其中，Wo，So分別代表起點(diǎn)充電站的排隊(duì)時(shí)長(zhǎng)、單位充電成本.

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

情形1Ns不是充電站，生成標(biāo)簽ls,1.

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

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

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

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

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

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

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

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

證明若lc代表的任一選擇在到達(dá)Nc時(shí)，旅行成本為T(mén)Nc，剩余電量為ENc，總存在對(duì)應(yīng)的一種選擇，其具有旅行成本則標(biāo)簽會(huì)比lc占優(yōu)，即下述不等式成立.

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

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

4 算例分析

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

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

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

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

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

4.2 算法求解速度對(duì)比

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

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

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

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

5 結(jié)論

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