半開放式的多車場(chǎng)移動(dòng)充電車路徑優(yōu)化

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

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

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

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

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

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

1 半開放式的多車場(chǎng)移動(dòng)充電車路徑問題

1.1 問題描述

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

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

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

1.2 模型假設(shè)

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

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

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

(3)不考慮車場(chǎng)建設(shè)成本,假設(shè)均已建設(shè)運(yùn)營。

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

(5)移動(dòng)充電車行駛路線起止點(diǎn)均為車場(chǎng),應(yīng)急服務(wù)點(diǎn)不接受充電車的最終停靠。

1.3 符號(hào)說明

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

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

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

1.4 模型建立

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

minZ=Z1+Z2+Z3

(1)

式(1)中:Z為移動(dòng)充電平臺(tái)投入運(yùn)營的總成本值。

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

2 遺傳算法設(shè)計(jì)

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

2.1 編碼規(guī)則

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

0～2表示3個(gè)車場(chǎng)編號(hào);3～14表示移動(dòng)充電車服務(wù)的應(yīng)急需求點(diǎn)圖3 染色體編碼示意圖Fig.3 Chromosome coding diagram

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

2.2 精英保留策略

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

2.3 交叉操作

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

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

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

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

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

2.4 變異操作

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

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

3 算例分析

3.1 算例描述

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

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

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

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

3.2 算法比較與分析

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

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

根據(jù)算例節(jié)點(diǎn)數(shù),經(jīng)過多次實(shí)驗(yàn),模型相關(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次運(yùn)行結(jié)果及每次運(yùn)行得到的解與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算例運(yùn)行10次的目標(biāo)均值為8 552.43元,其中行駛成本均值為5 667.83 元,車輛啟動(dòng)成本均值為1 050 元,時(shí)間懲罰成本均值1 834.59 元。3D-30C算例運(yùn)行10次的總成本最優(yōu)值為8 449.36元,每次運(yùn)行目標(biāo)值與最優(yōu)目標(biāo)值的平均gap為1.22%,最大gap值為2.40%,充分說明遺傳算法求解的穩(wěn)定性。從表6可以看出,3個(gè)車場(chǎng)共派出11輛移動(dòng)充電車滿足30個(gè)應(yīng)急服務(wù)點(diǎn)的全部充電需求,其中有4輛充電車返回原車場(chǎng),7輛車由于距離因素,返回其他車場(chǎng)。

最優(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 敏感性分析

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

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

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

4 結(jié)論

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

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

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

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