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

（北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044)

0 引言

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

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

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

1 針對(duì)發(fā)車延遲的列車運(yùn)行圖加線模型構(gòu)建

1.1 問題描述

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

E表示事件集合。事件分為2類，一是原圖事件Eori，表示原定的運(yùn)行圖，具體標(biāo)定了原計(jì)劃中各列車的運(yùn)行時(shí)刻。二是加線事件Eadd，表示調(diào)整后的運(yùn)行圖，確定新加的運(yùn)行線的各個(gè)時(shí)刻。

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

運(yùn)行圖網(wǎng)絡(luò)示意圖如圖1所示。

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

1.2 模型構(gòu)建

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

圖1 運(yùn)行圖網(wǎng)絡(luò)示意圖Fig.1 Train operation diagram network

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

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

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

2 實(shí)證分析

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

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

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

表1 原運(yùn)行圖信息Tab.1 Original train operation diagram information

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

表2 運(yùn)行圖調(diào)整信息Tab.2 Train paths alteration information

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

圖4 運(yùn)行圖網(wǎng)絡(luò)示意圖Fig.4 Train operation diagram network

圖5 網(wǎng)絡(luò)結(jié)構(gòu)示意圖Fig.5 Network structure

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

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

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

表4 調(diào)整后列車時(shí)刻表Tab.4 Train paths after adjustment

3 結(jié)束語

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