吳學良，王偉，彭浩，王志凱，謝輝，曹馳

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

0 引言

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

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

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

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

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

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

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

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

1.1 問題描述

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

圖1 城軌線路拓撲結構示意圖

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

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

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

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

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

1.2 符號定義

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

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

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

表2 決策變量定義

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

1.3 目標函數(shù)

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

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

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

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

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

將所有計劃車次的延誤時間進行求和，得到：

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

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

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

1.4 約束構建

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

至此，列車運行的基本模型構建完畢。在模型的構建過程中，部分約束引入了二次項導致模型非線性，為方便求解，必須將約束線性化。

2 模型線性化方法

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

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

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

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

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

3 仿真驗證

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

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

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

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

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

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

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

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

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

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

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

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

4 結論

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