城軌過(guò)渡時(shí)段列車(chē)運(yùn)行圖調(diào)整方法

吳學(xué)良，王偉，彭浩，王志凱，謝輝，曹馳

（1.北京市地鐵運(yùn)營(yíng)有限公司，北京 100044；2.交控科技股份有限公司，北京 100070；3.北京交通大學(xué) 電子信息工程學(xué)院，北京 100044）

0 引言

為滿(mǎn)足市民日益增長(zhǎng)的出行需求，緩解交通矛盾，城市軌道交通得到了快速發(fā)展。與其他交通方式相比，城市軌道交通具有安全可靠、速度快、密度大及乘車(chē)環(huán)境舒適等特點(diǎn)，目前已經(jīng)成為市民選擇出行的主要交通方式之一。

在實(shí)際運(yùn)營(yíng)過(guò)程中，城軌運(yùn)營(yíng)公司一般會(huì)根據(jù)客流需求并結(jié)合運(yùn)營(yíng)成本提前做好行車(chē)組織工作并編制列車(chē)運(yùn)行圖，確保列車(chē)安全有序地開(kāi)行。但城軌是一個(gè)復(fù)雜巨系統(tǒng)，在運(yùn)營(yíng)的過(guò)程中難免會(huì)出現(xiàn)如車(chē)門(mén)故障、線(xiàn)路阻塞等復(fù)雜因素的干擾。運(yùn)營(yíng)干擾通常會(huì)導(dǎo)致某個(gè)或者多個(gè)列車(chē)產(chǎn)生延誤，導(dǎo)致原計(jì)劃不可行。為減小延誤對(duì)運(yùn)營(yíng)和乘客造成的負(fù)面影響，需要對(duì)列車(chē)運(yùn)行圖進(jìn)行調(diào)整［1］。

目前，城軌調(diào)度員調(diào)整運(yùn)行圖的目標(biāo)是從運(yùn)營(yíng)公司的角度考慮，使線(xiàn)路上的列車(chē)盡快按照計(jì)劃運(yùn)行圖運(yùn)行，同時(shí)減少列車(chē)延誤，提高運(yùn)行圖兌現(xiàn)率，但這種調(diào)整目標(biāo)存在一定的缺陷。由于城軌客流分布具有顯著的時(shí)間不均衡特性，城軌運(yùn)營(yíng)公司為了節(jié)約運(yùn)營(yíng)成本通常根據(jù)客流量的大小將全天的運(yùn)營(yíng)時(shí)段劃分為高峰和平峰時(shí)段。高峰時(shí)段線(xiàn)上運(yùn)行的列車(chē)多，發(fā)車(chē)間隔小，運(yùn)力充足。相反地，平峰時(shí)段運(yùn)行的列車(chē)少，發(fā)車(chē)間隔大，運(yùn)力較小。在高峰到平峰過(guò)渡階段若有列車(chē)發(fā)生延誤，則會(huì)導(dǎo)致高峰時(shí)段的乘客在站臺(tái)滯留。如果調(diào)度員繼續(xù)調(diào)整運(yùn)行圖使列車(chē)按照計(jì)劃運(yùn)行，會(huì)導(dǎo)致運(yùn)力不足，使原本滯留的乘客無(wú)法被服務(wù)，降低了乘客服務(wù)質(zhì)量。因此，調(diào)度員在運(yùn)行調(diào)整時(shí)應(yīng)當(dāng)綜合考慮運(yùn)營(yíng)公司指標(biāo)和乘客服務(wù)質(zhì)量，尋求二者的平衡關(guān)系。

以最小化站臺(tái)滯留乘客、取消車(chē)次數(shù)量和運(yùn)行圖偏移為優(yōu)化目標(biāo)構(gòu)建了優(yōu)化模型，該模型考慮加開(kāi)臨時(shí)客運(yùn)車(chē)次（簡(jiǎn)稱(chēng)加開(kāi)臨客）的調(diào)度策略。利用線(xiàn)性化手段將模型中的非線(xiàn)性約束線(xiàn)性化，進(jìn)而將模型轉(zhuǎn)化為混合整數(shù)規(guī)劃模型，最后利用CPLEX 求解器求解模型。通過(guò)仿真案例驗(yàn)證模型能夠在減少滯留乘客的同時(shí)盡快恢復(fù)正常的列車(chē)運(yùn)行秩序，模型的目標(biāo)最小化站臺(tái)滯留乘客數(shù)量能夠在一定程度上指導(dǎo)運(yùn)營(yíng)公司提高乘客服務(wù)質(zhì)量。

目前，關(guān)于城軌調(diào)度的研究按照目標(biāo)可以分為以下兩類(lèi)：（1）乘客服務(wù)質(zhì)量；（2）運(yùn)營(yíng)公司成本及服務(wù)質(zhì)量。與乘客服務(wù)相關(guān)的指標(biāo)包括：乘客等待時(shí)間、乘客旅行時(shí)間、車(chē)廂滿(mǎn)載率等。Barrena等［2］研究了鐵路列車(chē)晚點(diǎn)條件下的運(yùn)行圖調(diào)整問(wèn)題，構(gòu)建了2個(gè)非線(xiàn)性數(shù)學(xué)模型以最小化乘客在車(chē)站的等待時(shí)間，并提出一種近鄰搜索算法來(lái)提高求解速度。Gao 等［3］研究了城軌中斷恢復(fù)后的列車(chē)運(yùn)行調(diào)整問(wèn)題，以最小化滯留乘客數(shù)量為目標(biāo)構(gòu)建了混合整數(shù)規(guī)劃模型，并設(shè)計(jì)一種基于分解的迭代式啟發(fā)算法求解模型。

與運(yùn)營(yíng)公司成本及服務(wù)質(zhì)量相關(guān)的指標(biāo)包括：列車(chē)運(yùn)行能耗、列車(chē)延誤、取消車(chē)次數(shù)量等。D’Ariano等［4］提出利用比選圖和人工變量“大M”表示軌道交通網(wǎng)絡(luò)中列車(chē)運(yùn)行的閉塞區(qū)間占用過(guò)程，并設(shè)計(jì)了基于分支定界和啟發(fā)式分支規(guī)則的求解算法，該方法可以在較短的時(shí)間內(nèi)得到精確的最優(yōu)解或者近似最優(yōu)解。Lamorgese 等［5］提出了面向列車(chē)延誤最小化的基于jobshop 的鐵路列車(chē)時(shí)刻表調(diào)整模型。研究采用Benders［5］分解方法重新建模，改進(jìn)了傳統(tǒng)采用“大M”變量的job-shop 方式。Wang 等［6］考慮了可用車(chē)底數(shù)量約束，以時(shí)刻表偏差、取消車(chē)次數(shù)量、追蹤間隔變化為優(yōu)化目標(biāo)，建立了一個(gè)復(fù)雜的混合整數(shù)規(guī)劃模型，提出兩階段求解算法從而提高計(jì)算效率。

近年來(lái)也有一些學(xué)者將2 個(gè)目標(biāo)綜合考慮。Zhan等［7］利用時(shí)空網(wǎng)絡(luò)模型，建立了列車(chē)調(diào)度和乘客路徑優(yōu)化的綜合問(wèn)題。研究使用交替方向乘子算法（ADMM）將該模型分解為列車(chē)調(diào)度問(wèn)題和乘客路徑問(wèn)題2個(gè)子問(wèn)題，之后進(jìn)一步分解為一系列列車(chē)或乘客的最短路徑問(wèn)題，并用動(dòng)態(tài)規(guī)劃算法求解。Zhu 等［8］針對(duì)中斷場(chǎng)景提出了一種運(yùn)行圖調(diào)整模型，將靈活停站和靈活中途折返與其他調(diào)度措施結(jié)合，該模型的目標(biāo)是盡量減少乘客延誤。

1 列車(chē)運(yùn)行圖調(diào)整模型

1.1 問(wèn)題描述

研究案例為一條典型的單線(xiàn)雙向城市軌道交通運(yùn)營(yíng)線(xiàn)路，其線(xiàn)路拓?fù)浣Y(jié)構(gòu)示意見(jiàn)圖1。為了方便表述，將車(chē)站站臺(tái)簡(jiǎn)稱(chēng)為車(chē)站。線(xiàn)路中的終點(diǎn)車(chē)站提供折返線(xiàn)供上下行列車(chē)換端并改變運(yùn)行方向，同時(shí)實(shí)現(xiàn)上下行車(chē)次的車(chē)底銜接。線(xiàn)路中的車(chē)輛段中提供存車(chē)、檢修的場(chǎng)地，列車(chē)可以直接從車(chē)輛段出庫(kù)或返回車(chē)輛段存車(chē)。

圖1 城軌線(xiàn)路拓?fù)浣Y(jié)構(gòu)示意圖

為了方便建模，提出基本模型假設(shè)如下：

（1）假設(shè)所有列車(chē)都按照規(guī)定的次序運(yùn)行，運(yùn)行過(guò)程中不考慮越行或會(huì)讓的情況。在以往很多城軌運(yùn)行調(diào)整文章中都有類(lèi)似的假設(shè)［9-10］。

（2）為保證乘客服務(wù)質(zhì)量，假設(shè)所有列車(chē)經(jīng)過(guò)車(chē)站時(shí)都必須停車(chē)，即不考慮車(chē)站跳停的情況。

（3）研究未考慮到OD 客流，所以列車(chē)到達(dá)各個(gè)車(chē)站時(shí)的容量無(wú)法確定。為簡(jiǎn)化模型，認(rèn)為列車(chē)到達(dá)后，從車(chē)站乘坐該列車(chē)的乘客數(shù)量是有限的。

（4）由于城軌線(xiàn)路不同方向上存在不同的客流特性，因此假設(shè)開(kāi)行的臨客車(chē)次運(yùn)行至終點(diǎn)站后直接進(jìn)入車(chē)站存車(chē)線(xiàn)或車(chē)輛段，不再折返開(kāi)行其他車(chē)次。

1.2 符號(hào)定義

（1）集合及參數(shù)符號(hào)定義見(jiàn)表1。

表1 集合及參數(shù)符號(hào)定義

（2）決策變量定義見(jiàn)表2。

表2 決策變量定義

（3）中間變量定義見(jiàn)表3。

1.3 目標(biāo)函數(shù)

研究一種在高峰向平峰過(guò)渡時(shí)段列車(chē)發(fā)生延誤情況下的列車(chē)運(yùn)行調(diào)整方法，構(gòu)建了綜合考慮乘客服務(wù)質(zhì)量、列車(chē)延誤和取消車(chē)次數(shù)量的城軌列車(chē)運(yùn)行調(diào)整模型。

（1）車(chē)站滯留乘客數(shù)量。車(chē)站滯留乘客數(shù)量和加開(kāi)車(chē)次的滯留乘客數(shù)量為：

將所有車(chē)次在所有車(chē)站的滯留乘客數(shù)量求和：

（2）列車(chē)延誤。定義列車(chē)延誤為：

式中：|ai，des(i)-，des(i)|為車(chē)次i在其終點(diǎn)站的到達(dá)時(shí)間與計(jì)劃到達(dá)時(shí)間的差值絕對(duì)值；|di，ori(i)-，ori(i)|為車(chē)次i從始發(fā)站發(fā)車(chē)的時(shí)間與計(jì)劃發(fā)車(chē)時(shí)間的差值絕對(duì)值。

將所有計(jì)劃車(chē)次的延誤時(shí)間進(jìn)行求和，得到：

（3）取消車(chē)次。取消車(chē)次數(shù)量為：

定義目標(biāo)函數(shù)權(quán)重參數(shù)ωz，ωd，ωc分別表示滯留乘客數(shù)量、運(yùn)行圖偏移和取消車(chē)次數(shù)量的權(quán)重，研究構(gòu)建的模型目標(biāo)函數(shù)為：

在定義上述目標(biāo)時(shí)均引入了非線(xiàn)性表達(dá)式，以下將通過(guò)線(xiàn)性化手段將它們轉(zhuǎn)化為線(xiàn)性表達(dá)式。

1.4 約束構(gòu)建

（1）若車(chē)次i的服務(wù)在車(chē)站p被取消，那么令該車(chē)次在車(chē)站p的發(fā)車(chē)時(shí)間為0：

式中：M為一個(gè)充分大的正數(shù)；當(dāng)ci= 1，由于M充分大，上面的約束自然成立；當(dāng)ci= 0時(shí)，di，p= 0。

（2）為了保證正常的乘客乘降作業(yè)，列車(chē)在車(chē)站的停站時(shí)間必須大于最小值dmin：

（4）同方向的連續(xù)2個(gè)車(chē)次在同一車(chē)站的發(fā)車(chē)和到達(dá)時(shí)間必須大于最小值h′min：

（5）同方向的連續(xù)2個(gè)車(chē)次在車(chē)站的發(fā)車(chē)間隔必須大于一個(gè)最小值，用hmin來(lái)表示連續(xù)2 個(gè)車(chē)次的發(fā)車(chē)間隔約束：

（6）列車(chē)需要利用折返線(xiàn)來(lái)改變運(yùn)行方向，列車(chē)折返需要滿(mǎn)足一定的折返時(shí)間約束：

（7）一個(gè)車(chē)次折返后只能銜接一個(gè)反向的車(chē)次，每一個(gè)車(chē)次也只能由另一個(gè)反向的車(chē)次進(jìn)行銜接，約束表示為：

（8）若車(chē)次沒(méi)有車(chē)底執(zhí)行則會(huì)被取消服務(wù)。一個(gè)車(chē)次在某車(chē)站是否有車(chē)底執(zhí)行取決于2個(gè)方面，必須有反方向的車(chē)次在終點(diǎn)站折返后開(kāi)行該車(chē)次或者由車(chē)輛段中的車(chē)底直接開(kāi)行。否則該車(chē)次在該車(chē)站的服務(wù)將被取消。上述條件可以由以下表達(dá)式進(jìn)行約束：

（9）為了保證乘客服務(wù)質(zhì)量，車(chē)次到達(dá)車(chē)站的間隔不應(yīng)過(guò)大，規(guī)定不能連續(xù)2個(gè)車(chē)次取消服務(wù)，從而保證了各個(gè)車(chē)站的服務(wù)頻次，約束保證為：

（10）在實(shí)際運(yùn)營(yíng)中，從車(chē)輛段發(fā)出的車(chē)底數(shù)量應(yīng)該小于等于車(chē)輛段初始的存車(chē)數(shù)量，約束保證為：

（11）在實(shí)際運(yùn)營(yíng)中，車(chē)次在各個(gè)車(chē)站的提前發(fā)車(chē)時(shí)間一般不得超過(guò)一個(gè)固定的閾值，用符號(hào)emax來(lái)表示最大允許的早發(fā)時(shí)間，并定義約束為：

（12）加開(kāi)車(chē)次約束。對(duì)于加開(kāi)車(chē)次來(lái)說(shuō)，其本身需要滿(mǎn)足式（7）—式（12）這幾類(lèi)約束。此外，由于加開(kāi)車(chē)次的次序和計(jì)劃車(chē)次的次序不確定，因此需要增加加開(kāi)車(chē)次和計(jì)劃車(chē)次的追蹤間隔約束：

（13）乘客乘降約束。首先計(jì)算乘客等待人數(shù)：

式中：nwi，p表示在車(chē)站p等待乘坐車(chē)次i的乘客數(shù)量。

式（20）是一個(gè)取最小值的表達(dá)式，左邊項(xiàng)即ci，p?M表示若車(chē)次i取消，則等待上車(chē)人數(shù)為0。右邊項(xiàng)表示在車(chē)站p等待乘坐車(chē)次i的乘客數(shù)量等于在車(chē)站p等待乘坐車(chē)次i- 1 的乘客數(shù)量減去實(shí)際乘坐車(chē)次i- 1的乘客數(shù)量nsi-1，p，加上車(chē)次i之前車(chē)次的發(fā)車(chē)時(shí)刻至車(chē)次i發(fā)車(chē)時(shí)刻到達(dá)的乘客數(shù)量，最后減去乘坐加開(kāi)車(chē)次g的乘客。mi，p計(jì)算公式如下：

如果車(chē)次i在車(chē)站p取消服務(wù)，那么mi，p就等于車(chē)次i之前第1 個(gè)沒(méi)有取消的車(chē)次發(fā)車(chē)時(shí)間，否則mi，p等于車(chē)次i在車(chē)站p的發(fā)車(chē)時(shí)間。

計(jì)算車(chē)站上車(chē)人數(shù)，車(chē)站p乘坐車(chē)次i的乘客數(shù)量是等待人數(shù)和最大上車(chē)人數(shù)的最小值：

至此，列車(chē)運(yùn)行的基本模型構(gòu)建完畢。在模型的構(gòu)建過(guò)程中，部分約束引入了二次項(xiàng)導(dǎo)致模型非線(xiàn)性，為方便求解，必須將約束線(xiàn)性化。

2 模型線(xiàn)性化方法

構(gòu)建列車(chē)運(yùn)行約束時(shí)引入了大量非線(xiàn)性約束，為了方便求解，采用線(xiàn)性化方法將模型轉(zhuǎn)化為整數(shù)規(guī)劃模型。下面針對(duì)模型中典型的非線(xiàn)性結(jié)構(gòu)介紹其對(duì)應(yīng)的線(xiàn)性化方法。

（1）min 函數(shù)線(xiàn)性化。以上車(chē)人數(shù)約束為例進(jìn)行線(xiàn)性化。nsi，p= min{nwi，p，NSMAX}可以改寫(xiě)為：

（2） max 函數(shù)線(xiàn)性化。以表達(dá)式mi，p=max{di，p，mi-1，p，dg，p?xg，i}，i> 1 為例進(jìn)行說(shuō)明，該表達(dá)式可以由下面的線(xiàn)性約束進(jìn)行替換：

（3）絕對(duì)值函數(shù)線(xiàn)性化。在計(jì)算列車(chē)延誤時(shí)引入絕對(duì)值和二次項(xiàng)表達(dá)式devi=(|ai，des(i)-，des(i)|+|di，ori(i)-，ori(i)|) ?ci，i∈I。為了將該表達(dá)式中的絕對(duì)值函數(shù)線(xiàn)性化，首先定義輔助變量ui，p，vi，p并添加約束如下［11］：

上面的約束將絕對(duì)值表達(dá)式轉(zhuǎn)化為4 個(gè)線(xiàn)性約束，此時(shí)原表達(dá)式可以等價(jià)改寫(xiě)為：

3 仿真驗(yàn)證

為了驗(yàn)證提出模型的有效性，設(shè)計(jì)仿真案例進(jìn)行驗(yàn)證分析?？紤]一個(gè)典型的城軌線(xiàn)路，線(xiàn)路中有5個(gè)車(chē)站，每個(gè)車(chē)站有上下行2 個(gè)站臺(tái)。為了方便出車(chē)和回庫(kù)，在上下行的終點(diǎn)站各設(shè)置1個(gè)車(chē)輛段。選取上下行各15 個(gè)車(chē)次，上下行前10 個(gè)車(chē)次保持180 s 的發(fā)車(chē)間隔，后續(xù)的5 個(gè)車(chē)次按照360 s 間隔運(yùn)行。下面將針對(duì)不同的參數(shù)設(shè)置進(jìn)行仿真驗(yàn)證。

（1）以最小化運(yùn)行圖偏移和取消車(chē)次數(shù)量為目標(biāo)的運(yùn)行調(diào)整方式。設(shè)置權(quán)重參數(shù)ωz= 0，ωd= 1，ωc=300，選取不同的故障車(chē)站進(jìn)行仿真驗(yàn)證，每個(gè)案例設(shè)置故障時(shí)長(zhǎng)300 s，仿真結(jié)果見(jiàn)表4。

表4 以最小化運(yùn)行圖偏移和取消車(chē)次數(shù)量為目標(biāo)的運(yùn)行調(diào)整方式仿真結(jié)果

案例1—案例3 為上行車(chē)次9 故障，案例4—案例5為下行車(chē)次9故障，為更直觀(guān)地顯示運(yùn)行調(diào)整效果，繪制了案例2中的列車(chē)運(yùn)行圖（見(jiàn)圖2）。

（2）以最小化滯留乘客數(shù)量為目標(biāo)的運(yùn)行調(diào)整方式。設(shè)置權(quán)重參數(shù)ωz= 1，ωd= 0，ωc= 0，選取不同的故障時(shí)長(zhǎng)和故障位置進(jìn)行仿真，仿真結(jié)果見(jiàn)表5。

表5 以最小化滯留乘客數(shù)量為目標(biāo)的運(yùn)行調(diào)整方式仿真結(jié)果

對(duì)比表4、表5 的計(jì)算結(jié)果可知，表5 的滯留乘客數(shù)量相比于表4 的結(jié)果大大減少，但運(yùn)行圖偏移較大，這主要是由于目標(biāo)函數(shù)權(quán)重的設(shè)置不同導(dǎo)致的。接著，繪制表5中案例2的運(yùn)行調(diào)整結(jié)果見(jiàn)圖3。

圖3 以最小化滯留乘客數(shù)量為目標(biāo)的運(yùn)行調(diào)整結(jié)果（上行車(chē)次9在車(chē)站3故障300 s）

（3）綜合考慮乘客服務(wù)與運(yùn)營(yíng)指標(biāo)的調(diào)整方式。采用綜合考慮滯留乘客數(shù)量和運(yùn)營(yíng)指標(biāo)的調(diào)整方式，設(shè)置車(chē)站3 為故障車(chē)站，上行車(chē)次9 為故障車(chē)次，選取不同的權(quán)重參數(shù)進(jìn)行仿真，與上面的2 組實(shí)驗(yàn)進(jìn)行對(duì)比，計(jì)算結(jié)果見(jiàn)表6。由表6 可知，隨著滯留乘客數(shù)量權(quán)重的增加，優(yōu)化得到的滯留乘客數(shù)量隨之減少。因此，調(diào)度員在調(diào)整運(yùn)行圖時(shí)應(yīng)當(dāng)根據(jù)實(shí)時(shí)運(yùn)行狀況采取不同的調(diào)整手段。例如在滯留乘客數(shù)量較多時(shí)，增加有關(guān)乘客服務(wù)的權(quán)重，及時(shí)服務(wù)車(chē)站滯留乘客，反之則增加運(yùn)行圖偏移和取消車(chē)次的權(quán)重。

表6 綜合考慮運(yùn)行圖偏移、取消車(chē)次數(shù)量和滯留乘客數(shù)量的運(yùn)行調(diào)整方式仿真結(jié)果

（4）考慮加開(kāi)臨客的調(diào)度策略。研究加開(kāi)臨客策略對(duì)運(yùn)行調(diào)整結(jié)果的影響，在上行方向增加1個(gè)臨時(shí)客運(yùn)車(chē)次，研究不同故障車(chē)站對(duì)仿真結(jié)果的影響。目標(biāo)函數(shù)權(quán)重設(shè)置為0.5∶0.5∶150，計(jì)算結(jié)果見(jiàn)表7。對(duì)比表1 和表2 的計(jì)算結(jié)果可以發(fā)現(xiàn)，加開(kāi)車(chē)次后，滯留乘客的數(shù)量大大減少了，驗(yàn)證了加開(kāi)車(chē)次策略的有效性。

表7 考慮加開(kāi)車(chē)次調(diào)整措施的運(yùn)行調(diào)整仿真結(jié)果

4 結(jié)論

以城軌高峰到平峰過(guò)渡時(shí)段發(fā)生列車(chē)延誤為場(chǎng)景，綜合考慮運(yùn)營(yíng)公司指標(biāo)以及乘客服務(wù)質(zhì)量，以最小化列車(chē)延誤、取消車(chē)次和車(chē)站滯留乘客數(shù)量為目標(biāo)函數(shù)構(gòu)建了城軌列車(chē)運(yùn)行圖調(diào)整模型。為了提高故障的恢復(fù)效率，該模型考慮了加開(kāi)備車(chē)的調(diào)度策略，利用線(xiàn)性化手段將目標(biāo)和約束中的非線(xiàn)性表達(dá)式線(xiàn)性化，從而將模型轉(zhuǎn)化為混合整數(shù)線(xiàn)性規(guī)劃模型。為了驗(yàn)證模型的有效性，設(shè)計(jì)了仿真案例進(jìn)行驗(yàn)證。通過(guò)CPLEX求解器求解模型，結(jié)果表明提出的運(yùn)行調(diào)整方法能夠在恢復(fù)運(yùn)營(yíng)秩序的同時(shí)有效減少過(guò)渡時(shí)段因列車(chē)延誤導(dǎo)致的滯留乘客數(shù)量，為運(yùn)營(yíng)公司提高乘客服務(wù)質(zhì)量提供良好的支撐。在未來(lái)的研究過(guò)程中，可以進(jìn)一步考慮乘客OD數(shù)據(jù)。