維修天窗與列車運行圖一體化編制模型

穆策，孟令云，廖正文，冉鋒，王輝

維修天窗與列車運行圖一體化編制模型

穆策1, 2，孟令云1, 2，廖正文1, 2，冉鋒3，王輝4

(1. 北京交通大學(xué) 交通運輸學(xué)院，北京 100044；2. 北京交通大學(xué) 軌道交通控制與安全國家重點實驗室，北京 100044；3. 天津南環(huán)鐵路有限公司，天津 300204；4. 天津南環(huán)鐵路維修有限責(zé)任公司，天津 300331)

針對維修天窗的開設(shè)方式、維修開始時間和維修時長靈活性較高，不同的維修天窗計劃對鐵路的通過能力、行車組織方式具有不同程度的影響。目前，大多采用分步規(guī)劃的方法對列車運行圖和維修天窗進行編制，并且未涉及維修作業(yè)引起的列車運行限速對列車運行圖編制的影響問題，導(dǎo)致維修天窗編制質(zhì)量較低?？紤]將維修天窗與列車運行圖一體化編制，以求得一個更加合理的維修天窗計劃和列車運行圖。基于混合整數(shù)規(guī)劃法建立一體化編制模型，考慮雙線鐵路中維修作業(yè)引起的列車運行限速，并以某路網(wǎng)為背景，利用CPLEX求解軟件對模型進行驗證。

維修天窗；列車運行圖；一體化；混合整數(shù)規(guī)劃；限速

1 問題的提出

為了保證列車的運行安全，日常鐵路生產(chǎn)活動中需要制定維修計劃，定期對線路股道、供電、信號等固定設(shè)備設(shè)施進行日常維護和檢修，以確保列車安全高效的運行。為了保證維修作業(yè)的安全有序進行，線路維修期間不允許列車占用相應(yīng)行車資源，從而形成“天窗”，而維修天窗的開設(shè)方式、維修開始時間和維修時長的靈活性對鐵路的通過能力、行車組織方式具有不同程度的影響。例如：V形“天窗”較垂直“天窗”通過能力損失較小，列車旅行速度較高，但并不能保證所有供電設(shè)備都得到維修，因此，某些供電設(shè)備需要全線停電施工維修，還需在月度計劃中另行安排垂直天窗進行維修作業(yè)補遺。在我國鐵路運輸資源有限的情況下，如何在滿足維修作業(yè)需求的同時，將其對列車運行的影響降到最低，一直是專家和學(xué)者研究的重點和熱點。既有的對于維修天窗優(yōu)化的研究可以分為3類：1) 不考慮維修天窗的列車運行圖編制研究，一般以最小運輸成本或者總旅行時間最小為目標(biāo)函數(shù)，代表學(xué)者有：彭其淵[1]，史峰[2?3]，黃鑒[4]和Caimi[5]等；2) 不考慮列車運行圖的維修天窗編制研究，一般以維修費用或者維修時間最小為目標(biāo)函數(shù)，代表學(xué)者有：魏滟玲[6]，李凱[7]和校磊[8]等； 3) 考慮維修天窗的列車運行圖編制研究，一般以維修費用最小且運輸效率最高為目標(biāo)函數(shù)，代表學(xué)者有：趙麗珍[9]，羅建[10]，劉敏[11]，楊奎[12]，彭其 淵[13]和Boland[14?15]等。既有研究大多是將列車運行圖和維修天窗編制單獨作為目標(biāo)進行考慮，而其中又往往將列車運行圖編制問題看作主要矛盾，將維修天窗作為已知條件和模型輸入，淡化了維修天窗的規(guī)劃。同時，維修任務(wù)完成后所產(chǎn)生的列車放行條件的限制，也將影響列車運行圖的編制，而既有研究中對此問題研究較少。設(shè)置合理的維修天窗，即有利于保證維修作業(yè)的連續(xù)性、安全性和維修質(zhì)量，又可避免天窗規(guī)劃質(zhì)量低下導(dǎo)致列車運行不均衡、旅行速度降低等不利影響。本文采用混合整數(shù)規(guī)劃的方法建立維修天窗與列車運行圖一體化編制模型，重點研究雙線鐵路中維修作業(yè)引起的列車運行限速問題，統(tǒng)籌兩者之間的關(guān)系，協(xié)同編制，對提高列車運行效率具有非常重要的實用意義。

2 問題描述

2.1 不同維修天窗編制方法分析

維修天窗的編制主要分為2種：1) 將維修天窗與列車運行圖分步編制，而其中又以先對列車運行圖進行編制，然后結(jié)合所得的列車運行圖特點再進行維修天窗編制為主，此方法往往需要經(jīng)過多次調(diào)整才可確定較優(yōu)的維修天窗計劃，如圖1(a)所示；2) 將維修天窗與列車運行圖協(xié)同優(yōu)化編制，綜合考慮兩者之間的約束，得到最優(yōu)的維修天窗計劃，如圖1(b)所示。前者的編制過程是在不斷的循環(huán)調(diào)整中尋求所有已知調(diào)整方案中的最優(yōu)，而后者的編制過程可以直接得到整體最優(yōu)的結(jié)果。通過比較圖1(a)和1(b)，可以看出1(b)中因維修天窗開設(shè)而受影響的列車少于1(a)。可見，一體化編制即可以提高維修天窗和列車運行圖質(zhì)量，又可以提高編制效率。

圖1 維修天窗的不同編制方法對比

2.2 限速規(guī)則分析

依據(jù)鐵運[2012]280號文件[16]，為了保證維修作業(yè)安全進行及檢驗維修質(zhì)量，需要根據(jù)維修任務(wù)的不同特點，對維修作業(yè)進行中和維修完成后的列車運行設(shè)置不同的放行條件，采取限速措施。維修作業(yè)引起的列車限速分為本線限速和鄰線限速2種形式。

本線限速指的是當(dāng)維修任務(wù)完成后，需對經(jīng)過維修區(qū)段的列車設(shè)置放行條件，利用逐步提速恢復(fù)至正常限速的方式，達到檢驗維修作業(yè)質(zhì)量，保證行車安全的目的。例如：維修完成后，恢復(fù)行車的第1列列車限速60 km/h，第2列列車限速80 km/h，第3列列車限速120 km/h，第4列列車恢復(fù)正常限速等。不同的維修任務(wù)具有不同的放行標(biāo)準(zhǔn)。

鄰線限速指的是雙線鐵路中，一條線路區(qū)段在進行維修作業(yè)時，為了保證維修人員的安全和維修作業(yè)的安全進行，需對經(jīng)過另一條線路相應(yīng)區(qū)段的列車進行限速。維修作業(yè)完成后，結(jié)束鄰線列車限速，恢復(fù)正常行駛速度。其有效作用時間為維修 期間。

2.3 模型說明

模型輸入為路網(wǎng)拓撲結(jié)構(gòu)；列車數(shù)量；各次列車的起訖車站；列車運行徑路；停站方案；正常情況下(不受天窗干擾)列車運行限速；受天窗干擾的列車運行限速；列車始發(fā)時間范圍(在始發(fā)站的最早出發(fā)時刻至最晚出發(fā)時刻之間的時間段)，各個車站的最小停站時分；維修區(qū)段；維修作業(yè)開始時間范圍(維修作業(yè)最早開始時刻至最晚開始時刻之間的時間段)以及維修作業(yè)最小時長。

模型輸出為列車在其運行徑路上各個車站的到達和出發(fā)時刻；維修開始時刻和維修結(jié)束時刻。

3 維修天窗與列車運行圖一體化編制模型

3.1 路網(wǎng)描述

為了更好地描述問題，將鐵路路網(wǎng)及行車資源抽象為圖2形式。

圖2 路網(wǎng)及行車資源示意圖

節(jié)點：設(shè)置若干個節(jié)點，可以更清晰的描述路網(wǎng)，圖2中，1，2，3…均表示節(jié)點。

行車資源單元：表示列車進路之間資源占用以及是否存在沖突的最小單元。在站間區(qū)段中，行車資源單元按照閉塞分區(qū)形式進行劃分，如圖2所示，5-101，101-103，103-6等均表示行車單元；而在站內(nèi)，行車資源單元按照進路之間是否存在占用沖突進行劃分，如圖2所示，當(dāng)列車需要占用6-7進行停站作業(yè)時，為了確保行車安全，6-9不能被其他列車占用，因此6-7與6-9屬于同一行車單元，記6-7-9。由此可知，在圖2中，車站2由6-7-9，7-8， 9-10，8-10-11，12-13-14，13-16，14-15，15-16-17等8個行車資源單元組成。

接車進路：表示列車從進站信號機開始到出站信號機結(jié)束的走行徑路，由行車資源單元組成。進路采用非分段解鎖的形式進行接車，即：從列車進入行車資源單元開始進行鎖閉至列車完全離開進站進路結(jié)束鎖閉，期間不允許其他任何列車占用該進路。如圖2所示，6-8，6-10，12-16，12-15等均為接車進路，當(dāng)列車占用6-8進行停站作業(yè)時，從列車經(jīng)過節(jié)點6至列車經(jīng)過節(jié)點7期間，6-10不能接入列車。

發(fā)車進路：表示列車從出站信號機開始至完全離開車站的走行徑路，由行車資源單元組成。與接車進路相同，同樣采用非分段解鎖的形式進行發(fā)車。如圖2所示，8-11，10-11，16-17，15-17等均為發(fā)車進路。

維修區(qū)段：以行車資源單元為最小單位組成的區(qū)段。如圖2所示，6-7需要進行維修作業(yè)，則接車進路6-8，6-10均作為維修區(qū)段進行封鎖；而區(qū)間5-6需要進行維修作業(yè)，則5-101，101-103，103-6均作為維修區(qū)段進行封鎖。

3.2 模型假設(shè)

1) 列車在同一行車資源單元的走行弧段內(nèi)勻速行駛；

2) 本線限速中，只對經(jīng)過維修區(qū)段的第1列和第2列列車進行限速，第3列及后續(xù)列車恢復(fù)正常行駛速度；鄰線限速列車中，本文只考慮列車進入維修區(qū)段鄰線的時刻大于維修開始時刻，且離開時刻小于維修結(jié)束時刻一種情況，其他情況，列車正常行駛；

3) 不考慮列車長度對行車資源單元的占用影響。

3.3 符號說明

表1 集合的符號化表述

表2 決策變量的符號化表述

表3 參數(shù)的符號化表述

3.4 模型建立

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

本文所研究為維修天窗與列車運行圖一體化編制問題，因此，將規(guī)劃時間內(nèi)全部列車旅行時間最小作為目標(biāo)函數(shù)，可以直觀檢驗所建立模型的優(yōu)化效果。

3.4.2 約束條件

為了更好的刻畫問題，將模型約束分為列車運行約束、維修作業(yè)約束和列車限速約束3部分進行表述。

1) 列車運行約束

約束條件(1)表示列車出發(fā)時刻需滿足始發(fā)時間窗要求，適應(yīng)運輸市場需求；約束條件(2)~(3)表示列車在行駛過程中，不能超過最高限制速度要求；約束條件(4)~(5)保證列車行駛過程中的時空連續(xù)性；約束條件(6)保證列車在行駛路徑中有且只能選擇一條徑路；約束條件(7)保證列車1和2在行駛過程中，不同時占用同一行車資源；約束條件(8)~(9)保證列車1和2均需在車站進行停站作業(yè)時，不會同時占用同一到發(fā)線而引發(fā)行車資源占用沖突。

2) 維修作業(yè)約束

本文將維修作業(yè)抽象為一列“虛擬列車”，當(dāng)維修區(qū)段開始維修作業(yè)時，即該“虛擬列車”開始占用該行車資源(即維修區(qū)段)；當(dāng)維修區(qū)段結(jié)束維修作業(yè)時，即該“虛擬列車”結(jié)束占用該行車資源。然后，對其他占用該維修區(qū)段的列車與該“虛擬列車”占用時間先后進行比較判斷，確定需要進行限速的列車，實現(xiàn)對列車的限速。

約束條件(10)保證維修作業(yè)在規(guī)定時間窗內(nèi)開展，降低其對列車運行計劃的影響；約束條件(11)保證維修時長，依據(jù)鐵運280號文件[16]，高速鐵路天窗開設(shè)原則上不少于240 min，普速鐵路雙線不少于120 min；約束條件(12)~(13)保證相鄰的行車資源維修作業(yè)不間斷，降低對行車作業(yè)的影響；約束條件(14)~(16)保證在維修期間，列車不允許經(jīng)過維修區(qū)段，保證維修作業(yè)安全進行。

3) 列車限速約束

圖3 列車經(jīng)過維修區(qū)段示意圖

具體約束如下：

3.4.3 模型變換

本文通過將維修天窗看作“虛擬列車”，并利用該“虛擬列車”與其他列車的關(guān)系，實現(xiàn)了限速列車的判斷，并通過引入輔助0-1變量來降低模型復(fù)雜度，提高求解效率。

4 模型驗證

利用商業(yè)求解軟件IBM ILOG CPLEX 12.3對模型進行求解。CPLEX運行環(huán)境為Intel Core i5- 2430M，CPU(4核心)2.40GHz，4GB RAM的計 算機。

本文以某既有線一部分為背景對模型的可行性進行驗證。該路段共有5個車站，線路示意圖如圖4所示。規(guī)劃時間內(nèi)，計劃開行8列車，列車等級相同，正常行駛限速為150 km/h。其中，上行方向A-E共4列車，下行方向E-A共4列車，列車均在B，C和D站進行停站作業(yè)，最小停站時分分別為5，8和7 min。車站B與C上行方向設(shè)置維修區(qū)段，維修開始時間窗為[0:20,0:50]，維修時長2 h。本線限速中，第1列列車限速60 km/h，第2列列車限速120 km/h；鄰線限速中，列車限速為60 km/h，所以，1=2.5，2=1.25，adj=2.5。

圖4 某線路車站及維修區(qū)段示意圖

利用CPLEX對模型進行求解，經(jīng)過52.29 s求得最優(yōu)解，求解結(jié)果如表4所示，列車運行圖如圖4所示(陰影部分為天窗開設(shè)時間)。求得維修天窗0:20開始，2:20結(jié)束時，列車總運行時間最小。由表4和圖5可知，本線需對列車5和7采取限速措施，鄰線需對列車1采取限速措施，并且由于維修天窗的開設(shè)，使得部分列車在其他區(qū)間也受到 影響。

表4 模型求解結(jié)果

圖5 列車運行圖

5 結(jié)論

1) 利用將維修任務(wù)看作“虛擬列車”占用維修區(qū)段的方法，采用混合整數(shù)規(guī)劃的方法，建立維修天窗和列車運行圖一體化編制模型。

2) 模型通過利用列車經(jīng)過維修區(qū)段以及與“虛擬列車”前后關(guān)系特點，實現(xiàn)了本線限速問題中第1列和第2列列車，以及鄰線限速問題中需采取限速措施列車的判斷，使得模型更加符合實際鐵路生產(chǎn)現(xiàn)場。

3) 針對模型中存在的難約束，引入輔助變量，降低模型復(fù)雜度，提高求解效率。

4) 以某既有線為背景，利用CPLEX求解軟件對模型進行驗證，結(jié)果表明，模型可以更加科學(xué)合理的規(guī)劃維修天窗，在保證維修任務(wù)按時完成的同時，提高路網(wǎng)運輸效率。

[1] 彭其淵, 朱松年. 網(wǎng)絡(luò)列車運行圖的數(shù)學(xué)模型及算法研究[J]. 鐵道學(xué)報, 2001, 23(1): 1?8. PENG Qiyuan, ZHU Songnian. Study on a general optimization model and its solution for railway network train diagram[J]. Journal of the China Rrailway Society, 2001, 23(1): 1?8.

[2] 史峰, 黎新華, 秦進. 單線列車運行調(diào)整的最早沖突優(yōu)化方法[J]. 中國鐵道科學(xué), 2005, 26(1): 106?113. SHI Feng, LI Xinhua, QIN Jin. The earliest conflict optimal method for train operation adjustment on single track railway[J]. China Railway Science, 2005, 26(1): 106?113.

[3] 史峰, 黎新華, 秦進. 單線列車運行圖鋪劃的時間循環(huán)迭代優(yōu)化方法[J]. 鐵道學(xué)報, 2005, 27(1): 1?5. SHI Feng, LI Xinhua, QIN Jin. A timing-cycle iterative optimizing method for drawing single-track railway train diagrams[J]. Journal of the China Railway Society, 2005, 27(1): 1?5.

[4] 黃鑒, 彭其淵. 基于分時客運需求的客運專線列車運行圖優(yōu)化[J]. 鐵道科學(xué)與工程學(xué)報, 2012, 9(6): 66?71. HUANG Jian, PENG Qiyuan. Train diagram optimization of passenger dedicated line based on passenger transport demand in different time[J]. Journal of Railway Science and Engineering, 2012, 9(6): 66?71.

[5] Caimi G, Fuchsberger M, Laumanns M. Periodic railway timetabling with event flexibility[J]. Networks, 2011, 57(1): 3?18.

[6] 魏滟玲. 京廣高速鐵路綜合維修天窗的設(shè)置研究[D]. 成都: 西南交通大學(xué), 2014.WEI Yanling. Research on setting of the Beijing- Guangzhou high-speed railway comprehensive maintenance gap[D]. Chengdu: Southwest Jiaotong University, 2014.

[7] 李凱, 楊彬, 張亞蘭. 高速鐵路分段垂直矩形天窗設(shè)置的探討[J]. 交通運輸工程與信息學(xué)報, 2014(2): 90?95.LI Kai, YANG Bin, ZHANG Yanlan. Discussion on the setting of segmented vertical rectangular window in high-speed railway[J]. Journal of Transportation Engineering and Information, 2014(2): 90?95.

[8] 校磊, 安定. 高速鐵路列車夜間開行維修天窗設(shè)置研究[J]. 鐵道運輸與經(jīng)濟, 2013, 35(9): 58?61. JIAO Lei, AN Ding. Research on setting up night maintenance window for high-speed railway trains[J]. Railway Transport and Economy, 2013, 35(9): 58?61.

[9] 趙麗珍, 趙映蓮, 楊岳勤. 高速鐵路綜合維修“天窗”開設(shè)形式與行車組織協(xié)調(diào)問題的研究[J]. 中國鐵道科學(xué), 2002, 23(2): 127?131.ZHAO Lizhen, ZHAO Yinglian, YANG Yueqin. The study of coordination problems of high-speed railway comprehensive maintenance window forms and the traffic organization[J]. China Railway Science, 2002, 23(2): 127?131.

[10] 羅建, 彭其淵. 綜合維修天窗與列車開行方案的協(xié)同優(yōu)化研究[J]. 鐵道運輸與經(jīng)濟, 2007, 29(8): 65?67.LUO Jian, PENG Qiyuan. Study on collaboratively optimizing the coordination between train running schedule and the comprehensive maintenance gap[J]. Railway Transport and Economy, 2007, 29(8): 65?67.

[11] 劉敏, 朱克非, 李博. 高速鐵路夜行列車開行和天窗設(shè)置優(yōu)化研究[J]. 鐵道運輸與經(jīng)濟, 2015, 37(11): 22?25. LIU Min, ZHU Kefei, LI Bo. Study on optimization of night train operation and maintenance window configuration of high-speed railway[J]. Railway Transport and Economy, 2015, 37(11): 22?25.

[12] 楊奎, 彭其淵, 魯工圓, 等. 高速鐵路天窗設(shè)置與夜間列車運行協(xié)調(diào)優(yōu)化技術(shù)[J]. 鐵道學(xué)報, 2015(4): 1?7.YANG Kui. PENG Qiyuan, LU Gongyuan, et al. Co-optimization between maintenance curfew ang overnight train plan in high speed railway[J]. Journal of the China Railway Society, 2015(4): 1?7.

[13] 彭其淵, 楊奎, 文超, 等. 我國高速鐵路夜間行車組織方法[J]. 西南交通大學(xué)學(xué)報, 2015, 50(4): 569?576.PENG Qiyuan, YANG Kui, WEN Chao, et al. Organization methods of overnight operation for Chinese high-speed railway[J]. Journal of Southwest Jiaotong University, 2015, 50(4): 569?576.

[14] Boland N, Kalinowski T, Waterer H. Mixed integer programming based maintenance scheduling for the hunter valley coal chain[J]. Journal of Scheduling, 2013, 16(6): 649?659.

[15] Boland N, Kalinowski T, Waterer H. Scheduling arc maintenance jobs in a network to maximize total flow over time[J]. Discrete Applied Mathematics, 2014, 163(1): 34?52.

[16] 鐵運[2012]-280號,鐵路營業(yè)線施工安全管理辦法[S].Railway Transportation No.[2012]-280, The rules of railway safe construction management[S].

(編輯 蔣學(xué)東)

Integrated optimization model on maintenance time window and train timetabling

MU Ce1, 2, MENG Lingyun1, 2, LIAO Zhengwen1, 2, RAN Feng3, WANG Hui4

(1. School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China; 2. State Key Laboratory of Rail Traffic Control and Safety, Beijing Jiaotong University, Beijing 100044, China; 3. Tianjin South Circle Railway Cooperation, Tianjin 300204, China; 4. Tianjin Nanhuan Railway Maintenance Co. Ltd, Tianjin 300331, China)

The maintenance time window has features of complexity and diversity, such as the form, starting time, during time, and so on. Therefore, it has different degrees of impact on carrying capacity of trains as well as operation organization. At present, most of previous studies optimize maintenance time window scheduling problem under a given train schedule, and the relevant studies which research speed restriction caused by maintenance are few, leading to a relatively poor quality of maintenance time window schedule and increasing the influence on traffic assignment. In order to reduce the negative effects on maintenance schedule and improve the utilization of railway resources, this paper considered integrating maintenance time window scheduling and train timetabling. More reasonable maintenance time window can be obtained with this way. The paper proposed a mixed integer programming model which focuses on the characteristics of the problem, including the speed limits affects by maintenance tasks on a double-track railway. The benefits of the proposed model are demonstrated by numerical experiments based on CPLEX software.

maintenance time window; train timetabling; integrated optimization; mixed integer programming; speed restriction

10.19713/j.cnki.43?1423/u.2018.08.032

U292.41

A

1672 ? 7029(2018)08 ? 2155 ? 08

2017?06?08

國家自然科學(xué)基金面上資助項目(71571012)

孟令云(1983?)，男，河北唐山人，副教授，博士，從事鐵路運輸組織研究；E?mail：lymeng@bjtu.edu.cn