郭建媛，賈利民，秦 勇

（北京交通大學(xué)a.交通運(yùn)輸學(xué)院；b.軌道交通控制與安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京100044）

運(yùn)行計(jì)劃約束下的動(dòng)態(tài)可達(dá)性分析與計(jì)算

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

（北京交通大學(xué)a.交通運(yùn)輸學(xué)院；b.軌道交通控制與安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京100044）

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

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

1 引 言

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

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

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

本文在已有研究的基礎(chǔ)上，進(jìn)一步分析動(dòng)態(tài)可達(dá)性內(nèi)涵特征，以提高路網(wǎng)服務(wù)能力為目標(biāo)，給出適用于末班車開(kāi)行優(yōu)化的可達(dá)性定義與計(jì)算方法.

2 可達(dá)性分析

2.1 可達(dá)性相關(guān)定義

OD間的載客服務(wù)隨時(shí)間的動(dòng)態(tài)變化反映了運(yùn)行計(jì)劃影響路徑可達(dá)和OD可達(dá)的過(guò)程.在已有可達(dá)性定義的基礎(chǔ)上，本文結(jié)合站點(diǎn)間服務(wù)能力隨運(yùn)行計(jì)劃的變化特點(diǎn)，做出了更進(jìn)一步的擴(kuò)充，包括路徑可達(dá)性，OD可達(dá)性.

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

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

OD可達(dá)性指能否從O通過(guò)路網(wǎng)到達(dá)D，及其可達(dá)的便捷程度.使用FOD表示OD間可達(dá)性，當(dāng)FOD=0時(shí)表示OD不可達(dá)，當(dāng)FOD＞0時(shí)表示OD可達(dá)，其計(jì)算如式（2）所示.

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

2.2 末班車對(duì)可達(dá)性的影響

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

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

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

當(dāng)搭乘末班車在換乘方向L11-S1-L21上可以銜接時(shí)，則搭乘末班車在換乘方向L21-S2-L11無(wú)法銜接；當(dāng)搭乘末班車在換乘方向L22-S1-L12上可以銜接時(shí)，則搭乘末班車在換乘方向L12-S2-L22無(wú)法銜接.因此，末班車開(kāi)行會(huì)帶來(lái)?yè)Q乘銜接間的互相約束，進(jìn)一步在不同路徑的可達(dá)性之間產(chǎn)生相互約束.

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

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

3 末班車開(kāi)行下的路網(wǎng)可達(dá)性計(jì)算方法

3.1 路網(wǎng)可達(dá)性計(jì)算方法

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

式中 G表示路網(wǎng)站點(diǎn)集合；fOD表示從O去往D的客流量.

可以用末班車開(kāi)行下的路網(wǎng)可達(dá)性ALG來(lái)衡量末班車銜接效果，計(jì)算用式（4）表示.

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

3.2 末班車開(kāi)行下的路網(wǎng)可達(dá)性計(jì)算流程

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

步驟1 加載路網(wǎng)物理結(jié)構(gòu)GS、運(yùn)行計(jì)劃TG和OD間的客流量 fOD；

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

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

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

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

3.3 OD的最晚可達(dá)時(shí)間計(jì)算方法

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

為了更加高效并準(zhǔn)確地求解OD間最晚可達(dá)時(shí)間，本文在列車運(yùn)行計(jì)劃和網(wǎng)絡(luò)拓?fù)涔餐s束下，以節(jié)點(diǎn)與線路關(guān)系集合為基礎(chǔ)，采用遞歸的方法快速求解準(zhǔn)確的OD最晚可達(dá)時(shí)間.

節(jié)點(diǎn)與線路關(guān)系集合包括后繼線路集合和后繼節(jié)點(diǎn)集合.定義在O點(diǎn)可以搭乘列車出發(fā)的線路為后繼線路，后繼線路集合為L(zhǎng)S(O)，集合中的元素表示為L(zhǎng)i，其中i為線路編號(hào)；定義從O點(diǎn)出發(fā)沿后繼線路可以到達(dá)的第一個(gè)節(jié)點(diǎn)為后繼節(jié)點(diǎn)，用N(O)i表示O點(diǎn)在線路Li上的后繼節(jié)點(diǎn)，后繼節(jié)點(diǎn)集合為NS(O).

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

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

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

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

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

更進(jìn)一步，對(duì)路網(wǎng)中所有OD間的最晚可達(dá)時(shí)間求解可利用遞歸求解過(guò)程中產(chǎn)生的中間結(jié)果TLO'D，減少重復(fù)計(jì)算.

4 可達(dá)性計(jì)算在末班車銜接優(yōu)化中的應(yīng)用

4.1 應(yīng)用流程

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

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

圖2 可達(dá)性應(yīng)用流程Fig.2 Flow of applying accessibility

4.2 算例分析

仍以圖1為背景，假設(shè)路網(wǎng)末班車運(yùn)營(yíng)時(shí)限為23:00，區(qū)間運(yùn)行時(shí)間均為5 min，換乘時(shí)間均為2 min，停站時(shí)間均為30 s，末班車開(kāi)行時(shí)OD間客流量為

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

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

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

5 研究結(jié)論

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

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

[2]王偉,劉軍,李海鷹,等.鐵路網(wǎng)抗毀性分析[J].鐵道學(xué)報(bào),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]羅欽,徐瑞華,江志彬,等.基于運(yùn)行圖的軌道交通網(wǎng)絡(luò)動(dòng)態(tài)可達(dá)性研究[J].同濟(jì)大學(xué)學(xué)報(bào)(自然科學(xué)版), 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]江志彬,徐瑞華,羅欽.基于時(shí)間窗約束的城市軌道交通網(wǎng)絡(luò)動(dòng)態(tài)可達(dá)性計(jì)算方法[P]:中國(guó),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]徐瑞華，李璇.城市軌道交通網(wǎng)絡(luò)末班車銜接方案的綜合優(yōu)化[J].同濟(jì)大學(xué)學(xué)報(bào)(自然科學(xué)版),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]徐瑞華，張銘，江志彬.基于線網(wǎng)運(yùn)營(yíng)協(xié)調(diào)的城市軌道交通首末班列車發(fā)車時(shí)問(wèn)域研究[J].鐵道學(xué)報(bào), 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

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

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

：jialm@vip.sina.com