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

趙 軍，張思宇，彭其淵

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

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

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

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

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

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

1 問題描述與假設(shè)

1.1 問題描述

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

圖1 調(diào)車場示意圖

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

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

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

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

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

圖2 連掛走行距離的度量

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

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

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

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

1.2 問題假設(shè)

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

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

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

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

2 數(shù)學模型

2.1 符號定義

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

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

2.2 目標函數(shù)

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

(1)

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

2.3 約束條件

2.3.1 唯一性約束

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

(2)

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

(3)

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

(4)

(5)

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

(6)

此外，變量xcr、yckr和zdkr需滿足關(guān)系約束

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

(7)

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

2.3.2 溜放約束

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

(1)編組時段沖突

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

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

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

?c,c′∈C|c

(8)

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

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

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

(9)

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

(2)編組順序沖突

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

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

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

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

(10)

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

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

(11)

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

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

2.3.3 連掛約束

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

(12)

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

(13)

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

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

(14)

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

2.3.4 能力約束

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

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

(15)

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

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

(16)

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

2.4 整體模型及線性化

綜上，可將技術(shù)站調(diào)車線運用問題構(gòu)建為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個變量的正確關(guān)系

λ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可轉(zhuǎn)化為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個調(diào)車場一般設(shè)置不超過40條線路，1個階段(3～4 h)集結(jié)車組數(shù)一般小于100組，出發(fā)列車平均連掛次數(shù)一般不超過3次，模型(LCTA)的規(guī)模是可控的。因此，使用商業(yè)優(yōu)化軟件直接求解模型(LCTA)，直到獲得最優(yōu)解或者其他預(yù)設(shè)終止條件達到為止。

3 算例分析

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

3.1 算例設(shè)置

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

表2 調(diào)車線信息

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

表3 列車解編方案

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

表4 車流推算方案

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

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

3.2 計算結(jié)果

3.2.1 約束建模技術(shù)對比

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

模型對比結(jié)果見表6。由表6可見，使用極大團技術(shù)改進各約束后，約束數(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%，改進效果較明顯。綜上，采用極大團技術(shù)建模溜放約束和能力約束，均有助于縮減模型規(guī)模，提高求解速度，且使用該技術(shù)對能力約束進行改進的效果更為顯著。

表5 車組信息

表6 模型對比

3.2.2 結(jié)果分析

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

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

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

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

圖3 調(diào)車線運用方案

表7 編組調(diào)車計劃

表8 統(tǒng)計結(jié)果

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

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，結(jié)果見表9。

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

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

3.2.4 調(diào)車線占用權(quán)重的影響

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

表10 調(diào)車線占用權(quán)重的影響

從表10可發(fā)現(xiàn)，隨著wcr的減小，調(diào)車線運用方案的總解編調(diào)車成本tcost呈減小趨勢，但按固定方案使用調(diào)車線的車輛占比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內(nèi)獲得的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內(nèi)求解到相同的最優(yōu)解；但當按規(guī)則2和3取值時，只能在180 s內(nèi)找到gap分別為7.7%和21.1%的可行解，此時為尋找最優(yōu)解，規(guī)則2下需耗時486.7 s，規(guī)則3下將遇到內(nèi)存越界，無最優(yōu)解返回。主要原因是車組對不同調(diào)車線的wcr越接近，將使得模型LCTA中解的對稱性增強，進而增大模型的求解難度?？梢?，wcr的取值同時影響模型的求解效果和性能，小的wcr有利于減小總解編調(diào)車成本，但不利于維持調(diào)車線運用的規(guī)律性，還會增大模型LCTA的求解難度。為盡量滿足現(xiàn)場的調(diào)車線固定使用要求，應(yīng)給wcr取較大的值，以在求解效果和效率上取得好的折中。

4 結(jié)論

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

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