高速鐵路列車(chē)運(yùn)行圖新增列車(chē) 運(yùn)行線優(yōu)化方法研究

毛萬(wàn)華，陳亞茹

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

0 引言

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

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

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

1 高速鐵路列車(chē)運(yùn)行圖新增列車(chē)運(yùn)行線模型構(gòu)建

1.1 問(wèn)題描述

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

1.2 事件－活動(dòng)圖

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

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

1.3 線性規(guī)劃模型

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

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

2 案例分析

2.1 數(shù)據(jù)準(zhǔn)備

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

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

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

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

表1 新增列車(chē)運(yùn)行線信息Tab.1 Information of newly-added train paths

2.2 結(jié)果驗(yàn)證

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

表2 成功新增列車(chē)運(yùn)行線信息Tab.2 Information of successfully newly-added train paths

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

表3 指標(biāo)統(tǒng)計(jì)分析Tab.3 Statistical analysis of indicators

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

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

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

3 結(jié)束語(yǔ)

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