基于定序優(yōu)化的高速鐵路網(wǎng)絡(luò)列車運(yùn)行圖優(yōu)化

周文梁，屈林影，史峰，鄧連波

(中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長沙 410075)

在我國高速鐵路網(wǎng)絡(luò)化運(yùn)營背景下，構(gòu)建高速鐵路網(wǎng)絡(luò)化運(yùn)輸組織優(yōu)化方法迫切需要，特別是網(wǎng)絡(luò)列車運(yùn)行圖的鋪劃，由于需要在叉點(diǎn)站銜接多個線路方向，使本來難度很大的列車運(yùn)行圖鋪劃方法變得更為復(fù)雜。目前，針對網(wǎng)絡(luò)列車運(yùn)行圖鋪劃方法的研究仍然較少。馬建軍等[1]將鐵路路網(wǎng)表示為分層節(jié)點(diǎn)圖，將列車運(yùn)行圖表示為時間序列，基于離散事件方法計算列車到發(fā)時間；彭其淵等[2?3]通過不斷向子路網(wǎng)增加區(qū)段，使運(yùn)行圖鋪劃范圍不斷擴(kuò)大，最終獲得整個路網(wǎng)運(yùn)行圖；同時通過在列車運(yùn)行圖時空局域內(nèi)設(shè)置和滾動窗口，每次優(yōu)化窗口中運(yùn)行線來動態(tài)地完成網(wǎng)絡(luò)運(yùn)行圖鋪劃；Dorfman等[4]將各種列車優(yōu)先策略融合到列車離散事件仿真框架中來解決路網(wǎng)列車運(yùn)行圖鋪劃問題；王濤等[5]采用分層多級優(yōu)化分枝定界算法，針對列車調(diào)度問題給出了一種基于替代圖的列車運(yùn)行圖修正及優(yōu)化方法；Eva等[6]進(jìn)一步引用了ANLS算法對旅客等待時間進(jìn)行優(yōu)化；文超等[7]給出了在運(yùn)行圖鋪化過程中單個列車化解沖突的方法；白紫熙等[8]在給定列車車站到發(fā)順序的基礎(chǔ)上，進(jìn)一步采用原始對偶算法優(yōu)化列車車站到發(fā)時間；史峰[9]基于分層鋪化的思想確定速度優(yōu)先級，給出相同徑路的運(yùn)行圖編制；而周文梁等[10]通過設(shè)計高鐵線路列車運(yùn)行圖的有向圖表示形式，以此結(jié)合文獻(xiàn)[8]和[9]方法優(yōu)化列車到發(fā)作業(yè)順序以及到發(fā)時刻；Kaspi等[11]采用交叉熵算法對列車運(yùn)行圖和開行方案進(jìn)行綜合優(yōu)化，而ZHOU等[12]基于拉格朗日松弛分解方法協(xié)同優(yōu)化列車車站徑路與車站到發(fā)時刻。本文在文獻(xiàn)[10]研究方法的基礎(chǔ)上，通過在車站對各銜接區(qū)間的接發(fā)列車作業(yè)進(jìn)行組合約束，以列車旅行時間最少為目標(biāo)，建立高鐵網(wǎng)絡(luò)運(yùn)行圖優(yōu)化模型；通過擴(kuò)展高鐵網(wǎng)絡(luò)松弛運(yùn)行圖的有向圖表示形式，建立網(wǎng)絡(luò)松弛運(yùn)行圖的定序優(yōu)化線性規(guī)劃模型，在網(wǎng)絡(luò)松弛運(yùn)行圖中以平移作業(yè)組、交換作業(yè)順序、變更停站方案等方法優(yōu)化網(wǎng)絡(luò)運(yùn)行圖。

1　網(wǎng)絡(luò)運(yùn)行圖優(yōu)化模型與求解思想

高速鐵路網(wǎng)絡(luò)由客運(yùn)站和各相鄰客運(yùn)站間的線路區(qū)間組成，記為N=(S,E)，其中S為客運(yùn)站集，為區(qū)間集。每個客運(yùn)站至少銜接一個區(qū)間(或方向)，車站 sk銜接的區(qū)間集為

描述網(wǎng)絡(luò)運(yùn)行圖最關(guān)鍵的環(huán)節(jié)在于描述作業(yè)間隔時間時必須考慮作業(yè)的銜接區(qū)間。對于車站sk的2個銜接區(qū)間，不同列車分別經(jīng)過區(qū)間e1和e2并同在車站sk作業(yè)時，作業(yè)之間需要滿足如下時間間隔：

以上各項作業(yè)時間間隔查定值與車站布局和列車過站徑路等因素有關(guān)。一些作業(yè)對之間因為有足夠的安全保障，可以不作時間間隔約束。

設(shè)高速鐵路網(wǎng)絡(luò) N = ( S,E)上開行旅客列車集為?。對于列車i∈?，記oi為始發(fā)站，di為終到站，分別表示其經(jīng)由的區(qū)間序列與車站序列，為始發(fā)時間域分別為列車i在區(qū)的啟動附加時間、純運(yùn)行時間和停止附加時間；列車i在車站的最少停站時間；列車i在車站的停站標(biāo)志，若列車i在車站sk停車，則列車i從車站sk經(jīng)區(qū)間開往車站的出發(fā)、到達(dá)作業(yè)時刻分別記為另記區(qū)間 e的維修天窗為

以列車旅行時間最少為優(yōu)化目標(biāo)，結(jié)合線路運(yùn)行圖優(yōu)化模型[10]和網(wǎng)絡(luò)運(yùn)行圖中作業(yè)間隔的銜接區(qū)間屬性，建立高速鐵路網(wǎng)絡(luò)列車運(yùn)行圖優(yōu)化模型如下：

以上模型中目標(biāo)函數(shù)式(1)為最小化列車旅行時間，其中符號Θ表示兩整數(shù)關(guān)于運(yùn)營周期T的模運(yùn)算；式(2)~(5)分別為不同時出發(fā)時間間隔、不同時到達(dá)時間間隔、不同時發(fā)到時間間隔以及不同時到發(fā)時間間隔約束，式(6)和(7)分別為列車區(qū)間運(yùn)行時間、車站停留時間約束，式(8)為列車始發(fā)時間約束，式(9)為區(qū)間天窗時間約束，式(10)與(11)為變量取值約束。

模型式(1)~(11)是一個大規(guī)模優(yōu)化問題，本文借助于文獻(xiàn)[10]求解思想設(shè)計求解算法。首先在忽略各列車車站作業(yè)間隔約束關(guān)系下，根據(jù)列車始發(fā)時間分布和列車區(qū)間運(yùn)行時間等確定初始網(wǎng)絡(luò)松弛運(yùn)行圖，然后在保持其它作業(yè)之間的順序關(guān)系的條件下，按一定沖突選擇策略逐步選擇化解列車作業(yè)沖突，直至所有沖突全部化解為止，獲得完整的高鐵網(wǎng)絡(luò)運(yùn)行圖。

2　網(wǎng)絡(luò)松弛運(yùn)行圖的有向圖表示形式

線路松弛運(yùn)行圖的多平行四邊形表示形式的構(gòu)造可通過將一端邊界上沖突相關(guān)的運(yùn)行線在另一端添加該運(yùn)行線的副本(與原運(yùn)行線段相差一個時間周期T的運(yùn)行線段)以準(zhǔn)確反映列車作業(yè)之間的位置關(guān)系。對于網(wǎng)絡(luò)松弛運(yùn)行圖，需通過判斷增加必要的運(yùn)行線副本來保持叉點(diǎn)站各銜接方向運(yùn)行線的位置關(guān)系，形成網(wǎng)絡(luò)松弛運(yùn)行圖的擴(kuò)展多平行四邊形。銜接4個方向的網(wǎng)絡(luò)松弛運(yùn)行圖的多平行四邊形如圖 1 所示，其中，BDD′B′和 CEE′C′分別表示相交在車站中心線AA′的2個平面，4個銜接方向的運(yùn)行圖鋪劃在這4個半平面上，其中，列車1與2經(jīng)由站均為車站E，A與C，而列車3與4經(jīng)由站分別為車站D，A與B。此外，以虛線表示的列車1與3運(yùn)行線作為平行四邊形表示形式的右邊界，與其對應(yīng)的左邊界構(gòu)成一個周期，如1 d1 440 min。

圖1　網(wǎng)絡(luò)松弛運(yùn)行圖的多平行四邊形表示形式Fig. 1　Multi-parallelogram of relaxed train diagram on rail network

記各列車在車站的到發(fā)作業(yè)為點(diǎn)集Vz，各列車的始發(fā)時間域上下限時間為點(diǎn)集Vs，各區(qū)間兩端車站相應(yīng)的天窗起始、終止時間為點(diǎn)集Vw，獲得點(diǎn)集V=Vz∪Vs∪Vw；將車站所有存在作業(yè)間隔時間限制的相鄰定序列車作業(yè)間(沖突運(yùn)行線段的相關(guān)作業(yè)除外)沿時間增加方向作弧得相鄰作業(yè)弧集 Ap，將各區(qū)間運(yùn)行線段兩端作業(yè)沿時間增加方向作弧的區(qū)間運(yùn)行弧集Ay，將各列車在同一車站的到達(dá)作業(yè)至發(fā)車作業(yè)間作弧得停站弧集At，將各列車始發(fā)作業(yè)至其始發(fā)時間域上限時間、列車始發(fā)時間域下限時間至其始發(fā)作業(yè)間作弧得始發(fā)時間域弧集As，將列車運(yùn)行圖中各區(qū)間兩端車站相應(yīng)的天窗時間與其緊前或緊后列車作業(yè)間沿時間增加方向作弧得天窗弧集Aw，將一段邊界線上列車作業(yè)與另一端邊界線上對應(yīng)作業(yè)沿時間增加方向作弧得周期約束弧集Az，獲得弧集，由此便得網(wǎng)絡(luò)松弛運(yùn)行圖的有向圖表示形式 G = ( V,A)。圖 1中多平行四邊形運(yùn)行圖對應(yīng)的有向圖如圖 2所示(圖中包含區(qū)間運(yùn)行弧、停站弧、作業(yè)時間間隔弧及周期約束弧)，其中，區(qū)間弧對應(yīng)于列車區(qū)間運(yùn)行，如區(qū)間弧(1,2)與(3,4)分別對應(yīng)于列車1在兩區(qū)間的運(yùn)行；停站弧對應(yīng)于列車車站停車過程，如停站弧(2,3)與(6,7)分別對應(yīng)于列車1與3在車站A的停車過程，若列車不停車，則將其權(quán)值設(shè)為0即可；作業(yè)間隔弧對應(yīng)于列車作業(yè)之間的間隔，如間隔弧(1,9)與(2,6)分別對應(yīng)于同徑路列車1和2進(jìn)入?yún)^(qū)間間隔與不同徑路列車1和3離開區(qū)間間隔；而周期弧為邊界約束，如周期弧(1,17)保證了同一列車在相鄰周期的時間間隔正好為周期長度。值得說明的是，在網(wǎng)絡(luò)狀態(tài)下不同運(yùn)行徑路列車在叉點(diǎn)站存在作業(yè)時間間隔要求，如圖2中間隔弧(2,6)與(3,7)描述的正是列車1與3從不同區(qū)間進(jìn)入車站A的時間間隔要求，以及它們離開車站A進(jìn)入不同區(qū)間的時間間隔要求。

圖2　網(wǎng)絡(luò)松弛運(yùn)行圖的有向圖表示形式Fig. 2　Digraph of relaxed train diagram on rail network

將列車車站作業(yè)時間、列車始發(fā)時間域上下限值以及天窗起始、終止時間作為圖G中相應(yīng)點(diǎn)v上的加權(quán) t(v)，同時將每條弧(u,v)尾節(jié)點(diǎn)加權(quán)與首節(jié)點(diǎn)加權(quán)的差值定義為該弧上的加權(quán)w(u,v)=t(v)?t(u)，確定所有有向弧(u,v)上加權(quán)的下限w0(u,v)，便得到網(wǎng)絡(luò)松弛列車運(yùn)行圖的加權(quán)有向圖G。

3　網(wǎng)絡(luò)松弛運(yùn)行圖的定序優(yōu)化線性規(guī)劃模型

網(wǎng)絡(luò)松弛運(yùn)行圖的定序優(yōu)化指在忽略所有沖突的相關(guān)作業(yè)之間的順序關(guān)系、保持與沖突外不相關(guān)作業(yè)之間的順序關(guān)系的條件下，使得列車旅行時間最小化。記Uk為網(wǎng)絡(luò)松弛運(yùn)行圖的擴(kuò)展有向圖中左端邊界線上車站Ssk∈的邊界作業(yè)集。對于xik∈ Uk或 yik∈ Uk，記 xi′k或 yi′k為其相應(yīng)右端邊界線上作業(yè)，根據(jù)各類有向弧加權(quán)函數(shù)約束，建立網(wǎng)絡(luò)松弛運(yùn)行圖的定序優(yōu)化線性規(guī)劃模型如下：

其中：約束式(28)表示列車停站變量與列車車站到發(fā)時刻之間一致性約束，即當(dāng)列車在車站停留，即=1時，列車停留時間至少大于1 min；否則列車停留時間為0。

4　基于定序優(yōu)化的網(wǎng)絡(luò)運(yùn)行圖鋪劃方法

基于定序優(yōu)化的網(wǎng)絡(luò)運(yùn)行圖鋪劃方法是在鋪劃松弛網(wǎng)絡(luò)運(yùn)行圖的基礎(chǔ)上，每次選擇一定數(shù)量沖突進(jìn)行化解；在化解沖突時，先確定其相關(guān)作業(yè)順序，然后構(gòu)造當(dāng)前松弛運(yùn)行圖的有向圖，在此有向圖中，保持非沖突作業(yè)之間的關(guān)系，利用作業(yè)平移的方法化解沖突，如此反復(fù)，直至獲得不存在沖突的網(wǎng)絡(luò)運(yùn)行圖。若平移作業(yè)仍無法完全滿足最小作業(yè)時間間隔，可進(jìn)一步結(jié)合交換列車作業(yè)順序、變更停站方案或擴(kuò)大列車始發(fā)時間域等優(yōu)化手段。

4.1　化解沖突及化解方案的選擇

根據(jù)沖突發(fā)生位置將松弛運(yùn)行圖中沖突分為區(qū)間沖突和車站沖突。對于區(qū)間沖突，可通過讓速度等級高的列車在前方或后方車站越行速度等級低列車而化解；對于車站沖突，只需讓速度等級高的列車在該車站越行速度等級低列車化解。故沖突化解均需使得沖突運(yùn)行線平移一定時間距離而滿足最小作業(yè)間隔時間要求。通常沖突化解平移時間之和越少，所帶動平移的運(yùn)行線數(shù)量越少，這既對運(yùn)行圖質(zhì)量影響較小，也容易實(shí)現(xiàn)沖突化解。因此，對于區(qū)間沖突應(yīng)優(yōu)先選擇化解平移時間之和最少越行站進(jìn)行化解。

每次化解沖突的選擇，可簡單從松弛運(yùn)行圖中隨機(jī)選擇一定數(shù)量沖突，或者根據(jù)沖突化解時平移時間以概率方式選擇一定數(shù)量沖突，這兩種方法易操作，但運(yùn)行圖優(yōu)化質(zhì)量不明顯。為了提高運(yùn)行圖優(yōu)化質(zhì)量，這里設(shè)計兩種沖突選擇原則：沖突化解平移時間總和最小原則和沖突化解平移時間差距最大原則。

1) 平移時間總和最小原則

采用平移時間總和最小原則選擇數(shù)量為λ的化解沖突集C滿足：

2) 平移時間差距最大原則采用平移時間差距最大原則選擇數(shù)量為λ的化解沖突集C滿足：

4.2　松弛運(yùn)行圖的定序優(yōu)化方法

根據(jù)當(dāng)前化解沖突及其化解方案確定當(dāng)前所有化解沖突作業(yè)之間的時間先后順序后，進(jìn)而基于有向圖調(diào)整其作業(yè)時間使得其滿足最小作業(yè)時間間隔要求?？刹捎玫姆椒ㄖ饕衅揭屏熊囎鳂I(yè)、交換列車作業(yè)順序、變更停站方案和調(diào)整列車始發(fā)時間域等關(guān)鍵技術(shù)。文獻(xiàn)[10]詳細(xì)介紹了區(qū)段列車運(yùn)行圖鋪劃過程中這些關(guān)鍵技術(shù)的實(shí)現(xiàn)方法。由于網(wǎng)絡(luò)運(yùn)行圖鋪劃與區(qū)段運(yùn)行圖鋪劃主要區(qū)別在于同時考慮了叉點(diǎn)站對各銜接區(qū)間的接發(fā)(或通過)作業(yè)之間的時間間隔約束，而有向圖構(gòu)造已經(jīng)完全反映了作業(yè)之間的先后關(guān)系，因此，文獻(xiàn)[10]中關(guān)于這些關(guān)鍵技術(shù)的實(shí)現(xiàn)方法同樣適應(yīng)于網(wǎng)絡(luò)運(yùn)行圖鋪劃，因篇幅有限，不再敘述。只是在化解沖突作業(yè)平移時，不僅帶動一條線路上相關(guān)作業(yè)平移，也帶動所有銜接線路上的相關(guān)作業(yè)一起平移。

5　網(wǎng)絡(luò)運(yùn)行圖鋪劃算例

由13個客運(yùn)站和20個復(fù)線線路區(qū)間組成的高鐵網(wǎng)絡(luò)如圖3所示(圖中標(biāo)記了以km為單位的路段里程)。在該網(wǎng)絡(luò)上鋪劃兩種速度等級列車，其中高速度等級列車191對、低速度等級列車158對。高、低速等級列車在各區(qū)間的啟停附加時分均設(shè)為 1分，在各區(qū)間的技術(shù)速度分別為 320 km/h和 250 km/h。在此基礎(chǔ)上，結(jié)合區(qū)間里程便可計算出2種速度列車在區(qū)間的純運(yùn)行時間，進(jìn)一步結(jié)合列車區(qū)間前后車站停車情況與啟停附加時分便可獲得其區(qū)間運(yùn)行時分。車站不同銜接方向列車的不同時出發(fā)、不同時到達(dá)、不同時發(fā)到及不同時到發(fā)時間間隔為3 min。

圖3　高速鐵路網(wǎng)絡(luò)結(jié)構(gòu)示意圖Fig. 3　Structure schematic of an example rail network

利用基于定序優(yōu)化的網(wǎng)絡(luò)運(yùn)行圖鋪劃方法求解網(wǎng)絡(luò)上的列車運(yùn)行圖，下面僅以車站S6銜接的4個區(qū)間S4-S6-S5,S3-S6-S8在12:00-18:00時間段內(nèi)的運(yùn)行圖展示如圖4和圖5所示。圖中很容易看出列車先后通過S4-S6和S6-S5，S3-S6和S6-S8的銜接關(guān)系，篇幅所限，列車先后通過其它線路的銜接關(guān)系并未畫出來，讀者可以通過組合這兩個圖看出它們的銜接關(guān)系，如列車Z147先通過區(qū)間S4-S6，再通過區(qū)間S6-S8。

1) 沖突選擇策略對算法優(yōu)化效率與質(zhì)量比較

首先隨機(jī)產(chǎn)生165個運(yùn)行圖鋪劃實(shí)例，分別采用隨機(jī)策略、最小平移時間策略和最大平移差距策略選擇化解沖突優(yōu)化列車運(yùn)行圖，確定算法計算時間與其列車總旅行時間，統(tǒng)計各策略使得列車總旅行時間、計算時間以及兩者為3種策略中最小值的次數(shù)以及所占比例如表1所示。由于各沖突選擇策略下計算的列車總旅行時間或計算時間可能相等，所以表中各策略次數(shù)之和大于鋪劃實(shí)例數(shù) 165，百分率之和也不等于1。

圖4　區(qū)段S4-S6-S5的列車運(yùn)行圖Fig. 4　Train diagram of section S4-S6-S5

圖5　區(qū)段S3-S6-S8的列車運(yùn)行圖Fig. 5　Train diagram of section S3-S6-S8

表1　在運(yùn)行實(shí)例數(shù)165條件下3種沖突選擇策略效果比較Table 1　Compare of three conflict-selection strategies used for 165 instances

由表1數(shù)據(jù)可知：3種沖突選擇策略中，最小平移時間策略使列車總旅行時間最小的次數(shù)達(dá)到84次，占到實(shí)例總數(shù)的51%；而計算時間最小的次數(shù)達(dá)到103次，占到實(shí)例總數(shù)的62%，而使得兩者均最小的次數(shù)達(dá)到63次，占到實(shí)例總數(shù)的38%。由此可見，相比隨機(jī)策略和最大平移差距策略，采用最小平移時間策略選擇化解沖突能夠以最大概率花費(fèi)較較少的計算時間而獲得列車總旅行時間較小的列車運(yùn)行圖。

圖6　計算時間隨一次同時化解沖突數(shù)的變化關(guān)系圖Fig. 6　Change relation of computing time with the number of disposed conflicts

圖7　列車平均延誤時間隨一次同時化解沖突數(shù)的變化關(guān)系圖Fig. 7　Change relation of average train delay time with the number of disposed conflicts

2) 一次同時化解沖突數(shù)量對算法優(yōu)化效率與質(zhì)量的影響

分別采用隨機(jī)策略、最小平移時間策略和最大平移差距策略，依次選擇一次同時化解沖突數(shù)為 1至 50優(yōu)化網(wǎng)絡(luò)運(yùn)行圖，確定各沖突選擇策略下計算時間與其列車平均延誤時間(列車旅行時間與技術(shù)時間之差)隨一次同時選擇化解沖突數(shù)的變化曲線關(guān)系分別如圖6和圖7所示。

由圖5和圖6可知：每次選擇化解沖突的數(shù)量對運(yùn)行圖鋪劃時間和列車平均延誤時間的影響不是很明顯。這是因為作業(yè)沖突化解過程中，沖突作業(yè)之間的定序工作量很少，而大部分工作量是調(diào)整兩作業(yè)間隔時間使之滿足最小作業(yè)間隔時間，所以若將多個沖突進(jìn)行一次定序，所節(jié)約的計算時間相比調(diào)整列車作業(yè)間隔所花的時間是非常小的。

6　結(jié)論

1) 建立了以列車旅行時間最少為目標(biāo)的網(wǎng)絡(luò)運(yùn)行圖優(yōu)化模型，同時考慮了車站上各銜接方向列車到發(fā)或通過作業(yè)之間約束關(guān)系，確保了列車運(yùn)行圖的整體優(yōu)化質(zhì)量。

2) 設(shè)計基于定序優(yōu)化的網(wǎng)絡(luò)列車運(yùn)行圖鋪劃方法，在鋪劃初始網(wǎng)絡(luò)松弛運(yùn)行圖的基礎(chǔ)上，通過最小平移時間策略和最大平移差距策略等各種沖突化解策略能夠有效地化解網(wǎng)絡(luò)松弛運(yùn)行圖中沖突，獲得完整的網(wǎng)絡(luò)運(yùn)行圖。

3) 算例分析表明，定序優(yōu)化沖突化解策略的方法能提高運(yùn)行圖鋪化速率并獲得較優(yōu)的列車運(yùn)行圖。而如何進(jìn)一步將車站到發(fā)線、進(jìn)路等約束考慮到模型和算法中，是有待擴(kuò)展的重要研究內(nèi)容。

參考文獻(xiàn)：

[1] 馬建軍, 周磊山, 胡思繼. 計算機(jī)編制網(wǎng)狀線路列車運(yùn)行圖系統(tǒng)研究[J]. 鐵道學(xué)報, 2000, 22(1): 7?11.MA Jianjun, ZHOU Leishan, HU Siji. Research on train working diagram system of railway netted lines worked out with computer[J]. Journal of the China Railway Society, 2000, 22(1): 7?11.

[2] 彭其淵, 朱松年. 網(wǎng)絡(luò)列車運(yùn)行圖的數(shù)學(xué)模型及算法研究[J]. 鐵道學(xué)報, 2001, 23(1): 1?8.PENG Qiyuan, ZHU Songnian. Study on a general optimization model and its solution for railway network train diagram[J]. Journal of the China Railway Society,2001, 23(1): 1?8.

[3] 彭其淵, 王寶杰, 周黨瑞. 基于實(shí)用的一種網(wǎng)絡(luò)列車運(yùn)行圖計算方法[J]. 西南交通大學(xué)學(xué)報, 1999, 34(5):588?593.PENG Qiyuan, WANG Baojie, ZHOU Dangrui. A practical algorithm for making train diagram of railway network[J]. Journal of Southwest Jiaotong University,1999, 34(5): 588?593.

[4] Dorfman M J, Medanic J. Scheduling trains on a railway network using a discrete event model of railway traffic[J].Transportation Research Part B, 2004(38): 81?98.

[5] 王濤, 張琦, 趙宏濤, 等. 基于替代圖的列車運(yùn)行調(diào)整計劃編制及優(yōu)化方法[J]. 中國鐵道科學(xué), 2013, 34(5):126?133.WANG Tao, ZHANG Qi, ZHAO Hongtao. A method for generation and optimization of train operation adjustment plan based on alternative graph[J]. China Railway Science, 2013, 34(5): 126?133.

[6] Eva Barrena, David Canca. Single-line rail rapid transit timetabling under dynamic passenger demand[J].Transportation Research Part B, 2014(70): 134?150.

[7] 文超, 彭其淵, 陳芋宏. 高速鐵路單個列車運(yùn)行沖突消解研究[J]. 鐵路技術(shù)與工程, 2013, 13(10): 2741?2747.WEN Chao, PENG Qiyuan, CHEN Yuhong. Train operation adjustment based on conflict resolution for high-speed rail[J]. Science Technology and Engineering,2013, 13(10): 2741?2747.

[8] 白紫熙, 邵靜靜. 相同徑路的高速列車運(yùn)行圖編制方法[J]. 中國鐵道科學(xué), 2015, 36(6): 135?140.BAI Zixi, SHAO Jingjing. Drawing method for working diagram of high speed train with same path[J]. China Railway Science, 2015, 36(6): 135?140.

[9] 史峰. 定序單線列車運(yùn)行圖的原始－對偶算法[J]. 鐵道學(xué)報, 1996, 18(1): 8?20.SHI Feng. A primal-dual algorithm for making train diagram fixed order on single-track rail lines [J]. Journal of the China Railway Society, 1996, 18(1): 8?20.

[10] 周文梁, 史峰, 陳彥. 基于定序優(yōu)化的客運(yùn)專線列車運(yùn)行圖鋪劃方法[J]. 鐵道學(xué)報, 2010, 32(1): 1?7.ZHOU Wenliang, SHI Feng, CHEN Yan. A method for drawing train diagram of dedicated passenger line based on fixed order optimization[J]. Journal of The China Railway Society, 2010, 32(1): 1?7.

[11] Kaspi M, Raviv T. Service-oriented line planning and timetabling for passenger trains[J]. Transport Science,2013, 47(3): 295?311.

[12] ZHOU Wenliang, TENG Hualiang. Simultaneous passenger train routing and timetabling using an efficient train-based Lagrangian relaxation decomposition[J].Transportation Research Part B, 2016(11): 409?439.