軌道交通單線接運電動公交調度優化模型

楊亞璪,吳 釗,賓 濤

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

0 引 言

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

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

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

綜上,目前的研究主要關注電動公交自身運營的調度策略,構建的優化模型中主要考慮充電、成本等約束條件,并采用啟發式算法對所構建的模型求解。

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

1 問題描述

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

軌道交通與常規公交的換乘模式主要分為站內換乘、接續換乘、站外換乘[13],文中主要研究的換乘模式為站外換乘。當地面公交沿線的出行需求中加入了軌道交通換乘需求時,原有的調度策略會出現不能適應的情況。此時,地面公交被賦予接運屬性,即公交車輛到達接駁站點時,需要為有換乘需求的乘客提供足量、及時和有效服務。

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

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

2 建立模型

2.1 基本假設

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

2.2 目標函數

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

minz=zw+zf+zo+zc

(1)

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

(2)

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

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

(3)

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

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

(4)

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

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

(5)

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

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

2.3 約 束

設dj為在給定時間段內為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+為一組正整數。式(7)迫使接運公交線路l的第一班車在給定時間段內發車;式(8)保證了時刻表的實用性?？晒┦褂玫慕舆\電動公交車數量應不少于J=「TP/Hmin?,其中TP為給定時間段的持續時間。為便于實際公交運行,將終點站出發時間和發車間隔設置為整數變量,如式(9)。

當接運公交j的終點站出發時間和來自列車i的乘客到達公共汽車終點站的時間之間的差值為非負數時,來自列車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的分鐘數,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上的乘客人數見式(13):

(13)

(14)

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

(15)

Lij=?wij·xij·α」

(16)

式中:i=1,2,…,I;j=1,2,…,J;pi為列車i排隊的乘客人數;? 」表示該數字應該向下舍入,以確保Lij是整數變量;xij為二元變量,當接運公交j的出發時刻與列車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列車乘客中參與排隊的乘客數量見式(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算法是一種基于蜜蜂群覓食行為的啟發式算法,其中被稱為食物源的解決方案由人工蜜蜂隨時間修改,蜜蜂的目標是發現具有較高花蜜量的食物源[14]。ABC算法已被廣泛應用于解決公交優化問題[15-16]。

3.1 算法描述

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

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

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

3.2 算法步驟

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

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

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

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

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

4 算 例

重慶兩江公交886路作為與軌道交通6號線光電園站點的接運電動公交,主要承擔軌道交通線路之間的換乘及軌道交通站點到渝北區光電園周邊各大寫字樓之間的乘客疏解功能,如圖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,途經24個站點。路線全線運營平均耗時68 min,站間距及站間行駛時長如表1。其中,該線路在軟件園渝興廣場站實現與軌道6號線光電園站換乘,主要連接山頂總部基地、服務貿易產業園、互聯網產業園3個工作集散地。

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

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

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

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

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

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

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

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

4.1 最優解

建立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路在軟件園渝興廣場站換乘,接運電動公交從始發站到達換乘站的距離為10.7 km,需要行駛約42 min,可得到這18班電動公交始發站的發車時刻,見表4。

表4 優化后的發車時間

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

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

4.2 模型評價

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

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

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

表5 3種算法的性能對比

5 結 語

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