蘭澤康，何世偉，黎浩東

(北京交通大學城市交通復雜系統(tǒng)理論與技術(shù)教育部重點實驗室，北京100044)

0 引言

當列車出發(fā)晚點、運行晚點、臨時加開列車或列車早點到達等情況發(fā)生時，都會導致列車運行偏離圖定時刻，為了恢復列車安全有序運行，需要采取列車運行調(diào)整措施.目前列車運行調(diào)整研究主要集中于單條線路，限制了調(diào)整的空間，若可以擴展至一定區(qū)域的線路網(wǎng)絡，則可以充分利用其他線路上空閑的資源，達到整體的優(yōu)化效果.但鐵路網(wǎng)絡求解規(guī)模較大，不易快速求解，而列車運行調(diào)整實時性要求較高，故需要設計高效的算法.

在鐵路網(wǎng)絡列車運行圖方面，彭其淵等[1]在列車選擇線路固定條件下，提出采用加邊法求解；Meng等[2]建立鐵路網(wǎng)絡列車運行調(diào)整的MILP模型，利用拉格朗日松弛算法化解成單列車的最短路徑問題；陳雍君等[3]考慮微觀路網(wǎng)的復雜性采用了序優(yōu)化算法；Mu等[4]提出了多種啟發(fā)式方法，包括初始化候選路徑集，以及從路網(wǎng)或列車數(shù)量角度分解成小規(guī)模問題滾動求解的方法.可以看出研究方法大多采取不同的分解策略，達到簡化求解的目的.本文首先在文獻[2]研究成果的基礎上，建立基于列車到發(fā)時刻的MILP模型，再構(gòu)建基于列車時空路徑的ILP模型，設計分支定價方法求解.

1 問題描述與模型假設

1.1 問題描述

相對于單條線路，鐵路網(wǎng)絡的列車運行調(diào)整問題，每一列列車可能有多條行駛線路可以選擇.如圖1所示，是由2條單線鐵路和3個車站組成的調(diào)度區(qū)段，標有數(shù)字的節(jié)點指軌道電路的分界點，連接相鄰兩個節(jié)點的弧段指區(qū)間內(nèi)閉塞分區(qū)或車站內(nèi)股道線路.圖中矩形方框表示相應弧段在某一時間段內(nèi)進行維修作業(yè)，期間不可被列車占用.正常情況下，列車可按照既定的計劃有序地在該網(wǎng)絡上運行.當列車晚點進入調(diào)度區(qū)段時，就可能與其他列車和維修作業(yè)發(fā)生沖突.假設可以變更列車運行線路的條件下，需要重新調(diào)整列車運行計劃，使得列車盡可能按圖定時刻到達終點.

現(xiàn)有研究大多將車站看作是一個點，到發(fā)線數(shù)量約束作為模型的約束條件，如文獻[5].本文考慮車站內(nèi)進路，將到發(fā)線運用和列車時刻表一同優(yōu)化，因此可以不必單獨考慮車站能力約束，但同時也造成求解規(guī)模增大.

1.2 模型假設

假設1將列車看作是一個質(zhì)點，列車可選擇任意1條從始發(fā)節(jié)點到終到節(jié)點的可達路徑，包括更改運行線路和變更站內(nèi)到發(fā)線.

圖1 鐵路網(wǎng)絡示意圖Fig.1 Sketch map of railway network

假設2不考慮停站變動的影響.正線不允許停車，只準在側(cè)線上停車，例如圖1中的2-4、15-16和9-10弧段為側(cè)線.

假設3已知維修作業(yè)的開始時間、結(jié)束時間及作業(yè)地點.每一個維修作業(yè)所占用的弧段是緊鄰的.

2 基于列車到發(fā)時刻的模型建立

2.1 基本符號定義

給定鐵路網(wǎng)絡G=(V,A)，其中V為節(jié)點集合，A為弧段集合，v∈V，a∈A；G內(nèi)所有運行的列車集合為F，f∈F，列車f有唯一索引If=0,1,…,|F|-1；列車f的始發(fā)節(jié)點為of，終到節(jié)點為df；Af為列車f可能通過的弧段集合，As為允許停車的弧段集合；A o(v)和A d(v)分別為以v起點和終點的弧段集合；Rf(a)為列車f在弧段a上的最小運行時間分別為列車f在弧段a(a∈As)上的最小和最大停留時間；h為列車車頭安全間隔時間，即統(tǒng)一所有安全間隔時間為h；Sf為列車f最早可能始發(fā)時間；Ef為列車f圖定終到時間；K為維修作業(yè)集合，k∈K；M為足夠大的正整數(shù).

決策變量sf(a)和ef(a)分別為列車f到達和離開弧段a的時間；yf(a)表示列車f是否通過弧段a的二元變量，是則取值為1，否為0；λ(f,f′,a)為二元變量，當列車f′在f之后通過弧段a時，取值為1，否為0.

2.2 約束條件和目標函數(shù)

(1)流平衡約束.

式(1)和式(2)分別保證列車在始發(fā)節(jié)點和終到節(jié)點的流平衡，式(3)保證列車在中間節(jié)點的流平衡.

(2)最早發(fā)車時間及時間變量相關約束.

式(4)為列車最早允許出發(fā)時間約束；式(5)表示列車離開前一弧段與到達下一相鄰弧段的時間相等；式(6)和式(7)表示當列車f不占用弧段a時，則sf(a)和ef(a)均取值為 0.

(3)最小運行時間和停站時間約束.

式(8)為最小運行時間約束；式(9)和式(10)分別將最小停站時間和最大停站時間附加到弧段運行時間上，以滿足停站時間約束.

(4)安全間距約束.

式(11)表示當列車f和f′都占用弧段a，且f′在f之后占用時，f′到達弧段a時間與f離開弧段a的時間應間隔h，(f,f′)?F表示F中滿足If′＞If的兩列車；式(12)與式(11)同理；式(13)表示當列車f和f′都占用弧段a時，有λ(f,f′,a)+λ(f′,f,a)≥ 1，結(jié)合

式(14)，得到λ(f,f′,a)+λ(f′,f,a)=1，即f在f′之前或之后占用a；式(15)和(16)表示列車f或f′不占用a時，λ(f,f′,a)和λ(f′,f,a)均取值為 0.

(5)維修作業(yè)約束.

式中：Ak為維修作業(yè)k所占用弧段集合分別為維修作業(yè)k的開始時間和結(jié)束時間；zf(k)是二元變量，當列車f在維修作業(yè)k結(jié)束之后通過弧段a(a∈Ak)時，取值為1，f在維修作業(yè)k開始之前通過a或不通過a時均取值為0.

式(17)表示當列車f在維修作業(yè)k結(jié)束之后通過弧段a時，應滿足sf(a)≥moteknd；式(18)表示當列車f在維修作業(yè)k還未開始時通過弧段a，或者不通過a，應滿足ef(a)≤motstartk.

(6)目標函數(shù)及相關約束.

3 基于列車時空路徑的模型建立

為刻畫列車在鐵路網(wǎng)絡上運行的時空路徑，如圖2所示，以鐵路網(wǎng)絡為空間平面，并加上時間軸，形成三維的立體空間.以固定時間長度離散化時間軸，為平衡求解精度和時間，本文取固定時長為1 min.用時間拓展的時空聯(lián)弧(v1,v2,t,s)連接節(jié)點v1和v2，t、s分別表示到達節(jié)點v1和v2的時間，順次連接列車經(jīng)過的所有節(jié)點，即形成1條時空路徑p，p在空間平面上的投影即為列車在鐵路網(wǎng)絡中實際通過的物理路徑.

圖2 列車在鐵路網(wǎng)絡中運行的時空路徑Fig.2 The time-space path of train on a railway network

假設開始調(diào)整的時間為0，調(diào)整時段長為T.令Pf為列車f所有可能的時空路徑集.cf(p)為p(p∈Pf)的費用，若p的終到時間為則cf(p)可按式(23)計算.

xf(p)為列車f是否選擇p(p∈Pf)的二元變量，若選擇則取1，否取0.為滿足列車安全間距要求，需要保證任意弧段在時間段[τ,τ+h-1](τ=1,2,…,T-h)內(nèi)至多被1列列車占用，定義Pf中在該時間段內(nèi)占用弧段a的時空路徑集為Pf(a,τ,τ+h-1).建立基于列車時空路徑的模型M2為

式(24)為目標函數(shù)，表示最小化所需費用；式(25)表示列車f選擇Pf中唯一的1條時空路徑；式(26)確保被選擇的任意2條時空路徑滿足安全間距要求.

模型M2與文獻[5]模型主要有以下幾點不同：①本文定義了每1列列車的可選路徑集，而文獻[5]中只定義了1個可選路徑集；②由于本文考慮了車站內(nèi)軌道電路設置，不必單獨考慮到發(fā)線數(shù)量約束，且不同于文獻[5]以車站到發(fā)間距描述安全間隔，本文以任一弧段不被2列列車同時占用進行描述.

4 求解模型M2的分支定價算法

分支定價算法是一種將列生成算法和分支定界算法相結(jié)合的組合算法.由于列生成算法所得到的解一般不是整數(shù)解，需要借助分支定界算法對非整數(shù)變量分支以獲取整數(shù)解，每個子結(jié)點仍采用列生成算法求解.以下是基于目標函數(shù)為最小化，0-1整數(shù)規(guī)劃問題為前提進行分析的.

4.1 求解線性松弛模型的列生成算法

上述模型M2結(jié)構(gòu)簡單，但缺點在于列車可選時空路徑數(shù)量是非常巨大的，無法一一枚舉，因此采用列生成算法定價生成路徑的方法.首先將M2分解成限制主問題RMP和|F|個子問題，列車f對應的子問題為SPf.令P′f表示Pf的子集，替換M2中的Pf，且將式(27)線性松弛，即構(gòu)成RMP.在RMP求解之后，可以得到對偶最優(yōu)解(μ,λ)，其中μ=(μf)，λ=(λ(τ,a))分別為式(25)和式(26)的對偶變量，則SPf求解模型為

式中：AP為所包含的弧段集合為上弧段a所對應的時空聯(lián)弧在時間軸上投影所包含的時間點集合.

將λ(τ,a)看作是在τ時刻占用弧段a的價格，結(jié)合時空路徑的形成，子問題可轉(zhuǎn)化成求每1列列車的最短路問題，本文最短路算法采用的是文獻[2]中離散時空標號更新算法.若SPf的目標值，則在P′f中添加當前最短路，否則不需要添加.RMP和子問題不斷迭代求解，直至所有子問題都沒有添加新的路徑時終止，可獲得模型M2線性松弛后的最優(yōu)解，它是模型M2的下界值.

4.2 獲取整數(shù)解的分支定界算法

分支求解過程較為耗時，需采用加快算法收斂的分支策略和結(jié)點搜索策略.本文采用的分支策略為偽費用分支[6-7](Pseudocost Branching).其主要思想是給每個變量定義相應的評估值，每次選擇出分支后最有可能使得下界值更快上升變量進行分支.對于一個非整數(shù)變量xi，若對其分支可得目標值對xi變化的敏感度為

式中：c(q)為父結(jié)點的目標值分別為對變量xi上、下取整之后得到子結(jié)點的目標值.

由于xi可能多次被分支，記的累計值分別為累計次數(shù)分別為若子結(jié)點的RMP問題不可行則不予累計，最終xi的評估值按式(30)計算，每次選擇評估值最大的變量進行分支.由于在分支樹的開始階段，大部分變量沒有被分支過，無法計算評估值，可采用強分支(Strong Branching)方法對評估值進行初始化，這里不在贅述，可以參見文獻[6-7].

式 中 ：score(s+,s-)=(1-μ)?min(s+,s-)+μ?max(s+,s-)，μ=1 6.

分支中上取整對目標值的影響較大，也可能是無解的，而下取整對目標值的影響較小，故本文僅對上取整得到的子結(jié)點用列生成算法求解，而下取整的子結(jié)點添加取整約束后用對偶單純形算法求解以獲取目標值，進一步加快算法收斂.為便于后續(xù)論述，記上取整得到的子結(jié)點為右結(jié)點，而下取整得到的子結(jié)點為左結(jié)點.結(jié)點搜索采用最佳優(yōu)先(Best-node First)搜索策略，即每次選擇目標值最小的結(jié)點，使得下界可以更快地上升.

4.3 處理眾多約束條件的行生成方法

4.4 算法流程

算法流程中涉及到的符號定義如表1所示.

Step 1獲得初始可行解和初始化.

按照列車最早可能出發(fā)時間，依次對列車按照最短路算法進行規(guī)劃，獲得可行解的目標值作為UB的初始值，令LB=0.創(chuàng)建1個結(jié)點，以初始可行解建立該結(jié)點的RMP問題，將其加入ANL.

Step 2終止條件.

表1 算法流程中的符號定義Table 1 Notations for the algorithm flow

Step 3結(jié)點選擇.

以最佳優(yōu)先搜索策略從ANL中選擇1個結(jié)點作為當前結(jié)點n，將n從ANL中移除.若n是左結(jié)點，用對偶單純形算法求解RMP(n)，否則用列生成算法求解RMP(n).

Step 4結(jié)點操作判斷.

若RMP(n)不可行或Z(n)≥UB，轉(zhuǎn)Step2；若B(n)=1，更新UB，轉(zhuǎn)Step 2；若B(n)=0，轉(zhuǎn)Step5.

Step 5分支.

按照偽費用分支策略分支，生成右結(jié)點和左結(jié)點，并在RMP(n)的基礎上添加分支變量的取整約束，構(gòu)建相應子結(jié)點的RMP問題，將2個子結(jié)點加入ANL，轉(zhuǎn)Step2.

5 算例分析

5.1 算例數(shù)據(jù)

本文算例設計鐵路網(wǎng)絡共有76個節(jié)點和85個弧段，總長度137.6 km，如圖3所示.維修作業(yè)和部分列車相關數(shù)據(jù)分別如表2和表3所示，列車晚點進入?yún)^(qū)段的時間分布在[0,20]min范圍內(nèi).計劃運行圖中所有列車均未通過交叉渡線(圖3中54-58，56-57，44-47，45-46)，而列車運行調(diào)整后，列車可能通過交叉渡線從一條線路換軌至另一條線路.

表2 維修作業(yè)相關數(shù)據(jù)Table 2 The data for maintenances

圖3 算例的鐵路網(wǎng)絡Fig.3 The railway network for numerical experiment

表3 部分列車相關數(shù)據(jù)Table 3 The data for some trains

5.2 算法性能分析

為分析本文分支定價算法的性能，用2種方法分別求解算例，測試計算機參數(shù)為Intel Pentium CPUB9602.20GHZ，6GB內(nèi)存.求解結(jié)果如表4所示.

(1)IP_GUROBI.運用求解器GUROBI6.5.0求解基于列車到發(fā)時刻的模型.

(2)BAP_C#.運用C#語言實現(xiàn)分支定價方法求解模型M2，以GUROBI作為LP求解器.

求解結(jié)果表明，隨著列車數(shù)量的增多，即求解規(guī)模的增大，IP_GUROBI方法求解越來越困難，列車數(shù)為4列時，5.3 s即可得到最優(yōu)解，當列車數(shù)增加到20列時，求解時間達到3 468 s.在規(guī)模較小時，IP_GUROBI比BAP_C#更具有優(yōu)勢，隨著規(guī)模增大，BAP_C#可以在較短的時間內(nèi)獲得滿意解，如列車數(shù)量為20列時，求解時間減少(3 463.7-290)/3 463.7=91.6%，得到的最終可行解距離最優(yōu)解的間隔為(508-463)/463=9.72%.

在分支策略中，一種較為常用的分支策略是最為分數(shù)分支(Most Fractional Branching)策略，即每次選擇最接近0.5的變量進行分支[6-7].現(xiàn)以列車數(shù)為20列的情況為例，比較本文分支策略和最為分數(shù)分支策略，兩者的上下界收斂曲線如圖4所示.本文分支策略在290 s處收斂，最終收斂目標值為508 min，而最為分數(shù)分支策略在389 s處收斂，最終收斂目標值為515 min，說明了本文分支策略具有一定優(yōu)勢.需要指出，最終收斂時上下界相等并不是得到了最優(yōu)解，因為分支樹中的某些結(jié)點沒有用列生成算法求解.

表4 IP_GUROBI和BAP_C#的求解時間和目標值Table 4 The computational time and objective value for IP_GUROBI and BAP_C#

5.3 可變更線路與按原始線路行駛的比較

本文按原始線路行駛指的是限定列車不能使用交叉渡線，同樣用GUROBI求解得到該種調(diào)整方式的目標值，結(jié)果如圖5所示.可以看出，可變線路相比于按原始行駛線路得到優(yōu)化，目標值降低31.4%～41.9%，平均降低37.4%.

圖4 不同分支策略上下界收斂曲線Fig.4 The upper and lower bound for different branch strategies

圖5 2種列車運行調(diào)整方式的目標值Fig.5 The objective value for two kinds of train rescheduling

6 結(jié)論

本文分別構(gòu)建了基于列車到發(fā)時刻和基于列車時空路徑的鐵路網(wǎng)絡列車運行調(diào)整模型，前者適用于商業(yè)軟件求解，可獲取最優(yōu)解.結(jié)合后者模型的特點，設計了分支定價算法求解，對比得出隨著求解規(guī)模的增大，本文算法求解時間變化較為平緩，且能夠得到較優(yōu)解，表現(xiàn)出更好地適應性.同時得出本文分支策略比最為分數(shù)分支策略可以更快地使算法收斂，可變更線路相對于按照原始線路行駛的調(diào)整方式可降低目標值31.4%～41.9%.

[1]彭其淵，朱松年，王培.網(wǎng)絡列車運行圖的數(shù)學模型及算法研究[J].鐵道學報，2001，23(1):1-8.[PENG Q Y，ZHU S N，WANG P.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.]

[2]MENG L Y，ZHOU X S.Simultaneous train rerouting and rescheduling on an N-track network:a model reformulation with network-based cumulative flow variables[J].Transportation Research Part B Methodological，2014，67(3):208-234.

[3]陳雍君，周磊山.基于序優(yōu)化方法的列車運行調(diào)整算法研究[J].鐵道學報，2010，32(3):1-8.[CHEN Y J，ZHOU L S.Study on train operation adjustment algorithm based on ordinal optimization[J].Journal of the China Railway Society，2010，32(3):1-8.]

[4]MU S，DESSOUKY M.Scheduling freight trains traveling on complex networks[J].Transportation Research Part B Methodological，2011，45(7):1103-1123.

[5]CACCHIANI V，CAPRARA A，TOTH P.A column generation approach to train timetabling on a corridor[J].4or Quarterly Journal of the Belgian French&Italian Operations Research Societies，2008，6(2):125-142.

[6]ACHTERBERG T，KOCH T，MARTIN A.Branching rules revisited[J].Operations Research Letters，2005，33(1):42-54.

[7]FRIBERG D.An implementation of the branch-and price algorithm applied to opportunistic maintenance planning[D].Gothenburg:University of Gothenburg，2015.