趙金觀，朱志國(guó)

(西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031)

?

基于解體順序的編組站到解作業(yè)計(jì)劃自動(dòng)化編制研究

趙金觀，朱志國(guó)

(西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031)

摘要:以階段內(nèi)正點(diǎn)出發(fā)列車數(shù)最多為目標(biāo)，構(gòu)建考慮列車解體順序和配流問題的廣義動(dòng)態(tài)配流問題模型;設(shè)計(jì)按照先到先服務(wù)的原則和貪婪思想為每一列車分配車流的啟發(fā)式算法，并確定到解列車的解體順序。在解體順序的基礎(chǔ)上，運(yùn)用已編制好的編組站到解作業(yè)計(jì)劃自動(dòng)化編制系統(tǒng)確定到解列車到發(fā)線和調(diào)機(jī)運(yùn)用。研究結(jié)果表明：構(gòu)建的模型和編制的系統(tǒng)較好地實(shí)現(xiàn)編組站到解作業(yè)計(jì)劃的自動(dòng)編制，能為編組站實(shí)際工作中作業(yè)安排提供決策支持。

關(guān)鍵詞：編組站；階段計(jì)劃；廣義動(dòng)態(tài)配流；啟發(fā)式算法；到解作業(yè)

階段計(jì)劃是編組站調(diào)度計(jì)劃的核心部分，它既是實(shí)現(xiàn)日班計(jì)劃的分階段部署，又是編制調(diào)車作業(yè)計(jì)劃的主要依據(jù)，包括配流、調(diào)車機(jī)車運(yùn)用和到發(fā)線運(yùn)用3個(gè)子計(jì)劃。到解列車解體順序是確定占用到發(fā)線時(shí)間和調(diào)機(jī)運(yùn)用的關(guān)鍵因素，王世軍等[1-5]分別針對(duì)到發(fā)線和調(diào)機(jī)運(yùn)用進(jìn)行了研究，趙金觀等[6]對(duì)到發(fā)線和調(diào)機(jī)運(yùn)用進(jìn)行了協(xié)同研究，并考慮咽喉區(qū)行調(diào)車進(jìn)路約束，建立到發(fā)線和調(diào)機(jī)運(yùn)用模型,但沒有給出解體順序的確定方法；到解列車解體順序與配流計(jì)劃密切相關(guān)，王慈光等[7]構(gòu)建了動(dòng)態(tài)配流的樹狀模型，提出相應(yīng)的回溯算法搜索有利方案，解決了解體方案的選擇問題，但回溯算法在復(fù)雜情況下的搜索時(shí)間較長(zhǎng)，影響算法的實(shí)用性，王正彬等[8-9]基于列車解編順序?qū)﹄A段計(jì)劃配流進(jìn)行研究，并分別采用混合遺傳算法和和聲搜索算法進(jìn)行求解，王明慧等[10]設(shè)計(jì)了啟發(fā)式算法求解，彭其淵等[11]構(gòu)建了考慮列車解體順序與配流的廣義動(dòng)態(tài)配流模型，設(shè)計(jì)了啟發(fā)式算法對(duì)模型進(jìn)行求解，但給出的算例結(jié)果有待商榷。本文在文獻(xiàn)[6]的基礎(chǔ)上，通過構(gòu)建考慮解體順序和配流計(jì)劃的廣義動(dòng)態(tài)配流模型確定到解列車的解體順序，同時(shí)運(yùn)用已編制好的編組站到解作業(yè)計(jì)劃自動(dòng)化編制系統(tǒng)確定到解列車到發(fā)線和調(diào)機(jī)運(yùn)用，并通過算例驗(yàn)證了算法和系統(tǒng)的實(shí)用性，為全面實(shí)現(xiàn)編組站階段計(jì)劃自動(dòng)編制打下基礎(chǔ)。

1模型構(gòu)造和求解

1.1　模型說明

本文以縱列式編組站、解體配置2臺(tái)調(diào)機(jī)進(jìn)行作業(yè)、駝峰采用雙推單溜的形式為例進(jìn)行研究。

1.2　配流模型

1.2.1模型構(gòu)造

Ts和Te分別為本階段開始和結(jié)束時(shí)刻,這里以調(diào)機(jī)開始作業(yè)時(shí)刻為階段開始時(shí)刻。

以該階段正點(diǎn)出發(fā)列車數(shù)最大化為目標(biāo)，可以等價(jià)于被正點(diǎn)出發(fā)列車吸收的車組最多，目標(biāo)函數(shù)為：

列車解體順序安排中，第p+1時(shí)段列車解體開始時(shí)刻必須在第p時(shí)段列車解體結(jié)束之后；第p時(shí)段列車解體開始時(shí)刻必須在該時(shí)段解體列車的最早可能解體時(shí)刻之后；且同一時(shí)段只能解體1列列車，同一列車只在1個(gè)時(shí)段解體，滿足約束如下：

(1)

(2)

(3)

(4)

到達(dá)列車中的車組最多被一列出發(fā)列車吸收：

(5)

被出發(fā)列車吸收的車組必須滿足編組計(jì)劃的要求：

xi,k,j≤fj,bvi,k,b,

?i∈ND,k∈K(i),b∈B,j∈NF

(6)

被出發(fā)列車吸收的車組應(yīng)滿足車流接續(xù)時(shí)間的要求：

xi,k,j≤σi,j,?i∈ND,k∈K(i),j∈NF

(7)

(8)

出發(fā)列車應(yīng)滿足換算長(zhǎng)度的要求

(9)

變量約束條件如下：

σi,j∈{0,1},?i∈ND, j∈NF

(10)

1.2.2算法求解

上述模型在不考慮列車解體順序的約束(1)~(4)下其已屬于NP-C[1]，而單純的解體順序排序共有m種情況，整個(gè)問題復(fù)雜性進(jìn)一步提升，對(duì)于該問題的求解，很難找到好的精確算法。本文為了便于編程實(shí)現(xiàn)，假設(shè)同一編組去向的車組換長(zhǎng)都相同，且以列車滿足換長(zhǎng)的要求作為列車開行標(biāo)準(zhǔn)，設(shè)計(jì)針對(duì)上述模型的啟發(fā)式算法，設(shè)計(jì)思路為：以配流為主線按照先到先服務(wù)的原則為每1列出發(fā)列車分配車流，直到該列出發(fā)列車最大程度地滿足換長(zhǎng)的要求或因接續(xù)車流不足而停運(yùn)，最后統(tǒng)計(jì)出發(fā)列車數(shù)，并確定到解列車的解體順序。算法每次只考慮1列出發(fā)列車，屬于基于貪婪思想的啟發(fā)式算法。在文獻(xiàn)[4]的算法基礎(chǔ)上加以改進(jìn)，具體步驟為如下。

步驟2：引入0-1變量φj和δi，當(dāng)出發(fā)列車j已滿軸或停運(yùn)時(shí)，取值為1，否則為0，當(dāng)?shù)竭_(dá)列車i已解體時(shí)，δi取值為1，否則為0。引入變量si，代表到達(dá)列車i的解體結(jié)束時(shí)間，其中s0=Ts。令當(dāng)前出發(fā)列車集為J=NF和φj=0，?j∈J，到達(dá)列車集I=ND，δ0=1和δi=0,i=2,…,n，并轉(zhuǎn)入下一步。

步驟3：若J≠φ，轉(zhuǎn)入下一步，否則轉(zhuǎn)步驟10。

步驟6：若φj*=0，轉(zhuǎn)下一步，否則，J=J{j*}，轉(zhuǎn)步驟3。

若Ck≥Cj*，按下面2步進(jìn)行分析。

2)判斷需要解體的列數(shù)，在滿足解體距離[7]條件下能配流成功，則，φj*=1，對(duì)相關(guān)列決策變量進(jìn)行賦值，并更新δi，si，否則j*停運(yùn)，令φj*=1，xi,b,j*=0,?i∈I,b∈B′,k∈K(i)，轉(zhuǎn)步驟6。

步驟10:統(tǒng)計(jì)出發(fā)列車數(shù)，并確定到解列車的解體順序。算法結(jié)束。

2算例

以某縱列式編組站，駝峰采用雙推單溜作業(yè)為例，對(duì)某車站作業(yè)進(jìn)行安排。該編組站下行到達(dá)場(chǎng)咽喉區(qū)的示意圖如圖1所示，該到達(dá)場(chǎng)銜接了2個(gè)方向，有12條股道，其中，1道為正線，只用于接發(fā)通過列車，咽喉區(qū)共分為了10個(gè)道岔組；2臺(tái)調(diào)機(jī)負(fù)責(zé)解體，1調(diào)負(fù)責(zé)2，3，4，5，6，7道列車解體，2調(diào)負(fù)責(zé)6，7，8，9，10，11，12道列車解體。列車解體作業(yè)時(shí)間標(biāo)準(zhǔn)為20 min，編組作業(yè)時(shí)間標(biāo)準(zhǔn)中遠(yuǎn)程直達(dá)、直通、區(qū)段列車均為25 min、摘掛、小運(yùn)轉(zhuǎn)列車為30 min; 列車到達(dá)和出發(fā)技術(shù)作業(yè)時(shí)間標(biāo)準(zhǔn)均為25 min；按照換長(zhǎng)要求列車編組為35輛，摘掛列車允許欠軸開行；階段初調(diào)車場(chǎng)沒有現(xiàn)在車。

圖1　某編組站下行到達(dá)場(chǎng)咽喉區(qū)示意圖Fig.1 Layout of turnouts in the throat of arrival yard in a marshalling station

到達(dá)和出發(fā)列車信息數(shù)據(jù)分別見表1和表2。

系統(tǒng)生成的配流方案和到達(dá)列車解體順序見表3和表4。

表1　列達(dá)列車信息

表2　出發(fā)列車信息

表3　出發(fā)列車配流方案

注：編組內(nèi)容中，數(shù)字分別代表車輛來源、去向組號(hào)和輛數(shù)。

從生成結(jié)果可以看出，配流方案中除22212次出發(fā)列車因其接續(xù)車流不足而被停運(yùn)外，其他出發(fā)列車都符合編制要求開行。

表4　到達(dá)列車解體順序

設(shè)該編組站接車進(jìn)路占用咽喉時(shí)間為5 min，調(diào)車進(jìn)路占用咽喉時(shí)間為3 min，解體預(yù)推時(shí)間為5 min。根據(jù)表4中得解體順序，系統(tǒng)求得到發(fā)線運(yùn)用和調(diào)機(jī)運(yùn)用具體方案見圖2，對(duì)應(yīng)進(jìn)路咽喉道岔組占用情況見圖3。

圖2　到發(fā)線和調(diào)機(jī)運(yùn)用方案Fig.2 Using of up-and-down lines and locomotive

圖3　各進(jìn)路咽喉道岔組占用情況Fig.3 Occupation of throat turnouts by each route

到發(fā)線和調(diào)機(jī)使用方案比較均衡，各個(gè)道岔組間沒有交叉干擾，是可行的排列方案。

3結(jié)論

1)完善了階段計(jì)劃中配流計(jì)劃和解體順序的確定方法，設(shè)計(jì)的啟發(fā)式算法能較快得到可行解，并通過算例驗(yàn)證了模型和系統(tǒng)的可行性；

2)編組站到解作業(yè)計(jì)劃自動(dòng)編制是編組站階段計(jì)劃自動(dòng)編制的一部分，缺省了出發(fā)場(chǎng)股道安排和峰尾調(diào)機(jī)運(yùn)用方案，可以作為下一步完善方案，爭(zhēng)取全面實(shí)現(xiàn)編組站階段計(jì)劃自動(dòng)化編制，為編組站實(shí)際工作提供輔助決策。

參考文獻(xiàn)：

[1] 王世東，鄭力，張智海，等.編組站階段計(jì)劃自動(dòng)編制的數(shù)學(xué)模型及算法[J].中國(guó)鐵道科學(xué),2008,29(2):120-125.

WANG Shidong, ZHENG Li, ZHANG Zhihai,et al.Mathematical model and algorithm for automatically programming the stage plan of marshalling station[J].China Railway Science,2008,29(2):120-125.

[2] 張英貴，雷定猷,劉明翔.鐵路車站股道運(yùn)用排序模型與算法[J].中國(guó)鐵道科學(xué),2010,31(2):97-100.

ZHANG Yinggui, LEI Dingyou, LIU Mingxiang.Scheduling model and algorithm for track application in railway station [J].China Railway Science,2010,31(2):97-100.

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

LI Wenquan,WANG Wei,CHEN Gshihui.Scheduling modeland algorithm of using up-and down lineson railway mar shalling sation[J].Systems Engineering-Theory & Practice,2000,20(6):75-78.

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

WANG Shidong, ZHENG Li, ZHANG Zhihai,et al.Solving the scheduling problem of hump locomotive with ant colony optimization[J].China Railway Science,2007,28(3):104-109.

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

LI Wenquan,WANG Wei,DU Wen,et al.The model and algorithm of using shunting engines for railroad technical service station[J].Journal of Systems Engineering,2000,15(1):38-43.

[6] 趙金觀，朱志國(guó).編組站到解作業(yè)計(jì)劃自動(dòng)化編制研究[J].鐵道科學(xué)與工程學(xué)報(bào)，2015,12(4):71-75.

ZHAO Jinguan, ZHU Zhiguo.A study on the plan of using up-and-Down lines and locomotives in marshalling station[J].Journal of Railway Science and Engineering, 2015,12(4):71-75.

[7] 王慈光.編組站動(dòng)態(tài)配流模型與算法研究[J].鐵道學(xué)報(bào),2004,26(1) :1-6.

WANG Ciguang.Research on the model and algorithm of dynamic wagon-flow allocating in a marshalling station[J].Journal of the China Railway Society,2004,26(1):1-6.

[8] 王正彬，杜文，吳柏青，等.基于解編順序的階段計(jì)劃車流推算模型及算法[J].西南交通大學(xué)學(xué)報(bào)，2008，43(1) :91-95.

WANG Zhengbin, DU Wen, WU Baiqing, et al.Model and algorithm for estimation of wagon flow of stage operating plan based on break-up and make-up sequences[J].Journal of Southwest Jiaotong University,2008,43(1):91-95.

[9] 黎浩東,宋瑞,何世偉,等.基于列車解編作業(yè)時(shí)間估算的編組站階段計(jì)劃配流優(yōu)化[J].中南大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,45(1): 317-326.

LI Haodong, SONG Rui, HE Shiwei, et al.Wagonflow allocation of stage plan for marshaling station based on time estimation of breakup and makeup of trains[J].Journal of Central South University(Science and Technology), 2014,45(1):317-326.

[10] 王明慧, 趙強(qiáng).編組站智能調(diào)度系統(tǒng)階段計(jì)劃優(yōu)化模型及算法研究[J].鐵道學(xué)報(bào),2005,27(6):1-9.

WANG Minghui, ZHAO Qiang.Optimal model and algorithmof stage plan of intelligent dispatching system for marshalling stations[J].Journal of the China Railway Society, 2005, 27(6):1-9.

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

PENG Qiyuan,ZHAO Jun,HAN Xuesong.Model and algorithm for the generalized wagon-flow allocation problem of railway technical station[J].China Railway Science,2010, 31(2):108-114.

[12] Kroonl L G, Romeijn H E,Zwaneveld P J.Routing trains through railway stations: complexity issues[J].European Journal of Operational Reseach,1997,98(3):485-498.

[13] Zwaneveld P J, Dauzere PERES S, Hoesel C P M V, et al.Routing trains through railway stations: model figuretion and algorithms[J].Transportation Science,1996,30(3):181-194.

[14] Zwaneveld P J,Kroon L G, Hoesel C P M V.Routing trains through a railway station based on a node packing model[J].European Journal of Operational Research,2001(128):14-33.

[15] Crarey M, Crarville S.Scheduling and platforming trains at busy complex stations[J].Transportation Research, Part A, Policy and Practice,2003,37(A3):195-224.

(編輯陽麗霞)

Research on the utilizing of up-and-down lines and locomotives inmarshalling station based on the disassembling sequences

ZHAO Jinguan, ZHU Zhiguo

(School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 610031, China)

Abstract：Aiming at maximizing the number of punctual outbounding trains, the paper establishes the generalized dynamic wagon-flow allocation model considering the train disassembling sequence and wagon-flow allocation problems.The heuristic algorithm according to the principle of first come first service and greedy thought allocating wagon-flow for each train was designed, and the disassembling sequences of the disassembled trains was then determined.Finally, based on the disassembling sequences, the utilizing of up-and-down lines and locomotives are made with the application of automatic operation arrangement system for disassembled trains.The numerical experiments show that the models and system can well accomplish auto-scheduling of operation planning in a stage , and provide decision support for marshaling station in practical work assignments.

Key words：marshaling station; stage plan; generalized dynamic wagon-flow allocation; heuristic algorithm; disassembled trains

通訊作者：朱志國(guó)(1963-)，男，遼寧錦州人，副教授，從事軌道交通規(guī)劃與設(shè)計(jì)研究；E-mail:zhuzhiguo@home.swjtu.edu.cn

收稿日期：2015-06-15

中圖分類號(hào)：U291

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1672-7029(2015)06-1507-06