張正坤 朱昌鋒 馬文虎

（蘭州交通大學(xué)交通運輸學(xué)院 蘭州730070)

0 引 言

列車在正常情況下按圖定計劃運行，當(dāng)列車受不確定因素干擾而偏離計劃時，需要對列車秩序進(jìn)行調(diào)整，其目的是控制列車晚點傳播效應(yīng)，使列車盡可能快地復(fù)序運行[1]。列車運行調(diào)整的關(guān)鍵是合理確定列車在各站的到發(fā)時間及其對運行區(qū)間的占用次序，從而有效疏解相鄰列車間的沖突關(guān)系[2]。在此過程中，因列車運行調(diào)整是基于列車實時狀態(tài)，故而對調(diào)整措施具有較強的時效性要求。相比于其他線路，單線鐵路因上下行列車共用1套固定設(shè)備而使得沖突疏解變得復(fù)雜[3]。因此，單線鐵路上的列車運行調(diào)整問題成為眾多學(xué)者研究和關(guān)注的重點。

最小化列車晚點時間是列車運行調(diào)整的主要優(yōu)化目標(biāo)[4]。Sotskov等[5]和Gholami等[6]將列車運行調(diào)整抽象為一類特殊的、具有阻塞特性的生產(chǎn)調(diào)度問題，其數(shù)學(xué)模型具備NP-hard特性，求解比較困難。D'Ariano等[7]和Lamorgese等[8]通過圖論分析了列車調(diào)整過程中的潛在沖突關(guān)系，構(gòu)建了混合整數(shù)規(guī)劃模型，并設(shè)計局部搜索算法和主從分解算法，但忽略了車站能力對列車運行調(diào)整的影響。為體現(xiàn)列車占用區(qū)間的時序性，Yang等[9]和Meng等[10]從時空網(wǎng)絡(luò)角度建立列車運行調(diào)整的優(yōu)化模型，但因時空網(wǎng)絡(luò)難以刻畫列車屬性及其在技術(shù)站的作業(yè)類型，故而實用性略顯不足。以上研究本質(zhì)上屬于列車運行調(diào)整的靜態(tài)優(yōu)化，其優(yōu)點是通過建立數(shù)學(xué)模型，利用現(xiàn)有的求解軟件或設(shè)計相應(yīng)算法便可獲得質(zhì)量較高的調(diào)整計劃[11-12]，但求解效率較為低下，難以滿足列車運行調(diào)整的時效性需求。此外，通過靜態(tài)優(yōu)化得到調(diào)整計劃在實施過程中對外部條件要求較為苛刻，適應(yīng)性較差。

針對上述研究不足，部分學(xué)者從離散系統(tǒng)仿真的角度對列車運行調(diào)整問題展開研究，并取得較好成果。Goverde等[13]利用極大代數(shù)和理論構(gòu)建列車運行的離散仿真系統(tǒng)，并用Lyapunov指數(shù)對其穩(wěn)定性做了評價分析。離散系統(tǒng)仿真的關(guān)鍵在于沖突預(yù)判和事件觸發(fā)。根據(jù)列車運行實時狀態(tài)，Dorfman等[14]設(shè)計了基于沖突實時檢測和疏解的列車行進(jìn)策略（travel-advance strategy，TAS）。TAS是將列車進(jìn)站作為離散事件的觸發(fā)標(biāo)志，通過設(shè)計事件轉(zhuǎn)移函數(shù)和能力檢測算法驅(qū)動事件變化，進(jìn)而達(dá)到列車運行秩序?qū)崟r調(diào)整的目的。鑒于TAS具有較強的靈活性和廣泛的適應(yīng)性，故而被用于求解不同場景下的列車調(diào)整和調(diào)度問題[15]。

事件轉(zhuǎn)移函數(shù)和能力檢測算法是TAS的核心。其中，事件轉(zhuǎn)移函數(shù)的主要功能是根據(jù)列車在其前方站的到達(dá)時間確定下一離散事件的觸發(fā)時間，但基于該函數(shù)的調(diào)整策略因需重復(fù)執(zhí)行能力檢測算法，致使TAS的執(zhí)行效率有待提升。能力檢測算法是TAS的核心，其主要目的是約束檢查和沖突疏解，該算法通過回溯檢測前方列車數(shù)量與車站剩余能力，判定潛在的沖突類型，進(jìn)而采取相應(yīng)的疏解措施確定離散事件的發(fā)生次序。由于該疏解措施是基于列車的實時運行狀態(tài)，故而得出的調(diào)整計劃是局部最優(yōu)計劃，但不一定是理論上的全局最優(yōu)計劃。為此，Li等[16]從非局部信息的角度改進(jìn)了TAS的調(diào)整策略，但改進(jìn)后的TAS沒有考慮列車在車站的技術(shù)作業(yè)需求，這與實際略有不符。Xu等[17]在列車越行規(guī)則上對TAS做了改進(jìn)，改進(jìn)后的TAS可以減少慢車的等待被越行時間，但該研究僅限于車站單向只含1條到發(fā)線的列車調(diào)度問題，且研究過程中忽略了多等級列車的調(diào)整問題。

基于上述分析，本文采用離散系統(tǒng)仿真方法對單線鐵路半自動閉塞區(qū)段上的列車運行調(diào)整問題展開進(jìn)一步研究。與現(xiàn)有離散系統(tǒng)及TAS相比，本文創(chuàng)新點主要體現(xiàn)在以下3個方面。

1）構(gòu)建的離散系統(tǒng)仿真模型充分考慮了列車等級、車站到發(fā)線數(shù)量及列車在站技術(shù)作業(yè)類型等關(guān)鍵約束，豐富了離散系統(tǒng)仿真列車運行調(diào)整的內(nèi)涵，增強了研究的實用性。

2）設(shè)計基于列車出站的事件轉(zhuǎn)移函數(shù)，與既有TAS的事件轉(zhuǎn)移函數(shù)相比，該函數(shù)有效避免調(diào)整策略在列車區(qū)間運行及在站最小作業(yè)時間上的重復(fù)執(zhí)行，提高了系統(tǒng)仿真的時效性。

3）針對多級列車運行調(diào)整在沖突疏解時產(chǎn)生的決策困難，設(shè)計多級列車分層隨機調(diào)整策略。該策略在豐富調(diào)整結(jié)果多樣性、提高離散系統(tǒng)全局尋優(yōu)能力的同時，擺脫了檢測函數(shù)對車站到發(fā)線數(shù)量的限制。

1 列車運行調(diào)整的離散系統(tǒng)仿真模型

以單線鐵路半自動閉塞區(qū)段的多級列車運行調(diào)整為研究對象，給定DEDS=(S，E，C，V)表示列車運行調(diào)整離散系統(tǒng)（以下簡稱調(diào)整系統(tǒng)）。其中：S為調(diào)整系統(tǒng)論域；E為調(diào)整系統(tǒng)變量；C和V分別為調(diào)整系統(tǒng)的約束條件和優(yōu)化目標(biāo)。系統(tǒng)各要素分別說明如下。

1.1 調(diào)整系統(tǒng)論域

調(diào)整系統(tǒng)論域S包括調(diào)整時域T、車站集合Z、區(qū)間集合Q和列車集合L。其中，所有集合中的元素均為序化數(shù)字。t∈[0 ，T]為系統(tǒng)時鐘，對于任意區(qū)間q及其銜接的兩端車站z和z′，存在如下關(guān)系，見式（1）。

式中：fl=1時，列車l為上行方向列車；fl=0時，列車l為下行方向列車。

1.2 調(diào)整系統(tǒng)變量

1.3 調(diào)整系統(tǒng)的約束條件

單線鐵路半自動閉塞區(qū)段，區(qū)間內(nèi)最多允許有一趟列車運行，見式（5）。

式中：z和z′滿足式（2）關(guān)系。

為確保行車安全，相鄰到達(dá)或相鄰出發(fā)列車間需滿足必要的安全間隔時間，即

式中：列車l為列車l′的前行列車；I為車站安排進(jìn)路及列車進(jìn)出站所需的最小作業(yè)時間，本文取I=3 min。

車站在為列車辦理進(jìn)站作業(yè)時，車站內(nèi)應(yīng)至少有1條空余到發(fā)線以滿足接車需求，即

式中：Nz為車站z的到發(fā)線數(shù)量。

1.4 調(diào)整系統(tǒng)的優(yōu)化目標(biāo)

列車運行調(diào)整的主要目的是盡可能地讓列車按圖定計劃運行。據(jù)此，將調(diào)度區(qū)段末或調(diào)度時段末列車到達(dá)其所在車站的累計晚點時間作為調(diào)整系統(tǒng)的優(yōu)化目標(biāo)，見式（13）。

式中：wr為r等級列車的權(quán)重系數(shù)；為列車l在z站的圖定到達(dá)時間；zl∈Z為調(diào)度區(qū)段末或調(diào)度時段末，列車l所在的車站。

2 多級列車分層隨機調(diào)整策略

2.1 事件轉(zhuǎn)移函數(shù)

事件轉(zhuǎn)移函數(shù)的主要功能是確定調(diào)整系統(tǒng)中下1個離散事件的發(fā)生時間，是實現(xiàn)系統(tǒng)狀態(tài)轉(zhuǎn)移、仿真列車運行過程的關(guān)鍵。本文在文獻(xiàn)[14]的基礎(chǔ)上設(shè)計基于列車出站的事件轉(zhuǎn)移函數(shù)以提高系統(tǒng)仿真的時效性。

為對比分析，首先給出文獻(xiàn)[14]根據(jù)距離與速度間的物理關(guān)系而設(shè)計的基于列車進(jìn)站的事件轉(zhuǎn)移函數(shù)，即

式中：x(l，k)為列車i在進(jìn)站事件e時所在的位置向量；P(l，e)為進(jìn)站事件e時列車l的前方車站向量；xd為車站位置向量；S(l，e)為進(jìn)站事件e時列車i所在的區(qū)間向量；V(l，S(l，e))為區(qū)間速度向量。

可見，基于列車進(jìn)站的事件轉(zhuǎn)移函數(shù)是將系統(tǒng)當(dāng)前所有區(qū)間運行列車到達(dá)其前方站的最小時間作為下1個事件的觸發(fā)時間，以此實現(xiàn)事件轉(zhuǎn)移。在此過程中，事件轉(zhuǎn)移函數(shù)需要能力檢測算法頻繁地回溯檢查有關(guān)列車的實時信息和沖突狀況，致使TAS策略的執(zhí)行效率低下。此外，對于辦理技術(shù)作業(yè)的停站列車，其最小作業(yè)時間段內(nèi)不存在與之相關(guān)的發(fā)車作業(yè)，故而可將這段時間予以忽略，以進(jìn)一步提高仿真效率。

針對基于列車進(jìn)站的事件轉(zhuǎn)移函數(shù)在實現(xiàn)系統(tǒng)狀態(tài)轉(zhuǎn)移過程中存在的不足，本文設(shè)計基于列車出站的事件轉(zhuǎn)移函數(shù)為

事件轉(zhuǎn)移函數(shù)中，式（17）和式（18）的作用是確定調(diào)整系統(tǒng)中滿足最小停站時間的待發(fā)列車所對應(yīng)的前探步長Δt，而式（16）則是選取間隔時間最小的步長Δt，并以此確定下1個出站事件的觸發(fā)時間。鑒于本文中的事件轉(zhuǎn)移函數(shù)是基于累計狀態(tài)變量而設(shè)計的，因此，一旦調(diào)整策略同時確定出無沖突的列車發(fā)車時間和到達(dá)時間，事件轉(zhuǎn)移函數(shù)便可直接將列車發(fā)車作為事件轉(zhuǎn)移的判斷依據(jù)，而無需重復(fù)檢查有關(guān)列車在區(qū)間運行和最小停站期間的實時信息和沖突狀況。

2.2 同級列車有限隨機調(diào)整策略

多級列車的差異性主要體現(xiàn)在列車運行時效性及其占用線路資源的優(yōu)先級上[18]。鑒于同等級列車間對線路資源占用具有相同的優(yōu)先級，在同等級列車調(diào)整時，本文借鑒文獻(xiàn)[19]中的并行策略，將事件轉(zhuǎn)移函數(shù)確定的時間t作為參考點，經(jīng)檢查并評價各區(qū)間所銜接的兩端車站內(nèi)的待發(fā)列車，確定當(dāng)前時刻各區(qū)間對應(yīng)的出發(fā)列車。在此過程中，由于不同的區(qū)間決策順序及發(fā)車順序產(chǎn)生的調(diào)整結(jié)果會有所不同，為提高調(diào)整系統(tǒng)的搜索能力，設(shè)計同級列車的有限隨機調(diào)整策略。

根據(jù)列車晚點評價值val(l)和區(qū)間評價值val(q)，設(shè)計同級列車有限隨機調(diào)整策略的具體步驟如下。

式中：εt(l)為經(jīng)驗庫中列車l∈φij在t時刻已占用或已釋放區(qū)間q的調(diào)整結(jié)果數(shù)量與經(jīng)驗庫中所有調(diào)整結(jié)果數(shù)量的比值。本文中經(jīng)驗庫為系統(tǒng)調(diào)整得出的可行解集合。

以上即為同等級列車的有限隨機調(diào)整策略。在調(diào)整過程中，涉及到的隨機策略采用輪盤賭法[20]，這樣既可以確保實時最優(yōu)解出現(xiàn)的概率，又能保證調(diào)度時域內(nèi)同級列車調(diào)整結(jié)果的多樣性，從而提高搜尋全局最優(yōu)解的能力。

2.3 多級列車分層隨機調(diào)整策略

當(dāng)調(diào)整系統(tǒng)中存在不同等級列車時，由于低等級列車一般不能越行高等級列車而使得沖突疏解變得較為困難，因此，同級列車的有限隨機調(diào)整策略不能直接應(yīng)用于多等級列車的運行調(diào)整問題。為尋求較為合理的越行站和會讓站，以滿足多等級列車共線運行條件下的越行規(guī)則，本文利用分層決策在預(yù)測越行站和會讓站等方面的優(yōu)勢[21]，對不同等級列車進(jìn)行差異化的調(diào)整。分層決策是指是把列車按其等級劃分成不同的層級r∈{1 ，2，…，R}，進(jìn)而利用同級列車有限隨機調(diào)整策略對各層級內(nèi)的列車進(jìn)行調(diào)整。很明顯，經(jīng)列車分層后，較高等級列車將優(yōu)先占用運行時間窗，進(jìn)而為較低等級列車的調(diào)整奠定基礎(chǔ)，而低等級列車的調(diào)整則是對高的等級調(diào)整結(jié)果的進(jìn)一步細(xì)化[22]。據(jù)此，在同級列車調(diào)整策略的基礎(chǔ)上，設(shè)計多級列車分層隨機調(diào)整策略，見圖1。

圖1 多級列車分層隨機調(diào)整策略Fig.1 Hierarchical randomstrategyadjustment of multi-class trains

圖1中，調(diào)整策略的最優(yōu)準(zhǔn)則為：若可行解集合中最優(yōu)計劃的目標(biāo)值val連續(xù)Nmax次優(yōu)于后續(xù)迭代所產(chǎn)生的可行解，則可行解集合中的最優(yōu)計劃即為滿足最優(yōu)準(zhǔn)則的調(diào)整計劃。顯然，Nmax越大，解的質(zhì)量越高，但調(diào)整策略的時效性較低，反之，Nmax越小，調(diào)整策略的時效性越高，但解的質(zhì)量相對較差。

3 實例分析

3.1 基礎(chǔ)數(shù)據(jù)

以某單線鐵路半自動閉塞區(qū)段為例，該區(qū)段內(nèi)共有10個車站，各車站內(nèi)到的發(fā)線數(shù)量見表1。給定調(diào)整時間范圍為t∈[ ]0，360，在該調(diào)整時間段內(nèi)，共涉及24趟列車。其中，列車等級及其初始晚點時間見表2，列車在各車站的技術(shù)作業(yè)類型見表3，初始列車運行圖見圖2。

表1 車站內(nèi)到發(fā)線數(shù)量Tab.1 Number of arrival and departure lines in the station

表2 列車等級及初始晚點時間Tab.2 Train rank and original time delay

表3 列車在各車站的技術(shù)作業(yè)類型Tab.3 Type of the technical operation of trains in each station

圖2 原始列車運行圖Fig.2 Plan of original train operation

假定車站技術(shù)作業(yè)時間不得低于圖定計劃時間的85%，r=1等級列車的區(qū)間運行時間不得超過圖定時間的15%，r∈{2 ，3}等級列車的區(qū)間運行時間不得超過10%。目標(biāo)函數(shù)中的權(quán)重值wr分別為w1=1，w2=0.6和w3=0.4。另外，給定調(diào)整策略中的最優(yōu)準(zhǔn)則為Nmax=80。

3.2 結(jié)果分析

根據(jù)上述基礎(chǔ)數(shù)據(jù)，結(jié)合本文設(shè)計調(diào)整系統(tǒng)及多級列車分層隨機調(diào)整策略，以PyCharm為開發(fā)環(huán)境，通過Python編程，調(diào)整策略共計迭代118次，得到調(diào)整過程的收斂圖見圖3。

圖3中，當(dāng)?shù)螖?shù)為37時得到滿足最優(yōu)準(zhǔn)則的調(diào)整結(jié)果，系統(tǒng)耗時約16.28 s，目標(biāo)函數(shù)值約為307.0 min。另外，圖3還給出了文獻(xiàn)[15]中TAS調(diào)整結(jié)果，其目標(biāo)函數(shù)值約為325.8 min，與本文設(shè)計的調(diào)整策略在第4次迭代時得出的結(jié)果一致。相比于TAS策略，本文設(shè)計的調(diào)整策略可以將解的質(zhì)量提高約5.77%。多級列車調(diào)整時，滿足最優(yōu)準(zhǔn)則的列車運行圖見圖4。

圖3 調(diào)整過程收斂圖Fig.3 Convergency of the adjustment process

圖4 多級列車調(diào)整后的列車運行圖Fig.4 Train-operation plan after adjusting multi-class trains

對比圖2和圖4可見，幾乎所有的r=1等級列車均能夠整點交出，而r∈{2 ，3}等級列車中，晚點比較明顯的列車有{4 ，14，2，3，7，12}，且大部分屬于r=3等級列車?？梢?，采用多級列車分層隨機調(diào)整策略時，列車的等級越高，調(diào)整效果越明顯。為進(jìn)一步分析分層調(diào)整策略對調(diào)整結(jié)果的影響，將所有列車置于同一等級，得到同級列車調(diào)整后的列車運行圖見圖5。

圖5 同級列車調(diào)整后的列車運行圖Fig.5 Train-operation plan after adjusting the same-class trains

如圖5所示的調(diào)整結(jié)果，其目標(biāo)函數(shù)值約為211.2 min。與圖4所示的調(diào)整結(jié)果相比，圖5中r∈{1 ，2}等級列車出現(xiàn)明顯晚點?？梢姡捎梅謱与S機調(diào)整策略能有效確保高等級列車的時效性，符合列車運行實際調(diào)整的需求，但需以犧牲低等級列車的時效性為代價，系統(tǒng)時效性損失約(3 07.0-211.2)/211.2≈45.3%。

為了分析系統(tǒng)中事件轉(zhuǎn)移函數(shù)對調(diào)整系統(tǒng)仿真效率的影響，給出系統(tǒng)內(nèi)各層級列車在調(diào)整過程中的離散步長Δt分別見圖6和圖7。

圖6 r=1等級列車調(diào)整過程中的離散時間步長Fig.6 Discrete-time step during adjusting which class r=1 trains

圖7 r∈{2 ，3}等級列車調(diào)整過程中的離散時間步長Fig.7 Discrete-time step during adjusting which class r∈{2 ，3} trains

可見，在分層調(diào)整過程中，調(diào)整r=1等級列車時的離散時間步長變化最明顯，而調(diào)整r=3等級列車時的離散步長變化最弱，說明較低等級列車因高等級列車干擾而長時間處于車站待發(fā)狀態(tài)，這是導(dǎo)致系統(tǒng)時效性損失的主要原因?？傮w而言，事件轉(zhuǎn)移函數(shù)在不影響調(diào)整結(jié)果的前提下能夠避免調(diào)整策略在區(qū)間運行時間和最小停站時間上的重復(fù)執(zhí)行，從而提高了調(diào)整策略的執(zhí)行效率。仿真結(jié)果表明，采用事件轉(zhuǎn)移函數(shù)時，平均每100次迭代的系統(tǒng)耗時約為42.18 s，但如果不采用事件轉(zhuǎn)移函數(shù)，則平均每100次迭代的耗時約為64.37 s?？梢?，本文設(shè)計的事件轉(zhuǎn)移函數(shù)可將調(diào)整系統(tǒng)的仿真效率提升約為34.47%。

考慮到不同等級列車的權(quán)重值wr對目標(biāo)函數(shù)值的影響，設(shè)w1=1為定值，取w2，w3∈[ ]0，1，得到不同w2和w3取值下的目標(biāo)函數(shù)值見圖8。

圖8 不同w2和w3取值下的目標(biāo)函數(shù)值Fig.8 Objective function values with different values of w2 and w3

圖8表明，目標(biāo)函數(shù)值與w2和w3的取值呈正相關(guān)，但是對w3取值更為敏感，說明在任意的wr=[1 ，w2，w3]組合下，滿足最優(yōu)準(zhǔn)則的調(diào)整結(jié)果中r=3等級列車的晚點情況最為嚴(yán)重。

調(diào)整策略中，列車評價函數(shù)val(l)中的列車到達(dá)晚點系數(shù)λ1和出發(fā)晚點系數(shù)λ2是根據(jù)實時待發(fā)列車集中的列車晚點狀況而確定的。為分析二者對調(diào)整結(jié)果的影響，給出不同λ1和λ2取值下目標(biāo)函數(shù)的平均值見圖9。

圖9 不同λ1和λ2取值下目標(biāo)函數(shù)的平均值Fig.9 Average value of an objective function under different values ofλ1 andλ2

圖9中，目標(biāo)函數(shù)平均值是指調(diào)整策略中可行解規(guī)模為300時的平均值?？梢?，調(diào)整結(jié)果對到達(dá)晚點更敏感，符合調(diào)整實際情況，因為出發(fā)晚點時間可通過減少區(qū)間運行時間來彌補，而車站作業(yè)則取決于列車到達(dá)狀況。因此，在列車運行調(diào)整過程中，應(yīng)盡量確保列車準(zhǔn)點到達(dá)。

4 結(jié)束語

針對單線鐵路半自動閉塞區(qū)段的多等級列車共線運行調(diào)整問題，構(gòu)建了考慮車站能力及技術(shù)作業(yè)類型等關(guān)鍵約束的離散系統(tǒng)仿真模型。通過分析既有TAS策略在列車運行調(diào)整過程中存在的不足，設(shè)計以列車出站為離散狀態(tài)標(biāo)志的事件轉(zhuǎn)移函數(shù)，并在此基礎(chǔ)上提出調(diào)整系統(tǒng)的同級列車有限隨機調(diào)整策略和多級列車分層隨機調(diào)整策略。通過算例分析驗證了離散系統(tǒng)仿真模型及其調(diào)整策略的有效性，結(jié)果分析表明，事件轉(zhuǎn)移函數(shù)和隨機調(diào)整策略對提高系統(tǒng)仿真的時效性和全局搜索能力具有很好的促進(jìn)作用，但分層策略在避免高等級列車出現(xiàn)嚴(yán)重晚點的同時，需以犧牲低等級列車的時效性為代價，且系統(tǒng)時效性損失明顯。此外，系統(tǒng)參數(shù)分析表明，相對于列車發(fā)車晚點，系統(tǒng)對列車到達(dá)晚點更為敏感。

本文中，分層策略僅從列車等級的角度展開，若從列車運行圖結(jié)構(gòu)及晚點程度對列車分層，其調(diào)整結(jié)果更具綜合性，將是下一步研究的重點。