趙金觀，朱志國

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

?

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

趙金觀，朱志國

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

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

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

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

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

1.1　模型說明

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

1.2　配流模型

1.2.1模型構(gòu)造

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

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

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

(1)

(2)

(3)

(4)

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

(5)

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

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

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

(6)

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

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

(7)

(8)

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

(9)

變量約束條件如下：

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

(10)

1.2.2算法求解

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

步驟2：引入0-1變量φj和δi，當(dāng)出發(fā)列車j已滿軸或停運時，取值為1，否則為0，當(dāng)?shù)竭_列車i已解體時，δi取值為1，否則為0。引入變量si，代表到達列車i的解體結(jié)束時間，其中s0=Ts。令當(dāng)前出發(fā)列車集為J=NF和φj=0，?j∈J，到達列車集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步進行分析。

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

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

2算例

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

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

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

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

表1　列達列車信息

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

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

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

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

表4　到達列車解體順序

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

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

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

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

3結(jié)論

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

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

參考文獻：

[1] 王世東，鄭力，張智海，等.編組站階段計劃自動編制的數(shù)學(xué)模型及算法[J].中國鐵道科學(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] 張英貴，雷定猷,劉明翔.鐵路車站股道運用排序模型與算法[J].中國鐵道科學(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ā)線運用的排序模型和算法[J].系統(tǒng)工程理論與實踐,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)機運用計劃中的應(yīng)用[J].中國鐵道科學(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].系統(tǒng)工程學(xué)報,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] 趙金觀，朱志國.編組站到解作業(yè)計劃自動化編制研究[J].鐵道科學(xué)與工程學(xué)報，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] 王慈光.編組站動態(tài)配流模型與算法研究[J].鐵道學(xué)報,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].西南交通大學(xué)學(xué)報，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è)時間估算的編組站階段計劃配流優(yōu)化[J].中南大學(xué)學(xué)報(自然科學(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] 王明慧, 趙強.編組站智能調(diào)度系統(tǒng)階段計劃優(yōu)化模型及算法研究[J].鐵道學(xué)報,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].中國鐵道科學(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

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

收稿日期：2015-06-15

中圖分類號：U291

文獻標志碼：A

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