賈曉秋，關曉宇

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

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

1 列車運行圖的布線條件及沖突解決方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 數(shù)值算例

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

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

圖 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.