趙 軍，向江海，彭其淵

(1. 西南交通大學 交通運輸與物流學院，四川 成都 611756； 2. 西南交通大學 綜合交通運輸智能化國家地方聯(lián)合工程實驗室，四川 成都 611756)

技術(shù)站是鐵路貨運網(wǎng)絡(luò)中的重要節(jié)點，通常以3～4 h為一個階段編制階段計劃，主要解決車流推算、調(diào)機運用和到發(fā)線安排等問題，以此指導日常運輸生產(chǎn)工作。其中，車流推算和調(diào)機運用常合稱為配流問題；以配流方案為輸入，制定到發(fā)線安排和進路排列計劃稱為進路調(diào)度問題。為確保階段計劃的可行性和有效性，應綜合優(yōu)化配流和進路調(diào)度決策，但整個問題非常復雜，更為可行的策略是先解決配流問題，再解決進路調(diào)度問題。本文探討給定配流方案下的技術(shù)站進路調(diào)度問題，已知車站數(shù)據(jù)、運行圖和配流方案，該問題關(guān)鍵在于同時指派并調(diào)度行車和調(diào)車作業(yè)的進路及其開始時刻，以使得所有作業(yè)在時間和空間上無沖突。與常規(guī)車站到發(fā)線安排相比，技術(shù)站進路調(diào)度問題優(yōu)化存在多項決策任務(wù)并行、作業(yè)間有復雜時空約束等難點。

目前,國外對鐵路車站到發(fā)線運用和進路排列問題開展許多研究工作，研究方法可大致分類為進路沖突法、資源沖突法和車間調(diào)度法，具體見文獻[1]。其中，進路沖突法將原問題抽象為沖突圖中的最大獨立集問題，相關(guān)模型包括點裝箱模型[2-3]、集合裝箱模型[4]和圖著色模型[5]。資源沖突法為基于進路沖突的改進方法，同時考慮所有進路對單個資源的占用情況，相關(guān)模型包括集合裝箱模型[6]、多商品流模型[7]和約束指派模型[8]。車間調(diào)度法將原問題轉(zhuǎn)化為作業(yè)車間調(diào)度問題，其中，車站被視為車間，資源和作業(yè)分別被視為車間中的機器和工件，其相關(guān)模型主要有約束規(guī)劃模型[9]、替代圖模型[10]和整數(shù)規(guī)劃模型[11]。

同時，國內(nèi)也對鐵路客運站到發(fā)線和進路指派問題開展一定研究。陳彥等[12]建立旅客列車過站徑路優(yōu)化的0-1規(guī)劃模型，并設(shè)計基于極大性概念的模擬退火算法。賈文崢等[13]將原問題轉(zhuǎn)換為約束滿意問題，并開發(fā)包含多項進程的約束規(guī)劃算法。趙鵬等[14]以到發(fā)線運用和咽喉區(qū)進路運用均衡為優(yōu)化目標，構(gòu)建0-1規(guī)劃模型，并編制模擬退火算法求解。郭彬等[15]基于作業(yè)鏈研究高鐵車站作業(yè)計劃魯棒性編制問題，以列車間總沖突系數(shù)最小為目標，建立基于列車時空資源占用函數(shù)的模型，并設(shè)計改進GRASP算法求解。馬駟等[16]建立高鐵車站進路分配優(yōu)化模型，并開發(fā)進路分配調(diào)整的動態(tài)優(yōu)化算法。彭其淵等[17]針對高鐵車站到發(fā)線運用調(diào)整開展研究，建立混合整數(shù)線性規(guī)劃模型，并設(shè)計分支定界算法求解。

然而，國內(nèi)當前鮮有文獻研究技術(shù)站進路運用問題。史峰等[18]探討技術(shù)站咽喉區(qū)進路排列問題，通過分別將咽喉和進路抽象為網(wǎng)絡(luò)和路徑，設(shè)計近似求解算法。崔炳謀等[19]研究編組站進路調(diào)度問題，將原問題轉(zhuǎn)換為作業(yè)車間調(diào)度問題，構(gòu)建0-1非線性規(guī)劃模型，并設(shè)計基于優(yōu)先權(quán)編碼的遺傳算法。龍建成等[20]針對相同問題，采用無向圖描述車場拓撲結(jié)構(gòu)，構(gòu)建混合整數(shù)非線性規(guī)劃模型，并設(shè)計雙層模擬退火算法求解。

綜上，國內(nèi)外主要針對鐵路客運站到發(fā)線和進路指派/調(diào)整開展研究，但所提出方法并不完全適用于我國鐵路技術(shù)站進路安排的實際情況。首先，所研究的調(diào)度對象往往只包括列車到發(fā)和出入庫作業(yè)，不包括機車出入段和調(diào)機解編作業(yè)。其次，所提出的方法普遍未考慮作業(yè)間復雜的時空一致性，且往往只被測試于小型和簡化的車站或車站的一端咽喉。最后，所建模型往往未考慮除到發(fā)線以外的其他資源的占用約束，且資源占用約束大多以進路為最小單位，與以軌道電路區(qū)段為單位進行分段解鎖的現(xiàn)場實際不符，模型精度有待提高。

鑒于此，本文為鐵路技術(shù)站進路調(diào)度問題開發(fā)完整且有效的求解策略。首先通過問題抽象，將原問題轉(zhuǎn)換為約束指派問題。其次，充分考慮作業(yè)間的時空一致性以及軌道電路區(qū)段和站線的占用約束，構(gòu)建0-1線性規(guī)劃模型，并討論模型的可拓展性和應對不可行的策略。最后，采用實際案例，驗證所提出方法的效果和效率。

1 問題描述

本文探討技術(shù)站單個負責列車接發(fā)作業(yè)的車場(包括到達場、出發(fā)場和到發(fā)場)在給定計劃時段內(nèi)的進路調(diào)度問題?；谲囌緮?shù)據(jù)、運行圖和配流方案，給定列車到發(fā)時刻、列車解編調(diào)機及其時刻，該問題在于為計劃時段內(nèi)各項技術(shù)作業(yè)指派并調(diào)度進路及其開始時刻。不同到發(fā)車場的進路調(diào)度問題大致相同，區(qū)別僅在于可使用的調(diào)度資源和需考慮的調(diào)度對象，以到達場為例，對所研究問題進行描述,到達場示意見圖1。根據(jù)《車站行車工作細則》規(guī)定的車站與區(qū)間、車場與機務(wù)段以及車場間的分界點，可確定車場的空間范圍。車場內(nèi)的資源主要包括各類站線、道岔、信號機、絕緣節(jié)等，其中站線和道岔由絕緣節(jié)分割成軌道電路區(qū)段(以下簡稱軌道區(qū)段)，站線和軌道區(qū)段組合形成進路。進路調(diào)度的主要資源為站線和軌道區(qū)段，V為所有站線和軌道區(qū)段資源的集合，v為索引。其中，站線可為列車或機車作業(yè)提供短暫停留和折返場所，包括到發(fā)線、機待線、推峰線、牽出線等，P為所有站線的集合，p為索引；U為軌道區(qū)段連接各類站線的集合，u為索引。為使各項作業(yè)時空無沖突且與其他車場技術(shù)作業(yè)銜接，技術(shù)站到發(fā)車場的進路調(diào)度不僅需考慮不同作業(yè)在時間和空間上的復雜一致性約束，還需滿足站線和軌道區(qū)段資源的嚴格占用約束。

到發(fā)車場的作業(yè)包括行車和調(diào)車作業(yè)，兩者均占用車場資源。為統(tǒng)一建模，引入“工作”、“活動”的概念將兩類作業(yè)分解為若干過程，重新定義進路調(diào)度對象，并借助“進路模式”的概念將原問題轉(zhuǎn)化為一類約束指派問題。同時，由于兩類作業(yè)存在差異，將從資源占用時間計算、目標權(quán)重取值和進路模式生成3個方面進行差異化處理。

1.1 調(diào)度對象

1.1.1 工作

定義技術(shù)站里列車或機車通過一條或多條進路而完成的特定走行過程為一項“工作”。據(jù)此，可將技術(shù)站各類列車的技術(shù)作業(yè)中列車或機車的走行過程分解為若干項工作，見表1。T為工作集合，t為索引。工作可分類為列車和機車工作，列車工作代表與列車接發(fā)和改編有關(guān)的作業(yè)，包括列車接車、列車推峰、列車轉(zhuǎn)線、列車發(fā)車工作；機車工作代表與機車站內(nèi)走行有關(guān)的作業(yè)，包括機車入段、機車出段、調(diào)機連掛和調(diào)機解掛工作。

表1 技術(shù)作業(yè)與工作對應關(guān)系

1.1.2 活動

完成一項工作時，列車或機車的走行過程需要占用一條或多條進路，占用進路的數(shù)量由車場結(jié)構(gòu)和作業(yè)程序決定。為詳細描述工作完成過程，定義列車或機車由一條進路的起點持續(xù)走行到終點的過程為一項活動，則一項工作可進一步分解為若干項活動。例如，圖1中，一列到達列車從進路信號機接入3道，占用1條接車進路，則該列車接車工作只包括1項活動；一臺解體調(diào)機從推峰線經(jīng)4道和1條機待線迂回走行至5道連掛一列待解列車，其全程走行占用3條調(diào)車進路，則該調(diào)機連掛工作由3項活動構(gòu)成。

At為工作t所有活動的集合，a為索引。若稱進路上的第一個資源為起點，最后一個資源為終點，則每項活動a的屬性可用五元組(ta,Oa,Da,sa,0,ea,0)表示，其中ta為活動所屬工作，Oa為起點集，Da為終點集，sa,0和ea,0分別為活動最早開始和最早結(jié)束時刻，其值由運行圖和配流方案給定，活動a∈At可描述工作t從起點oa∈Oa走行至終點da∈Da的過程。

活動為列車和機車走行的基本過程，本文以活動作為進路調(diào)度對象，進路調(diào)度的任務(wù)即是為每一項活動指派并調(diào)度進路及其開始時刻，并確保各活動的進路時空無沖突，以順利完成各項工作，進而完成各項技術(shù)作業(yè)。

1.2 進路模式

進路調(diào)度需為調(diào)度對象同時指派進路和調(diào)度進路開始時刻，為把兩項決策合并為一項決策，本文引入以下“進路模式”的概念：

定義工作t中活動a的進路模式b表示活動a的可選進路與時刻的組合，其屬性由所屬工作tb、所屬活動ab、起點ob∈Oa、終點db∈Da、開始時刻sb≥sa,0、結(jié)束時刻eb≥ea,0和資源占用鏈fb構(gòu)成，記為

(tb,ab,ob,db,sb,eb,fb)

資源占用鏈fb由1組資源占用組成，含直接占用資源和因敵對進路而間接占用的資源，記為

fb={{vb,i,kb,i}|i=1,…,|fb|}

{vb,i,kb,i}為某個具體的資源占用，包括占用資源名稱vb,i∈V及其占用時區(qū)kb,i=[lb,i,rb,i]，其中，lb,i和rb,i分別為占用開始和結(jié)束時刻。

各進路模式b的資源占用鏈fb不是現(xiàn)成數(shù)據(jù)，但可根據(jù)車場結(jié)構(gòu)、進路信息、對應活動性質(zhì)、列車/機車長度、重量及走行性能、車場聯(lián)鎖系統(tǒng)等進行計算[8,20]。顯然，構(gòu)造fb時，通過合理的參數(shù)設(shè)置，可體現(xiàn)不同行車和調(diào)車作業(yè)的差異性。

據(jù)定義，進路的起終點為站線或分界點，便于建模，規(guī)定起點或終點為站線的進路模式始發(fā)或終到于其所對應站線的中心，起點或終點是分界點的進路模式始發(fā)或終到于分界點。

對于活動a∈At，若由起點集Oa到終點集Da有n條進路，且基于最早開始時刻sa,0或最早結(jié)束時刻ea,0有m個開始時刻，則兩者組合可生成n×m個進路模式。記活動a∈At生成的所有進路模式的集合為Ba，所有活動的進路模式集合為

B={b:t∈T,a∈At,b∈Ba}

每個進路模式包含進路和開始時刻信息，可把進路調(diào)度問題的兩項決策合并為一項。

1.3 問題轉(zhuǎn)化

通過以上定義，工作、活動和進路模式三者之間的關(guān)系結(jié)構(gòu)見圖2，該結(jié)構(gòu)中的所有信息可通過車場拓撲結(jié)構(gòu)、運行圖和配流方案等數(shù)據(jù)提前生成?；诖?，若將技術(shù)站到發(fā)車場里的各項技術(shù)作業(yè)分解為若干項工作，并把工作進一步分解為幾項關(guān)聯(lián)活動，再為各項活動提前生成有限個包含進路和開始時刻信息的進路模式，則可將技術(shù)站進路調(diào)度問題轉(zhuǎn)化為一類特殊的約束指派問題，即從給定的若干個進路模式中為各個工作的各項活動指派進路模式，以使得所有活動的進路模式時空無沖突，且擬定的目標函數(shù)達到最優(yōu)。

2 數(shù)學方法

本節(jié)首先將技術(shù)站進路調(diào)度問題構(gòu)建為1個0-1線性規(guī)劃模型。為使所有活動無時空沖突，該模型考慮唯一性、時空一致性、以及軌道區(qū)段和站線占用約束。其中，時空一致性約束確保給定活動對在空間上具有一致的起終點，且在時間上滿足要求的時間間隔。軌道區(qū)段和站線占用約束確保各軌道區(qū)段和各站線在同一時間至多能被一列列車或一臺機車占用。然后，討論模型的可拓展性，并設(shè)計迭代算法，確保模型找到可行進路調(diào)度方案。

2.1 約束條件

2.1.1 唯一性約束

唯一性約束指必須且正好為每項活動指派一個進路模式，即每項活動有且僅有一條進路和一個開始時刻。令xb為0-1指示變量，若將進路模式b指派給其所屬活動，則取值為1，否則，取值為0。唯一性約束可表達為

( 1 )

2.1.2 時空一致性約束

在技術(shù)站，不同技術(shù)作業(yè)在空間上有銜接關(guān)系，在時間上有先后順序，且不同作業(yè)間存在安全時間間隔，因此不同活動之間存在著緊密的時空聯(lián)系，稱為時空一致性。

引入空間一致性活動對集合

任一活動對(a,a′)∈Q1表示前項活動a的終點需與后項活動a′的起點相同，例如機車入段起點需與其列車到達的終點相同。

類似的，引入時間一致性活動對集合

任一活動對(a,a′)∈Q2表示前項活動a的結(jié)束時刻需與后項活動a′的開始時刻滿足給定時間間隔σa,a′，例如機車入段只能在對應列車到達后才能開始。

有Q1?Q2，基于這兩個集合，可靈活描述以下活動對間的時空一致性要求：

① 為避免工作分解導致不可行解，屬于同一工作的任意相鄰活動對應滿足時空一致性約束。為此，對于各個活動數(shù)大于1的工作t∈T，|At|>1，令活動對(a,a′)既屬于Q1，也屬于Q2，其中，a,a′∈At，a≠|(zhì)At|，且活動a′僅后于活動a。

② 來自于不同工作但對應同一列車的活動間存在時空一致性要求。對于到達列車，集合Q1和Q2包括各列車接車工作的末項活動分別與其對應機車入段工作的首項活動和與其對應列車推峰工作的首項活動、以及各調(diào)機連掛工作的末項活動與其對應列車推峰工作的首項活動。對于出發(fā)列車，集合Q1和Q2包括各列車轉(zhuǎn)線工作的末項活動分別與其對應調(diào)機解掛工作的首項活動和與其對應列車發(fā)車工作的首項活動、以及各機車出段工作的末項活動與其對應列車發(fā)車工作的首項活動。

③ 屬于不同工作但對應同一調(diào)機的活動對也具有時間或空間一致性要求。對于解體調(diào)機，各列車推峰工作的末項活動與其對應調(diào)機的下次連掛工作的首項活動屬于集合Q1和Q2。對于編組調(diào)機，各調(diào)機解掛工作的末項活動與該調(diào)機下次轉(zhuǎn)線工作的首項活動屬于集合Q2。

④ 為避免運營過程中的潛在沖突，還可要求部分活動對滿足時間一致性約束。例如，集合Q2可包括各機車入段工作的首項活動與其對應調(diào)機連掛工作的首項活動、以及各調(diào)機解掛工作的首項活動與其對應機車出段工作的末項活動。

(1) 空間一致性約束

具有空間一致性的活動對的銜接點為各類站線。對(a,a′)∈Q1，令Ba,d,p為活動a所有終點為站線p∈P的進路模式集合，即Ba,d,p={b∈Ba|db=p}；令Ba′,o,p為活動a′所有起點為站線p∈P的進路模式集合，即Ba′,o,p={b′∈Ba′|ob′=p}；令Pa,a′?P為活動a可終到且活動a′可始發(fā)的站線集合，即Pa,a′={p∈P|Ba,d,p≠?,Ba′,o,p≠?}?；赑a,a′，通過式(2)限制各站線p∈Pa,a′處可指派的進路模式，可確?？臻g一致性約束：

?(a,a′)∈Q1p∈Pa,a′

( 2 )

由式( 1 )可得，式( 2 )左邊第一項∑xb和第二項∑xb′同時為1或0，意味著任意活動對(a,a′)∈Q1所獲得的兩個進路模式b和b′，滿足b的終點與b′的起點始終為同一站線p。

(2) 時間一致性約束

為滿足作業(yè)間的時間間隔要求，對于活動對(a,a′)∈Q2，直觀上可對不滿足時間間隔要求的兩兩進路模式進行約束。為使約束更緊湊，這里提出“極大不匹配進路模式集對”的概念對該約束進行建模。對于活動對(a,a′)∈Q2，有如下定義：

① 進路模式b∈Ba與b′∈Ba′稱為是不匹配的，當且僅當b′的開始時刻與b的結(jié)束時刻之差小于要求的間隔時間，即sb′-eb<σa,a′；否則，稱為是匹配的。

② 進路模式集M?Ba與N?Ba′稱為是不匹配的，當且僅當其包含的所有進路模式對(b,b′):b∈M,b′∈N都是不匹配的。

③ 集合M?Ba與N?Ba′稱為是極大不匹配的，當且僅當對所有的b*∈BaM，進路模式集對(M∪{b*},N)至少包含1個匹配進路模式對，且對所有的b′*∈Ba′N，進路模式集對(M,N∪{b′*})也至少包含1個匹配進路模式對。

Step2對Ba按結(jié)束時刻升序排序，創(chuàng)建有序列表L；對Ba′按開始時刻升序排序，創(chuàng)建有序列表L′。

Step4令b′*為L′中開始時刻最小的進路模式，M={b∈L|b與b′*不匹配}，更新L:=M。

Step5若L≠?，則令b*為L中結(jié)束時刻最小的進路模式，N′={b′∈L′|b′與b*不匹配}，更新N:=N∪N′，L′:=L′-N′。

基于此，為滿足時間一致性，只需限制各活動對的各極大不匹配進路模式集對H=(M,N)中，最多只能選擇1個進路模式

( 3 )

2.1.3 軌道區(qū)段占用約束

技術(shù)站任一軌道區(qū)段同一時間至多被一列列車或一臺機車占用，由此，需確保任一軌道區(qū)段的所有占用時間區(qū)間無交叉，稱為軌道區(qū)段占用約束。由定義可知，進路模式b占用軌道區(qū)段vb,i的時間區(qū)間為[lb,i,rb,i]，直觀上可對時區(qū)有交叉的兩兩進路模式進行約束，以規(guī)避時區(qū)交叉情形。本文為加強對該約束的建模，特引入“極大不相容進路模式集”的概念：

(1) 進路模式b∈B與b′∈B稱為是不相容的，當且僅當其需在同一時間占用同一軌道區(qū)段u，即?u∈U，vb,i=vb′,i′=u，[lb,i,rb,i]∩[lb′,i′,rb′,i′]≠?；否則，稱為是相容的。

(2) 定義軌道區(qū)段u的占用方案Bu為給定B中所有需占用u的進路模式集，即Bu= {b∈B|?vb,i=u}。稱集合Cu?Bu在軌道區(qū)段u上是不相容的，當且僅當其包含的所有進路模式對(b,b′):b,b′∈Bu,b≠b′都是不相容的。

(3) 稱集合Cu?Bu在軌道區(qū)段u上是極大不相容的，當且僅當對所有的b*∈BuCu，進路模式集Cu∪{b*}至少包含1個相容進路模式對。

Step2取Bu中所有進路模式的占用結(jié)束時刻和開始時刻，創(chuàng)建時刻列表G。其中，各時刻g∈G有一個三元組屬性((α(g),β(g),γ(g))，分別表示其時刻值、所屬進路模式以及時刻指示標記(若g為結(jié)束時刻，則γ(g)為1，否則為0)。

Step3按時刻值對G升序排序，當兩時刻值相等時，結(jié)束時刻排在開始時刻之前。

Step5令g*為G中取值最小的時刻，若γ(g*)=0，轉(zhuǎn)Step6，否則，轉(zhuǎn)Step7。

Step6更新Cu:=Cu∪{β(g*)}，δ:=1，轉(zhuǎn)Step8。

Step8更新G:=G-{g*}，返回Step4。

( 4 )

2.1.4 站線占用約束

技術(shù)站到發(fā)車場的站線類型主要包括到發(fā)線、機待線、推峰線和牽出線等，與軌道區(qū)段相同，各站線同一時間至多被一列列車或一臺機車實際占用。但不同的是，任意進路模式只能完整表示其包含軌道區(qū)段的占用時區(qū)，但不能完整表示其端點處站線的，各站線的占用時區(qū)需由開始和結(jié)束占用該站線的兩項活動共同確定。此外，即使某條站線已被占用，機車仍可從端部進入或離開該站線，但不可穿越該站線，例如，對于到達列車，其本務(wù)機車始發(fā)于其停留的到發(fā)線開始入段工作，其解體調(diào)機終到于其停留的到發(fā)線結(jié)束連掛工作；對于出發(fā)列車，其編組調(diào)機始發(fā)于其所占用的到發(fā)線開始解掛工作，其出發(fā)機車終到于其所占用的到發(fā)線結(jié)束出段工作。特規(guī)定列車工作必然實際占用其始點或終點處的站線，機車工作在當且僅當通過站線或在站線處停留/折返時才實際占用站線。

引入站線占用活動對集合Q3，各活動對(a,a′)∈Q3表示前項活動a與后項活動a′分別實際開始和結(jié)束占用某條站線，由于這兩項活動必須按正確的時間順序終到和始發(fā)于相同的站線，因此需要滿足時空一致性要求，即Q3?Q1?Q2。由定義，任意活動對(a,a′)∈Q3中，開始占用活動a必然對應唯一的結(jié)束占用活動a′，記為θ(a)。

根據(jù)現(xiàn)場實際，集合Q3包括：

(1) 列車接車工作的末項活動與其對應列車推峰工作的首項活動，占用相同到發(fā)線。

(2) 各列車轉(zhuǎn)線工作的末項活動與其對應列車發(fā)車工作的首項活動，占用相同到發(fā)線。

(3) 各列車推峰工作的末項活動與對應調(diào)機下次連掛工作的首項活動，占用相同推峰線。

(4) 各活動數(shù)大于1的機車工作的各相鄰活動對，占用相同到發(fā)線或機待線。

任意站線p∈P的三種可行占用情形見圖3。可見，第一種情形，若站線p在計劃初和計劃末均空閑，則其每次占用由1個開始占用活動a和1個結(jié)束占用活動a′構(gòu)成。第二種，若站線p在計劃初被占用，則其第1個占用可能只有1個結(jié)束活動a′，對此，為了建模方便，可為活動a′引入1個虛擬開始活動a，令其對站線p的占用時區(qū)早于計劃初時刻，基于此構(gòu)建1個虛擬活動對(a,a′)并添入集合Q3。第三種，若站線p在計劃末被占用，則其最后1個占用可能只有1個開始活動a，類似地，也可為活動a引入1個虛擬結(jié)束活動a′，令其對其對站線p的占用時區(qū)晚于計劃末時刻，創(chuàng)建虛擬活動對(a,a′)并納入集合Q3。從而，三種站線占用情形可采用統(tǒng)一的方法進行建模。

令Bd,p為實際開始占用站線p∈P的進路模式集合，即Bd,p={b∈Ba|db=p,(a,a′)∈Q3}，Bo,p為實際結(jié)束占用站線p∈P的進路模式集合，即Bo,p={b′∈Ba|ob′=p,(a,a′)∈Q3}。一項活動只有在開始占用某條站線時才可能在該條站線處與其他活動沖突，且任意站線在被當前占用活動釋放后可立刻由其他活動開始占用，所以，對Bd,p中所有的占用開始時刻引入占用約束足以刻畫站線p∈P的占用情況。即對各站線p∈P，為滿足占用要求，只需在其各個占用開始時刻lb*,p∈{lb,p:b∈Bd,p}限制占用該站線的活動數(shù)不大于1，即

?p∈Pb*∈Bd,p

( 5 )

由唯一性約束式( 1 )，式( 5 )左邊第一項表示在時刻lb*,p前已開始占用站線p的活動數(shù)，第二項表示在時刻lb*,p前已結(jié)束占用站線p的活動數(shù)，兩者之差即表示在時刻lb*,p正占用站線p的活動數(shù)。

由一致性約束式( 2 )、式( 3 )，任意活動只有在進入站線后才可能離開站線，換言之，任意站線在任意時刻的占用活動數(shù)不可能為負數(shù)。同時，任意活動對(a,a′)∈Q3中，活動a′的所有進路模式Ba′在站線p上存在一個最晚占用結(jié)束時刻τa′,p，即τa′,p=max{rb′,p:b′∈Ba′|ob′=p}。由于活動對(a,a′)∈Q3滿足時空一致性約束，若lb*,p≥τa′,p，則活動a終到于站線p的所有進路模式Ba,d,p必包含于{b∈Bd,p|lb,p≤lb*,p}，且活動a′始發(fā)于站線p的所有進路模式Ba′,o,p也必包含于{b′∈Bo,p|rb′,p≤lb*,p}，由此，式( 5 )對該活動對恒有∑b∈Ba,d,pxb-∑b′∈Ba′,o,pxb′=0。因此，將式( 5 )改進為

?p∈Pb*∈Bd,p

( 6 )

2.2 目標函數(shù)

( 7 )

2.3 整體模型與拓展

綜上，技術(shù)站進路調(diào)度問題可構(gòu)建為以下0-1線性規(guī)劃模型

M 式( 7 )

s.t. 式( 1 )—式( 4 )和式( 6 )

xb∈{0,1} ?t∈Ta∈Atb∈Ba

標準模型M具有良好的可拓展性，只需對調(diào)度對象和進路模式的生成規(guī)則進行簡單調(diào)整，便可刻畫多種運營條件下的進路調(diào)度問題，具體如下：

(1) 為描述中轉(zhuǎn)旅客和貨物列車，模型M可調(diào)整調(diào)度工作的內(nèi)容以及工作間的對應關(guān)系。例如，對于各需更換機車的中轉(zhuǎn)列車，可將其抽象為1個列車接車工作和1個列車發(fā)車工作，并令其列車接車工作對應1個機車入段工作，其列車發(fā)車工作對應1個機車出段工作。對于各只作技術(shù)檢查的中轉(zhuǎn)列車，只需將其分解為1個列車接車和1個列車發(fā)車工作。

(2) 模型M通過調(diào)整特殊工作的初始進路模式集，可刻畫旅客列車和特種貨物列車的股道要求、到發(fā)線/推峰線固定使用方案，進路一次/分段解鎖等特殊的運營規(guī)則。例如，只為旅客列車工作生成端點為鄰接站臺到發(fā)線的進路模式，也只為特種列車工作生成可通往具備接車條件到發(fā)線的進路模式；同時，可按照站線固定使用方案為各列車/機車工作生成進路模式集；此外，進路不同的解鎖方式可在生成各進路模式的資源占用鏈時進行刻畫。

2.4 迭代算法

為實施標準模型M，需對所有活動按一定的進路選項和開始時刻選項生成進路模式集B。在實際應用時，各活動a的Ba可包含其全部可行的進路選項，因為即使在大型到發(fā)車場，對于任意作業(yè)一般存在不超過20條可行進路，但是，開始時刻存在無窮多個，Ba只能包含有限個開始時刻選項。由此，基于給定的進路模式集B，標準模型M不一定能獲得可行解。為此，鑒于任意可行的進路調(diào)度方案必然可為所有活動指派時空無沖突的進路模式，在標準模型M中，將目標函數(shù)替換為最大化加權(quán)獲得進路模式活動的數(shù)量，并將唯一性等式約束式( 1 )松弛為不等式，構(gòu)建技術(shù)站進路調(diào)度問題的輔助模型為

式( 2 )—式( 4 )、式( 6 )

xb∈{0,1} ?t∈Ta∈Atb∈Ba

與標準模型相比，輔助模型A不依賴于進路模式集B，總存在可行解，例如，解x={xb=0:t∈T,a∈At,b∈Ba}為可行解。另外，給定進路模式集B下，若輔助模型A的最優(yōu)解中獲得進路模式的活動數(shù)不為∑|At|，意味著標準模型M不可行，此時，需為活動提供額外的進路或開始時刻選項來擴充其進路模式，以擴大標準模型可行域的范圍。

基于此，提出進路調(diào)度迭代算法，反復求解、檢驗并增廣輔助模型A，直到所有活動可在當前進路模式集B下獲得時空無沖突的進路模式，主要步驟如下：

Step1對進路模式集B進行初始化。所有活動a均包含其端點間所有可行的進路選項。為盡早給行車作業(yè)安排進路，與列車接車和列車發(fā)車工作有關(guān)的活動a只包含1個開始時刻選項，為其最早開始時刻sa,0；為賦予調(diào)車作業(yè)更多機動性，基于統(tǒng)一步長ι，與機車入段、機車出段、調(diào)機連掛、調(diào)機解掛、列車推峰和列車轉(zhuǎn)線工作有關(guān)的活動a包含η個開始時刻選項，依次比其最早開始時刻sa,0晚0，ι，… ，(η-1)ι個時間單位。

Step2在每步迭代，基于當前進路模式集B，求解輔助模型A至最優(yōu)，將獲得最優(yōu)解中進路模式為空的活動視為關(guān)鍵活動。基于統(tǒng)一步長ι，為各關(guān)鍵活動a*擴充κ個開始時刻選項，其值依次比a*的當前最大開始時刻晚ι，2ι，… ，κι個時間單位?；诖?，通過遍歷給定進路選項和新的開始時刻選項，為a*擴充新的進路模式進入Ba。

Step3Step2迭代執(zhí)行，直到在當前進路模式集B下，輔助模型A的最優(yōu)解中獲得進路模式的活動數(shù)等于∑|At|。此時，使用當前進路模式集B，求解標準模型M，直到獲得最優(yōu)解或者其他預設(shè)終止條件達到為止，即可獲得最終的進路調(diào)度方案。

此外，在初始化和擴充進路模式集B時，為各活動提供了其所有可行進路選項，并從其最早開始時刻起往后逐步增加開始時刻選項。顯然，原問題的可行域隨著集合B的擴充逐步增大，若各活動的開始時刻選項被賦予的足夠多且計算時間允許，所提出算法可找到原問題最優(yōu)解。當然，為滿足階段計劃實時決策的需要，開始時刻選項和計算時間是有限的，但通過合理的參數(shù)設(shè)置，算法具備找到高質(zhì)量滿意解的能力。

3 算例分析

以某編組站下行到達場的實際數(shù)據(jù)構(gòu)造算例，驗證所提出方法的有效性。采用Matlab R2016a編程所提出方法，并調(diào)用CPLEX 12.8求解標準模型M和輔助模型A。所有計算在CPU為Inter Core i5-4210H 2.9 GHz，內(nèi)存為12 GB的64位個人計算機上執(zhí)行。

3.1 算例描述

測試車場采用分段解鎖的聯(lián)鎖系統(tǒng)，其拓撲結(jié)構(gòu)見圖4。圖中，B1和B2為車場與區(qū)間的分界點，分別銜接一個接車方向；B3—B8為車場與其他車場/段所的分界點。該車場設(shè)置到發(fā)線12條，可同時接入B1和B2方向的到達列車，其中A1為正線兼到發(fā)線；設(shè)置機待線3條，機車折返線1條；駝峰調(diào)車采取雙推單溜作業(yè)方案，設(shè)有2條推峰線H1和H2，配有2臺解體調(diào)機D1和D2；車場內(nèi)共計軌道區(qū)段98個，可排列進路220條(R為進路)，限于篇幅，省略軌道區(qū)段和進路詳細信息。

考慮測試車場06:00—09:00階段計劃中所有到達解體列車的進路調(diào)度任務(wù)。假設(shè)緊前階段無作業(yè)殘留到當前階段，階段初解體調(diào)機D1和D2分別停留于推峰線H1和H2上。階段內(nèi)共有15列到達解體列車，所有到達列車的技術(shù)作業(yè)按以下辦法進行參數(shù)設(shè)置：各到達列車的解體調(diào)機和解體開始時刻按先到先解原則確定，到達作業(yè)時間標準為30 min，解體作業(yè)時間標準為20 min，兩相鄰到達列車的解體結(jié)束間隔不小于8 min；列車長度為650 m，機車和調(diào)機長度為25 m，列車進站速度為30 km/h，機車入段和調(diào)機連掛速度為20 km/h，調(diào)機推峰速度為8 km/h?；诖?，到達列車對應技術(shù)作業(yè)信息見表2，其中，第6～9列為各項工作的活動編號。

表2 到達列車對應技術(shù)作業(yè)信息

測試算例共計60項工作和105項活動，各項活動的最早開始和最早結(jié)束時刻(sa,0和ea,0)按以下方法確定。列車接車工作唯一活動的ea,0取為到達時刻、sa,0取為到達時刻-可行進路最長走行時間。機車入段工作含2項活動，首項活動的sa,0取為到達時刻+3 min(試風和摘機車時間)，ea,0取為sa,0+最短走行時間；剩余活動的sa,0取為ea-1,0，ea,0取為sa,0+最短走行時間。調(diào)機連掛工作含3項活動，首項活動的sa,0取為解體開始時刻、ea,0取為sa,0+最短走行時間；剩余活動的sa,0取為ea-1,0，ea,0取為sa,0+最短走行時間。列車推峰工作唯一活動的sa,0取為對應調(diào)機連掛工作末項活動的et′,a,0+2 min(掛機車時間)、ea,0取為sa,0+最短走行時間。

令列車和機車活動的權(quán)重分別為10和1，正線和其余站線的權(quán)重分別為2和1。時間單位設(shè)為min，在初始化所有活動的進路模式時，步長ι取為1 min，個數(shù)η取為10。在擴充關(guān)鍵活動的進路模式時，個數(shù)κ取為5。

3.2 約束建模技術(shù)比較

如2.1.2節(jié)所述，對于時間一致性約束，一種直觀的建模方法為引入兩兩關(guān)聯(lián)不等式約束，規(guī)避同時選擇任意活動對任意兩個不匹配的進路模式。另一種可行的建模方法為采用本文提出的極大關(guān)聯(lián)不等式約束(3)，基于極大不匹配的概念將兩兩不匹配的進路模式最大可能地集計在同一個約束里。類似地，軌道區(qū)段占用約束既可直觀地采用兩兩關(guān)聯(lián)技術(shù)建模，也可采用本文提出的極大關(guān)聯(lián)不等式約束(4)建模。

兩類約束建模技術(shù)的比較結(jié)果見表3。其中，NTO為約束總數(shù)，NMI、NAV和NMA分別為各活動對或各軌道區(qū)段約束數(shù)的最小值、平均值和最大值；SMI、SAV和SMA分別為各約束涉及變量數(shù)的最小值、平均值和最大值。由表可得，對于時間一致性約束，極大關(guān)聯(lián)技術(shù)將原只含2個變量的弱約束加強為平均含190個變量的強約束，使得約束總數(shù)從115萬個減少到649個，減小4個數(shù)量級。對于軌道區(qū)段占用約束，極大關(guān)聯(lián)技術(shù)通過引入平均含38個變量的強約束將原721萬余個約束縮減至6 275個，減小3個數(shù)量級。因此，相比于兩兩關(guān)聯(lián)技術(shù)，所提出的極大關(guān)聯(lián)技術(shù)可顯著縮減模型規(guī)模，并有利于提高模型求解效率。

表3 約束建模技術(shù)比較

3.3 計算結(jié)果

測試算例求解過程如下：首先，基于給定技術(shù)作業(yè)信息和參數(shù)設(shè)置，為60項工作的105項活動生成初始進路模式16 749個；其次，通過求解輔助模型A一次，驗證標準模型M在初始進路模式下可行；接著，基于初始進路模式，求解標準模型M到最優(yōu)。最終，耗時48.9 s，得到解，總偏移時間為21 min，其中總列車和總機車偏移時間分別為3、18 min；總走行時間為444 min，其中總列車、總機車走行時間分別為197、247 min，總列車、總機車繞行率分別為3.1%、2.9%(繞行率=實際走行時間/最短走行時間-1)。為評估獲得解的質(zhì)量，分別設(shè)置η為20、30，重新運行算法。結(jié)果分別耗時169.8、191.2 s，得到相同最優(yōu)目標值。因此，可認定該解是測試算例的最優(yōu)解，后續(xù)計算分析中，參數(shù)η取10。

進度調(diào)度方案主要信息見表4，表中，DT，TT和DR分別指偏移時間、走行時間和走行繞行率。由表4可看出，求解質(zhì)量方面，此方案總偏移時間小，有利于實現(xiàn)階段計劃，具體只有8項機車入段活動共延遲9 min，有9項調(diào)機連掛活動共延遲9 min，有3項列車推峰活動共延遲3 min，除這些活動以外，其余活動均按最早開始時刻進行。同時，此方案繞行率較低，幾乎所有的列車和機車活動獲得走行時間最短的進路，有利于節(jié)省運營成本。關(guān)于計算時間，盡管同時提前生成進路和時刻選項可能增大模型規(guī)模，但所提出的方法耗時不到50 s便完成整個求解過程。綜上，本文方法具有較好的求解效果和效率，可滿足現(xiàn)場實時決策的需要。

表4 進度調(diào)度方案

主要資源占用見圖5，圖5中，橫坐標表示時間，縱坐標表示資源，標記“③混合占用”指列車和機車活動共同完成一次實際占用，如列車推峰末項活動與調(diào)機連掛首項活動完成對推峰線的占用。資源占用統(tǒng)計見表5，其中，資源利用程度=占用時間/階段計劃長度×100%。可見，站線占用方面，對于到發(fā)線，正線A1未被占用，處于下部的到發(fā)線利用程度較高，總的來看，到發(fā)線能力不緊張，部分到發(fā)線常處于空閑狀態(tài)，說明在研究階段內(nèi)到發(fā)線接車能力充足。對于推峰線，H1占用次數(shù)比H2多1次，且被占用的時間更長，總體上推峰線作業(yè)緊湊、能力較為緊張，駝峰能力可能限制研究車場能力的發(fā)揮。機待線和折返線中，因調(diào)機連掛主要在W3處折返，W3比W1繁忙，同時，W2和Z1被機車因折返入段占用的時間相當。對于軌道區(qū)段占用，各軌道區(qū)段占用次數(shù)和占用時間差距較大，其中，軌道區(qū)段114-162DG、138DG、130-136DG、142-154DG和141-161DG最為繁忙，利用程度最高的軌道區(qū)段(114-162DG)位于咽喉區(qū)的關(guān)鍵部位，是限制研究車場能力的瓶頸。

表5 資源占用統(tǒng)計

3.4 靈敏度分析

3.4.1 站線指派策略的影響

為評估不同站線指派策略的影響，設(shè)計三種比較策略。第一種稱為動態(tài)策略(DTA)，該策略完全根據(jù)所提出方法獲得的解為各項活動指派站線。第二種稱為靜態(tài)策略1(STA1)，該策略固定推峰線使用，規(guī)定解體調(diào)機D1和D2分別只能在H1和H2上進行推峰作業(yè)。第三種策略在STA1的基礎(chǔ)上，進一步固定到發(fā)線和機待線的使用，規(guī)定從B1方向來的到達列車只能接入A2、A3、A4和A6，從B2方向來的到達列車只能接入A6、A7、A8、A9、A10和A12，機車走行線限定為A5和A11，記為靜態(tài)策略2(STA2)。

站線指派策略比較結(jié)果見表6，其中，第2列和第3列分別為標準模型M的變量數(shù)和約束數(shù)，第4列為輔助模型A的迭代次數(shù)，TDT、TTDT和TEDT分別為總偏移時間、總列車偏移時間和總機車偏移時間，TTT、TTTT和TETT分別為總走行時間、總列車走行時間和總機車走行時間，TTDR和TEDR分別為總列車和總機車繞行率，最后1列為總的求解時間?？芍?，相比于DTA，STA1固定推峰線使用，使得偏移時間增加3 min，解的質(zhì)量略差，但變量數(shù)和約束數(shù)更少，求解速度更快。STA2在STA1基礎(chǔ)上進一步固定到發(fā)線和機走線使用，其解的質(zhì)量明顯下降，相比于DTA，總偏移時間增加55 min，將加大對階段計劃的影響，但另一方面STA2的變量數(shù)和約束數(shù)大為下降，求解時間顯著縮短。綜上，站線使用方案越固定，模型的變量數(shù)和約束數(shù)越少，求解速度更快，但解的質(zhì)量變差。因此，在實際應用時，可根據(jù)現(xiàn)場情況合理制定站線使用方案，以兼顧進度調(diào)度方案的質(zhì)量和編制速度。

表6 站線指派策略的比較

3.4.2 進路解鎖方式的影響

根據(jù)現(xiàn)場聯(lián)鎖系統(tǒng)，進路解鎖方式包括分段解鎖和一次解鎖兩種。在分段解鎖下，列車或機車尾部只要出清某軌道區(qū)段后即可釋放對該軌道區(qū)段的占用。而在一次解鎖下，列車或機車尾部只有在出清整個進路后才能一次釋放該進路上的所有軌道區(qū)段。顯然，一次解鎖下技術(shù)作業(yè)對資源的占用時間比分段解鎖下的更長，從而對模型的規(guī)模和解的質(zhì)量有影響。

進路解鎖方式比較結(jié)果見表7。由表7可見，兩種解鎖方式下，模型規(guī)模相當，且都能在較短時間內(nèi)獲得進路調(diào)度方案。但相比于分段解鎖，一次解鎖的總偏移時間增加11 min，總走行時間減少1 min，解的質(zhì)量更差，說明分段解鎖更有利于為活動盡早安排進路，從而減少偏移時間。因此，技術(shù)經(jīng)濟條件允許的到發(fā)車場應裝備分段解鎖的聯(lián)鎖系統(tǒng)，以確保車場的能力。

表7 進路解鎖方式的比較

4 結(jié)束語

本文通過引入工作和活動定義調(diào)度對象，利用進路模式表達決策變量，將原包含兩項決策任務(wù)的技術(shù)站進路調(diào)度問題轉(zhuǎn)化為只包含一項決策任務(wù)的約束指派問題。以總加權(quán)偏移和走行時間最小為目標，構(gòu)建包含唯一性、時空一致性和資源占用約束的0-1線性規(guī)劃模型。接著，提出標準模型的拓展方法，以描述更多的運營和安全要求，并通過構(gòu)建輔助模型，設(shè)計迭代算法，解決標準模型可能存在的不可行問題。最后，對實際算例的計算結(jié)果表明，所提出的進路調(diào)度方法具有較好的求解效果和高效的求解效率，可為解決技術(shù)站階段計劃優(yōu)化編制問題提供決策支持。

本文研究可在以下幾方面進行拓展。首先，所提出的方法未考慮站線占用的均衡性，下一步可將均衡性目標或要求納入進路調(diào)度問題，增強模型的優(yōu)化能力。其次，本文嘗試提出通用的進路調(diào)度描述范式和求解框架，但不同類型車站或車場的特點和復雜性不同，接下來可將所提出方法應用于更多類型的車站和車場，根據(jù)研究對象的特點對方法進行相應改進，擴大方法的適用范圍。另外，配流和進路調(diào)度是技術(shù)站階段計劃編制的兩個關(guān)鍵問題，相互影響，研究配流與進路調(diào)度綜合優(yōu)化、實現(xiàn)技術(shù)站階段計劃整體編制也是未來的研究方向。