喬永濤，孫 猷

（1.卡斯柯信號有限公司，上海 200071；2.上海市鐵路智能調(diào)度指揮系統(tǒng)工程研究中心，上海 200071）

1 概述

列車運行圖是鐵路運輸調(diào)度指揮的核心內(nèi)容，是鐵路行車組織工作的基礎(chǔ)[1]。而列車運行調(diào)度是指在列車運行工作中，因各種因素和突發(fā)事件的影響，使得列車運行的實際狀態(tài)偏離預(yù)定值，需要不斷對列車運行計劃進行調(diào)整，以盡可能小的代價，盡快恢復(fù)列車的有序運行狀態(tài)[2]。

傳統(tǒng)的列車運行計劃調(diào)整手段為人工調(diào)整[3]，但人工調(diào)整的手段效率較低，且較大程度依賴于調(diào)度員的知識熟練程度和業(yè)務(wù)能力，表現(xiàn)為調(diào)整結(jié)果不一致。因此以各種算法為主體的調(diào)整方案受到了一定關(guān)注。文獻[4-6]以統(tǒng)籌學(xué)方法為原理，以股道占用、列車運行晚點最小等作為調(diào)整目標，建立了數(shù)學(xué)模型實現(xiàn)了對運行圖的優(yōu)化。但這些方法在求解大規(guī)模列車運行圖仍存在一定困難。文獻[7]采用了遺傳算法進行列車運行調(diào)整，可以較好地模擬列車運行調(diào)整過程。然而遺傳算法本身存在一些問題，如收斂速度較慢、易出現(xiàn)早熟等，不易獲得最優(yōu)結(jié)果。文獻[8]采用了禁忌搜索算法，考慮了較為全面的優(yōu)化策略進行調(diào)整。然而這些模型變量多，建模過程復(fù)雜，當優(yōu)化目標存在動態(tài)變化時，難以得到較好效果。文獻[9]采用了粗糙集的方法解決列車運行調(diào)整系統(tǒng)中信息難以獲取和表達的問題。但對于不同調(diào)度區(qū)段不同的決策規(guī)則難以適用，因此通用性不強。

本文提出一種基于情景推理的列車運行調(diào)整方法，該方法的應(yīng)用場景是列車在運行中遭遇突發(fā)情況需要封鎖或限速時，給調(diào)度員提供一種根據(jù)調(diào)度規(guī)則快速調(diào)整運行圖的方法。充分考慮各調(diào)度區(qū)段調(diào)度員的決策規(guī)則。算法以站場圖上列車與車站的位置變化為步進單元，快速推理出列車調(diào)整中每一狀態(tài)下的合理狀態(tài)從而得到優(yōu)化的調(diào)整結(jié)果。

2 情景推理原理

本節(jié)將介紹情景推理的原理部分，從算法中應(yīng)用的名詞解釋、步進條件、算法流程和結(jié)果應(yīng)用4部分進行闡述。

2.1 名詞解釋

情景限制：分為線路限制和故障限制。線路限制是指車站股道數(shù)目、咽喉接發(fā)能力、股道有無站臺、站臺接車編組限制和有無上水吸污設(shè)備等車站條件。故障限制是指接觸網(wǎng)停電、異物侵線、區(qū)間紅光帶、道岔故障、風/雨/雪天氣和列車故障等異常條件。在情景推理過程中，將上述限制條件歸納為股道可用限制、咽喉可用限制、區(qū)間可用限制和降速限制等。

當前車次：指某一時刻，正在線路上運行的車次，包括站內(nèi)車次和區(qū)間車次。

等待車次：指某一時刻，等待接入本區(qū)段的車次和本區(qū)段內(nèi)等待始發(fā)的車次。

路網(wǎng)：指按照調(diào)度區(qū)段內(nèi)車站行車方向，以車站為頂點，區(qū)間行車方向為邊的有向圖。

情景：指特定路網(wǎng)中，在某一時刻T情景限制的條件下，當前車次和等待車次組成的集合。每一個情景都對應(yīng)一個具體時刻。

調(diào)整開始時間：指調(diào)度員設(shè)置的開始調(diào)整時刻。

調(diào)整結(jié)束時間：指調(diào)度員設(shè)置的結(jié)束調(diào)整時刻。

調(diào)整時長：指調(diào)整開始時間至調(diào)整結(jié)束時間的時間長度。

初始情景：指當前時刻的情景，作為情景推理的基礎(chǔ)開始情景。

結(jié)束情景：指調(diào)整結(jié)束這一時刻的情景，用于判斷情景推理結(jié)束。

2.2 步進條件

每一步的情景推理過程都是基于上一情景展開的，推理開始即為初始情景S0，推理成功時則流轉(zhuǎn)至下一情景S1。以→表示流轉(zhuǎn)過程，一個完整的情景推理流程可表示為S0→S1→S2→…→Sn。如果Sn是結(jié)束情景，那么推理結(jié)束。

Si到Si+1的推理過程說明如下。

在列車運行圖上，調(diào)度員人工調(diào)整運行線實際上就是重新安排列車在每個車站的到發(fā)時間，所以情景推理算法就以列車到達點和出發(fā)點的變化作為推理步進條件。下面以車次A 與車站B 的進/出站情況來闡述步進條件。

針對單個車次的步進條件分析如表1 所示，而實際推理過程中情景是當前車次和等待車次集合構(gòu)成的。因此整個情景的步進條件選取是以距離當前時間最近的單個車次步進條件操作為依據(jù)。在Si中存在集合T1={t11,t12…t1m},表示m個車次，它們分別在時刻t11,t12…t1m進站。存在集合T2={t21,t22…t2n},表示有n個車次，它們分別在時刻t21,t22…t2n出站。區(qū)間中有多個車次的情況下，區(qū)間中車次要依次進站。綜上可知有m+n種從Si推理至Si+1的步進方案，但最優(yōu)的步進方案即為集合T1，T2中時間最小的一種，此時最小時間記為t。而實際上這個最優(yōu)方案能否推理成功受到情景限制的影響。如果步進方案和情景限制不沖突，那么便可以從情景Si推理出Si+1，Si+1的情景時間即為Si的情景時間加t。

表1 步進條件Tab.1 Step condition table

若由于情景限制，導(dǎo)致Si不能推出Si+1，此時進行情景回退，回退至與Si情景操作同一車次的上一情景Sk，針對Sk進行操作處理。例如在Si情景到Si+1情景推理方案是車次進站，如果Si情景中該進站車站的股道已經(jīng)被其他車次占用或者可用股道被封鎖時，那么Si就不能推出Si+1。此時推理失敗的原因是Sk往Si推理時車次出站過早。解決方法是在Sk車站將車次扣停一定時間，該時間由Si+1最早股道空閑時間ti減去Si的情景時間和該車次區(qū)間運行時分計算出，將該時間命名為Δt。此時情景回退至Sk，同時將車次扣停時間增加Δt，重新進行推理。

2.3 算法流程

算法的調(diào)整時間范圍是需要調(diào)度員確定的。如果本次調(diào)整指定的調(diào)整時間范圍為[Ts,Te]，其中Ts是調(diào)整開始時間，Te是設(shè)定的調(diào)整結(jié)束時間，那么算法本次僅調(diào)整該時間范圍內(nèi)的列車。算法的輸入是當前時刻下的調(diào)監(jiān)表示和列車運行圖，調(diào)監(jiān)表示用于獲取路網(wǎng)中所有當前車次的實時狀態(tài)，列車運行圖用于獲取等待車次與結(jié)果應(yīng)用。

2.3.1 構(gòu)造初始情景S0

初始情景即為當前時刻的情景。初始情景S0包括以下元素：初始情景時間、當前車次、等待車次、情景限制和路網(wǎng)。當前時刻即為初始情景時間，路網(wǎng)可以從配置文件中獲取，下面著重說明初始情景的其他3 個要素如何構(gòu)造。

啟動調(diào)整這一時刻的調(diào)監(jiān)畫面如圖1 所示。從調(diào)監(jiān)服務(wù)器可以獲取這一時刻在路網(wǎng)上運行的車次位置及方向，將它們保存下來并整理之后就是初始當前車次。另外從調(diào)監(jiān)服務(wù)器可以獲取到區(qū)段停電或封鎖、道岔故障或封鎖、股道停電或封鎖、限速區(qū)段及限速值等信息，將以上信息整理之后將形成情景限制的第一部分。

圖1 啟動調(diào)整時刻調(diào)監(jiān)畫面Fig.1 Monitoring screen image at startup adjustment time

啟動調(diào)整這一時刻的運行圖畫面如圖2 所示。從運行圖服務(wù)器可以獲取到這一時刻（圖2 中用藍豎線表示）之后等待接入路網(wǎng)或者始發(fā)到路網(wǎng)的車次所在的車站及先后順序，將它們保存并整理之后就是初始情景等待車次。另外從運行圖服務(wù)器可以獲取到區(qū)段中調(diào)度員繪制的封鎖，限速慢行和接觸網(wǎng)停電符號等信息，將以上信息整理之后將形成情景限制的第二部分。

圖2 啟動調(diào)整時刻運行圖畫面Fig.2 TWD screen image at startup adjustment time

將以上兩部分信息進行合并后，即得到了完整的情景限制條件，初始情景至此構(gòu)造完畢。

2.3.2 基于情景棧的算法流程

2.3.1 節(jié)中已經(jīng)構(gòu)造好了初始情景S0，為了便于推理，本節(jié)引入情景棧這一概念。情景棧是由情景構(gòu)成的棧結(jié)構(gòu)，用于保存情景元素。情景推理時算法按照推理順序?qū)⒚恳粋€推理成功的情景壓入棧中保存，在進行情景推理時，取出棧頂元素。具體流程如圖3 所示。算法流程如下。

圖3 算法流程Fig.3 Algorithm flow chart

步驟1：構(gòu)造初始化情景S0，將構(gòu)造出來的S0壓入情景棧。

步驟2：彈出情景棧頂?shù)脑兀僭O(shè)將其命名為S。

步驟3：如果S是結(jié)束情景，那么結(jié)束推理；如果S不是結(jié)束情景，執(zhí)行步驟4。

步驟4：由情景S推理出S1，如果上次推理失敗，需要在推理時考慮推理失敗原因。

步驟5：S如果推理出S1成功，那么將S1壓入情景棧，跳至步驟2。S如果無法推理出S1，即推理失敗，此時返回導(dǎo)致情景發(fā)生推理失敗的原因與情景S操作同一車次的上一情景S2。在棧中彈出該情景以上全部情景，并重新以解決推理失敗原因的方案進行情景推理，跳至步驟2。

2.4 結(jié)果應(yīng)用

經(jīng)過上述情景推理調(diào)整過程，即得到一組有序情景集合{S1,S2…Sn}。這個情景集合對應(yīng)的情景時間為T1,T2…Tn，即為每個推理車次于特定站的到點或發(fā)點。將以上推理得出的到發(fā)點賦值到車次對應(yīng)的運行線上就完成了情景推理的結(jié)果應(yīng)用。

3 結(jié)果與分析

武廣三臺鋪畫封鎖符號時的列車運行如圖4 所示。藍色軸線代表當前時間線，紅色軸線代表調(diào)整范圍開始時刻，黑色軸線代表調(diào)整范圍結(jié)束時刻。在此時調(diào)整范圍內(nèi)，存在約100 趟列車。封鎖符號鋪畫于郴州西站至樂昌東站區(qū)間，封鎖時長為1 h。

圖4 武廣三臺鋪畫封鎖符號時的列車運行Fig.4 Santai (Wuhan-Guangzhou railway) TWD when plotting blocking symbol

經(jīng)過本文算法調(diào)整后，武廣三臺的列車運行如圖5 所示，調(diào)整后的列車運行線在封鎖符號期間避開封鎖區(qū)間。且后方站的列車發(fā)點均未早于封鎖結(jié)束時間，各列車之間的發(fā)點也滿足列車追蹤間隔。

圖5 武廣三臺經(jīng)算法調(diào)整后的列車運行Fig.5 Santai (Wuhan-Guangzhou railway) TWD after algorithm adjustment

4 總結(jié)

本文提出的基于情景推理的列車運行計劃調(diào)整方法計算速度較快，實用性較強，可以在一定程度上解決目前調(diào)度臺在遇到惡劣天氣、設(shè)備故障等情況下大規(guī)模列車快速調(diào)度的問題。在算法設(shè)計過程中，充分考慮了各約束條件以及決策規(guī)則，規(guī)避了大量無需考慮的情景，使計劃調(diào)整實時運算耗時急劇減小。應(yīng)用結(jié)果表明，該算法在列車計劃調(diào)度調(diào)整方面具有一定時效性與準確性，能夠減輕調(diào)度員工作強度，提高故障處理效率。