考慮解編調車成本的鐵路技術站調車線運用優(yōu)化

趙 軍，張思宇，彭其淵

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

調車場是鐵路技術站里的重要調車設施，是供中轉車、本站作業(yè)車、維修車等車輛集結和停留的場所。車輛/車流去向-調車線的指派方案不僅直接影響駝峰解體和峰尾編組調車工作的質量，也限制車流推算、調機運用等車站作業(yè)計劃的可行性。目前，我國大多數(shù)技術站里，主要采用固用活用相結合的經驗規(guī)則使用調車線，此做法固然可降低調車線運用計劃的編制難度，但不適用于車流去向多、車流波動性強的技術站，也不利于控制解編調車成本及發(fā)揮調車場的能力。根據(jù)各類型車輛對調車場的占用需求，并結合調車線的固定使用方案，研究調車線靈活運用的優(yōu)化方法，是技術站作業(yè)計劃編制需解決的重要問題。

目前國外針對技術站調車線運用的研究不多。國外技術站調車作業(yè)壓力一般較小，列車解體和編組都由駝峰來完成，各去向的車輛可溜放到不同的調車線上，若調車線數(shù)量不足，某些去向的車輛需暫時停放在“混合線”上，后續(xù)再拉回駝峰進行二次解體，直到所有出發(fā)列車按要求完成編組。對此，Bohlin等[1]研究了含混合線的列車-調車線指派問題，以總重復解體車數(shù)最少為目標，分別建立了基于生成列和弧索引的整數(shù)規(guī)劃模型，并提出分支定價和滾動時域算法。Gestrelius等[2]進一步將出發(fā)列車的站順要求納入列車-調車線指派，構建了基于生成列的整數(shù)規(guī)劃模型，并采用分支定價算法求解。此外，國外還探討了含調車線指派的作業(yè)計劃綜合編制問題。例如，Gestrelius等[3]研究了列車-到達線/調車線指派與解體/編組排序綜合問題，提出了最小化重復解體車數(shù)和線路占用成本的整數(shù)規(guī)劃模型。Haahr等[4]針對車流推算、解體/編組排序和調車線指派綜合問題，設計了分解算法，其中，構建解體排序和編組排序問題的整數(shù)規(guī)劃模型，調車線指派由貪婪啟發(fā)式規(guī)則求解。Raut等[5]研究了相同的問題，但提出了整個問題的混合整數(shù)線性規(guī)劃模型，并采用滾動時域算法求解。

國內對技術站調車線運用開展了一定工作。在我國技術站特別是編組站，每天的改編工作量大，應用國外的解編調車模式會導致大量的重復解體工作，影響調車場的使用效率，由此，現(xiàn)場通常規(guī)定駝峰主要負責解體，而峰尾主要負責編組作業(yè)。根據(jù)國內實際情況，早期，任勇[6]、孫玉明等[7]和陳伯羽[8]主要探討了制定調車線固定使用方案的量化方法。近來，國內更關注技術站作業(yè)計劃編制階段的調車線靈活運用方法。薛鋒等[9]以出發(fā)列車集結占用線路數(shù)、調車線集結車流去向的分散度和調車線的空閑車數(shù)為目標，建立調車線調整運用優(yōu)化模型。黎浩東等[10]構建了最小化“整理線”數(shù)量和出發(fā)列車連掛次數(shù)的調車線運用優(yōu)化模型。張英群等[11]在此基礎上設計了禁忌算法求解模型。Zhang等[12]進一步考慮站順編組要求，對調車線運用模型進行拓展，并開發(fā)禁忌搜索算法求解。馬亮等[13]引入固定屬性作為車組的特征，以此為基礎，建立以調車線混亂度最小和占用優(yōu)先級最大的優(yōu)化模型，并設計啟發(fā)式回溯算法。

綜上，技術站調車線運用尚未引起國內外廣泛關注，國外方法不適用于我國實際情況，國內針對調車線固用和活用做了許多嘗試，但還存在進一步研究的空間，在編制作業(yè)計劃時，需根據(jù)車輛和調車場的實際情況，快速生成解編調車成本更低，滿足作業(yè)計劃兌現(xiàn)需要的調車線靈活運用方案。文獻[10-12]對本文工作有所啟發(fā)，但存在一些可改進的地方。文中提出了整理線這一概念，并嘗試最小化其數(shù)量，但沒有提出在這類線路存在時如何處理，事實上，整理線一旦出現(xiàn)，會給技術站帶來額外調車負荷，在制定調車線運用計劃時，應盡可能避免存在整理線。此外，僅使用出發(fā)列車連掛次數(shù)描述調車成本，不能具體刻畫由調車線運用產生的解編調車成本，還可能導致最優(yōu)解集過大，影響模型算法求解性能。

本文研究技術站作業(yè)計劃編制階段的調車線靈活運用優(yōu)化方法。定義由調車線運用帶來的解體和編組調車成本，并根據(jù)固定使用方案引入車組-調車線占用權重。以總加權解編調車成本最小為目標，考慮車組溜放和連掛、出發(fā)列車編組順序和調車線能力等要求，構建0-1非線性規(guī)劃模型，基于圖的極大團提出溜放和能力約束的緊湊表達式，該模型容易簡化為線性模型，并由商業(yè)軟件直接求解。最后采用算例驗證所建模型。

1 問題描述與假設

1.1 問題描述

本文考慮技術站的1個調車場在給定計劃時段內的調車線運用問題。典型調車場的結構見圖1，該車場一端與到達場相鄰，兩車場一般以調車信號機分界(例如D201)，中間設有駝峰，是到達列車解體的場所；另一端連接出發(fā)場，兩車場也以調車信號機分界(例如D301)，中部是峰尾，出發(fā)列車往往在這里編組。調車場由若干條平行且長度不一的線路組成，根據(jù)車站布置結構的不同，每條調車線可通達所有的或者部分駝峰溜放線和峰尾牽出線。對于各調車線，從與到達場分界的調車信號機至該條線入口端調車表示器的線路稱為溜放進路，從該條線出口端調車/發(fā)車信號機至與出發(fā)場分界的調車信號機的線路稱為連掛進路，該條線入口端調車表示器與出口端調車/發(fā)車信號機間的線路是可供車組集結的場所。

圖1 調車場示意圖

計劃時段內：A為到達列車集合；D為出發(fā)列車集合；R為調車線集合。到達列車有|A|列，各到達列車由若干去向的車輛組成，其編組內容、編組順序、解體起時和終時已知，將計劃時段初調車場的現(xiàn)在車視為1列虛擬到達列車。出發(fā)列車有|D|列，各出發(fā)列車的編組內容由提前確定的車流推算方案給定，其編組起時、終時已知，且必須按照給定的車流去向排列順序要求完成編組。根據(jù)車流推算結果，將計劃時段末各去向的殘存車分別視為1列虛擬出發(fā)列車。根據(jù)到達列車信息和車流推算方案，將到達列車中的車輛劃分為若干車組，作為調車線指派的基本對象，其集合為C。車組共有|C|個，各車組中的車輛來自于同一到達列車、具有相同的去向且緊鄰編組、并將接續(xù)同一出發(fā)列車，規(guī)定各車組在解體時需以一鉤溜往同一條調車線，且在編組時在其集結調車線上以一鉤完整連掛牽出。

共有|R|條調車線可用于車組集結占用，其能力以其有效長度量。規(guī)定各車組在其對應到達列車解體開始時即預定/實際占用為其指派的調車線，并在其接續(xù)的出發(fā)列車編組結束時才釋放對其指派調車線的占用。已知去向-調車線固定使用方案，各調車線可集結其固定和非固定去向的車組。各出發(fā)列車的車組可在多條調車線上集結，由多次連掛完成編組，各次連掛需將對應調車線上屬于該出發(fā)列車的車組全部牽出。為降低峰尾編組調車工作負擔，要求在各調車線上，任意車組的編組開始時刻不能早于比其更靠近峰尾車組的編組結束時刻，若如此，必然需在峰尾進行必要的中部挑車調車作業(yè)，增加額外編組作業(yè)時間。同時，各調車線的容車能力是有限的，任意時刻集結的車組總長不能超過其有效長。

接下來分析調車線運用對解編調車成本的影響。從圖1可見，車組經駝峰解體調車從到達場進入調車場，再經峰尾編組調車離開調車場進入出發(fā)場，為該車組指派哪條調車線主要影響其解體調車時的溜放作業(yè)過程和調車線上的走行過程、及峰尾編組時的連掛作業(yè)過程。因此，在研究的調車場范圍內，將各車組視為質點，將其解編調車過程劃分為溜放走行和連掛走行兩部分。

r為調車線，r∈R；hr、lr和pr分別為調車線r的溜放進路長度、有效長和連掛進路長度,m。規(guī)定各車組的解體調車成本與其溜放走行距離正相關，后者取為該車組指派調車線r對應的hr與lr之和。各車組的編組調車成本與其連掛走行距離正相關，后者的度量相對復雜，同時與為該車組指派的調車線r以及該車組接續(xù)出發(fā)列車的連掛作業(yè)有關。

例如，對車組連掛走行距離的度量進行描述。已知有1列出發(fā)列車，含5個車組(C1～C5)，車組C1和C2在調車線R1集結，車組C3～C5在調車線R2集結，根據(jù)編組順序要求，需依次對調車線R1和R2進行連掛。該出發(fā)列車的完整連掛過程見圖2。

圖2 連掛走行距離的度量

由圖2可知，若將各車組視為1個質點，對于車組C1和C2，在第1次連掛中，其連掛走行距離為p1，在第2次連掛中，該兩車組需要首先跟隨調機前往調車線R2連掛車組C3～C5，走行p2，之后再隨調機返回牽出線，再次走行p2。車組C3～C5在第1次連掛中無需走行，第2次連掛中的走行距離為p2。因此，車組C1和C2在連掛過程中需要走行的距離為p1+2p2，車組C3～C5在連掛過程中需要走行的距離為p2。

稍加整理，可得出一般性規(guī)律。若出發(fā)列車d的車組分布在|K|條調車線上，則在其編組過程中需進行|K|次連掛，一般的，各出發(fā)列車只進行有限次連掛，可根據(jù)實際情況確定一個|K|的取值上限。若其中一個車組c于第k次被連掛牽出，在編組出發(fā)列車d進行第k′(k≤k′≤|K|)次連掛時，都會產生一段連掛走行。當k′=k時，車組c的走行距離為發(fā)生第k′次連掛所在調車線對應的連掛進路長度；當k′>k時，車組c的走行距離為發(fā)生第k′次連掛所在調車線對應的連掛進路長度的2倍(隨調機往返于第k′次連掛的調車線)。

注意，本文對車組在進出調車線上的走行距離的度量做了適當簡化，但相比于既有研究[9-13]，可更為細致地刻畫因調車線運用帶來的解編調車成本，并在一定程度上降低模型的建模難度和求解難度。

綜上，技術站調車線運用問題可描述為：給定計劃時段內的車流推算方案(到發(fā)列車的車流接續(xù)方案)、到達列車的解體方案(解體起時、終時)、出發(fā)列車的編組方案(編組起時、終時),以及車流去向-調車線固定使用方案，為各車組指派調車線，以使得調車線占用不沖突、出發(fā)列車編組順序要求和調車線能力限制等約束得到滿足，且綜合衡量解編調車成本和調車線固定使用方案的總加權解編調車成本達到最小。

1.2 問題假設

根據(jù)給定計劃時段內提前確定的車流推算方案和列車解編方案，重在為到發(fā)列車間接續(xù)的有調中轉車輛指派調車線。為便于后續(xù)方法闡述，提出以下假設：

(1)不使用本站作業(yè)車、檢修車、禁溜車、特種車等車輛固定占用的調車線。

(2)只考慮受調車線運用影響的解編調車成本，包括解體調車過程中的溜放成本和編組調車過程中的連掛成本。

(3)不考慮列車/車輛的解體溜放和編組連掛的具體調車作業(yè)過程。

2 數(shù)學模型

2.1 符號定義

文中主要集合、參數(shù)和變量定義見表1。

表1 集合、參數(shù)及變量定義

2.2 目標函數(shù)

調車場是技術站的調車設施，衡量調車線運用方案優(yōu)劣的標準可為調車成本。受調車線運用影響的調車成本主要是解體溜放成本和編組連掛成本，1.1節(jié)對各車組的溜放成本和連掛成本的度量進行了說明。同時，為簡化調車工作，現(xiàn)場傾向于盡量按固定使用方案為車組指派調車線。因此，引入車組-調車線占用權重，提出總加權解編調車成本最小的目標函數(shù)，以期得到不僅調車成本低而且容易被現(xiàn)場接受的調車線運用方案，目標函數(shù)為

(1)

為盡量照顧調車線的固定使用方案，wcr的取值規(guī)定為：若調車線r是車組c的固用線路，即r∈Fc，取wcr=1；否則，將wcr設置為調車線r離車組c的所有固用線路的最小線間距，即wcr=min{grr′,r′∈Fc}。根據(jù)現(xiàn)場情況，不同調車線的總溜放和連掛走行距離的比值一般不超過1.5，且相鄰調車線的線間距一般不小于5 m。顯然，wcr的取值可使得各車組盡量在其固用調車線里選擇解編調車成本小的線路，若能力不足，也優(yōu)先選擇離其固用線路近且調車成本小的調車線。wcr的不同取值對計算結果的影響在3.2.4節(jié)作對比分析。

2.3 約束條件

2.3.1 唯一性約束

各車組經解體溜放作業(yè)從駝峰進入調車場，再由編組連掛作業(yè)由調車場進入峰尾牽出線。由此，在溜放過程中，車組c必須且僅能溜放到某條調車線r上，即

(2)

在連掛過程中，各車組c必須且只能在其歸屬出發(fā)列車的某次連掛k時于某條調車線r上牽出，即

(3)

各出發(fā)列車d在進行編組作業(yè)時可能經過一次或多次連掛才能編成，規(guī)定各次連掛k(如果存在)必須發(fā)生在某條調車線r上，且在各條調車線r上最多進行一次連掛，即各出發(fā)列車d的各次連掛k需將對應調車線r上集結的且屬于該出發(fā)列車的所有車組牽出，即

(4)

(5)

各出發(fā)列車d必然至少需要進行一次連掛，即

(6)

此外，變量xcr、yckr和zdkr需滿足關系約束

yckr=xcr·zdkr?d∈D,c∈Cd,k∈K,r∈R

(7)

式(7)表示只有當出發(fā)列車d的第k次連掛在調車線r上執(zhí)行(zdkr=1)，且其包含車組c也正在調車線r上集結(xcr=1)時，車組c才會在其歸屬出發(fā)列車d的第k次連掛時從調車線r上牽出(yckr=1)。通過式(7)可正確控制3個決策變量的取值。

2.3.2 溜放約束

為減輕峰尾編組調車工作壓力，具備以下沖突的車組不能溜往同一條調車線。

(1)編組時段沖突

屬于不同出發(fā)列車的車組在編組時段上可能存在沖突，簡稱編組時段沖突(Conflict of Assembly Interval, CoAI)，不能在同一條調車線上集結。具體地，對于任意兩屬于不同出發(fā)列車的車組c和c′，假設車組c的解體開始時刻比c′的早(ecuc′)，此時，若將這兩車組溜往同一條調車線r，車組c極有可能阻礙車組c′的編組連掛，為連掛車組c′，需先將車組c牽出置于另一條調車線，再回到調車線r，增加額外調車工作。應避免這種沖突，不允許車組c和c′占用同一條調車線。

參照文獻[10-12]的建模方法，可對所有車組C按解體開始時刻ec從小到大排序，然后對兩兩具有CoAI沖突的車組建立約束

vc-uc′≤M(2-xcr-xc′r)

?c,c′∈C|c

(8)

式中:M為充分大正數(shù)。

式(8)可確保具備CoAI沖突的車組不占用同一條調車線，但這類方法只針對兩兩車組引入約束，使得各約束只含2個變量，可能導致整個優(yōu)化模型的線性松弛結構松弛，影響求解性能。這里，利用圖的極大團對這類約束進行改進。

引入無向沖突圖G1=(C,I1)，其中，頂點集C為車組集，邊集I1表示車組的CoAI沖突，若車組c和c′具有CoAI沖突，則在這兩車組對應的頂點間連1條無向邊。車組集Cmc1?C為G1的1個團，當且僅當Cmc1中的任意兩車組c,c′∈Cmc1具有CoAI沖突，團Cmc1為極大團，當且僅當對所有車組c*∈CCmc1，車組集Cmc1∪{c*}中至少存在兩不具有CoAI沖突的車組，令CMC1為G1中所有極大團的集合。為避免具有CoAI沖突的車組溜往同一條調車線r，可限制每個極大團Cmc1?CMC1中，最多只有1個車組指派給該條調車線，即

(9)

相比于式(8)，式(9)中每個約束的變量數(shù)最少為2，最多可為車組的數(shù)量。因此，式(9)有助于加強整個模型線性松弛的定界能力，加快模型收斂。

(2)編組順序沖突

在具有特定編組順序要求的1列出發(fā)列車中，其車組由于指定的編組順序還可能存在沖突，簡稱編組順序沖突(Conflict of Block Sequence, CoBS)，也不能溜往同一條調車線。例如，某出發(fā)列車d有兩車組c和c′，假設coc′，若選擇在同一條調車線集結這兩車組，不能只用一個連掛鉤便可將c和c′編組為要求的排列順序。為簡化峰尾編組調車工作，應將車組c和c′安排在不同調車線上集結，再使用2個連掛鉤依次連掛車組c′和c，以保證這兩車組可按正確的順序排列。

文獻[12]考慮出發(fā)列車的編組順序要求，提出了兩兩編組順序沖突約束

oc-oc′≤M(2-xcr-xc′r)

?d∈D2,c,c′∈Cd|c

(10)

式(10)可保證各出發(fā)列車嚴格按照指定的編組順序編成，但該式與式(8)存在類似問題，不利于構建緊湊的數(shù)學模型。這里，同樣使用圖的極大團提出該約束的另一表達式。

類似地，引入另一個無向沖突圖G2=(C,I2)，其中，頂點集C包括所有車組，邊集I2代表車組的CoBS沖突，若車組c和c′具有CoBS沖突，則在這兩車組的頂點間構造1條無向邊。定義CMC2為G2中所有極大團的集合，索引為Cmc2∈CMC2。對各調車線r，要求在各極大團Cmc2∈CMC2中，最多只有1個車組可在該調車線上集結，由此，可避免同一列出發(fā)列車中存在CoBS沖突的車組同時溜放調車線r，即

(11)

式(11)可發(fā)揮式(10)相同的作用，但有助于提高該類約束的定界效果。

目前，尋找沖突圖中所有極大團的方法已較為成熟，推薦使用文獻[14]的算法，對于許多具有上萬頂點數(shù)的無向圖，一般可在幾十秒內生成所有的極大團。

2.3.3 連掛約束

模型引入出發(fā)列車的編組連掛決策，以較為合理地估計各車組在其對應出發(fā)列車的整個編組連掛過程中的走行距離，進而度量各車組的編組連掛成本。根據(jù)定義，各出發(fā)列車d只有在實際發(fā)生第k次連掛后才可能發(fā)生第k+1次連掛，該約束可表示為

(12)

在同樣的要求下，對于任意出發(fā)列車d，只有在其有車組c′∈Cd于第k次連掛時被牽出，才可能有其另外車組c∈Cd于第k+1次連掛時牽出，即

(13)

此外，對于有特定編組順序要求的出發(fā)列車d∈D2，在編組時，還需按指定的車組排列順序依次連掛調車場里該出發(fā)列車吸收的車組。例如，出發(fā)列車d∈D2有兩車組c和c′∈Cd，假設oc≤oc′，則要求在編組d時，車組c需不晚于車組c′被連掛牽出。該約束為

?d∈D2,c,c′∈Cd|oc≤oc′

(14)

通過式(10)或式(11)，可使得任意出發(fā)列車d∈D2中具有CoBS沖突的車組溜往不同調車線上集結，再由式(14)，可對這些車組按要求的排列順序連掛，從而確保通過簡單的溜放和連掛作業(yè)便可將各出發(fā)列車d∈D2按指定的編組順序編成。

2.3.4 能力約束

各調車線r∈R具有有限的有效長lr可供車組集結占用，考慮到可能有車組溜放不到位進而在調車線上產生空隙，引入有效長可利用率θr，規(guī)定任意時刻在該線路上占用的車組總長不能大于其可利用有效長θrlr。由定義，各車組c∈C在其對應到達列車的解體起時ec開始占用其調車線，在其歸屬出發(fā)列車的編組終時vc釋放占用其調車線，即車組c對調車場的占用時段為[ec,vc]。顯然，各調車線r∈R上集結的車輛只會在各車組c∈C的占用開始時刻ec和結束時刻vc發(fā)生變化，可在各車組c∈C的占用開始和結束時刻引入調車線能力約束。

令T為車組對調車場占用開始和結束時刻的集合，索引為t∈T；δct為0-1變量，若車組c在時刻t占用調車場，取1，否則取0。文獻[10-12]提出了以下約束

(15)

式(15)容易理解和實施，但未利用1個有用的特征。任意時刻t∈T同時占用調車場的車組集合(記為Ct)可能與另一個時刻t′∈T的Ct′相同，即Ct=Ct′，甚至Ct?Ct′，基于式(15)可能產生許多冗余且不緊湊的約束，影響模型性能。

現(xiàn)利用區(qū)間圖的極大團對既有的調車線能力約束進行改進。不難看出，車組對調車場的占用時段可誘導出1個區(qū)間圖G3=(C,I3)，其中，頂點集C為所有車組，對任意兩車組c和c′∈C，若其對調車場的占用時段相交，即[ec,vc]∩[ec′,vc′]≠?，則在G3中用1條無向邊連接對應頂點c和c′。定義CMC3為G3中所有極大團的集合，由圖論可得，G3中各極大團Cmc3∈CMC3是不相同的，且可代表其所包含所有時刻同時占用調車場的最大車組集合。基于CMC3，調車線能力約束可通過要求任意極大團Cmc3∈CMC3在任意調車線r∈R上集結的車輛總長不能超過該調車線的可利用有效長來滿足，即

(16)

相比于式(15)，式(16)可有效避免冗余約束。事實上，對各調車線r∈R，只需對滿足∑c∈Cmc3sc>θrlr的極大團Cmc3∈CMC3建立約束，進而可對式(16)作進一步簡化。此外，區(qū)間圖的極大團生成是易解問題，既有文獻存在多項式精確算法[15]可直接使用。

2.4 整體模型及線性化

綜上，可將技術站調車線運用問題構建為0-1非線性規(guī)劃模型OCTA

式(1)

s.t. 式(2)～式(7),式(9),式(11),式(12)～式(14),式(16)

xcr∈{0,1} ?c∈C,r∈R

(17)

yckr∈{0,1} ?c∈C,k∈K,r∈R

(18)

zdkr∈{0,1} ?d∈D,k∈K,r∈R

(19)

上述模型中，式(7)含1個非線性項xcr·zdkr，為兩個0-1變量相乘，容易線性化。采用以下3個線性表達式直接替代式(7)

yckr≤xcr?d∈D,c∈Cd,k∈K,r∈R

(20)

yckr≤zdkr?d∈D,c∈Cd,k∈K,r∈R

(21)

xcr+zdkr-1≤yckr?d∈D,c∈Cd,k∈K,r∈R

(22)

目標函數(shù)(1)中還有1個非線性項yckr·zbck′r′，也是兩個0-1變量相乘。為此，引入新的0-1變量λcbckk′rr′=yckr·zbck′r′，在目標函數(shù)(1)中以λcbckk′rr′替代yckr·zbck′r′，并采用下式維持3個變量的正確關系

λcbckk′rr′≤yckr

?c∈C,k,k′∈K,k′≥k,r,r′∈R

(23)

λcbckk′rr′≤zbck′r′

?c∈C,k,k′∈K,k′≥k,r,r′∈R

(24)

yckr+zbck′r′-1≤λcbckk′rr′

?c∈C,k,k′∈K,k′≥k,r,r′∈R

(25)

由此，模型OCTA可轉化為0-1線性規(guī)劃模型LCTA

(26)

s.t. 式(2)～式(6)、式(9)、式(11)、式(12)～式(14)、式(16)、式(17)～式(25)

λcbckk′rr′∈{0,1}

?c∈C,k,k′∈K,k′≥k,r,r′∈R

(27)

模型(LCTA)是0-1線性規(guī)劃，既有研究提出了許多高效求解算法，并已集成到主流商業(yè)優(yōu)化軟件(例如CPLEX、GUROBI)中。同時，我國典型編組站的統(tǒng)計數(shù)據(jù)顯示，1個調車場一般設置不超過40條線路，1個階段(3～4 h)集結車組數(shù)一般小于100組，出發(fā)列車平均連掛次數(shù)一般不超過3次，模型(LCTA)的規(guī)模是可控的。因此，使用商業(yè)優(yōu)化軟件直接求解模型(LCTA)，直到獲得最優(yōu)解或者其他預設終止條件達到為止。

3 算例分析

本節(jié)以文獻[10]中的數(shù)據(jù)為基礎構造算例，驗證所提出方法的有效性。采用Matlab 9.0編程所提出方法，并調用CPLEX 12.8求解模型(LCTA)。計算環(huán)境是CPU為Inter(R) Core(TM) i7-7700 3.60 GHz，RAM為16 GB的個人計算機。

3.1 算例設置

測試技術站的調車場設置10條調車線(R1～R10)，用于集結7個去向(1～7)的車輛，調車線信息見表2。

表2 調車線信息

考慮測試車站2個階段(09:00—15:00)的調車線靈活運用問題。已知到達列車共13列，編號為A0～A12，其中，A0為虛擬到達列車，用于表示階段初調車場現(xiàn)在車。到達列車解體方案見表3，為便于計算，設置A0的解體起時為階段開始時刻。出發(fā)列車共18列，編號為D1～D18，其中，D13～D18為虛設出發(fā)列車，用于分別表示階段末去向2～7在調車場的殘存車。出發(fā)列車編組方案見表3，設置D13～D18的編組起時為階段結束時刻。

表3 列車解編方案

已知車流推算方案見表4，其中，出發(fā)列車D5、D6和D12需按照給定的可編去向順序編組。

表4 車流推算方案

根據(jù)表3和表4，可將到達列車劃分為67個車組，車組信息見表5。

算例其他參數(shù)設置如下。首先，對于單位解體溜放成本α1和單位編組連掛成本α2，由于缺乏相應成本標準，采用調機每車公里油耗費用對這兩個參數(shù)進行設置。對于α2，鑒于編組連掛全過程需要調機提供動力，產生油耗成本，故令α2=10-7E油耗P柴油Q車≈ 0.004 元/ (車·m)，其中，調機每萬噸公里油耗E油耗取為 50 kg/萬t·km，柴油單價P柴油取為10元/kg，單車質量Q車取為 80 t/車。對于α1，與編組連掛相比，解體溜放過程不需要調機參與，不直接產生調機油耗費用，但是車組在解體溜放全過程中具有的動能是由調機將其推峰積累的勢能來提供的，即解體溜放間接產生調機油耗費用，結合這一特點，令α1=0.5α2。其次，令各調車線r的有效長的可利用率θr為1。需指出的是，在實際應用中，可根據(jù)考慮技術站的實際情況對α1、α2和θr進行賦值。此外，已知階段初現(xiàn)在車組C1、C2、C3、C4和C5分別位于調車線R2、R8、R9、R2和R3上，設出發(fā)列車最大允許連掛次數(shù)|K|為3。

3.2 計算結果

3.2.1 約束建模技術對比

在模型LCTA的建立過程中，使用圖的極大團技術對既有溜放約束式(8)、式(10)和能力約束式(15)進行了改進，以期減小模型規(guī)模，提高求解效率。為檢驗改進效果，設置3個替代模型ACTA1～ ACTA3與模型LCTA進行對比分析，其中，ACTA1使用溜放約束式(8)、式(10)和能力約束式(15)建立模型，ACTA2使用溜放約束式(9)、式(11)和能力約束式(15)，ACTA3使用溜放約束式(8)、式(10)和能力約束式(16)。

模型對比結果見表6。由表6可見，使用極大團技術改進各約束后，約束數(shù)量均有不同程度的減小，較為顯著地縮減了模型規(guī)模。對于溜放約束式(8)，使用式(9)使約束數(shù)量減少81.9%，各約束中平均決策變量數(shù)從2增加至6；對于溜放約束式(10)、式(11)使約束數(shù)量減少86.1%，去除了冗余約束；對于能力約束式(15)、式(16)使約束數(shù)量減少26.7%，且將約束中的最小決策變量數(shù)由5提高到16。求解效率方面，僅改進溜放約束，求解時間從54.4 s減少至46.1 s；僅改進能力約束，求解時間減少至36.5 s；同時改進兩類約束，求解時間減少至36.1 s，縮短率達33.6%，改進效果較明顯。綜上，采用極大團技術建模溜放約束和能力約束，均有助于縮減模型規(guī)模，提高求解速度，且使用該技術對能力約束進行改進的效果更為顯著。

表5 車組信息

表6 模型對比

3.2.2 結果分析

測試算例的最優(yōu)調車線運用方案見圖3，圖中，峰尾在右端，縱軸表示調車線，橫軸表示車組，橫軸從右往左表示車組對調車線的占用順序，更靠近峰尾的車組先占用調車線。方便理解，以調車線R5為例，從圖3中可見，歸屬于出發(fā)列車D5的車組C8、C24和C29以及歸屬于出發(fā)列車D12的車組 C32、C40、C56、C62依次占用調車線R5。

最優(yōu)出發(fā)列車編組調車計劃見表7，表中，第3列為編組調車計劃，由若干連掛鉤組成，編組調機根據(jù)該計劃指定的順序依次將關聯(lián)調車線上的車輛連掛牽出，即可將出發(fā)列車按規(guī)定的順序編成。例如，為編組有順序要求的出發(fā)列車D5，需首先在調車線R5上連掛去向5的40輛車(來自于車組C8、C24和C29)，然后在調車線R7上連掛去向6的24輛車(來自于車組C10、C25和C33)，總連掛鉤數(shù)2鉤。

由圖3、表7可知，各車組盡可能按固定方案且以最小調車成本使用調車線。例如，對于出發(fā)列車D11，只可編入去向1的車輛，其吸收的車組C37、C50、C59和C63全部分配在其固用調車線R1上；對于出發(fā)列車D2，可同時編入去向1和2的車輛，去向1的車組C18分配至其固用調車線R1，去向2的車組C5、C19和C21則分配至其固用調車線R3。同時，受調車線能力的限制，部分車組不能在其固用調車線上集結。例如，出發(fā)列車D12可編入去向5和6的車輛，去向5的車組C32、C40、C56和C62被分配在固用線路R5上，但去向 6的車組C60和C65則被分配到了調車線R7，盡管未能滿足固定使用方案，但盡可能靠近了其固用線路R6，可方便后續(xù)編組連掛作業(yè)。

統(tǒng)計結果見表8，其中：gap為目標值與最好可知下界的相對間隔；tcost為實際總解編調車成本；rcost為實際總解體溜放成本；rdis為車輛平均溜放距離；pcost為實際總編組連掛成本；pdis為車輛平均連掛距離；frate為按固定方案使用調車線的車輛占比；fint為車輛實際占用調車線與其固用線路的平均最小間距。

圖3 調車線運用方案

表7 編組調車計劃

表8 統(tǒng)計結果

從表8來看，在采用的單位調車成本下，總解編調車成本為4 942.7元，其中，總解體溜放成本為2 379.9元，占比48.1%，總編組連掛成本為2 562.8元，占比51.9%，表明編組連掛調車作業(yè)對總解編調車成本的影響更大。注意，在不同技術站，調車成本的度量可能有所不同，此結論不具有一般性。其次，按固定方案使用調車線的車輛占比達85.5%，車輛實際占用調車線與其固用線路的平均最小間距為1.0 m，達到預期效果，即車輛盡可能占用其固用線路，若不能滿足，也盡可能靠近其固用線路，以方便調車工作。求解效率方面，耗時36.1 s將算例求解到最優(yōu)(即gap為0)，能夠滿足實時決策的要求?？梢姡Ｐ蚅CTA具有高質量的求解效果和高效的求解速度，可用于輔助現(xiàn)場技術站調車線靈活運用的決策。

3.2.3 最大連掛次數(shù)的影響

出發(fā)列車最大允許連掛次數(shù)|K|是模型LCTA的輸入?yún)?shù)，其取值影響模型的規(guī)模和求解性能，本節(jié)采用靈敏度分析方法討論參數(shù)|K|的影響?？紤]|K|的4種取值，分別為2、3、4和5，在每種取值下，保持其他參數(shù)不變，分別以180 s限制時間和求到最優(yōu)為終止條件，求解模型LCTA，結果見表9。

表9 最大連掛次數(shù)的影響

根據(jù)表9可得，隨著|K|的增大，模型LCTA的規(guī)模呈近似二次多項式增長，使得模型的求解難度逐步加大，且在180 s內模型的求解質量呈變差趨勢。具體地，當|K|等于2和3時，分別耗時72.0 s和36.1 s便可收斂，與最好目標值(即8 181.6)相比，獲得目標值分別增加43.6%和0.0%，注意，|K|取3時，已找到最好解。但當|K|等于4和5時，在180 s內均不能收斂，獲得目標值分別增加15.8%和874.7%，事實上，|K|等于4和5時，需分別耗時近8.5 min和2.5 h才能收斂，且找到的是與|K|取3時相同的最好解?？梢?，參數(shù)|K|同時影響模型的求解質量和時間，在實際應用時，需結合對解質量和實時決策的需要，采用例如本節(jié)提出的靈敏度分析等方法合理設置|K|的取值。

3.2.4 調車線占用權重的影響

車組對調車線的占用權重wcr也是模型LCTA的輸入?yún)?shù)，本節(jié)在2.2節(jié)取值規(guī)則的基礎上，提出3個新的規(guī)則，以此討論wcr的影響。與現(xiàn)規(guī)則相比，規(guī)則1加強按固定方案使用調車線的要求，增大(車組對非固用調車線的占用權重)wcr，對各車組c，若調車線r?Fc，令wcr=2 min{grr′,r′∈Fc}；規(guī)則2弱化調車線固定使用的要求，減小wcr，對各車組c，若調車線r?Fc，令wcr=2 min{grr′,r′∈Fc}/5；規(guī)則3忽略調車線的固定使用方案，規(guī)定各車組c占用各調車線的權重wcr均為1。在各規(guī)則下，保持其余參數(shù)不變，終止條件分別取為180 s限制時間和求到最優(yōu)，求解模型LCTA，結果見表10。

表10 調車線占用權重的影響

從表10可發(fā)現(xiàn)，隨著wcr的減小，調車線運用方案的總解編調車成本tcost呈減小趨勢，但按固定方案使用調車線的車輛占比frate也呈下降趨勢，使得該方案可能缺乏規(guī)律性，與固定使用方案的要求存在較大出入，不利于實際實施。具體來講，對于tcost，相比于規(guī)則1，wcr按現(xiàn)規(guī)則取值時，最優(yōu)的tcost無變化；按規(guī)則2取值時，最優(yōu)的tcost減小3.8%；按規(guī)則3取值時，盡管未找到最優(yōu)解，但在180 s內獲得的tcost仍減小4.8%。對于frate，相比于規(guī)則1，現(xiàn)規(guī)則下最優(yōu)解的frate無變化，規(guī)則2下最優(yōu)解的frate的增加量為0.02%，規(guī)則 3下最好解的frate的減小量達73.2%。此外，伴隨wcr的減小，模型LCTA的求解難度逐漸增大，當wcr按規(guī)則1和現(xiàn)規(guī)則取值時，均能在180 s內求解到相同的最優(yōu)解；但當按規(guī)則2和3取值時，只能在180 s內找到gap分別為7.7%和21.1%的可行解，此時為尋找最優(yōu)解，規(guī)則2下需耗時486.7 s，規(guī)則3下將遇到內存越界，無最優(yōu)解返回。主要原因是車組對不同調車線的wcr越接近，將使得模型LCTA中解的對稱性增強，進而增大模型的求解難度?？梢姡瑆cr的取值同時影響模型的求解效果和性能，小的wcr有利于減小總解編調車成本，但不利于維持調車線運用的規(guī)律性，還會增大模型LCTA的求解難度。為盡量滿足現(xiàn)場的調車線固定使用要求，應給wcr取較大的值，以在求解效果和效率上取得好的折中。

4 結論

本文提出了鐵路技術站在作業(yè)計劃編制階段的調車線靈活運用的優(yōu)化方法。在對調車線運用問題進行分析的基礎上，以總加權解編調車成本最小為目標，考慮車組溜放和連掛、出發(fā)列車編組順序和調車線能力等要求，構建0-1線性規(guī)劃模型，并使用基于圖的極大團技術對其中的溜放約束和能力約束的既有建模方法進行改進，以減小模型規(guī)模，加快求解速度。算例結果表明，所提出方法可在合理時間內獲得總加權解編成本低且容易被現(xiàn)場接受的調車線運用方案，能夠為技術站靈活運用調車線提供決策支持。

本文側重于研究調車線靈活運用的線性優(yōu)化模型，該模型的規(guī)模隨調車線與車組的數(shù)量以及最大連掛次數(shù)呈多項式增長，可能給求解帶來挑戰(zhàn)，針對大規(guī)模問題，研究有效的調車線靈活運用算法，是下一步將開展的工作。其次，本文對車組的溜放和連掛走行距離做了近似估計，接下來可研究這兩個參數(shù)更加準確的度量策略，以進一步提高所提出的調車線運用模型的理論與實際價值。接著，在現(xiàn)場，調車線運用方案的可行性可能受解編調車進路安排的影響，未來可研究調車線運用與調車進路安排綜合優(yōu)化問題，提高調車線運用方案的兌現(xiàn)率。此外，在編制技術站作業(yè)計劃時，調車線運用與車流推算和列車解編排序相互影響，探討三者集成優(yōu)化，解決作業(yè)計劃整體編制問題，也是將來值得研究的方向。