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

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

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

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

以上各項(xiàng)作業(yè)時(shí)間間隔查定值與車(chē)站布局和列車(chē)過(guò)站徑路等因素有關(guān)。一些作業(yè)對(duì)之間因?yàn)橛凶銐虻陌踩Ｕ?，可以不作時(shí)間間隔約束。

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

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

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

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

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

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

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

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

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

將列車(chē)車(chē)站作業(yè)時(shí)間、列車(chē)始發(fā)時(shí)間域上下限值以及天窗起始、終止時(shí)間作為圖G中相應(yīng)點(diǎn)v上的加權(quán) t(v)，同時(shí)將每條弧(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ò)松弛列車(chē)運(yùn)行圖的加權(quán)有向圖G。

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

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

其中：約束式(28)表示列車(chē)停站變量與列車(chē)車(chē)站到發(fā)時(shí)刻之間一致性約束，即當(dāng)列車(chē)在車(chē)站停留，即=1時(shí)，列車(chē)停留時(shí)間至少大于1 min；否則列車(chē)停留時(shí)間為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)行化解；在化解沖突時(shí)，先確定其相關(guān)作業(yè)順序，然后構(gòu)造當(dāng)前松弛運(yùn)行圖的有向圖，在此有向圖中，保持非沖突作業(yè)之間的關(guān)系，利用作業(yè)平移的方法化解沖突，如此反復(fù)，直至獲得不存在沖突的網(wǎng)絡(luò)運(yùn)行圖。若平移作業(yè)仍無(wú)法完全滿(mǎn)足最小作業(yè)時(shí)間間隔，可進(jìn)一步結(jié)合交換列車(chē)作業(yè)順序、變更停站方案或擴(kuò)大列車(chē)始發(fā)時(shí)間域等優(yōu)化手段。

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

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

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

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

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

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

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

根據(jù)當(dāng)前化解沖突及其化解方案確定當(dāng)前所有化解沖突作業(yè)之間的時(shí)間先后順序后，進(jìn)而基于有向圖調(diào)整其作業(yè)時(shí)間使得其滿(mǎn)足最小作業(yè)時(shí)間間隔要求。可采用的方法主要有平移列車(chē)作業(yè)、交換列車(chē)作業(yè)順序、變更停站方案和調(diào)整列車(chē)始發(fā)時(shí)間域等關(guān)鍵技術(shù)。文獻(xiàn)[10]詳細(xì)介紹了區(qū)段列車(chē)運(yùn)行圖鋪劃過(guò)程中這些關(guān)鍵技術(shù)的實(shí)現(xiàn)方法。由于網(wǎng)絡(luò)運(yùn)行圖鋪劃與區(qū)段運(yùn)行圖鋪劃主要區(qū)別在于同時(shí)考慮了叉點(diǎn)站對(duì)各銜接區(qū)間的接發(fā)(或通過(guò))作業(yè)之間的時(shí)間間隔約束，而有向圖構(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è)平移時(shí)，不僅帶動(dòng)一條線(xiàn)路上相關(guān)作業(yè)平移，也帶動(dòng)所有銜接線(xiàn)路上的相關(guān)作業(yè)一起平移。

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

由13個(gè)客運(yùn)站和20個(gè)復(fù)線(xiàn)線(xiàn)路區(qū)間組成的高鐵網(wǎng)絡(luò)如圖3所示(圖中標(biāo)記了以km為單位的路段里程)。在該網(wǎng)絡(luò)上鋪劃兩種速度等級(jí)列車(chē)，其中高速度等級(jí)列車(chē)191對(duì)、低速度等級(jí)列車(chē)158對(duì)。高、低速等級(jí)列車(chē)在各區(qū)間的啟停附加時(shí)分均設(shè)為 1分，在各區(qū)間的技術(shù)速度分別為 320 km/h和 250 km/h。在此基礎(chǔ)上，結(jié)合區(qū)間里程便可計(jì)算出2種速度列車(chē)在區(qū)間的純運(yùn)行時(shí)間，進(jìn)一步結(jié)合列車(chē)區(qū)間前后車(chē)站停車(chē)情況與啟停附加時(shí)分便可獲得其區(qū)間運(yùn)行時(shí)分。車(chē)站不同銜接方向列車(chē)的不同時(shí)出發(fā)、不同時(shí)到達(dá)、不同時(shí)發(fā)到及不同時(shí)到發(fā)時(shí)間間隔為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ò)上的列車(chē)運(yùn)行圖，下面僅以車(chē)站S6銜接的4個(gè)區(qū)間S4-S6-S5,S3-S6-S8在12:00-18:00時(shí)間段內(nèi)的運(yùn)行圖展示如圖4和圖5所示。圖中很容易看出列車(chē)先后通過(guò)S4-S6和S6-S5，S3-S6和S6-S8的銜接關(guān)系，篇幅所限，列車(chē)先后通過(guò)其它線(xiàn)路的銜接關(guān)系并未畫(huà)出來(lái)，讀者可以通過(guò)組合這兩個(gè)圖看出它們的銜接關(guān)系，如列車(chē)Z147先通過(guò)區(qū)間S4-S6，再通過(guò)區(qū)間S6-S8。

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

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

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

圖5　區(qū)段S3-S6-S8的列車(chē)運(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í)間策略使列車(chē)總旅行時(shí)間最小的次數(shù)達(dá)到84次，占到實(shí)例總數(shù)的51%；而計(jì)算時(shí)間最小的次數(shù)達(dá)到103次，占到實(shí)例總數(shù)的62%，而使得兩者均最小的次數(shù)達(dá)到63次，占到實(shí)例總數(shù)的38%。由此可見(jiàn)，相比隨機(jī)策略和最大平移差距策略，采用最小平移時(shí)間策略選擇化解沖突能夠以最大概率花費(fèi)較較少的計(jì)算時(shí)間而獲得列車(chē)總旅行時(shí)間較小的列車(chē)運(yùn)行圖。

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

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

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

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

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

6　結(jié)論

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

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

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

參考文獻(xiàn)：

[1] 馬建軍, 周磊山, 胡思繼. 計(jì)算機(jī)編制網(wǎng)狀線(xiàn)路列車(chē)運(yùn)行圖系統(tǒng)研究[J]. 鐵道學(xué)報(bào), 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ò)列車(chē)運(yùn)行圖的數(shù)學(xué)模型及算法研究[J]. 鐵道學(xué)報(bào), 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ò)列車(chē)運(yùn)行圖計(jì)算方法[J]. 西南交通大學(xué)學(xué)報(bào), 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] 王濤, 張琦, 趙宏濤, 等. 基于替代圖的列車(chē)運(yùn)行調(diào)整計(jì)劃編制及優(yōu)化方法[J]. 中國(guó)鐵道科學(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] 文超, 彭其淵, 陳芋宏. 高速鐵路單個(gè)列車(chē)運(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] 白紫熙, 邵靜靜. 相同徑路的高速列車(chē)運(yùn)行圖編制方法[J]. 中國(guó)鐵道科學(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] 史峰. 定序單線(xiàn)列車(chē)運(yùn)行圖的原始－對(duì)偶算法[J]. 鐵道學(xué)報(bào), 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)專(zhuān)線(xiàn)列車(chē)運(yùn)行圖鋪劃方法[J]. 鐵道學(xué)報(bào), 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.