毛萬華，陳亞茹

（1.中國鐵路蘭州局集團有限公司 調(diào)度所，甘肅 蘭州 730000；2.中國鐵道科學研究院集團有限公司 電子計算技術研究所，北京 100081）

0 引言

列車運行圖是用以表示列車在區(qū)間運行及在車站到發(fā)或通過時刻的技術文件，是全路組織列車運行的基礎[1]。在實際運營過程中，由于突發(fā)事件或節(jié)假日客流激增，都需要組織臨時加開列車，新增列車運行線可以應用于日常計劃編制及列車運行圖調(diào)整過程中。在新增列車運行線時，需要綜合考慮原始列車及新增列車對運行圖性能的影響，應在對原始列車影響程度最小的情況下，盡可能從需要新增的列車運行線備選集中加入更多的運行線，以滿足客流出行需求。

目前，關于列車運行圖新增列車運行線的調(diào)整問題研究相對較多。Burdett等[2]提出三階段加線過程，通過固定或適當移動已鋪畫的列車運行線實現(xiàn)加線。Tan等[3]將列車加線問題分解為2個子問題，分別是列車重排序問題和列車順序固定情況下的插線問題，并利用分支定界算法，設計迭代重排序策略求解。徐涵等[4]在周期列車運行圖加線過程中，考慮靈活接續(xù)約束，實現(xiàn)列車接續(xù)與列車運行圖的協(xié)同優(yōu)化。江峰等[5]基于時空網(wǎng)絡構建模型，考慮列車始發(fā)時刻和初始利潤，目標函數(shù)為運行線總利潤最大，設計基于拉格朗日松弛的啟發(fā)式算法求解，進一步提高算法求解效率。劉敏[6]針對部分客運專線增開本線列車及調(diào)整列車開行方案，實現(xiàn)運力資源與需求的合理匹配，進一步優(yōu)化運輸資源配置。王鍇楷等[7]考慮貨物列車在集結(jié)或者編組過程中因外在因素導致部分列車延誤，結(jié)合運到期限、停站時間限制等約束條件，建立了針對貨物列車延遲情況下的列車運行圖加線模型，以中歐班列西通道鄭州—阿拉山口為例，驗證模型的有效性。張小炳等[8]考慮貨物運到期限，建立0-1整數(shù)規(guī)劃模型，并設計了模擬退火算法求解。

總體而言，既有文獻對列車運行圖加線問題的研究主要是基于周期列車運行圖。對于非周期列車運行圖的調(diào)整主要考慮針對加線列車確定的情況，但由于線路通過能力的限制，在新增列車運行線較多的情況下，難以全部實現(xiàn)加線成功。研究針對部分線路列車客座率普遍較高的情況，建立列車運行圖新增列車運行線模型，基于提供的新增列車運行線備選集，在盡可能減少對原始列車運行圖調(diào)整的原則下，以合適的目標函數(shù)為導向，優(yōu)先選擇恰當?shù)男略隽熊囘\行線組合。

1 高速鐵路列車運行圖新增列車運行線模型構建

1.1 問題描述

隨著高速鐵路路網(wǎng)規(guī)模的不斷擴大，我國高速鐵路已經(jīng)從快速建設階段向高效運營階段過渡，為旅客提供更加優(yōu)質(zhì)的服務是鐵路部門提供運輸產(chǎn)品的目標。高速鐵路更是以其安全、舒適、便捷的特點，成為廣大旅客出行選擇的主要交通方式之一。近年來旅客出行需求不斷增長，部分高速鐵路線路能力緊張，其列車客座率普遍較高，為滿足高峰時段或特殊時期旅客快速增長的出行需求，亟需開展新增列車運行線時列車運行圖調(diào)整問題的研究。通過合理組織加開列車的方式，在充分利用線路剩余通過能力的同時，盡可能多地為旅客提供出行服務。新增列車運行線時，涉及到列車運行圖調(diào)整問題。主要包含2類列車，一類是原始列車，一類是新增列車。在加入新的列車運行線時，需要滿足一定的原則：①保持原有開行列車的開行方案不變，適當調(diào)整部分列車在其途經(jīng)站的到發(fā)時間；②新增列車運行線時，需要滿足規(guī)定的時間窗范圍，提高旅客服務的滿意度，盡可能減少對原有列車旅行速度的影響。

1.2 事件－活動圖

為了更加形象地表示列車運行圖中各個元素之間的關聯(lián)關系，研究利用事件－活動圖構建列車運行圖新增列車運行線模型。

定義事件－活動圖G= （V，A）。點集合V表示事件的集合，具體包括列車在車站的出發(fā)或到達事件，即V=Vdep∪Varr，Vdep表示出發(fā)事件集合，Varr表示到達事件集合?；〖螦表示活動的集合，任一活動弧可由2個列車事件表示。主要考慮3類活動弧，分別是運行?。ˋrun）、停站弧（Adwell）和安全?。ˋsafe）。運行弧Arun?Vdep×Varr，表示的是一列車在相鄰2個車站，由前一車站的出發(fā)事件指向后一車站的到達事件；停站弧Adwell?Varr×Vdep，表示的是一列車在同一車站的到達事件指向在該車站的出發(fā)事件。若到達事件與出發(fā)事件發(fā)生時間相同，則表示該列車在車站不停車直接通過；安全弧Asafe?Aarr×Aarr∪Adep×Adep，表示的是不同列車在同一車站到達和出發(fā)事件之間的連接，要滿足安全作業(yè)時間標準。事件－活動圖如圖1所示。

1.3 線性規(guī)劃模型

式中：yi為0-1決策變量，表示列車t（i）狀態(tài)，對于需要新增列車運行線而言，一共有加線成功或加線失敗2種狀態(tài)。其值為1時，表示該列車被選中加線，否則表示該列車無法加入。對于原始列車而言，默認其狀態(tài)為加線成功；runemin為運行弧的區(qū)間最小運行時分；M表示一個無窮大的正整數(shù)；xi，xj表示事件i，j在新時刻表中發(fā)生的時間i∈V；V表示列車事件集合；runemax為運行弧的區(qū)間最大運行時分；e表示由事件i、事件j構成的活動弧；wi為0-1變量，取值為1時，表示停站方案中，列車t（i）在車站s（i）停車，取值為0時，表示停站方案中，列車t（i）在車站s（i）不停車直接通過；dwemin表示停站弧的最小停站時間；dwemax表示停站弧的最大停站時間；λij為0-1決策變量，其值為1，表示事件i比事件j先發(fā)生，否則表示事件j比事件i先發(fā)生；he表示任意2個連續(xù)事件發(fā)生的最小安全間隔時間；zij表示0-1決策變量，其值為1，表示列車t（i）和列車t（j）同時加線成功，即yi=yj= 1；否則，表示至少有1列車加線失??；μ（i）和μ（j）分別表示事件i和事件j發(fā)生的下一個事件；twimin和twimax分別表示事件i的最早發(fā)生時間和最晚發(fā)生時間；V ini表示原始列車事件集合，V ini?V；θi表示事件i相對于原圖最大的調(diào)整程度；πi表示事件i在原時刻表中發(fā)生的時刻，i∈V ini；T ini表示原始列車集合。

公式 ⑴ 為模型的目標函數(shù)，表示成功加入的列車運行線數(shù)量最多。保證在線路能力允許范圍內(nèi)，盡可能多地加入新的列車運行線，以滿足旅客出行需求；公式 ⑵ 為區(qū)間運行時分約束，runemin和runemax為考慮起動和停車附加時分的區(qū)間最小運行時分和區(qū)間最大運行時分。當該列車運行線保留或加線成功，即當yi= 1時，需嚴格滿足區(qū)間運行時分約束；否則該式恒成立，為無效不等式；公式 ⑶ 為列車停站時分約束，表示列車在車站的停站時間要滿足一定的作業(yè)時間要求，即位于最大停站時間dwemax和最小停站時間dwemin之間，同時考慮列車運行線狀態(tài)；公式 ⑷ 和公式 ⑸ 為車站追蹤間隔時間約束，表示2列車在同一車站到達、出發(fā)或通過時，需要滿足的作業(yè)時間間隔，其中he為安全間隔時間約束；公式 ⑹ 對非線性約束zij=yi·yj進一步進行了線性化處理，便于后續(xù)模型求解。公式 ⑺ 為區(qū)間防越行約束，表示任意2列車在區(qū)間上一車站的先后順序與在下一車站的先后順序要保持一致，即區(qū)間不能發(fā)生越行；公式 ⑻ 為列車合理始發(fā)時間窗約束，表示列車的發(fā)車時間要位于合理始發(fā)時間下限twimin和上限twimax之間，若twimin=twimax表示列車出發(fā)時間為固定時間點；公式 ⑼ 表示原始列車的允許調(diào)整時間范圍，其中θi為事件i相對于原圖最大調(diào)整程度；公式 ⑽ 表示原始列車運行線必須保留；公式 ⑾ 為決策變量之間的耦合關系約束；公式 ⑿ 為變量取值約束。

2 案例分析

2.1 數(shù)據(jù)準備

（1）車站線路數(shù)據(jù)：選取京滬高速鐵路（北京南—上海虹橋）北京南—徐州東區(qū)段下行單方向列車運行圖鋪畫為例，涉及到北京南、廊坊、天津南、滄州西、德州東、濟南西、泰安、曲阜東、滕州東、棗莊、徐州東共11個車站。

（2）原始列車運行圖：考慮始發(fā)時間范圍為3 h，共包含30列車，并將時間范圍限制在6 : 00—9 : 00，原始列車運行圖信息如圖2所示。

（3）新增列車運行線備選集：考慮客流波動性，設計加入8條列車運行線，并將運行線的停站方案、列車始發(fā)、終到時間范圍作為模型的輸入。允許新增列車運行線信息如表1所示。

由表1可知，新增列車運行線備選集中一共包含8列車，為了盡可能提高旅客出行滿意度，規(guī)定新增運行線的始發(fā)時間不得早于最早始發(fā)時間，終到時間不得晚于最晚到達時間。

表1 新增列車運行線信息Tab.1 Information of newly-added train paths

2.2 結(jié)果驗證

設計一組案例，具體參數(shù)設置情況為：允許新增列車運行線數(shù)量為8，設置原始列車允許調(diào)整時間為5 min，列車停站時間范圍為2 ～ 15 min，基于以上參數(shù)取值，以新增列車運行線數(shù)量最多為目標函數(shù)，求解得到新增列車運行線示意圖如圖3所示，紅色標注的線為成功新增的列車運行線。根據(jù)模型求解結(jié)果發(fā)現(xiàn)，成功新增列車運行線信息如表2所示。

表2 成功新增列車運行線信息Tab.2 Information of successfully newly-added train paths

分析求解結(jié)果可以發(fā)現(xiàn)，當允許新增列車運行線數(shù)量較多時，線路剩余通過能力不足以組織全部列車開行，此時模型會按照一定的求解規(guī)則選擇合適的列車運行線開行。將新增列車運行線前后的列車運行圖各項指標進行對比，指標統(tǒng)計分析如表3所示。

表3 指標統(tǒng)計分析Tab.3 Statistical analysis of indicators

綜合分析新增列車運行線前后列車運行圖各項指標，可以發(fā)現(xiàn)，由于新增列車運行線導致線路能力緊張，影響原始列車運行圖的性能，比如降低旅行速度、增加停站時間等。同時新增列車的平均旅行速度為177 km/h，與原始列車的平均旅行速度261 km/h相比，其旅行速度也相對較低。這是由于在新增列車運行線時，需要保證對原有列車到發(fā)時刻的調(diào)整程度盡可能小，這就導致了新增列車運行線需要以犧牲自身旅行速度為代價減少對原有列車運行圖的干擾。新增列車運行線后，原始列車的旅行速度由261 km/h下降到209 km/h，這也是受新增列車運行線影響，原有列車的到發(fā)時刻調(diào)整、停站時間增加導致的。另外，原始列車總調(diào)整時間為6 958 min?？傉{(diào)整時間是指原始列車在其途經(jīng)站到發(fā)時刻變化的絕對值之和。由于在案例求解時，設置原始列車始發(fā)時間窗調(diào)整范圍為5 min以內(nèi)，導致列車在其后續(xù)途經(jīng)站的變化時刻可能會出現(xiàn)累加的情況，從而導致列車全程總調(diào)整時間進一步增加。原始列車始發(fā)時間變化分布如圖4所示，原始列車終到時間變化分布如圖5所示。

觀察圖4數(shù)據(jù)，可以發(fā)現(xiàn)原始列車始發(fā)時間調(diào)整范圍為5 min的列車數(shù)量占列車總數(shù)的一半以上，其次是調(diào)整范圍為4 min的列車數(shù)量。而原始列車終到時間變化范圍主要集中在10 ～ 20 min范圍內(nèi)（不包括10 min，但包括20 min），位于該區(qū)間的列車數(shù)量約占列車總數(shù)的1/3，其次是變化范圍為10 min以內(nèi)（包括10 min）的列車數(shù)量。原始列車允許調(diào)整時間的參數(shù)設置會影響新增列車運行線的難度，從而影響最終成功新增的列車運行線數(shù)量。目前模型在求解過程中，只約束了原始列車在其始發(fā)站的發(fā)車調(diào)整時間范圍，若是嚴格限制所有列車在其各個途經(jīng)站的到發(fā)調(diào)整時間范圍，則模型容易出現(xiàn)無解的情況。

實際列車運行圖在調(diào)整過程中，需要考慮新增列車運行線的動車組運用及到發(fā)線股道運用等眾多問題，極大地增加了新增列車運行線的難度。并且由于新增列車運行線備選集中的列車途經(jīng)車站不同，列車所面向的服務客流不一樣，不同列車運行線的優(yōu)先級也會有所不同，后續(xù)可以為新增列車設置不同的優(yōu)先級，確保高等級列車優(yōu)先選中加線。同樣地，選擇不同的目標函數(shù)，也會影響模型求解的方向，從而影響新增列車運行線的最終選擇。若目標函數(shù)選擇新增列車服務客流數(shù)量最多，模型會傾向于選擇為客流較大的OD提供服務的列車；若目標函數(shù)選擇列車總走行距離最長，則模型會傾向于選擇長途旅客列車優(yōu)先加線。因此，在實際列車運行圖調(diào)整過程中，需要綜合考慮各方面因素，并根據(jù)鐵路運營部門的需求，選擇恰當?shù)哪繕撕瘮?shù)，為實際決策提供輔助支撐功能。

3 結(jié)束語

研究通過構建高速鐵路列車運行圖新增列車運行線模型，在已知新增列車運行線備選集的基礎上，以成功新增列車運行線數(shù)量最多為目標函數(shù)，在充分利用線路剩余通過能力的基礎上，盡可能多地加入新的列車運行線。模型實現(xiàn)了新增列車運行線的自主選擇，可根據(jù)實際需求設置不同的目標函數(shù)，從而在線路能力允許范圍內(nèi)，決策最合適的新增列車運行線組合。通過實例結(jié)果證明，該模型可以應用于列車運行圖的調(diào)整或日計劃編制階段，為鐵路運營部門提供輔助決策支撐。該模型未考慮動車組運用和股道分配問題，后續(xù)需要進一步細化模型約束。