考慮多路徑選擇的定制電動(dòng)公交線路優(yōu)化

郭戎格，關(guān)偉，張文義，段夢(mèng)媛

(北京交通大學(xué)，綜合交通運(yùn)輸大數(shù)據(jù)應(yīng)用技術(shù)交通運(yùn)輸行業(yè)重點(diǎn)實(shí)驗(yàn)室，北京100044)

0 引言

定制公交憑借其靈活、直達(dá)和響應(yīng)快速的優(yōu)勢(shì)，成為提高公共交通準(zhǔn)時(shí)性和舒適性的解決方案。定制公交作為一種需求響應(yīng)型服務(wù)，如何優(yōu)化運(yùn)營(yíng)線路來(lái)滿足出行需求是亟待研究的問(wèn)題。Guo 等[1]考慮乘客出行時(shí)間窗，實(shí)現(xiàn)線路與時(shí)刻表的共同決策。Huang 等[2]采用兩階段優(yōu)化方法，以運(yùn)營(yíng)收益最大為目標(biāo)，求解針對(duì)動(dòng)態(tài)出行需求的線路方案。陳汐等[3]同時(shí)考慮乘客出行成本和運(yùn)營(yíng)成本，構(gòu)建多區(qū)域運(yùn)營(yíng)模式的定制公交線路規(guī)劃模型。然而，當(dāng)前研究主要針對(duì)傳統(tǒng)車輛，未考慮純電動(dòng)車輛在定制服務(wù)中的應(yīng)用。楊揚(yáng)等[4]表明純電動(dòng)公交在環(huán)境保護(hù)和節(jié)約能源方面有較大優(yōu)勢(shì)，可替代傳統(tǒng)公交車，但其運(yùn)營(yíng)特性(續(xù)航里程短、充電時(shí)間長(zhǎng))會(huì)為線路規(guī)劃帶來(lái)挑戰(zhàn)。Hiermann 等[5]通過(guò)確定車輛的充電地點(diǎn)和充電時(shí)間，實(shí)現(xiàn)不同類型電動(dòng)車輛的線路決策。Montoya等[6]則采用分段線性函數(shù)近似捕捉車輛充電過(guò)程的非線性行為。

實(shí)際路網(wǎng)中，地理上分隔的兩點(diǎn)間通常存在多條可選子路徑，且每條路徑包含多個(gè)屬性，為線路進(jìn)一步優(yōu)化提供可能性。Baldacci 等[7]引入多路徑路網(wǎng)的概念，用以研究生活垃圾轉(zhuǎn)運(yùn)車輛路徑優(yōu)化問(wèn)題。Lai等[8]基于行駛時(shí)間、距離等屬性獲取兩點(diǎn)之間的多路徑，設(shè)計(jì)了求解異構(gòu)車輛路徑問(wèn)題的禁忌搜索算法。Garaix等[9]在多路徑的按需運(yùn)輸問(wèn)題中，提出一種動(dòng)態(tài)規(guī)劃算法求解固定序列弧段選擇問(wèn)題。盡管學(xué)界對(duì)路徑選擇問(wèn)題進(jìn)行了廣泛而深入的研究，但較少考慮多路徑選擇對(duì)定制公交線路的影響。

綜上，本文提出一個(gè)混合整數(shù)規(guī)劃模型，實(shí)現(xiàn)定制電動(dòng)公交線路與路徑的共同決策，目標(biāo)函數(shù)考慮乘客出行費(fèi)用、車輛運(yùn)營(yíng)費(fèi)用和充電費(fèi)用。算法求解方面，基于自適應(yīng)大鄰域搜索算法框架，設(shè)計(jì)可優(yōu)化線路的destroy和repair規(guī)則。最后，通過(guò)實(shí)例數(shù)值分析，驗(yàn)證多路徑選擇可有效提高定制公交運(yùn)營(yíng)效率。

1 問(wèn)題描述與模型

1.1 問(wèn)題描述

本文須解決的問(wèn)題可描述為，場(chǎng)站擁有相同容量的滿電車輛，服務(wù)已知的乘客出行時(shí)空需求，通過(guò)優(yōu)化站點(diǎn)訪問(wèn)順序和路徑選擇創(chuàng)建線路，使得：①車輛服務(wù)所有出行需求，且滿足乘客和場(chǎng)站服務(wù)時(shí)間窗，②每輛車載客人數(shù)不少于車輛最低載客量，③車輛在充電站達(dá)到滿電狀態(tài)后離開(kāi)。圖1為本文多子路徑路網(wǎng)示意圖，每條路徑廣義費(fèi)用考慮距離和時(shí)間兩種屬性。

圖1 路網(wǎng)示意圖Fig.1 Schematic drawing of road network

本文使用G=(V,A)表示路網(wǎng)，其中，V為節(jié)點(diǎn)集，它由站點(diǎn)集S、場(chǎng)站集O及充電站集F共同組成，即V=S∪O∪F，A表示弧集。集合S中的節(jié)點(diǎn)i(i∈S)對(duì)應(yīng)非負(fù)權(quán)值屬性：服務(wù)時(shí)間si和服務(wù)時(shí)間窗[TiArr,TiDep]，其中，TiArr為車輛最早到達(dá)時(shí)間，TiDep為車輛最遲離開(kāi)時(shí)間。集合S中任意兩節(jié)點(diǎn)r(r∈S)與s(s∈S)對(duì)應(yīng)乘客出行需求qr,s和乘客出行費(fèi)用fr,s。集合O中的節(jié)點(diǎn)j對(duì)應(yīng)場(chǎng)站服務(wù)時(shí)間窗[uj,lj]，uj和lj分別表示場(chǎng)站開(kāi)始和結(jié)束服務(wù)時(shí)間，即車輛須在[uj,lj]內(nèi)出發(fā)并返回場(chǎng)站。集合F中的節(jié)點(diǎn)對(duì)應(yīng)充電速率g，充電基本費(fèi)用c4和單位時(shí)間充電成本c5。集合A中的每條弧(i,j)對(duì)應(yīng)一組可選路徑Pi,j，每條路徑φi,j,p(p∈Pi,j)與距離di,j,p和旅行時(shí)間ti,j,p相關(guān)聯(lián)。K表示車輛集合，每輛車k對(duì)應(yīng)非負(fù)權(quán)值屬性：滿電電量E，能耗速率h，最大車容量M，抵達(dá)點(diǎn)i時(shí)的在車乘客數(shù)Qi,k，最低載客量λ，最大訪問(wèn)站點(diǎn)數(shù)R，單位車輛發(fā)車成本c1，單位時(shí)間運(yùn)營(yíng)成本c2和單位距離運(yùn)營(yíng)成本c3。決策變量定義如表1所示。

表1 決策變量含義Table 1 Decision variables

1.2 模型建立

定制電動(dòng)公交線路優(yōu)化問(wèn)題是一個(gè)NP-hard問(wèn)題，可構(gòu)造成一個(gè)混合整數(shù)規(guī)劃模型。模型目標(biāo)函數(shù)考慮乘客出行費(fèi)用、運(yùn)營(yíng)費(fèi)用(CBus)和充電費(fèi)用(CElectric)，以收益最大為目標(biāo)，構(gòu)建數(shù)學(xué)模型為

式中：B為一個(gè)較大常數(shù)。

目標(biāo)函數(shù)：式(1)定義了運(yùn)營(yíng)收益最大化，由乘客出行費(fèi)用，運(yùn)營(yíng)費(fèi)用和充電費(fèi)用組成；式(2)表示運(yùn)營(yíng)費(fèi)用，包含發(fā)車費(fèi)用，運(yùn)行時(shí)間費(fèi)用和運(yùn)行距離費(fèi)用；式(3)表示充電費(fèi)用，包括充電基本費(fèi)用和充電時(shí)間費(fèi)用。約束條件：式(4)表示可多次訪問(wèn)站點(diǎn)和充電站；式(5)表示車輛從場(chǎng)站出發(fā)并返回；式(6)為流量平衡約束；式(7)規(guī)定，車輛在服務(wù)某需求時(shí)，須訪問(wèn)該需求的起訖點(diǎn)；式(8)表示當(dāng)車輛訪問(wèn)充電站時(shí)，即發(fā)生充電行為；式(9)表示當(dāng)車輛行駛某一路段時(shí)，只選擇其中一條路徑；式(10)規(guī)定每輛車的最低載客量；式(11)為乘客分配約束；式(12)～式(14)為車容量約束；式(15)和式(16)表示車輛能耗與距離相關(guān)，保證每輛車的電量不低于0；式(17)和式(18)分別保證車輛在離開(kāi)場(chǎng)站、站點(diǎn)及充電站后的時(shí)間可行；式(19)～式(21)為時(shí)間窗約束；式(22)表示車輛離開(kāi)站點(diǎn)時(shí)間為車輛到達(dá)站點(diǎn)時(shí)間與服務(wù)時(shí)間之和；式(23)規(guī)定了每條線路訪問(wèn)站點(diǎn)的數(shù)量。

2 優(yōu)化模型求解算法

定制電動(dòng)公交線路優(yōu)化問(wèn)題屬于NP-hard 問(wèn)題，且規(guī)模較大。因此，本文基于自適應(yīng)大鄰域搜索 算 法(Adaptive Large Neighborhood Search，ALNS)，設(shè)計(jì)求解方法[10]。本文在ALSN框架下，基于貪心算法制定初始解產(chǎn)生規(guī)則，設(shè)計(jì)多個(gè)destroy和repair算子進(jìn)行鄰域搜索，優(yōu)化站點(diǎn)訪問(wèn)順序，并采用輪盤賭選擇機(jī)制選擇算子。由于在鄰域搜索中，并未指定車輛進(jìn)行運(yùn)送時(shí)兩站點(diǎn)間的具體子路徑，故本文采用Garaix等[9]提出的動(dòng)態(tài)規(guī)劃算法，以廣義費(fèi)用(行駛距離成本和行駛時(shí)間成本)最小，求解兩點(diǎn)間的最優(yōu)路徑。

2.1 初始解求解

采用貪心算法尋找初始可行解，其核心思想為：在不破壞模型約束的前提下尋找距離當(dāng)前節(jié)點(diǎn)最近的OD 加入線路，如果違反任意約束，則基于同樣規(guī)則搜索新線路。同時(shí)，還要考慮最優(yōu)路徑選擇情況。算法步驟如下：

Step 1 選擇場(chǎng)站i規(guī)劃新路線l，i為當(dāng)前節(jié)點(diǎn)a。

Step 2 搜索距離a最近未被服務(wù)的OD(r,s)，計(jì)算發(fā)車時(shí)間，選擇最優(yōu)路徑，判斷加入該OD(r,s)是否滿足時(shí)間窗和車容量約束。如果是，繼續(xù)；否則，返回Step 1。

Step 3 判斷電池容量是否滿足服務(wù)OD(r,s)。如果是，將OD 加入線路l，將s設(shè)置為當(dāng)前節(jié)點(diǎn)a，轉(zhuǎn)至Step 5；否則，繼續(xù)。

Step 4 判斷a附近是否存在充電站F，使車輛由最佳路徑前往F充電，并服務(wù)OD(r,s)。如果是，依次將F、OD(r,s)插入線路，將s作為當(dāng)前節(jié)點(diǎn)a，繼續(xù)；否則，返回Step 1。

Step 5 判斷站點(diǎn)數(shù)是否達(dá)到R。如果否，轉(zhuǎn)至Step 2；否則，搜索距離當(dāng)前a最近場(chǎng)站j，選擇最優(yōu)路徑，判斷加入j是否滿足時(shí)間窗約束，若滿足，繼續(xù)，否則，返回Step 1。

Step 6 判斷電池容量是否滿足到達(dá)j。如果滿足，將j加入線路l，結(jié)束；否則，繼續(xù)。

Step 7 判斷j附近是否存在充電站F，使得車輛由最佳路徑前往F充電，返回j。如果存在，依次將F、j插入線路，結(jié)束；否則，返回Step 1。

2.2 Destroy規(guī)則

在ALNS中，destroy算子可隨機(jī)破壞當(dāng)前解的一部分[10]。本文從隨機(jī)性與節(jié)省運(yùn)營(yíng)費(fèi)用的角度提出與站點(diǎn)相關(guān)的兩個(gè)算子?？紤]到電動(dòng)車在服務(wù)過(guò)程中的充電行為是線路規(guī)劃的關(guān)鍵，去除不必要的充電站可有效提高運(yùn)營(yíng)效率，故提出針對(duì)充電站的destroy算子。具體如下：

(1)Random destroy，隨機(jī)選取n組OD，移除對(duì)應(yīng)的站點(diǎn)。

(2)Worst cost destroy，依據(jù)節(jié)約廣義出行費(fèi)用移除站點(diǎn)，通過(guò)計(jì)算每個(gè)站點(diǎn)造成所在線路的廣義運(yùn)營(yíng)費(fèi)用增量，選擇增量最多的n個(gè)站點(diǎn)進(jìn)行移除，如圖2所示，其中站點(diǎn)上方的數(shù)字表示乘客上下車人數(shù)，例如+10表示上車10人，-10表示下車10人。費(fèi)用增量為

圖2 Worst cost destroy算子Fig.2 Worst cost destroy operator

(3)Low charge destroy，考慮到車輛在到達(dá)充電站時(shí)仍保有較多電量，充電效率低，可移除充電量低于Emin的充電站。如圖3所示，百分比為車輛剩余電量SOC，當(dāng)充電量低于30%的滿額電量，則移除充電站。

圖3 Low charge destroy算子Fig.3 Low charge destroy operator

2.3 Repair規(guī)則

在ALNS 中，repair 算子針對(duì)被destroy 算子破壞的部分進(jìn)行重建，實(shí)現(xiàn)鄰域搜索，從而得到一系列解的集合[10]，同時(shí)，需要判斷重建線路是否滿足模型約束。Repair算子介紹如下：

(1)Random repair，依次隨機(jī)選擇被破壞線路中的任意位置插入被移除OD，直到所有出行需求都被服務(wù)。

(2)Greedy repair，選擇被移除站點(diǎn)的現(xiàn)有線路l，采用式(24)計(jì)算使廣義運(yùn)營(yíng)費(fèi)用增量最小的位置j，插入站點(diǎn)。

(3)High charge repair，計(jì)算當(dāng)前線路車輛在電池容量滿額情況下可訪問(wèn)的最遠(yuǎn)站點(diǎn)i，在i附近尋找導(dǎo)致廣義運(yùn)營(yíng)費(fèi)用增量最小的充電站，插入到線路中，重復(fù)上述步驟，直到所有線路滿足乘客需求，如圖4所示，該算子可造成新的充電站替換被移除充電站。

圖4 High charge repair算子Fig.4 High charge repair operator

為證明ALNS 的有效性，分別運(yùn)用CPLEX 和ALNS對(duì)算例進(jìn)行求解[3]。如表2所示，發(fā)現(xiàn)ALNS所得最大目標(biāo)函數(shù)值與精確解相差較小，且在計(jì)算效率上存在較大優(yōu)勢(shì)，故認(rèn)為ALNS可應(yīng)用于大規(guī)模實(shí)例求解。

表2 算法對(duì)比結(jié)果Table 2 Comparison results of algorithms

3 實(shí)例研究

3.1 實(shí)例設(shè)計(jì)

本文以北京市區(qū)路網(wǎng)及乘客出行時(shí)空需求為基礎(chǔ)，設(shè)計(jì)3種類似于Solomon標(biāo)準(zhǔn)算例R、C和RC的實(shí)例[3]，R、C 和RC 分別對(duì)應(yīng)隨機(jī)乘客分布、聚集乘客分布和混合乘客分布。每個(gè)實(shí)例包含工作日早高峰7:00-8:00 的20 組出行需求(227 名乘客)和11 個(gè)場(chǎng)站，每一組出行需求包含出行起訖點(diǎn)，服務(wù)時(shí)間窗和出行人數(shù)信息，其中，兩站點(diǎn)間存在3 條可選子路徑。如圖5所示，R實(shí)例通過(guò)隨機(jī)選擇20組出行需求獲得，C實(shí)例基于密度的空間聚類方法獲得，RC實(shí)例由隨機(jī)選取的10組需求和聚類產(chǎn)生的10組需求組成。

圖5 R，C和RC案例的乘客位置Fig.5 Passenger locations of R,C and RC instances

實(shí)例采用40 座的電動(dòng)公交車，滿電電量為80 kWh，能耗速率為2 kWh·km-1，每輛車的最小負(fù)載為20 人，服務(wù)6 個(gè)站點(diǎn)，須在場(chǎng)站服務(wù)時(shí)間窗[7:00, 8:30]內(nèi)完成任務(wù)。案例中，場(chǎng)站即為充電站，充電速率為4 kWh·min-1。其余參數(shù)如下：c1=80元，c2=60元·h-1，c3=1.8元·km-1，c4=50元，c5=10 元·min-1，si=1 min。自適應(yīng)大鄰域搜索算法迭代150次。

3.2 結(jié)果分析

采用上述求解算法分析充電方式、乘客分布及多路徑選擇對(duì)收益的影響，為降低啟發(fā)式算法隨機(jī)性對(duì)結(jié)果的影響，重復(fù)計(jì)算每個(gè)算例10次，基于此結(jié)果進(jìn)行分析。

(1)充電方式及乘客分布對(duì)收益的影響

考慮到不同充電方式會(huì)極大影響公交運(yùn)營(yíng)成本，針對(duì)快充模式(R1，C1，RC1)和換電模式(R2，C2，RC2)進(jìn)行收益分析，計(jì)算3 種乘客分布情況下的總收益(z)，運(yùn)行時(shí)間(T)，運(yùn)行距離(D)，充電費(fèi)用(CElectric)和車輛數(shù)(N)。其中，換電模式的充電時(shí)間為0，換電基本費(fèi)用c4=300元。

如表3所示，針對(duì)每種乘客分布情況，采用快充模式可獲得更多運(yùn)營(yíng)收益，盡管整車快充會(huì)增加充電時(shí)間，但相較于換電模式，快充模式的基本充電費(fèi)用較低，降低了車輛的充電成本。分析3種乘客分布對(duì)應(yīng)的數(shù)值結(jié)果可以發(fā)現(xiàn)：聚類乘客分布及混合乘客分布的收益優(yōu)勢(shì)逐漸體現(xiàn)出來(lái)，C 與RC實(shí)例對(duì)應(yīng)的總收益較高；與R相比，C與RC采用較多運(yùn)營(yíng)車輛，有效減少充電次數(shù)與充電時(shí)間；車輛服務(wù)分布較為集中的乘客時(shí)，運(yùn)行距離和運(yùn)行時(shí)間相應(yīng)減少。因此，在設(shè)計(jì)定制服務(wù)時(shí)，尋求乘客分布和運(yùn)輸成本之間的平衡是極其重要的。

表3 快充模式與換電模式算例結(jié)果Table 3 Results of fast charging and battery swapping

(2)多路徑選擇效果分析

為研究路徑靈活性的影響，分析比較兩站點(diǎn)間單一子路徑和多子路徑情況下的結(jié)果。其中，單一子路徑在實(shí)例基礎(chǔ)上保留兩站點(diǎn)間距離最短路徑。

由表4可知，考慮路徑選擇的運(yùn)營(yíng)方案比單一子路徑情況更優(yōu)。R實(shí)例，主要通過(guò)減少充電次數(shù)和充電時(shí)間提高收益；C與RC實(shí)例，主要通過(guò)減少車輛運(yùn)行時(shí)間和距離達(dá)到減少運(yùn)營(yíng)費(fèi)用的目的。這是由于單一子路徑為距離最短子路徑，而非時(shí)間最短子路徑，車輛為了滿足乘客出行時(shí)空約束，往往會(huì)改變節(jié)點(diǎn)訪問(wèn)次序，在運(yùn)送途中進(jìn)行充電以滿足出行需求。相比之下，多子路徑的情況可通過(guò)選擇時(shí)間-距離加權(quán)最短子路徑到達(dá)下一個(gè)站點(diǎn)，從而減少電量消耗，降低運(yùn)營(yíng)成本，為運(yùn)營(yíng)商提供更多運(yùn)行方案來(lái)實(shí)現(xiàn)運(yùn)營(yíng)效率的提升。結(jié)果表明，多路徑選擇在提高定制電動(dòng)公交系統(tǒng)充電效率和降低運(yùn)營(yíng)成本方面潛力巨大。

表4 單一子路徑與多子路徑算例對(duì)比結(jié)果Table 4 Comparison results between single path and multiple paths

4 結(jié)論

本文提出一種帶多路徑選擇的定制電動(dòng)公交線路優(yōu)化方法，構(gòu)建了混合整數(shù)規(guī)劃模型?；谧赃m應(yīng)大鄰域搜索算法框架，設(shè)計(jì)針對(duì)站點(diǎn)和充電站的destroy和repair規(guī)則求解模型。在實(shí)例分析中，通過(guò)比較不同充電模式發(fā)現(xiàn)，整車充電模式可有效減少充電成本，增加總收益，而乘客聚類分布和混合聚類分布情況的收益優(yōu)勢(shì)較大；同時(shí)，實(shí)例驗(yàn)證了多路徑選擇的加入可有效節(jié)省充電和運(yùn)營(yíng)費(fèi)用，提高服務(wù)運(yùn)營(yíng)效率。