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

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

0 引言

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

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

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

1 問題描述與模型

1.1 問題描述

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

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

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

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

1.2 模型建立

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

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

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

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

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

2.1 初始解求解

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

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

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

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

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

Step 5 判斷站點數(shù)是否達(dá)到R。如果否，轉(zhuǎn)至Step 2；否則，搜索距離當(dāng)前a最近場站j，選擇最優(yōu)路徑，判斷加入j是否滿足時間窗約束，若滿足，繼續(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é)省運營費用的角度提出與站點相關(guān)的兩個算子?？紤]到電動車在服務(wù)過程中的充電行為是線路規(guī)劃的關(guān)鍵，去除不必要的充電站可有效提高運營效率，故提出針對充電站的destroy算子。具體如下：

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

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

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

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

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

2.3 Repair規(guī)則

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

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

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

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

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

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

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

3 實例研究

3.1 實例設(shè)計

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

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

實例采用40 座的電動公交車，滿電電量為80 kWh，能耗速率為2 kWh·km-1，每輛車的最小負(fù)載為20 人，服務(wù)6 個站點，須在場站服務(wù)時間窗[7:00, 8:30]內(nèi)完成任務(wù)。案例中，場站即為充電站，充電速率為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é)果分析

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

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

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

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

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

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

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

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

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

4 結(jié)論

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