徐文愷，趙 鵬，寧麗巧，張 輝

(1.北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044；2.山東建筑大學(xué) 交通工程學(xué)院，山東 濟(jì)南 250101)

城市軌道交通網(wǎng)絡(luò)末班車時(shí)刻表調(diào)整是指網(wǎng)絡(luò)中某線路末班車發(fā)生延誤時(shí)，通過調(diào)整末班車在換乘站的到發(fā)時(shí)刻，協(xié)調(diào)不同線路末班車在換乘站的銜接關(guān)系，實(shí)現(xiàn)一定目標(biāo)下的系統(tǒng)最優(yōu)。末班車間的銜接關(guān)系決定著城市軌道交通網(wǎng)絡(luò)在運(yùn)營結(jié)束階段的換乘可達(dá)性[1]，在末班車運(yùn)行延誤的條件下，網(wǎng)絡(luò)換乘可達(dá)性的變化會(huì)導(dǎo)致?lián)Q乘乘客錯(cuò)失計(jì)劃換乘，從而無法經(jīng)由城市軌道交通網(wǎng)絡(luò)完成出行。因此，當(dāng)末班車運(yùn)行發(fā)生延誤時(shí)，有必要結(jié)合乘客需求和運(yùn)營管理要求，及時(shí)調(diào)整網(wǎng)絡(luò)末班車時(shí)刻表，盡可能保證乘客的正常出行。隨著乘客對(duì)城市軌道交通系統(tǒng)服務(wù)水平要求的提高，該問題具有重要的研究?jī)r(jià)值和現(xiàn)實(shí)意義。

目前，國內(nèi)外學(xué)者主要從末班車換乘銜接的角度研究網(wǎng)絡(luò)末班車時(shí)刻表問題，期望得到一個(gè)更優(yōu)的網(wǎng)絡(luò)末班車計(jì)劃時(shí)刻表，但針對(duì)網(wǎng)絡(luò)末班車時(shí)刻表調(diào)整問題的研究較少。文獻(xiàn)[2]根據(jù)網(wǎng)絡(luò)中各線路和換乘站的重要度系數(shù)確定網(wǎng)絡(luò)的主協(xié)調(diào)線路和換乘站，以乘客在換乘站的總候車時(shí)間最小化為目標(biāo)，根據(jù)重要度從大到小依次求出各線路末班車在各換乘站的到發(fā)時(shí)刻。文獻(xiàn)[3]通過選取主導(dǎo)銜接關(guān)系和主協(xié)調(diào)換乘站，以成功實(shí)現(xiàn)換乘的末班車乘客數(shù)量最大化為目標(biāo)構(gòu)建網(wǎng)絡(luò)末班車銜接方案優(yōu)化模型，并將問題轉(zhuǎn)化為最大生成樹問題，借鑒Kruskal算法推算出協(xié)同優(yōu)化的網(wǎng)絡(luò)末班車時(shí)刻表。文獻(xiàn)[4]結(jié)合路徑選擇模型，以乘客換乘等待時(shí)間最小化和換乘失敗乘客數(shù)量最小化為目標(biāo)，設(shè)計(jì)一種遺傳算法求解出各線路末班車在始發(fā)站的發(fā)車時(shí)刻。文獻(xiàn)[5-6]通過選取網(wǎng)絡(luò)的關(guān)鍵換乘方向，以乘客換乘等待時(shí)間最小化和成功換乘銜接關(guān)系數(shù)量最大化為目標(biāo)構(gòu)建網(wǎng)絡(luò)末班車協(xié)同優(yōu)化模型。文獻(xiàn)[7]設(shè)計(jì)一種啟發(fā)式算法優(yōu)化網(wǎng)絡(luò)末班車時(shí)刻表，案例分析表明該算法明顯優(yōu)于模擬退火算法和遺傳算法。文獻(xiàn)[8]建立以乘客總體換乘不滿意度最小、換乘成功的乘客數(shù)量最多和各線路方向末班車結(jié)束運(yùn)營時(shí)間最早為目標(biāo)的確定環(huán)境下的末班車時(shí)刻表銜接優(yōu)化模型，設(shè)計(jì)NSGA-II算法求解。文獻(xiàn)[9]從網(wǎng)絡(luò)末班車時(shí)段出發(fā)，構(gòu)建以總乘客換乘等待時(shí)間最小化為目標(biāo)的末班車時(shí)段時(shí)刻表協(xié)同優(yōu)化模型。

總之，目前絕大多數(shù)關(guān)于網(wǎng)絡(luò)末班車問題的研究集中于網(wǎng)絡(luò)末班車計(jì)劃時(shí)刻表的編制優(yōu)化，很少涉及網(wǎng)絡(luò)末班車運(yùn)營過程中遭遇突發(fā)事件延誤后的時(shí)刻表調(diào)整問題。但無論是網(wǎng)絡(luò)末班車時(shí)刻表協(xié)調(diào)優(yōu)化問題還是網(wǎng)絡(luò)末班車時(shí)刻表調(diào)整問題，換乘乘客都是研究的重點(diǎn)。本文從乘客的角度出發(fā)，以實(shí)現(xiàn)換乘的乘客數(shù)量最大化為目標(biāo)；從運(yùn)營的角度出發(fā)，以調(diào)整時(shí)刻表與計(jì)劃時(shí)刻表的偏離程度最小化為目標(biāo)構(gòu)建網(wǎng)絡(luò)末班車時(shí)刻表調(diào)整模型。通過ε-constraint法[10-11]，將模型轉(zhuǎn)化為單目標(biāo)混合整數(shù)規(guī)劃模型，并通過不斷調(diào)整ε取值，求出相應(yīng)的近似Pareto最優(yōu)解，即網(wǎng)絡(luò)末班車的時(shí)刻表調(diào)整方案。

1 網(wǎng)絡(luò)末班車時(shí)刻表調(diào)整模型

在實(shí)際運(yùn)輸生產(chǎn)過程中，當(dāng)發(fā)生列車運(yùn)行延誤時(shí)，調(diào)度管理人員往往采用趕點(diǎn)、跨站停車、扣車、小交路等措施使列車盡快恢復(fù)正點(diǎn)運(yùn)行，而較少考慮對(duì)乘客的影響[12-14]。此外，既有研究中的末班車時(shí)刻表模型大多是基于預(yù)先確定的主協(xié)調(diào)線路或關(guān)鍵換乘方向。本文所構(gòu)建的模型結(jié)合網(wǎng)絡(luò)末班車間換乘客流分布，不選擇主協(xié)調(diào)線路或關(guān)鍵換乘方向，從乘客以及全局優(yōu)化的角度，協(xié)調(diào)延誤條件下各線路末班車間的銜接關(guān)系。

1.1 符號(hào)和變量

模型的符號(hào)和參數(shù)定義如下：

模型的決策變量定義如下：

1.2 末班車銜接關(guān)系

根據(jù)各線路末班車在換乘站的實(shí)際到發(fā)時(shí)刻，每一個(gè)銜接關(guān)系c存在以下兩種情景：

圖1 換乘銜接成功

圖2 換乘銜接失敗

( 1 )

( 2 )

( 3 )

1.3 優(yōu)化模型

針對(duì)網(wǎng)絡(luò)末班車問題，網(wǎng)絡(luò)換乘可達(dá)性對(duì)乘客出行有著十分重要的影響。本模型從乘客和運(yùn)營兩個(gè)角度出發(fā)，建立目標(biāo)函數(shù)。

( 4 )

( 5 )

式( 4 )從乘客的角度出發(fā)，以換乘成功乘客數(shù)量最大化為優(yōu)化目標(biāo)。從運(yùn)營的角度出發(fā)，當(dāng)發(fā)生列車運(yùn)行延誤時(shí)，調(diào)度管理人員須盡快使列車運(yùn)行恢復(fù)至計(jì)劃時(shí)刻表，因此，式( 5 )表示調(diào)整時(shí)刻表與計(jì)劃時(shí)刻表的偏離程度最小化。該目標(biāo)也有利于降低調(diào)整時(shí)刻表對(duì)非換乘乘客的影響。

模型約束如下：

s.t.

( 6 )

( 7 )

( 8 )

( 9 )

(10)

(11)

(12)

(13)

(14)

式( 6 )、式( 7 )為安全性約束，各線路末班車在區(qū)間的運(yùn)行時(shí)間不得小于最短運(yùn)行時(shí)間，在車站的停站時(shí)間不得小于最短停站時(shí)間[15]。式( 8 )為靈活性約束，對(duì)于發(fā)生列車延誤事件后還未從始發(fā)站發(fā)出的末班車，允許調(diào)整其在始發(fā)站的實(shí)際發(fā)車時(shí)刻。式( 9 )、式(10)即式( 2 )、式( 3 )，用于判斷各線路末班車在換乘站的銜接關(guān)系是否成立。式(11)為初始延誤約束，用于輸入列車的延誤時(shí)間及位置。式(12)～式(14)為實(shí)際問題決策變量約束。

2 模型求解

本文所構(gòu)建的雙目標(biāo)優(yōu)化模型旨在最大化換乘成功乘客數(shù)量的同時(shí)最小化調(diào)整時(shí)刻表與計(jì)劃時(shí)刻表的偏離程度，期望得到一組近似Pareto最優(yōu)解以體現(xiàn)兩個(gè)目標(biāo)函數(shù)之間的均衡，可以直觀地作用于調(diào)度管理人員的決策過程。多目標(biāo)優(yōu)化模型求解時(shí)需要轉(zhuǎn)換為單目標(biāo)模型，而常用的權(quán)重系數(shù)法存在權(quán)重系數(shù)難以確定的問題。因此，本文采用ε-constraint法求解近似Pareto最優(yōu)解。

選取目標(biāo)函數(shù)式( 5 )作為ε-constraint，將式( 5 )轉(zhuǎn)換為式(15)。

(15)

式中：F*為僅考慮目標(biāo)函數(shù)式( 5 )的條件下模型求得的最優(yōu)值；ε為調(diào)度管理人員對(duì)調(diào)整時(shí)刻表與計(jì)劃時(shí)刻表偏離程度的容忍度，0≤ε≤εmax，εmax為調(diào)度管理人員對(duì)偏離程度的最大容忍度。

采用ε-constraint法，將本文所構(gòu)建模型轉(zhuǎn)換為以換乘成功乘客數(shù)量最大化為目標(biāo)的單目標(biāo)混合整數(shù)線性規(guī)劃模型(MILP)，通過改變?chǔ)诺娜≈担褂肅plex軟件編程求解出相應(yīng)的近似Pareto最優(yōu)解。模型的求解過程如圖3所示。

圖3 模型求解

3 案例分析

本文以北京地鐵網(wǎng)絡(luò)為研究對(duì)象，驗(yàn)證模型的有效性。截至2017年6月底，除機(jī)場(chǎng)線外，北京地鐵網(wǎng)絡(luò)共包含18條雙線線路，53座換乘站，路網(wǎng)結(jié)構(gòu)如圖4所示。由于客流特征等因素的不同，不同的線路有不同的運(yùn)營時(shí)間范圍，各線路的末班車計(jì)劃時(shí)刻表詳見北京地鐵官方網(wǎng)站。

圖4 北京地鐵路網(wǎng)(不包括機(jī)場(chǎng)線)

換乘客流量是決定一個(gè)末班車銜接關(guān)系是否要滿足的關(guān)鍵因素。但清分后的地鐵自動(dòng)售檢票(AFC)數(shù)據(jù)只能給出一段時(shí)間內(nèi)每一個(gè)換乘方向的換乘客流量，無法準(zhǔn)確得到來自某列車的換乘客流量。因此，在現(xiàn)有的技術(shù)條件下我們無法準(zhǔn)確獲得來自末班車的換乘客流量。本文以各線路最后30 min的AFC數(shù)據(jù)為基礎(chǔ)生成在各個(gè)換乘站從末班車下車去往其他線路的換乘客流量。由于本文所提出的模型并不需要提前選取實(shí)際路網(wǎng)中的主協(xié)調(diào)線路或關(guān)鍵換乘方向，所以基于AFC數(shù)據(jù)生成的換乘客流數(shù)據(jù)雖然與實(shí)際不符，但并不影響驗(yàn)證模型的有效性。

3.1 隨機(jī)延誤情景分析

為驗(yàn)證模型的有效性，本文隨機(jī)生成若干延誤情景，每個(gè)延誤情景隨機(jī)選擇北京地鐵網(wǎng)絡(luò)中的某條線路，假設(shè)該線路的末班車發(fā)生延誤，延誤時(shí)間設(shè)置為3～10 min。具體延誤情景見表1。

表1 延誤情景

通過在3.1 GHz CPU, 8 GB RAM臺(tái)式電腦上使用Cplex軟件編程求解每一個(gè)末班車延誤問題，所有問題均在2 s內(nèi)求得最優(yōu)解，可以滿足實(shí)際運(yùn)輸生產(chǎn)過程中實(shí)時(shí)性的要求。為驗(yàn)證模型的有效性，設(shè)置對(duì)比方案，各方案詳細(xì)求解結(jié)果見表2，括號(hào)中的百分比代表相對(duì)于方案A的提高比例。

方案A：列車運(yùn)行延誤后不進(jìn)行任何調(diào)整，仍然按照計(jì)劃時(shí)刻表中的區(qū)間運(yùn)行時(shí)間和停站時(shí)間運(yùn)行。

表2 求解結(jié)果

求解結(jié)果表明，在任意延誤情景下，方案B都不比無調(diào)整的方案A差，而方案C都要優(yōu)于方案A。這也說明在末班車延誤的條件下，調(diào)度管理人員一定要及時(shí)響應(yīng)，科學(xué)調(diào)整末班車時(shí)刻表，保證系統(tǒng)的服務(wù)水平。相對(duì)于方案B，方案C的優(yōu)化效果更加明顯：在換乘成功乘客數(shù)量上，方案C與方案A相比有1.95%～7.61%的增長(zhǎng)，而方案B最高也僅有2.06%的提高。方案C可以明顯提高末班車延誤后系統(tǒng)的服務(wù)水平，更好地保證乘坐末班車換乘乘客的正常出行。求解結(jié)果證明了本文所提出方法的準(zhǔn)確性和有效性。

3.2 近似Pareto最優(yōu)

Pareto最優(yōu)是指資源有限的條件下一種理想的資源分配狀態(tài)，當(dāng)多目標(biāo)模型中某個(gè)目標(biāo)函數(shù)的函數(shù)值變優(yōu)時(shí)必然會(huì)導(dǎo)致其他目標(biāo)函數(shù)的函數(shù)值變差，此時(shí)對(duì)應(yīng)的解即Pareto最優(yōu)解，Pareto最優(yōu)解也是資源利用效率最高的解。在給定路網(wǎng)及延誤情景的條件下，調(diào)度管理人員對(duì)調(diào)整時(shí)刻表與計(jì)劃時(shí)刻表偏離程度的容忍度越高，調(diào)整時(shí)刻表與計(jì)劃時(shí)刻表的偏離程度越大，相反，各線路末班車在換乘站實(shí)現(xiàn)換乘銜接的可能性越大。本文以延誤情景1為例，通過改變?chǔ)诺娜≈?εmax=0.5，Δε=0.05)，求出相應(yīng)的近似Pareto最優(yōu)解，見表3。繪制換乘成功乘客數(shù)量與偏離程度散點(diǎn)圖，如圖5所示。可以發(fā)現(xiàn)一個(gè)明顯的趨勢(shì)：隨著偏離程度的增加，換乘成功乘客數(shù)量明顯提高。而每一個(gè)近似Pareto最優(yōu)解代表一個(gè)時(shí)刻表調(diào)整方案，調(diào)度管理人員在實(shí)際運(yùn)輸生產(chǎn)過程中要權(quán)衡各方案的優(yōu)劣，并選擇一個(gè)最有利的方案。

表3 近似Pareto最優(yōu)解(情景1)

圖5 換乘成功乘客數(shù)量與偏離程度散點(diǎn)圖

為輔助調(diào)度管理人員決策，本文引入?yún)?shù)總運(yùn)行時(shí)間tTotal，是指所有線路末班車從始發(fā)站到終點(diǎn)站的運(yùn)行時(shí)間之和。

(16)

根據(jù)式(16)計(jì)算無調(diào)整方案A的總運(yùn)行時(shí)間為99 900 s，計(jì)算各近似Pareto最優(yōu)解的總運(yùn)行時(shí)間見表3。以高偏離容忍度(ε=0.5)求出的時(shí)刻表調(diào)整方案，換乘成功乘客數(shù)量比方案A增加515 (+6.03%)人，而總運(yùn)行時(shí)間僅增加1 227 s?？紤]到北京地鐵包括18條雙線線路、36列末班車，平均每列末班車運(yùn)行時(shí)間僅增加34 s，幾乎可以忽略不計(jì)。這也說明調(diào)整時(shí)刻表對(duì)非換乘乘客的影響較小。在其他延誤情景下，也得到了相似的結(jié)果。因此，當(dāng)網(wǎng)絡(luò)中發(fā)生末班車運(yùn)行延誤時(shí)，調(diào)度管理人員應(yīng)該更多的從乘客的角度出發(fā)，選擇換乘成功乘客數(shù)量更多的時(shí)刻表調(diào)整方案。

4 結(jié)論

在網(wǎng)絡(luò)化運(yùn)營條件下，換乘銜接質(zhì)量是衡量城市軌道交通服務(wù)水平的重要指標(biāo)。而針對(duì)末班車銜接優(yōu)化問題，末班車銜接合理與否直接關(guān)系到網(wǎng)絡(luò)換乘可達(dá)性的高低。一旦換乘乘客錯(cuò)過其銜接線路的末班車，則意味著該乘客無法通過軌道交通系統(tǒng)完成出行，將嚴(yán)重降低系統(tǒng)的服務(wù)水平。

本文針對(duì)城市軌道交通網(wǎng)絡(luò)末班車延誤問題，以換乘成功乘客數(shù)量最大化和調(diào)整時(shí)刻表與計(jì)劃時(shí)刻表偏離程度最小化為目標(biāo)構(gòu)建了末班車時(shí)刻表調(diào)整模型，并采用ε-constraint法將模型轉(zhuǎn)換為單目標(biāo)混合整數(shù)線性規(guī)劃模型，使用Cplex軟件可快速求出最優(yōu)解。在以北京地鐵網(wǎng)絡(luò)為研究對(duì)象的案例分析中，隨機(jī)生成末班車延誤情景，使用模型求解出的調(diào)整時(shí)刻表能夠使換乘成功乘客數(shù)量增加1.95%～7.61%。在給定延誤情景的條件下，改變?chǔ)湃≈?，可使用模型求得相?yīng)的近似Pareto最優(yōu)解，為調(diào)度管理人員提供決策支持。

案例分析結(jié)果表明，隨著調(diào)整時(shí)刻表與計(jì)劃時(shí)刻表偏離程度的增加，換乘成功乘客數(shù)量明顯增加，而末班車的運(yùn)行時(shí)間沒有明顯變化：ε=0.5時(shí)，換乘成功乘客數(shù)量增加了6.03%，而平均每列末班車的運(yùn)行時(shí)間僅增加了34 s，對(duì)非換乘乘客影響較小。因此，隨著乘客對(duì)軌道交通系統(tǒng)服務(wù)水平要求的日益提高，當(dāng)網(wǎng)絡(luò)中發(fā)生末班車延誤時(shí)，調(diào)度管理人員應(yīng)該在整合分析歷史客流數(shù)據(jù)、末班車延誤數(shù)據(jù)的基礎(chǔ)上，合理確定ε取值，選擇更有利于乘客的末班車時(shí)刻表調(diào)整方案。