既定列車作業(yè)計劃下高鐵站可用能力算法研究

陳韜，倪少權(quán)*，潘金山，申雪松

（1.西南交通大學(xué)a.交通運輸與物流學(xué)院；b.全國鐵路列車運行圖編制研發(fā)培訓(xùn)中心，成都610031；2.綜合交通運輸智能化國家地方工程聯(lián)合實驗室，成都610031；3.北京鐵路局運輸處，北京100860）

既定列車作業(yè)計劃下高鐵站可用能力算法研究

陳韜1,2，倪少權(quán)*1,2，潘金山1,2，申雪松3

（1.西南交通大學(xué)a.交通運輸與物流學(xué)院；b.全國鐵路列車運行圖編制研發(fā)培訓(xùn)中心，成都610031；2.綜合交通運輸智能化國家地方工程聯(lián)合實驗室，成都610031；3.北京鐵路局運輸處，北京100860）

高鐵站可用能力計算對確定列車開行方案的可行性有重要意義.首先分析了高鐵站可用能力的影響因素，然后構(gòu)建了基于股道空閑時段的高鐵站可用能力數(shù)學(xué)模型，提出了先驗性優(yōu)化策略與智能優(yōu)化算法相結(jié)合的雙階段算法對模型求解.其中，第一階段是綜合運用最小股道空閑時段優(yōu)先、最大平行進路優(yōu)先、股道空閑時間段內(nèi)出發(fā)時間最小的列車類型優(yōu)先等策略規(guī)則求出模型可行初始解，第二階段是在初始解基礎(chǔ)上運用禁忌搜索算法尋找模型優(yōu)化滿意解，最后用實例對算法的有效性進行驗證.

鐵路運輸；可用能力計算；雙層算法；高鐵站；列車作業(yè)計劃

1 引言

我國高鐵新線相繼開通，高鐵聯(lián)網(wǎng)格局逐漸形成，諸多高鐵站銜接線路方向也隨之增加.為制定優(yōu)質(zhì)列車開行方案，以充分發(fā)揮高鐵成網(wǎng)優(yōu)勢，需對高鐵站可用能力進行計算和評估.目前，在全路編制開行方案及運行圖工作中，高鐵站可用能力主要還是依靠編圖人員的經(jīng)驗及手工調(diào)圖試湊的方法進行計算，局限性突出，因此有必要對其優(yōu)化算法進行研究，提高工作效率.

可用能力是指在既定車站作業(yè)計劃和列車進路排列方案下，車站在某時段內(nèi)可增加的最大接發(fā)列車數(shù)，屬于一種特殊的通過能力利用場景[1]，目前，主要運用計算機模擬法研究該問題，但相關(guān)文獻不多.文獻[1]中提出了求解車站通過能力的列車路徑壓縮優(yōu)化模型和加密方法，該方法有利于車站能力利用率的評估.文獻[2]～文獻[4]運用基于極大代數(shù)的petri網(wǎng)、資源樹沖突解決等技術(shù)，對高鐵站通過能力的仿真場景建立及計算進行了相關(guān)研究，但對既有列車作業(yè)計劃場景下的車站通過能力涉及較少.本文在前人基礎(chǔ)上，對既有列車作業(yè)計劃下的高鐵站通過能力問題開展分析，提出了運用先驗性優(yōu)化策略與智能優(yōu)化算法相結(jié)合的雙階段算法，并進行了實例驗證.

2 問題分析

高鐵站可用能力計算的影響因素主要有3方面：

（1）車站固定設(shè)備資源及作業(yè)組織規(guī)則對可用能力的影響.

車站固定設(shè)備資源包括：車站到發(fā)線、道岔、信號機等及其相互聯(lián)鎖關(guān)系；作業(yè)組織規(guī)則包括：各種作業(yè)時間標(biāo)準(zhǔn)、列車安全間隔標(biāo)準(zhǔn)等.這些都是可用能力計算時必須滿足的時空資源約束條件.

（2）既定列車作業(yè)計劃對可用能力的影響.

高鐵站可用能力的計算本質(zhì)上是對車站某時段內(nèi)剩余時空資源的最大化利用.由于既定列車作業(yè)計劃的存在，割裂了整個車站的時空資源，車站剩余可用的時空資源呈現(xiàn)碎片化，這些時空資源碎片主要體現(xiàn)為多個股道空閑時段，如圖1（a）和圖1（b）所示，由于列車的既定計劃安排，導(dǎo)致某時段內(nèi)分別出現(xiàn)了4個和3個股道空閑時段，可用能力被限定其中.因此，高鐵站可用能力計算可以轉(zhuǎn)化為求解車站某時段內(nèi)的所有股道空閑時段內(nèi)可增加的最大列車數(shù)及其作業(yè)方案.

圖1 股道空閑時段分布圖Fig.1 Idle periods of tracks

（3）可用能力計算時新增列車的作業(yè)方案對可用能力的影響.

在各種時空資源約束確定的條件下，可用能力計算時新增列車采用的作業(yè)方案對可用能力影響較大.列車作業(yè)方案包括：

①車流構(gòu)成類型的確定.

車流構(gòu)成類型由列車種類（速度、型號）、列車作業(yè)性質(zhì)（站折、出段、入段）及列車到發(fā)方向確定，不同的車流構(gòu)成類型會影響可用能力計算結(jié)果不同.以列車到發(fā)方向為例，如圖2所示（實線線條表示已經(jīng)安排的列車，虛線線條表示新增列車），在相同的股道空閑時段內(nèi)，圖2（b）中安排的第2個列車是折角列車，發(fā)車最小間隔時間不足，致使可安排列車數(shù)量比圖2（a）中少.本文采用列車出發(fā)時間為指標(biāo)來衡量不同列車類型對資源的占用情況，特定的股道空閑時段中，出發(fā)時間越小的列車類型時間資源占用越少.

圖2 車流構(gòu)成類型對可用能力的影響Fig.2 The influence on available capacity of various train type

②列車到發(fā)時刻的確定.

由圖2可知，當(dāng)列車類型確定后，列車到發(fā)時刻主要由股道空閑時段起止時間、各種最小列車車站間隔約束、及列車停站時間幾個要素決定.

③列車接發(fā)股道及進路的安排.

由于列車股道作業(yè)間耦合性極強，同一個列車不同的股道空閑時段選擇方案，可用能力計算結(jié)果可能會不同，如圖3所示（實線線條表示已經(jīng)安排的列車，虛線線條表示新增列車），當(dāng)圖3（a）中的列車1從股道1調(diào)整到股道2后，如圖3（b）所示列車2就無法安排了.由于列車接發(fā)股道只能在有空閑時段的股道間選擇，而且列車到發(fā)時刻也取決于股道空閑時段，因此，列車的接發(fā)股道安排實際上就是股道空閑時段的安排，每個列車在同一時刻內(nèi)僅能安排一個股道空閑時段.本文按照生產(chǎn)調(diào)度中緊張資源優(yōu)先原則，采用最小空閑時段股道優(yōu)先規(guī)則、最大平行進路優(yōu)先規(guī)則確定列車股道及進路方案.

圖3 列車接發(fā)股道及進路安排對可用能力的影響Fig.3 The influence on available capacity of train track and route arrangement

綜上所述，高鐵站可用能力計算就是在車站資源與既定列車作業(yè)計劃約束條件下，以列車構(gòu)成類型、列車股道及進路安排、列車到發(fā)時刻為決策變量的，某時段內(nèi)列車最大新增數(shù).下面對問題進行抽象假設(shè)并建立模型，為了縮小模型求解空間，需要確定某時段內(nèi)的所有股道空閑時段.

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

3.1 條件假設(shè)及符號說明

某高鐵樞紐站有M個銜接方向、S條到發(fā)股道；每個銜接方向有Li(i∈M)條接發(fā)車進路、P個已安排計劃的列車；每個列車是一個七元組的變量分別表示每個列車的到達方向、出發(fā)方向、接發(fā)股道、接車進路、發(fā)車進路、股道占用開始時間、股道占用結(jié)束時間；假設(shè)高峰小時段的車站可增加列車數(shù)為Pnew，求Pnew的最大值.

需要注意，根據(jù)現(xiàn)行列車運行圖規(guī)定，高鐵站的列車出入動車所的時刻點必須在運行圖上直接確定，因此把動車所視作車站一個銜接方向，從動車所方向接發(fā)的車為出入段車，各方向列車股道停留時間為.設(shè)新增列車等級、長度、速度、都相同，作業(yè)安排時需要滿足各種最小車站間隔).高峰時段內(nèi)不設(shè)天窗及非列車作業(yè)時間.

3.2 股道空閑時段的確定

3.3 模型建立

給出高鐵站可用能力計算模型

約束條件：

股道空閑時段占用唯一性約束如式（3）～式（7）.

接發(fā)進路占用唯一性約束如式（8）～式（17）：

式（1）表示新增列車數(shù)量最大化；式（2）表示盡量按照股道固定使用方案安排列車.

式(3)表示每個列車僅能安排一個股道空閑時段；式(4)表示每個列車股道占用時間要大于等于規(guī)定的股道停留時間標(biāo)準(zhǔn)；式(5)表示每個股道空閑時段內(nèi)的任何列車占用時間都不能沖突；式（6）表示每個列車的到發(fā)時間必須滿足股道空閑時段的時間起止約束；式（7）表示每個股道空閑時段的起止時間滿足高峰小時段時間起止約束.

式(8)表示每個列車僅能安排一條接車進路及一條發(fā)車進路；式(9)～式(12)表示新增列車間的接發(fā)車進路設(shè)備占用沖突時，要滿足車站安全間隔時間標(biāo)準(zhǔn)；式(13)～式(16)表示新增列車與既定作業(yè)計劃列車的接發(fā)車進路設(shè)備占用沖突時，要滿足車站安全間隔時間標(biāo)準(zhǔn)約束；式(17)表示為列車安排的到發(fā)線股道與被安排的接發(fā)車進路設(shè)備相連通.

式(18)是列車安排股道空閑時段的決策變量；式(19)和式(20)是列車安排接發(fā)車進路的決策變量.式(21)和式（22）是模型中其他參數(shù)的取值范圍.

4 算法設(shè)計

4.1 算法思路

高鐵車站可用能力計算是一個NP問題[2].為解決該問題，本文采用爬山能力較強且適合離散解空間的禁忌搜索算法進行計算.禁忌搜索算法對初始解有較強的依賴性，因此，本文將分為兩個階段進行求解：

第1階段，綜合運用最小股道空閑時段優(yōu)先規(guī)則（按時段長短對所有股道空閑時段進行排序，時段長度小的股道空閑時段優(yōu)先增加列車并安排作業(yè)）、最大平行進路優(yōu)先規(guī)則[7]（對增加的列車安排接發(fā)車進路時，優(yōu)先安排具有最多平行進路的進路）、股道空閑時段內(nèi)出發(fā)時間最小的列車構(gòu)成類型優(yōu)先規(guī)則（某個股道空閑時段內(nèi)，每增加一個列車時，該列車類型的確定遵循優(yōu)先選擇接發(fā)進路安排后出發(fā)時間最小的列車類型），在每個股道空閑時段內(nèi)增加列車并安排作業(yè)計劃，得到滿足各種時空資源約束的一個初始方案.第1階段算法僅能保證每個股道空閑時段內(nèi)列車作業(yè)安排的優(yōu)化性，屬于局部優(yōu)化過程.

第2階段，運用禁忌搜索算法，以列車數(shù)量增加最大化為優(yōu)化目標(biāo)，對第1階段初始方案進行改進，實現(xiàn)全局方案優(yōu)化，具體方法為：采用2-opt原則交換兩個不同股道空閑時段的安排順序，然后運用股道空閑時段內(nèi)出發(fā)時間最小的列車類型優(yōu)先規(guī)則、最大平行進路優(yōu)先規(guī)則，在調(diào)整后的每個股道空閑時段內(nèi)增加列車并安排作業(yè)計劃，直到達到算法終止條件.

4.2 算法實現(xiàn)

4.2.1 生成初始方案

（1）初始化車站設(shè)備參數(shù)：股道、道岔、銜接方向及其聯(lián)通關(guān)系，生成車站接發(fā)進路表；初始化車站股道作業(yè)時間標(biāo)準(zhǔn)、車站間隔時間標(biāo)準(zhǔn)、能力計算起止時間；生成既定車站作業(yè)計劃.

（2）根據(jù)既定列車作業(yè)計劃，生成股道空閑時段集合{}qij，并按起止時段長度從小到大排序，詳見3.2節(jié).

（3）初始化列車類型集合.算法中生成了兩個列車類型集合數(shù)組，第一個是根據(jù)列車類型比例生成的集合數(shù)組用以確定列車類型被安排的范圍和順序，第二個是由第一個集合數(shù)組中未被安排的列車類型組成，用以挑選出其中出發(fā)時間最小的列車類型.

（4）根據(jù)最小股道空閑時段優(yōu)先規(guī)則，依次選擇一個股道空閑時段，然后對每個股道空時段運用出發(fā)時間最小的列車類型優(yōu)先規(guī)則、最大平行進路優(yōu)先規(guī)則進行增加列車及接發(fā)車進路安排操作，直到股道空閑時段集合為空.

具體算法流程如圖4所示.

4.2.2 運用禁忌搜索算法尋找高鐵車站可用能力優(yōu)化解[6]

在可用能力初始方案基礎(chǔ)上，運用禁忌搜索算法尋找優(yōu)化解.禁忌搜索算法的關(guān)鍵是要設(shè)計合理的鄰域結(jié)構(gòu)、評價函數(shù)、禁忌表、終止規(guī)則.

（1）初始解.

以上一步驟中的新增列車數(shù)及排列初始方案為初始解.

（2）鄰域結(jié)構(gòu).

本文中滿足2-opt映射的解，即在已排序的股道空閑時段集合中，兩個不同的股道空閑時段交換順序后產(chǎn)生一個鄰域解，則領(lǐng)域規(guī)模為

（3）評價函數(shù).

以新增列車數(shù)為評價指標(biāo)，數(shù)值越大則方案越好.

（4）候選解集.

鄰域解中選取股道空閑時間段數(shù)的平方根為候選集范圍，即候選解集大小為，將候選解集中新增列車數(shù)最大的方案作為新的當(dāng)前解進行下一次迭代搜索.

（5）禁忌表.

將已經(jīng)評價過的股道空閑時段排列方案及其評價值進行禁忌，貯存在禁忌表內(nèi)，本文的禁忌表用鏈表結(jié)構(gòu)來表示.為了獲得較好的搜索效果，采用動態(tài)禁忌長度.本文根據(jù)頻率信息動態(tài)控制禁忌的長度，當(dāng)一個目標(biāo)函數(shù)值重復(fù)出現(xiàn)，可以增加禁忌長度以避開循環(huán).

（6）特赦條件.

為了避免丟失最優(yōu)解，規(guī)定在找不到領(lǐng)域解及迭代一定次數(shù)后，特赦禁忌表中最優(yōu)值為當(dāng)前解繼續(xù)進行迭代搜索.

（7）終止條件.

設(shè)置最大迭代次數(shù)作為終止條件.

（8）算法流程.

①設(shè)迭代次數(shù)為1，將可用能力計算初始方案置為當(dāng)前方案；

②隨機對換2個不同的股道空閑時段后，并按照第一階段中算法流程，進行新增列車及作業(yè)安排，生成鄰域解，以最大評價指標(biāo)對鄰域解進行評價；

③判斷鄰域解中對象是否滿足藐視準(zhǔn)則，選擇鄰域解中未被禁忌的對象及滿足藐視準(zhǔn)則的禁忌對象為候選解，更新禁忌表；

④迭代次數(shù)增加1，若迭代次數(shù)為最大迭代次數(shù)或者最大值出現(xiàn)頻率較高時，算法終止，輸出最優(yōu)方案，否則轉(zhuǎn)②.

圖4 第一階段算法流程Fig.4 The first-stage algorithm flow

5 算例

以某真實大型高速鐵路樞紐站為例對算法的有效性進行驗證.該車站共有3個銜接方向，其中C為動車所方向，各方向間都有列車到發(fā)，站場圖如圖5所示.列車到達追蹤間隔3 min、列車出發(fā)追蹤間隔3 min、列車不同時發(fā)到間隔時間8 min、列車不同時到發(fā)間隔時間2 min，車站不考慮延續(xù)進路，列車不能在正線停車，列車停留時間均為6 min，列車在股道上的停留效益相同.車站已安排的列車到發(fā)作業(yè)計劃如圖7所示，其中黑框中為高峰時段14:00-17:00的作業(yè)計劃共16列車，求此情況下14:00-17:00內(nèi)的可用能力.

圖5 高鐵站站場圖Fig.5 HSP station yard diagram

運用本文算法進行高鐵站可用能力計算，首先得到14:00-17:00的股道空閑時段共26段并從小到大排序，運用第一階段算法得到初始方案，然后運用第二階段禁忌搜索算法尋求優(yōu)化解，當(dāng)?shù)螖?shù)為60次后，得到圖6所示結(jié)果，最大增加列車數(shù)為39列，其作業(yè)計劃的時空分布如圖8所示.運用文獻[1]中的壓縮加密法計算本算例的高峰時段可用能力，首先壓縮既有計劃16列車間的緩沖時間，然后加密5次后，最終得到可用能力結(jié)果為36列，比本文算法計算結(jié)果少3列，主要原因是壓縮已安排計劃的列車作業(yè)緩沖時間會破環(huán)股道空閑時段時空分布，導(dǎo)致可用能力的計算結(jié)果失真，由此也表明了本算法的可行性和優(yōu)化性.

圖6 可用能力計算優(yōu)化迭代過程Fig.6 The iterative process of optimization

圖7 給定車站作業(yè)計劃圖Fig.7 Train reception and departure plan diagram

圖8 高峰時段可用能力計算后車站作業(yè)計劃圖Fig.8 Train reception and departure plan diagram after available capacity calculation

6 研究結(jié)論

既定列車作業(yè)計劃下的高鐵站可用能力計算問題屬于典型的NP問題，運用計算機模擬法求解效率較高.本文提出了基于股道空閑時段的先驗性優(yōu)化策略與智能優(yōu)化算法相結(jié)合的雙階段算法，為該問題的解決提供了一個有效的思路.

[1]劉敏，韓寶明，李得偉，等.高速鐵路車站通過能力計算和評估[J].鐵道學(xué)報，2012，34(4)：9-15.[LIU M, HAN B M,LIU H D,et al.Calculation and evaluation of carrying capacities at high-speed railway stations[J]. Journal of Railway Society,2012,34(4):9-15.]

[2]Peter S.Calculation of realistic railway station capacity by plat forming feasibility checks[C].2nd International Conference on Models and Technologies for Intelligent Transportation Systems,2011.

[3]張嘉敏.基于雙層模型的高速鐵路車站能力計算與評估[J].交通運輸工程與信息學(xué)報,2014，4：39-48 [ZHANG J M.Calculation and evaluation of station capacity for high speed railway based on bi-level model[J].Journal of Transportation Engineering and Information,2014,4:39-48.]

[4]鐘俊，王正彬，等.客專車站高峰通過能力一體化計算研究[J].交通運輸工程與信息學(xué)報,2012，2：125-131.[ZHONG J,WANG Z B,et al.Study on integrated algorithm for the peak through capacity of a dedicated passenger line terminal[J].Journal of Transportation Engineering and Information,2012,2:125-131.]

[5]史峰，謝楚農(nóng)，于桂芳，等.鐵路車站咽喉區(qū)進路排列優(yōu)化方法[J].鐵道學(xué)報，2004，26(4)：5-9.[SHI F,XIE C N,YU G F,et al.Optimization methods for arranging train routes in station bottleneck[J].Journal of Railway Society,2004,26(4):5-9.]

[6]王凌.智能優(yōu)化算法及其應(yīng)用[M]．北京：清華大學(xué)出版社，2004.[WANGL.Intelligentoptimization algorithm and its application[M].Beijing:Tsinghua Univercity Press,2004.]

HSR Passenger Station Available Capacity Calculation under Train Reception and Departure Plan Established

CHEN Tao1,2，NI Shao-quan1,2，PAN Jin-shan1,2，SHEN Xue-song3
(1a.School of Transportation and Logistics;1b.National Railway Train Diagram Research and Training Center,Southwest Jiaotong University,Chengdu 610031,China;2.National United Engineering Laboratory of Integrated and Intelligent Transportation,Chengdu 610031,China;3.Beijing Railway Bureau Transportation Department,Beijing 100860,China)

The calculation of HSR passenger station available capacity is of great significance to determine the feasibility of passenger train operation plan.The main influence factors of HSR available capacity firstly are analyzed.Then mathematical model of HSR available capacity based on the idle periods of tracks is built. A two-level heuristic algorithm,in which some optimization strategies are combined with intelligent optimization algorithm,is offered.In the first level,a feasible initial solution is found by using the policy of minimum idle period of track priority,the maximum parallel route priority,the minimum departure time of train type priority.In the second level,the Tabu search algorithm is used to search a satisfied solution based on the initial solution.At last,an example is used to validate the effectiveness of the proposed algorithm.

railway transportation;calculation of available capacity;two-level algorithm;high-speed passenger station;train reception and departure plan

1009-6744（2015）05-0178-08

U268.6

A

2015-05-13

2015-07-08錄用日期：2015-07-21

國家自然科學(xué)基金（61273242，61403317，60776826）；四川省科技廳軟科學(xué)計劃項目（2015ZR0141）；中央高?；究蒲袠I(yè)務(wù)費專項資金資助（2682015CX043）；中國鐵路總公司科技研究計劃項目（2015X008-B，2014X004-D）.

陳韜（1981-），女，廣西柳州人，博士生. ＊

shaoquanni@163.com