韓寶明，孫士釗，鄭 玢，張 琦

(1.北京交通大學(xué)交通運輸學(xué)院，北京 100044；2.中鐵工程設(shè)計咨詢集團有限公司，北京 100055)

高速夜行列車車底運用及優(yōu)化方法研究

韓寶明1，孫士釗1，鄭 玢2，張 琦1

(1.北京交通大學(xué)交通運輸學(xué)院，北京 100044；2.中鐵工程設(shè)計咨詢集團有限公司，北京 100055)

高速夜行列車在運用時間范圍和運用時間跨度方面都與現(xiàn)有高速動車組存在較大差異，因而導(dǎo)致諸多運用條件發(fā)生改變。在總結(jié)夜行列車車底運用問題特征的基礎(chǔ)上，將該問題求解過程劃分成基本交路生成和完整循環(huán)交路生成兩個階段，其中前者作為后者模型的輸入。構(gòu)建以車底運用不均衡度和非配屬地檢修次數(shù)最小為目標(biāo)的數(shù)學(xué)優(yōu)化模型，通過改進的深度優(yōu)先搜索算法進行求解，并以京廣線為背景對模型和算法進行驗證。結(jié)果表明，針對我國鐵路實際該方法能有效解決夜行列車車底周轉(zhuǎn)運用問題，可為我國夜行列車的開行提供技術(shù)支持。

夜行列車；運用模式；交路計劃；深度優(yōu)先搜索算法

近些年，隨著國家快速鐵路網(wǎng)絡(luò)日漸完善，在高速鐵路上開行夜行列車的基礎(chǔ)條件已經(jīng)具備。由于高速鐵路運行速度更快，城市之間的通達(dá)時間大大縮短，一些距離短的城市之間已沒有開行夜行列車的必要，而另外約有32.8%距離在2 000 km以上的城市之間列車進入夜行列車優(yōu)勢到發(fā)時間范圍[1]，因此組織開行高速夜行列車尚有很大需求并十分必要。

高速夜行列車也稱高速夕發(fā)朝至列車或高速夜行動車組(以下簡稱夜行列車)。由于我國高速鐵路綜合維修天窗設(shè)置在夜間，全線(或分段)雙向同時停電檢修，從而直接制約了夜行列車在夜間的運行。針對這個問題不少學(xué)者做了可行性研究[2-3]，并從壓縮天窗時長和調(diào)整天窗布置形式等方面提出了解決措施[4-5]，為后續(xù)的研究奠定了基礎(chǔ)。在此基礎(chǔ)上，有學(xué)者進一步對夜行列車開行方案進行了探討[6-7]。此外，針對動車組運用和優(yōu)化方面的研究大都局限在日間動車組，即動車組在日間運行，夜間檢修。這種模式下的動車組運用和優(yōu)化相關(guān)理論成果較為豐碩，其中文獻[8-11]進行了較為系統(tǒng)的研究和總結(jié)。而目前，對于夜行列車車底運用問題的研究還較為少見。

夜行列車由于其運用時間范圍(17：00—次日9：00)和運用時間跨度(6 h以上)與現(xiàn)有高速動車組存在較大差異，導(dǎo)致一系列運用條件發(fā)生改變，因此不能簡單套用既有的模型和算法。在借鑒既有方法的基礎(chǔ)上，提出該問題的分解策略，針對新的運用條件，重新建立雙目標(biāo)優(yōu)化模型，通過改進的深度優(yōu)先搜索算法得以求解夜行列車車底周轉(zhuǎn)運用問題。最后以京廣高速夜行列車為例進行實例驗證，證明了方法的有效性。

1 夜行列車車底運用問題分析

1.1 相關(guān)概念解析

(1)夜行列車

夜行列車的具體解釋是：當(dāng)日下午5點以后至12點之前始發(fā)，次日上午6點以后至9點到達(dá)的高速列車。其運行時間在6 h以上，運行里程一般在1 000～3 000 km。

(2)基本交路

即夜行列車完成一次一級檢修后至完成下一次一級檢修期間擔(dān)當(dāng)?shù)牧熊嚾蝿?wù)與進行的各種作業(yè)的有序集合稱為一條“基本交路”，簡稱“交路”，等同于運用交路的概念。

(3)完整循環(huán)交路

不考慮二級檢修條件下，對若干列車運用交路進行組合，在一定時間跨度內(nèi)列車再次回到原始發(fā)地，這個過程夜行列車擔(dān)當(dāng)?shù)牧熊嚾蝿?wù)與進行各種作業(yè)的有序集合稱為“完整循環(huán)交路”。

(4)運用模式

圖1 夜行列車獨立運用模式

夜行列車運用模式分為獨立運用和日夜套跑運用兩種模式。獨立運用是指列車只在夜間擔(dān)任運用任務(wù)，白天在動車運用所整備停留，如圖1所示。這種模式下的接續(xù)較為疏松，出現(xiàn)較大的運行干擾時，列車所受的影響不大，但是運用效率較低，個別時候存在尚未達(dá)到修程標(biāo)準(zhǔn)卻不得不入庫檢修的情況，因此這種方式動車組檢修次數(shù)較多。日夜套跑運用是指列車夜間擔(dān)任夜行任務(wù)后，在車站進行整備，繼續(xù)擔(dān)任本線或其他線路日間列車運行任務(wù)，如圖2所示。這種模式下，列車接續(xù)較為緊密，出現(xiàn)較大的運行干擾時，列車所受的影響較大。相比獨立運用模式運用效率大大提高，檢修次數(shù)也在一定程度上有所減少。實際應(yīng)用中可根據(jù)我國鐵路現(xiàn)場實際，靈活采用不同的運用模式。

圖2 夜行列車日夜套跑運用模式

1.2 問題特征及求解策略

夜行列車車底運用問題特征表現(xiàn)在以下4個方面。

(1)運用時間方面。現(xiàn)有高速動車組可總結(jié)為“日間運用(06：00—24：00)，夜間檢修(24：00—06：00)”的運用模式，運用時間范圍在當(dāng)日6點至當(dāng)日24點，運用時間跨度一般在數(shù)小時以內(nèi)。夜行列車與此不同，其運用時間跨度在6 h以上，運用時間范圍在當(dāng)日17點至次日9點。由于夜行列車白天可繼續(xù)套跑日間運用任務(wù)，因此運用時間大大增加，擔(dān)當(dāng)下次夜行任務(wù)前列車往往就已達(dá)到修程而不得不在日間完成一級檢修。

(2)交路時間跨度?，F(xiàn)有高速動車組運用交路一般由若干交路段組成，時間跨度在2 d以上。夜行列車運用時間和走行距離較長，如果連續(xù)2次擔(dān)當(dāng)夜行任務(wù)勢必會超出列車的檢修修程。因此其交路時間跨度可縮短至24 h以內(nèi)。此時，運用交路稱為基本交路。

(3)約束因素。由于涉及夜行列車日間套跑，列車時空接續(xù)要求更為復(fù)雜。同時，為盡可能接近我國鐵路實際，特別考慮夜行列車車型、多基地情況下列車配屬關(guān)系、車型和檢修點匹配等約束。

(4)優(yōu)化目標(biāo)?，F(xiàn)有高速動車組運用問題大多以接續(xù)時間最小或動車組使用數(shù)量最少為目標(biāo)函數(shù)，從而使管理成本最小化。由于不存在同一列車同一天擔(dān)當(dāng)2次夜行任務(wù)的情況，因此夜行列車開行方案確定后開行對數(shù)往往就決定了運用車底的數(shù)量。這里，以車底運用不均衡度和非配屬地一級檢修次數(shù)為優(yōu)化目標(biāo)。車底運用不均衡度表現(xiàn)為各列車與所有列車運用距離或運用時間的偏差程度，用標(biāo)準(zhǔn)方差表示。數(shù)值越大反映列車之間運用差異越大，從而越不利于日常列車調(diào)度的調(diào)整?，F(xiàn)有管理體制下，由于列車在非配屬地檢修將會因溝通和協(xié)調(diào)使管理成本上升，因此希望非配屬地檢修次數(shù)越少越好。

借鑒現(xiàn)有高速動車組運用問題中分步求解[12]的策略，提出將夜行列車交路計劃編制過程分成“基本交路生成”和“完整循環(huán)交路生成”兩個階段。

基本交路生成主要解決“列車在第一天怎么走”的問題，作為后一階段模型的輸入。它是指根據(jù)修程修制，按照一定接續(xù)原則生成所有可行的基本交路。主要是通過運行線調(diào)整，合理組合，完成計劃規(guī)定的所有夜行運用任務(wù)和檢修任務(wù)，條件允許的情況下可多次套跑日間運用任務(wù)。根據(jù)夜行列車夜間運用里程和始發(fā)終到站檢修條件的不同，套跑可分為以下3種形式。

(1)終到站短交路套跑。列車到達(dá)終點站后，合理套跑若干日間短交路，返回后入庫進行一級檢修。適用于列車夜行運用里程在2 000 km及以上的情形。如圖3所示。

圖3 終到站短交路套跑

(2)立折套跑。列車到達(dá)終點站后，立即套跑日間返程交路。一般情況下不再擔(dān)當(dāng)其他短途的日間運用任務(wù)。適用于列車夜行運用里程2 000 km以下的情形。如圖4所示。

圖4 立折套跑

(3)檢修套跑。夜行任務(wù)的始發(fā)或終到站無檢修條件，而列車又不得不進行一級檢修時，需套跑該站與具備該車型檢修條件的檢修點所在站之間的短交路。如圖5所示。

圖5 檢修套跑

基本交路生成階段，若考慮日間套跑，相關(guān)約束較為復(fù)雜且與實際結(jié)合緊密，尤其涉及夜行列車在日間擔(dān)當(dāng)?shù)倪\用任務(wù)與現(xiàn)有運行圖匹配，列車運行線調(diào)整以及由此導(dǎo)致的現(xiàn)有高速動車組運用調(diào)整等問題，往往需要現(xiàn)場經(jīng)驗豐富的技術(shù)人員完成，本文暫不做深入探討。作為后一階段模型的輸入條件，將基本交路生成簡化為運用任務(wù)之間的緊密接續(xù)，套跑的日間交路以現(xiàn)有高速動車組開行的區(qū)段為依據(jù)，暫不考慮現(xiàn)有列車時刻表。這一階段可轉(zhuǎn)化為經(jīng)典問題，已有的研究方法[13]即可求解，本文不再贅述。

完整循環(huán)交路生成主要解決“列車在接下來幾天怎么走”的問題，是本文重點研究的內(nèi)容。這一階段列車采用周期性運用方式，列車各天擔(dān)當(dāng)?shù)倪\營任務(wù)具有一定規(guī)律性，便于列車運用組織與管理。此階段特別考慮車型、列車配屬關(guān)系、車型和檢修點匹配等約束條件，生成一定時間跨度內(nèi)列車交路任務(wù)的組合序列，通過指定具體的列車來擔(dān)當(dāng)該組合序列，并且循環(huán)執(zhí)行，從而形成完整的循環(huán)交路。這個時間跨度就是列車的運用周期。主要方法是將該問題歸結(jié)為多旅行商問題，構(gòu)建基于MTSP的列車車底運用網(wǎng)絡(luò)，建立車底運用優(yōu)化模型，并利用改進的深度優(yōu)先搜索算法對模型進行求解。

2 模型與求解

2.1 模型建立

構(gòu)建以基本交路為點，以交路間接續(xù)關(guān)系為有向弧的列車接續(xù)網(wǎng)絡(luò)，表示為加權(quán)有向圖D=(V,A)。V和A分別表示圖D中的點集合與有向弧集合。

A={aij=(vi,vj),vi,vj∈V}是D的弧集合，弧對應(yīng)基本交路之間的接續(xù)關(guān)系。

在列車接續(xù)網(wǎng)絡(luò)基礎(chǔ)上，為表述列車與交路的接續(xù)關(guān)系，定義如下變量

(1)

(2)

則循環(huán)周期t內(nèi)列車k累計運用里程、累計運用時間、非配屬地檢修次數(shù)可分別表示為式(3)～式(5)

(3)

(4)

(5)

基于上述變量，車底運用優(yōu)化模型可以描述為：

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

式(6)表示車底運用不均衡度，即Ne個列車在編制周期t內(nèi)以里程為標(biāo)準(zhǔn)的修程利用系數(shù)的總體標(biāo)準(zhǔn)誤差，其中L表示列車一級檢修修程；式(7)表示編制周期t內(nèi)Ne個列車在非配屬地一級檢修的次數(shù)；式(8)為目標(biāo)函數(shù)，表示車底運用不均衡度和非配屬地一級檢修次數(shù)的加權(quán)和最小，w1和w2為權(quán)重系數(shù)；式(9)～式(15)為模型約束條件。其中：式(9)和式(10)保證1天中每個基本交路僅有1個列出擔(dān)當(dāng)，并且每個列車一天內(nèi)僅擔(dān)當(dāng)1個基本交路；式(11)保證終到站和所接續(xù)的交路的起始站為同一車站；式(12)中Tc表示兩個交路之間最小接續(xù)時間標(biāo)準(zhǔn)；式(13)、式(14)和式(15)保證列車在一個編制周期結(jié)束后回到配屬地。模型中也考慮了車型和檢修點約束，即某種型號的列車k只能擔(dān)當(dāng)終到站具備該型號列車檢修條件的基本交路，即模型中的k∈Ex，i∈Vx。

2.2 求解算法

車底運用問題屬于典型的NP-hard問題，直接求解比較困難。本文中將這一問題分解為兩步。第一步生成列車k在編制周期t內(nèi)滿足模型中約束條件的基本交路序列的可行集，同理依次生成所有列車的基本交路序列可行集，這一步通過計算機遍歷基本交路集合V即可求解；由于每個列車交路序列的可行集在同一天可能會有沖突，因此第二步對所有列車的基本交路序列組合生成滿足約束條件的列車運用方案，這一步利用改進的深度優(yōu)先搜索算法求解。

圖6 遍歷搜索示意

深度優(yōu)先搜索算法實質(zhì)上是一種枚舉法，如果不加任何約束條件，就是尋找從起點到終點之間的所有可能的組合，對于本問題任意兩個起點到終節(jié)點之間的組合數(shù)量都是非常巨大的，因此這里引入啟發(fā)函數(shù)。所謂啟發(fā)函數(shù)就是增加一部分約束條件，以減少搜索計算量。它的含義主要體現(xiàn)在以下兩個方面。

一方面搜索的過程中需要判斷前后節(jié)點組合時是否存在沖突，如果有沖突則可以終止組合，返回上層節(jié)點(回溯)繼續(xù)搜索。這里的沖突主要指編制周期某一天中出現(xiàn)了相同的兩個基本交路編號。

(16)

引入啟發(fā)函數(shù)后搜索計算量往往也非常巨大，因此將解的數(shù)量達(dá)到Num作為算法的終止條件。

這一階段模型求解步驟如下。

Step1：數(shù)據(jù)準(zhǔn)備。包括3類數(shù)據(jù)：交路數(shù)據(jù)，其屬性有交路編號、始發(fā)站、終到站、起始時間、終到時間、運用距離、可運行車型；列車數(shù)據(jù)，其屬性有列車序號、配屬地點、車型；基礎(chǔ)數(shù)據(jù)，包括接續(xù)時間、編制周期、一級檢修修程等。

Step3：初始化。確定α、β、w1、w2、Num和其他相關(guān)參數(shù)的初始值。

Step4：根據(jù)啟發(fā)函數(shù)進行深度優(yōu)先搜索，形成完整循環(huán)交路，不斷更新最優(yōu)解，如圖7所示。

Step5：輸出完整循環(huán)交路的組合序列和最優(yōu)解。

圖7 深度優(yōu)先搜索流程

3 案例研究

本文以京廣高速夜行列車開行方案數(shù)據(jù)[7]為基礎(chǔ)，對車底運用方案進行實例研究。

3.1 開行方案及相關(guān)參數(shù)

開行方案：京廣高速鐵路夜行列車最高運營速度均為250 km/h，共開行列車11對。其中北京西—武漢1對；北京西—長沙南2對，其中1對經(jīng)停武漢；北京西—廣州南1對；北京西到深圳北1對，經(jīng)停石家莊和廣州南；鄭州東到深圳北1對，經(jīng)停廣州南；北京西到西安北2對；西安北—長沙南1對；西安北—深圳北1對，經(jīng)停廣州南；南京南—深圳北1對，經(jīng)停廣州南。

作業(yè)參數(shù)：列車立折時間取20 min；兩交路接續(xù)時間Tc取140 min；列車車型均為CRH2E車型；列車一級檢修修程為4 000 km。

算法參數(shù)：編制周期t取4 d；w1、w2分別取80和0.2；α、β分別取0.02和0.2；Num取100 000，當(dāng)產(chǎn)生新解的次數(shù)為100 000時搜索結(jié)束。

車輛及檢修條件：全部配屬CRH2E車型，共計22組列車。其中7組配屬北京西動車運用所，4組配屬廣州南動車運用所，5組配屬武漢動車運用所，4組配屬西安北動車運用所，1組配屬鄭州東動車運用所。對于無檢修條件的長沙南(有檢修點，無技術(shù)條件)和深圳(無檢修點)，通過套跑形式分別安排到武漢和廣州南檢修點進行檢修。同時增加廣州CRH2型車的運用檢修技術(shù)條件。

3.2 計算結(jié)果

基本交路生成階段共有22個基本交路，平均運行里程為2 938.045 km，如表1 所示。利用C#編程求解得到的完整循環(huán)交路，車底運用不均衡度為5.93%，非配屬地檢修次數(shù)為25次，完整交路計劃如表2所示。

3.3 結(jié)果評價

編制結(jié)果表明，車底運用不均衡度5.93%和異地檢修次數(shù)25次已接近理論最優(yōu)解上界的5.87%和20次，如表3所示。由此可見，在暫不考慮對日間列車影響的情況下，本文所提出的模型和算法可有效解決夜行列車車底在日間和夜間綜合運用和優(yōu)化等問題，從而為我國高速夜行列車的開行提供一定的技術(shù)支持。

表1 基本交路

注：①表示列車進行一級檢修任務(wù)，檢修地點為接續(xù)車站所在的動車運用所。

表2 完整交路計劃

表3 編制結(jié)果

注：1.理論最優(yōu)解上界的確定方法為：分別將不均衡度和異地檢修次數(shù)作為單目標(biāo)條件進行求解所得結(jié)果。

2.理論最優(yōu)解下界的確定方法為：分析計算在接續(xù)條件最差的情況下的不均衡度和異地檢修次數(shù)。

4 結(jié)語

本文對夜行列車車底運用問題這一新的研究方向進行了初步探索，重點研究了完整循環(huán)交路階段模型構(gòu)建和求解算法，提出了夜行列車運用的兩種模式，并對周期性運用方式下的交路計劃求解策略進行了分析；針對完整循環(huán)交路階段，建立以車底運用不均衡度和列車在非配屬地一級檢修次數(shù)為目標(biāo)函數(shù)的優(yōu)化模型，利用改進的深度優(yōu)先搜索算法進行求解；最后以京廣高速夜行列車車底運用方案為例進行驗證，表明了模型和算法的有效性。

日夜套跑運用模式下，高速夜行列車的開行勢必要對運行圖和現(xiàn)有高速動車組周轉(zhuǎn)運用產(chǎn)生較大影響，本文未予考慮，未來面向日夜運行列車協(xié)同優(yōu)化的動車組綜合運用方案將是一個新的研究方向。此外，本文只研究了夜行列車交路計劃編制方法，對于夜行列車檢修計劃和乘務(wù)計劃也是需要進一步研究的問題。

[1] 聶磊，胡必松，付慧伶，等. 客運專線夜間行車與天窗的相互影響分析[J].交通運輸系統(tǒng)工程與信息，2010，10(5)：66-72.

[2] 徐小勇.客運專線開行夕發(fā)朝至旅客列車的可行性研究[J].價值工程，2010(10)：141-142.

[3] 王相平，花偉，李博，等.基于矩型天窗下客運專線開行夕發(fā)朝至列車的可行性研究[J].鐵道運輸與經(jīng)濟，2014(11)：16-17，48．

[4] 彭其淵.客運專線運輸組織[M].北京：科學(xué)出版社，2007.

[5] 朱文亭.高速鐵路“夕發(fā)朝至”跨線列車運輸組織研究[D].成都：西南交通大學(xué)，2011.

[6] 胡秀婷.京滬高速鐵路綜合維修天窗設(shè)置[J].交通運輸工程與信息學(xué)報，2011，9(3)：103-110.

[7] 王超.京廣高速鐵路夜行列車開行方案研究[D].北京：北京交通大學(xué)，2014.

[8] 趙鵬，張迦南.鐵路動車組的運用問題研究[J].北京交通大學(xué)學(xué)報，2009，33(3)：6-10，16.

[9] 李華，韓寶明，趙鵬.面向我國鐵路實際的動車組運用計劃編制問題[J].北京交通大學(xué)學(xué)報：自然科學(xué)版，2012，36(6)：8-14.

[10]王忠凱.動車組運用檢修計劃優(yōu)化方法的研究[D].北京：中國鐵道科學(xué)研究院，2012．

[11]李華.高速鐵路動車組運用計劃編制理論與方法研究[D].北京：北京交通大學(xué)，2013．

[12]曲思源，徐行方.城際鐵路動車組運用計劃模型[J].同濟大學(xué)學(xué)報：自然科學(xué)版，2010，38(9)：1298-1302．

[13]吳冰芝.客運專線動車組運用優(yōu)化研究[D].成都：西南交通大學(xué)，2012.

Research on Circulation and Optimization of High-speed Night Train

HAN Bao-ming1， SUN Shi-zhao1， ZHENG Bin2， ZHANG Qi1

(1.School of Traffic and Transportation， Beijing Jiaotong University， Beijing 100044， China; 2.China Railway Engineering Consulting Group Co.， Ltd.， Beijing 100055， China)

The main differences between high speed night train and the existing high-speed EMU lie in the range and span of operation time， which may lead to the changes of operation conditions. On the basis of the summary of the characteristics of circulation plan for the night train， this paper proposes a strategy to solve the problem by dividing the solution process into two phases: fundamental circulation plan and full circle circulation plan. The former is the input of the latter’s model. Then a mathematical optimal model is established to minimize the inequality of operation and frequency of vehicle maintenance in other operation depots， which is fulfilled with improved depth-priority search algorithm and verified with data from Beijing-Guangzhou high-speed night train. The results show that the proposed method is effective to solve the problem of night train circulation and may provide technical support to the operation of night train.

Night train; Operation pattern; Circulation planning; depth-priority search algorithm

2014-11-17；

2014-11-26

國家科技支撐計劃(2009BAG12A10)；國家自然科學(xué)基金聯(lián)合基金項目(1434207)

韓寶明(1963—)，男，教授，博士生導(dǎo)師。

1004-2954(2015)07-0009-06

U292.3

A

10.13238/j.issn.1004-2954.2015.07.003