區域內不同層次軌道交通末班車時刻表協同優化

胡勇健 鄭俊鋒 李 莉

(合肥市軌道交通集團有限公司，230601，合肥∥第一作者，高級工程師)

0 引言

規劃建設干線鐵路、城際鐵路、市域(郊)鐵路和城市軌道交通的多層次軌道交通、推進“四網融合”發展，是推進國家新型城鎮化戰略實施，促進城市群、都市圈一體化發展的重要舉措。目前，我國多層次軌道交通仍然面臨功能分工不合理、網絡布局不完善、樞紐銜接不順暢等現實問題。接續優化不同層次軌道交通在“四網”樞紐換乘站和線間換乘站的末班車時刻表，是提高多層次軌道交通網絡時效性與可達性的重要途徑。本文研究不同層次軌道交通末班車時刻表協同優化，主要是通過調整末班車的始發站發車時間與換乘站到達時間，實現不同線路末班車時刻表協同優化，實現區域OD(起訖點)可達。

單一層次軌道交通(如城市軌道交通)時刻表的既有研究已較為完善，其大致將末班車時刻表協同優化目標分為乘客換乘量最大和網絡可達性最大兩類。文獻[1]以區域 OD 可達客流比例最大和各線路收車延時最小為目標，以列車開行間隔及停站時分為約束，構建了雙目標優化模型。文獻[2-3]基于Logit模型計算乘客路徑選擇概率，以時空可達性為目標，構建了雙層規劃模型。文獻[4]基于線網拓撲網絡構建復雜度計算指標，實現末班車協同優化。文獻[5]通過遺傳算法，通過調整列車發車間隔及停站間隔等減少乘客換乘等待時間。文獻[6]參考城市軌道交通末班車時刻表優化方法，實現了公交車末班車時刻表協同優化。

城市軌道交通末班車時刻表協同優化問題常以滯留乘客數量最小為目標，但末班車時段OD間不同路徑存在可行性差異，因此乘客的路徑選擇將直接影響末班車時段乘客滯留數量。而乘客面對多層次軌道交通網絡和單一層次軌道交通網絡時，其路徑選擇行為存在差異：在單一層次軌道交通網絡中，乘客僅以出行總時間最小為目標；而在多層次軌道交通網絡中，乘客的出行路徑涉及不同層次軌道交通間的換乘，除考慮出行時間最小外，乘客還會考慮換乘的復雜度及困難度。本文分別以乘客路徑總的軌道交通復雜度及不同層次軌道交通間收車延時值差異對其進行量化，通過MML模型計算乘客選擇OD間不同路徑的概率，使多層次軌道交通末班車時刻表協同優化到達一定程度，以增強長距離出行客流需求的匹配度。

本文設計了算法來分析、判斷區域OD可達性，從區域OD可達性和運營部門成本出發，構建多目標優化模型，以實現不同層次軌道交通末班車時刻表協同優化。

1 不同層次軌道交通末班車時刻表協同優化問題描述

不同層次軌道交通末班車時刻表協同優化問題可分為2個子問題：區域OD可達性判別問題和末班車時刻表協同優化問題。前者為評價后者質量的重要指標，后者為乘客需求及運營部門效益的集中體現。

區域OD可達與否取決于乘客換乘過程中的冗余時間，如圖1所示。若換乘冗余時間大于或等于零，則該次換乘可行。若乘客選擇路徑中不存在換乘不可行狀態，則判斷OD可達；反之，則不可達。

圖1 換乘冗余時間示意圖Fig.1 Diagram of transfer redundancy time

單一層次軌道交通網絡OD間常存在多條可行路徑，當最佳路徑因線路收車而失效后，乘客亦可選擇替代方案完成出行。如圖2所示，OD間同時包含O—H1—H2—H4—D和O—H1—H3—H4—D(H代表換乘站)兩條可行路徑，當其中一條路徑因收車失效后，乘客可選擇另一條路徑。多層次軌道交通網絡OD間會存在更多可行路徑，然而隨著乘客出行路徑涉及的交通方式和線路的增多，使線路換乘和收車信息愈加復雜。如圖3所示，圖中空心點為不同層次軌道交通間的換乘點；其OD間途經3種交通方式，可行路徑有9條，包含不同層次軌道交通間的5個換乘點，乘客難以在出行路徑失效時選擇當前狀態的最佳替代方案。

圖2 單一層次軌道交通網絡換乘示意圖Fig.2 Diagram of single-level rail transit network interchange

圖3 多層次軌道交通網絡換乘示意圖Fig.3 Diagram of multi-level rail transit network interchange

2 不同層次軌道交通末班車時刻表協同優化數學模型

2.1 模型假設

為簡化模型，增加求解效率，本文多模型做出以下假設：① 列車區間運行時分、停站時分、間隔時間恒定；② 末班車時段內OD已知，乘客換乘時間恒定且不低于平均值；③ 乘客對于單一層次軌道交通網絡熟悉度恒定且已知；④ 乘客出行需求不因實際交通條件而改變。

2.2 模型構建

設θ為乘客對不同層次軌道交通網絡及服務信息的熟悉度，為乘客對不同層次軌道交通間換乘點、線路覆蓋區域及收車時刻差異的量化指標。乘客對網絡及服務的熟悉度隨θ增大而增大。出行路徑涵蓋多層次軌道交通網絡的乘客常具有較低的熟悉度值。本文在文獻[7]研究基礎上，結合本文研究背景，增加了多層次軌道交通網絡中各線路列車收車時刻差異值。本文構建的具體熟悉度計算公式為：

ωe=np+nc+hp+γewi，i∈[1,na]

(1)

式中：

ωe——乘客對各層次軌道交通網絡的熟悉度；

γe——收車時刻差異影響系數；

na——網絡中交通方式數量；

np、nc、hp——分別為單一層次軌道交通網絡中換乘節點數量、不同層次軌道交通間換乘節點數量、單一層次軌道交通網絡中的線路數量；

wi——多層次軌道交通網絡中i交通方式列車收車時刻差異指標。

wi=(Dmax-Dmin)τi

(2)

式中：

τi——時刻差異校正系數；

Dmax、Dmin——分別表示線網中的最晚和最早收車時間。

多層次軌道交通網絡OD間線路信息復雜度計算公式為：

(3)

式中：

ωOD——OD間線路信息復雜度；

δi——乘客最短出行路徑上交通方式Si的被選擇線路是否存在已收車的情況，如已收車，取值為1，反之，取值為0。

文獻中常將θ控制在[0.05,5.00]。本文在θ基礎上根據影響因素進行調整，調整后的乘客對多層次軌道交通網絡的熟悉度θd計算公式為：

θd=θ(1-f1ωOD)

(4)

式中：

f1——網絡復雜度對熟悉度的影響因子。

以乘客出行時間為效用值，利用MML模型，構建乘客在出行條件限制下的路徑選擇概率模型：

(5)

其中：

(6)

式中：

Pr,OD——按OD間出行時間從小到大排列的第r條可行路徑被乘客選擇概率(不包含OD間的最短路徑)；

cr,OD——OD間第r條路徑的效用值；

Lr,OD,i——交通方式Si該路徑上的里程；

vi——交通方式Si的列車運行速度。

未選擇其他可行路徑的乘客成為滯留乘客，總滯留乘客qna計算公式式為：

式中：

tmax——多層次軌道交通網絡中的最晚發車時間；

ξo,d,t——末班車時段乘客選擇軌道交通的比例；

qOD,t——時刻tOD間客流量；

Pr,m,OD——OD間出行時間最短路徑的選擇概率；

Rr,OD,t,min——時刻tOD間第r條可行路徑上列車定員數最小值。

模型目標1總滯留乘客最小數量Z1為：

因運營計劃調整而造成的多層次軌道交通網絡中各線路收車最小延時Z2計算公式即目標2為：

(8)

式中：

Di,j——交通方式Si的第j條線路的收車延時值。

模型的約束條件為：

(9)

式中：

xc,i,j,v、xc,m,i,j,v——第Si種制式軌道交通的第j條線路倒數第c次列車在車站v的到、發時刻；

v——各制式間換乘節點中的制式內換乘節點；

gi,j,v——第Si種制式軌道交通的第j條線路上車站v至v+1間運行時間；

hi.n——線路Si停站時間；

Tl,i——第Si種制式軌道交通的最晚發車時間；

hi.m——線路Si發車間隔時間；

Di,j、Di,j,max——分別表示第Si種制式軌道交通的第j條線路的收車延時值、延時值最大值。

3 多制式軌道交通末班車時刻表協同優化的算法設計

本文基于乘客出行需求及運營部門效益構建了多目標優化模型。對多目標優化模型進行處理時，常引入權重系數實現多目標向單目標的轉化。但這種方式的主觀性較大，結果形式較單一。本文提出嵌套Dijkstra搜索法的NSGA-II求解算法。Dijkstra算法用以求解末班車時段區域OD是否可達，基于NSGA-II算法搜索決策空間中的最優解集合，協調、組合后確定分目標最佳方案。

3.1 改進Dijkstra算法

本文以OD間乘客最晚乘車時間量化區域OD可達性，基于最晚到達時間問題(K-LAP)，從乘客終點站最晚到達時間向前推，以確定最晚乘車時間，設定以下變量：

Xc,i,j,u,v——交通方式Si第j條線路倒數第c次列車在車站u的到達時間；

Xc,m,i,j,u,v——交通方式Si第j條線路倒數第c次列車在車站u的出發時間；

M(u,v,w)——從有向邊e(u,v)至邊e(v,w)的換乘時間；

tc,r,i,j,w,u,v——有向邊e(w,u)至邊e(u,v)的換乘冗余時間；

e(u,v)-——有向邊的上一可行邊；

E*——不同層次軌道交通的換乘節點與單一層次軌道交通換乘節點組成邊的集合(利用標記法計算時僅考慮E*，其余邊利用E*內涉及的關鍵節點進行推算)。

具體算法步驟如下：

步驟1：標記值初始化。針對每一終到點D，搜索其與不同層次軌道交通的換乘節點與單一層次軌道交通換乘節點組成邊的集合，標記c(u,v)=X1,m,i,j,u,v，其余邊標記為0。

步驟2：若E*內所有c(o,v)≥c(u,v)，算法轉至步驟6。o節點標記值即為起訖點OD間的最晚乘車時間，不滿足則繼續。

步驟3：記E*內c(u,v)最大的邊為e(u*,v*)，標記值記為c(u*,v*)。

步驟4：搜索e(u*,v*)的起點v*的所有鄰接邊e(w,u*)，確定換乘可行的邊，即滿足tc,r,i,j,w,u,v≥0，記搜索的列車為c*，tc,r,i,j,w,u,v=c(u*,v*)-M(u,v,w)-Xc,i,j,u,v，基于初始出行路徑客流qOD，以路徑選擇概率Pr,OD計算可行路徑選擇客流量。

步驟5：針對以u*為有向邊的邊e(u,v)更新其標記值c(u,v)，判斷e(u,v)倒數c*列車在u的發車時間Xc,m,i,j,u,v與c(u,v)的大小關系。若Xc,m,i,j,u,v>c(u,v)，則c(u,v)=Xc,m,i,j,u,v、e(u*,v*)-=e(u*,v*)，返回步驟2。

步驟6：算法停止。輸出OD間乘客最晚乘車時間，c(o)=maxc(w,u),依順序輸出c(w,u)，不可行的上一條可行邊即為OD間最晚可達路徑。

3.2 NSGA-II算法

NSGA-II算法為基于Pareto最優解架構建立的優化算法，一定程度避免了多目標優化算法中權重取值的主觀性。本文將各OD間列車始發時刻作為算法基因，以染色體表征各方案，染色體數目為多層次軌道交通網絡內線路數總和。在算法進化階段，利用距離大小與各基因支配關系對個體進行篩分，最后基于融合變異隨機法與單點交叉法的混合進化法處理個體，當目標函數值波動范圍在閾值內時，算法停止。

4 實例分析

多層次軌道交通網絡常包含高速鐵路、城際鐵路、市域鐵路、城市軌道交通。本文以高速鐵路與城市軌道交通的末班車時刻表協同優化為例進行實力驗證，以合肥地鐵、合福高鐵、合武高鐵、合蚌高鐵、商杭高鐵構成的多層次軌道交通網絡為例分析模型算法的合理有效性。截止2022年5月，合肥地鐵共開通5條線路，共有122座車站投入使用；線路內部共設8座換乘站，其中與高速鐵路換乘的換乘站共有2座。基于多層次軌道交通網絡特征構建城市軌道交通、高速鐵路的雙層復合拓撲網絡，換乘信息如表1所示。

表1 合肥地鐵各線與合肥各高鐵線的換乘信息表

城市軌道交通與高速鐵路的列車收車時間有差異，本文僅選取城市軌道交通末班車時段內的列車進行時刻表優化。現僅對2022年2月1日—28日的22:00—23:50時段內日平均客流量進行分析。表2為合肥地鐵末班車OD日均客流量。表3為各高鐵線路部分末班車日均客流量。部分模型參數取值見表4。

表2 合肥地鐵2022年2月1日—28日部分末班車22:00—23:50時段內日均客流量

表3 合肥各高鐵線路2022年2月1日—28日部分列車22:00—23:50時段內日均客流量

利用Matlab軟件編程求解模型。NSGA-II 算法參數設置為：初始種群規模為150個，最大迭代次數為250次，最優前段個體系數為0.32。算法運行結束后共生成15個Pareto最優解。

表4 模型參數取值表Tab.4 Model parameter value

算法生成的Pareto front圖及Pareto分析表分別如圖4和表5所示。

圖4 Pareto front圖Fig.4 Diagram of Pareto front

由圖4可見：末班車收車總延時值與區域OD不可達比例呈現近似反比的關系。當區域OD不可達比例為最小值0.149 6與最大值0.155 7時，末班車收車總延時值分別取得最大值12.715 min與最小值-10.272 min(負值表示優化方案末班車收車時間早于現行方案的)。

表5展示了部分Pareto解集合，其目標函數包含末班車收車最小延時值和不可達最小客流量2個子目標；方案序號從小到大表示末班車收車最小延時值目標的權重從小到大，不可達最小客流量目標的權重從大到小。序號1的方案具有最小的不可達比例，同時其具有最大的末班車收車延時值，可達比例較原方案增加了24.29 %。最優方案集合中，客流不可達比例隨末班車延時值減少而提高，這是由于提前收車致使乘客的出行路徑大量失效，產生大量不可行客流。第7個方案后，具有比現有開行方案更早的收車時間，在此條件下運營部門成本較低，同時具有比現行方案更低的不可達比例,因此運營部門可根據不可達比例與末班車收車延時值側重于解集中選擇合適的方案。

表5 部分Pareto最優解分析表Tab.5 Partial Pareto optimal solution analysis

5 結語

本文研究了多層次軌道交通網絡末班車時刻表協同優化問題，并以合肥地鐵、合福高鐵、合武高鐵、合蚌高鐵、商杭高鐵組成的多層次軌道交通網絡為例進行了實例分析。結果表明：最優方案集均在一定程度優于現行方案，其中不可達比例最低的方案可達客流增加24.29%，發車時間推后56 s；不可達比例優于現行計劃的方案中，末班車收車延時最小值為-10.272 min，城市軌道交通在10:50的不可達客流數量達到峰值，因此需增加相應時段的列車開行頻率。實例分析表明模型具有有效性，為多層次軌道交通網絡協調及決策提供了一定的理論支撐。