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

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

0 引言

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

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

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

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

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

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

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

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

1.1 問題描述

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

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

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

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

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

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

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

1.2 符號定義

（1）集合及參數(shù)符號定義見表1。

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

（2）決策變量定義見表2。

表2 決策變量定義

（3）中間變量定義見表3。

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

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

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

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

（2）列車延誤。定義列車延誤為：

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

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

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

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

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

1.4 約束構(gòu)建

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

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

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

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

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

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

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

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

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

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

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

（12）加開車次約束。對于加開車次來說，其本身需要滿足式（7）—式（12）這幾類約束。此外，由于加開車次的次序和計(jì)劃車次的次序不確定，因此需要增加加開車次和計(jì)劃車次的追蹤間隔約束：

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

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

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

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

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

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

2 模型線性化方法

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

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

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

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

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

3 仿真驗(yàn)證

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

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

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

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

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

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

對比表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é)果見圖3。

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

（3）綜合考慮乘客服務(wù)與運(yùn)營指標(biāo)的調(diào)整方式。采用綜合考慮滯留乘客數(shù)量和運(yùn)營指標(biāo)的調(diào)整方式，設(shè)置車站3 為故障車站，上行車次9 為故障車次，選取不同的權(quán)重參數(shù)進(jìn)行仿真，與上面的2 組實(shí)驗(yàn)進(jìn)行對比，計(jì)算結(jié)果見表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ù)車站滯留乘客，反之則增加運(yùn)行圖偏移和取消車次的權(quán)重。

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

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

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

4 結(jié)論

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