考慮多種資源約束的城際鐵路運輸能力計算方法

廖正文，李海鷹，王 瑩，苗建瑞

(1. 北京交通大學 軌道交通控制與安全國家重點實驗室，北京 100044；2. 北京交通大學 交通運輸學院，北京 100044)

鐵路運輸能力既取決于固定設備的配置數(shù)量和結(jié)構，又取決于活動設備(或稱移動設備)的配屬，還取決于固定設備與活動設備的相互適配[1]。傳統(tǒng)的運輸能力通常采用通過能力和輸送能力兩種概念。通過能力僅取決于固定設備設置條件，而輸送能力還需要考慮與活動設備相關的多種運輸資源配置條件。城際鐵路一般采用動車組獨立配屬的活動設備配置方法，是以動車組立即折返實現(xiàn)公交化的運輸組織模式[2]，具有發(fā)車密度大、運行距離短、固定設備資源利用率高等特點。在這種資源配置和運用方式下，活動設備和固定設備之間存在較強的制約關系。若不考慮動車組數(shù)量和運用約束，僅基于固定設備配置計算通過能力，很可能高估了實際可能運行的列車數(shù)量，難以用于實際運營決策。因此，有必要將動車組這類采購周期長且價格昂貴的活動資源納入城際鐵路運輸能力研究的范圍。本文研究的“城際鐵路運輸能力”是在一定的固定設備、動車組類型和行車組織方法條件下，利用一定數(shù)量的動車組，在單位時間(一晝夜)內(nèi)最多能夠開行的列車數(shù)量。該運輸能力除了考慮固定設備資源的制約外，還將“輸送能力”定義中關于活動設備的動車組數(shù)量因素考慮在內(nèi)，突破了“通過能力”的研究范疇，是面向城際鐵路運營特點的一種用于衡量區(qū)間、車站到發(fā)線與動車組等多種資源約束下的運輸能力。

國內(nèi)外關于鐵路運輸能力的研究以通過能力為主。為了使通過能力計算簡便易行，忽略部分復雜的影響因素，簡化了計算條件。一些研究為克服既有方法的弊端，改進了分析計算法，以得到更符合實際的通過能力[3-7]。部分學者利用優(yōu)化方法模擬編制列車運行圖、車站作業(yè)計劃等計算通過能力[8-12]。在歐洲的鐵路運輸能力研究中，列車運行圖壓縮法是用于計算鐵路運輸能力利用飽和度的常用方法，如文獻[13]。由于固定設備建設成本高，投產(chǎn)周期長，是運輸能力研究主要關注的對象，國內(nèi)的研究普遍未將活動設備的運用對運輸能力的影響考慮在內(nèi)，忽略了固定設備與活動設備的適配關系，難以準確地反映實際運輸能力。本文針對城際鐵路運輸能力受多種資源相互制約的問題，以動車組數(shù)量為約束，考慮動車組運用與運行圖、車站股道運用間相互制約關系，提出一種針對城際鐵路運輸能力的計算方法，可計算得到更準確的運輸能力，以支撐運營決策。

1 城際鐵路運輸能力計算模型

根據(jù)上述城際鐵路運輸能力的定義，本文研究的城際運輸能力計算問題是在給定鐵路網(wǎng)拓撲、運行圖標尺和追蹤間隔時間、車站股道占用間隔時間、動車組數(shù)量、立即折返最小接續(xù)時間等條件下，計算當前城際鐵路區(qū)段一晝夜內(nèi)各方向最多可以開行的列車總數(shù)。為此，給出一種向基本運行圖中循環(huán)插入虛擬列車，直至獲得滿表運行圖的城際鐵路運輸能力計算方法。該方法以給定的基本運行圖為框架，以運行圖鋪畫規(guī)則、股道運用規(guī)則與動車組運用規(guī)則為約束條件。根據(jù)涉及的運輸資源類別，城際鐵路運輸能力計算問題可進一步劃分為列車運行圖、動車組運用和車站股道分配3個子問題，三者之間存在關聯(lián)關系。本節(jié)運用數(shù)學模型刻畫三者對運輸能力的影響及其相互關聯(lián)關系。

1.1 符號說明

1.2 列車運行圖子問題

列車運行圖子問題的主要決策變量是列車在各車站的到達和出發(fā)時刻。從運輸能力利用的角度看，列車運行圖的鋪畫是對鐵路區(qū)間時空資源的分配。本文使用以下約束條件表示列車運行圖問題變量間的關聯(lián)關系

(1)

?f∈F*e∈Πf

(2)

(3)

(4)

?f∈F*f′∈F*-fs∈Γf∩Γf′

(5)

(6)

?f∈F*f′∈F*-fe∈Πf∩Πf′

(7)

?f∈F*f′∈F*-fe∈Πf∩Πf′

(8)

1.3 動車組運用子問題

動車組運用子問題的關鍵在于確定折返列車間的銜接關系，在數(shù)學上是一個0-1指派問題，是對有限的活動設備資源的時空調(diào)撥與分配。以下是動車組接續(xù)關系的基本約束。

(9)

(10)

?s∈Γf∈F*f′∈F*:ω(f)=δ(f′)=s

(11)

圖1 動車組接續(xù)條件示意圖

1.4 車站股道分配子問題

車站股道分配子問題的決策內(nèi)容是列車在各車站的股道選擇，保證股道占用不沖突，是對車站股道這一時空資源進行優(yōu)化分配。股道分配問題的基本約束為

(12)

(13)

式(12)、式(13)表示列車股道選擇的唯一性約束，列車若在當前車站停站，則須選擇具備乘降條件的股道停站，否則須選擇正線股道通過。股道的占用與列車的到達和出發(fā)時刻、動車組的接續(xù)關系有密切的關聯(lián)，約束條件為

(14)

式(14)表示中間站股道的占用間隔時間約束，即當兩列車均選用同一股道k時，后行列車須在前行列車離開若干時間后才允許進入該股道，如圖2中的f1與f3。

ω(f)=δ(f′)=sk∈Ks

(15)

ω(f)=δ(f′)=sk∈Ks

(16)

(17)

圖2 股道分配時間條件示意圖

1.5 城際鐵路運輸能力計算一體化模型

由列車運行圖、動車組運用、車站股道分配3個子問題的數(shù)學模型可知，上述3個子問題共用部分決策變量。這些共用的決策變量是子問題間互相關聯(lián)的紐帶，體現(xiàn)了運輸能力的組成要素間存在著相互作用、相互影響的耦合關系，運輸能力影響要素互動關系示意見圖3，分別為：

圖3 運輸能力影響要素互動關系示意圖

耦合關系1：列車運行圖與股道分配耦合關系。列車在車站的到達、出發(fā)時刻與列車進入、離開相應股道的時刻有對應關系。

耦合關系2：列車運行圖與動車組運用耦合關系。具有立即折返接續(xù)關系的2列車，其前序列車的到達時刻與后序列車的出發(fā)時刻須滿足動車組的接續(xù)時間標準。

耦合關系3：股道分配與動車組運用耦合關系。具有立即折返接續(xù)關系的2列車在立即折返車站必須分配在同一股道。

根據(jù)上述運輸能力的影響因素及關聯(lián)關系分析，可構建城際鐵路運輸能力計算的一體化模型P1：

max ‖F(xiàn)*‖

s.t.

式(1)～式(17)

FB?F*

(18)

F*?F

(19)

該模型的第1個目標函數(shù)為運輸能力計算的主要目標，即盡可能多地在運行圖中鋪畫滿足約束條件的列車。其中集合F*表示入選列車集合，是決策變量。第2個目標函數(shù)為次要目標，即在滿足規(guī)劃列車盡可能多的條件下，令獲得的運行圖盡可能緊湊。式(1)～式(8)為運行圖子問題約束，式(9)、式(10)為動車組接續(xù)子問題約束，式(12)、式(13)為股道分配子問題的約束。式(11)、式(14)～式(17)表示各子系統(tǒng)間關聯(lián)關系的耦合約束。式(18)表示所有的基本圖列車必須被鋪畫，式(19)表示入選列車須從可能被鋪畫的列車全集中選出。

2 運輸能力計算分時段滾動壓力測試算法

文獻[8]提出向運行圖中不斷增加列車，直到無法在給定的時間內(nèi)鋪畫所有列車為止的鐵路運輸能力計算“壓力測試法”。本文依據(jù)該方法的基本思路，考慮車站股道分配和動車組數(shù)量約束，利用模型P1對列車運行圖進行壓力測試，計算城際鐵路運輸能力。模型P1存在約束F*?F，表示從列車全集中選擇符合約束條件的列車進行鋪畫。由于運行線鋪畫的可能情況非常多，F(xiàn)*集合難以被窮舉，因此在求解時采用壓力測試算法，在基本運行圖框架下(基本圖中的運行線必須被鋪畫，但到發(fā)時刻可在給定范圍內(nèi)調(diào)整)不斷加入新列車以擴充列車集合F*，最終可獲得滿表運行圖，其中包含的列車數(shù)量‖F(xiàn)*‖即可視為城際鐵路的運輸能力。

在擴充列車集合F*時，首先依據(jù)停站方案比例，以一定的概率隨機生成將要加入的列車集合FI，與已成功插入的列車合并生成待驗證列車集合FQ，再使用商業(yè)求解軟件求解混合整數(shù)規(guī)劃模型P2驗證集合FQ的可行性，若可行，則將這些虛擬列車加入集合F*，然后繼續(xù)加車；若不可行，則認為當前的可行列車集合F*即包含了可被鋪畫的所有列車，壓力測試結(jié)束。其中數(shù)學規(guī)劃模型P2為

s.t.

式(1)～式(18)

式中：FQ為待驗證可行性的列車集合，用以替換各約束式中的F*集合，表示測試FQ是否滿足約束式(1)～式(18)。

上述數(shù)學規(guī)劃模型是大規(guī)模的組合優(yōu)化問題，直接計算全天的運行圖存在困難。依據(jù)編圖人員編制大規(guī)模列車運行圖與動車組交路計劃的經(jīng)驗，本文遵循“從前往后”順次鋪畫的原則，設計了分時段滾動的求解算法。該算法設置了時間寬度為T的滾動時間窗，每次只“壓力測試”求解該時間窗涉及的變量。當某時間窗求解完畢后，首先固定該時間窗內(nèi)所有決策變量的值，然后平移該時間窗至下一位置繼續(xù)進行“壓力測試”求解，直至完成線路全天運輸能力的壓力測試計算，見圖4。設置過長的時間窗寬度T會導致模型規(guī)模過大，商業(yè)求解軟件在較短時間內(nèi)得不到可行解；而設置過短的時間窗寬度T，運行圖在時間維度上分割過細，可能導致全局運行圖質(zhì)量不佳。因此，滾動時間窗寬度T應根據(jù)問題規(guī)模和求解器的求解效率合理設置。

圖4 分時段滾動壓力測試求解示意圖

具體實現(xiàn)步驟為

Step1初始化。定義滾動時間窗時間寬度為T，據(jù)此生成滾動時間窗的開始時間序列t0,t1,…,tN-1(其中N為滾動時間窗數(shù))；定義n為時間窗的序號，令n:=0，F(xiàn)*(n):=?。

Step2確定當前鋪畫的時間窗范圍[tn,tn+1]。

Step3篩選始發(fā)站出發(fā)時間范圍與當前鋪畫時間窗范圍有重疊的基本圖列車，并將其添加至當前鋪畫時間窗的待驗證列車集合中，即

FQ(n):=F*(n-1)∪{f∈FB|[tn,tn+1]∩[Ef,lf]≠?}

Step4在給定待驗證列車集合FQ(n)的條件下，對當前時間窗進行壓力測試求解：

Step4.1求解模型P2，若模型求得可行解，令F*(n):=FQ(n)；否則轉(zhuǎn)跳至Step4.3；

Step4.2按照給定的概率隨機生成插入的虛擬列車集合FI，令FQ(n):=FI∪FQ(n)，轉(zhuǎn)跳至Step4.1；

Step4.3無列車可加入當前時間窗，獲得當前時間窗的局部最優(yōu)滿表運行圖。

Step5固定當前時間窗內(nèi)已經(jīng)求得的變量：

Step6若全天運行圖已計算完成，輸出運輸能力計算結(jié)果‖F(xiàn)*‖及對應的運行圖、股道運用方案和動車組接續(xù)方案，退出算法；否則向前平移時間窗至下一時段，即令n:=n+1，轉(zhuǎn)跳至Step3繼續(xù)求解。

3 算例驗證

本文以京津城際鐵路北京南至天津區(qū)段為例，通過對比分析考慮與不考慮動車組運用與股道分配的運輸能力計算結(jié)果，說明考慮多種資源約束在運輸能力計算中的必要性；通過分析動車組數(shù)量與運輸能力之間的對應關系，說明在不同條件下運輸能力的實際限制條件可能不同。算例分析了可行解搜索時限對運輸能力計算結(jié)果的影響，驗證上述模型與算法的可行性。在此暫不考慮跨線列車和北京南至于家堡長交路列車對運輸能力的影響，采用的基礎數(shù)據(jù)見表1。

表1 算例基礎參數(shù)

算法的計算機程序利用C# (.NET Framework 4.5.1)語言編寫，在1臺CPU為Intel Core i7-4770 3.40 GHz，8 GB內(nèi)存的臺式計算機上運行，混合整數(shù)規(guī)劃模型的求解引擎采用Gurobi 8.0.0。

3.1 考慮動車組運用與股道分配的運輸能力計算結(jié)果

為了對比考慮動車組運用、股道分配前后運輸能力計算的結(jié)果，本算例設計了3種列車加壓場景，即

場景1：全部加入武清站不停站列車；

場景2：全部加入武清站停站列車；

場景3：按1∶1的比例通過隨機函數(shù)產(chǎn)生武清站停站或武清站不停站列車。

同時，根據(jù)考慮的資源約束不同，在模型P1的基礎上，通過松弛相關約束設計了4種運輸能力計算模型，以此對比考慮多種影響因素的運輸能力計算結(jié)果差異：

模型1：僅加壓列車運行圖(松弛約束式(9)～式(17))；

模型2：僅考慮中間站股道分配加壓列車運行圖(松弛約束式(9)～式(11)及式(15)～式(17))；

模型3：僅考慮動車組立即折返接續(xù)加壓列車運行圖(松弛約束式(12)～式(17))；

模型4：考慮動車組立即折返及股道分配加壓列車運行圖(包含所有約束)。

實驗中的動車組數(shù)量按17組標準動車組給定。根據(jù)上述場景和模型劃分進行交叉實驗，可得運輸能力計算結(jié)果，見表2。

表2 各模型在不同停站方案下的計算結(jié)果對比 列

上述結(jié)果說明了考慮動車組資源約束的運輸能力計算模型的計算結(jié)果更加準確。以全部停站的方案為例，若僅考慮運行圖約束計算運輸能力，上下行列車數(shù)量分別為200列和208列；加入中間站股道分配約束后，列車數(shù)量變化不大，這是因為對于城際鐵路而言中間站股道分配不是運輸能力的制約因素；當加入動車組接續(xù)約束后，上下行列車數(shù)量分別降為155列和156列，該結(jié)果能夠在一定程度上反映動車組數(shù)量影響了運行圖通過能力的實現(xiàn)。若考慮動車組立即折返作業(yè)中股道分配沖突，上下行列車數(shù)量則進一步降為145列，該結(jié)果說明在股道資源緊張的條件下，忽略立即折返作業(yè)在股道分配沖突而僅考慮動車組接續(xù)對運輸能力的影響，將會導致計算結(jié)果偏大。以上的計算結(jié)果表明，運輸能力是多種資源協(xié)同運用下運輸供給量的體現(xiàn)，采用考慮多種資源的一體化運輸能力計算模型，能充分體現(xiàn)多種資源的制約與互動，使運輸能力計算結(jié)果更加貼近實際。

3.2 動車組數(shù)量對運輸能力的影響

動車組的數(shù)量和配屬是運輸能力的重要影響因素。算例通過對動車組數(shù)量進行加壓，研究動車組數(shù)量對運輸能力的影響。各方案除了提供的動車組數(shù)量有所差異以外，其他的參數(shù)設置完全相同，以相等的比例插入在武清站停站或不停站的列車，并統(tǒng)計在不同動車組數(shù)量供給的情況下開行的列車數(shù)量及始發(fā)終到車站的股道占用率，以分析動車組數(shù)量與運輸能力之間的規(guī)律。

當動車組數(shù)量較少時，動車組數(shù)量是運輸能力的決定因素，而區(qū)間通過能力相對較為富余，列車的數(shù)量與動車組數(shù)量呈近似線性的關系，見圖5。當動車組數(shù)量較多時(多于16組)，區(qū)間通過能力開始成為運輸能力的制約因素。當動車組數(shù)量大于22組時，列車數(shù)量不再隨動車組數(shù)量的增加而增加，此時線路和車站的通過能力是整體運輸能力的決定因素，無法通過投入更多的動車組以提升運輸能力。

圖5 動車數(shù)量與列車數(shù)量關系折線圖

隨著動車組數(shù)量的增加，動車組的折返需占用更多的股道資源，因此始發(fā)終到車站的股道占用率也隨之增加，見圖6。但動車組數(shù)量增加到一定程度后，每條動車交路長度變短，動車組在執(zhí)行完幾個列車任務后即迅速入段，不在終到車站產(chǎn)生過長時間的停留，因此股道的占用率呈不變或下降趨勢。

圖6 動車數(shù)量與車站股道占用率關系折線圖

3.3 可行解搜索時限對結(jié)果的影響

在實際求解當中，求解器判別部分比較復雜的列車集合的可行性需要耗費大量計算時間。由于壓力測試的目的是為了獲得可行解而并非最優(yōu)解，對解的優(yōu)化質(zhì)量要求相對較低，因此為了提升壓力測試的效率，在前述實驗中為每次求解設定了搜索可行解的時間限制為60 s(到達該時間限制尚未搜索到可行解則認為當前輸入無可行解)。進一步地，研究了單次最大求解時間的設置對求解效率和求解質(zhì)量的影響，見表3。

表3 單次最大求解時限對壓力測試求解質(zhì)量的影響

實驗數(shù)據(jù)說明，單次求解時間會影響壓力測試計算的質(zhì)量。當單次求解時間限制較短時，可以在較快時間內(nèi)獲得運輸能力計算結(jié)果，但結(jié)果的優(yōu)化程度較低。隨著單次求解時間長度的增加，運輸能力計算壓力測試的結(jié)果逐步趨于穩(wěn)定，說明適當擴大單次最大求解時間有利于提升壓力測試結(jié)果的質(zhì)量。但是，過大的單次最大求解時間對結(jié)果質(zhì)量提升意義不大，反而延緩了計算進度。綜合權衡求解計算時間和求解質(zhì)量，本案例將單次搜索時限設置為40 s較為合理。

4 結(jié)論

論文提出了針對城際鐵路的考慮多種資源協(xié)同運用的運輸能力計算方法。提出了考慮運行圖、股道分配、動車組接續(xù)的運輸能力計算數(shù)學模型，以及針對運營全日的運輸能力計算分時段滾動壓力測試算法。算例對比分析了求解參數(shù)設置對運輸能力計算結(jié)果的影響，可用于分析不同運營參數(shù)條件下的運輸能力。算例表明，相比于只考慮運行圖的通過能力計算結(jié)果，考慮股道運用與動車組接續(xù)的運輸能力計算結(jié)果能夠更加準確地反映運營的實際運輸能力利用情況，能識別特定場景下運輸能力的決定性因素，對運行圖、動車組運用計劃編制等工作更具有指導意義。未來的研究可考慮將其他運輸能力的影響因素(如車站進路沖突等)納入本論文構建的多種資源協(xié)同運用框架中，完善和豐富本論文提出的運輸能力計算方法。