基于TPr/T_系統的編組站配流研究

張正坤，朱昌鋒

蘭州交通大學 交通運輸學院，蘭州 730070

基于TPr/T_系統的編組站配流研究

張正坤，朱昌鋒

蘭州交通大學 交通運輸學院，蘭州 730070

通過考慮分析編組站作業(yè)流程，根據Petri網理論，將Pr/T_系統擴展為基于時延性的TPr/T_系統，在此基礎上，逐步建立編組站TPr/T_系統模型。在模型中，以列車（車列）為元組，解決配流對資源的約束；通過謂詞容量限制，解決配流在空間上的約束；通過變遷限制，解決配流對時間的約束。系統以滿軸、盡量不晚點為優(yōu)化目標，根據反向推理思想設計算法，以求得較為合理的配流方案。最后，通過實例，驗證提出理論的合理性。

編組站；配流；Petri網；TPr/T_系統

1 引言

配流的主要目的是確定出發(fā)列車的車流來源和編組內容，合理的配流方案對指導編組站作業(yè)、提高編組站運輸效率具有重要意義。為此，有相關學者對編組站配流問題開展了大量研究。

王慈光[1]首次提出靜態(tài)配流和動態(tài)配流概念；彭其淵等[2]認為廣義配流應包括列車解體方案、配流和列車編組方案。根據研究視角不同，趙軍等[3]將編組站配流問題轉化為指派問題；馬亮等[4]將配流問題等價為作業(yè)排程問題；黎浩東等[5]用整數規(guī)劃對配流問題進行了研究。根據研究內容不同，薛峰[6]、趙軍[7]、黎浩東[8]等分別從車流來源、調機運用及不確定性方面對配流展開了研究。上述文獻從不同角度對編組站配流進行了研究，對進一步研究該問題具有一定的參考價值。

但是，配流受車流、作業(yè)及時間等因素影響，既有文獻在研究過程中對車流所處狀態(tài)、技術作業(yè)的并行性及時間接續(xù)方面分析不足，而Pr/T_系統對解決這些缺陷具有一定優(yōu)勢?；诖耍疚耐ㄟ^分析配流的影響因素，利用Pr/T_系統理論建立編組站系統模型，并以滿軸、盡量不晚點為優(yōu)化目標，對編組站配流展開研究。

2 TPr/T_系統的基本理論

Pr/T_系統側重研究個體的狀態(tài)變化過程，是高級Petri網系統之一。由于該系統未引入時間參數，考慮到配流過程中，車流在時間上的接續(xù)關系，本文依據文獻[9]，將Pr/T_系統擴展為與時間有關的TPr/T_系統。

定義1 Σ=(P，T，F；D，V，AP，AT，AF，τF， )

M0構成TPr/T_系統的條件是：

（1）( )

P,T,F 為有向網，稱為Σ的基網。

（2）D為非空有限集，為Σ的個體集，也為系統的論域，D上有給定的運算符集Ω。

（3）V是D上的變量集。

（4）AP：P→π，其中π是D上的可變謂詞集。對于 p∈P，若 AP(p)為n元謂詞，就說 p為n元謂詞。

（5）AT：T→fD，其中 fD是D的公式集，對t∈T，AT(t)只含靜態(tài)謂詞和Ω中的運算符。

（6）AF：F→fS，其中 fS是D的符號和集。對n元謂詞 p∈P，若(p ,t)∈F或(t , p)∈F，則 AF(t , p)或AF(p ,t)為n元符號和。對于t∈T，公式AT(t)中的自由變量（即不受量詞?和?約束的變量）必須是以t為一端的有向弧上的自由變量。

（7）τF：T→R，R為非負實數集。對于t∈T，τF()t表示與變遷有關的時間參數。

（8）M0：P→fS，對n元謂詞 p∈P，M0(p)是n元符號和。

根據定義1，TPr/T_系統模型如圖1所示。

圖1 TPr/T_系統模型

圖1 中，＜＞及+組合在一起構成符號和；變遷t1中，x可替換a或b，分別記為(x ←a)和(x ←b)，稱其為t1的可行替換，該替換適合于其他變遷。

定義2D中的元素和D上的變量均稱為D的項（term），以 D的項為分量的 n元向量 ＜v1,v2,…,vn＞（n≥1）稱為D的n元組。

3 編組站TPr/T_系統模型建立

3.1 配流及作業(yè)分析

配流是編組站將到達列車中符合接續(xù)時間的車列解體，并按去向編入規(guī)定的出發(fā)列車中，這涉及到以下幾個主要研究內容。

就車流而言，車流是配流涉及的主體，貫穿于編組站整個作業(yè)過程，構成了配流的資源上約束。

就作業(yè)而言，技術作業(yè)是有關計劃的具體實施，車流狀態(tài)依賴作業(yè)變化，具有嚴格的流程性約束。

就時間而言，技術作業(yè)時間是確定車流搭配的重要因素之一，進而構成了配流問題在時間上的約束。

編組站主要作用是解體和編組貨物列車，列車在編組站的主要作業(yè)有到達技術作業(yè)、解體作業(yè)、編組作業(yè)及發(fā)車前的技術作業(yè)等。編組站作業(yè)組織如圖2所示。

圖2可以看出，在編組站的不同環(huán)節(jié)，車流所處的狀態(tài)有所不同，在整個過程中，車流狀態(tài)依賴作業(yè)而變化，這為利用TPr/T_系統研究編組站提供了依據。此外，由于配流得出的方案最終要通過具體作業(yè)而實現，因此，配流方案的不能脫離車站實際作業(yè)而盲目編制。

圖2 編組站作業(yè)組織

3.2 有關假設

編組站是一個復雜的車流加工系統，其設備、作業(yè)及車流比較復雜，為方便研究且不失一般性，本文作如下假設。

（1）站型假設，以單向縱列式編組站為背景，駝峰和峰尾各有一臺調機進行調車作業(yè)。

（2）車流假設，車流信息與列車確報一致，對禁溜車、超限車等特殊作業(yè)車不予考慮。

（3）時間假設，依據《技規(guī)》規(guī)定，編組站作業(yè)時間由《站細》規(guī)定給出，且無意外發(fā)生。

3.3 模型建立

編組站是由到解子系統和編發(fā)子系統組成的車流加工系統。到解子系統主要辦理有關接車、到達技術作業(yè)及推峰解體作業(yè)，基于假設，根據Petri網及TPr/T_系統有關理論，結合車流狀態(tài)變化過程，給出到解子系統的TPr/T_系統模型。到解子系統模型如圖3所示。

圖3 到解子系統模型

圖3 中，P={ p0,p1,…,p11}為庫所集合，表示車場或股道，則AP(p)表示車流所處狀態(tài)（謂詞），T={t0,t1,…,t8}為變遷集合，表示作業(yè)過程。到解子系統中符號表示含義見表1。

表1 到解子系統符號表示含義

編發(fā)子系統主要辦理有關編組、轉場及出發(fā)前的技術作業(yè)等，同樣地，給出到編發(fā)子系統的TPr/T_系統模型，該模型如圖4所示。結合圖4所示，編發(fā)子系統符號表示含義見表2。

圖4 編發(fā)子系統模型

表2 編發(fā)子系統符號表示含義

圖3、圖4分別表示了到解子系統模型和編發(fā)子系統模型。其中，AP(p0)和AP(p ′0)均表示列車在區(qū)間的運行狀態(tài)，AP(p4)和AP(p ′4)均為本務機處于整備的狀態(tài)，兩個系統中均含有AP(p7)，都表示車列處于集結狀態(tài)。鑒于到解子系統和編發(fā)子系統中有表示同一狀態(tài)的謂詞，因此，根據文獻[10]提出的Petri網共享合成理論將兩個子系統進行合并。

定義3設Petri網PNi=(Pi,Ti;Fi,M0i)(i =1,2)，令PN=(P ,T;F,M0)使得

（1）P=P1?P2，P1?P2≠?

（2）T=T1?T2，T1?T2=?

（3）F=F1?F2

則稱 PN是 PN1與 PN2的共享合成網，記作 PN=PN1OPPN2。

根據定義3，現將到解子系統和編發(fā)子系統合成為編組站的TPr/T_系統模型，合成的編組站TPr/T_系統模型如圖5所示。

（4）

圖5 編組站TPr/T_系統模型

圖5 中，AP(p0)表示到達或出發(fā)列車在區(qū)間的運行狀態(tài)，其余謂詞表示含義均不變，該模型詳細反映了車流在編組站的主要作業(yè)過程及其所處狀態(tài)。

3.4 系統模型說明

3.4.1 模型中車流的表示

編組站主要作用是解體和編組列車，車組（或車輛）及機車（本務機和調機）是作業(yè)中的最小單位，因此，本文將它們作為系統中D的項，記為vij。其中，v∈N表示車組中所含車輛的數量，i表示到達場的股道號，當i=0時表示列車在區(qū)間運行，j為《站細》中規(guī)定的車流組號，特別定義

定義元組Vi表示列車或車列，則列車可表示為Vi=＜00i,vij1,vij2,…,vijn＞，車列可表示為Vi=＜vij1,vij2,…,vijn＞其中，jl∈{1 ,2,…,j} ，l=1,2,…,n 。

定義4給定一個特殊運算符Φ，用以表示v與vij的對應關系，使得：

3.4.2 模型中謂詞容量的約束

根據謂詞中存放元組的數量來劃分，系統中的謂詞可分為A、B兩大類。其中，A={AP(p0)，AP(p3)，AP(p5)，AP(p8)}為單元謂詞，即謂詞中只允許存放一個元組。需要說明的是，對于編組站而言，列車是以單列的形式到達或出發(fā)，因此，本文將AP(p0)視為單元謂詞以方便研究。B={AP(p1)，AP(p2)，AP(p4)，AP(p6),AP(p7)，AP(p9)，AP(p10) }為多元謂詞，即可以存放多個元組，且有：

式（1）～（3）分別為到達場、編組場及出發(fā)場的空間容量約束，即股道數限制；式（4）中的 Ki為元組Vi=＜vij1,中個體項（車組）的個數，其數值依賴于解體車列，為動態(tài)值，圖5中，k=Ki。

以AP(p6)、AP(p7)為例，現給出車組在謂詞中的存放形式如下：

其中，i或il′為到達場的股道號，m≤FN為車流組號對應的編組場的股道號。

3.4.3 模型中變遷時間的約束

定義5[11]設M 為Pr/T_系統的一個標識，則變遷t∈T在M具有發(fā)生權的充分必要條件是：存在M下的可行替換 t(z1← d1，z2← d2，…，zl←dl) ，其中，{z1，z2，…，zl}為與t有關的符號和及公式中的自由變量。M和t的這種發(fā)生權記作：

定義5是基于Pr/T_系統定義的變遷發(fā)生權，在該定義的基礎上，依照本文所建立的編組站TPr/T_系統模型，根據變遷對時間要求的不同，也將變遷分為A、B兩大類。其中，A={AT(t1)，AT(t8) }中的變遷需符合到達計劃或發(fā)車計劃所規(guī)定的時間，變遷過程需一定的時間，其中，τF(t1)=DT表示到達列車從區(qū)間進入到達場的時間，τF(t8)=FT表示出發(fā)列車從出發(fā)場到區(qū)間的時間。B={AT(t2)，AT(t3)，AT(t4)，AT(t5)，AT(t6)，AT(t7)}中的變遷則與計劃無關，只需滿足變遷條件即可。其中，τF(t2)=DJT表示到達技術作業(yè)時間，τF(t3)=GT為掛車時間，τF(t4)=TT為峰調推峰時間，τF(t5)=LT為k次循環(huán)變遷的總時間，表示溜放時間，τF(t6)=BT為尾調編組及轉場時間，τF(t7)=FJT為出發(fā)技術作業(yè)所需的時間。另外，因不同類型的出發(fā)列車對編組作業(yè)時間要求不同，τF(t6)=BT應滿足如下規(guī)定：

根據變遷的前集謂詞中可參與替換的元組數量不同，將B進一步分為B′、B″兩大類。其中，B′={AT(t4)，AT(t5) }，這類變遷對前集謂詞中參與變遷的元組無選擇性。 B″={AT(t2)，AT(t3)，AT(t5)，AT(t6)，AT(t7) }，這類變遷對其前集謂詞中參與可行替換的元組具有選擇性。

對于AT(t7)，應最先選擇滿足列車運行圖規(guī)定的出發(fā)列車的元組參與變遷。對于AT(t6)，除了和 AT(t7)的選擇要求一樣外，還應滿足以下約束：

式（5）中，QTm表示階段內m次列車最遲發(fā)車時間，由發(fā)車計劃規(guī)定；Ti6表示元組vi參與t6變遷的起始時間；QYj表示 j方向上的最大牽引數，為硬約束。

對于AT(t3)，在前集謂詞中選擇元組參與變遷時，應遵循“先到先解、解體照顧編組”原則，即在AP(p2)中選擇含最先出發(fā)列車急需車流的元組vj參與變遷，還應滿足以下約束：

式（5）和式（7）共同構成了配流在接續(xù)時間上的約束，其中，T3j表示元組vj參與t3變遷的起始時間。

4 算法設計

為了提高求解效率，減少系統模型的變遷次數，Dijkstra算法[12]、啟發(fā)式算法[13]、推理算法[14-15]等，已被引入到該領域。但由于在優(yōu)化配流方案時，需遵循“先到先解、解體照顧編組”原則，而該原則也是基于一種反向推理的過程。基于此，本文在既有變遷約束的基礎上，借鑒文獻[14]中的反向推理設計算法，同時考慮到系統模型時間的全局性，在謂詞及變遷約束的基礎上，給出如下算法步驟。

步驟1有關參數錄入。

步驟2置n為系統變遷起始時間（n為全局時間控制變量，以分鐘計）。

步驟3結合反向推理思想，依照系統模型中各變遷規(guī)則，依次選取符合參與t8,t7,…,t1變遷的元組。

步驟4記錄變遷內容，更新系統標識，n++。

步驟5判斷n是否溢出系統的變遷時間范圍。如果是，系統變遷結束，進入下一步；否則，返回步驟3。

步驟6記錄變遷內容，更新系統標識。

步驟7有關記錄輸出，算法結束。

在已有說明的基礎上，根據配流問題核心，給出配流的示意如圖6所示。

圖6 配流示意圖

結合圖6，通過該算法步驟，便可確定車流的解體時間、編組時間以及車流間如何搭配。

5 算例驗證

以某編組站2∶00～6∶00階段為例，對本文提出的理論進行驗證。剔除該階段內無關車流及設備，各車場容量及作業(yè)時間分別見表3、表4。

表3 車場容量

表4 作業(yè)時間

根據該站車流在不同去向上的牽引定數及出發(fā)列車類型，可獲取調車場股道的運用方案。調車場股道運用見表5。

表5 調車場股道運用

按照列車確報及列車運行圖的要求，在2：00～6：00內，該站列車到達計劃及發(fā)車計劃分別見表6、7所示。

表6 列車到達計劃

表7 列車發(fā)車計劃

本階段開始，有關謂詞中的元組存放情況如下所示：

將有關參數輸入模型中，根據算法，經VC++6.0語言編程，便可得到配流方案。根據t3和t6每次變遷時間及前集謂詞中元組參與變遷的次序，最終得到的解體順序表、編組順序表分別見表8、表9。

表8 解體順序表

從表6～9可以看出，因受接續(xù)時間及滿軸約束，45005次列車晚點發(fā)車2 min，并影響后續(xù)24040次列車晚點發(fā)車1 min，其余出發(fā)列車均正點發(fā)車，該階段內，正點發(fā)車率為77.8%。另外，考慮到調機在該階段內的應用情況，根據t3和t6變遷，調機累計作業(yè)時間如圖7所示。

表9 編組順序表

圖7 調機累計作業(yè)時間

圖7 可以看出，該階段內，t3累計變遷112 min，t6累計變遷168 min，分別反應了峰調和尾調的累計工作時間，各占總時間的46.7%和70.0%，這主要是因為系統在變遷過程中，推峰解體時間小于編組作業(yè)時間，這也反映出該站編組能力較為緊張。截止本階段末，在各車場的結存情況如下：

可以看出，謂詞及元組可以直觀地反應出本階段末車流結存情況。經分析車流可以發(fā)現，為了確保28010次列車按時發(fā)車，階段開始時AP(p2)中的元組＜82a,242c,42d＞首先參與了變遷，這主要是因為算法中的變遷約束所致。可見，該算法對于系統變遷過程中參與變遷元組的選擇具有一定的優(yōu)勢，進而減少了系統變遷的次數。在算例求解過程中，系統變遷共計約為120次。

針對配流問題，文獻[16]認為動態(tài)規(guī)劃無法求得最優(yōu)解，故用Greedy算法對其模型進行求解?；诖耍疚囊韵到y模型為基礎，利用Greedy算法思想對算例求解，結果發(fā)現，系統變遷約106次，45005次列車正點發(fā)車，但同時導致了32007次列車停運?？梢姡cGreedy算法相比，本文設計的反向推理算法雖然在系統變遷效率方面略顯不足，但是在軟約束方面具有一定的優(yōu)勢，更具實用性。

最后，根據算法中的變遷過程，給出4∶40～5∶56時間段內系統變遷的一個進程，該進程如圖8所示。

圖8 系統變遷的一個進程

從圖8中可以看出，系統各變遷是同時進行的，即系統具有異步、并發(fā)的特性，從而也說明了編組站作業(yè)系統是一個集順序和并發(fā)于一體的車流加工系統。

6 結語

配流是編制階段計劃的核心，對提高編組站作業(yè)效率具有重要作用。本文以單向縱列式編組站為背景，結合編組站作業(yè)流程，通過建立TPr/T_系統對編組站作業(yè)的流程再造，并行性分析，進而得出配流過程中的瓶頸所在，以達到研究編組站配流的目的，這也是利用TPr/T系統研究配流的優(yōu)勢所在。此外，系統模型的求解效率以及如何尋求更加有效的求解算法將是本論文下一步所研究的重點。

[1]王慈光.編組站動態(tài)配流模型與算法研究[J].鐵道學報，2004，26（1）：1-6.

[2]彭其淵，趙軍，韓雪松.技術站廣義配流問題模型與算法[J].中國鐵道科學，2010，31（2）：108-114.

[3]趙軍，彭其淵.雙向編組站配流問題整數規(guī)劃模型及算法[J].鐵道學報，2014，36（9）：10-19.

[4]馬亮，郭進，陳光偉，等.鐵路編組站動態(tài)配流的約束傳播和多點構建性搜索的混合算法[J].信息與控制，2015，44（2）：230-237.

[5]黎浩東，何世偉，景云，等.考慮不同滿軸約束的編組站階段計劃配流優(yōu)化[J].鐵道學報，2012，34（7）：10-17.

[6]薛鋒，王慈光.編組站配流相關問題分析[J].交通運輸工程與信息學報，2008，6（4）：29-39.

[7]趙軍，彭其淵.單向編組站配流與調機運用綜合問題[J].鐵道學報，2012，34（11）：1-9.

[8]黎浩東，宋瑞，何世偉，等.基于列車解編作業(yè)時間估算的編組站階段計劃配流優(yōu)化[J].中南大學校報，2014，45（1）：317-327.

[9]李望，倪少權.基于TPr/T-S的客專車站通用模型及仿真[J].西南交通大學學報，2013，48（5）：934-941.

[10]王琦，韓江洪，王青山.Petri網合成理論及應用綜述[J].計算機仿真，2008，25（12）：8-11.

[11]袁崇義.Petri網原理與應用[M].北京：電子工業(yè)出版社，2005.

[12]周強，司豐煒，修言彬.Petri網結合Dijkstra算法的并行測試任務調度方法[J].電子測量與儀器學報，2015，29（6）：920-927.

[13]李斌.基于Petri網和啟發(fā)式搜索的調度算法研究[D].杭州：浙江大學，2015.

[14]周劍峰，彭磊.基于反向模糊Petri網的應急響應條件下事故的質因分析[J].災害學，2015，30（3）：124-126.

[15]王慧英，樂曉波，周愷卿.一種基于模糊Petri網的雙向并行推理算法[J].計算機工程，2014，40（40）：208-212.

[16]郭瑞，郭進，蘇躍斌，等.基于Greedy方法的動態(tài)配流模型與近似算法[J].西南交通大學學報，2014，49（4）：712-719.

ZHANG Zhengkun,ZHU Changfeng

School of Traffic and Transportation,Lanzhou Jiaotong University,Lanzhou 730070,China

Research on wagon-flow allocation for marshalling yard based on TPr/T_system.Computer Engineering and Applications,2017,53（21）：219-224.

The model of TPr/T_system about marshalling yard is built,by extending Pr/T_system to TPr/T_system,according to Petri net theory and the marshalling yard operation procedure.In the model,regarding train or car row as a tuple to restrain the resource condition to wagon-flow allocation.By restraining the predicate capacity to settle the space constrain,besides,the time constraint is settled by restraining transition.In order to obtain a reasonable scheme about wagon-flow allocation,the full axis departure,as far as possible with the punctual departure,is regarded as the optimization goal in the model.The optimization goal can be realized by using the algorithm based on the backward reasoning thought.Finally,an example is used to verify the rationality of the theory presented by the paper.

marshalling yard;wagon-flow allocation;Petri net;TPr/T_system

A

U292.4

10.3778/j.issn.1002-8331.1605-0027

國家自然科學基金（No.61364028）；教育部人文社科規(guī)劃基金項目（No.15XJAZH002）；蘭州市科技局研政產合作支撐計劃項目（No.2011-1-111）。

張正坤（1989—），男，碩士研究生，主要研究方向為交通運輸優(yōu)化理論與方法，E-mail：zzknlxy@163.com；朱昌鋒（1972—），男，教授，主要研究方向為交通運輸優(yōu)化理論與方法。

2016-05-05

2016-07-05

1002-8331（2017）21-0219-06

CNKI網絡優(yōu)先出版：2016-08-01,http://www.cnki.net/kcms/detail/11.2127.TP.20160801.1017.002.html