張 琴，朱曉寧，王 力，商 攀

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

高速鐵路(以下簡稱“高鐵”)多條線路相交時，傳統(tǒng)列車運行圖鋪畫采用“先單獨鋪畫每條線路，再協(xié)調(diào)車站到發(fā)線分配”的方法.隨著高鐵不斷建設(shè)，線路交叉頻率越來越大，銜接樞紐站的車站通過能力成為限制路網(wǎng)通過能力的瓶頸，多線路列車運行圖在銜接樞紐站的協(xié)調(diào)問題 “牽一發(fā)而動全身”，獲得高效可行的列車運行圖愈加困難.考慮車站到發(fā)線和咽喉區(qū)資源，同時編制列車運行圖和到發(fā)線分配方案能夠更好地協(xié)調(diào)多線路、多車站資源利用，具有重要研究意義.

編制列車運行圖和到發(fā)線分配方案是鐵路運輸組織的經(jīng)典問題，既有研究主要將兩類問題單獨求解及優(yōu)化[1-2].針對列車運行圖編制問題，大多數(shù)學者基于宏觀角度，將鐵路運輸網(wǎng)絡(luò)劃分為區(qū)間和車站兩部分[3]，Zhang等[4]建立了高鐵周期列車運行圖優(yōu)化模型，車站主要考慮到發(fā)線數(shù)量約束，未涉及車站內(nèi)部結(jié)構(gòu)及具體到發(fā)線分配，假設(shè)列車上下行獨立運行，互不干擾.擾動情況下調(diào)整優(yōu)化列車運行圖通常以閉塞分區(qū)或者軌道區(qū)段為最小研究單位，造成決策變量的增加，對求解算法提出了極高的要求[5-6].為了解決到發(fā)線分配問題，大多數(shù)學者通過建立不同的多目標規(guī)劃模型進行優(yōu)化[7-8]，其中部分學者并未考慮車站咽喉區(qū)資源利用情況[9-10]，喬瑞軍等[11]假設(shè)上下行系統(tǒng)相互獨立，但成網(wǎng)條件下不同方向列車在銜接樞紐車站相互干擾，無法分解.

針對高鐵成網(wǎng)條件下，考慮車站到發(fā)線和咽喉區(qū)資源利用的多線路列車運行圖協(xié)同編制方法的研究尚不多見.本文作者基于靈活使用到發(fā)線的規(guī)則，提出區(qū)間-咽喉區(qū)-到發(fā)線三段式列車運行圖編制框架，從中觀角度，構(gòu)建基于時空網(wǎng)絡(luò)的高鐵列車運行圖和到發(fā)線分配方案協(xié)同編制0-1整數(shù)規(guī)劃模型，編制多線路、多車站的列車運行計劃，并使用整數(shù)規(guī)劃商業(yè)求解器CPLEX進行模型求解.算例結(jié)果驗證了模型的有效性，同時表明中觀層面建模既能夠考慮到發(fā)線的具體分配，又能夠有效降低模型規(guī)模.

1 問題描述

1.1 列車運行圖和到發(fā)線分配問題

列車運行圖規(guī)定了各列車在物理網(wǎng)絡(luò)中的運行路徑以及在各車站等關(guān)鍵節(jié)點的到、發(fā)和通過時刻.編制過程中，通常將車站視為一個具有到發(fā)線數(shù)量約束的點，不考慮車站資源的利用，將兩站之間的區(qū)間線路視為一個整體，同時，上下行列車通常單獨規(guī)劃，互不干擾.

到發(fā)線分配問題通常以列車運行圖為輸入，將其規(guī)定的當前車站所有列車合理地分配到到發(fā)線上，使其進路無沖突且滿足各項安全技術(shù)要求[8].因此，到發(fā)線分配問題不僅要考慮到發(fā)線資源，還應考慮咽喉區(qū)資源.

列車運行圖編制和到發(fā)線分配是密不可分的，傳統(tǒng)分步式編制方法生成的列車運行圖可能無法生成可行的到發(fā)線分配方案，需要重新進行列車運行圖的調(diào)整，并重復循環(huán)該過程直至兩類方案均可行.

1.2 協(xié)同編制時空網(wǎng)絡(luò)構(gòu)建

為了考慮車站咽喉區(qū)占用和到發(fā)線的具體分配，將列車運行圖傳統(tǒng)的區(qū)間-車站的宏觀圖形表示方法重構(gòu)成區(qū)間-車站咽喉區(qū)-車站到發(fā)線的中觀圖形表示模式，構(gòu)建如圖1左側(cè)所示的物理網(wǎng)絡(luò).從中觀角度將高速鐵路運輸網(wǎng)絡(luò)中的車站劃分出到發(fā)線資源，而區(qū)間線路保持為一個整體.高鐵物理網(wǎng)絡(luò)由點和邊構(gòu)成，其中點主要用來表示列車進站點(圖1左側(cè)點1、8)、列車出站點(圖1左側(cè)點2、7)、車站中心線所在的各到發(fā)線上的點(圖1左側(cè)點3—6)以及列車在區(qū)間需要進行徑路選擇的關(guān)鍵性節(jié)點(區(qū)間正線和聯(lián)絡(luò)線的交點)，邊用來表示銜接兩個點的線路.

圖1 高鐵時空網(wǎng)絡(luò)示意圖Fig.1 Space-time network diagram for high-speed railway

高鐵時空網(wǎng)絡(luò)由點和時空弧構(gòu)成，見圖1右側(cè).其中，時空網(wǎng)絡(luò)中的點是物理網(wǎng)絡(luò)中的點在時間上的拓展，時空弧包括區(qū)間運行弧、咽喉區(qū)運行弧和到發(fā)線等待弧三類，分別表示列車在區(qū)間、咽喉區(qū)和到發(fā)線上的時空軌跡.根據(jù)列車運行方向，區(qū)間運行弧和咽喉區(qū)運行弧可以進一步劃分為上行運行弧和下行運行弧兩類；根據(jù)作業(yè)類型，咽喉區(qū)運行弧可以分為進站運行弧和出站運行弧兩類；根據(jù)進路是否切割正線，咽喉區(qū)運行弧可以分為一般運行弧和反向占用運行弧.

給定帶有沖突的理想列車運行圖，為了生成無沖突、安全的基本列車運行圖，假定鐵路旅客運輸計劃編制部門可采取以下調(diào)整措施：①延遲列車在起點的理想發(fā)車時間；②延長列車在車站到發(fā)線上的停留時間；③調(diào)整車站到發(fā)線分配方案；④取消列車.為了表示列車在起點的延遲和取消，本文同時引入了列車起點等待弧和列車虛擬運行路徑.

2 協(xié)同編制模型的建立與求解

2.1 模型假設(shè)

模型假設(shè)如下：

① 理想列車運行圖(有沖突)、線路運行(包括安全間隔時間)等基本資料已知；

②列車在起點的允許調(diào)整時間窗長度以及在各車站的最小、最大停站時間給定；

③ 車站咽喉區(qū)道岔同時解鎖，同一列車在車站咽喉區(qū)的接、發(fā)車進路走行時間相同；

④ 列車的長度忽略不計；

⑤ 時間精度為1 min.

2.2 模型的構(gòu)建

(1)

單一列車徑路的時空網(wǎng)絡(luò)流平衡約束條件為

(2)

(3)

列車在車站的最小和最大停站時間約束為

?f∈F,?k∈Kf

(4)

安全間隔約束條件是列車運行圖編制和到發(fā)線分配問題的復雜約束條件，主要包括區(qū)間安全間隔約束、車站咽喉區(qū)進路安全間隔和到發(fā)線使用安全間隔約束.

區(qū)間安全間隔約束包括接、發(fā)車安全間隔兩類約束，假設(shè)Ta、Td分別表示接、發(fā)車安全間隔時間，對于任意的時空點v∈Vd∪Vse，定義其發(fā)車不兼容弧集為

對于任意的時空點v∈Va∪Vse，定義其接車不兼容弧集為

任一不兼容弧集中的所有時空弧僅可被一列列車占用，因此，區(qū)間安全間隔約束為

(5)

(6)

則對于所有車站從同一進站點接入或者從同一發(fā)車點發(fā)出的列車應滿足的咽喉區(qū)進路安全間隔約束條件為

(7)

(8)

圖2 車站接車進路沖突及發(fā)車進路沖突示意圖Fig.2 Schematic diagram of receiving-receiving and departure-departure conflicts

為了避免圖2中接車進路之間以及發(fā)車進路之間的沖突，對于銜接多線路的車站，其咽喉區(qū)不同起點接車、不同終點發(fā)車安全間隔約束條件為

(9)

(10)

(11)

因此，車站到發(fā)線安全間隔約束可轉(zhuǎn)化為任意到發(fā)線等待弧最多能被一列列車實際占用或者隱含占用，約束式為

?g∈Ast

(12)

2.3 模型求解

中觀層面時空網(wǎng)的合理構(gòu)建，不僅減少了決策變量個數(shù)，同時也減少了一定數(shù)量的約束條件，主要包括：①車站正線通過約束[11]；②到發(fā)線占用唯一性約束[12].

各類不兼容弧集合或者不兼容邊集合的構(gòu)建，能夠?qū)崿F(xiàn)對復雜安全約束條件的預處理，方便了復雜安全約束條件的構(gòu)建，使得本文能夠直接采用CPLEX12.9 對模型進行求解.

3 算例研究

高速鐵路路網(wǎng)示意圖見圖3.圖3中有兩條高鐵線路，3個車站，中觀線路物理網(wǎng)絡(luò)共37個點，75條邊，研究時長為100 min，研究列車共44列，區(qū)間正線各段運行時間為4 min，聯(lián)絡(luò)線運行時間為2 min，車站1進路走行時間為2 min，車站2、3進路走行時間為1 min.

3.1 中、微觀層面下構(gòu)建網(wǎng)絡(luò)的規(guī)模對比

假設(shè)圖3中微觀層面區(qū)間單方向閉塞分區(qū)個數(shù)為10個，每個車站咽喉區(qū)列車徑路選擇點為軌道區(qū)段的起訖點.從中觀和微觀層面構(gòu)建圖3的線路物理網(wǎng)絡(luò)的規(guī)模對比見表1.由表1可見，相較于微觀層面構(gòu)建的網(wǎng)絡(luò)規(guī)模，從中觀層面構(gòu)建網(wǎng)絡(luò)使得點的數(shù)量減少了70%以上，邊的數(shù)量減少了75%以上，很大程度上減少了模型的決策變量個數(shù).

圖3 高速鐵路路網(wǎng)示意圖Fig.3 Schematic diagram of high-speed railway network

表1 中、微層面構(gòu)建線路物理網(wǎng)絡(luò)的規(guī)模對比Tab.1 Comparison of the railway network scale from microscopic and macroscopic perspectives

3.2 列車數(shù)量同求解時間的變化

假設(shè)列車在起點的出發(fā)時間窗長度為5 min，停站列車最小停站時間為1 min，停站時間范圍為4 min(即最大停站時間和最小停站時間的差值)，不同列車數(shù)量下求解時間對比見表2.由表2可以看出，隨著列車數(shù)量的增加，求解時間整體呈現(xiàn)出增長的趨勢，但是所有場景仍然能夠在較短的時間內(nèi)求得最優(yōu)解.

表2 不同列車數(shù)量下求解時間對比Tab.2 Comparison of solution time under different train numbers

場景2-9下不同車站區(qū)段列車運行圖見圖4.由圖4可見，車站1、2區(qū)段以及車站1、3區(qū)段的最優(yōu)列車運行圖和到發(fā)線分配方案均滿足各項安全技術(shù)作業(yè)需要，驗證了模型的有效性.相較于已知的有沖突存在的理想列車運行圖，有3列列車取消.

圖4 場景2-9下不同車站區(qū)段列車運行圖Fig.4 Train operation diagram for different station sections under scenarios 2-9

3.3 列車路徑規(guī)模同求解時間的變化

對于每列列車的可行路徑規(guī)模主要取決于列車起點出發(fā)時間窗長度和停站時間范圍兩個因素，兩種因素的改變對模型求解時間有不同的影響，不同列車路徑規(guī)模下求解時間對比見表3.設(shè)定兩種環(huán)境，環(huán)境一下列車停站時間范圍相同，其他條件保持不變，共5種場景(3-1至3-5)；環(huán)境二下改變車站停站時間范圍，其他條件同樣保持不變，共5種場景(3-2、3-6至3-9).由表3可以看出，在環(huán)境一下，求解時間隨著起點時間窗長度的增長，整體呈現(xiàn)增長的模式，且變化較大；在環(huán)境二下，求解時間隨著停站時間范圍的增加，幾乎保持不變.

表3 不同列車可行路徑規(guī)模下求解時間對比Tab.3 Comparison of solution time under different train feasible path numbers

4 結(jié)論

在列車運行圖編制過程中考慮車站到發(fā)線的具體分配及咽喉區(qū)資源的占用，研究了多線路列車運行圖和多車站到發(fā)線分配協(xié)同編制問題.通過設(shè)計算例，比較了不同影響因素對模型求解時間的影響，驗證了模型有效性.本文直接使用CPLEX方法求解對于中小規(guī)模問題有效，大規(guī)模問題下，研究更加快速有效的求解算法是今后的重點工作.具體結(jié)論如下：

1)中觀層面高速鐵路網(wǎng)絡(luò)的構(gòu)建，相較于宏觀層面能夠具體考慮車站資源利用情況，相較于微觀層面網(wǎng)絡(luò)規(guī)模能夠減少70%以上，很大程度上減少了決策變量個數(shù).

2)模型求解時間同列車數(shù)量和列車可行路徑規(guī)模整體呈正相關(guān)，可行路徑中，列車起點時間窗長度影響較大，車站停站時間范圍影響相對較小.