針對發(fā)車延遲的列車運行圖加線模型構建及實證

王鍇楷，何世偉，蘭澤康，馮 驍

（北京交通大學 交通運輸學院，北京 100044)

0 引言

列車運行圖規(guī)定了鐵路運輸生產中列車在區(qū)間運行以及在各個車站到發(fā)或者通過的具體時刻，是鐵路系統(tǒng)組織列車運行的基礎。貨運班列作為一種固定車次、線路的運輸形式，在運行圖上表現為到發(fā)時刻相對固定的運行線，具有運輸效率高、經濟效益好的優(yōu)點。然而，在實際運營過程中，由于集結過程存在一定隨機因素，可能會出現在規(guī)定的時刻無法完成貨物集結，繼而影響貨物作業(yè)、編組作業(yè)，最終影響貨運班列出發(fā)時間的情況。因此，對于因貨物集結、場站作業(yè)等因素而無法按圖定時刻出發(fā)的貨運班列，可以在其滿足發(fā)車條件的時間點后，以不影響其他列車正常運行為前提，在列車運行圖上鋪畫一條新的運行線，提高貨物送達的時效性。

目前，針對列車運行圖已經有很多研究。Tan[1]通過構造事件活動圖研究運行圖結構，建立運行圖加線模型。李建等[2]以各列車在途中停留時間加權值的總和最小化為優(yōu)化目標，建立直達列車運行線選擇的0-1整數規(guī)劃模型，采用粒子群算法對模型進行優(yōu)化求解。徐涵等[3]考慮周期結構和靈活接續(xù)等約束條件，構建基于靈活接續(xù)的列車運行圖加線模型，實現列車“周期+非周期”運行圖鋪畫的綜合優(yōu)化。劉敏[4]針對列車與客流協調性問題，建立增開本線列車模型，實現輸送能力優(yōu)化配置。張小炳等[5]以車流在途運輸時間最小為優(yōu)化目標，構建基于貨物運到期限的列車運行線選擇0-1整數規(guī)劃模型，采用模擬退火算法求解。周浩然[6]針對鐵路系統(tǒng)特定區(qū)間的擾動情況，采用混合整數規(guī)劃模型實現臨時待避方案的生成。江峰等[7]構造時空網絡將列車運行圖鋪畫轉化為路徑搜索問題，通過啟發(fā)式算法求解。郭一唯等[8]以運行時間、追蹤時間、停站時間等作為約束條件，建立以運行圖均衡性為優(yōu)化目標的決策模型。

然而，這些研究針對旅客列車運行圖調整較多，對于貨物列車尤其是貨運班列的運行圖調整較少，需要針對實際運營中存在的列車發(fā)車延遲問題，構建列車運行圖加線模型優(yōu)化原運行圖，并通過實際算例進行驗證。

1 針對發(fā)車延遲的列車運行圖加線模型構建

1.1 問題描述

為了直觀地描述運行圖中的各要素以及要素之間的關聯關系，這里采用事件和活動來表示運行圖結構。其中，所有列車的到達與出發(fā)事件統(tǒng)稱為事件，而連接事件的聯弧則稱為活動，由此可以得到由事件與活動構成的運行圖網絡G= (E，A)。

E表示事件集合。事件分為2類，一是原圖事件Eori，表示原定的運行圖，具體標定了原計劃中各列車的運行時刻。二是加線事件Eadd，表示調整后的運行圖，確定新加的運行線的各個時刻。

A表示活動集合，A= {(i，j) |i，j∈E}，按照類型分為以下4類：①旅行弧。連接同一列車的發(fā)車事件與到達事件，其中Aoritrip為原圖旅行弧，Aaddtrip為加線旅行弧。②安全間隔弧。Aint為安全間隔弧，連接同一個車站相鄰的2個到達事件或者出發(fā)事件，表示在同一個車站任何屬于不同列車的相鄰2個到達事件與出發(fā)事件之間必須保持一定時間間隔。③停站弧。Adwell為停站弧，連接同一列車在某站的到達事件與出發(fā)事件，表示對于有停車需求的列車在特定的車站進行停車作業(yè)的過程。④延遲弧。連接需要進行調整的運行線在起始站的原發(fā)車事件和新發(fā)車事件，以及在終到站的原到達事件和新到達事件。其中，原發(fā)車事件與原到達事件均屬于原圖事件Eori，新發(fā)車事件與新到達事件均屬于加線事件Eadd。設定Adeplag為出發(fā)延遲弧，Aarrlag為到達延遲弧。

運行圖網絡示意圖如圖1所示。

為了使模型更加簡潔，提出以下2點基本假設：①除了需要調整的列車運行線，其他運行線不作調整。②對運行線進行調整時，可根據需求在任何車站進行停車作業(yè)。

1.2 模型構建

以最小化總延遲時間為目標函數，兼顧總體和局部的運到期限要求，構建針對發(fā)車延遲的列車運行圖加線模型，具體如下。

圖1 運行圖網絡示意圖Fig.1 Train operation diagram network

式中：(i，j)表示連接事件的聯弧，(i，j)∈A，i是聯弧的起點，j是聯弧的終點，i，j∈E；dmina和dmaxa分別為停站弧a的最小停站時間和最大停站時間，min；tmina和tmaxa分別為旅行弧a的區(qū)間最小旅行時間和區(qū)間最大旅行時間，min；ha表示安全間隔弧a的安全間隔時間，min；ti，tk，tl分別表示原圖中事件i，k，l發(fā)生的時間點，其中i，k，l∈Eori；pa表示需要調整的列車相比原定的發(fā)車時間延遲的時間，其中a∈Adeplag，min；qi表示需要調整的列車在原運行圖中的終到事件與運到期限之間的冗余值，其中i∈Eori，min；決策變量xi，xj分別表示調整后的列車事件i，j發(fā)生的時間點，其中i，j∈Eadd。

公式 ⑴ 為模型的目標函數，表示所有調整后的列車相對于原圖最終到達終點站的總延遲時間最??；公式 ⑵ 為列車的出發(fā)時間約束，表示需要調整的列車在起點站的出發(fā)時間必須晚于列車整備完畢的時間；公式 ⑶ 為列車的旅行時間約束，表示列車在各個區(qū)間的運行時間必須處于該區(qū)間的最小運行時間與最大運行時間之間，從而保證列車在合理的速度范圍內運行；公式 ⑷ 為列車的停站時間約束，表示列車在車站的停站作業(yè)時間必須滿足作業(yè)標準；公式 ⑸ 為列車的安全間隔時間約束，表示對于不同列車在同一個車站的同類型事件必須在時間上保持一定安全間隔，這里考慮到技術站到達場與出發(fā)場一般不存在作業(yè)沖突，可同時進行到達作業(yè)與發(fā)車作業(yè)，因此對發(fā)—到和到—發(fā)事件之間的時間間隔不做限制；公式 ⑹ 為列車的區(qū)間越行約束，其中(i，j)與(k，l)表示位于同一個區(qū)間屬于不同列車的2條旅行弧，如果出發(fā)事件i的發(fā)生時間晚于出發(fā)事件k，則i對應的到達事件j的發(fā)生時間也晚于與k對應的到達事件l，反之同理，從而保證任何區(qū)間都不會發(fā)生列車越行現象；公式 ⑺ 為貨物運到時限約束，表示每列列車調整后到達終點站的時間都不可超過運到期限，在局部保證運到期限；公式 ⑻ 為決策變量的邏輯約束。

針對發(fā)車時間延遲的列車運行圖加線模型為整數規(guī)劃模型，可以采用分支定界法獲得精確解。

2 實證分析

（1）線路選擇。以中歐班列西通道重要運行線路鄭州—阿拉山口為例，涉及沿途8個重要技術站，包括鄭州北站(A)、新豐鎮(zhèn)站(B)、蘭州北站(C)、武威南站(D)、嘉峪關站(E)、哈密東站(F)、烏西站(G)以及阿拉山口(H)。線路示意圖如圖2所示。

圖2 線路示意圖Fig.2 Route structure

（2）運行圖信息。將列車S1的出發(fā)時刻設定為時間原點，記為0，其余時間點以此為原點進行推算，以距離此原點的分鐘數表示，單位為min，可以得到原運行圖信息如表1所示。運行圖示意圖如圖3所示，共涉及15列列車。

表1 原運行圖信息Tab.1 Original train operation diagram information

（3）運行線調整信息。列車S1與S9是服務于A—H的貨運班列，由于在貨物集結過程中發(fā)生時間延誤，因此需要延遲從A站出發(fā)的時間。運行圖調整信息如表2所示。

表2 運行圖調整信息Tab.2 Train paths alteration information

（4）運行圖網絡構建。以線路中的車站E(嘉峪關站)為例，新增的列車運行線會在本站產生新的到達事件與出發(fā)事件，兩者之間建立停站弧。新增的到達事件與原圖中屬于其他列車運行線的本站到達事件一一建立安全間隔弧，同樣地，新增的出發(fā)事件與其他列車運行線的本站出發(fā)事件一一創(chuàng)建安全間隔弧。特別的，在起點站與終點站，原發(fā)車事件和新發(fā)車事件以及原到達事件和新到達事件之間分別建立延遲弧。至此，運行圖網絡構建完成。運行圖網絡示意圖如圖4所示，將其簡化為網絡結構圖，網絡結構示意圖如圖5所示。

圖4 運行圖網絡示意圖Fig.4 Train operation diagram network

圖5 網絡結構示意圖Fig.5 Network structure

（5）模型參數設定。設定最小停站時間20 min，最大停站時間180 min，區(qū)段旅行時間如表3所示。對于從A—H的貨運班列，運到期限為4 320 min。

表3 區(qū)段旅行時間 minTab.3 Trip time of sections

對針對發(fā)車延遲的列車運行圖加線模型進行求解，采用以上實例，可以得到調整后列車時刻表如表4所示。相比較于原計劃，列車S1的出發(fā)時間點調整為146 min，為避免與其他列車沖突，在C站停留144 min，最終在3 521 min到達H站，相比于原運行圖推遲300 min；列車S9的出發(fā)時間點調整為541 min，最終在3 852 min到達H站，相比于原運行圖推遲221 min。根據模型優(yōu)化的結果，調整后的總延遲時間為521 min，并且2列列車調整后均未超出各自的運到期限。結果表明，針對發(fā)車延遲的列車運行圖加線模型可快速有效地提供特殊狀況下的列車運行圖臨時調整方案，驗證了模型的有效性和可行性。

表4 調整后列車時刻表Tab.4 Train paths after adjustment

3 結束語

實際運營存在由于外界因素影響使得貨運班列無法按原計劃發(fā)車的情況，研究基于不影響其他列車正常運行的前提，充分考慮列車的運行特點以及貨運的時效性要求，采用加線模型實現列車運行圖調整的綜合優(yōu)化。通過實證驗算結果表明，該模型能夠同時兼顧宏觀的調整量最小和微觀的時效性最優(yōu)，在較短時間內生成運行線的調整方案，可以為鐵路運營部門提供輔助決策。但是，該模型僅僅針對單一班列考慮，沒有考慮列車之間的接續(xù)關系，還應進一步考慮對其他貨物列車的影響進行綜合優(yōu)化。