楊 維 ，李海鷹，王久亮

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

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

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

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

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

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

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

1.1 符號定義

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

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

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

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

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

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

1.3約束條件

（1）旅客列車開行框架約束

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

（2）列車出發(fā)時刻約束

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

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

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

（4）列車停站時間約束

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

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

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

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

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

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

2 分段編制

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

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

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

2.2 時間段銜接的處理

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

2.3 某一時間段無可行解的處理

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

3 算例

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

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

4 結(jié)束語

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

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

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

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

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