郭根材,聶 磊,佟 璐,賀振歡
(1.北京交通大學(xué) 交通運(yùn)輸學(xué)院,北京 100044;2.中國鐵道科學(xué)研究院 電子計算技術(shù)研究所,北京 100081)
為提高換乘客流服務(wù)質(zhì)量周期性列車運(yùn)行圖模型[1-5]明確規(guī)定了列車接續(xù)約束。國內(nèi)一些學(xué)者對周期性列車運(yùn)行圖的研究以單條線路為主[6-10],列車接續(xù)約束設(shè)置簡單或被忽略,研究側(cè)重于模型求解算法、計算機(jī)編制周期性列車運(yùn)行圖等方面。歐洲鐵路經(jīng)過多年運(yùn)營,已經(jīng)形成固定的列車接續(xù)關(guān)系,編制周期性列車運(yùn)行圖的列車接續(xù)約束是明確的[11,12];而我國高速鐵路快速成網(wǎng),列車運(yùn)行圖隨新線的開通不斷調(diào)整,尚未形成明確的列車接續(xù)關(guān)系。編制周期性列車運(yùn)行圖時,列車接續(xù)可能與運(yùn)行圖的安全間隔約束矛盾,列車接續(xù)需要根據(jù)實(shí)際情況調(diào)整,根據(jù)周期性列車開行方案生成的列車接續(xù)[14]仍為備選列車接續(xù)。
編圖過程中,列車開行方案、備選列車接續(xù)、列車運(yùn)行圖三者相互制約,需要不斷根據(jù)運(yùn)行線間的沖突調(diào)整列車開行方案、列車接續(xù)方案,以保證運(yùn)營階段列車安全運(yùn)行。本文側(cè)重研究周期性列車開行方案給定時基于備選列車接續(xù)的周期性列車運(yùn)行圖編制模型,以提高周期性列車運(yùn)行圖在我國高速鐵路的適用性。介紹歐洲鐵路使用的周期性列車運(yùn)行圖編制模型(Cycle Periodicity Formulation,CPF模型);針對固定列車接續(xù),研究備選列車接續(xù)條件下CPF模型求解周期性列車運(yùn)行圖存在的問題,提出基于備選列車接續(xù)的周期性列車運(yùn)行圖編制流程;給出新流程中分類整數(shù)圈基的構(gòu)造方法,改進(jìn)CPF模型的整數(shù)圈基約束條件以避免CPF模型重構(gòu);進(jìn)一步調(diào)整CPF模型的決策變量、目標(biāo)函數(shù)與約束條件,建立適合備選列車接續(xù)的周期性列車運(yùn)行圖編制模型PCCPF模型;以我國高速鐵路網(wǎng)為例,運(yùn)用Cplex12.3對模型求解,進(jìn)行了案例驗(yàn)證。
運(yùn)用CPF模型編制周期性列車運(yùn)行圖的核心思想是將列車事件(到達(dá)、出發(fā)、通過)的發(fā)生時刻看作周期勢,列車事件的發(fā)生間隔看作周期壓[2,3],利用列車事件間的約束關(guān)系構(gòu)建表示列車到發(fā)間隔約束的有向圖(稱為約束圖),進(jìn)而根據(jù)約束圖中圈的周期性質(zhì)構(gòu)建周期性列車運(yùn)行圖編制模型。約束圖G=(N,A)的頂點(diǎn)N代表列車事件,約束圖的邊A代表列車事件間的約束關(guān)系,如列車發(fā)發(fā)間隔約束、到發(fā)間隔約束等。約束圖的每條邊a∈A存在一個取值范圍la≤xa≤ua表示列車事件之間應(yīng)滿足的約束條件,xa為邊a的周期壓,la為最小發(fā)生間隔,ua為最大發(fā)生間隔。約束圖的邊A由運(yùn)行邊Ar、停站邊Ad、安全邊As、接續(xù)邊Ac等組成。圖1為區(qū)段AD之間兩列列車構(gòu)成的約束圖,圖中每條邊上的數(shù)值區(qū)間[la,ua]表示列車事件之間應(yīng)滿足的約束條件,如圖中點(diǎn)1與點(diǎn)7之間的弧表示兩列車在A站的出發(fā)間隔約束,弧上數(shù)值區(qū)間[4,56]表示兩列車在A站的出發(fā)間隔應(yīng)在4~56 min之內(nèi),以滿足4 min安全追蹤間隔要求,約束圖的詳細(xì)介紹可參考文獻(xiàn)[13]。
圖1 兩列列車的約束圖
( 1 )
aC≤qC≤bC?C∈G
( 2 )
( 3 )
( 4 )
文獻(xiàn)[3]進(jìn)一步證明,如果約束圖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)運(yùn)用于荷蘭鐵路[3]和柏林地鐵[4]的周期性列車運(yùn)行圖編制中,CPF模型的詳細(xì)介紹可參考文獻(xiàn)[3]和文獻(xiàn)[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)
相對固定列車接續(xù),備選列車接續(xù)條件下編制周期性列車運(yùn)行圖需要根據(jù)運(yùn)行圖編制的實(shí)際情況不斷迭代調(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ù)條件下,運(yùn)用CPF模型編制周期性列車運(yùn)行圖的流程分別如圖2(a)與圖2(b)所示。
(2)換乘客流的接續(xù)服務(wù)在列車接續(xù)調(diào)整過程中缺乏保障
固定列車接續(xù)條件下編制周期性列車運(yùn)行圖,提供接續(xù)服務(wù)的換乘客流OD不變,換乘客流的接續(xù)服務(wù)在運(yùn)行圖編制過程中可以得到保障;備選列車接續(xù)條件下編制周期性運(yùn)行圖,不同的列車接續(xù)組合服務(wù)的換乘客流OD不同,導(dǎo)致調(diào)整列車接續(xù)時換乘客流的列車接續(xù)服務(wù)缺乏保障。調(diào)整列車接續(xù)不僅影響列車接續(xù)直接服務(wù)的一次換乘客流,而且影響多個列車接續(xù)接力服務(wù)的多次換乘客流。
(3)周期性列車運(yùn)行圖的穩(wěn)定性隨列車接續(xù)的調(diào)整動態(tài)變化
列車接續(xù)是影響周期性列車運(yùn)行圖穩(wěn)定性重要因素,在實(shí)際運(yùn)營階段根據(jù)列車的晚點(diǎn)程度維持或取消列車接續(xù),維持列車接續(xù)往往造成嚴(yán)重的晚點(diǎn)傳播,取消列車接續(xù)又會降低換乘客流服務(wù)質(zhì)量,所以調(diào)整列車接續(xù)時還應(yīng)兼顧不同組合的列車接續(xù)對周期性列車運(yùn)行圖的穩(wěn)定性。
圖2 固定列車接續(xù)與備選列車接續(xù)的周期性列車運(yùn)行圖編制流程比較
本文通過分類整數(shù)圈基使列車接續(xù)邊形成的基圈與其他基圈保持獨(dú)立,避免了求解列車接續(xù)時傳統(tǒng)CPF模型的重構(gòu);通過調(diào)整傳統(tǒng)CPF模型的決策變量與目標(biāo)函數(shù),保證換乘客流的列車接續(xù)服務(wù),從而確定了備選列車接續(xù)條件下周期性列車運(yùn)行圖編制的新流程(圖2(c))。由于運(yùn)行圖穩(wěn)定性不僅與列車接續(xù)有關(guān),還與冗余時間設(shè)置有關(guān),為簡化模型本文暫不考慮列車接續(xù)與周期性列車運(yùn)行圖穩(wěn)定性的作用關(guān)系。
如果將約束圖的整數(shù)基圈按照是否包含接續(xù)邊分類,并使包含接續(xù)邊的基圈保持相互獨(dú)立,調(diào)整列車接續(xù)時只需松弛調(diào)整列車接續(xù)對應(yīng)的基圈,而不需要調(diào)整其他基圈,避免了約束圖整數(shù)圈基的重復(fù)搜索。本文將具有上述特征的整數(shù)圈基稱為“分類整數(shù)圈基”。
分類整數(shù)圈基由兩類基圈構(gòu)成:一類基圈B1由運(yùn)行邊、停站邊、安全邊組成,不包含列車接續(xù)邊;另一類基圈B2由列車接續(xù)邊、運(yùn)行邊、停站邊、安全邊組成,且每個基圈只包含一個列車接續(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)
決策變量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)
周期性列車運(yùn)行圖編制目標(biāo)可以設(shè)為旅客總旅行時間最小、列車總運(yùn)行時間最小、動車組運(yùn)用數(shù)量最少、運(yùn)行圖穩(wěn)定性最強(qiáng)等多類目標(biāo)。由于本文重點(diǎn)研究基于備選列車接續(xù)的周期性列車運(yùn)行圖編制問題,模型目標(biāo)選取列車總運(yùn)行時間最小、列車接續(xù)服務(wù)換乘客流最大。
(1)列車總運(yùn)行時間最小。列車運(yùn)行總時間最小不僅可以減少旅客的旅行時間,而且可以減少動車組的運(yùn)用時間。
(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)
(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)運(yùn)行圖約束。運(yùn)行圖約束是保證列車安全運(yùn)營的重要約束,由列車區(qū)間運(yùn)行時間約束、停站時間約束、安全間隔約束、接續(xù)時間約束等組成,代表了列車到達(dá)、通過、出發(fā)等事件應(yīng)滿足的間隔時間,這些約束可歸納為式(22)。各類約束的取值范圍計算方法文獻(xiàn)[4]已經(jīng)作了詳細(xì)介紹,本文不再重復(fù)。
la≤xa≤ua?a∈A
(22)
綜上所述,建立基于列車接續(xù)備選集的周期性列車運(yùn)行圖編制模型(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
選取速度等級為300 km/h及部分速度等級為200 km/h的線路作為案例路網(wǎng),涉及26個節(jié)點(diǎn)城市,31個車站,29個區(qū)段,路網(wǎng)規(guī)模約8 700 km(見圖3)。周期性列車開行方案的周期長度為1 h,周期列車僅考慮大節(jié)點(diǎn)停站的高速列車,共計32對/h(見表1),為增加列車停站組合數(shù)量,每類列車的開行頻率設(shè)為1列/h。周期性列車開行方案服務(wù)542個客流OD,其中290個直達(dá)客流OD、152個一次換乘客流OD、100個二次換乘客流OD。列車運(yùn)行速度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)圖
編號列車起訖點(diǎn)編號列車起訖點(diǎn)編號列車起訖點(diǎn)1G1北京—哈爾濱西23G23深圳北—南昌西45G45武漢—濟(jì)南西2G2哈爾濱西—北京24G24南昌西—深圳北46G46濟(jì)南西—武漢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濟(jì)南西—西安北20G20西安北—北京西42G42武漢—深圳北64G64西安北—濟(jì)南西21G21北京西—深圳北43G43廣州南—太原南22G22深圳北—北京西44G44太原南—廣州南
表2 備選列車接續(xù)方案
根據(jù)周期性列車開行方案和備選列車接續(xù)構(gòu)建約束圖,約束圖包含612個點(diǎn)、1 824條邊。設(shè)置目標(biāo)權(quán)重系數(shù)ψ為-1,運(yùn)用CPLEX 12.3對模型進(jìn)行求解。運(yùn)算環(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。案例開行列車的總運(yùn)行時間為22 460 min,總運(yùn)行距離為79 900 km,平均旅速為213.4 km/h,平均列車接續(xù)時間為19.4 min,圖4顯示了列車在沿途節(jié)點(diǎn)車站的時刻信息,圖中方框表示列車途經(jīng)車站,方框上的數(shù)字表示列車在該站的到達(dá)時刻與出發(fā)時刻。
表3 求解獲得的列車接續(xù)
根據(jù)周期性列車開行方案設(shè)計的列車接續(xù)關(guān)系需要在周期性列車運(yùn)行圖編制階段根據(jù)運(yùn)行圖編制狀態(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ù)條件下周期性列車運(yùn)行圖的編制問題,既可以保證換乘客流的列車接續(xù)服務(wù)又可以滿足周期性列車運(yùn)行圖的編制要求,提高了周期性列車運(yùn)行圖在我國的適用性。接續(xù)穩(wěn)定性是影響列車接續(xù)服務(wù)性能的重要因素,影響列車接續(xù)可靠性的因素不僅有列車接續(xù)類型,如始發(fā)終到接續(xù)、中間站接續(xù),還有區(qū)間冗余時間的設(shè)置,可對列車接續(xù)穩(wěn)定性問題開展進(jìn)一步研究。
參考文獻(xià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)周期性列車運(yùn)行圖
[6]汪波,楊浩,牛豐,等.周期運(yùn)行圖編制模型與算法研究[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ò)周期運(yùn)行圖編制研究[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]謝美全,聶磊.周期性列車運(yùn)行圖編制模型研究[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]聶磊,張淵,武鑫.計算機(jī)編制周期性列車運(yùn)行圖關(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ùn)專線旅客列車周期運(yùn)行圖的優(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)周期性列車運(yùn)行圖接續(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.