既有線列車(chē)運(yùn)行圖分段優(yōu)化編制方法的研究

楊 維 ，李海鷹，王久亮

（北京交通大學(xué) 交 通運(yùn)輸學(xué)院，北京 1 00044）

列車(chē)運(yùn)行圖編制是運(yùn)輸組織中的一個(gè)核心環(huán)節(jié)，編圖時(shí)應(yīng)盡可能地減少或避免列車(chē)在非停站停車(chē)或者被越行，同時(shí)要考慮旅客的方便換乘，合理地安排列車(chē)的到發(fā)時(shí)刻。既有研究多是針對(duì)列車(chē)運(yùn)行次序已定的情況下[1~2]，或者是從充分利用運(yùn)能的角度出發(fā)[3]，安排貨物列車(chē)在各站的到發(fā)時(shí)刻和車(chē)站作業(yè)情況。本文針對(duì)既有線列車(chē)運(yùn)行圖編制的特點(diǎn)，對(duì)其優(yōu)化編制方法進(jìn)行研究，提出一種基于數(shù)學(xué)優(yōu)化的分段編制方法。

1 列車(chē)運(yùn)行圖優(yōu)化編制模型

既有線列車(chē)運(yùn)行圖優(yōu)化鋪畫(huà)模型的已知條件主要有：

（1）給定列車(chē)開(kāi)行情況。既有列車(chē)在各站的到發(fā)時(shí)刻。

（2）待鋪畫(huà)列車(chē)的開(kāi)行需求。列車(chē)開(kāi)行數(shù)量、列車(chē)的始發(fā)、終到、途經(jīng)站、列車(chē)的停站方案、列車(chē)在各站的到發(fā)時(shí)間窗。

（3）列車(chē)作業(yè)時(shí)分標(biāo)準(zhǔn)。主要是區(qū)間運(yùn)行時(shí)分、起停車(chē)附加時(shí)分、列車(chē)停站時(shí)間、列車(chē)間隔時(shí)間（同向列車(chē)的到達(dá)間隔時(shí)間、出發(fā)間隔、通過(guò)間隔時(shí)間等）。

1.1 符號(hào)定義

f 區(qū) 間，f∈F；按下行方向，將區(qū)間f的起點(diǎn)站記為f0，終點(diǎn)站記為fd

di列車(chē)i的運(yùn)行方向，i∈Tr；di取值為{1，2}，分別表示下行和上行

o(i) 列車(chē)i的起點(diǎn)站，i∈Tr

d(i)列車(chē)i的終點(diǎn)站，i∈Tr

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

以列車(chē)旅行時(shí)間總和最小為模型的目標(biāo)函數(shù)。包含了總停站時(shí)間最小、被越行次數(shù)最?。ㄔ叫袝?huì)產(chǎn)生額外的停站時(shí)間），體現(xiàn)了列車(chē)運(yùn)行的快捷性。計(jì)算公式為：

1.3約束條件

（1）旅客列車(chē)開(kāi)行框架約束

旅客列車(chē)開(kāi)行數(shù)目、旅客列車(chē)的始發(fā)、終到、途徑站、旅客列車(chē)的停站情況、旅客列車(chē)在各個(gè)車(chē)站的到發(fā)時(shí)刻均為已知，即：

（2）列車(chē)出發(fā)時(shí)刻約束

列車(chē)在始發(fā)站的出發(fā)時(shí)間應(yīng)該在一定的時(shí)間范圍內(nèi)，即：

（3）列車(chē)的區(qū)間運(yùn)行時(shí)分約束

列車(chē)的區(qū)間運(yùn)行時(shí)分包含列車(chē)的純運(yùn)行時(shí)分和起停附加時(shí)分，則上下行列車(chē)的區(qū)間運(yùn)行時(shí)分分別為：

（4）列車(chē)停站時(shí)間約束

列車(chē)在車(chē)站的停站時(shí)間應(yīng)該大于最小的停站時(shí)間，即：

（5）列車(chē)的車(chē)站作業(yè)間隔時(shí)間約束

對(duì)于雙線鐵路，列車(chē)在車(chē)站需要滿足的間隔時(shí)間包括同向列車(chē)的到達(dá)間隔時(shí)間、出發(fā)間隔時(shí)間和通過(guò)間隔時(shí)間。對(duì)于：

即任意2列經(jīng)過(guò)同一區(qū)間的下行列車(chē)，需要滿足如下的間隔時(shí)間：

其中，M是一個(gè)足夠大的正整數(shù)，引入M是為了將非線性約束轉(zhuǎn)化為線性約束。公式（10）和（11）的含義是當(dāng)前后行列車(chē)自區(qū)間起點(diǎn)出發(fā)時(shí)，需要滿足出發(fā)間隔。類似地，公式（12）和（13）條件為到達(dá)間隔時(shí)間，分別表示前后行列車(chē)在區(qū)間終點(diǎn)停車(chē)時(shí)，2列車(chē)的到達(dá)時(shí)間應(yīng)滿足同向列車(chē)的到達(dá)間隔；公式（14）為通過(guò)間隔時(shí)間，即當(dāng)前后行列車(chē)在區(qū)間起點(diǎn)的狀態(tài)為通過(guò)時(shí)，2列車(chē)的始發(fā)間隔應(yīng)滿足同向列車(chē)通過(guò)間隔。

上述（1）～（25）式共同構(gòu)成了既有線列車(chē)運(yùn)行圖的優(yōu)化編制模型。

2 分段編制

本文建立的模型是一個(gè)線性整數(shù)規(guī)劃模型，決策變量的個(gè)數(shù)（主要是列車(chē)前后行關(guān)系變量rijf）隨著列車(chē)數(shù)和區(qū)間數(shù)的增加而呈指數(shù)型增長(zhǎng)，是一個(gè)NP難問(wèn)題，當(dāng)列車(chē)數(shù)較多時(shí)，直接對(duì)模型進(jìn)行求解比較困難。對(duì)約束條件和目標(biāo)函數(shù)進(jìn)行分析，可以看出，運(yùn)行圖優(yōu)化鋪畫(huà)模型的核心就是在滿足基本的時(shí)間約束的情況下，合理安排列車(chē)在區(qū)間的運(yùn)行次序和在車(chē)站的到發(fā)時(shí)刻，而難點(diǎn)在于合理確定列車(chē)的運(yùn)行次序和避免產(chǎn)生沖突，而沖突的發(fā)生往往是在一個(gè)較小的時(shí)間范圍內(nèi)。因此，本文采用分段鋪畫(huà)的方法，取3-6 h為一個(gè)時(shí)間段（具體取值視問(wèn)題規(guī)模而定），從天窗的結(jié)束時(shí)間開(kāi)始，每次鋪畫(huà)一個(gè)時(shí)間段的運(yùn)行圖，然后不斷將該時(shí)間段往前推進(jìn)，直至推進(jìn)到天窗的開(kāi)始時(shí)間。對(duì)于每個(gè)時(shí)間段內(nèi)的運(yùn)行圖鋪畫(huà)，由于列車(chē)數(shù)大大減少，可直接利用成熟的數(shù)學(xué)軟件（Lingo）對(duì)模型進(jìn)行求解。這樣，通過(guò)合理地設(shè)置時(shí)間段長(zhǎng)度和進(jìn)入時(shí)間段的列車(chē)以及時(shí)間段接續(xù)的處理，可以快速地完成運(yùn)行圖優(yōu)化鋪畫(huà)模型的求解，并保持了運(yùn)行圖的整體優(yōu)化性。下面對(duì)該方法中幾個(gè)關(guān)鍵問(wèn)題的處理方法進(jìn)行說(shuō)明：

2.1 列車(chē)的時(shí)間段分布情況的預(yù)處理

列車(chē)的時(shí)間段分布情況是指每個(gè)時(shí)間段內(nèi)需要鋪畫(huà)的列車(chē)數(shù)量和構(gòu)成情況。如果開(kāi)行方案的結(jié)果細(xì)化到小時(shí)，或者小于時(shí)間段的長(zhǎng)度，則該步可以省略。否則，根據(jù)列車(chē)的時(shí)間分布特性確定列車(chē)的時(shí)間段分布情況：將始發(fā)站、終到站、停站、列車(chē)種類、編組內(nèi)容均相同的列車(chē)記為一類列車(chē)。這部分的處理結(jié)果體現(xiàn)在列車(chē)的出發(fā)時(shí)刻范圍約束上，即對(duì)于每列車(chē)，其出發(fā)時(shí)刻范圍應(yīng)為其所在時(shí)間段與開(kāi)行方案中規(guī)定的列車(chē)始發(fā)時(shí)間范圍的交集。要求在進(jìn)行本部分處理時(shí)，應(yīng)保證該交集不為空。

2.2 時(shí)間段銜接的處理

對(duì)于2個(gè)相鄰時(shí)間段，可能會(huì)出現(xiàn)跨時(shí)間段運(yùn)行線，即鋪畫(huà)結(jié)果中，某一運(yùn)行線的部分運(yùn)行時(shí)間在本時(shí)間段，部分運(yùn)行時(shí)間進(jìn)入下一時(shí)間段。考慮到后續(xù)時(shí)間段的優(yōu)化以及跨時(shí)間段運(yùn)行線對(duì)其后續(xù)運(yùn)行線的影響（間隔約束），將跨時(shí)間段列車(chē)計(jì)入下一時(shí)間段，并將進(jìn)入下一時(shí)間段的到發(fā)時(shí)刻轉(zhuǎn)化為未知，作為變量求解。此外，對(duì)相鄰時(shí)間段內(nèi)的有換乘接續(xù)關(guān)系的列車(chē)，都記入前一個(gè)時(shí)間段進(jìn)行鋪畫(huà)，并將鋪畫(huà)結(jié)果記入后一時(shí)間段，是一個(gè)連續(xù)推進(jìn)的過(guò)程。

2.3 某一時(shí)間段無(wú)可行解的處理

對(duì)于列車(chē)數(shù)較多的時(shí)間段，可能會(huì)出現(xiàn)無(wú)可行解的情況，即該時(shí)間段的列車(chē)無(wú)法在本時(shí)間段內(nèi)全部鋪畫(huà)完，不滿足間隔時(shí)間，需要移部分列車(chē)至其它時(shí)間段。對(duì)于這種情況，記錄無(wú)可行解的時(shí)間段，并根據(jù)開(kāi)行方案中的列車(chē)到發(fā)時(shí)間范圍將部分列車(chē)移入下一時(shí)間段，直至有可行解，然后繼續(xù)分段時(shí)間段，若至天窗仍無(wú)法全部鋪畫(huà)，則根據(jù)無(wú)可行解發(fā)生的時(shí)間段記錄重新調(diào)整列車(chē)的時(shí)間段分布情況，重新進(jìn)行鋪畫(huà)。分段求解流程如圖1。

3 算例

以南昌鐵路局鷹潭至向塘區(qū)段為實(shí)例，進(jìn)行列車(chē)運(yùn)行圖鋪畫(huà)。該區(qū)段共有9個(gè)車(chē)站，8個(gè)區(qū)間。按照2008年7月1日的列車(chē)運(yùn)行圖，該區(qū)段開(kāi)行的列車(chē)有：動(dòng)車(chē)組旅客列車(chē)、直達(dá)特快旅客列車(chē)、特快旅客列車(chē)、快速旅客列車(chē)、普通旅客列車(chē)、貨物列車(chē)、行郵特快專列、行包特快專列以及路用列車(chē)，其中以旅客列車(chē)和貨物列車(chē)為主。在旅客列車(chē)鋪畫(huà)框架已定，各列車(chē)參數(shù)取值已定的情況下，運(yùn)用本文提出的方法，鋪畫(huà)列車(chē)運(yùn)行圖如圖2。

圖1 分段求解方法思路示意圖

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

本文針對(duì)既有線列車(chē)開(kāi)行的特點(diǎn)，對(duì)既有線列車(chē)運(yùn)行圖的優(yōu)化編制問(wèn)題進(jìn)行了研究，建立了既有線列車(chē)運(yùn)行圖的優(yōu)化編制模型，設(shè)計(jì)了基于數(shù)學(xué)優(yōu)化的分段編制方法。算例表明，該方法有效地降低了問(wèn)題求解的復(fù)雜性，并保持了求解結(jié)果的整體優(yōu)化性。

圖2 運(yùn)行圖鋪畫(huà)結(jié)果

[1] 彭其淵，朱松年，王 培. 網(wǎng)絡(luò)列車(chē)運(yùn)行圖的數(shù)學(xué)模型及其算法研究[J]. 鐵道學(xué)報(bào)，2001，23（1）：1-8.

[2] 史 峰.單線列車(chē)運(yùn)行圖鋪畫(huà)的時(shí)間循環(huán)迭代優(yōu)化方法[J].鐵道學(xué)報(bào)，2005，27（1）：1-5.

[3] 周磊山. 計(jì)算機(jī)編制網(wǎng)狀線路列車(chē)運(yùn)行圖方法研究[J].鐵道學(xué)報(bào)，1998，20（5）：15-21.