劉 洪,戚博碩，韓震燾，葛少云，張 強

1. 天津大學 智能電網(wǎng)教育部重點實驗室，天津 300072；2. 國網(wǎng)遼寧省電力有限公司 經(jīng)濟技術研究院，遼寧 沈陽110013)

0 引言

電動汽車作為新型的交通工具，可以有效緩解能源和環(huán)境壓力[1]，因而得到國家的大力推廣。作為電動汽車運行的重要支撐，完善的電動汽車充電服務體系可以促進電動汽車的規(guī)?；瘧?。目前，私人電動汽車主要選擇在充電站或居民小區(qū)進行電能補給。但受到城市土地資源短缺、現(xiàn)階段充電站難以盈利[2]等客觀因素影響，充電站的建設數(shù)量遠低于社會預期，電動汽車在行駛途中很難找到合適的充電站進行充電。而部分居民小區(qū)現(xiàn)有配電網(wǎng)容量有限、電力負荷緊張，不能接納過多電動汽車[3-5]。與此同時，共享經(jīng)濟已漸成規(guī)模：在國內(nèi)，共享燃油汽車現(xiàn)身北京、成都等地，共享電動汽車正在醞釀中；在國外，Car2Go公司已在美國圣迭戈推出共享電動車項目，但由于當?shù)爻潆娫O施短缺，共享電動車運營同樣陷入困境[6]。因此，亟待探索新的充電服務模式，用于解決電動汽車充電難的問題。

無線充電可以作為一種候選充電服務模式，如韓國科學技術學院將充電電纜埋在路面下方的聯(lián)網(wǎng)電動車OHV(Online Electric Vehicle)項目[7]，但和充電站建設類似，高昂的建設費用使得該模式在短時間內(nèi)難以普及。文獻[8]提出移動充電服務的概念，并分析了在物聯(lián)網(wǎng)技術支持下移動充電服務的技術可行性；同時指出移動充電服務可以提高充電設施利用率，有助于充電行為在時間上交錯進行，避免電動汽車無序充電沖擊電網(wǎng)。文獻[9]中認為移動充電服務模式可以解決現(xiàn)階段充電設施覆蓋率不足的問題，并研究了移動充電車容量的經(jīng)濟配置。

移動充電服務運營過程中主要涉及移動充電車的路徑選擇和能源補給兩過程。在車輛路徑選擇方面，文獻[10]研究了移動充電車在接到充電服務請求后在路網(wǎng)中的調(diào)度策略，但并未涉及移動充電車的能源補給策略；文獻[11]考慮加權道路長度，建立了充換電服務網(wǎng)絡中配送車輛路徑選擇模型，文獻[12]建立了動態(tài)路網(wǎng)中單車場、多車輛帶時間窗的車輛路徑模型，并設計相應算法進行求解，但文獻[11-12]未涉及多個車場的車輛路徑問題；文獻[13-14]針對多車場、多車輛帶時間窗的車輛路徑問題，給出“先客戶聚類再規(guī)劃路徑”的兩階段算法，這種方法雖然求解速度較快，但解的質(zhì)量不高。上述研究均是基于靜態(tài)路網(wǎng)的假設且車輛不能重復使用。在移動充電車能源補給領域，由于移動充電車車輛類型易于統(tǒng)一，換電模式可作為移動充電車有效的能源補給方式，文獻[15]以充換電站各時刻的充電功率作為決策變量，建立多目標調(diào)度模型，得出次日優(yōu)化充電計劃；文獻[16]考慮公交車的運行規(guī)律和耗電特性，建立了以充電成本最小為目標的兩階段充電模型。但上述文獻中均假設電池的在充電過程中完全可控，未深入考慮電池荷電狀態(tài)(SOC)、電池數(shù)量和充電機數(shù)量間的匹配關系，所得最優(yōu)解通常難以實現(xiàn)[17]。另外，目前尚未有相關文獻研究如何將兩者結合實現(xiàn)一體化優(yōu)化。

為此，本文提出了包含移動充電車行駛路徑選擇和能源補給的移動充電服務一體化經(jīng)濟調(diào)度模型。分析了移動充電服務運營模式與優(yōu)化調(diào)度框架；針對移動充電車行駛路徑選擇過程，考慮用戶服務時間窗和動態(tài)路網(wǎng)，構建了移動充電車可重復使用的路徑選擇模型，通過優(yōu)化用戶的服務順序和行駛路段使得物流成本最小；針對移動充電車能源補給過程，考慮離散化的電池組荷電狀態(tài)，構建了考慮分時電價的有序充電整數(shù)規(guī)劃模型，在滿足移動充電車換電需求的前提下，通過優(yōu)化不同荷電狀態(tài)電池組的接入時段使得充電費用最??；以移動充電車為紐帶，構建了包含能源服務站-移動充電車-用戶的一體化經(jīng)濟調(diào)度模型并設計算法實現(xiàn)用戶智能分配，對模型進行求解；通過算例分析驗證了模型和算法的有效性。所建模型及仿真結果可以為移動充電服務運營商在移動充電車路徑選擇和能源補給兩方面提供有價值的參考，有助于運營商控制日運營成本，提高經(jīng)濟效益。

1 移動充電服務運營模式及優(yōu)化調(diào)度框架

設置多個能源服務站可以降低物流成本、提高服務效率[14]。移動充電服務運營模式如附錄中圖A1所示。各能源服務站調(diào)度移動充電車從而有序地為用戶充電，當移動充電車內(nèi)電池組剩余電量不足時，車輛返回各自能源服務站更換電池組，之后繼續(xù)服務用戶。能源服務站可對卸載的電池組進行充電、維護。

對于路徑選擇過程，在滿足用戶需求和每條子路徑中移動充電車容量約束的前提下，保證服務質(zhì)量、降低物流成本是運營商追求的目標；對于電池組能源補給過程，在滿足移動充電車換電需求的前提下，運營商期望降低充電成本。顯然，不同的路徑選擇方案會產(chǎn)生不同的換電需求，而未考慮換電能力得到的路徑選擇方案往往是不可行的，因此，需要從整體角度協(xié)調(diào)兩過程，避免決策沖突，得到全局最優(yōu)解。

考慮將兩者結合的移動充電服務運營優(yōu)化調(diào)度框架如附錄中圖A2所示。運營商首先為各個能源服務站動態(tài)安排所需服務的用戶，為每輛移動充電車制定路徑方案，得到物流費用；隨后，根據(jù)路徑方案制定充電計劃，并將充電費用反饋回該路徑方案上。運營商根據(jù)該一體化調(diào)度方案的總費用，重新調(diào)整路徑方案，并重新制定充電計劃，如此循環(huán)迭代至預先設定的最大迭代次數(shù)，得到優(yōu)化結果，實現(xiàn)移動充電服務運營的一體化調(diào)度。

2 移動充電車行駛路徑調(diào)度模型

2.1 動態(tài)路網(wǎng)模型

定義動態(tài)路網(wǎng)模型為G={V,E,fij(t)}，其中V={v1,v2,…,vn}表示路網(wǎng)節(jié)點的集合，E={e1,e2,…,em}表示路網(wǎng)中路段集合，fij(t)表示對每一個路段(vi,vj)∈E的時間代價函數(shù)，t∈[t0,tm]為車輛離開vi的時間，[t0,tm]為問題研究的時間域。

因為人們?nèi)粘３鲂幸?guī)律具有周期性，所以車輛在路段中的行程時間也呈現(xiàn)一定周期性。選用Ichoua等[18]提出的旅行速度分段依賴函數(shù)，該函數(shù)通過路段長度和行駛速度作比計算行程時間，所得行程時間連續(xù)變化，滿足先進先出準則，具體如附錄中圖A3所示。

用T={T0,T1,…,TL}表示時段集合，[Tl-1,Tl]為第l個時段，時段間隔長度記為ΔT，Vij(t)表示t時刻在路段(vi,vj)上的行駛速度，可采用式(1)計算車輛在路段(vi,vj)上的行程時間。

(1)

其中，Tvi,vj(di,t)為t時刻在路段(vi,vj)上已經(jīng)行駛了距離di的車輛繼續(xù)行駛完全程所需的時間；tre為t時刻所在時段的剩余時間，即tre=Tl-t且t∈[Tl-1,Tl)；dij為路段(vi,vj)的長度；dre=treVij(t)，為以t時刻的恒定速度駛完當前時段對應的行駛里程。

2.2 考慮車輛重復使用的移動充電車路徑選擇模型

構建移動充電車路徑選擇模型前，本文進行如下假設：在為移動充電車安排行駛路徑之前已知每個用戶的地理位置、充電需求量、任意用戶可接受充電服務的時間窗；每個用戶只能由一輛移動充電車服務一次；每輛移動充電車以恒定功率為用戶提供充電服務；移動充電車僅在能源服務站和用戶所在節(jié)點停留，在其他路網(wǎng)節(jié)點不停留。

基于上述假設，以移動充電車行駛過程中物流費用最小建立目標函數(shù)如下：

(2)

涉及的約束條件如下。

a. 路徑約束。

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

b. 移動充電車容量約束。

(12)

其中，Qk為移動充電車k的容量，且Qk=NnumCr(?k∈K)，Nnum為移動充電車搭載電池組的額定數(shù)量，Cr為每塊電池組的可用容量。式(12)表示每條子路徑上用戶電量需求總和不超過移動充電車最大容量限制。

c. 能源服務站物流能力約束。

(13)

其中，|Kd|為能源服務站d含移動充電車數(shù)量。式(13)表示各能源服務站調(diào)用移動充電車的數(shù)量不超過該能源服務站擁有的車輛數(shù)量。

d. 用戶時間窗約束。

(14)

(15)

3 電池組有序充電的整數(shù)規(guī)劃模型

為方便對移動充電車換電服務模型進行分析，將全天24 h以Δh(單位為min)間隔等分，分成H個調(diào)度時段，H=24×60/Δh。對模型做出如下假設：① 第t個時段更換下來的電池組最早可在第t+1個時段起始時刻開始充電；② 充電機和電池組采用一對一的恒功率充電方式，出于對電池組壽命的考慮，電池組接入充電機后直至電量到達預設值時方可被換下；③ 移動充電車內(nèi)車載電池通過串并聯(lián)形式組成，通過電池管理系統(tǒng)對電池組內(nèi)電池放電進行控制，因此，可認為移動充電車返回能源服務站換電時各電池組荷電狀態(tài)值相同。

3.1 電池組荷電狀態(tài)離散化

在單位時間步長充電機功率已知的情況下，可將電池按充電所需時段數(shù)分為Z1類：

(16)

其中，SOCmax為電池組最大荷電狀態(tài)；SOCmin為電池組最小荷電狀態(tài)；pc為充電機的額定充電功率；ηc為充電機充電效率；Cr為電池組額定容量；Δh為單位時間步長；「·?表示向上取整。

對于第t個時段回收的第n塊電池組，其充電時段數(shù)Mt,n為：

(17)

通過計算各個時段回收電池組所需充電時段數(shù)，可近似得到各電池組充電時長。

3.2 能源服務站內(nèi)運營建模

對于任意第t個時段，站內(nèi)電池組按狀態(tài)可劃分為[19]：可用電池組S(t)，即第t個時段滿電電池組；待充電池組NW(t)，即在第t個時段之前未接入充電的電池組；在充電池組NA(t)，即第t個時段處于充電狀態(tài)的電池組。

將新入站電池組荷電狀態(tài)進行離散化后，得到規(guī)模為Z×H的二維矩陣Ω，如式(18)所示。

(18)

其中，Ωz,h為第h個充電調(diào)度時段回收充電時長為z的電池組數(shù)量。

能源服務站內(nèi)各狀態(tài)電池組間的轉移關系可表示為：

S(t)=S(t-1)+NC(t)-Nde(t)

(19)

NW(t)=NW(t-1)-NI(t-1)+Nnew(t)

(20)

NA(t)=NA(t-1)-NC(t)+NI(t)

(21)

(22)

(23)

(24)

3.3 單個能源服務站充電優(yōu)化模型建立

區(qū)域內(nèi)各能源服務站運營情況相同，單個能源服務站內(nèi)以充電費用最小為目標，模型如下：

(25)

其中，NCH為該能源服務站內(nèi)充電機數(shù)；X(ic,t)為第ic個充電機在第t個時段的狀態(tài)，X(ic,t)=1表示充電機處于充電狀態(tài)，X(ic,t)=0表示充電機處于其他狀態(tài)；pr(t)為第t個時段的電價。

涉及的約束條件如下。

a. 充電設施約束。能源服務站內(nèi)任意時段在充電池組數(shù)量不能超過站內(nèi)充電機數(shù)量。

NA(t)≤NCH

(26)

b. 待充電池約束。能源服務站內(nèi)任意時刻在接入電池組數(shù)量不能超過該類電池該時刻的電池組數(shù)量。

(27)

c. 能源服務站換電能力約束。為使移動充電服務正常進行，第t個時段站內(nèi)滿電電池組數(shù)量不小于此時移動充電車的換電需求。

S(t)≥Nde(t)

(28)

d. 接入時段約束。因電池充電為持續(xù)充電過程，為避免對下一調(diào)度周期產(chǎn)生影響，充電負荷不應持續(xù)到下一調(diào)度時段。則第z類電池允許接入時段為：

t∈[1,H-z]

(29)

4 移動充電服務一體化經(jīng)濟調(diào)度模型

4.1 兩過程的關聯(lián)方程

移動充電車為用戶服務充電的過程與能源服務站內(nèi)電池組有序充電的過程，體現(xiàn)了移動充電車的載體特性，這期間產(chǎn)生電能的轉移。能源服務站內(nèi)電池組的優(yōu)化過程與移動充電車路徑選擇方案密切相關。

k1(t)輛移動充電車在第t個時段從能源服務站出發(fā)，換電需求如式(30)所示。

Nde(t)=Nnumk1(t)k1(t)∈Kd

(30)

k2(t)輛移動充電車在第t個時段返回能源服務站，將新入站電池組荷電狀態(tài)離散化，更新式(18)；根據(jù)假設 ①，時段t回收電池組數(shù)量影響時段t+1待充電池數(shù)量，得到式(31)。

Nnew(t+1)=Nnumk2(t)k2(t)∈Kd

(31)

將移動充電車離開時刻和返回時刻與Δh作比，并向上取整可以得到其所處時段。

4.2 一體化經(jīng)濟調(diào)度模型

從運營商角度出發(fā)，移動充電服務日運營費用主要包括移動充電車物流費用和電池組充電費用。根據(jù)路徑方案制定的充電方案，通過影響日運營費用對移動充電車路徑方案產(chǎn)生影響，由此體現(xiàn)移動充電車路徑選擇與電池組充電優(yōu)化間的關系。據(jù)此建立移動充電服務一體化經(jīng)濟調(diào)度模型，目標函數(shù)如式(32)所示。

(32)

其中,Ni,CH為第i個能源服務站內(nèi)充電機數(shù)量。涉及的約束條件為式(3)—(15)、式(26)—(31)。

5 遺傳算法嵌套lpsolve工具箱的求解方法

車輛路徑問題已被證明是一個非確定性多項式難(NP-hard)問題，遺傳算法可以對其進行有效求解[20]，因此選擇遺傳算法求解路徑方案；對于電池組有序充電模型，為加快求解速度，采用lpsolve工具箱進行求解。

5.1 染色體編碼和用戶智能分配

本文采用自然數(shù)編碼，一組用戶排列表示用戶服務順序。借鑒文獻[21]在解決多配送中心問題時提出的整體法思想，從尋找全局最優(yōu)解的角度出發(fā)，通過設置虛擬用戶實現(xiàn)能源服務站的服務用戶的智能分配。以10用戶-3能源中心為例，通過設置2個虛擬用戶形成12個代碼。虛擬用戶隨機將實際用戶分割為3個部分，對應3個能源補給站，如圖1所示。為實現(xiàn)有效分割，規(guī)定虛擬用戶不能相鄰，且不能位于代碼的首位和末位。

圖1 染色體編碼示例
Fig.1 Example of chromosome encoding

5.2 適應度函數(shù)計算

在得到路徑方案后，根據(jù)移動充電車出發(fā)時刻，更新?lián)Q電需求，如式(30)所示；根據(jù)移動充電車返回時刻，更新下一調(diào)度時段待充電池狀態(tài)，如式(31)所示，并調(diào)用lpsolve工具箱求出對應的有序充電方案。

由于構造路徑時可能不滿足移動充電車車輛數(shù)目約束和時間窗約束，將物流費用最小化目標函數(shù)松弛為：

(33)

其中，β1和β2為懲罰因子，分別表示方案在用戶i延遲服務的懲罰以及總的車輛違反懲罰。

由于能源站內(nèi)備用電池數(shù)量限制，無法滿足部分路徑方案對應的換電需求，此時將充電費用賦值為一個較大的正數(shù)π，則充電費用為：

(34)

5.3 求解流程

本文所提求解方法的整體求解流程圖如附錄中圖A4所示，具體求解步驟如下。

a. 算法初始化。輸入路網(wǎng)中速度依賴函數(shù)、路網(wǎng)節(jié)點坐標、用戶的地理位置、時間窗、需求電量、能源服務站內(nèi)充電機數(shù)量、備用電池數(shù)量等參數(shù)，設置算法相關參數(shù)，生成初始種群。

b. 解碼染色體形成移動充電車調(diào)度方案，計算物流費用；調(diào)用lpsolve工具箱得到此路徑方案下的最優(yōu)充電費用，通過5.2節(jié)的方法評價其適應度函數(shù)。

c. 使用遺傳算法更新種群狀態(tài)。

d. 循環(huán)操作。返回步驟b循環(huán)計算，直到全局最優(yōu)解沒有更新或者達到種群最大迭代次數(shù)，停止循環(huán)。

e. 輸出最終解，得到移動充電車路徑方案及對應的充電方案。

6 算例分析

6.1 算例介紹

圖2 區(qū)域路網(wǎng)結構示意圖Fig.2 Schematic diagram of area road network

區(qū)域內(nèi)環(huán)形城市快速路將區(qū)域分為3個部分，一般城市中心較為擁堵，郊區(qū)附近較為通暢，仿照北京市二環(huán)、三環(huán)的概念，設置三環(huán)之外、二環(huán)之外、二環(huán)之內(nèi)區(qū)域擁堵系數(shù)ξ分別為1、1.5、2。 不同道路類型其設計行駛速度也不同，據(jù)此設計城市快速路、城市主干路道路類型系數(shù)φ分別為1、0.8。參考文獻[22]中已有的一些數(shù)據(jù)，以15 min為一個取樣周期，得到基準旅行速度分段時間依賴函數(shù)如圖3所示。

圖3 基準旅行速度分段時間依賴函數(shù)Fig.3 Benchmark split time-dependent function of travel speed

綜合路況因素和道路類型因素可得到具體路段的時間依賴函數(shù)為：

(35)

其中，Vi,j(t)為路段(vi,vj)的速度時間依賴函數(shù)；Vbase(t)為基準速度時間依賴函數(shù)；ξi,j為路段(vi,vj)所在區(qū)域的擁堵系數(shù)；φi,j為路段(vi,vj)道路類型系數(shù)。

6.2 結果分析

為說明本文所提用戶智能分配方法以及一體化求解移動充電服務兩過程給運營商帶來的經(jīng)濟效益，本文設計了3個仿真案例：案例1首先將用戶智能分配到能源服務站，然后進行一體化求解；案例2首先將用戶按距離分配到能源服務站，然后進行一體化求解；案例3采用分步優(yōu)化，首先得到最優(yōu)路徑選擇方案，然后在該路徑方案下進行電池組充電過程優(yōu)化。

6.2.1 案例1與案例2經(jīng)濟調(diào)度結果分析

表1、表2分別為案例1、2的路徑選擇方案，表3為相應的物流費用和充電費用。案例1對應的能源服務站電池接入安排見附錄C，其中數(shù)字0表示能源服務站。通過對比可知，案例1中運營商的總運營成本為620.30元，案例2中運營商的總運營成本為694.96元，案例2與案例1相比運營成本增加了12.04%。

案例1、2中充電成本差異較大，分析2種用戶分配策略下各能源服務站的服務用戶總需求見圖4?？梢娫趦赡茉捶照緟?shù)相同的情況下，案例1中兩能源服務站覆蓋的用戶充電需求分配較為均勻。

表1 案例1路徑選擇方案Table 1 Routing scheme in Case 1

表2 案例2路徑選擇方案Table 2 Routing scheme in Case 2

表3 案例1和案例2對應的物流費用和充電費用Table 3 Logistics cost and charging cost of Case 1 and Case 2

圖4 各能源服務站服務用戶總電量Fig.4 Total power of users served by energy service stations

案例1、2中各能源服務站充電曲線分別如圖5和圖6所示。從圖5可以看出，案例1中，為滿足移動充電車換電需求，兩能源服務站均在非谷電價時段接入電池。結合附錄C中能源服務站接入電池狀態(tài)，兩能源服務站均選擇充電時長最短的電池組接入充電，以減少充電費用，這從側面說明了本文充電優(yōu)化方法的有效性。從圖6可以看出，案例2中，能源服務站1#內(nèi)備用電池可以滿足移動充電車換電需求，且存在閑置，移動充電車所換下的電池全部在夜間低谷時段進行充電；能源服務站2#服務用戶需求較多，需多次往返能源服務站進行能源補給。為滿足移動充電車需求，能源服務站2#在電價峰時、平時接入較多電池組充電，造成充電費用高昂，增加了運營成本。

圖5 案例1中各能源服務站內(nèi)電池充電狀態(tài)Fig.5 Battery charging status of energy service station in Case 1

圖6 案例2中各能源服務站內(nèi)電池充電狀態(tài)Fig.6 Battery charging status of energy service stations in Case 2

通過上述分析可知，案例1中區(qū)域內(nèi)資源利用更加合理。通過本文方法可為能源服務站合理分配用戶，降低移動充電車使用頻次，減少峰、平時段充電電池組數(shù)量，降低整體運營費用。

6.2.2 案例1與案例3運營費用對比

案例3中，采用分步優(yōu)化得到運營商物流費用和充電費用，案例1和案例3的各項成本如表4所示。雖然方案3所需物流成本較小，但案例1中總運營成本更低，比案例3節(jié)省了4.18%，這說明采用分步求解方法往往只能得到問題的次優(yōu)解，本文在算法中以總運營費用對解的質(zhì)量進行評價，反復迭代求解，所得結果更優(yōu)。

表4 案例1和案例3運營費用對比Table 4 Comparison of operating cost between Case 1 and Case 3

6.2.3 不同充電模式運營費用對比

為進一步說明本文所提充電方法的有效性，在已知案例1路徑方案的前提下，能源服務站2#采用直接充電策略，得充電曲線如圖7所示。由圖7可知，使用本文方法優(yōu)化充電后，能源服務站內(nèi)電價谷時段充電容量利用率為75.78%，充電費用為230.54元；而采用直接充電策略，電價谷時段充電容量利用率為8.20%，充電費用為620.57元?？梢姡疚乃岱椒沙浞掷霉葧r電價時段對空載電池進行充電，大幅降低移動充電服務運營過程中的充電費用。

圖7 不同充電策略下能源服務站內(nèi)電池充電狀態(tài)Fig.7 Battery charging status of energy service station under different charging strategies

7 結論

資源和環(huán)境壓力為電動汽車產(chǎn)業(yè)提供了發(fā)展機遇，為完善電動汽車能源補給體系，推動電動汽車行業(yè)更好更快發(fā)展，本文構建了移動充電服務運營中一體化經(jīng)濟調(diào)度模型，并針對模型特點提出了遺傳算法內(nèi)嵌lpsolve工具箱的求解方法，得到如下結論。

a. 該模型利用本文提出的用戶智能分配方法，可統(tǒng)籌用戶需求和能源服務站服務能力，在不增加固定投資的前提下充分發(fā)揮區(qū)域內(nèi)能源服務站最大服務能力，有效降低運營商的運營成本。

b. 該模型以移動充電車為紐帶，將移動充電服務運營中涉及的兩過程進行一體化求解，避免了決策沖突，可有效減少運營商運營成本，且這種求解方法具有一定的通用性和普適性。

c. 該模型在移動充電車路徑方案調(diào)度過程中，考慮動態(tài)路網(wǎng)使得制定的路徑方案更貼合實際；當為電池組制定充電計劃時，在滿足換電需求的前提下，考慮分時電價影響，合理決策何時接入何種荷電狀態(tài)的電池組，大幅降低了充電費用。

附錄見本刊網(wǎng)絡版(http:∥www.epae.cn)。