賈曉秋，關(guān)曉宇

（1.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031；2.西南交通大學(xué) 材料科學(xué)與工程學(xué)院，四川 成都 610031）

目前，國內(nèi)外學(xué)者在計算機(jī)鋪畫列車運(yùn)行圖方面進(jìn)行了深入研究，主要涉及單線、雙線、區(qū)域和網(wǎng)絡(luò)范圍[1-4]。隨著我國高速鐵路的建設(shè)，針對列車運(yùn)行圖的鋪畫，在有關(guān)研究的基礎(chǔ)上，設(shè)計了基于運(yùn)行線分解的列車運(yùn)行圖布線方法。該方法可以適應(yīng)周期或非周期列車運(yùn)行圖的鋪畫，并在實際規(guī)劃過程中，能較快地給出較優(yōu)鋪畫方案。

1 列車運(yùn)行圖的布線條件及沖突解決方法

列車運(yùn)行圖是列車的開行計劃，其前提條件是已經(jīng)編制好列車開行方案。因此，可以根據(jù)列車開行方案確定所規(guī)劃區(qū)段上各區(qū)間的列車數(shù)量、速度、類型、起停車附加時分、區(qū)間純運(yùn)行時間、在各車站的停站方案等信息，同時還必須已知車站及區(qū)間的各種安全間隔時間、線路長度、到發(fā)線數(shù)量、容車類型等信息，這些信息是鋪畫列車運(yùn)行圖的基本信息。

在不考慮安全間隔時間約束的理想條件下，列車運(yùn)行圖的布線問題就是一個簡單的列車發(fā)到的時間傳播過程。為了解決運(yùn)行線沖突，需要將每一始發(fā)站至終到站的運(yùn)行線分解成若干個列車-區(qū)間，假設(shè)全部列車的所有運(yùn)行區(qū)間集合構(gòu)成了的待規(guī)劃集合TS＝{(ti，sj) |ti∈Tr，sj∈ρti，j＜kti}，如圖1所示，最左邊的下行列車t，可以按照所經(jīng)過的區(qū)間將其分為3個列車-區(qū)間。圖1中待規(guī)劃的列車共有3列，因而共有9個列車-區(qū)間，其中TS＝{(t,1)，…，(t,3)，(r,1)，…，(r,3)，(p,1)，…，(p,3)}。

圖 1 列車運(yùn)行線按區(qū)間分解示意圖

在實際布線過程中，需要動態(tài)地考慮運(yùn)行線之間的沖突問題。對于某一區(qū)間，當(dāng)前待布置的運(yùn)行線必須滿足該區(qū)間內(nèi)已經(jīng)布置列車到發(fā)時間的運(yùn)行線之間的安全間隔時間約束。若當(dāng)前待布置的運(yùn)行線與區(qū)間內(nèi)已布置列車到發(fā)時間的運(yùn)行線發(fā)生沖突時，由于已布置運(yùn)行線的列車區(qū)間發(fā)到時刻不宜改動，因而具有較高的優(yōu)先權(quán)，所以需要延遲當(dāng)前待布置運(yùn)行線的列車區(qū)間發(fā)車時刻，以緩解沖突，實現(xiàn)列車安全運(yùn)行。重復(fù)上述的布線過程，直至待規(guī)劃的運(yùn)行線任務(wù)集合為空集，即完成一個運(yùn)行圖的布線任務(wù)。

對于同向列車布線，如圖2所示，假設(shè)當(dāng)前待規(guī)劃列車為t，其中p、q、r、m、n是已經(jīng)布置到當(dāng)前區(qū)間s的運(yùn)行線，假設(shè)τ是t在區(qū)間s的初始發(fā)車時刻，α、β、γ為該區(qū)間列車t的發(fā)車位置。

（1）當(dāng)t在初始位置發(fā)車時，會因為列車速度差而與運(yùn)行線r在區(qū)間發(fā)生沖突；當(dāng)t在位置α發(fā)車時，可能會因為在車站v不滿足運(yùn)行線間的最小到達(dá)間隔約束而與列車p或q發(fā)生沖突。

（2）當(dāng)t在位置β發(fā)車時，可能會因為在車站u不滿足運(yùn)行線間的最小發(fā)車間隔約束而與列車q或m發(fā)生沖突。

（3）只有當(dāng)列車在位置γ發(fā)車時，既滿足在車站u的最小發(fā)車間隔時間和在車站v的到達(dá)間隔時間約束，同時又不會因為列車速度差而導(dǎo)致運(yùn)行線間的沖突，因而運(yùn)行線t需要延遲到γ發(fā)車。

圖 2 布置同向列車時，搜索發(fā)車位置示意圖

從上述過程看，在區(qū)間s＝(u，v) 上布置列車運(yùn)行線t時，必須考慮已經(jīng)布置的列車運(yùn)行線p、q、r、m、n，當(dāng)發(fā)生沖突時，需要延遲待布置列車運(yùn)行線的發(fā)車時刻。因此，列車合理發(fā)車時刻的搜索過程就變成在該區(qū)間上尋找已布置相鄰列車運(yùn)行線間的“合理時間間隔”問題。

在上述過程中，需要指出的是，若待規(guī)劃的列車運(yùn)行線t在車站u計劃發(fā)車狀態(tài)是通過車站，而假設(shè)t此時又必須在車站u等待前行列車p、q或m離開車站u，并滿足一定間隔時間后才能在位置發(fā)車，從而不發(fā)生沖突，因此列車t在車站u必須將原來計劃的通過狀態(tài)改為停站狀態(tài)，即技術(shù)停站狀態(tài)。這時列車t在車站u和車站v的發(fā)到時刻，均需要增加適當(dāng)?shù)钠鹜＼嚫郊訒r分，以適應(yīng)列車技術(shù)停站的需要。

對于異向列車布線而言，僅需要在上述搜索列車發(fā)車位置時，考慮異向列車之間的車站到發(fā)間隔及區(qū)間運(yùn)行時間即可，如圖3所示。

圖 3 布置異向列車時，搜索發(fā)車位置示意圖

具體對于周期為T的列車運(yùn)行圖情況，如圖4所示，首先需要對已經(jīng)布置到區(qū)間u→v的運(yùn)行線按照列車發(fā)車時間由小到大順序排列，得到已布置時間的列車運(yùn)行線序列L＝(y，…，r－1，r，r＋1，…，x－1，x)。在序列L中，為了尋找t的合理發(fā)車位置，首先初始化t的最早發(fā)車時間：＝＋＋Tp，其中、、、p分別為列車t在車站u的出發(fā)時間、到達(dá)時間、停站時間 (計劃停站或技術(shù)停站) 和到發(fā)事件之間的模參數(shù)，并且進(jìn)行下列步驟的運(yùn)行線發(fā)車位置搜索過程。

圖 4 某區(qū)間周期運(yùn)行圖搜索發(fā)車位置示意圖

步驟 1：假設(shè)得到的初始發(fā)車位置k位于序列L中的運(yùn)行線r－1 與運(yùn)行線r之間。

步驟 2：開始的搜索方向是從位置k向序列L的右方向進(jìn)行，搜索任意兩條運(yùn)行線間的發(fā)車位置，判斷該位置是否滿足周期情況下的發(fā)車約束條件，若滿足則停止搜索，置該位置的發(fā)車時刻為列車t的發(fā)車時刻，否則一直搜索至序列L的最后一個相鄰運(yùn)行線x－1 與x之間的發(fā)車位置。

步驟 3：若經(jīng)過步驟2后，并未得到合理的發(fā)車位置，則可以檢查L的最后一條運(yùn)行線x與L最左邊的第一條運(yùn)行線y之間的位置，來判斷是否滿足周期約束條件；若滿足，則置該位置的發(fā)車時刻為列車t的發(fā)車時刻，并停止搜索過程。

步驟 4：若經(jīng)過步驟3后，仍未得到合理的發(fā)車位置，則需要由序列L中的y與y＋1 位置開始繼續(xù)向右搜索，直至列車t的初始發(fā)車位置的前一個位置，即r－2 和r－1 之間的位置為止。若搜索到可行的發(fā)車位置，則將其對應(yīng)的時刻設(shè)置為列車t的發(fā)車時刻，并停止搜索過程。

步驟 5：若經(jīng)過上述搜索步驟仍未得到可行的發(fā)車位置，則需要向前回朔。這說明至少列車t在當(dāng)前運(yùn)行線鋪畫圖譜下，在區(qū)間內(nèi)無可行解，需重新布置鋪畫圖譜。

非周期列車運(yùn)行圖與周期列車運(yùn)行圖區(qū)間發(fā)車位置的具體搜索過程類似，可以將該區(qū)間上一晝夜的運(yùn)行線看作是“一個周期”，即只需要令周期T＝1 440 即可。上述區(qū)間列車發(fā)車位置搜索過程，適用于周期與非周期、單線與雙線系統(tǒng)。例如，當(dāng)搜索單線列車運(yùn)行的約束條件時，就得到單線列車運(yùn)行圖。

2 列車-區(qū)間動態(tài)布線搜索樹

為了得到滿足列車運(yùn)行圖條件的列車-區(qū)間集合TS的元素排序，獲得列車占用區(qū)間的順序，需要動態(tài)地維護(hù)一棵搜索樹。該樹的各個節(jié)點表示列車—區(qū)間節(jié)點 (ti，sj)。在開始時，令該搜索樹的根節(jié)點為空，表示開始搜索。當(dāng)獲得所有列車-區(qū)間節(jié)點(ti，sj)的發(fā)到時刻后，便可以結(jié)束搜索過程。每次在TS中搜索尚未安排列車到發(fā)時刻的節(jié)點(ti，sj)，一旦得到合適的發(fā)車位置，就將合適的列車發(fā)到時刻布置到當(dāng)前的 (ti，sj)，并從TS中刪除當(dāng)前節(jié)點 (ti，sj)。反復(fù)進(jìn)行上述搜索直到TS的全部元素均已分配列車發(fā)到時刻為止。

設(shè) (ti，sj) 屬于搜索樹的第l層，則節(jié)點 (ti，sj) 的后繼節(jié)點是TS中所有未布置列車發(fā)到時刻的(ti，sj) 節(jié)點，即第l層中 (ti，sj) 的兄弟節(jié)點和節(jié)點(ti，sj+1)。列車運(yùn)行圖的規(guī)劃過程，實質(zhì)是在動態(tài)搜索樹上，尋找一條由初始節(jié)點出發(fā)至結(jié)束節(jié)點的路徑，按照這條路徑可以得到較好的運(yùn)行圖鋪畫方案。

3 數(shù)值算例

某區(qū)段列車開行方案如圖5所示，列車速度為300 km/h，計劃停站時間窗[2，5]60，車站各類間隔時間均為 3 min，列車起停車附加時分為 1 min。用C++實現(xiàn)上述算法，經(jīng)過 2 000 次迭代計算。列車在各站的一個周期 (1 h) 的到發(fā)時刻如表1所示 (一個周期內(nèi)的數(shù)據(jù))。

該算法能在較短時間內(nèi)解決一個周期內(nèi)，以及相鄰周期之間的列車運(yùn)行線的沖突問題，而且對周期與非周期列車運(yùn)行圖均適用，對于中小規(guī)模的列車運(yùn)行圖實例收斂速度也較快。

圖 5 某區(qū)段列車開行方案

表 1 某區(qū)段列車時刻表

[1] Lindner，T. Train Schedule Optimization in Public Rail Transport[D]. TU Braunschweig，Germany，2000.

[2] Odijk，M. Railway Timetable Generation[D]. TU Delft，The Netherlands，1997.

[3] Peeters L. Cyclic railway timetable optimization[D]. Erasmus Institute，Erasmus University，Rotterdam，2003.

[4] Liebchen C. Symmetry for periodic railway timetables[J].Electronic Notes in Theoretical Computer Science，2004(92)：34-51.