周長影,張圣忠,陸迪,白雪

(1.長安大學(xué)運輸工程學(xué)院,西安 710064;2.長安大學(xué)經(jīng)濟(jì)管理學(xué)院,西安 710064)

在技術(shù)進(jìn)步和政策扶持的雙重影響下,新能源汽車產(chǎn)業(yè)迅速發(fā)展,并被廣泛應(yīng)用在出行和貨運領(lǐng)域。截至2021年12月底,中國新能源汽車保有量累計784萬輛,占汽車總量2.60%。隨著新能源汽車應(yīng)用場景多元化,充電服務(wù)需求大幅提升,但充電樁數(shù)量不足、布局不合理等問題依然存在,不同程度加劇了新能源車主的里程焦慮。在此背景下,移動充電平臺應(yīng)運而生,移動充電服務(wù)的典型模式是依托充電車對在路上因電量不足拋錨的新能源汽車進(jìn)行救援服務(wù),相較于固定充電站充電的模式,能夠減少顧客里程焦慮,提供更加靈活方便的上門充電服務(wù),有效補(bǔ)充城市新能源車輛的充電服務(wù)網(wǎng)絡(luò)。

移動充電平臺使用的充電車為電動車,受自身行駛里程約束,需要科學(xué)規(guī)劃充電車的服務(wù)路徑。目前有關(guān)移動充電車路徑優(yōu)化的文獻(xiàn)較少,且主要基于單車場模式。Cui等[1-2]引入帶時間窗和多模式的移動充電車問題,建立以行駛距離最短為目標(biāo)的模型,并對充電車電池容量、服務(wù)效率等進(jìn)行敏感性分析。陳萍等[3]考慮顧客軟時間窗、充電車?yán)锍滔拗频燃s束,建立平臺收益最大的數(shù)學(xué)規(guī)劃模型,將移動充電車服務(wù)路徑歸納為團(tuán)隊定向問題,開展新能源移動充電車的路徑優(yōu)化研究。

單車場獨立服務(wù)模式適用于顧客點分布集中的情形,而新能源汽車應(yīng)急充電服務(wù)對需求響應(yīng)速度要求高。已有城市配送路徑優(yōu)化的相關(guān)文獻(xiàn)表明,多車場聯(lián)合配送能提高物流效率,尤其是半開放式的多車場聯(lián)合服務(wù)能高效處理顧客需求,即松弛車輛必須返回原車場的閉環(huán)限制,服務(wù)結(jié)束后的車輛可返回任意車場。移動充電服務(wù)具有類城市配送的特征,故移動充電平臺可構(gòu)建半開放式的多車場移動充電車路徑優(yōu)化模型。馬冰山等[4]研究了物流配送模式下多車場半開放式聯(lián)合服務(wù),證明多車場和半開放式路徑結(jié)合能顯著降低物流配送總成本。范厚明等[5]提出了半開放式的多物流中心聯(lián)合配送模式,表明該模式能快速響應(yīng)顧客生鮮需求,提高產(chǎn)品配送效率。凌海峰等[6]在開放式車輛路徑基礎(chǔ)上,考慮多車場和時間窗約束,通過模型求解,證明半開放式的多車場聯(lián)合服務(wù)能提高顧客滿意度。劉長石等[7]針對多物流中心共享信息資源模式,建立了總成本最小的開放式車輛聯(lián)合配送路徑規(guī)劃模型。葉勇等[8]為提高城市配送效率和交通運輸服務(wù)水平,通過Solomon多組算例對比驗證算法求解的穩(wěn)定性和高效性。周毅君等[9]考慮成本最小和完工時間最短等因素,建立柔性的作業(yè)車間調(diào)度模型,通過標(biāo)準(zhǔn)算例對問題進(jìn)行求解。韓孟宜等[10]考慮時間窗懲罰最小和成本最低等約束,求解突發(fā)事件下應(yīng)急物資的最優(yōu)調(diào)度路線,合理解決應(yīng)急狀態(tài)下的供需不平衡問題。張瑾等[11]考慮車容量和時間窗約束,建立總成本最小和客戶滿意度最大的雙目標(biāo)模型,通過實際算例求得問題解并驗證算法有效性。姜彥寧等[12]通過遺傳算法求解共享車輛和共享車輛分撥中心的整車物流配送問題,證明共享資源配送模式優(yōu)于傳統(tǒng)的單中心配送模式,能夠顯著節(jié)約配送成本。

基于此,考慮應(yīng)急服務(wù)點分布隨機(jī)性特征,將移動充電車置于多車場聯(lián)合服務(wù)場景,提出半開放式的多車場移動充電車路徑優(yōu)化問題,設(shè)計分支定界法和遺傳算法求解小中規(guī)模算例,以驗證模型正確性和算法有效性。研究成果豐富了新能源汽車只能在固定充電站進(jìn)行充電的研究理論,為移動充電平臺總成本降低和移動充電車資源優(yōu)化提供一定的理論意義。

1 半開放式的多車場移動充電車路徑問題

1.1 問題描述

移動充電平臺有固定數(shù)量的多車場提供聯(lián)合服務(wù),每個車場有足夠數(shù)量的移動充電車,能夠滿足N個應(yīng)急服務(wù)點的全部充電需求。每個應(yīng)急服務(wù)點有一個最佳時間窗[ei,li],ei為應(yīng)急服務(wù)點能夠接受的最早服務(wù)時間窗,早于該時間時,充電車等待,產(chǎn)生等待成本;li為應(yīng)急服務(wù)點能夠接受的最晚服務(wù)時間窗,晚于該時間時,要給予應(yīng)急服務(wù)點補(bǔ)償,作為懲罰。車場提供移動充電車的充電服務(wù),即充電車從車場滿電量出發(fā)。目標(biāo)是如何規(guī)劃移動充電車的數(shù)量和服務(wù)路徑,使得移動充電平臺在滿足全部應(yīng)急服務(wù)點充電需求的前提下總成本最低。移動充電服務(wù)流程圖如圖1所示,移動充電平臺收到應(yīng)急服務(wù)點請求,直接派出移動充電車對其提供服務(wù),移動充電車在特定時間內(nèi)完成服務(wù)并返回任意車場。半開放式的多車場移動充電車路徑優(yōu)化問題示例如圖2所示,該例子中有3個車場提供聯(lián)合服務(wù),共派出4輛移動充電車滿足9個應(yīng)急服務(wù)點的全部充電需求。

圖1 移動充電服務(wù)流程圖Fig.1 Flow chart of mobile charging service

[]內(nèi)的數(shù)字為該節(jié)點最佳時間窗;百分?jǐn)?shù)為到達(dá)該節(jié)點剩余電量,表示到達(dá)上一節(jié)點剩余電量減去此節(jié)點服務(wù)電量和兩節(jié)點間行駛消耗的電量圖2 半開放式的多車場移動充電車路徑優(yōu)化問題示例Fig.2 An example of mobile charging vehicles path optimization problem on half-open multi depots

1.2 模型假設(shè)

為便于模型建立,做如下假設(shè)。

(1)車場和應(yīng)急服務(wù)點地理位置、時間窗等信息均已知,所有節(jié)點間互聯(lián)互通。

(2)移動充電車出發(fā)前,收到n個應(yīng)急服務(wù)點預(yù)約的充電請求,途中不會產(chǎn)生新的應(yīng)急服務(wù)需求點。

(3)不考慮車場建設(shè)成本,假設(shè)均已建設(shè)運營。

(4)移動充電車為同一車型,具有相同的電池容量、服務(wù)效率等參數(shù)。

(5)移動充電車行駛路線起止點均為車場,應(yīng)急服務(wù)點不接受充電車的最終?？?。

1.3 符號說明

(1)集合。C為應(yīng)急服務(wù)點編號集合,且C={1,2,…,n};D為車場編號集合,且D={1,2,…,m};N為所有節(jié)點集合,即N=D∪C;K為移動充電車集合,且K={1,2,…,k};kD為分配給車場D的移動充電車數(shù)量。

(2)參數(shù)。i、j為編號,應(yīng)急服務(wù)點編號集合為C,車場編號集合為D;Q為移動充電車電池容量,包括為應(yīng)急服務(wù)點提供服務(wù)的電量和自身行駛消耗的電量;M為極大值,作為懲罰進(jìn)行約束;qi為應(yīng)急服務(wù)點i所需電量;h為移動充電車電量消耗率;[ei,li]為應(yīng)急服務(wù)點i的最佳時間窗;u為移動充電車充電服務(wù)效率;wk為移動充電車固定發(fā)車成本;CTransport為移動充電車單位運輸成本;epu為車輛早到應(yīng)急服務(wù)點的單位時間等待成本;lpu為車輛晚到應(yīng)急服務(wù)點的單位時間懲罰成本;dij為節(jié)點i和節(jié)點j之間距離;tij為移動充電車從節(jié)點i行駛到節(jié)點j的時間。

(3)決策變量。xijk為0-1變量,移動充電車k從節(jié)點i行駛到節(jié)點j為1,反之為0;τi為到達(dá)節(jié)點i的時間;τbegin,i為在節(jié)點i開始服務(wù)的時間;yi為到達(dá)節(jié)點i的剩余電量。

1.4 模型建立

為解決移動充電平臺投入運營成本高的問題,利用多車場間信息共享進(jìn)行移動充電車的合理調(diào)度至關(guān)重要?；诙嘬噲?、應(yīng)急服務(wù)點流量平衡、時間連續(xù)性、里程限制等約束條件,建立包括移動充電車啟動成本、行駛成本和在應(yīng)急服務(wù)點違反時間窗的懲罰成本在內(nèi)的總成本最小的目標(biāo)函數(shù),如式(1)所示。模型建立如式(1)～式(23)所示。

minZ=Z1+Z2+Z3

(1)

式(1)中:Z為移動充電平臺投入運營的總成本值。

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

τbegin,i=max(τi,ei),?i∈C

(11)

τbegin,i=0,?i∈D

(12)

τbegin,i+(tij+qiu)xijk-l0(1-xijk)≤τj,

?k∈K;?i∈N;?j∈C;i≠j

(13)

式(13)中:l0為極大值,作為時間懲罰系數(shù)進(jìn)行條件約束。

τbegin,i+tijxijk-l0(1-xijk)≤τj,

?k∈K;?i∈D;?j∈C

(14)

τj≤τbegin,i+tij+qiu+M(1-xijk),

?k∈K;?i∈N;?j∈N;i≠j

(15)

τj+M(1-xijk)≥τbegin,i+tij+qiu,

?k∈K;?i∈N;?j∈N;i≠j

(16)

xijkqj≤yj≤yi-hdijxijk-qixijk+Q(1-xijk),

?k∈K;?i∈C;?j∈N;i≠j

(17)

xijkqj≤yj≤Q-hdijxijk+Q(1-xijk),

?k∈K;?i∈D;?j∈C

(18)

yj≤yi-hdij-qi+M(1-xijk),

?k∈K;?i∈C;?j∈N;i≠j

(19)

yj+M(1-xijk)≥yi-hdij-qi,

?k∈K;?i∈C;?j∈N;i≠j

(20)

yj≤Q-hdij+M(1-xijk),

?k∈K;?i∈D;?j∈C

(21)

yj+M(1-xijk)≥Q-hdij,

?k∈K;?i∈D;?j∈C

(22)

xijk∈{0,1},?i∈N;?j∈N;i≠j;?k∈K

(23)

式(1)表示移動充電平臺總成本最低的目標(biāo)函數(shù),包括式(2)移動充電車啟動成本,式(3)行駛成本和式(4)在應(yīng)急服務(wù)點最佳時間窗外提供服務(wù)產(chǎn)生的等待成本或懲罰成本;式(5)、式(6)表示每個車場派出和返回的充電車數(shù)量不超過該車場的最大車輛泊位,且松弛充電車必須返回原車場約束;式(7)表示派出服務(wù)的移動充電車不能直接從車場行駛到車場;式(8)保證每個應(yīng)急服務(wù)點都被且僅被服務(wù)一次,并只能由一輛充電車提供服務(wù);式(9)表示應(yīng)急服務(wù)點進(jìn)出平衡;式(10)表示每輛移動充電車最多屬于一個車場,且最多允許服務(wù)一次;式(11)、式(12)表示移動充電車在節(jié)點i開始服務(wù)時間;式(13)、式(14)表示移動充電車到達(dá)各應(yīng)急服務(wù)點的時間范圍;式(15)、式(16)計算移動充電車到達(dá)各節(jié)點的準(zhǔn)確時間值;式(17)、式(18)表示移動充電車到達(dá)各節(jié)點的剩余電量范圍;式(19)～式(22)計算移動充電車到達(dá)各節(jié)點的剩余電量準(zhǔn)確值;式(23)表示0-1決策變量。

2 遺傳算法設(shè)計

遺傳算法將問題初始解在染色體中進(jìn)行編碼,通過計算種群各個體適應(yīng)度值,把適應(yīng)度高的個體按比例保留到子代,經(jīng)過交叉、變異等方式尋求更優(yōu)解,能夠快速求解復(fù)雜的組合優(yōu)化問題,適合中大規(guī)模算例的啟發(fā)式求解。故采用遺傳算法對半開放式的多車場移動充電車路徑優(yōu)化模型求解,既能提高求解效率和求解質(zhì)量,也能得到該問題的近似全局最優(yōu)解。

2.1 編碼規(guī)則

帶時間窗的半開放式多車場移動充電車路徑優(yōu)化問題(HO-MDEVRP-TW)屬于混合整數(shù)非線性規(guī)劃問題,具有時間和空間雙重維度求解難度,故采取自然數(shù)形式進(jìn)行編碼。染色體長度為n+k+3,其中,n為新能源汽車應(yīng)急服務(wù)點數(shù)量,k為移動充電車數(shù),3為車場數(shù)量。染色體編碼示意圖如圖3所示。

0～2表示3個車場編號;3～14表示移動充電車服務(wù)的應(yīng)急需求點圖3 染色體編碼示意圖Fig.3 Chromosome coding diagram

從染色體編碼示意圖(圖3)可以看出,充電車1屬于第一個車場,其服務(wù)路徑為從車場0出發(fā),服務(wù)應(yīng)急需求點4、3、7和8;充電車2屬于第2個車場,其服務(wù)路徑為從車場1出發(fā),服務(wù)應(yīng)急需求點5、10、6、9和14;充電車3屬于第3個車場,其服務(wù)路徑為從車場2出發(fā),服務(wù)應(yīng)急需求點11、12和13。

2.2 精英保留策略

每次迭代結(jié)束,經(jīng)過選擇比較,將子代種群前50%優(yōu)秀個體和父代種群前50%優(yōu)秀個體運用精英保留策略進(jìn)行融合,納入精英庫,確保每次迭代后子代種群能保留和父代種群相同的個體。通過輪盤賭策略對精英庫中被選擇個體執(zhí)行再次篩選,確保精英庫保存全部優(yōu)秀個體,同時加快算法收斂速度。

2.3 交叉操作

從精英庫中任意選擇兩條染色體作為父代個體,在選中的父代個體上隨機(jī)選擇一條子路徑,記錄子路徑的個數(shù)n1。通過改進(jìn)交叉算子對選中的兩條染色體進(jìn)行交叉操作,將選擇的子路徑在子代染色體中前置,未訪問節(jié)點多次隨機(jī)插入車輛,打斷為1～(n1-1)條子路。選擇生成的子路徑中總成本最小的,添加到子代染色體片段之后,形成完整的子染色體。

假設(shè)有兩個父代個體,如圖4所示。

圖4 父代染色體片段Fig.4 Parental chromosome fragment

經(jīng)交叉操作得到兩個子代個體,如圖5所示。

圖5 子代染色體片段Fig.5 Progeny chromosome fragment

2.4 變異操作

隨機(jī)在染色體上選取兩個基因位點,如圖6中的8和14所示,采用2-opt算法對該染色體進(jìn)行局部優(yōu)化,將兩位點之間的基因片段反轉(zhuǎn)并接回原來的位置。如果變異后染色體總成本小于變異前染色體總成本,則用變異后染色體代替變異前染色體,否則保持原染色體不變。染色體變異如圖6所示。

圖6 染色體變異示意圖Fig.6 Chromosome variation diagram

3 算例分析

3.1 算例描述

由于半開放式的多車場移動充電車聯(lián)合服務(wù)模式下相關(guān)約束較多,且具有時間懲罰成本和半開放式的特點,目前沒有通用的算例集。選用Solomon設(shè)計的VRPTW標(biāo)準(zhǔn)算例中的R102算例,根據(jù)聯(lián)合服務(wù)的特點對其進(jìn)行修改,生成3個車場、8個應(yīng)急服務(wù)點的小規(guī)模測試算例(3D-8C)如表1、表2所示,3個車場、30個應(yīng)急服務(wù)點的中規(guī)模測試算例(3D-30C)如表3所示。在Windows10操作系統(tǒng)、16 GB內(nèi)存、2.60 GHz的Intel(R)Core(TM)i5-11400處理器上,通過Python3.7編寫分支定界法和遺傳算法實現(xiàn)模型求解。

表1 3D-8C算例各節(jié)點需求量及時間窗Table 1 3D-8C instance demands and time windows of each node

表2 3D-8C算例各節(jié)點間距離Table 2 3D-8C instance distances between nodes

表3 3D-30C各節(jié)點坐標(biāo)、需求量及時間窗Table 3 3D-30C coordinates,demands and time windows of each node

3.2 算法比較與分析

采用分支定界法對3個車場、8個應(yīng)急服務(wù)點(3D-8C)的小規(guī)模構(gòu)造算例進(jìn)行精確求解,驗證所建模型準(zhǔn)確性。對比遺傳算法的求解時間和計算結(jié)果可知,遺傳算法在小規(guī)模算例下能夠得到和分支定界法相同的精確解,表明遺傳算法具有較好的求解質(zhì)量,且對中大規(guī)模算例求解更具時間優(yōu)勢。結(jié)果如表4所示。

表4 3D-8C算例結(jié)果Table 4 Result of 3D-8C instance

根據(jù)算例節(jié)點數(shù),經(jīng)過多次實驗,模型相關(guān)參數(shù)設(shè)置如下:種群數(shù)量400,交叉概率0.90,Q=300,h=1,u=1,wk=100,CTransport=5,epu=2,lpu=3,迭代次數(shù)設(shè)為250次。遺傳算法求解R102算例的10次運行結(jié)果及每次運行得到的解與10次中最優(yōu)解偏差(gap)值如表5所示。最優(yōu)解如表6所示。

表5 3D-30C算例下遺傳算法求解10次結(jié)果Table 5 Results were solved 10 times by genetic algorithm under 3D-30C instance

表6 3D-30C算例下遺傳算法求得的最優(yōu)解Table 6 The optimal solution was obtained by genetic algorithm under 3D-30C instance

3D-30C算例運行10次的目標(biāo)均值為8 552.43元,其中行駛成本均值為5 667.83 元,車輛啟動成本均值為1 050 元,時間懲罰成本均值1 834.59 元。3D-30C算例運行10次的總成本最優(yōu)值為8 449.36元,每次運行目標(biāo)值與最優(yōu)目標(biāo)值的平均gap為1.22%,最大gap值為2.40%,充分說明遺傳算法求解的穩(wěn)定性。從表6可以看出,3個車場共派出11輛移動充電車滿足30個應(yīng)急服務(wù)點的全部充電需求,其中有4輛充電車返回原車場,7輛車由于距離因素,返回其他車場。

最優(yōu)解的算法迭代過程如圖7所示。行駛路線如圖8所示。通過迭代圖(圖7)可知,算法在第125代左右向最優(yōu)解收斂,能夠跳出局部最優(yōu)解,說明遺傳算法具有較好的求解質(zhì)量和求解效果。

圖7 3D-30C算例最優(yōu)解迭代圖Fig.7 Iteration diagram of optimal solution under 3D-30C instance

圖8 3D-30C算例最優(yōu)解路線圖Fig.8 Routing diagram of optimal solution under 3D-30C instance

3.3 敏感性分析

為明確帶時間窗的半開放式多車場移動充電車聯(lián)合服務(wù)路徑優(yōu)化問題(HO-MDEVRP-TW)的特點,設(shè)計了傳統(tǒng)帶時間窗的單車場(EVRP-TW)獨立服務(wù)模型進(jìn)行對比分析,EVRP-TW模型在HO-MDEVRP-TW模型的基礎(chǔ)上,將多車場集合D修改為一個車場即可。在相同的參數(shù)假設(shè)和系統(tǒng)運行環(huán)境下,通過不同客戶分布類型(R為隨機(jī)分布、C為集中分布、RC為混合分布)的規(guī)模算例,運用遺傳算法對其進(jìn)行10次求解計算均值。不同算例的成本變化情況如表7所示。

表7 EVRP-TW和HO-MDEVRP-TW的成本變化情況Table 7 Changing situation of EVRP-TW and HO-MDEVRP-TW costs

對比HO-MDEVRP-TW和EVRP-TW算例運行結(jié)果(表7),可以看出,半開放式多車場聯(lián)合服務(wù)比單車場獨立服務(wù)在R102算例和R205算例分別節(jié)約26.18%和10.30%的總成本,主要體現(xiàn)在移動充電車為應(yīng)急服務(wù)點提供充電服務(wù)時行駛成本的節(jié)約和在應(yīng)急服務(wù)點違反時間窗的時限減少;在C102算例和C205算例分別節(jié)約2.52%和0.02%的總成本,主要體現(xiàn)在移動充電車為應(yīng)急服務(wù)點提供充電服務(wù)時行駛成本的節(jié)約;在RC102算例和RC205算例分別節(jié)約4.74%和10.57%的總成本,主要體現(xiàn)在移動充電車提供充電服務(wù)時在應(yīng)急服務(wù)點違反時間窗的時限減少。比較結(jié)果表明,半開放式的多車場聯(lián)合服務(wù)能夠大幅減少單車場獨立服務(wù)模式下由于充電車頻繁往返始發(fā)中心產(chǎn)生的重復(fù)行駛路徑;移動充電平臺提供的移動充電車在滿足全部應(yīng)急服務(wù)點充電需求的前提下,能夠顯著降低包括移動充電車為應(yīng)急服務(wù)點提供充電服務(wù)的車輛啟動成本、行駛成本和在應(yīng)急服務(wù)點違反時間窗的懲罰成本在內(nèi)的總成本,從而為移動充電平臺帶來更大的收益;移動充電平臺在R型算例和RC型算例下節(jié)約成本較為明顯,說明半開放式的多車場聯(lián)合服務(wù)對隨機(jī)分布客戶群體和混合分布客戶群體的需求能夠做出更快響應(yīng),體現(xiàn)了將移動充電車置于半開放式多車場聯(lián)合服務(wù)場景的優(yōu)越性。

4 結(jié)論

考慮新能源汽車應(yīng)急服務(wù)點分布隨機(jī)性特點,將移動充電車置于半開放式的多車場聯(lián)合服務(wù)場景,構(gòu)建了半開放式的多車場移動充電車路徑優(yōu)化模型,利用分支定界法和遺傳算法對模型求解,驗證了模型的正確性和算法的有效性。通過三種客戶分布類型的算例對半開放式的多車場聯(lián)合服務(wù)和單車場獨立服務(wù)兩種模型對比分析,得出以下結(jié)論。

(1)半開放式的多車場聯(lián)合服務(wù)能夠為移動充電車提供更多的路徑選擇,減少移動充電車的行駛里程,有效提高移動充電平臺的服務(wù)效率,降低平臺的運營成本。

(2)半開放式的多車場聯(lián)合服務(wù)能夠適用新能源汽車應(yīng)急服務(wù)點分布隨機(jī)性特點,在R型和RC型算例下顯著節(jié)約移動充電平臺的總運營成本,為移動充電平臺規(guī)劃合理的服務(wù)路徑,使得移動充電車和多車場設(shè)施等資源得到充分利用。

在后續(xù)的研究中,可考慮顧客動態(tài)服務(wù)需求以及多車場選址等因素,建立更加符合實際場景的應(yīng)用模型,為移動充電車做出合理的路徑規(guī)劃,給移動充電平臺提供科學(xué)的決策價值。