鐵路技術(shù)站進(jìn)路調(diào)度問題優(yōu)化研究

趙 軍，向江海，彭其淵

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

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

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

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

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

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

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

1 問題描述

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

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

1.1 調(diào)度對(duì)象

1.1.1 工作

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

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

1.1.2 活動(dòng)

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

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

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

1.2 進(jìn)路模式

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

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

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

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

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

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

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

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

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

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

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

1.3 問題轉(zhuǎn)化

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

2 數(shù)學(xué)方法

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

2.1 約束條件

2.1.1 唯一性約束

唯一性約束指必須且正好為每項(xiàng)活動(dòng)指派一個(gè)進(jìn)路模式，即每項(xiàng)活動(dòng)有且僅有一條進(jìn)路和一個(gè)開始時(shí)刻。令xb為0-1指示變量，若將進(jìn)路模式b指派給其所屬活動(dòng)，則取值為1，否則，取值為0。唯一性約束可表達(dá)為

( 1 )

2.1.2 時(shí)空一致性約束

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

引入空間一致性活動(dòng)對(duì)集合

任一活動(dòng)對(duì)(a,a′)∈Q1表示前項(xiàng)活動(dòng)a的終點(diǎn)需與后項(xiàng)活動(dòng)a′的起點(diǎn)相同，例如機(jī)車入段起點(diǎn)需與其列車到達(dá)的終點(diǎn)相同。

類似的，引入時(shí)間一致性活動(dòng)對(duì)集合

任一活動(dòng)對(duì)(a,a′)∈Q2表示前項(xiàng)活動(dòng)a的結(jié)束時(shí)刻需與后項(xiàng)活動(dòng)a′的開始時(shí)刻滿足給定時(shí)間間隔σa,a′，例如機(jī)車入段只能在對(duì)應(yīng)列車到達(dá)后才能開始。

有Q1?Q2，基于這兩個(gè)集合，可靈活描述以下活動(dòng)對(duì)間的時(shí)空一致性要求：

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

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

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

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

(1) 空間一致性約束

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

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

( 2 )

由式( 1 )可得，式( 2 )左邊第一項(xiàng)∑xb和第二項(xiàng)∑xb′同時(shí)為1或0，意味著任意活動(dòng)對(duì)(a,a′)∈Q1所獲得的兩個(gè)進(jìn)路模式b和b′，滿足b的終點(diǎn)與b′的起點(diǎn)始終為同一站線p。

(2) 時(shí)間一致性約束

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

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

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

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

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

Step4令b′*為L(zhǎng)′中開始時(shí)刻最小的進(jìn)路模式，M={b∈L|b與b′*不匹配}，更新L:=M。

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

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

( 3 )

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

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

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

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

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

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

Step3按時(shí)刻值對(duì)G升序排序，當(dāng)兩時(shí)刻值相等時(shí)，結(jié)束時(shí)刻排在開始時(shí)刻之前。

Step5令g*為G中取值最小的時(shí)刻，若γ(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ā)車場(chǎng)的站線類型主要包括到發(fā)線、機(jī)待線、推峰線和牽出線等，與軌道區(qū)段相同，各站線同一時(shí)間至多被一列列車或一臺(tái)機(jī)車實(shí)際占用。但不同的是，任意進(jìn)路模式只能完整表示其包含軌道區(qū)段的占用時(shí)區(qū)，但不能完整表示其端點(diǎn)處站線的，各站線的占用時(shí)區(qū)需由開始和結(jié)束占用該站線的兩項(xiàng)活動(dòng)共同確定。此外，即使某條站線已被占用，機(jī)車仍可從端部進(jìn)入或離開該站線，但不可穿越該站線，例如，對(duì)于到達(dá)列車，其本務(wù)機(jī)車始發(fā)于其停留的到發(fā)線開始入段工作，其解體調(diào)機(jī)終到于其停留的到發(fā)線結(jié)束連掛工作；對(duì)于出發(fā)列車，其編組調(diào)機(jī)始發(fā)于其所占用的到發(fā)線開始解掛工作，其出發(fā)機(jī)車終到于其所占用的到發(fā)線結(jié)束出段工作。特規(guī)定列車工作必然實(shí)際占用其始點(diǎn)或終點(diǎn)處的站線，機(jī)車工作在當(dāng)且僅當(dāng)通過站線或在站線處停留/折返時(shí)才實(shí)際占用站線。

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

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

(1) 列車接車工作的末項(xiàng)活動(dòng)與其對(duì)應(yīng)列車推峰工作的首項(xiàng)活動(dòng)，占用相同到發(fā)線。

(2) 各列車轉(zhuǎn)線工作的末項(xiàng)活動(dòng)與其對(duì)應(yīng)列車發(fā)車工作的首項(xiàng)活動(dòng)，占用相同到發(fā)線。

(3) 各列車推峰工作的末項(xiàng)活動(dòng)與對(duì)應(yīng)調(diào)機(jī)下次連掛工作的首項(xiàng)活動(dòng)，占用相同推峰線。

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

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

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

?p∈Pb*∈Bd,p

( 5 )

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

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

?p∈Pb*∈Bd,p

( 6 )

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

( 7 )

2.3 整體模型與拓展

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

M 式( 7 )

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

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

標(biāo)準(zhǔn)模型M具有良好的可拓展性，只需對(duì)調(diào)度對(duì)象和進(jìn)路模式的生成規(guī)則進(jìn)行簡(jiǎn)單調(diào)整，便可刻畫多種運(yùn)營(yíng)條件下的進(jìn)路調(diào)度問題，具體如下：

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

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

2.4 迭代算法

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

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

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

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

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

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

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

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

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

3 算例分析

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

3.1 算例描述

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

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

表2 到達(dá)列車對(duì)應(yīng)技術(shù)作業(yè)信息

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

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

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

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

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

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

3.3 計(jì)算結(jié)果

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

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

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

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

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

3.4 靈敏度分析

3.4.1 站線指派策略的影響

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

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

表6 站線指派策略的比較

3.4.2 進(jìn)路解鎖方式的影響

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

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

表7 進(jìn)路解鎖方式的比較

4 結(jié)束語(yǔ)

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

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