基于狀態(tài)轉(zhuǎn)移的編組站列車調(diào)度優(yōu)化模型

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

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

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

4、小,即車輛在編組站的平均停留時間最短為目標(biāo)函數(shù)進行優(yōu)化,得到編組站列車調(diào)度的優(yōu)化模型,模型的解反映了編組站各子系統(tǒng)的狀態(tài),可以更好地對調(diào)度作業(yè)進行實時控制。2模型符號約定定義符號和參數(shù)如下: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為列車不換向直接轉(zhuǎn)發(fā)的時間;T z為列車換向轉(zhuǎn)發(fā)的時間;T h為車輛駝峰區(qū)解體到編組場集結(jié)的時間;T f為車輛從編組場到出發(fā)場的時間;b為021變量,表示車輛的類型,1表示重車,0表示空車。定義邏輯變量如下:J ij(k為021變量,如果列車i的第27卷第7期(總第187期系統(tǒng)工程V ol.27,N o.7 2009年7月Syste m s Engineering July.,2009收稿日期:2009205220基金項目:國家自然科學(xué)基金資助項目(60172012;國防科學(xué)技術(shù)大學(xué)優(yōu)秀研究生創(chuàng)新資助項目(

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

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

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

9、統(tǒng)狀態(tài)圖根據(jù)提出的狀態(tài)轉(zhuǎn)移關(guān)系模型生成約束條件,以中時最小為優(yōu)化的目標(biāo)函數(shù),建立了編組站列車調(diào)度的優(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)守恒關(guān)系。(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ū)的車輛轉(zhuǎn)移成為k +1階段編組場同類型的車輛;式(5表示k 階段解體的車輛到達第d 條軌道上,形成新列車的遞推關(guān)系;式(6和式(7分別表示k 階段新列車長度和重量限制關(guān)系。(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ā)場的列車對應(yīng)第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 階段轉(zhuǎn)發(fā)場和編組場需要換向的列車。16第7期張林,廖天俊等:基于狀態(tài)轉(zhuǎn)移的編組站列車調(diào)度優(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表示一個階段內(nèi)只能有一列車

13、進行編組;式(13表示一列車只能編組一次。3.2目標(biāo)函數(shù)m in G =Ti Nqi(14式(14表示優(yōu)化的目標(biāo)是一個班次的列車中時即平均中轉(zhuǎn)停留時間最小。其中T 是一個周期從開始到結(jié)束時車輛在編組站停留的總時間,可由式(15計算得到。系統(tǒng)從第k 階段變化到第k +1階段,車站系統(tǒng)各個場地的狀態(tài)轉(zhuǎn)化需要一定的時間,包括k 階段的四項時間變化增量:車輛在到達場停留的時間;駝峰區(qū)列車解體成車輛到達編組場的時間;編組場新列車駛向同向出發(fā)場的時間;編組場新列車駛向換向出發(fā)場的時間。車輛停留總時間的遞推關(guān)系式為: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編組調(diào)度優(yōu)化模型綜上所述,得到基于狀態(tài)轉(zhuǎn)移的雙向編組站列車調(diào)度優(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數(shù)據(jù)和求解結(jié)果以鄭州北站為例,采用雙向縱列式三級六場機械化駝峰編組站站型,利用上述模型確定列車調(diào)度的編組計劃。模型參數(shù)為: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。模型的求解結(jié)果是計劃期間的中時為147分鐘,經(jīng)過編組后新列車的出發(fā)信息見表3。26系統(tǒng)工程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編組計劃期間到達列車信息車次編號到達時刻方向車輛數(shù)列車編組內(nèi)容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ā)時刻方向車輛數(shù)編組內(nèi)容車次編號出發(fā)時刻方向車輛數(shù)編組內(nèi)容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靈敏度分析提高“瓶頸”硬件設(shè)施能力能提高編組能力,考慮2個因素:到達場到駝峰區(qū)的牽引軌道條數(shù);編組場到出發(fā)場的牽引時間。保持其它條件不變,分別改變這2個因素,形成對照“實驗”,進行靈敏度分析,駝峰區(qū)軌道數(shù)量因素的影響見表4,牽引時間因素的影響見表5。表4駝峰區(qū)軌道數(shù)量對中時的影響駝峰區(qū)軌道數(shù)(條牽引時間(分鐘中時(分鐘 15393251474510636第7期張林,廖天俊等:基于狀態(tài)轉(zhuǎn)移的編組站列車調(diào)度優(yōu)化模型從表中可以看出,在其他因素不變的時,當(dāng)駝峰區(qū)軌道減少到1條,中時增加到393分鐘,當(dāng)駝峰區(qū)軌道增加到4條

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

23、型的解反應(yīng)了編組站各子系統(tǒng)的狀態(tài),有利用對編組作業(yè)的實時控制,對編組站具有重要的實用價值。我們下一步研究工作將考慮滿軸發(fā)車等兼顧多個目標(biāo)建立多目標(biāo)規(guī)劃模型,解決更加復(fù)雜的編組調(diào)度優(yōu)化問題。參考文獻:1李致中等.鐵道運輸管理的數(shù)學(xué)模型及算法M.武漢:華中理工大學(xué)出版社,1995.2林柏梁,朱松年.優(yōu)化編組計劃的非線性021規(guī)劃模型及模擬退火算法J.鐵道學(xué)報,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李映紅,吳世貴,彭其淵.貨物列車編組計劃網(wǎng)絡(luò)模型的建立及算法J.西南交通

25、大學(xué)學(xué)報,2002,37(1:6871.7查偉雄,秦作睿.路網(wǎng)上列車編組計劃的有利去向模型及其網(wǎng)絡(luò)流算法J.鐵道學(xué)報,1998,20(2:12 19.8許紅等.技術(shù)站單組列車編組方案模型與計算方法的研究J.鐵道學(xué)報,2006,28(3:1217.9梁棟,林柏梁.技術(shù)站分組列車編組計劃的優(yōu)化理論及模型研究J.鐵道學(xué)報,2006,28(3:15. 10?；菝?雙向編組站列車調(diào)度調(diào)整的優(yōu)化模型及算法J.中國鐵道科學(xué),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