楊亞璪,吳 釗,賓 濤

(1. 重慶交通大學 交通運輸學院,重慶 400074;2. 江蘇緯信工程咨詢有限公司,江蘇 南京 210014;3. 重慶交通大學 智能綜合立體交通重慶市重點實驗室,重慶 400074)

0 引 言

根據(jù)交通運輸部數(shù)據(jù),截至2022年末,全國54個城市開通運營城市軌道交通線路共292條,運營里程為9 554.6 km;同時,公共汽電車運營線路開通7.8萬條,公共汽電車70.32萬輛,其中純電動車45.55萬輛,占比64.8%。電動公交憑借其節(jié)能、低碳等優(yōu)勢逐漸確立了在城市公交運營中的主體地位。與傳統(tǒng)燃油公交相比,電動公交尚存在續(xù)航時間不能滿足全日運行、充電周期長等問題,對公交車輛的調(diào)度造成較大影響。軌道交通作為城市公共交通的重要組成部分,軌道交通站點的影響范圍較大,部分乘客在軌道交通站點存在換乘接運公交前往目的地的需求。通過對接運電動公交與軌道交通的乘客接運關(guān)系進行分析,建立接運電動公交更優(yōu)調(diào)度模型,對提高乘客運輸效率與滿意度等具有積極意義。

在電動公交的調(diào)度優(yōu)化模型構(gòu)建方面,TANG Xindi等[1]分別構(gòu)建了動、靜態(tài)兩種模型,將時間與道路狀況的隨機性考慮在內(nèi),對電動公交車隊進行周期性安排;T.PAUL等[2]從整體電網(wǎng)供電狀態(tài)出發(fā),將電動公交與化石燃料公交一同進行調(diào)度,并給出了電動公交的充電計劃;C.M.CHAN等[3]從配電網(wǎng)有限的條件出發(fā),以優(yōu)化接運電動公交配置為目標,構(gòu)建了離散非線性優(yōu)化模型來解決電動公交車輛的配置問題;唐春艷等[4]考慮不同電動車車型的運營差異,構(gòu)建多目標優(yōu)化模型,研究了不同車型混合使用情況下的發(fā)車時刻表;ZHU Chao等[5]建立具有特定約束條件的單車場車輛調(diào)度模型來解決電動汽車調(diào)度問題;J.P.FONSECA等[6]將發(fā)車時刻表和車輛調(diào)度問題同時考慮,構(gòu)建了一個轉(zhuǎn)移成本和運行成本最小化的雙目標混合整數(shù)規(guī)劃模型。

公交調(diào)度和車輛調(diào)度問題是NP-hard問題,A.S.PEPIN等[7]采用5種不同的啟發(fā)式算法進行對比分析,認為大領(lǐng)域搜索啟發(fā)式算法解決公交調(diào)度問題最有效;SHEN Yindong等[8]通過使用領(lǐng)域搜索法與一種改進的禁忌搜索算法對車輛與駕駛員調(diào)度模型進行求解;ZHANG Le等[9]、劉昊翔等[10]采用列生成算法對構(gòu)建的模型進行求解;DOU Xueping等[11]采用人工蜂群算法對所構(gòu)建的模型進行求解,并通過對比發(fā)現(xiàn)該算法的收斂性較好。

綜上,目前的研究主要關(guān)注電動公交自身運營的調(diào)度策略,構(gòu)建的優(yōu)化模型中主要考慮充電、成本等約束條件,并采用啟發(fā)式算法對所構(gòu)建的模型求解。

筆者擬通過對電動公交與軌道交通接運關(guān)系的分析,構(gòu)建一個混合整數(shù)非線性規(guī)劃(mixed integer nonlinear programming,MINLP)模型,以實現(xiàn)3個目標:①盡量減少已服務乘客的總等候時間成本;②將未服務乘客的換乘失敗成本降至最低;③使公交公司的總運營成本最小。利用人工蜂群算法(artificial bee colony algorithm,ABC)求解模型,給出接運電動公交的調(diào)度策略與最優(yōu)發(fā)車時刻表,為接運電動公交調(diào)度問題提供解決思路。

1 問題描述

常規(guī)公交是公共交通方式的重要組成部分,常規(guī)公交與軌道交通之間存在交互脅迫的關(guān)系[12]。在公共交通網(wǎng)絡中,軌道交通是“骨架”,而常規(guī)公交則用于滿足沿線居民的短途出行需求。

軌道交通與常規(guī)公交的換乘模式主要分為站內(nèi)換乘、接續(xù)換乘、站外換乘[13],文中主要研究的換乘模式為站外換乘。當?shù)孛婀谎鼐€的出行需求中加入了軌道交通換乘需求時,原有的調(diào)度策略會出現(xiàn)不能適應的情況。此時,地面公交被賦予接運屬性,即公交車輛到達接駁站點時,需要為有換乘需求的乘客提供足量、及時和有效服務。

假設軌道交通站200 m范圍內(nèi)存在接運電動公交停靠站,乘客可從軌道交通換乘至電動公交。換乘乘客由于步行速度不同,從軌道交通站步行至電動公交站的時間為1.5～3.0 min,而乘客能夠接受的等待時間最長為8 min。早高峰08:00—08:30內(nèi),共有6輛電動公交與同時段抵達的5列軌道交通列車形成接運關(guān)系,見圖1。由于兩類車輛到站時刻、換乘乘客步行時間的差異,接運電動公交采用怎樣的調(diào)度策略提升乘客換乘的滿意度,同時兼顧公交企業(yè)的運營成本,此為文中主要研究問題。

圖1 電動公交與軌道交通接運關(guān)系Fig. 1 Relation between electric feeder bus and rail transit

2 建立模型

2.1 基本假設

為反映真實情況,作以下基本假設:①軌道交通的列車運行嚴格執(zhí)行預先計劃的時間表,到站時刻沒有延誤和提前;②選擇換乘接運公交線路的乘客,只有在超過等待時間上限后,才會考慮選擇其他方式離開接運站點;③換乘乘客從軌道交通站步行至電動公交站所需時間根據(jù)現(xiàn)場測算給出;④每輛電動公交的容量一致,區(qū)別在于到達接運站點時的滿載率不同;⑤如果換乘乘客排隊,則按照電動公交的最大載客量進行核減后,確定成功換乘的乘客數(shù)量。

2.2 目標函數(shù)

令SB為服務于目標接運公交線路的公交班次集合,J為SB內(nèi)可用接運公交的行程總數(shù),j為可用的接運電動公交行程序號,j=1,2,…,J;令SR為某一時段內(nèi)軌道交通列車到達的集合,I為SR內(nèi)軌道交通列車的到達行程總數(shù),i為軌道交通列車的到達車次,i=1,2,…,I。以每次行程中接運電動公交j的發(fā)車時間dj和荷電狀態(tài)Oj為決策變量,以乘客和公交企業(yè)的廣義成本z為目標函數(shù):

minz=zw+zf+zo+zc

(1)

在給定時間段內(nèi),乘坐接運電動公交j的乘客總等待時間成本zw如式(2):

(2)

式中:μ1為總等待時間成本的單位值,元/min;sij為實際從i列車轉(zhuǎn)移到接運公交j的乘客數(shù)量,人;dj為接運電動公交j的發(fā)車時刻;Ai為軌道交通列車i的換乘乘客抵達公交車站時刻。

在給定時間內(nèi)換乘失敗的乘客換乘總失敗成本zf見式(3):

(3)

式中:μ2為總轉(zhuǎn)移失敗成本的單位值,元/人;Pi為軌道交通列車i產(chǎn)生的換乘需求。

公交公司的運營成本分為接運電動公交的使用成本與充電成本,其中接運電動公交的車輛使用成本zo見式(4):

(4)

式中:μ3為接運電動公交使用成本的單位值,元;φ為電動公交車輛使用的年化系數(shù);Yj為0、1變量,若行程j被接運電動公交執(zhí)行則Yj=1,否則Yj=0。

接運電動公交的充電成本zc見式(5):

(5)

式中:μ4為充電成本的單位值,元/(kW·h);εj為二元變量,用作判斷是否需要充電的依據(jù);Oj為電池的荷電狀態(tài),指電池在一定的放電倍率下,剩余電量與相同條件下額定容量的比值;Du為電動公交u的電池容量,kW;lj為需要被執(zhí)行行程j的里程,km;C為電動公交車行駛過程中電量的平均消耗速率,(kW·h)/km。

式(5)中,設置的公交電池荷電狀態(tài)的最大、最小值分別為Omax和Omin。每一班電動公交發(fā)車時檢查荷電狀態(tài)Oj,若Oj≤Omin或OminOmax時,則停止充電;當Oj≥lj·C/Du時,則不需要充電,充電與否通過0、1變量εj判斷。

2.3 約 束

設dj為在給定時間段內(nèi)為l線服務的接運公交j的到站時間,見式(6)～式(9):

dj=dj-1+hj-1,j=2,3,…,J

(6)

Tmin≤d1

(7)

Hmin≤hj≤Hmax,j=1,2,…,J-1

(8)

d1,hj∈Z+,j=1,2,…,J-1

(9)

式中:hj-1為接運電動公交j-1與j之間的間隔時間,min;Tmin為給定時間段的開始時間,min;Hmin、Hmax分別為最小和最大允許間隔時間,min;Z+為一組正整數(shù)。式(7)迫使接運公交線路l的第一班車在給定時間段內(nèi)發(fā)車;式(8)保證了時刻表的實用性。可供使用的接運電動公交車數(shù)量應不少于J=「TP/Hmin?,其中TP為給定時間段的持續(xù)時間。為便于實際公交運行,將終點站出發(fā)時間和發(fā)車間隔設置為整數(shù)變量,如式(9)。

當接運公交j的終點站出發(fā)時間和來自列車i的乘客到達公共汽車終點站的時間之間的差值為非負數(shù)時,來自列車i的乘客有機會登上接運公交j。二元變量yij用來表示來自列車i的乘客是否有機會登上接運公交j,見式(10)、式(11):

yij∈{0,1}

(10)

M·(yij-1)≤dj-Ai

(11)

式中:i=1,2,…,I;j=1,2,…,J;M為一天24 h的分鐘數(shù),M=1 440;Ai為來自列車i的乘客到達接運公交車站的時間。如果來自列車i的乘客有機會登上接運公交j,則二進制變量yij為1,否則為0。

由于接運公交的載客量固定,yij=1時,但是來自列車i的乘客可能無法登上接運公交j。當yij=1且接運公交j上有可用空間時,來自i列車的乘客將被允許登上接運公交j。sij見式(12):

(12)

當乘客從列車i開始登上接運公交j時,接運公交j上的乘客人數(shù)見式(13):

(13)

(14)

式中:i=1,2,…,I;j=1,2,…,J;wij為接運公交j-1被調(diào)度后,等待接運公交j的來自列車i的乘客數(shù)量;Lij為在接運公交j調(diào)度前已經(jīng)停止等待接運公交j的來自列車i的乘客數(shù)量。變量wij與Lij見式(15)、式(16):

(15)

Lij=?wij·xij·α」

(16)

式中:i=1,2,…,I;j=1,2,…,J;pi為列車i排隊的乘客人數(shù);? 」表示該數(shù)字應該向下舍入,以確保Lij是整數(shù)變量;xij為二元變量,當接運公交j的出發(fā)時刻與列車i乘客的到達時刻之差大于TL時,xij=1,否則xij=0,見式(17)、式(18):

M·(xij-1)

(17)

xij∈{0,1}

(18)

式中:i=1,2,…,I;j=1,2,…,J。

第i列車乘客中參與排隊的乘客數(shù)量見式(19):

pi=βPi-βmin{max{Q-qi,0},P}+min{max{Q-qi,0},P}

(19)

式中:i=1,2,…,I;qi為從i列車上下來的乘客到換乘站點時隊伍的長度;Q為最長可容忍排隊長度;β為乘客加入隊列的概率。由式(19)可知,當qiQ時,β<1。qi見式(20):

(20)

3 求解算法

ABC算法是一種基于蜜蜂群覓食行為的啟發(fā)式算法,其中被稱為食物源的解決方案由人工蜜蜂隨時間修改,蜜蜂的目標是發(fā)現(xiàn)具有較高花蜜量的食物源[14]。ABC算法已被廣泛應用于解決公交優(yōu)化問題[15-16]。

3.1 算法描述

在給定起點站發(fā)車時間與接運電動公交容量的情況下,根據(jù)蜂群算法的原理可得出,一個解決方案(即一個食物源)由2J-1個元素組成,代表了J-1個時間間隔和J班次電動公交車出發(fā)時的荷電狀態(tài),見圖2。

圖2 解決方案示意Fig. 2 Schematic diagram of the solution scheme

每個元素ej是一個介于0和1之間的隨機數(shù),由偽隨機數(shù)發(fā)生器產(chǎn)生。根據(jù)算法設計流程,接運電動公交在站點處發(fā)車時間間隔的解碼原理為hj=?Hmin+(Hmax-Hmin)」×ej。電動公交荷電狀態(tài)的解碼原理如下:當e2J-1滿足Oj≤Omin或OjOmin后發(fā)車;當e2J-1滿足Oj>Omax時,無須充電直接發(fā)車。

3.2 算法步驟

步驟1初始化食物源Nf的數(shù)量、雇傭蜂Ne的數(shù)量、觀察蜂No的數(shù)量、預定的試驗次數(shù)限制和最大迭代次數(shù)Nmax,設迭代次數(shù)的計數(shù)器N=1。

步驟2將雇傭蜂Ne與食物源一一對應,為每只蜜蜂隨機生成一個2J-1維的可能解,并計算其適應度值fi=1/(1+zi),其中,zi為該電動公交運營時刻表下的總成本。

步驟4對于剩余的蜜蜂,在食物源附近進行鄰域搜索,尋找新的食物源。

步驟5計算新生成食物源的適應度值并進行評估,記錄當前蜜蜂尋找到的最優(yōu)食物源信息,即發(fā)車時刻方案。

步驟6當N>Nmax時,終止算法并輸出最優(yōu)解;否則,設置N=N+1,重復步驟3～步驟5。

4 算 例

重慶兩江公交886路作為與軌道交通6號線光電園站點的接運電動公交,主要承擔軌道交通線路之間的換乘及軌道交通站點到渝北區(qū)光電園周邊各大寫字樓之間的乘客疏解功能,如圖3。

圖3 重慶兩江公交886路上下行路線Fig. 3 Upward and downward routes of Chongqing Liangjiang bus route 886

公交886路下行(軌道康莊站—重慶兒童公園)06:10開班,21:00收班;其上行(重慶兒童公園—軌道康莊站)早上06:30開班,21:00收班,全程16.7 km,途經(jīng)24個站點。路線全線運營平均耗時68 min,站間距及站間行駛時長如表1。其中,該線路在軟件園渝興廣場站實現(xiàn)與軌道6號線光電園站換乘,主要連接山頂總部基地、服務貿(mào)易產(chǎn)業(yè)園、互聯(lián)網(wǎng)產(chǎn)業(yè)園3個工作集散地。

表1 886路公交站間距及站間運營時間

車輛規(guī)格方面,866路公交車采用宇通ZK6117BEV純電動客車,座位數(shù)為35個,滿載人數(shù)cj=60人,電池容量Du=180 kW·h,設Omin=0.2。該電動客車在滿電量情況下行駛里程lj≥130 km。重慶市工作日早高峰公交車行駛速度約為14.1 km/h,公交優(yōu)先道的車速約為15.8 km/h,可以計算電量平均消耗速率C=1.38 (kW·h)/km,額定充電功率取120 kW,充電效率為0.9。

假設乘客刷卡出站后步行至公交站所用時間為2 min,乘客換乘后需要乘坐公交在上班時間前抵達公司附近公交站。以終點為互聯(lián)網(wǎng)產(chǎn)業(yè)園附近的乘客為例,需要其至少在08:30前抵達換乘公交站,乘坐公交車前往公司。軌道交通6號線在光電園站共有53趟地鐵列車在07:00—08:30時間段內(nèi)到達,相關(guān)班次的地鐵到達時間見表2。

表2 重慶軌道交通6號線光電園站車輛運行時刻

假設該公交站點本地乘客的平均到達率λ=2 prs/min,給定時段內(nèi)允許的最小發(fā)車間隔和最大發(fā)車間隔Hmin、Hmax分別設置為1、5 min。在研究時段內(nèi)第1班抵達光電園站的換乘乘客步行至換乘公交站,用時以2 min計,接運公交最早抵達該接運公交站點的時間Tmin應為07:03。根據(jù)本地乘客到達率與換乘到達人數(shù),得到接運公交可到達的班次及換乘人數(shù)。具體07:00—08:30時間段內(nèi)接運需求見表3。

表3 886路公交車07:00—08:30時間段內(nèi)接運需求

最長可容忍的排隊長度Q設置為35名乘客。最長可容忍等待時間TL設置為8 min,參數(shù)α和β均為0.5。接運公交的規(guī)模J為20輛,滿載時載客量為60名乘客,接運公交的運營成本參數(shù)為1.7。其中參數(shù)μ1通過重慶市城鎮(zhèn)常住居民人均可支配收入進行換算,取0.36元/min:μ2通過平均等待候車超過Q后放棄的人數(shù)與重慶市人均工資進行換算,取1.17元/人;μ3通過選取電動公交購置成本、維修成本與使用壽命換算為每日每趟成本,取43.28元;根據(jù)電動公交的使用壽命確定其使用成本的年化系數(shù)φ=0.187 4;用公交車充電電價表示μ4,取0.82元/(kW·h)。

在蜂群算法中,食物源、雇傭蜂和觀察蜂的數(shù)量均設定為90。最大迭代次數(shù)設為2 000。在MATLAB(R2016A)環(huán)境中進行數(shù)值測試,并且在具有英特爾核心I7-1165G7 CPU的電腦上執(zhí)行所有計算。

4.1 最優(yōu)解

建立MINLP模型并運用蜂群算法得到合適的接運電動公交到達時刻為07:07、07:15、07:20、07:25、07:30、07:34、07:39、07:43、07:47、07:50、07:54、07:58、08:03、08:07、08:11、08:16、08:21、08:25,共18班。由于軌道交通光電園站與公交886路在軟件園渝興廣場站換乘,接運電動公交從始發(fā)站到達換乘站的距離為10.7 km,需要行駛約42 min,可得到這18班電動公交始發(fā)站的發(fā)車時刻,見表4。

表4 優(yōu)化后的發(fā)車時間

該時刻表下的總成本為1 355.32元,其中總等待時間成本為298.17元,總轉(zhuǎn)移失敗成本為84.03元,電動公交總運營成本為867.40元,電動公交車充電成本為105.71元。

目前該線路早高峰采用均勻發(fā)車時刻進行發(fā)車,在研究時段內(nèi)發(fā)車班次為18班,發(fā)車間隔為5 min,總成本為1 773.05元。與現(xiàn)有均勻時刻相比,采用該模型優(yōu)化后的時刻表在總成本上降低了23.56%。

4.2 模型評價

為了進一步評價所提出方法的適用性,將其與遺傳算法和粒子群算法進行比較。與ABC算法不同,遺傳算法需要交叉和變異算子來生成新的解,交叉率和變異率分別為0.9和0.5。在粒子群算法中,每個粒子的位置就是一個潛在解,在ABC算法中,粒子的數(shù)量等于食物源的數(shù)量。將粒子群算法的慣性權(quán)值設置為0.7,學習因子1設置為2.0,學習因子2設置為2.0。與ABC算法類似,遺傳算法和粒子群算法的最大迭代次數(shù)均被設置為2 000次,3種算法迭代曲線見圖4。

圖4 3種算法的收斂曲線Fig. 4 Convergence curves of three kinds of algorithms

3種算法在求解MINLP模型過程中均有較好的收斂性,其性能和優(yōu)化結(jié)果見表5。3種算法中ABC算法得到的最優(yōu)解優(yōu)于遺傳算法與粒子群算法得到的最優(yōu)解,總成本分別為1 355.32、1 393.56、1 361.82元。由圖4可知,收斂過程中粒子群算法很快達到收斂,并維持該收斂結(jié)果較長代數(shù);人工蜂群算法收斂過程耗時較長,在算法迭代至800次左右時再次給出更優(yōu)結(jié)果。

表5 3種算法的性能對比

5 結(jié) 語

在考慮公交公司運營成本的同時,充分考慮公交車容量限制與續(xù)航能力的約束,將乘客換乘等候與換乘失敗兩部分成本考慮在總成本內(nèi),能夠更好地從乘客角度出發(fā)優(yōu)化電動公交的調(diào)度。筆者提出的基于MINLP的電動公交時刻表優(yōu)化模型以及求解算法,通過優(yōu)化發(fā)車時間間隔降低總運營成本,求解過程相比遺傳算法和粒子群算法在效率與質(zhì)量上均更優(yōu)。由于考慮的換乘需求是已知的,而實際的換乘需求受換乘距離、等待時間等因素的影響不斷變化,后續(xù)應繼續(xù)研究動態(tài)換乘需求的電動公交調(diào)度問題。