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

趙金觀，朱志國

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

?

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

趙金觀，朱志國

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

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

關鍵詞：編組站；階段計劃；廣義動態配流；啟發式算法；到解作業

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

1模型構造和求解

1.1　模型說明

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

1.2　配流模型

1.2.1模型構造

Ts和Te分別為本階段開始和結束時刻,這里以調機開始作業時刻為階段開始時刻。

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

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

(1)

(2)

(3)

(4)

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

(5)

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

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

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

(6)

被出發列車吸收的車組應滿足車流接續時間的要求：

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

(7)

(8)

出發列車應滿足換算長度的要求

(9)

變量約束條件如下：

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

(10)

1.2.2算法求解

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

步驟2：引入0-1變量φj和δi，當出發列車j已滿軸或停運時，取值為1，否則為0，當到達列車i已解體時，δi取值為1，否則為0。引入變量si，代表到達列車i的解體結束時間，其中s0=Ts。令當前出發列車集為J=NF和φj=0，?j∈J，到達列車集I=ND，δ0=1和δi=0,i=2,…,n，并轉入下一步。

步驟3：若J≠φ，轉入下一步，否則轉步驟10。

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

若Ck≥Cj*，按下面2步進行分析。

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

步驟10:統計出發列車數，并確定到解列車的解體順序。算法結束。

2算例

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

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

到達和出發列車信息數據分別見表1和表2。

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

表1　列達列車信息

表2　出發列車信息

表3　出發列車配流方案

注：編組內容中，數字分別代表車輛來源、去向組號和輛數。

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

表4　到達列車解體順序

設該編組站接車進路占用咽喉時間為5 min，調車進路占用咽喉時間為3 min，解體預推時間為5 min。根據表4中得解體順序，系統求得到發線運用和調機運用具體方案見圖2，對應進路咽喉道岔組占用情況見圖3。

圖2　到發線和調機運用方案Fig.2 Using of up-and-down lines and locomotive

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

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

3結論

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

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

參考文獻：

[1] 王世東，鄭力，張智海，等.編組站階段計劃自動編制的數學模型及算法[J].中國鐵道科學,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].中國鐵道科學,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] 李文權,王煒,程世輝.鐵路編組站到發線運用的排序模型和算法[J].系統工程理論與實踐,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] 王世東,鄭力,張智海,等.蟻群算法在調機運用計劃中的應用[J].中國鐵道科學,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] 李文權,王煒,杜文,等.鐵路技術站調機運用模型及算法[J].系統工程學報,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] 趙金觀，朱志國.編組站到解作業計劃自動化編制研究[J].鐵道科學與工程學報，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] 王慈光.編組站動態配流模型與算法研究[J].鐵道學報,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].西南交通大學學報，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] 黎浩東,宋瑞,何世偉,等.基于列車解編作業時間估算的編組站階段計劃配流優化[J].中南大學學報(自然科學版),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] 王明慧, 趙強.編組站智能調度系統階段計劃優化模型及算法研究[J].鐵道學報,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] 彭其淵，趙軍，韓雪松.技術站廣義配流問題模型與算法[J].中國鐵道科學，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-)，男，遼寧錦州人，副教授，從事軌道交通規劃與設計研究；E-mail:zhuzhiguo@home.swjtu.edu.cn

收稿日期：2015-06-15

中圖分類號：U291

文獻標志碼：A

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