黎浩東，宋 瑞，呼志剛

北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044)

調(diào)車作業(yè)是鐵路編組站作業(yè)組織中重要而又復(fù)雜的內(nèi)容。它是在階段計(jì)劃的指導(dǎo)和約束下，考慮編組線數(shù)量與能力、調(diào)車作業(yè)端、作業(yè)時(shí)間要求、相關(guān)作業(yè)環(huán)節(jié)的銜接配合以及合理選編目標(biāo)的確定等，完成車站作業(yè)計(jì)劃，確保列車及時(shí)的接發(fā)。作為編組站調(diào)車作業(yè)的核心內(nèi)容之一，優(yōu)化編組場(chǎng)分類線(編組線)的運(yùn)用，是完成調(diào)車作業(yè)的關(guān)鍵。對(duì)于大部分編組站，車流組號(hào)的數(shù)量多于分類線數(shù)量，且車流存在一定的波動(dòng)性，這就存在如何合理運(yùn)用有限數(shù)量和存車能力的分類線，完成車流的集結(jié)，減少車流重復(fù)解體，以及出發(fā)列車連掛次數(shù)等問題。目前對(duì)編組線運(yùn)用的研究很少，國(guó)內(nèi)大部分關(guān)于編組站作業(yè)優(yōu)化的研究集中在車站作業(yè)計(jì)劃的編制[1]，如配流優(yōu)化[2-4]、到發(fā)線運(yùn)用[5,6]和調(diào)機(jī)運(yùn)用優(yōu)化[7,8]；調(diào)車作業(yè)計(jì)劃方面，集中在摘掛列車鉤計(jì)劃的編制方法的研究，如看圖調(diào)車法[9]、統(tǒng)籌對(duì)口調(diào)車法[10]、消逆法[11]以及計(jì)算機(jī)輔助編制方法[12,13]等；對(duì)于分類線的運(yùn)用，主要集中在分類線固定運(yùn)用方案的設(shè)計(jì)[14-15]。文獻(xiàn)[16]還對(duì)調(diào)車場(chǎng)線群的運(yùn)用進(jìn)行研究。國(guó)外將該問題分類為single-stage sorting[17-19]和multi-stage sorting[20,21]，并分別進(jìn)行了詳盡的研究。

編組站階段車流組織的研究，都沒有考慮編組場(chǎng)分類線能力的運(yùn)用，如大部分階段計(jì)劃優(yōu)化模型都是按去向集結(jié)和接續(xù)車流。而已有的調(diào)車作業(yè)計(jì)劃編制的研究，也都沒有針對(duì)分類線的運(yùn)用進(jìn)行闡述。我國(guó)的鐵路編組站，特別是路網(wǎng)性編組站中，作業(yè)的重點(diǎn)是中轉(zhuǎn)選編調(diào)車。車流量大和車站設(shè)施設(shè)備能力緊張的矛盾十分突出，在調(diào)車作業(yè)計(jì)劃的編制過程中則體現(xiàn)在編組場(chǎng)分類線能力的緊缺。而在分類線能力緊張的條件下，基于已有方法編制的階段計(jì)劃可能無法執(zhí)行。因此，有必要在階段計(jì)劃的指導(dǎo)和約束下，優(yōu)化分類線的運(yùn)用，這不僅可以在一定程度上緩解分類線能力的緊張局面，也有利于階段計(jì)劃和調(diào)車作業(yè)計(jì)劃之間的信息反饋和調(diào)整。本文基于此思想，對(duì)鐵路編組站分類線運(yùn)用優(yōu)化進(jìn)行研究，首先分析分類線運(yùn)用的類型，考慮其數(shù)量和能力等約束，構(gòu)建分類線運(yùn)用優(yōu)化的基本模型，最后設(shè)計(jì)算例對(duì)所構(gòu)建的模型進(jìn)行驗(yàn)證。

1 編組站分類線運(yùn)用分析

根據(jù)分類線存車情況的不同，可將其分為三類：一是空股道，即該股道上沒有停放任何車輛；二是單車流股道，即停放在該股道的車組的去向，或者歸屬的出發(fā)列車相同；三是混合車流股道，即該股道上同時(shí)停放了多個(gè)不同去向、或歸屬不同出發(fā)列車的車組。這種股道可細(xì)分為兩種，一是不同車組的停放順序和其對(duì)應(yīng)出發(fā)列車的編組順序相同，即需先編組的車組停放在股道靠近峰尾的一端(這里稱為前端)，所有車組可依次進(jìn)行編組作業(yè)；二是停放在其上的車組停放順序與其對(duì)應(yīng)出發(fā)列車的編組順序不同，此時(shí)部分車組如需編組則必須先處理在其前端的車組，一般都需要進(jìn)行再次解體作業(yè)。為區(qū)分這兩種類型，將第一種混合車流股道稱為暫存線，第二種稱為整理線。

對(duì)于空股道，可以直接用來集結(jié)車流，如沒有特殊規(guī)定或要求，可以用來集結(jié)任意去向的車輛；對(duì)于單車流股道，在能力允許的條件下，相同去向和不同去向的車組都可解體至該股道(相同去向的車組優(yōu)先)。如果到達(dá)的車組去向相同，該股道仍是單車流股道；而若到達(dá)的車組去向不同，則變成混合車流股道。對(duì)于第一種混合車流股道(暫存線)，它會(huì)增加調(diào)車作業(yè)難度，且可能存在安全隱患，但這種運(yùn)用方式在一定程度上有利于分類線能力的充分利用，運(yùn)能緊張情況下可酌情考慮，但股道上暫存車輛的去向的總數(shù)量有限。受能力限制，部分小股車流集中暫存在某一分類線上，以免這部分車流長(zhǎng)時(shí)間(等待后續(xù)車流直到滿足出發(fā)列車的滿軸約束)單獨(dú)占用有限的分類線，此時(shí)，便形成了整理線。整理線會(huì)增加車站的作業(yè)難度和強(qiáng)度，導(dǎo)致作業(yè)能力的浪費(fèi)，應(yīng)盡量避免。然而受車流結(jié)構(gòu)、車流量以及編組站布局等因素的影響，絕大部分編組站內(nèi)都不能避免整理線的出現(xiàn)。單車流股道在列車編組作業(yè)之后，整理線在再次解體作業(yè)之后都會(huì)變成空股道，而暫存線在完成一次列車編組作業(yè)之后，可能是單車流股道或者仍然是暫存線。編組站分類線運(yùn)用優(yōu)化目標(biāo)就是考慮分類線存車能力和出發(fā)列車的車組情況，將分類線分配給不同去向的車組，即不同的出發(fā)列車，并最小化混合車流股道的數(shù)量。為簡(jiǎn)化問題，本文假設(shè)階段內(nèi)配流方案、列車解編方案已定。

2 編組站分類線運(yùn)用優(yōu)化模型

假定階段內(nèi)有n列到達(dá)列車和m列出發(fā)列車。在列車解編方案已給定的條件下，可以根據(jù)解編順序?qū)Φ桨l(fā)列車進(jìn)行排序，此時(shí)有到達(dá)列車i+1在列車之后解體，出發(fā)列車j+1 在列車j之后編組。對(duì)于階段末未能出發(fā)的車組，則相同去向的車組整體視為同一出發(fā)列車，這些出發(fā)列車的編組開始時(shí)刻設(shè)定為階段末時(shí)刻。對(duì)于編組場(chǎng)的車流狀況，只有在到達(dá)列車解體后，或者出發(fā)列車編組后才發(fā)生變化。因此，可以根據(jù)到達(dá)列車解編開始時(shí)刻和結(jié)束時(shí)刻，出發(fā)列車的編組開始時(shí)刻和結(jié)束時(shí)刻，來檢查和更新不同分類線上的車流情況。設(shè)定T(t∈T)為時(shí)間節(jié)點(diǎn)集合，它包括所有到達(dá)列車的解體開始時(shí)刻和結(jié)束時(shí)刻、出發(fā)列車的編組開始時(shí)刻和結(jié)束時(shí)刻，并按照升序進(jìn)行排列。相鄰的兩個(gè)時(shí)間節(jié)點(diǎn)間的時(shí)間段定義為時(shí)段，則該階段內(nèi)最多有2m+n-1 個(gè)時(shí)段。

圖1 到達(dá)車組排序

基于上述分析和參變量定義，構(gòu)建編組站分類線運(yùn)用方案優(yōu)化模型如下

( 1 )

s.t.

( 2 )

( 3 )

?w,u≤u′

( 4 )

( 5 )

( 6 )

( 7 )

( 8 )

所構(gòu)建的模型為0-1整數(shù)規(guī)劃模型。作為編組站分類線運(yùn)用優(yōu)化的初步研究，本模型進(jìn)行了很多簡(jiǎn)化，如假定配流方案、列車解編方案已給定；沒有考慮整理線上車輛的再次解體作業(yè)，因此也沒考慮車組在編組場(chǎng)內(nèi)轉(zhuǎn)線作業(yè)，而只是在目標(biāo)中最小化這種作業(yè)的數(shù)量。本模型的一個(gè)重要特點(diǎn)，是通過設(shè)置不同時(shí)段內(nèi)車組與分類線的對(duì)應(yīng)關(guān)系，消除了決策變量中的時(shí)間維度，能有效減小問題的求解難度。與此同時(shí)，考慮到階段內(nèi)解編列車的數(shù)量和車組數(shù)有限，問題的規(guī)模大小在可接受的范圍內(nèi)，可采用ILOG、Lingo等優(yōu)化軟件進(jìn)行求解。

3 算例分析

算例基于如下數(shù)據(jù)：列車解編方案見表1，分別有12列到達(dá)列車和出發(fā)列車；表2為到達(dá)列車的車組信息，包括車組編號(hào)、車輛數(shù)和長(zhǎng)度(算例中按車輛數(shù)計(jì)算)，其中A0表示階段初的站存車；表3為車流接續(xù)方案，其中B1(3,4)表示出發(fā)列車B1包含去向3和4對(duì)車組；編組一欄表示“到達(dá)列車編號(hào)/車組編號(hào)/車輛數(shù)”。階段內(nèi)不能出發(fā)的車組，根據(jù)去向設(shè)為不同的出發(fā)列車，如表3中的列車B13～B17。

表1 列車解編方案

表2 到解列車的車組信息

表3 車流接續(xù)方案

假定有10條分類線，其存車能力分別為(45, 50, 60, 70, 75, 70, 70, 55, 50, 45)，單位為車輛輛數(shù)，τ的值設(shè)為5。階段初站存的三個(gè)車組分別停放在股道4、股道1和股道6上。采用IBM ILOG CPLEX 12.2進(jìn)行求解，得到編組場(chǎng)分類線運(yùn)用方案如圖2所示。

圖2 編組場(chǎng)分類線運(yùn)用方案(10股道情形)

目標(biāo)函數(shù)為20，其中整理線數(shù)量為0，連掛次數(shù)增加3次?；谏鲜鲕嚵鲾?shù)據(jù)，對(duì)不同情景下(不同數(shù)量、長(zhǎng)度)的分類線運(yùn)用方案進(jìn)行測(cè)算，可知：

(2)分類線的數(shù)量及其能力，直接決定了其運(yùn)用方案的制定。為方便測(cè)算分析和對(duì)比，對(duì)不同數(shù)量、能力的分類線情形進(jìn)行了測(cè)試，這個(gè)過程只需改變相應(yīng)的股道數(shù)量參數(shù)W和能力參數(shù)cw即可。當(dāng)分類線數(shù)量為9時(shí)(去掉原案例中的股道1)，目標(biāo)函數(shù)值為21，增加的出發(fā)列車連掛次數(shù)增加1次；當(dāng)分類線數(shù)量為8時(shí)(去掉原案例中的股道1和股道10)，目標(biāo)函數(shù)值為23，此時(shí)增加的出發(fā)列車連掛次數(shù)為6，都沒有出現(xiàn)整理線；當(dāng)分類線數(shù)量少于7時(shí)，則很難在可接受的時(shí)間范圍內(nèi)獲得可行解。主要原因在于出發(fā)列車B14、B15(本階段未能出發(fā)的車輛)需要在整個(gè)階段時(shí)間內(nèi)占用一條股道，造成分類線能力緊張，這說明在編組場(chǎng)能力約束下，階段配流方案不一定可行。保持分類線數(shù)量為7，增加其長(zhǎng)度至70時(shí)，股道2成為整理線，具體方案如圖3所示。

圖3 編組場(chǎng)分類線運(yùn)用方案(7股道情形)

(3)根據(jù)階段配流方案，車組5(來自到達(dá)列車A2)、車組12(來自到達(dá)列車A1)在本階段不能出發(fā)，因此整個(gè)階段都分別占用一條分類線(如圖2所示)，這嚴(yán)重影響分類線的運(yùn)用。如能在編制配流方案時(shí)，優(yōu)先考慮這類車組，則可能通過優(yōu)先分配并編組該車組，提升編組場(chǎng)分類線的利用效率。這需要階段計(jì)劃和分類線運(yùn)用計(jì)劃的綜合優(yōu)化，這也是本研究的最終目標(biāo)，實(shí)現(xiàn)階段計(jì)劃和鉤計(jì)劃的一體化編制。

圖4 編組場(chǎng)分區(qū)運(yùn)用時(shí)分類線運(yùn)用方案

4 結(jié)論

受車流結(jié)構(gòu)和場(chǎng)站布局等因素的影響，我國(guó)大部分編組站的分類線能力都很緊張。優(yōu)化分類線的運(yùn)用，不僅有助于更加充分地運(yùn)用有限的作業(yè)能力，提高編組站作業(yè)效率，而且能提高階段計(jì)劃的兌現(xiàn)率。本文在分析編組站分類線運(yùn)用類型的基礎(chǔ)上，構(gòu)建了分類線運(yùn)用的基本模型，并設(shè)計(jì)算例對(duì)其進(jìn)行了驗(yàn)證?；陔A段計(jì)劃，模型將列車解編作業(yè)開始、結(jié)束時(shí)刻作為時(shí)間節(jié)點(diǎn)，設(shè)置不同時(shí)段內(nèi)車組和分類線的對(duì)應(yīng)關(guān)系，消除了決策變量中的時(shí)間維度，能夠降低問題的求解難度。所設(shè)計(jì)的算例驗(yàn)證了模型的有效性。但是作為分類線運(yùn)用的初步研究，所構(gòu)建模型對(duì)于出發(fā)列車的車組順序、車流在編組場(chǎng)內(nèi)的作業(yè)(如回峰解體)等復(fù)雜情形都沒有考慮，而這些正是編組站調(diào)車作業(yè)計(jì)劃編制的難點(diǎn)所在。接下來，將針對(duì)這些更復(fù)雜情形下的分類線運(yùn)用優(yōu)化進(jìn)行深入研究。

參考文獻(xiàn)：

[1]黎浩東，何世偉，申永生，等. 鐵路編組站階段計(jì)劃編制研究綜述[J]. 鐵道學(xué)報(bào)，2011，33(8)：13-22.

LI Hao-dong, HE Shi-wei, SHEN Yong-sheng， et al. Survey of Stage Plan for Railway Marshaling Station[J]. Journal of the China Railway Society, 2011, 33(8):13-22.

[2]彭其淵，趙軍，韓雪松. 技術(shù)站廣義配流問題模型與算法[J]. 中國(guó)鐵道科學(xué)，2010，31(2):108-114.

PENG Qi-yuan, ZHAO Jun, HAN Xue-song. Model and Algorithm for the Generalized Wagon-Flow Allocation Problem of Railway Technical Station[J]. China Railway Science, 2010, 31(2):108-114.

[3]申永生，何世偉，王保華，等. 免疫算法求解編組站階段計(jì)劃配流問題研究[J]. 鐵道學(xué)報(bào)，2009，31(4):1-6.

SHEN Yong-sheng, HE Shi-wei, WANG Bao-hua, et al. Study on Allocation of Wagon-flow in Phase Plan by Using Immune Algorithm[J]. Journal of the China Railway Society, 2009, 31(4):1-6.

[4]黎浩東，何世偉，景云，等. 考慮不同滿軸條件的編組站階段計(jì)劃配流優(yōu)化研究[J]. 鐵道學(xué)報(bào)，2012，34(7)：10-17.

LI Hao-dong, HE Shi-wei, JING Yun, et al. Wagon-flow Allocation of Stage Plan for Marshaling Station by Considering Different Size Limitation of Departure Trains[J]. Journal of the China Railway Society, 2012, 34(7):10-17.

[5]李文權(quán)，王煒，程世輝. 鐵路編組站到發(fā)線運(yùn)用的排序模型和算法[J]. 系統(tǒng)工程理論與實(shí)踐， 2000，20(6):75-78.

LI Wen-quan, WANG Wei, CHENG Shi-hui. Scheduling Model and Algorithm of Using up and down Lines on Railway Marshaling Station[J]. Systems Engineering-Theory & Practice, 2000, 20(6):75-78.

[6]呂紅霞，倪少權(quán)，紀(jì)洪業(yè). 技術(shù)站調(diào)度決策支持系統(tǒng)的研究-到發(fā)線的合理使用[J]. 西南交通大學(xué)學(xué)報(bào)， 2000， 35(3):255-258.

LU Hong-xia, NI Shao-quan, JI Hong-ye. The Study on DSS of the Technical Station-Rationally Utilizing Reception and Departure Siding [J]. Journal of Southwest Jiaotong University, 2000, 35(3): 255-258.

[7]李文權(quán)，王煒，杜文，等. 鐵路技術(shù)站調(diào)機(jī)運(yùn)用模型及算法[J]. 系統(tǒng)工程學(xué)報(bào)，2000，15(1):38-43.

LI Wen-quan, WANG Wei, DU Wen, et al. The Model and Algorithm of Using Shunting Engines for Railroad Technical Service Station[J]. Journal of System Engineering, 2000,15(1):38-43.

[8]王世東，鄭力，張智海，等. 蟻群算法在調(diào)機(jī)運(yùn)用計(jì)劃中的應(yīng)用[J]. 中國(guó)鐵道科學(xué)，2007，28(3):104-109.

WANG Shi-dong, ZHENG Li, ZHANG Zhi-hai, et al. Solving the Scheduling Problem of Hump Locomotive with Ant Colony Optimization[J]. China Railway Science, 2007, 28(3): 104-109.

[9]劉德周.看圖調(diào)車法[M]. 北京, 中國(guó)鐵道出版社, 1979.

[10]胡安洲. 統(tǒng)籌對(duì)口調(diào)車法及其原理[M]. 北京：中國(guó)鐵道出版社, 1979: 59-83.

[11]高四維，張殿業(yè). 一種新的調(diào)車作業(yè)原理“消逆法”[J].鐵道學(xué)報(bào)，2003，22(8)：1-7.

GAO Si-wei, ZHANG Dian-ye. Elimination of Inverse-order, A New Model of Shunting Operation[J]. Journal of the China Railway Society, 2003, 22(8):1-7.

[12]趙源, 王巍巍, 孫焰. 調(diào)車鉤計(jì)劃編制方法研究與算法設(shè)計(jì)[J].鐵道運(yùn)輸經(jīng)濟(jì), 2004, 26(9): 64-67.

ZHAO Yuan, WANG Wei-wei, SUN Yan. Research on the Producing Method of Shunting Trip Plan and the Design of Algorithm[J]. Railway Transport and Economy, 2004, 26(9):64-67.

[13]劉彥虎. 鐵路調(diào)車作業(yè)計(jì)劃編制模型與算法研究[D]. 北京：北京交通大學(xué)，2007：32-47.

[14]孫玉明，李紅璇. 編制編組站調(diào)車場(chǎng)線路固定使用方案的探討[J]. 鐵道運(yùn)輸與經(jīng)濟(jì)，2003, 25(12): 20-21,59.

SUN Yu-ming, LI Hong-xuan. Analysis on the Fixed Usage of Classification Tracks of Hump Yard[J]. Railway Transport and Economy, 2003, 25(12): 20-21,59.

[15]陳伯羽. 鐵路編組場(chǎng)線路固定使用方案優(yōu)選方法研究[J]. 鐵道科學(xué)與工程學(xué)報(bào), 2006, 3(6): 80-82.

CHEN Bo-yu. Studying of Optimization of Fixed Usage Plan for Railway Marshaling Yard Tracks[J]. Journal of Railway Science and Engineering, 2006, 3(6): 80-82.

[16]薛峰，左大杰，羅建. 編組站調(diào)車場(chǎng)線群的調(diào)整運(yùn)用模型[J]. 鐵道運(yùn)輸與經(jīng)濟(jì), 2011, 33(11): 75-79.

XUE Feng, ZUO Da-jie, LUO Jian. Adjustment and Application Method of Shunting Yard Track Group in Marshaling Station[J]. Railway Transport and Economy, 2011, 33(11): 75-79.

[17]DAHLHAUS E, HORAK P, MILLER M, et al. The Train Marshaling Problem[J]. Discrete Applied Mathematics, 2000, 103(1):41-54.

[18]Di Stefano, G., Koci, M.L. A Graph Theoretical Approach to the Shunting Problem[J]. Electronic Notes in Theoretical Computer Science, 2004, 92(17):16-33.

[19] KRAFT E R. A Hum PSequence Algorithm for Real Time Management of Train Connection Reliability[J]. Journal of the Transportation Research Forum, 2000, 39(4): 95-115.

[20]HANSMANN R S, ZIMMERMANN U T. Optimal Sorting of Rolling Stock at Hump Yards[M]. //Krebs H J, J?ger W. Mathematics-Key Technology for the Future. Springer, Berlin/Heidelberg, 2008: 189-203.

[21]JACOB R, MARTON P, MAUE J, et al. Multistage Methods for Freight Train Classification[J]. Networks, 2011, 57(1): 87-105.