郭根材，聶 磊，佟 璐，賀振歡

(1.北京交通大學(xué) 交通運輸學(xué)院，北京 100044；2.中國鐵道科學(xué)研究院 電子計算技術(shù)研究所，北京 100081)

為提高換乘客流服務(wù)質(zhì)量周期性列車運行圖模型[1-5]明確規(guī)定了列車接續(xù)約束。國內(nèi)一些學(xué)者對周期性列車運行圖的研究以單條線路為主[6-10]，列車接續(xù)約束設(shè)置簡單或被忽略，研究側(cè)重于模型求解算法、計算機編制周期性列車運行圖等方面。歐洲鐵路經(jīng)過多年運營，已經(jīng)形成固定的列車接續(xù)關(guān)系，編制周期性列車運行圖的列車接續(xù)約束是明確的[11，12]；而我國高速鐵路快速成網(wǎng)，列車運行圖隨新線的開通不斷調(diào)整，尚未形成明確的列車接續(xù)關(guān)系。編制周期性列車運行圖時，列車接續(xù)可能與運行圖的安全間隔約束矛盾，列車接續(xù)需要根據(jù)實際情況調(diào)整，根據(jù)周期性列車開行方案生成的列車接續(xù)[14]仍為備選列車接續(xù)。

編圖過程中，列車開行方案、備選列車接續(xù)、列車運行圖三者相互制約，需要不斷根據(jù)運行線間的沖突調(diào)整列車開行方案、列車接續(xù)方案，以保證運營階段列車安全運行。本文側(cè)重研究周期性列車開行方案給定時基于備選列車接續(xù)的周期性列車運行圖編制模型，以提高周期性列車運行圖在我國高速鐵路的適用性。介紹歐洲鐵路使用的周期性列車運行圖編制模型(Cycle Periodicity Formulation，CPF模型)；針對固定列車接續(xù)，研究備選列車接續(xù)條件下CPF模型求解周期性列車運行圖存在的問題，提出基于備選列車接續(xù)的周期性列車運行圖編制流程；給出新流程中分類整數(shù)圈基的構(gòu)造方法，改進CPF模型的整數(shù)圈基約束條件以避免CPF模型重構(gòu)；進一步調(diào)整CPF模型的決策變量、目標(biāo)函數(shù)與約束條件，建立適合備選列車接續(xù)的周期性列車運行圖編制模型PCCPF模型；以我國高速鐵路網(wǎng)為例，運用Cplex12.3對模型求解，進行了案例驗證。

1 CPF模型

運用CPF模型編制周期性列車運行圖的核心思想是將列車事件(到達、出發(fā)、通過)的發(fā)生時刻看作周期勢，列車事件的發(fā)生間隔看作周期壓[2，3]，利用列車事件間的約束關(guān)系構(gòu)建表示列車到發(fā)間隔約束的有向圖(稱為約束圖)，進而根據(jù)約束圖中圈的周期性質(zhì)構(gòu)建周期性列車運行圖編制模型。約束圖G=(N，A)的頂點N代表列車事件，約束圖的邊A代表列車事件間的約束關(guān)系，如列車發(fā)發(fā)間隔約束、到發(fā)間隔約束等。約束圖的每條邊a∈A存在一個取值范圍la≤xa≤ua表示列車事件之間應(yīng)滿足的約束條件，xa為邊a的周期壓，la為最小發(fā)生間隔，ua為最大發(fā)生間隔。約束圖的邊A由運行邊Ar、停站邊Ad、安全邊As、接續(xù)邊Ac等組成。圖1為區(qū)段AD之間兩列列車構(gòu)成的約束圖，圖中每條邊上的數(shù)值區(qū)間[la，ua]表示列車事件之間應(yīng)滿足的約束條件，如圖中點1與點7之間的弧表示兩列車在A站的出發(fā)間隔約束，弧上數(shù)值區(qū)間[4，56]表示兩列車在A站的出發(fā)間隔應(yīng)在4～56 min之內(nèi)，以滿足4 min安全追蹤間隔要求，約束圖的詳細(xì)介紹可參考文獻[13]。

圖1 兩列列車的約束圖

( 1 )

aC≤qC≤bC?C∈G

( 2 )

( 3 )

( 4 )

文獻[3]進一步證明，如果約束圖G的整數(shù)圈基滿足圈周期約束( 1 )，則約束圖G中所有的圈都滿足圈周期約束，CPF模型中的圈周期約束( 1 )可以簡化為式( 5 )。整數(shù)圈基B是指圖G線性圈空間V的r個線性無關(guān)的圈向量，如果線性圈空間V中的每一個圈向量γG都可以由整數(shù)線性表示，則稱為圖G的一個整數(shù)圈基。如圖1中的虛線圈為約束圖的一個整數(shù)圈基。本文將圈基中的圈稱為基圈。

( 5 )

經(jīng)過多年的發(fā)展，CPF模型已經(jīng)運用于荷蘭鐵路[3]和柏林地鐵[4]的周期性列車運行圖編制中，CPF模型的詳細(xì)介紹可參考文獻[3]和文獻[7]。CPF模型結(jié)構(gòu)如下

( 6 )

s.t.

?C∈B

( 7 )

la≤xa≤ua?a∈A

( 8 )

aC≤qC≤bC?C∈B

( 9 )

xa∈Z?a∈A

(10)

qC∈Z?C∈B

(11)

2 基于備選列車接續(xù)周期性列車運行圖編制流程

相對固定列車接續(xù)，備選列車接續(xù)條件下編制周期性列車運行圖需要根據(jù)運行圖編制的實際情況不斷迭代調(diào)整列車接續(xù)，而調(diào)整列車接續(xù)時，CPF模型會產(chǎn)生以下問題：

(1)描述CPF模型的約束圖隨列車接續(xù)的調(diào)整動態(tài)變化

調(diào)整列車接續(xù)時，約束圖的接續(xù)邊Ac會發(fā)生變化，導(dǎo)致約束圖的拓?fù)浣Y(jié)構(gòu)改變，從而改變了約束圖的整數(shù)圈基B；由整數(shù)圈基構(gòu)成的約束條件( 5 )也需做相應(yīng)的調(diào)整，導(dǎo)致備選列車接接續(xù)條件下CPF模型在求解過程中需要不斷重構(gòu)。固定列車接續(xù)、備選接續(xù)條件下，運用CPF模型編制周期性列車運行圖的流程分別如圖2(a)與圖2(b)所示。

(2)換乘客流的接續(xù)服務(wù)在列車接續(xù)調(diào)整過程中缺乏保障

固定列車接續(xù)條件下編制周期性列車運行圖，提供接續(xù)服務(wù)的換乘客流OD不變，換乘客流的接續(xù)服務(wù)在運行圖編制過程中可以得到保障；備選列車接續(xù)條件下編制周期性運行圖，不同的列車接續(xù)組合服務(wù)的換乘客流OD不同，導(dǎo)致調(diào)整列車接續(xù)時換乘客流的列車接續(xù)服務(wù)缺乏保障。調(diào)整列車接續(xù)不僅影響列車接續(xù)直接服務(wù)的一次換乘客流，而且影響多個列車接續(xù)接力服務(wù)的多次換乘客流。

(3)周期性列車運行圖的穩(wěn)定性隨列車接續(xù)的調(diào)整動態(tài)變化

列車接續(xù)是影響周期性列車運行圖穩(wěn)定性重要因素，在實際運營階段根據(jù)列車的晚點程度維持或取消列車接續(xù)，維持列車接續(xù)往往造成嚴(yán)重的晚點傳播，取消列車接續(xù)又會降低換乘客流服務(wù)質(zhì)量，所以調(diào)整列車接續(xù)時還應(yīng)兼顧不同組合的列車接續(xù)對周期性列車運行圖的穩(wěn)定性。

圖2 固定列車接續(xù)與備選列車接續(xù)的周期性列車運行圖編制流程比較

本文通過分類整數(shù)圈基使列車接續(xù)邊形成的基圈與其他基圈保持獨立，避免了求解列車接續(xù)時傳統(tǒng)CPF模型的重構(gòu)；通過調(diào)整傳統(tǒng)CPF模型的決策變量與目標(biāo)函數(shù)，保證換乘客流的列車接續(xù)服務(wù)，從而確定了備選列車接續(xù)條件下周期性列車運行圖編制的新流程(圖2(c))。由于運行圖穩(wěn)定性不僅與列車接續(xù)有關(guān)，還與冗余時間設(shè)置有關(guān)，為簡化模型本文暫不考慮列車接續(xù)與周期性列車運行圖穩(wěn)定性的作用關(guān)系。

3 適應(yīng)備選列車接續(xù)的分類整數(shù)圈基

如果將約束圖的整數(shù)基圈按照是否包含接續(xù)邊分類，并使包含接續(xù)邊的基圈保持相互獨立，調(diào)整列車接續(xù)時只需松弛調(diào)整列車接續(xù)對應(yīng)的基圈，而不需要調(diào)整其他基圈，避免了約束圖整數(shù)圈基的重復(fù)搜索。本文將具有上述特征的整數(shù)圈基稱為“分類整數(shù)圈基”。

分類整數(shù)圈基由兩類基圈構(gòu)成：一類基圈B1由運行邊、停站邊、安全邊組成，不包含列車接續(xù)邊；另一類基圈B2由列車接續(xù)邊、運行邊、停站邊、安全邊組成，且每個基圈只包含一個列車接續(xù)邊，B1∪B2構(gòu)成約束圖的一個整數(shù)圈基。第二類基圈與備選列車接續(xù)具有一一對應(yīng)關(guān)系，記作：{c?C|C∈B2，c∈Ac}。

在第二類基圈的圈周期約束( 5 )中添加松弛變量μC∈Ζ用于判斷對應(yīng)的備選列車接續(xù)的選定狀態(tài)，當(dāng)μC=0時接續(xù)基圈未被松弛，對應(yīng)的備選列車接續(xù)被選定；第二類基圈的圈周期約束( 5 )轉(zhuǎn)變?yōu)槭?12)

?C∈B2

(12)

4 基于分類整數(shù)圈基的周期性列車運行圖編制模型

4.1 決策變量

決策變量xa∈Ζ表示約束圖G邊a∈A的周期壓；決策變量yc={0，1|c∈Ac}表示備選列車接續(xù)c是否為被選定。

多次換乘客流OD需要多個列車接續(xù)接力服務(wù)，調(diào)整列車接續(xù)不僅影響列車接續(xù)直接服務(wù)的一次換乘客流OD，還影響其間接服務(wù)的多次換乘客流OD。引入“二次列車接續(xù)”的概念，一個二次列車接續(xù)(c1，c2)由兩個列車接續(xù){c1∈Ac，c2∈Ac}組成，服務(wù)兩次換乘客流。由于三次及以上換乘客流較小，本文暫不考慮。決策變量z(c1，c2)表示二次接續(xù)(c1，c2)是否形成。z(c1，c2)與yc1、yc2存在耦合關(guān)系，只有備選列車接續(xù)c1、c2同時被選定時二次接續(xù)(c1，c2)才能形成，即

z(c1，c2)與yc1、yc2的耦合關(guān)系可用式(13)表示。

2z(c1，c2)≤yc1+yc2≤2z(c1，c2)+1
?c1，c2∈Ac

(13)

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

周期性列車運行圖編制目標(biāo)可以設(shè)為旅客總旅行時間最小、列車總運行時間最小、動車組運用數(shù)量最少、運行圖穩(wěn)定性最強等多類目標(biāo)。由于本文重點研究基于備選列車接續(xù)的周期性列車運行圖編制問題，模型目標(biāo)選取列車總運行時間最小、列車接續(xù)服務(wù)換乘客流最大。

(1)列車總運行時間最小。列車運行總時間最小不僅可以減少旅客的旅行時間，而且可以減少動車組的運用時間。

(14)

(2)列車接續(xù)服務(wù)換乘客流最大。列車接續(xù)服務(wù)的換乘客流越多，越有利于提高換乘客流的服務(wù)質(zhì)量。fc為備選列車接續(xù)c∈Ac服務(wù)的一次換乘客流量；f(c1，c2)為二次列車接續(xù)(c1，c2)服務(wù)的兩次換乘客流量。

(15)

增加目標(biāo)權(quán)重系數(shù)ψ，將多目標(biāo)規(guī)劃轉(zhuǎn)換為單目標(biāo)規(guī)劃，模型目標(biāo)函數(shù)轉(zhuǎn)換為

(16)

4.3 約束條件

(1)圈周期性質(zhì)約束。根據(jù)分類整數(shù)圈基構(gòu)建圈周期約束，式(17)為第一類基圈的圈周期約束，式(18)為第二類基圈的圈周期約束。

(17)

(18)

決策變量yc與第二類基圈的松弛變量μC存在耦合關(guān)系，如果基圈C對應(yīng)備選列車接續(xù)c，則

yc與μC的耦合關(guān)系可表示為式(19)，其中M為一個極大數(shù)。

-M(1-yc)≤μC≤M(1-yc)
?C∈B2，c∈Ac且c?C

(19)

(2)圈變量約束。圈變量qc取值范圍根據(jù)式( 3 )、式( 4 )計算。

aC≤qC≤bC?C∈B1∪B2

(20)

(3)接續(xù)對稱約束。我國列車基本成對開行，列車接續(xù)關(guān)系也應(yīng)具有對稱性。列車接續(xù)需滿足對稱約束(21)，其中c′為備選列車接續(xù)c的對向備選列車接續(xù)。

yc=yc′?c∈GC

(21)

(4)運行圖約束。運行圖約束是保證列車安全運營的重要約束，由列車區(qū)間運行時間約束、停站時間約束、安全間隔約束、接續(xù)時間約束等組成，代表了列車到達、通過、出發(fā)等事件應(yīng)滿足的間隔時間，這些約束可歸納為式(22)。各類約束的取值范圍計算方法文獻[4]已經(jīng)作了詳細(xì)介紹，本文不再重復(fù)。

la≤xa≤ua?a∈A

(22)

綜上所述，建立基于列車接續(xù)備選集的周期性列車運行圖編制模型(Potential Connections & Cyclic Timetabling Model，PCCTM)為

s.t.

?C∈B1

aC≤qC≤bC?C∈B1∪B2

-M(1-yc)≤μC≤M(1-yc)

?C∈B2，c∈Ac且c?C

2z(c1，c2)≤yc1+yc2≤2z(c1，c2)+1 ?c1，c2∈Ac

yc=yc′?c∈Ac

la≤xa≤ua?a∈A

xa∈Z?a∈A

yc，z(c1，c2)∈[0，1] ?c，c1，c2∈Ac

5 案例分析

選取速度等級為300 km/h及部分速度等級為200 km/h的線路作為案例路網(wǎng)，涉及26個節(jié)點城市，31個車站，29個區(qū)段，路網(wǎng)規(guī)模約8 700 km(見圖3)。周期性列車開行方案的周期長度為1 h，周期列車僅考慮大節(jié)點停站的高速列車，共計32對/h(見表1)，為增加列車停站組合數(shù)量，每類列車的開行頻率設(shè)為1列/h。周期性列車開行方案服務(wù)542個客流OD，其中290個直達客流OD、152個一次換乘客流OD、100個二次換乘客流OD。列車運行速度300km/h等級線路取270 km/h，200 km/h等級線路取180 km/h；起停車附加時分300 km/h等級線路分別取2 min、3 min，200 km/h等級線路分別取2 min、2 min，追蹤間隔時間取4 min；列車停站時間取2～8 min，列車接續(xù)時間取15～25 min；案例考慮的備選一次列車接續(xù)有58個，備選二次列車接續(xù)有36個，表2為案例使用的部分備選一次列車接續(xù)。

圖3 高速鐵路路網(wǎng)圖

編號列車起訖點編號列車起訖點編號列車起訖點1G1北京—哈爾濱西23G23深圳北—南昌西45G45武漢—濟南西2G2哈爾濱西—北京24G24南昌西—深圳北46G46濟南西—武漢3G3北京—大連25G25哈爾濱西—大連47G47西安北—廣州南4G4大連—北京26G26大連—哈爾濱西48G48廣州南—西安北5G5北京—吉林27G27吉林—大連49G49西安北—杭州東6G6吉林—北京28G28大連—吉林50G50杭州東—西安北7G7北京—沈陽北29G29上海虹橋—廣州南51G51沈陽北—鄭州東8G8沈陽北—北京30G30廣州南—上海虹橋52G52鄭州東—沈陽北9G9北京南—上海虹橋31G31上海虹橋—武漢53G53哈爾濱西—吉林10G10上海虹橋—北京南32G32武漢—上海虹橋54G54吉林—哈爾濱西11G11北京南—杭州東33G33上海虹橋—西安北55G55沈陽北—上海虹橋12G12杭州東—北京南34G34西安北—上海虹橋56G56上海虹橋—沈陽北13G13北京南—合肥35G35上海虹橋—青島57G57哈爾濱西—天津西14G14合肥—北京南36G36青島—上海虹橋58G58天津西—哈爾濱西15G15北京南—青島37G37上海虹橋—天津西59G59大連—天津西16G16青島—北京南38G38天津西—上海虹橋60G60天津西—大連17G17北京西—太原南39G39上海虹橋—長沙南61G61北京西—南昌西18G18太原南—北京西40G40長沙南—上海虹橋62G62南昌西—北京西19G19北京西—西安北41G41深圳北—武漢63G63濟南西—西安北20G20西安北—北京西42G42武漢—深圳北64G64西安北—濟南西21G21北京西—深圳北43G43廣州南—太原南22G22深圳北—北京西44G44太原南—廣州南

表2 備選列車接續(xù)方案

根據(jù)周期性列車開行方案和備選列車接續(xù)構(gòu)建約束圖，約束圖包含612個點、1 824條邊。設(shè)置目標(biāo)權(quán)重系數(shù)ψ為-1，運用CPLEX 12.3對模型進行求解。運算環(huán)境為Win7-64位操作系統(tǒng)，12G內(nèi)存，Core i7四核處理器，求解獲得42個列車接續(xù)、18個二次列車接續(xù)，占備選列車接續(xù)的72.4%，占備選二次列車接續(xù)的50%。最終選定的列車接續(xù)能夠服務(wù)的一次換乘客流OD有132個，二次換乘客流OD有52個，共184個，占換乘客流OD數(shù)量的73%、換乘客流量的85.8%，求解獲得的列車接續(xù)見表3。案例開行列車的總運行時間為22 460 min，總運行距離為79 900 km，平均旅速為213.4 km/h，平均列車接續(xù)時間為19.4 min，圖4顯示了列車在沿途節(jié)點車站的時刻信息，圖中方框表示列車途經(jīng)車站，方框上的數(shù)字表示列車在該站的到達時刻與出發(fā)時刻。

表3 求解獲得的列車接續(xù)

6 結(jié)論

根據(jù)周期性列車開行方案設(shè)計的列車接續(xù)關(guān)系需要在周期性列車運行圖編制階段根據(jù)運行圖編制狀態(tài)選定，研究案例從58個備選列車接續(xù)中選出了42個列車接續(xù)，占備選列車接續(xù)的72.4%；設(shè)計的分類整數(shù)圈基有效避免了調(diào)整列車接續(xù)時傳統(tǒng)CPF模型的重構(gòu)；從案例求解結(jié)果可以看出73%的換乘OD、85.8%的換乘客流提供了換乘時間在15～25 min之間的接續(xù)服務(wù)，表明PCCPF模型具有較好的適用性。

PCCPF模型解決了備選列車接續(xù)條件下周期性列車運行圖的編制問題，既可以保證換乘客流的列車接續(xù)服務(wù)又可以滿足周期性列車運行圖的編制要求，提高了周期性列車運行圖在我國的適用性。接續(xù)穩(wěn)定性是影響列車接續(xù)服務(wù)性能的重要因素，影響列車接續(xù)可靠性的因素不僅有列車接續(xù)類型，如始發(fā)終到接續(xù)、中間站接續(xù)，還有區(qū)間冗余時間的設(shè)置，可對列車接續(xù)穩(wěn)定性問題開展進一步研究。

參考文獻：

[1]NACHTIGALL K.Periodic Network Optimization and Fixed Interval Timetables[D].Hildesheim:University Hildesheim,1998.

[2]ODIJK M.Railway Timetable Generation[D].Delft: Delft University of Technology,1997.

[3]PEETERS L.Cyclic Railway Timetable Optimization[D].Rotterdam:Erasmus University Rotterdam,2003.

[4]LIEBCHEN C.The First Optimized Railway Timetable in Practice[J].Transportation Science,2008,42(4):420-435.

[5]KROON L.Flexible Connections in PES PModels for Cyclic Passenger Railway Timetabling[J].Transportation Science,2014,48(1):136-154.

圖4 高速鐵路網(wǎng)周期性列車運行圖

[6]汪波,楊浩,牛豐,等.周期運行圖編制模型與算法研究[J].鐵道學(xué)報,2007,29(5):1-6.

WANG Bo,YANG Hao,NIU Feng,et al.Study on Model and Algorithm of Periodic Train Diagram Generation[J].Journal of the China Railway Society,2007,29(5):1-6.

[7]汪波,韓寶明,戰(zhàn)明輝,等.城市軌道交通網(wǎng)絡(luò)周期運行圖編制研究[J].鐵道學(xué)報,2013,35(4):9-15.

WANG Bo,HAN Baoming,ZHAN Minghui,et al.Study on Formulation of Periodic Train Diagram of Urban Rail Transit Network[J].Journal of the China Railway Society,2013,35(4):9-15.

[8]謝美全,聶磊.周期性列車運行圖編制模型研究[J].鐵道學(xué)報,2009,31(4):7-13.

XIE Meiquan,NIE Lei.Model of Cyclic Train Timetable[J].Journal of the China Railway Society,2009,31(4):7-13.

[9]聶磊,張淵,武鑫.計算機編制周期性列車運行圖關(guān)鍵技術(shù)[J].中國鐵道科學(xué),2014,35(1):114-121.

NIE Lei,ZHANG Yuan,WU Xin.Key Technologies for Computer Generation of Cyclic Train Timetable[J].China Railway Science,2014,35(1):114-121.

[10]賈曉秋.客運專線旅客列車周期運行圖的優(yōu)化理論與方法研究[D].成都:西南交通大學(xué),2011.

[11]郭根材,聶磊.基于歐洲列車時刻表的高速鐵路列車銜接方案探討[J].北京交通大學(xué)學(xué)報,2012,36(6):21-26.

GUO Gencai,NIE Lei.Train Connection Plan for High-Speed Railway Based on European Rail Timetable[J].Journal of Beijing Jiaotong University,2012,36(6):21-26.

[12]付慧伶,聶磊,楊浩.基于歐洲列車時刻表的高速列車行車組織方案[J].北京交通大學(xué)學(xué)報,2009,33(3):45-51.

FU Huiling,NIE Lei,YANG Hao.Operation Plan for High-Speed Train Based on European Rail Timetable[J].Journal of Beijing Jiaotong University,2009,33(3):45-51.

[13]LIEBCHEN C,PEETERS L.Integral Cycle Bases for Cyclic Timetabling[J].Discrete Optimization,2009,6(1):98-109

[14]郭根材,聶磊,佟璐.高速鐵路網(wǎng)周期性列車運行圖接續(xù)約束生成模型[J].鐵道學(xué)報,2015,37(8):1-7.

GUO Gencai,NIE Lei,TONG Lu.Train Connection Model for Cyclic Timetable of High Speed Rail Network[J].Journal of the China Railway Society,2015,37(8):1-7.