1、文章編號:100124098(20090720060205基于狀態(tài)轉移的編組站列車調度優(yōu)化模型張林1,廖天俊1,劉英2(1.國防科學技術大學信息系統與管理學院,湖南長沙410073;2.重慶通信學院數學教研室,重慶400035摘要:編組站是鐵路樞紐的核心,使車輛在編組站停留時間最短是解決編組站編組計劃問題的關鍵。針對雙向編組站列車調度問題,提出編組站系統狀態(tài)轉移關系模型,并由此生成約束條件,設計以中時最小為優(yōu)化的目標函數,建立了基于狀態(tài)轉移的列車調度優(yōu)化模型。以鄭州北站數據進行實證分析,驗證了模型的有效性和通用性。關鍵詞:系統優(yōu)化;編組站;編組計劃;狀態(tài)轉移;非線性規(guī)劃中圖分類號:N945;U

2、292文獻標識碼:A1引言編組站的主要任務是根據列車編組計劃要求,辦理各種貨物列車的解編作業(yè),按照列車運行圖規(guī)定的時刻正點接發(fā)列車。在鐵路運輸管理中,列車編組計劃起著對鐵路貨物車流的組織作用,對車站的設備和能力進行統籌規(guī)劃和綜合使用1。目前的研究主要使用遺傳算法、神經網絡和模擬退火方法等解決列車編組計劃問題2-6。文獻7基于給定路網環(huán)境參數參考服務系統選址的增量算法,建立變量規(guī)模數為n3-n的尋找有利編組去向的數學模型。文獻8考慮車站編組能力、解體能力等影響因素,以技術站車輛集結消耗、改編消耗整體最小以及改編能力均衡利用為目標函數,構建協同優(yōu)化的多目標021規(guī)劃模型。文獻9以是否開行分組列車所

3、產生的技術效益最大化為目標,在引入階躍函數的前提下,提出技術站分組列車編組計劃的021規(guī)劃模型。文獻10研究雙向編組站調度優(yōu)化問題,以列車編成輛數、編組內容和作業(yè)能力等為約束條件,以列車的走行距離和產生的交換車數為綜合優(yōu)化的目標,構造列車調度調整的非線性優(yōu)化模型。上述模型主要以費用、距離、能力等因素作為優(yōu)化的目標來解決編組調度問題,對時間因素的重視程度不夠,不能完全解決調度問題。據統計,列車一次全周轉時間中,在編組站作業(yè)和停留的時間約占70%,因此提高作業(yè)效率,縮短車輛的周轉時間對提高鐵路運輸能力具有重大意義。本文對編組站系統進行分析,提出了狀態(tài)轉移關系模型,根據此模型生成約束條件,并以中時最

4、小,即車輛在編組站的平均停留時間最短為目標函數進行優(yōu)化,得到編組站列車調度的優(yōu)化模型,模型的解反映了編組站各子系統的狀態(tài),可以更好地對調度作業(yè)進行實時控制。2模型符號約定定義符號和參數如下:k為階段,定義為一列車的解體過程;q i表示到達場列車i的長度;at i為到達場列車i 的到達時刻;K為時段的集合;N為到達編組站列車的集合;R為到達場到駝峰區(qū)的軌道集合;Q i為列車i分解成的車輛集合;D A為駝峰區(qū)到編組場軌道的集合;D C,D S 分別為換向和不換向的軌道集合,且D A=D CD S; L m in,L m ax為列車的最小長度和最大長度;W m in,W m ax為列車的最小重量和最

5、大重量;t k為k階段解體的開始時刻; T k是從初始到k階段車輛停留時間的總和;T w為列車不換向直接轉發(fā)的時間;T z為列車換向轉發(fā)的時間;T h為車輛駝峰區(qū)解體到編組場集結的時間;T f為車輛從編組場到出發(fā)場的時間;b為021變量,表示車輛的類型,1表示重車,0表示空車。定義邏輯變量如下:J ij(k為021變量,如果列車i的第27卷第7期(總第187期系統工程V ol.27,N o.7 2009年7月Syste m s Engineering July.,2009收稿日期:2009205220基金項目:國家自然科學基金資助項目(60172012;國防科學技術大學優(yōu)秀研究生創(chuàng)新資助項目(

6、S080501作者簡介:張林(19852,男,四川彭山人,國防科學技術大學信息系統與管理學院研究生,研究方向:信息資源管理,系統優(yōu)化;廖天俊(19852,男,重慶人,國防科學技術大學信息系統與管理學院博士研究生,研究方向:系統優(yōu)化與綜合集成;劉英(19562,女,重慶人,重慶通信學院數學教研室副教授,研究方向:數理統計,運籌學。第j 輛車在k 階段解體則取1,否則取0;W b ijd(k 為021變量,如果到達場列車i 的第j 輛車對應第d 個目的地則取1,否則取0;Hb jd r(k 為021變量,如果駝峰區(qū)軌道r 上第j 輛車對應第d 個目的地則取1,否則取0;F b jd(k ,SD b

7、 jd (k ,CD bjd (k 為021變量,分別表示如果編組場、同向出發(fā)場、換向出發(fā)場第j 輛車對應第d 個目的地則取1,否則取0。3數學模型本文以雙向列車編組站為研究對象, 編組站系統包括到達場、駝峰區(qū)、編組場、轉發(fā)場、出發(fā)場等子系統。到達場用于臨時停靠到達編組站的列車,駝峰區(qū)對列車進行解體得到的車輛,編組場根據車輛去向和目的地將車輛重新編組成新的列車,轉發(fā)場是將編組后的新列車駛向出發(fā)場等待出發(fā)。本文把上行線和下行線統一看待,根據編組列車的不同去向,將轉發(fā)場進一步細分為兩種:列車繼續(xù)保持行進方向的同向出發(fā)場;列車需要從上(下行方向轉換為下(上行方向的換向出發(fā)場。中時的定義是車輛在編組站

8、的平均停留時間,衡量了編組站的效率。對編組站系統進行抽象,引入狀態(tài)轉移的思想提出編組站狀態(tài)轉移關系模型。狀態(tài)轉移關系的過程描述如下:對于上行線和下行線的各方向經過編組站的每一列列車分別駛入到達場內?？?然后判斷列車是否需要解體,如果不需要解體則根據列車去向駛入同向出發(fā)場或換向出發(fā)場待發(fā),如果需要解體則根據每一輛車的去向通過駝峰解體,分別向各自的編組場不同軌道線集結,從而編組成一列新的發(fā)往某一個方向的列車,最后轉往上行線或下行線的出發(fā)場待發(fā)。狀態(tài)轉移關系模型考慮了編組站各系統的狀態(tài)以及各子系統的狀態(tài)轉移關系,是優(yōu)化模型的基礎。第k 階段時編組站系統的狀態(tài)和狀態(tài)轉移關系見圖1。圖1第k 階段車站系

9、統狀態(tài)圖根據提出的狀態(tài)轉移關系模型生成約束條件,以中時最小為優(yōu)化的目標函數,建立了編組站列車調度的優(yōu)化模型。3.1約束條件(1到達場的狀態(tài)j Q i d D A b 0,1Jij(k W bijd (k =q i ,i =1,n (1式(1表示將第k 階段到達場列車i 解體成去向和類型不同的車輛,是狀態(tài)守恒關系。(2駝峰區(qū)的狀態(tài)r RHbjd r (k =i N(1-i (k W bijd (k ,b 0,1,d D A ,j Q i(2L m in q i L m ax Wm inWlj Q i d D A b =0Jij(k Wb ijd (k +Whj Q i d D A b =1Jij

10、(k W bijd(k W m ax,i =1,n(3式(2表示k 階段駝峰區(qū)的車輛是由出發(fā)場部分列車分解的得來的。式(3用于判定列車是否需要解體,如果滿足則i (k 取1表示不需要解體,否則取0。其中,W l 是一輛空車的重量;Wh是一輛重車的重量。(3編組場的狀態(tài)F bjd (k +1=r R Hb jd r (k ,b 0,1,d D A ,j Q i(4j Q iFbjd (k +1=j Q iFbjd(k +j Q i r RHb jd r(k ,b 0,1,d D A ,j Q i(5L m in j Q i b 0,1Fbjd(k L m ax ,d D A(6Wm inWlj

11、Q i b =0Fbjd(k +Whj Q i b =1Fbjd (k W m ax,d D A (7式(4表示k 階段駝峰區(qū)的車輛轉移成為k +1階段編組場同類型的車輛;式(5表示k 階段解體的車輛到達第d 條軌道上,形成新列車的遞推關系;式(6和式(7分別表示k 階段新列車長度和重量限制關系。(4同向出發(fā)場的狀態(tài)d D SSDbjd (k +1=i N d D SWbijd (k i (k +d D SFbjd (k ,b 0,1,j Q i(8式(8表示第k +1階段同向出發(fā)場的列車對應第k 階段到達場和編組場不需換向的列車。(5換向出發(fā)場的狀態(tài)d D CCDbjd (k +1=i N

12、d D CWbijd (k i (k +d D CFbjd (k ,b 0,1,j Q i(9式(9表示第k +1階段換向出發(fā)場列車是第k 階段轉發(fā)場和編組場需要換向的列車。16第7期張林,廖天俊等:基于狀態(tài)轉移的編組站列車調度優(yōu)化模型(6接續(xù)時間與到達時刻的約束t k +1-t k T hi N j Q iJij(k (10t k i N j Q iat i Jij(k (11式(10表示列車的解體過程是連續(xù)的;式(11表示列車的到達時刻有先后的次序。(7邏輯約束i N j Q i Jij(k =1(12k K j Q iJij(k =1,i =1,n(13式(12表示一個階段內只能有一列車

13、進行編組;式(13表示一列車只能編組一次。3.2目標函數m in G =Ti Nqi(14式(14表示優(yōu)化的目標是一個班次的列車中時即平均中轉停留時間最小。其中T 是一個周期從開始到結束時車輛在編組站停留的總時間,可由式(15計算得到。系統從第k 階段變化到第k +1階段,車站系統各個場地的狀態(tài)轉化需要一定的時間,包括k 階段的四項時間變化增量:車輛在到達場停留的時間;駝峰區(qū)列車解體成車輛到達編組場的時間;編組場新列車駛向同向出發(fā)場的時間;編組場新列車駛向換向出發(fā)場的時間。車輛停留總時間的遞推關系式為:T k +1-T k=(t k +1-t k i N j Q i d D A b BJij(

14、k W b ijd (k +T h j Q i d D A r R b BHbjd r(k +T z i N j Q i d D S b BWbijd(k i (k +T z j Q i d D S b BF b jd (k +T w i N j Q i d D C b BWbijd (k i (k +T f j Q i d D C b BF b jd (k (153.3編組調度優(yōu)化模型綜上所述,得到基于狀態(tài)轉移的雙向編組站列車調度優(yōu)化模型為:m in G =Ti Nqis .t .j Q i d D A b 0,1Jij(k W b ijd (k =q i ,i =1,nr R Hbjd r

15、(k =i N(1-i (k W bijd (k ,b 0,1,d D A ,j Q iF bjd (k +1=r RHb jd r (k ,b 0,1,d D A ,j Q ij Q iFbjd (k +1=j Q i Fb jd (k +j Q i r RHbjd r (k ,b 0,1,d D A ,j Q iL m in j Q i b 0,1Fb jd(k L m ax ,d D A Wm inWlj Q i b =0Fbjd(k +Whj Q i b =1Fbjd (k Wm ax,d D Ad D SSD bjd (k +1=i N d D SWbijd (k i (k +d D

16、 SFbjd (k ,b 0,1,j Q id D CCDb jd(k +1=i N d D CWbijd (k i (k +d D CFbjd (k ,b 0,1,j Q it k +1-t k T hi N j Q i Jij(k t k i N j Q iat iJij(k i N j Q iJij(k =1k K j Q iJij(k =1,i =1,n其中,k K .4算例4.1數據和求解結果以鄭州北站為例,采用雙向縱列式三級六場機械化駝峰編組站站型,利用上述模型確定列車調度的編組計劃。模型參數為:N =100列,R =2條,D A =29條,D C =13條,D S =16條,L

17、m in =40輛,L m ax =70輛,Wm in=3000噸,Wm ax=4800噸,T w =15分,T z =20分,T h =10分,T f =5分,W h=80噸,W l =20噸。編組車流去向代碼和開始時編組站殘存的各去向的車流流量見表1;編組計劃期間6:0018:00到達列車的部分信息見表2。模型的求解結果是計劃期間的中時為147分鐘,經過編組后新列車的出發(fā)信息見表3。26系統工程2009年表1編組車流去向代碼和揩始時編組站殘存的各去向的車流流量銜接方向編組車流去向代碼 車流量(輛向東方向E1 19,E2 14,E3 14,E4以南 33,E4以北 9,E5以遠 13,E5以

18、近 5,E6 8,E7 9,E8 7向南方向S1 17,S2以遠 13,S3以西及以遠 14,S3與S4間 6,S4與S5間 14,S6 17向西方向W1 41,W2 41,W3 30,W4 22,W5 25,W6以遠 25,W6以近 31,W7 16向北方向N1 35,N2 35,N2與N3間 30,N3與N4間 32,N5 22表2編組計劃期間到達列車信息車次編號到達時刻方向車輛數列車編組內容S0016:20上行59W2 59S0036:35上行62W1 24,W2 1,W3 2,W4 7,W5 16,W6以遠 2,W6以近 3,W7 1,N2 2, N2與N3間 4S0056:52上行5

19、9E2 2,E3 1,E4以南 1,S2以遠 10,S3以西及以遠 1,W2 6,W3 24,W4 8, W5 1S0077:10上行54W1 3,W2 10,W4 7,W5 8,W6以遠 2,W6以近 12,W7 2,N2與N3間 10 S0097:40上行56W2 5,N1 22,N2 19,N2與N3間 2,N3與N4間 8X0026:05下行61W2 61X0046:15下行53E2 10,E4以南 43X0066:30下行57E2 3,E6 3,E7 8,S1 14,S3以西及以遠 1,W2 1,W4 3,W5 8,N1 1X0086:45下行50E1 4,E3 1,E4以南 15,

20、E4以北 10,S2以遠 7,N1 2,N2 2,N3與N4間 9, N5 1X0106:55下行44E1 7,E4以南 4,W1 1,W2 24,W3 4,W4 4表3編組出發(fā)列車信息車次編號出發(fā)時刻方向車輛數編組內容車次編號出發(fā)時刻方向車輛數編組內容X0018:31下行69W2 69X0038:46下行62E4以南 44,E4以北18S0028:57上行68W2 68X0059:18下行49S3以西及以遠 16,S3與S4間 33 S0049:33上行57S2 以遠 65X0079:39下行65W5 57X0099:50下行61N1 61S0069:58上行63N2 41,N2與N3間 2

21、0X001110:11下行59W1 59S00810:22上行67E2 674.2靈敏度分析提高“瓶頸”硬件設施能力能提高編組能力,考慮2個因素:到達場到駝峰區(qū)的牽引軌道條數;編組場到出發(fā)場的牽引時間。保持其它條件不變,分別改變這2個因素,形成對照“實驗”,進行靈敏度分析,駝峰區(qū)軌道數量因素的影響見表4,牽引時間因素的影響見表5。表4駝峰區(qū)軌道數量對中時的影響駝峰區(qū)軌道數(條牽引時間(分鐘中時(分鐘 15393251474510636第7期張林,廖天俊等:基于狀態(tài)轉移的編組站列車調度優(yōu)化模型從表中可以看出,在其他因素不變的時,當駝峰區(qū)軌道減少到1條,中時增加到393分鐘,當駝峰區(qū)軌道增加到4條

22、,中時減少到106分鐘。表5牽引時間對中時的影響駝峰區(qū)軌道數(條牽引時間(分鐘中時(分鐘2311325147210284從表中可以看出,在其他因素不變的時,當牽引時間縮短到3分鐘,中時減少到113分鐘,當牽引時間增加到10分鐘,中時增加到284分鐘。綜合來看,駝峰區(qū)軌道因素對中時影響最為明顯,在實際中應該努力提高相應的人員和設施的效率,盡量減少這個“瓶頸”的限制,考慮適當增加駝峰區(qū)軌道的數量。5結束語本文提出的基于狀態(tài)轉移的編組優(yōu)化模型,通過以中時最小為目標,減少列車的等待時間,從而解決了列車調度優(yōu)化問題,提高了鐵路系統效率。基于狀態(tài)轉移的建模思想具有通用性,適用于各種編組站站型。該調度優(yōu)化模

23、型的解反應了編組站各子系統的狀態(tài),有利用對編組作業(yè)的實時控制,對編組站具有重要的實用價值。我們下一步研究工作將考慮滿軸發(fā)車等兼顧多個目標建立多目標規(guī)劃模型,解決更加復雜的編組調度優(yōu)化問題。參考文獻:1李致中等.鐵道運輸管理的數學模型及算法M.武漢:華中理工大學出版社,1995.2林柏梁,朱松年.優(yōu)化編組計劃的非線性021規(guī)劃模型及模擬退火算法J.鐵道學報,1999,21(2:31 66.3A r m acost A.M odeling railroad ter m inal operati onssupporting realti m e network p lanning and contr

24、olD.Cam bridge,1995.4M artinelli D R,T eng H.Op ti m izati on of rail w ayoperati ons using neural network sJ.T rans portati onR esearch,1996,4(1:3349.5R avindra K A,K rishna C J,L iu J.Solving real2liferailroad bl ock ing p roble m sJ.Infor m s,2007,37(5:404419.6李映紅,吳世貴,彭其淵.貨物列車編組計劃網絡模型的建立及算法J.西南交通

25、大學學報,2002,37(1:6871.7查偉雄,秦作睿.路網上列車編組計劃的有利去向模型及其網絡流算法J.鐵道學報,1998,20(2:12 19.8許紅等.技術站單組列車編組方案模型與計算方法的研究J.鐵道學報,2006,28(3:1217.9梁棟,林柏梁.技術站分組列車編組計劃的優(yōu)化理論及模型研究J.鐵道學報,2006,28(3:15. 10牛惠民.雙向編組站列車調度調整的優(yōu)化模型及算法J.中國鐵道科學,2007,28(6:102107.An Opti m i za ti on M odel for Tra i n Schedul i n g of M arsha ll i n g St a ti onBa sed on the St a te Tran sfor ma ti onZHAN G L in1,L I A O T ian2jun1,L I U Ying2(1.School of Infor m ati on Syste m s and M anage m ent,N ati onalU niversity of D efense T echno