喬永濤，孫 猷

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

1 概述

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

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

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

2 情景推理原理

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

2.1 名詞解釋

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

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

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

路網(wǎng)：指按照調(diào)度區(qū)段內(nèi)車站行車方向，以車站為頂點(diǎn)，區(qū)間行車方向?yàn)檫叺挠邢驁D。

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

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

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

調(diào)整時(shí)長(zhǎng)：指調(diào)整開(kāi)始時(shí)間至調(diào)整結(jié)束時(shí)間的時(shí)間長(zhǎng)度。

初始情景：指當(dāng)前時(shí)刻的情景，作為情景推理的基礎(chǔ)開(kāi)始情景。

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

2.2 步進(jìn)條件

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

Si到Si+1的推理過(guò)程說(shuō)明如下。

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

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

表1 步進(jìn)條件Tab.1 Step condition table

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

2.3 算法流程

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

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

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

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

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

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

圖2 啟動(dòng)調(diào)整時(shí)刻運(yùn)行圖畫(huà)面Fig.2 TWD screen image at startup adjustment time

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

2.3.2 基于情景棧的算法流程

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

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

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

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

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

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

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

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

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

3 結(jié)果與分析

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

圖4 武廣三臺(tái)鋪畫(huà)封鎖符號(hào)時(shí)的列車運(yùn)行Fig.4 Santai (Wuhan-Guangzhou railway) TWD when plotting blocking symbol

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

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

4 總結(jié)

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