鐵路客運站調(diào)機運用與列車進路排列協(xié)同優(yōu)化方法

霍亮

(中鐵第四勘察設(shè)計院集團有限公司，湖北 武漢430000)

既有線鐵路客站行車工作內(nèi)容主要包括列車接發(fā)作業(yè)進路排列、咽喉與到發(fā)線利用和調(diào)機運用三個問題，三者之間既相互聯(lián)系又相互制約。繁忙鐵路客運站在組織接發(fā)列車時，如何在保證行車設(shè)備占用相互協(xié)調(diào)的情況下，科學(xué)調(diào)度各項作業(yè)的設(shè)備使用，最小化設(shè)備總的占用時間和最大化設(shè)備運用效率，是鐵路客運站行車技術(shù)作業(yè)效率提升的關(guān)鍵所在。目前針對鐵路車站的列車接發(fā)作業(yè)進路排列、咽喉與到發(fā)線利用等問題，已經(jīng)有較為廣泛的研究。史峰等[1?2]分別提出了車站咽喉進路與車站進路排列優(yōu)化模型與算法；AL‐HOSSEIN 等[3?4]研究了高速鐵路車站進路排列問題；馬駟等[5]構(gòu)建了高鐵車站列車進路分配方案的優(yōu)化調(diào)整方法；SELS 等[6]致力于實現(xiàn)車站站臺運用與列車進路自動排列；MIAO 等[7]以提高方案穩(wěn)定性為目標優(yōu)化車站站臺安排問題；郎越等[8?10]提出高速鐵路車站列車進路分配與作業(yè)計劃鏈式優(yōu)化方法?？傮w而言，既有文獻分別對上述3個問題的優(yōu)化方法進行了獨立的分析和研究，這些單一優(yōu)化方法盡管對實踐工作具有一定的指導(dǎo)作用，但由于忽視了三者之間的整體性和關(guān)聯(lián)性，據(jù)此得到的單獨決策結(jié)果可能并不相容。雖然，陳彥等[11]將接車、發(fā)車作業(yè)進路和接入的到發(fā)線拼接形成列車過站徑路，實現(xiàn)客運站到發(fā)線運用與作業(yè)進路編排的整體優(yōu)化，但將調(diào)機出入段時間作為已知條件，而未考慮調(diào)機運用與其它作業(yè)間的相互影響。鐵路客運站的調(diào)機運用優(yōu)化問題，可描述為以調(diào)機作業(yè)接續(xù)里程和接續(xù)時間最小化為優(yōu)化目標的指派問題，該問題在調(diào)機出入段時間和到發(fā)線運用方案確定的條件下是一個0-1 線性規(guī)劃問題。本文在陳彥等[11]的基礎(chǔ)上，以客站接發(fā)列車作業(yè)進路、調(diào)機運行進路和接續(xù)時間為決策對象，構(gòu)建調(diào)機運用與列車徑路安排綜合優(yōu)化模型及其模擬退火求解算法，實現(xiàn)了鐵路客站接發(fā)列車作業(yè)進路排列、咽喉及到發(fā)線利用和調(diào)機運用的綜合優(yōu)化。

1 問題分析

設(shè)某繁忙鐵路客運站始發(fā)、終到、通過列車集合分別為S，Z和G，列車集合I=G∪S∪Z，車底集合為C，到發(fā)線集合為W，道岔集合為V，客技線集合為U，列車i進入車站的作業(yè)為i(0)，列車i離開車站的作業(yè)為i(1)。ti和t′i分別表示列車i需要占用到發(fā)線的開始和結(jié)束時刻，tc和t′c車底c∈C占用客技線的起止時刻。τi和τ′i分別表示列車i=S∪Z的車底出入段作業(yè)起止時刻，Q為車底在庫內(nèi)的標準作業(yè)時間，則有：

列車i∈I的進站端為o(i)，出站端為d(i)，o(i)與到發(fā)線w∈W之間共有n(o(i),w)條進路，其中第k條進路為到發(fā)線w與d(i)之間共有n(w,d(i))條進路，其中第k條 進 路 為為 進路上道岔v∈V的占用時長，且當(dāng)時

對于b= 0,1，記作業(yè)i(b)所在咽喉區(qū)的道岔集為V(i(b))，和分別表示作業(yè)i(b)對道岔v的占用起止時刻，ei(b)v是表示作業(yè)i(b)是否會占用道岔v的0-1 變量，占用為1，否則為0，是表示作業(yè)i(b)是否會選擇進路或的0-1變量，選擇為1，否則為0。

對于列車i,j∈S∪Z，記τij為調(diào)機在列車i、j的車底出入段作業(yè)之間的接續(xù)時間，lij為相應(yīng)的走行距離，J為規(guī)定的調(diào)機最小接續(xù)時間，L為客站與客技站之間的距離，則有：

式(3)中βij為0-1變量，若列車i和j同為始發(fā)或終到列車，其值為0，否則為1。

對于始發(fā)、終到列車和過路車，車站需要進行接發(fā)列車作業(yè)，并安排占用的到發(fā)線。對于始發(fā)終到列車，還分別需要進行車底入段和出段的調(diào)車作業(yè)。鑒于兩者之間具有密切關(guān)系，可將其視為一個一體化協(xié)同優(yōu)化問題，綜合優(yōu)化確定車底出入段作業(yè)的時間和列車過站徑路。對于列車i,j∈S∪Z，可引入該問題的決策變量yij和ziw如下：

2 調(diào)機運用與列車徑路安排綜合優(yōu)化模型

鐵路客站的普速客車車底出入段的調(diào)機運用，需保證各車底出入段作業(yè)有且只有一臺調(diào)機擔(dān)當(dāng)。因此，客車車底出入段調(diào)機運用的優(yōu)化目標，可設(shè)定為調(diào)機出入段作業(yè)之間的接續(xù)時間和走行距離最小化。而旅客列車過站徑路優(yōu)化則是接發(fā)列車作業(yè)進路排列和到發(fā)線運用的綜合優(yōu)化問題[11]，因此，可將調(diào)機運用優(yōu)化問題視為車底出入段時間優(yōu)化問題，結(jié)合文獻[11]的旅客列車過站徑路優(yōu)化模型，可構(gòu)建調(diào)機運用與客運列車徑路安排綜合優(yōu)化模型。

2.1 約束條件

根據(jù)鐵路客站行車技術(shù)作業(yè)特點，在綜合優(yōu)化模型中需考慮的約束條件主要有：

1) 列車接發(fā)車進路選擇約束

辦理列車i的作業(yè)i(0)時，需安排進站端oi至到發(fā)線w∈W間的一條接車進路，則

相應(yīng)地，對列車作業(yè)i(1)時，需安排到發(fā)線w∈W至出站端d(i)間的一條發(fā)車進路，則

2) 車站到發(fā)線資源占用約束

作業(yè)i(0)與i(1)的接發(fā)進路決定了列車i的到發(fā)線占用情況，有

3) 車站咽喉道岔資源占用約束

作業(yè)i(0)與i(1)的接發(fā)列車進路決定了列車i的道岔占用，有：

4) 車站咽喉道岔占用的時間約束

若列車i為通過和終到列車，則其到站時刻即可視為作業(yè)i(0)占用道岔v的開始時刻、占用到發(fā)線的開始時刻，即

若列車i為始發(fā)列車，其作業(yè)i(0)占用道岔v的開始時刻為車底出庫時刻，即

若列車i為通過和始發(fā)列車，則其發(fā)車時刻即可視為作業(yè)i(1)占用道岔的開始時刻和占用到發(fā)線的終止時刻，即

若列車i為終到列車，其作業(yè)i(1)占用道岔的開始時刻為車底入庫時刻，即：

若列車i為通過和終到列車，其作業(yè)i(0)占用道岔的終止時刻由其選擇的進路決定，即：

若列車i通過和始發(fā)列車，其作業(yè)i(1)占用道岔的終止時刻由其選擇的進路決定，即：

5) 車站到發(fā)線資源占用的相容性約束

列車占用到發(fā)線資源具有時間上的排他性，同一時間最多只能被一列車占用，即

6) 車站咽喉道岔資源占用的相容性約束

作業(yè)進路占用道岔資源具有時間上的排他性，同一時間最多只能被一項作業(yè)占用，即

7) 到發(fā)線占用與車底出入段作業(yè)之間的時間接續(xù)關(guān)系

始發(fā)列車i的車底出庫時刻與占用到發(fā)線的開始時刻對應(yīng)，即

終到列車i的車底入庫時刻與占用到發(fā)線的結(jié)束時刻對應(yīng)，即

列車i的車底作業(yè)開始、結(jié)束時刻間的關(guān)系為

8) 車底出入段和客技線占用的時間接續(xù)關(guān)系

車底c的入庫時刻為其占用客技線的開始時刻tc，即

車底c占用客技線的結(jié)束時刻t′c為其出庫時刻，即

式中：αic為0-1變量，若列車i套用車底c，其值為1，否則，其值為0。

9) 車底在客技線整備作業(yè)的時長約束

車底占用客技線進行整備作業(yè)的時間不短于最小整備作業(yè)時間B，即

10) 列車在車站始發(fā)、終到作業(yè)的時長約束

始發(fā)列車在車站占用到發(fā)線的時間標準不短于最小始發(fā)作業(yè)時間D，即

終到列車在車站占用到發(fā)線的時間標準不短于最小終到作業(yè)時間A，即

11) 調(diào)機牽引作業(yè)之間的接續(xù)關(guān)系約束

調(diào)機牽引作業(yè)的合理安排可被描述成一個指派問題，其約束如下：

12) 調(diào)機牽引作業(yè)之間的接續(xù)時間約束

調(diào)機牽引作業(yè)之間的接續(xù)時間為：

2.2 目標函數(shù)

鐵路客站的調(diào)機運用與列車徑路安排綜合優(yōu)化，有以下調(diào)機牽引作業(yè)的總接續(xù)時間最少、調(diào)機牽引作業(yè)的總接續(xù)里程最短和車站到發(fā)線的利用效用最大等3個目標，分別為：

式(33)中ciw為列車i占用到發(fā)線w的效用，列車占用到發(fā)線符合固定使用方案則具有較高效用，到發(fā)線全日固定使用時間系扣除天窗并考慮一定空費后的純占用時間，最大為1 122 min。

需要注意的是，該優(yōu)化問題不一定具有可行解，當(dāng)接發(fā)列車數(shù)量超過客站能力時，車站只能盡可能多地為列車安排過站徑路，較高等級的列車優(yōu)先安排。為此，將式(4)和式(6)分別松弛為

引入μ1,μ2,μ33個權(quán)重系數(shù),將3個優(yōu)化目標歸一化處理，引入列車i的等級權(quán)重δi(等級越高，δi越大)和大的罰因子θ將約束條件(34)和(35)作為目標函數(shù)的一部分，也即有

由此，得到由優(yōu)化目標(36)和約束條件(5)，(7)～(30)構(gòu)成的鐵路客站調(diào)機運用與列車徑路安排綜合優(yōu)化模型。

3 求解算法

由于模型的復(fù)雜性，本文選用模擬退火進行求解。依據(jù)問題的求解內(nèi)容，設(shè)計的退火解由車底出入段時間方案和對應(yīng)的列車過站徑路方案構(gòu)成，其中前一方案可表示為滿足約束條件(19)～(26)的時間集合T={ti,t′j:i∈S,j∈Z}。以車底出入段時間方案T下的極大列車過站徑路方案(J,X(J))作為列車過站徑路方案，其中列車集J?I，X(J)為車底出入段時間方案T下滿足約束條件(8)～(22)且不存在可行性擴展的

由此，模型的可行解可表示為(T,(J,X(J)))。

為盡量縮短始發(fā)、終到列車的到發(fā)線停留時間，設(shè)定ω為車底出入段的可行時間范圍，限定始發(fā)列車i∈S的車底出庫時間ti的取值范圍為終到列車i∈Z車底入庫時間的選擇范圍為，其中為始發(fā)列車i∈S的車底最晚出庫時間，為終到列車i∈Z的車底最早入庫時間。ω的取值必須滿足車底整備最小作業(yè)時間要求，以保證車底出入段作業(yè)時間滿足式(19)～(26)的要求。

(T,(J,X(J)))的鄰域解有兩種構(gòu)造方法：第1種方法是從始發(fā)終到列車集合中任意選擇k列車構(gòu)成的列車集J′，重新為這些列車安排車底出入段作業(yè)時間得到新的車底出入段時間方案T′，然后在保持列車集J″=J-J∩J′的過站徑路方案X(J″)不變的基礎(chǔ)上，基于車底出入段時間方案T′尋找列車集及其過站徑路方案使得構(gòu)成新的極大列車進路方案，由 此 得 到 (T,(J,X(J))) 的 鄰 域 解第2 種方法是從J中任意剔除k列車得列車集J?，然后在保持車底出入段時間方案T和列車集J?過站徑路方案不變的情況下，尋找列車集?及其過站徑路方案使構(gòu)成型的極大列車過站徑路方案，由此得到的鄰域解2 種鄰域結(jié)構(gòu)在退火過程中按等概率隨機選用，以擴大搜索范圍。為改善求解效率，采用變步長的溫度下降機制。

4 算例分析

針對某既有線繁忙鐵路客運站進行調(diào)機運用和列車徑路安排方案優(yōu)化，并與既有運營情況進行比對，以測試本模型與算法的優(yōu)化效果。該客站站型如圖1 所示，其中正線Ⅰ道和3，5 道用來接發(fā)下行方向的列車，正線Ⅱ道和4，6 和10 道用來接發(fā)上行方向的列車，8道為機車走行線，10道鄰靠基本站臺，客整所設(shè)有14 條供車底整備的客技線。該站目前全日接發(fā)列車總數(shù)為132列，其中停站通過100 列，始發(fā)、終到各16 列；在既有作業(yè)組織方式下，到發(fā)線辦理能力利用率為84.8%、車站咽喉道岔通過能力利用率為79.2%，到發(fā)線和咽喉道岔能力均較為緊張。

圖1 某客站站型布局圖Fig.1 Layout of a passenger station

車站所有進路均采用一次解鎖，左、右兩端咽喉道岔占用時間標準分別為1 min 和2 min。始發(fā)、終到列車的最小作業(yè)時間D和A均為25 min，同一條到發(fā)線先后接發(fā)列車的最小間隔為4 min，車底出入客整所作業(yè)的咽喉走行時間Q為10 min，最小的接續(xù)時間J按10 min考慮，最小整備作業(yè)時間B為5 h。目標函數(shù)中因子μ1=100.0，μ2,u3=10.0；懲罰因子θ=50 000.0，始發(fā)、終到列車的權(quán)重均取10.0，其他列車取5.0。

根據(jù)列車等級、方向及車站的到發(fā)線固定使用方案等因素確定各條到發(fā)線利用效用，見表1。

表1 到發(fā)線利用效用Table 1 Utility of arrival departure line

模擬退火計劃的相關(guān)參數(shù)為：初始溫度取200 000.0，初始的溫度下降比例取0.9，溫度低于10 時下降比例變更為0.5，每一溫度下進行200 次迭代，算法終止條件為溫度低于0.5或連續(xù)20次最優(yōu)解無改變。

表2 給出了優(yōu)化結(jié)果中部分列車的徑路方案，車底出入段時間及到發(fā)線利用方案見圖2和圖3。

圖2 18-6點到發(fā)線利用方案Fig.2 Utilization scheme of arrival departure line between 18-6 o’clock

圖3 6-18點到發(fā)線利用方案Fig.3 Utilization scheme of arrival departure line between 6-18 o’clock

表2 列車過站徑路方案(部分)Table 2 Train passing route scheme(part)

采用所提出的模型和算法對該客運站作業(yè)過程進行綜合優(yōu)化后，車站到發(fā)線、咽喉道岔的能力利用率分別降至70.7%和69.9%，可見，通過優(yōu)化調(diào)機運用與列車徑路安排，可有效緩解鐵路客運站到發(fā)線和咽喉道岔能力緊張的情況。因此，前文所建立的模型和算法優(yōu)化效果良好。

5 結(jié)論

1) 通過旅客列車過站徑路優(yōu)化建模，對接發(fā)列車作業(yè)進路排列與車站咽喉、到發(fā)線利用進行了一體化優(yōu)化。

2) 將接發(fā)列車作業(yè)進路、車底作業(yè)進路和時間作為決策對象，把調(diào)機運用和旅客列車過站徑路相結(jié)合，構(gòu)建了調(diào)機運用與鐵路客運站列車過站徑路一體化優(yōu)化模型，并基于模擬退火思想設(shè)計了該模型的求解算法。

3) 算例表明建立的模型可實現(xiàn)鐵路客運站接發(fā)列車作業(yè)進路排列、咽喉及到發(fā)線利用和調(diào)機運用的一體化優(yōu)化；求解算法運算快，結(jié)果合理正確，可為客運站的日常行車組織工作提供科學(xué)的決策依據(jù)。