運行計劃約束下的動態(tài)可達性分析與計算

郭建媛，賈利民，秦 勇

（北京交通大學a.交通運輸學院；b.軌道交通控制與安全國家重點實驗室，北京100044）

運行計劃約束下的動態(tài)可達性分析與計算

郭建媛a，賈利民*b，秦 勇b

（北京交通大學a.交通運輸學院；b.軌道交通控制與安全國家重點實驗室，北京100044）

在城市軌道交通中，隨著各條線路的末班車按運行計劃逐站完成載客任務，路網上OD兩點間的可達路徑逐漸變少，直至兩點間不可達，這樣的路網服務能力隨時間的動態(tài)變化，稱為動態(tài)可達性.本文研究運行計劃約束下的路網動態(tài)可達性計算方法，以支持末班車開行的優(yōu)化，實現(xiàn)搭乘末班車出行乘客目的地可達的最大化.本文首先分析了末班車開行帶來的動態(tài)可達性，給出了最晚可達時間、路徑可達性、OD可達性定義.在此基礎上，提出了末班車開行下路網可達性的計算方法與最晚可達時間求解的遞歸算法.最后，以路網可達性最大為目標，將可達性計算方法應用于末班車換乘銜接優(yōu)化.通過算例分析驗證了可達性計算方法的有效性.

城市交通；可達性；銜接方案；城市軌道交通；末班車

1 引 言

可達性經常被用來衡量交通系統(tǒng)中的服務提供能力或者達到某地的便捷性，可達性指標反映了去往不同地點的交通運輸系統(tǒng)的服務水平[1].可達性可以指從一個車站到達目的車站的便捷程度[2]，也可以指路網上OD之間能否到達[3].

隨著末班車的運行，路網上兩點間的可達路徑在逐漸變少，直至兩點不可達.這樣的路網服務能力隨時間的動態(tài)變化，本文稱之為動態(tài)可達性.不同的運行計劃，將帶來不同的可達性變化，從而影響路網的服務水平和乘客的出行質量.

近年我國已有學者開始對末班車造成的OD間可達性進行研究.羅欽等人[3]分析了列車運行計劃開行帶來的OD動態(tài)可達現(xiàn)象，提出通過優(yōu)化列車運行銜接和信息發(fā)布來提高出行目的地可達；江志彬等[4]提出了時間窗約束下的OD可達性計算方法，給出OD間的可達狀態(tài)與可達路徑的推算流程；徐瑞華等[5]提出末班車銜接優(yōu)化方案來提高換乘可達性.已有研究在為可達性在末班車開行優(yōu)化的應用打下基礎，但目前的研究無論是從可達性的分析定義，還是其在銜接優(yōu)化方面的效果，都有待進一步研究.

本文在已有研究的基礎上，進一步分析動態(tài)可達性內涵特征，以提高路網服務能力為目標，給出適用于末班車開行優(yōu)化的可達性定義與計算方法.

2 可達性分析

2.1 可達性相關定義

OD間的載客服務隨時間的動態(tài)變化反映了運行計劃影響路徑可達和OD可達的過程.在已有可達性定義的基礎上，本文結合站點間服務能力隨運行計劃的變化特點，做出了更進一步的擴充，包括路徑可達性，OD可達性.

路徑可達性指經特定路徑能否從O到達D；此處使用途徑車站的有序集合 ＜O,S0,…,Sn,D＞(n≥0)表示路徑R；使用FR表示路徑R的可達性，當FR=1時表示路徑R可達，當FR=0時表示路徑不可達.假設OD間的所有物理聯(lián)通的路徑的集合為ASOD，對于任意路徑R(R∈ASOD),FR會隨時間發(fā)生從1到0的階躍變化.

在此定義FR從1到0躍變的時間點為路徑R的最晚可達時間，用TLR表示，當乘客不晚于TLR到達O點站臺(后續(xù)將到達O點站臺的時間稱為待發(fā)時間，使用TAO表示)，則可搭乘列車經路徑R到達目的地，當乘客待發(fā)時間晚于TLR，則錯過路徑R上的末班車，無法經路徑R到達D.FR與待發(fā)時間關系如式（1）所示.

OD可達性指能否從O通過路網到達D，及其可達的便捷程度.使用FOD表示OD間可達性，當FOD=0時表示OD不可達，當FOD＞0時表示OD可達，其計算如式（2）所示.

式中 TLOD表示OD的最晚可達時間，當乘客待發(fā)時間晚于TLOD，則通過OD間的任何路徑都無法到達目的地D，待發(fā)時間不晚于TLOD，則存在物理聯(lián)通且可達的路徑R(FR=1?R∈ASOD)可以從O到達D；CSOD表示OD之間各條物理路徑均可達時，其中的平均成本最小的路徑（簡稱靜態(tài)最優(yōu)路徑）所對應成本；CDOD表示OD之間實際可達的路徑中的成本最小的路徑（簡稱動態(tài)最優(yōu)路徑）所對應成本；α為可調節(jié)的參數(shù).人們日常出行傾向于選擇靜態(tài)最優(yōu)路徑，當受到運行計劃約束出現(xiàn)部分路徑不可達的情況，則更愿意選擇動態(tài)最優(yōu)路徑.

2.2 末班車對可達性的影響

對于OD之間無需換乘的路徑，乘客搭乘末班車一定可以到達目的地，而對于OD之間需要換乘的路徑，乘客搭乘末班車能否到達目的地受到末班車間換乘銜接的影響[3].

如圖1所示，S1和S2是換乘站，A、B、C是中間站,L1和L2為雙向線路，圖中箭頭方向是線路下行方向，使用L11L12L21L22分別表示兩條線路的上下行，則存在四個換乘方向：L11-S1-L21、L21-S2-L11、L22-S1-L12和L12-S2-L22.

圖1 換乘銜接示例Fig.1 Example of connections

當搭乘末班車在換乘方向L11-S1-L21上可以銜接時，則搭乘末班車在換乘方向L21-S2-L11無法銜接；當搭乘末班車在換乘方向L22-S1-L12上可以銜接時，則搭乘末班車在換乘方向L12-S2-L22無法銜接.因此，末班車開行會帶來換乘銜接間的互相約束，進一步在不同路徑的可達性之間產生相互約束.

以從A到B為例，存在兩條可能的路徑：R1：A-S2-B和R2：A-S1-C-B，僅當L22-S1-L12和L12-S2-L22均無法銜接時，R1和R2均不可達，AB間不可達.因此，換乘無法銜接時路徑不可達，但OD之間不一定不可達.

假設存在某段時間[T0,T1]，L12-S2-L22無法銜接，但L22-S1-L12可以銜接時，則經由路徑R2可以到達B，而經由R1無法到達B，此時 R2為[T0,T1]時段內的AB間的動態(tài)最優(yōu)路徑.在此時間段內從A仍然能夠到達B，出行成本會產生變化，即OD可達性在大于0的情況下數(shù)值發(fā)生變化.

3 末班車開行下的路網可達性計算方法

3.1 路網可達性計算方法

路網向乘客提供的服務能力既與目的地能否可達相關，又與到達目的地所消耗的成本相關，當乘客出行對應的FOD數(shù)值越大，則說明路網向乘客提供的服務能力就越好.因此，定義路網可達性來衡量路網向乘客提供的到達目的地的便捷程度，其計算用式（3）表示.

式中 G表示路網站點集合；fOD表示從O去往D的客流量.

可以用末班車開行下的路網可達性ALG來衡量末班車銜接效果，計算用式（4）表示.

式中 LO表示從O點出發(fā)的末班車發(fā)車時間.

3.2 末班車開行下的路網可達性計算流程

為了計算得到式（4）中的ALG，主要求解流程如下：

步驟1 加載路網物理結構GS、運行計劃TG和OD間的客流量 fOD；

步驟2 計算所有 CSOD和 TLOD(O∈GS, D∈GS,O≠D)；

步驟3 每一對OD，當LO＞TLOD則FOD(LO)為0；否則，計算TLOD時刻的CDOD，根據(jù)式（2）計算得到FOD(LO)；

步驟4根據(jù)式（4）計算得到ALG.

步驟2中，對OD的最晚可達時間的求解是關鍵步驟，在后續(xù)展開說明，步驟3中對動態(tài)最優(yōu)可達路徑的計算，可以參考時刻表約束下的分支定界方法[6,7]求解.

3.3 OD的最晚可達時間計算方法

已有的OD最晚可達時間計算方法[3，4]是在備選路徑的停站列表已知情況下匹配時刻表得到結果.但當備選路徑不能覆蓋所有物理聯(lián)通路徑時，可能使結果出現(xiàn)偏差.

為了更加高效并準確地求解OD間最晚可達時間，本文在列車運行計劃和網絡拓撲共同約束下，以節(jié)點與線路關系集合為基礎，采用遞歸的方法快速求解準確的OD最晚可達時間.

節(jié)點與線路關系集合包括后繼線路集合和后繼節(jié)點集合.定義在O點可以搭乘列車出發(fā)的線路為后繼線路，后繼線路集合為LS(O)，集合中的元素表示為Li，其中i為線路編號；定義從O點出發(fā)沿后繼線路可以到達的第一個節(jié)點為后繼節(jié)點，用N(O)i表示O點在線路Li上的后繼節(jié)點，后繼節(jié)點集合為NS(O).

定義TLOD(i)為O在后繼方向i上的最晚可達時間，即從Li線路出發(fā)的最晚可達時間，則可用式（5）來表達OD最晚可達時間與后繼方向最晚可達時間的關系，其中OD間的最晚可達時間是從O沿各后繼線路出發(fā)到達D的最晚可達時間的最大值.

式中 CLOO'(i,j)表示從O點沿線路i到達線路 j上的O'點的消耗成本，O'是O在線路i上的后繼節(jié)點；TLO'D(j)表示O'在方向 j上的最晚可達時間；LTO(i)表示O點沿路徑i開往D的末班車在O點的發(fā)車時刻.

D不是O的后繼節(jié)點時，TLOD(i)為O'在各方向的最晚可達時間與O到O'的成本差值中取極大值；當D為O的后繼節(jié)點時，TLOD(i)為O點在方向i上的末班車發(fā)車時刻.

式中 TROO'(i)表示線路i上O到O'的運行時分；TTRO'(i,j)為在車站O'從線路i換乘到線路 j的走行時間；TWO'(i,j)表示在車站O'的等待時間.

當i和 j不相等時，TWOO'(i,j)表示換乘線路帶來的候車時間；當i和 j相等時，TWOO'(i,j)表示列車在車站O'的停站時間或終到O'時換乘列車帶來的候車時間.TWOO'(i,j)的求解如式（8）所示.

更進一步，對路網中所有OD間的最晚可達時間求解可利用遞歸求解過程中產生的中間結果TLO'D，減少重復計算.

4 可達性計算在末班車銜接優(yōu)化中的應用

4.1 應用流程

根據(jù)3.1中的計算流程，在路網物理結構和OD間客流已定的情況下，輸入不同的運行計劃將得到不同的可達性結果，據(jù)此可以使用路網可達性對運行計劃進行評價.而末班車銜接方案在運行計劃制定中具有重要作用[5,9]，現(xiàn)有的末班車銜接優(yōu)化從主觀判斷[9]或從換乘客流量出發(fā)進行優(yōu)化[5].

在此，結合前述的可達性計算方法，使用路網可達性最大為目標進行末班車銜接方案優(yōu)化，其應用流程如圖2所示.其中，運行計劃制定的其他條件包括：線路末班運營時限、區(qū)間運行時分、停站時分等，路網物理結構包括車站、線路關系及換乘時間等.

圖2 可達性應用流程Fig.2 Flow of applying accessibility

4.2 算例分析

仍以圖1為背景，假設路網末班車運營時限為23:00，區(qū)間運行時間均為5 min，換乘時間均為2 min，停站時間均為30 s，末班車開行時OD間客流量為

根據(jù)OD間的客流量可以得到四個換乘方向

L11-S1-L21、L21-S2-L11、L22-S1-L12和 L12-S2-L22的客流量分別為：500，200，300和400.根據(jù)文獻[5]（方法1）和本文中提出的方法（方法2）分別計算末班車換乘銜接方案，其中路網可達性計算參數(shù)α取1，以旅行時間來衡量路徑成本，兩個方法計算得到的最優(yōu)末班車銜接方案和末班車開行下的路網可達性數(shù)值對比如表1所示.兩種不同的方法求解得出不同的銜接方案和路網可達性數(shù)值.當以路網可達性為衡量指標時，方法2優(yōu)于方法1.

表1 銜接優(yōu)化方案對比表Table 1 Com parison of connection schemes

5 研究結論

本文分析了末班車開行引起的城市軌道交通路網動態(tài)可達性特征，給出了路徑可達性、OD可達性的內涵說明及最晚可達時間的定義；提出了適用于路網服務能力評價的路網可達性計算公式，和末班車開行下的路網可達性計算方法，并將之應用于末班車銜接優(yōu)化方法，通過算例分析，本文提出的方法有利于求出更優(yōu)的末班車銜接優(yōu)化方案，提高路網服務能力.

[1]Lawrence D Burns,Thomas F Golob.The role of accessibility in basic transportation choice behavior[J]. Transportation,1976,5(2):175-198.

[2]王偉,劉軍,李海鷹,等.鐵路網抗毀性分析[J].鐵道學報,2010,32(4):18-22.[WANG W,LIU J,LI H Y,et al. Survivability analysis of railway network[J].Journal of the China Railway Society,2010,32(4):18-22.]

[3]羅欽,徐瑞華,江志彬,等.基于運行圖的軌道交通網絡動態(tài)可達性研究[J].同濟大學學報(自然科學版), 2010,38(1):72-75.[LUO Q,XU R H,JIANG Z B,et al. Dynamic accessibility of urban mass transit network based on train diagram[J].Journal of Tongji University (Natural Science),2010,38(1):72-75.]

[4]江志彬,徐瑞華,羅欽.基于時間窗約束的城市軌道交通網絡動態(tài)可達性計算方法[P]:中國,CN 102169512A.2011-08-31.[JIANG Z B,XU R H, LUO Q.Computing dynamic accessibility of urban mass transit network based on time-window[P]:China,CN 102169512A.2011-08-31.]

[5]徐瑞華，李璇.城市軌道交通網絡末班車銜接方案的綜合優(yōu)化[J].同濟大學學報(自然科學版),2012,40 (10):1510-1516.[XU R H,LI X.Comprehensive optimization for connection scheme of last trains in urban mass transit network[J].Journal of Tongji University(Natural Science),2012,40(10):1510-1516.]

[6]Tong C O,Richardson A J.A computer model for finding the time-dependent minimum path in a transit system with fixed schedules[J].Journal of Advanced Transportation,1984,18,145-161.

[7]M H Poon,S C Wong,C O Tong.A dynamic schedulebased model for congested transit networks[J]. Transportation Research Part B,2004(38)343-368.

[8]Rachel C W Wong，Tony W Y Yuen，Kwok Wah Fung，et al.Leung,Optimizing timetable synchronization for rail mass transit[J].Transportation Science,2008,42(1): 57-69.

[9]徐瑞華，張銘，江志彬.基于線網運營協(xié)調的城市軌道交通首末班列車發(fā)車時問域研究[J].鐵道學報, 2008,30(2):7-11.[XU R H,ZHANG M,JIANG Z B. Study on departure time domain of the first and last trains of urban mass transit network based on operation coordination[J].Journal of the China Railway Society, 2008,30(2):7-11.]

Analyzing and Computing Dynamic Accessibility with Constraints of Schedule

GUO Jian-yuana,JIALi-minb,QIN Yongb
(a.School of Traffic and Transportation;b.State Key Laboratory of Rail Traffic Control and Safety, Beijing Jiaotong University,Beijing 100044,China)

When time close to the running of last trains,the number of active routes in urban rail transit will become less and less.The network accessibility changing along with the time is called dynamic accessibility. The method about computing dynamic accessibility is studied,which fits to the planning of last trains and improves the service quantity to passengers who want to take very late or even last trains to their destinations.These definitions are given,such as latest accessible time,route accessibility and OD accessibility.Then,the main steps to compute network accessibility with last trains running is presented,and a recursive algorithm is used to compute the latest accessible time.At last,a flow of applying network accessibility is proposed to optimize the connection scheme of last trains.The example is given to demonstrate the feasibility of the method.

urban traffic;accessibility;connection scheme;urban rail transit;last train

1009-6744（2015）01-0118-05

：U239.5

：A

2014-09-03

：2014-10-16錄用日期：2014-11-13

國家“十二五”科技支撐計劃課題(2011BAG01B02).

郭建媛(1979-)，女，河南人，講師，碩士. ＊

：jialm@vip.sina.com