基于模糊時間知識推理的到發(fā)線運用沖突預測

馮麗萍，張立東，高 佳

（1.山東交通學院 軌道交通學院，山東 濟南 250357；2. 山東交通學院 交通與物流工程學院，山東 濟南 250357)

0 引言

到發(fā)線運用方案是涉及車站固定資源調配、車站列車到發(fā)順序、特殊使用要求等限制的綜合性方案，是保證列車能夠正點、安全接發(fā)的關鍵技術文件之一。在使用過程中，往往由于列車運行受到干擾造成晚點導致實際使用方案偏離計劃，繼而需要對到發(fā)線運用方案進行調整。傳統(tǒng)的到發(fā)線運用方案調整多在計劃已經(jīng)發(fā)生偏離后進行，且假定后續(xù)不會再發(fā)生其他擾動事件，導致到發(fā)線運用調整前提假設過于絕對，到發(fā)線運用調整彈性不足。因此，如何科學合理地豐富到發(fā)線運用方案調整決策信息，對提高到發(fā)線運用方案調整與優(yōu)化水平具有重要意義。

目前針對到發(fā)線運用方案的研究主要集中在方案優(yōu)化與動態(tài)調整2個方面。任禹謀等[1-2]以到發(fā)線均衡利用為優(yōu)化目標，構建咽喉區(qū)和到發(fā)線整體運用優(yōu)化模型，并以列車晚點總時長最小為目標，引入滾動時域調度策略，建立高速鐵路車站到發(fā)線動態(tài)調整模型；霍亮[3]以咽喉道岔、到發(fā)線運用效率最大化和調機出段作業(yè)接續(xù)時間最少、走行距離最短為目標，對鐵路客運站調機運用與列車接發(fā)進路進行了協(xié)同優(yōu)化；朗越等[4]以均衡到發(fā)線設備時空應用和提高車站作業(yè)計劃的穩(wěn)定性為目標，提出列車進路鏈式分配模型；針對列車到發(fā)不確定性，李濤等[5-6]利用數(shù)理統(tǒng)計方法確定列車到發(fā)時刻的波動分布，并以列車占用到發(fā)線時間最小和到發(fā)線運用最均衡為優(yōu)化目標建立客運站到發(fā)線運用優(yōu)化模型；金福才等[7]將列車運行調整中的沖突判定轉化為區(qū)間、車站和到發(fā)線3類，并引入堆棧方法對到發(fā)線沖突進行判定；廉志斌等[8]以所有列車的連帶晚點時間之和最少、所有列車實際占用到發(fā)線偏離原計劃程度最小為目標構建到發(fā)線運用計劃調整模型并設計求解算法；潘明軒等[9]通過仿真實驗分析了到發(fā)線運用對到達時間間隔的影響，并以最小總運營時間為目標建立優(yōu)化模型，有效提高車站接發(fā)作業(yè)效率及通過能力。這些研究雖涉及列車到發(fā)不確定性的處理，但是優(yōu)化調整的決策過程多局限在當前時間段，對未來一段時間內的到發(fā)線運用情況未予考慮。

研究通過模糊時間知識推理，將模糊彈性處理后的到發(fā)線運用方案在未來一段時間內的沖突進行定位和量化，可反饋用于當前的調整決策。擬通過整合周期性統(tǒng)計數(shù)據(jù)，模糊化處理到發(fā)線運用過程中的時間要素，通過構建到發(fā)線運用方案Petri網(wǎng)模型，基于模糊時間知識推理算法定位列車到發(fā)沖突位置并量化沖突可能性，為到發(fā)線運用方案調整奠定決策基礎。

1 到發(fā)線運用方案建模

1.1 運用方案約束條件

到發(fā)線作業(yè)過程可以分為咽喉區(qū)占用作業(yè)和到發(fā)線占用作業(yè)2部分。到發(fā)線運用方案解決的是列車到發(fā)所需的咽喉區(qū)道岔、到發(fā)線的空間設備資源分配和列車占用到發(fā)線的時間分配問題。因此，到發(fā)線運用方案的制定受到時空約束如下。

（1）時間約束包括列車到發(fā)作業(yè)時間標準和相鄰列車到發(fā)間的最小時間間隔約束。前者是指列車進行到發(fā)作業(yè)過程所需的最小時間，后者是指包括車站間隔時間和追蹤間隔時間的列車間隔時間。

（2）空間約束是指由于車站設備資源的有限性和獨占性，導致的列車對各項設備資源的占用不能同時進行且同一設備資源不能同時被一列以上的列車同時占用。

對到發(fā)線運用方案的時空約束形式化定義如下。假定某車站計劃內共到發(fā)m列列車，車站內包括咽喉道岔組和到發(fā)線的設備資源n項，任一列車i在車站的到發(fā)過程中對任一設備資源j的占用關系xij需要滿足以下約束條件。當?shù)趇列列車占用第j項設備資源時，xij取1，否則取0。

1.2 基于Petri網(wǎng)的運用方案建模

Petri網(wǎng)自1962年由C.A.Petri提出以來，以其簡單的圖形化表示和嚴密的數(shù)學理論支撐，尤其是在描述系統(tǒng)順序、并發(fā)、沖突、異步等事件發(fā)生關系上的優(yōu)勢，被廣泛應用于典型的鐵路運輸問題。考慮到到發(fā)線運用方案中的約束關系，建立包括M個庫所和N個變遷的到發(fā)線運用方案Petri網(wǎng)形式化模型N如下。

式中：P= {p1，p2，…，pM}為模型中的庫所集合，根據(jù)庫所標識表達到發(fā)線運用方案模型中列車位置、設備資源處于占用或者空閑的狀態(tài)，此外還存在部分沒有實際含義的邏輯庫所，用以表達變遷間觸發(fā)的邏輯關系；Tr= {tr1，tr2，…，trN}為模型中的變遷集合，用以表示到發(fā)線運用方案使用中的列車對設備資源的占用與釋放；F為模型中的庫所與變遷間的流關系，用以描述列車對設備資源動作的約束條件與后續(xù)影響；K，W分別為模型中庫所的容量函數(shù)和流關系的權函數(shù)，且滿足K=W= 1；M0為模型的初始標識，表示當前所有列車對所有設備資源的占用或釋放狀態(tài)。

基于到發(fā)線運用方案模型的形式化定義，建立到發(fā)線運用方案模型的具體步驟如下。

（1）考慮每列列車在該站的到發(fā)作業(yè)過程，建立初始Petri網(wǎng)模型。單列車作業(yè)模型如圖1所示。其中，p1至p5分別代表列車到達站外、列車占用進站道岔組、列車占用到發(fā)線、列車占用出站道岔組和列車出站5種狀態(tài)，Tr1至Tr4分別代表列車占用進站道岔組、列車占用到發(fā)線、列車占用出站道岔組、列車出站4種事件。需要特別說明的是為了敘述的方便僅考慮了進出站各1個道岔組，在實際建模中需按照列車對道岔組的占用順序，依次添加庫所和變遷。

圖1 單列車作業(yè)模型Fig.1 Workflow model of a signal train

（2）考慮到發(fā)線運用方案中多列列車對同一個道岔組、同一條到發(fā)線在不同時間的計劃占用關系，增加模型空間約束。增加空間約束模型如圖2所示。其中，p6至p10，Tr5至Tr8的定義與圖1類似，為另一列列車的到發(fā)作業(yè)過程模型，p11為到發(fā)線約束邏輯庫所，根據(jù)到發(fā)線運用方案的形式化模型，庫所內含有唯一托肯，表示2列列車對1條到發(fā)線的資源競爭關系。

圖2 增加空間約束模型Fig.2 Model with spatial constraint

（3）考慮相鄰列車在該站的到發(fā)作業(yè)間的列車間隔時間，在空間約束模型的基礎上增加模型時間約束，構建完整到發(fā)線運用方案模型。運用方案模型示例如圖3所示，p12為2列列車作業(yè)順序關系，根據(jù)圖3中的流關系，下層列車出站道岔組占用變遷Tr8觸發(fā)完成后才有可能觸發(fā)上層列車進站道岔組占用變遷Tr1，即下層列車出發(fā)作業(yè)在前，上層列車進站作業(yè)在后。

圖3 運用方案模型示例Fig.3 Model example of the operation plan

2 時間模糊化處理與推理算法

2.1 時間模糊化處理

在計劃列車運行圖中，設列車在車站到發(fā)線的停留時間為T= (b，c)，其中c為圖定停站時間，min；b為最小停站時間，min；r= (c-b)為圖定冗余時間，min。當列車在該站通過時，其在到發(fā)線上的停留時間可表示為(0，0)?？紤]計劃列車運行圖使用的周期特性，以b，c為對比值，統(tǒng)計車站在1個周期內的到發(fā)列車實際停留時間，分別計算停留時間左偏(小于b)期望值E(Tb)和右偏(大于c)期望值E(Tc)，即可得到該站到發(fā)線停留時間的梯形模糊數(shù)如下。

其中，h= 1，表示取值可能性的最大值，以上所有時間要素均為時間段。

同理，可對車站各到發(fā)線的進站道岔組占用時間及出站道岔組占用時間進行模糊化處理得到相應的梯形模糊數(shù)。

2.2 沖突判定條件與評價

列車到發(fā)線運用沖突是指相鄰列車對同一設備資源(即進站道岔組、到發(fā)線、出站道岔組)占用的時間間隔不滿足最小時間間隔的約束，即

時間模糊化處理后，列車對設備資源的占用時間為梯形模糊數(shù)。沖突判定示意圖如圖4所示，設前行列車梯形模糊數(shù)為T1=h(A，B，C，D)，后行列車梯形模糊數(shù)為T2=h(E，F(xiàn)，G，H)，其沖突判定為后行列車的最早開始時間E與前行列車最晚結束時間D的差值，即

圖4 沖突判定示意圖Fig.4 Conflict judgment

基于梯形模糊數(shù)的定義及沖突判定準則，相鄰列車間對同一設備資源的占用沖突可能性可通過如下步驟獲得。

（1）根據(jù)緩沖時間使用的緊前原則，利用T1中的冗余時間進行沖突消解。若T1中的冗余時間r1=C-B大于沖突消解所需時間R，則沖突完全消解，沖突發(fā)生可能性為0。否則，進入第（2）步。

（2）利用T2中的緩沖時間r2=G-R進一步消解沖突，若r1+r2≥R，則沖突完全消解，沖突發(fā)生可能性為0，否則，T1，T2間隔時間不滿足最小時間間隔約束，進入第（3）步計算沖突發(fā)生可能性。

（3）沖突發(fā)生可能性計算的前提是r1，r2已全部用于消解沖突時間R。此時由于梯形T1，T2中冗余時間已為0，梯形T1中的B，C點重合為一點，同理梯形T2中的F，G點重合為一點。原有的梯形模糊數(shù)更新為T1=h(A'，B'(C')，D')，T2=h(E'，F(xiàn)'(G')，H')。以T1中D'為起點，以2事件最小間隔時間Imin為長度作輔助線與T2相交部分的陰影面積占T2總面積的比例即為沖突發(fā)生可能性。

沖突可能性求解示意圖如圖5所示。由于沖突的實際發(fā)生是在前后兩事件的冗余時間全部消耗完成后依然小于最小時間間隔的要求，因此，T1，T2中的冗余時間為0，由梯形模糊數(shù)變?yōu)槿悄：龜?shù)。T1，T2沖突可能性η12的計算公式為

圖5 沖突可能性求解示意圖Fig.5 Conflict possibility solving

式中：S(E'K'J')為陰影部分面積；S(E'H'F')為更新后的三角模糊數(shù)T2面積。

2.3 到發(fā)線運用沖突推理算法

模糊時間知識推理算法在模糊時間Petri網(wǎng)中引入模糊時間片π(τ)、模糊使能時間e(τ)、模糊發(fā)生時間o(τ)和模糊延遲時間d(τ) 4個模糊集理論函數(shù)，基于最遲時間可能性分布函數(shù)latest、最早時間可能性分布函數(shù)earliest以及最小操作min運算方法，對以梯形模糊數(shù)表示的不確定時間進行推理。算法具體可參照文獻[10]和文獻[11]，現(xiàn)對4個模糊集理論函數(shù)概述如下。

（1）模糊延遲時間d(τ)。模糊延遲時間d(τ)是庫所內托肯從到達到滿足時間間隔約束條件所經(jīng)歷的時間長度可能性分布。令d(τ) =h1(a1，b1，c1，d1)，其中，b1為最短作業(yè)時間，c1為圖定作業(yè)時間。

（2）模糊時間片π(τ)。模糊時間片是庫所內托肯在時間τ時處于可用狀態(tài)的可能性分布，即該庫所達到了觸發(fā)后集變遷的條件的可能性分布。同樣令π(τ) =h2(a2，b2，c2，d2)，則

式中：o(τ) = (a4，b4，c4，d4)為變遷的模糊發(fā)生時間；⊕為加法算子。

（3）模糊使能時間e(τ)。模糊使能時間e(τ)是變遷t在時間τ時所有前集庫所處于“有托肯”狀態(tài)且可用的可能性分布。在到發(fā)線運用方案Petri網(wǎng)模型中，變遷的前集庫所可能不止一個。根據(jù)Petri網(wǎng)的變遷使能條件，只有當所有前集庫所中的托肯可用時，變遷才處于使能狀態(tài)。因此，模糊使能時間e(τ)為前集庫所中的最晚模糊時間片π(τ)，即

式中：πx(τ)為m個變遷t的前集庫所的模糊時間片。

（4）模糊發(fā)生時間o(τ)。模糊發(fā)生時間o(τ)是指當多個變遷使能時，根據(jù)一定的決策策略確定該變遷在時間τ發(fā)生的可能性分布。決策策略根據(jù)實際情況可以選擇“先到先服務”“后到先服務”等。本次研究采用“先到先服務”的服務策略，對較早使能的變遷賦予優(yōu)先權。即

式中：ey(τ)為n個使能變遷的模糊使能時間。

基于模糊時間知識推理算法的到發(fā)線運用方案沖突預測步驟如下。①設置到發(fā)線運用方案Petri網(wǎng)模型初始標識，確定車站當前設備設施占用/空閑狀態(tài)、列車位置信息。②自上而下、自左向右基于模糊時間知識推理算法推算變遷模糊發(fā)生時間o(τ)，依次對存在最小追蹤間隔時間約束的前后列車進行沖突判定。若存在沖突，則計算沖突可能性η，并延后后行列車變遷發(fā)生時間以完全消解沖突，更新其模糊時間片。以圖5中的沖突消解為例，將后行作業(yè)發(fā)生時間整體后移K'-E'，滿足T1，T2間最小間隔約束。更新后T2的模糊發(fā)生時間為e(T2) = (K'，F(xiàn)'(G') + (K'-E')，H'+ (K'-E'))。若不存在沖突，則繼續(xù)推理，直至遍歷模型所有變遷。

3 算例

某單線橫列式區(qū)段站部分布置圖如圖6所示，共有7條到發(fā)線，6組道岔。其中1號、II號、3號到發(fā)線為旅客列車到發(fā)線；4號、6號、7號到發(fā)線為貨物列車到發(fā)線；道岔分組基于接發(fā)車進路與道岔的占用及妨礙關系確定。算例假定上行、下行各10列列車，其中旅客列車12列、貨物列車8列。時間間隔約束I= 5 min。列車到發(fā)數(shù)據(jù)示例如表1所示。需要特別說明的是，雖然在本示例中，1號到發(fā)線、II號正線的占用不存在妨礙道岔組，但在實際應用中除直接占用的道岔組外，需考慮由于到發(fā)線使用過程中對妨礙道岔組的間接占用關系。該約束可參照前文到發(fā)線運用方案建模方法，補充模型中的資源占用時空約束關系即可。

圖6 單線橫列式區(qū)段站部分布置圖Fig.6 Layout of district station in horizontal type of single track railway

表1 列車到發(fā)數(shù)據(jù)示例Tab.1 Data example of train arrival and departure

假設將列車到發(fā)數(shù)據(jù)周期性統(tǒng)計處理，接發(fā)列車占用道岔組時間的模糊時間片設置如表2所示。除占用道岔組的模糊時間片處理外，列車停站時間中圖定冗余時間r= 5 min，左偏3 min，右偏1 min。以列車1停站時間為例，其停站模糊時間片為(22，25，31，32)。其余相鄰列車到發(fā)時間間隔模糊時間片中，圖定冗余時間、左偏時間、右偏時間均為1 min。

表2 模糊時間片設置Tab.2 Fuzzy time slice

運用前文中的基于Petri網(wǎng)的到發(fā)線運用方案建模方法，以表1中列車1和列車3為例，構建到發(fā)線運用方案模型如下。

在分別繪制2列列車作業(yè)模型的基礎上，增加因2列車到發(fā)均需占用1號、2號道岔組產生的2個資源約束；最后考慮列車到發(fā)間的時間約束。列車1和列車3到發(fā)關系示意圖如圖7所示，存在列車1和列車3到達的追蹤間隔約束IZD，列車3到達與列車1出發(fā)之間的不同時到發(fā)間隔約束IDF和列車1和列車3出發(fā)的追蹤間隔約束IZF。

圖7 列車1和列車3到發(fā)關系示意圖Fig.7 Arrival-departure relationship between trains No. 1 and No. 3

綜上，構建列車1和列車3到發(fā)線運用方案模型如圖8所示。為增強模型的可讀性，對模型中庫所、變遷的命名規(guī)則規(guī)定如下：下標只有1位數(shù)字的表示列車序號；下標含有2位序號的表示列車對資源的占用關系；上標D表示列車到達站外、F表示列車出發(fā)進入?yún)^(qū)間、L表示占用到發(fā)線、DF表示到發(fā)時間間隔、ZD表示到達追蹤間隔時間、ZF表示出發(fā)追蹤間隔時間。

圖8 列車1和列車3到發(fā)線運用方案模型Fig.8 Arrival-departure plan model of trains No. 1 and No. 3

模型構建完成后，以表示列車1占用進站道岔組1的變遷t11、表示列車1占用到發(fā)線的變遷表示列車3占用進站道岔組1的變遷t31，進行模糊時間知識推理，列車1和列車3到發(fā)模糊時間知識推理示例如表3所示。其中變遷與變遷t31之間存在沖突檢查。

表3 列車1和列車3到發(fā)模糊時間知識推理示例Tab.3 Example of fuzzy temporal knowledge reasoning of arrival-departure relationship between train No. 1 and train No. 3

對算例中的20列列車的到發(fā)線運用方案構建Petri網(wǎng)模型，并基于模糊時間知識推理算法從上到下、從左到右進行推理，列車間沖突可能性示意圖如圖9所示。根據(jù)圖9列車間沖突可能性計算結果得到?jīng)_突可能性分布如表4所示。通過模糊時間知識推理，可對到發(fā)線運用沖突產生的位置及可能性進行預判，為到發(fā)線運用方案調整奠定決策基礎。

圖9 列車間沖突可能性示意圖Fig.9 Conflict possibility between trains

表4 沖突可能性分布Tab.4 Conflict possibility distribution

4 結論

研究通過將列車到發(fā)時間要素模糊化處理，提出基于模糊時間知識推理算法的到發(fā)線沖突預測算法，用以預判沖突發(fā)生位置及可能性，研究結論有以下幾點。

（1）利用到發(fā)線運用計劃周期性使用的統(tǒng)計數(shù)據(jù)，將運用方案中的時間要素從考慮冗余時間的區(qū)間數(shù)據(jù)模糊化為梯形模糊數(shù)，有利于豐富用于運用方案沖突預判的信息，并增強運用計劃調整的彈性。

（2）基于Petri網(wǎng)的到發(fā)線運用方案建模，從單列車作業(yè)模型開始，依次增加資源約束、時間約束，流程邏輯清晰，可為后續(xù)基于編程語言實現(xiàn)面向對象的到發(fā)線運用方案建模提供思路。

（3）利用模糊時間知識推理算法，可實現(xiàn)對到發(fā)線運用方案中單列車到發(fā)偏離程度、列車間到發(fā)沖突發(fā)生的位置及可能性的預判，預判結果可為到發(fā)線運用計劃調整奠定決策基礎。

（4）由于晚點傳播效應的影響，到發(fā)線運用方案的模糊時間知識推理存在越往后，沖突發(fā)生可能性越大，單列車偏離計劃越多的現(xiàn)象。因此，推理到一定時間后，基于模糊時間知識推理的沖突預測不再有實際意義。下一步，可對停止模糊時間知識推理的閾值及基于模糊時間知識推理結果的沖突調整策略開展深入研究。