基于安全約束的客站晚點(diǎn)列車到發(fā)線分配優(yōu)化

劉　偉，朱曉寧

(北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044)

數(shù)字出版日期： 2017-04-24

0　引言

安全是鐵路運(yùn)輸?shù)幕疽螅氰F路一切工作的基礎(chǔ)。鐵路大型客站的咽喉區(qū)和到發(fā)線的應(yīng)用十分復(fù)雜，車站在接發(fā)車作業(yè)時應(yīng)滿足安全約束、行車約束等。針對鐵路運(yùn)輸安全，張殿業(yè)等[1]提出了鐵路運(yùn)輸安全研究的框架體系；范振平等[2]分析了鐵路運(yùn)輸生產(chǎn)中的不利因素，探討了鐵路安全預(yù)警系統(tǒng)的實(shí)現(xiàn)。在車站安全作業(yè)的要求下，車站到發(fā)線作為鐵路客運(yùn)站基礎(chǔ)設(shè)施的關(guān)鍵資源和重要組成部分，在接、發(fā)車作業(yè)中發(fā)揮著不可替代的作用[3-6]。針對鐵路車站到發(fā)線作業(yè)優(yōu)化問題，國內(nèi)外學(xué)者建立了相關(guān)數(shù)學(xué)優(yōu)化模型，如Carey等[7]構(gòu)建了到發(fā)線分配優(yōu)化的混合整合規(guī)劃模型；Zwaneveld等[8]采用點(diǎn)包裝問題描述到發(fā)線運(yùn)用問題，建立了0-1整數(shù)規(guī)劃模型；Cardillo等[9]基于客運(yùn)站的到發(fā)線分配優(yōu)化，建立圖染色模型。此外，Billionnet等[10]定義相容進(jìn)路集，將車站到發(fā)線優(yōu)化視為帶有權(quán)重的點(diǎn)包裝問題，構(gòu)造了無向圖，采用分支定界法求解。Li等[11]建立了鐵路客站到發(fā)線選擇的優(yōu)化模型，將車站的作業(yè)能力作為約束條件，并使用K短路算法進(jìn)行求解。D’Ariano等[12-13]通過模擬人工調(diào)度，針對復(fù)雜車站列車到發(fā)線運(yùn)用調(diào)整問題設(shè)計相應(yīng)啟發(fā)式算法。

在保障列車進(jìn)站作業(yè)安全的條件下，通過提高旅客列車的準(zhǔn)點(diǎn)率，采取動態(tài)時刻表的方式，可優(yōu)化車站作業(yè)，消除列車在站內(nèi)的作業(yè)沖突，確保行車安全[14-15]。Huisman等[16]研究不確定列車運(yùn)行圖問題，考慮線路通過能力，根據(jù)防沖突的疏解原則建立了列車進(jìn)出站模型；Burdet等[17]對車站能力進(jìn)行評估，并設(shè)計隨機(jī)貪婪搜索算法計算車站最大通過能力；Castillo等[18]和Corman等[19]基于列車運(yùn)行圖，優(yōu)化列車進(jìn)出站路徑。

隨著列控技術(shù)的發(fā)展，鐵路技術(shù)裝備水平的提升，鐵路安全行車和準(zhǔn)點(diǎn)率水平顯著提高。然而，由于鐵路運(yùn)輸網(wǎng)絡(luò)的開放性和運(yùn)輸組織工作的復(fù)雜性，存在各種不確定因素的干擾，如車站設(shè)備故障、出現(xiàn)極端天氣、區(qū)間線路損壞、節(jié)假日旅客集中進(jìn)站上車和臨客的大規(guī)模開行等，造成不同規(guī)模、不同程度的晚點(diǎn)，車站到發(fā)線分配又受制于各種安全條件約束，因而需要根據(jù)實(shí)際情況及時調(diào)整到發(fā)線使用，避免列車晚點(diǎn)傳播。因此，基于安全約束對列車晚點(diǎn)情況下的到發(fā)線調(diào)整優(yōu)化具有重要的實(shí)用價值。鑒于此，本文研究基于安全約束的客站晚點(diǎn)列車到發(fā)線分配優(yōu)化。采用混合整數(shù)建模方法建立優(yōu)化模型，設(shè)計模擬退火算法進(jìn)行求解，并以寶雞站為例進(jìn)行案例分析。

1　基于安全約束的到發(fā)線分配優(yōu)化模型

1.1　問題提出

如圖1所示，正點(diǎn)情況下列車T3到達(dá)車站時刻t1，離開車站時刻t5，停留Ⅰ道；T1到達(dá)車站時刻t2，離開車站時刻t3，停留Ⅱ道；T2到達(dá)車站時刻t4，離開車站時刻t6，停留Ⅱ道。當(dāng)列車T1晚點(diǎn)至t4到達(dá)，此時出現(xiàn)列車進(jìn)站安全沖突，列車T1與T2在滿足安全約束條件下的進(jìn)站的先后次序，在實(shí)際接發(fā)車作業(yè)過程中是一個優(yōu)化決策問題。此外，后進(jìn)站列車T1(或T2)停留在Ⅰ道還是Ⅱ道(待T3離站)，也是一個決策優(yōu)化。以上示例僅考慮兩條到發(fā)線，一列車發(fā)生晚點(diǎn)的到發(fā)線優(yōu)化調(diào)整問題。在實(shí)際作業(yè)中列車晚點(diǎn)時有發(fā)生，且當(dāng)問題的規(guī)模逐漸擴(kuò)大(到發(fā)線數(shù)、列車數(shù)、晚點(diǎn)車數(shù))，同樣需要滿足安全條件約束，該組合優(yōu)化問題的復(fù)雜度呈幾何增長。為此，本文研究基于安全約束的客站晚點(diǎn)列車到發(fā)線分配優(yōu)化，可為該問題提供科學(xué)的理論依據(jù)。

圖1　鐵路車站列車晚點(diǎn)示意Fig.1　Train delay in a railway station

1.2　數(shù)學(xué)模型

1.2.1模型假設(shè)

模型建立基于以下假設(shè)：不存在行車事故，站內(nèi)設(shè)施設(shè)備均能正常使用；任意列車遍歷咽喉區(qū)單個道岔占用時間已知；前后兩列列車進(jìn)入同一到發(fā)線的安全時間間隔為常量。

1.2.2集合符號定義

集合定義：車站道岔組集合D，任意道岔組d∈D，D={d|d=1,2,...,n}，其中n為道岔組總數(shù)；階段計劃內(nèi)到發(fā)列車集合L，任意列車l∈L，L={l|l=1,2,...,m}，其中m為該階段計劃內(nèi)的列車到發(fā)總數(shù)；車站到發(fā)線集合，任意到發(fā)線g∈G，G={g|g=1,2,...,r}，其中r為到發(fā)線總數(shù)。

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

(1)

(2)

判斷列車l晚點(diǎn)到達(dá)車站時，預(yù)設(shè)到發(fā)線g是否空閑。?g,g′∈G,?l∈L：

(3)

式(3)表示列車是否進(jìn)入預(yù)設(shè)到發(fā)線。正點(diǎn)情況下列車l進(jìn)入預(yù)設(shè)到發(fā)線g，當(dāng)發(fā)生晚點(diǎn)后需判斷到發(fā)線g是否空閑。若到發(fā)線g空閑則晚點(diǎn)列車l可進(jìn)入該到發(fā)線；若到發(fā)線g繁忙則晚點(diǎn)列車需等待或另行分配。引入0～1變量αl，?g,g′∈G,?l∈L：

(4)

式(4)表示列車是否進(jìn)入原到發(fā)線。當(dāng)αl=1，則列車l進(jìn)入預(yù)設(shè)到發(fā)線；反之，需另行分配到發(fā)線。

其次，判斷該時刻是否有多列車同時到達(dá)，?g,g′∈G,?l∈L：

(5)

引入指標(biāo)函數(shù)f(αl,βg)：

f(αl,βg)=αl+βg

(6)

式(6)表示對列車到發(fā)線分配的方案設(shè)置。根據(jù)f(αl,βg)大小，對車站列車出現(xiàn)晚點(diǎn)情況下的到發(fā)線再分配計劃設(shè)閾值，根據(jù)閾值的大小，嵌入表1的操作。

表1　不同情況下的列車進(jìn)站操作

針對有多列車同時進(jìn)站，且其預(yù)設(shè)到發(fā)線相同的情況下，考慮列車權(quán)重系數(shù)wl。列車權(quán)重系數(shù)wl越大，安排其進(jìn)入預(yù)設(shè)到發(fā)線的可能性越大。當(dāng)出現(xiàn)表1中的情況2時，權(quán)重系數(shù)wl最大的列車進(jìn)入到發(fā)線g，其余列車另行分配。當(dāng)出現(xiàn)情況4時，根據(jù)不同列車的權(quán)重大小，逐一分配到發(fā)線。情況1和3由于只存在一列列車，因此，權(quán)重系數(shù)不必考慮。

對晚點(diǎn)情況下的列車進(jìn)站咽喉利用和到發(fā)線分配，本文以列車二次延誤時間最小化為目標(biāo)，考慮各趟列車的權(quán)重大小，目標(biāo)函數(shù)如公式(7)：

(7)

1.2.4模型約束條件

1)進(jìn)站道岔組安全約束

(8)

2)停站到發(fā)線安全約束

(9)

式(9)表示到發(fā)線占用安全約束。為確保進(jìn)站作業(yè)安全，1個時間段內(nèi)，1條到發(fā)線只能接發(fā)1列列車。

3)進(jìn)站列車必須安排到發(fā)線約束

(10)

式(10)表示必須給進(jìn)站列車l安排一條到發(fā)線進(jìn)行停站作業(yè)。

4)出站道岔組安全約束

(11)

5)防沖突安全約束

(12)

式(12)表示列車進(jìn)站防沖突安全約束，一般而言列車進(jìn)入到發(fā)線前要求到發(fā)線已清空。具體要求到發(fā)線的占用時段間需要有一段安全間隔時間，防止列車之間發(fā)生進(jìn)、出站沖突。Tmin表示最小安全時間間隔。

2　模擬退火算法

客站咽喉利用與到發(fā)線分配優(yōu)化問題是一類NP-hard問題，問題復(fù)雜度高且較難求解，本文采用基于模擬退火算法的啟發(fā)式算法求解以上模型。模擬退火算法的解的表示與迭代如圖2所示，解的橫軸表示到發(fā)線號，縱軸表示列車。單一父代解產(chǎn)生子代解的方法：通過變異任一列車的停站到發(fā)線，并檢查是否滿足約束條件，決定是否保留該子代解。兩個父代解產(chǎn)生子代解的方法：兩個父代解通過交換某列車的停站到發(fā)線生成兩個子代解，檢查子代解是否滿足約束，若滿足則保留該子代解。通過比較上述解的優(yōu)劣，選擇性保留最優(yōu)解作為下一次迭代的開始。

具體求解步驟如下：

第1步，初始化。

1)初始輸入。初始溫度值T0，算法停止溫度τ，降溫系數(shù)ω以及馬爾科夫鏈長度L為算法的初始輸入值。

2)基礎(chǔ)數(shù)據(jù)讀取。讀取車站咽喉結(jié)構(gòu)，輸入咽喉道岔組占用時間以及安全間隔時間ΔT、Tmin，列車的時刻及晚點(diǎn)時間。

3)產(chǎn)生初始解。初始化當(dāng)前溫度T=T0，隨機(jī)產(chǎn)生初始解s0，計算目標(biāo)函數(shù)值f(0)，檢查約束條件公式(8)～(12)，若滿足條件保留該初始解，如果不滿足通過交叉產(chǎn)生新解，直至滿足約束條件。

圖2　模擬退火算法解的表示Fig.2　Solution expressions of the simulated annealing algorithm

圖3　寶雞車站站場示意Fig.3　Map of the station bottleneck structure (Baoji, China)

第2步，迭代優(yōu)化。

1)產(chǎn)生新解。初始解通過交換某列車的停站到發(fā)線生成一個新的子代解，兩個父代解通過交換某列列車的停站到發(fā)線產(chǎn)生兩個新子代解sn

2)新解判斷。判斷以上子代解是否滿足約束條件(8)～(12)，并計算滿足約束條件解的目標(biāo)函數(shù)值f(η)，計算當(dāng)前解與前解的目標(biāo)函數(shù)之差Δf，Δf=f(η)-f(η-1)。若Δf≤0，則sn替換sn-1，否則采用隨機(jī)概率事件讓sn替換sn-1，概率為ρ=exp(-Δf/T)。

3)迭代終止判斷。對于當(dāng)前溫度T，如果T≤τ，停止；否則更新T=T×ω，繼續(xù)進(jìn)行下一次迭代。

3　實(shí)例研究

為了測試模型與算法的有效性，選取寶雞車站作為案例進(jìn)行研究與分析。圖3為寶雞站站場示意圖，其中到發(fā)線11條(股道VII，VIII號為正線)，道岔組28組。寶雞車站分為左右兩側(cè)咽喉，左側(cè)咽喉由奇數(shù)號道岔組構(gòu)成(1-3-5-…-25)，右側(cè)咽喉由偶數(shù)號道岔組構(gòu)成(2-4-6-…-28)，表2為列車時刻表相關(guān)信息。

表2　寶雞車站部分列車初始時刻

注：由于缺乏實(shí)際的列車延誤數(shù)據(jù)，本表采用正態(tài)分布模擬了列車延誤概率及時長。

3.1　延誤處理

為表示列車是否延誤，采用延誤概率計算。本文假設(shè)列車的延誤概率成正態(tài)分布，如表2所示，設(shè)為該列車的延誤概率。

(γl-1)·M≤(δl-Xl)≤γl·M

(13)

式(13)表示延誤列車。其中，M為極大整數(shù)；γl為0-1變量，表示列車l是否按延誤處理。若γl=1，則按延誤處理；若γl=0則按正點(diǎn)處理。當(dāng)延誤概率δl大于等于閾值Xl時，γl=1；否則，γl=0。

εl′=εl·γl

(14)

式(14)表示列車延誤時長。εl為列車的預(yù)設(shè)延誤時長，根據(jù)延誤概率計算列車的延誤時長εl′。

3.2　優(yōu)化結(jié)果

取Xl為0.5，對表3中列車延誤概率及延誤時長進(jìn)行統(tǒng)計，延誤列車數(shù)12列，延誤總時長333 min。到發(fā)線的占用頻次分別為[2 1 3 3 2 2 2 5 3 3 2]，其中，到發(fā)線8占用頻次最高，為5次；到發(fā)線2占用頻次最低，為1次；其余各條到發(fā)線均占用2到3次不等。

表3　列車延誤后到發(fā)線分配及道岔組組成優(yōu)化結(jié)果

3.3　延誤時長分析

改變列車延誤總時長，分析列車延誤時長對車站到發(fā)線分配的影響。將列車延誤數(shù)量逐一疊加，產(chǎn)生變化的延誤總時長。根據(jù)寶雞車站的列車運(yùn)行時刻表，假設(shè)列車延誤數(shù)量是離散變量，變量值范圍為1～7，統(tǒng)計相應(yīng)的延誤時間，分別從30～202 min，優(yōu)化后的結(jié)果見表4。發(fā)現(xiàn)隨著列車延誤總時長的增加，列車的二次延誤時長呈(準(zhǔn))對數(shù)函數(shù)遞增。

表4　列車延誤總時長分析

3.4　延誤時長與延誤車數(shù)熱力分析

列車調(diào)度優(yōu)化中準(zhǔn)點(diǎn)率是一個非常重要的指標(biāo)。隨著延誤列車數(shù)量的遞增(如受到延誤傳播的影響)，二次延誤時長勢必增加。造成列車二次延誤的原因除了受車站資源有限影響，也跟列車晚點(diǎn)時長相關(guān)。因此，分析延誤列車數(shù)量與列車延誤時長之間的熱力關(guān)系，能夠給調(diào)度工作者一定的科學(xué)指導(dǎo)。在此，假定列車延誤數(shù)量按線性增加，即1到N；各次列車的延誤時長亦呈線性遞增關(guān)系，即5到t′ min。

圖4　列車延誤數(shù)量與延誤時長對二次延誤的影響Fig.4　Influence of the number of delayed trains and delay times on the second-delay times

測試以上實(shí)驗數(shù)據(jù)，得到圖4和表5所示結(jié)果。發(fā)現(xiàn)當(dāng)列車延誤時長較短時(如2 min)，隨著延誤車數(shù)的增加，列車二次延誤時間遞增較緩慢。該結(jié)果說明寶雞車站的列車到達(dá)間隔時間預(yù)留較合理，滿足車站接發(fā)車安排作業(yè)的魯棒性特征。當(dāng)列車延誤時長增加至10 min時，延誤車數(shù)的影響逐漸凸顯。而當(dāng)列車延誤時長突增至24 min時，只需幾列列車延誤，便會造成長時間的二次延誤。以上結(jié)論說明，調(diào)度在安排列車晚點(diǎn)情況下的到發(fā)線分配作業(yè)時，首先建議考慮列車的延誤時長，當(dāng)延誤時長較長時，需要優(yōu)先解決延誤車數(shù)問題，即優(yōu)先安排非延誤列車的進(jìn)站作業(yè)；當(dāng)延誤時長在可控范圍內(nèi)，可以遵循“先到先服務(wù)”(First-in-first-service)原則，逐一安排到站列車完成到、發(fā)作業(yè)。

表5　二次延誤時長

4　結(jié)論

1)建立了列車到發(fā)線分配優(yōu)化混合整數(shù)規(guī)劃模型，設(shè)計了模擬退火算法求解該大規(guī)模NP-hard問題。

2)以寶雞車站案例分析表明，當(dāng)列車晚點(diǎn)時間較短情況下，列車依次進(jìn)站作業(yè)一般能滿足安全約束，可采取“先到先服務(wù)”原則，當(dāng)有多列列車晚點(diǎn)且時間較長時，在滿足安全約束條件下，優(yōu)先安排非晚點(diǎn)列車進(jìn)站作業(yè)才能有效避免晚點(diǎn)傳播。

[1]張殿業(yè), 金鍵, 楊京帥. 鐵路運(yùn)輸安全理論與技術(shù)體系[J]. 中國鐵道科學(xué),2005(5):114-118.

ZHANG Dianye, JIN jian, YANG Jingshuai. Railway transportation safety theory and technology system[J], China Railway Science, 2005(5):114-118.

[2]范振平, 林柏梁, 李俊衛(wèi).鐵路局安全預(yù)警系統(tǒng)的研究[J].交通運(yùn)輸系統(tǒng)工程與信息,2006(12):149-152.

FAN Zhenping, LIN Boliang, LI Junwei. Study on security early warning system of railroad bureau[J]. Journal of Transportation Systems Engineering and Information Technology, 2006(12):149-152.

[3]Kang L J, Wu J J, Sun H J. Using simulated annealing in a bottleneck optimization model at railway stations. Journal of Transportation Engineering [J]. 2012, 138: 1396-1402.

[4]張嘉敏, 韓寶明. 鐵路列車占用車站股道時序優(yōu)化研究[J]. 交通運(yùn)輸系統(tǒng)工程與信息, 2011,11(3): 100-107.

ZHANG Jianmin, HAN Baoming. Optimization on the occupation order for trains on tracks of the railway station[J]. Journal of Transportation Systems Engineering and Information Technology, 2011, 11(3): 100-107.

[5]青學(xué)江,馬國忠.遺傳算法在區(qū)段站到發(fā)線的應(yīng)用研究[J]. 西南交通大學(xué)學(xué)報, 1998(4): 387-393.

QING Xuejiang. MA Guozhong. Application of GA to arrival and departure lines in district stations[J]. Journal of Southwest Jiaotong University, 1998(4): 387-393.

[6]雷定猷, 王棟, 劉明翔. 客運(yùn)站股道運(yùn)用優(yōu)化模型及算法[J]. 交通運(yùn)輸工程學(xué)報, 2007(5):84-87.

LEI Dingyou, WANG Dong, LIU Mingxiang. Optimization model and algorithm of utilization of arrival and departure tracks in railroad passenger station [J]. Journal of Traffic and Transportation Engineering, 2007(5): 84-87.

[7]Carey M. A model and strategy for train pathing with choice of lines, platforms, and routes [J]. Transportation Research Part B Methodological, 1994, 28(5):333-353.

[8]Zwaneveld P J, Ambergen H W. Routing trains through railway stations: Model Formulation and Algorithms [J]. Transportation Science, 1996, 30(3):181-194.

[9]Cardillo D D L, Mione N. k L-list colouring of graphs [J]. European Journal of Operational Research, 1998, 106(1):160-164.

[10]Billionnet A. Using integer programming to solve the train-platforming problem [J]. Transportation Science, 2003, 37(2):213-222.

[11]Li Y, Zhao J, Cheng J. Model and algorithm for passenger station task allocation problem in railway terminal [J]. Journal of Transportation Engineering, 2010, 2590-2596.

[12]D’Ariano A, Dario, P. Assessment of flexible timetables in real-time traffic management of a railway bottleneck [J]. Transportation Research Part C. 2008, 16:232-245.

[13]Andrea DA, Dario P. Assessment of flexible timetables in real time traffic management of a railway bottleneck [J]. Transportation Research Part C, 2008, 16: 232-245.

[14]Delorme X, Gandibleux X, Rodriguez J. GRASP for set packing problems [J]. European Journal of Operational Research, 2004, 153(3): 564-580.

[15]Zwaneveld P J, Kroon LG, Hoesel S P M V. Routing trains through a railway station based on a node packing model [J]. European Journal of Operational Research, 2001, 128(1):14-33.

[16]Huisman T, Boucherie R J. Running times on railway sections with heterogeneous train traffic [J]. Transportation Research Part B, 2001, 35 (3): 271-292.

[17]Burdet T R L, Kozan E. A disjunctive graph model and framework for constructing new train schedules [J]. European Journal of Operation Research, 2010, 200(1):85-98.

[18]Castillo E, Gallego I, Uuena G J, Time tabling optimization of a mixed double and single tracked railway network [J]. Applied Mathematical Modeling, 2011, 35(2):859-878.

[19]Corman F, Dariano A, Pacciarelli D. A tabu search algorithm for rerouting trains during rail operations [J]. Transportation Research Part B: Methodological, 2010, 44(1):175-192.