高鐵夕發朝至列車開行與天窗設置協同優化

2021-07-25 06:15:52徐長安李晟東李斯涵倪少權

西南交通大學學報 2021年4期

徐長安，李晟東，李斯涵，倪少權 ,2,3

（1.西南交通大學交通運輸與物流學院，四川成都 610031；2.西南交通大學綜合交通運輸智能化國家地方聯合工程實驗室，四川成都 610031；3.西南交通大學綜合交通大數據應用技術國家工程實驗室，四川成都 610031）

高速鐵路夕發朝至列車是我國鐵路部門為滿足部分地區間旅客的夜間出行需求，在普速鐵路夕發朝至列車基礎上發展而來的一種客運產品，通常是指當日19∶00—23∶00 始發，次日06∶00—10∶00 終到，總在途時間7～15 h 的高速動車組列車.由于高速鐵路夕發朝至列車的開行需要占據運行圖中的夜間運行時分，會與天窗設置產生沖突，使得高鐵夕發朝至列車開行計劃編制難度很大.隨著高速鐵路夕發朝至客流的不斷增長，實現高速鐵路夕發朝至列車開行的網絡化與日常化，是順應鐵路客運市場發展的必然趨勢.在這種背景下，如何選擇高速鐵路夕發朝至列車開行模式，并實行天窗與高速鐵路夕發朝至列車的協同優化，是今后高速鐵路夕發朝至列車品牌發展所面臨的重要問題.

許多學者從不同視角分析和研究了高速鐵路夕發朝至列車開行與天窗設置協調優化問題，并取得了許多有意義的成果.趙麗珍等[1]以京滬高速鐵路天窗方案設置為例，首次系統闡釋了高速鐵路列車開行方案與天窗的協調優化問題.朱健梅等[2]深入研究了客運專線夕發朝至列車合理開行時間域與天窗方案的協調優化問題，并指出單向隔日矩形天窗是我國客運專線天窗設置的較優方案.聶磊等[3]在分析客運專線矩形天窗開設與夜間行車相互影響的基礎上，建立線性規劃模型求解最佳矩形天窗位置.楊奎等[4]通過分析高速鐵路綜合維修天窗與夜間運行列車之間的動態影響關系，構建了天窗設置與夜間列車開行的協同優化模型.李博[5]研究了成網條件下高速鐵路夕發朝至列車開行方案編制關鍵問題，提出了等天窗模式下的高速鐵路夕發朝至列車開行方案編制理論與方法.Zhang 等[6]基于通道型高速鐵路提出了列車運行方案與天窗設置的一體化編制模型.徐長安等[7]設計了基于優化進程分層的兩階段算法，求解天窗與列車運行圖協同優化問題.

然而，既有研究多是基于列車開行模式已知情況，少有研究考慮列車開行模式未定情形下天窗設置與列車運行圖的協同優化.本文以通道型高速鐵路為研究對象，引入狀態變量來刻畫不同類型列車開行模式，進而構建了高速鐵路夕發朝至列車開行與天窗設置協同優化模型，設計了基于自適應大鄰域搜索的啟發式求解算法，最后以京廣高速鐵路夕發朝至列車開行與天窗設置為例，驗證了模型算法的有效性.

1 問題描述和參數說明

目前，我國高速鐵路夕發朝至列車主要有3 種開行模式：等線模式、下線模式和下線-上線模式[8].等線模式是指夕發朝至列車始終在高速鐵路上運行，遇到天窗則在車站待避，等天窗結束后繼續運行.下線模式指夕發朝至列車在高速鐵路運行一段距離后，為了避開天窗，轉線至平行普速鐵路繼續運行，直至結束.下線-上線模式是指夕發朝至列車在高速鐵路上運行一段時間后，為了避開天窗，轉線至平行普速鐵路運行，等天窗結束后，又從普速鐵路轉線至高速鐵路繼續運行的過程.圖1 給出了3 種天窗開設模式在時空網絡圖中的對應表示，圖中：s1～s7為車站；i1、i2為高鐵夕發朝至列車；圖中實線表示在高速鐵路上運行，虛線表示在普速鐵路上運行，陰影部分表示天窗.由于高速鐵路列車轉線至普速鐵路運行后，運行速度不能超過普速鐵路設計速度，因此，圖1 中虛線的斜率小于實線的斜率.

圖1 高速鐵路夕發朝至列車開行模式Fig.1 Overnight train operation modes of high-speed railways

高速鐵路夕發朝至列車與天窗協同優化主要解決兩個層面的問題：一是根據線路條件與線路能力利用情況，確定選擇何種類型的高速鐵路夕發朝至列車開行模式.二是在選定列車開行模式后，如何安排天窗與列車在列車運行圖中的位置，使得天窗對列車運行的影響最小.因此，高速鐵路夕發朝至列車與天窗協同優化本質上是一個包含多變量多約束的組合優化問題.建模涉及的參數及變量定義如下：

1）常量.S為研究運輸通道上所有車站集合，S=SG∪SP，SG和SP分別為高速鐵路車站集合和普速鐵路車站集合.在運輸通道內，部分高速鐵路車站和普速鐵路車站通過聯絡線相連，具備高速鐵路列車轉線的可能，定義這類車站為關鍵車站，記為SK.IG、IP分別為高速鐵路列車集合與普速鐵路列車集合.IX、IR分別為高速鐵路夕發朝至列車集合和高速鐵路日間開行列車集合，則有IX?IG，IR?IG.ti(s,s+1)為列車i在區間 (s,s+1) 的運行時間，s為車站.Δta,a、Δtd,d、Δta,d和 Δtd,a分別為同方向列車同時到達、同時發車、不同時到發和不同時發到最小間隔時間[7].δs為車站s的到發線數目.zi,s為列車i在車站s的最小停站時間.分別為列車i在車站s的合理出發時間范圍、合理到達時間范圍.設DG={D1,D2,···,Dn} 為高速線路的n個天窗分段的集合，當n=1 時表示開設全線垂直矩形天窗.天窗分段可以用車站集合表示，出現在相鄰兩個天窗分段中的車站稱為相鄰天窗分段的分界站，分界站必屬于關鍵車站.對任意的Dj，Dj+1∈DG，當=1時，Dj和Dj+1為相鄰天窗分段，該車站為Dj和Dj+1的分界站.τb,j、τe,j分別為天窗分段Dj對應的天窗最早開始時間和最晚結束時間.Tm為天窗開設時長，ΔTm,b、ΔTm,e分別為天窗開始前和天窗結束后安全間隔.ζ 為足夠大的正數.

2）狀態變量.ρi,s表示當列車運行線與天窗發生沖突時，列車i在高速鐵路線路上是否從車站s運行到車站s+1，取值1 表示是，取值0 表示否.表示當列車運行線與天窗發生沖突時，列車i在車站s是否等線，取值1 表示是，取值0 表示否.表示當列車運行線與天窗發生沖突時，列車i是否從車站s轉到普速鐵路運行，取值1 表示是，取值0表示否.=1 表示在列車運行線與天窗發生沖突時，列車i在車站s是否從普速鐵路轉到高速鐵路線運行，取值1 表示是，取值0 表示否.xi,s為列車i在車站s是否停站，取值為1 表示停站，反之表示通過.

3）決策變量.ti,s,c、ti,s,d分別為列車i在車站s的出發時間、到達時間.Tm,j為第j個天窗分段對應的天窗開設時段.tj,b，tj,e分別為第j個天窗分段對應的天窗開始時間和結束時間，則Tm,j=[tj,b,tj,e].vi1,i2,s表示列車i1是否比列車i2更早從車站s出發，取值1 表示是，取值0 表示否.

2 模型構建

2.1 模型假設

本文研究基于以下前提進行：

1）高速鐵路夕發朝至列車開行方案、停站方案以及各類作業時間標準均已知；

2）高速鐵路在夜間00∶00—06∶00 開設分段矩形天窗，天窗分段劃分情況視為已知條件；

3）高速鐵路線路各個天窗分段時長相同，且各個天窗分段時長具有整體性，不能分割；

4）由于普速鐵路天窗設置比較靈活，在夕發朝至列車下線運行時，不考慮對普速鐵路天窗的影響；

5）相較于列車運行時間，夕發朝至列車通過銜接站下線或者上線都時間都很短，可忽略不計；

6）考慮高速鐵路夕發朝至列車的到發時間段，設定本文研究時間范圍為[19∶00，10∶00].

2.2 約束條件

1）列車合理到發時刻約束

為給旅客出行提供最大便利，夕發朝至列車在始發站的出發時間和在終到站的到達時間，以及在中間大站的到發時間均應處在合理時間范圍內[7]，表示為式（1）、（2）所示.

2）區間運行時分約束

夕發朝至列車i在車站s與車站s+1 構成區間的運行時分等于列車到達車站s+1 的時間與列車從車站s出發的時間之差[7]，如式（3）所示.

3）列車停站時間約束

夕發朝至列車在車站的停站時間不能小于規定的最小停站時間要求[5,7]，如式（4）所示.

4）列車間隔時間約束

夕發朝至列車在車站的到達、出發以及通過均需滿足一定的時間間隔要求[7]，如式（5）～（9）所示.

5）車站能力約束

在任意時刻t，車站被占用的到發線數量不能超過該站到發線能力[5].則車站到發線能力約束為

式中：i∈IX，s∈S；ω(ti,s,d,t) 和ω(ti,s,c,t) 為0-1 變量，分別表示車站s的到發線在時刻t是否被列車占用，取1 表示被占用，反之表示未被占用，具體定義如式（11）、（12）所示.

6）列車運行與天窗安全間隔約束

對天窗分段Dj，其天窗開始時刻和結束時刻均需與列車運行保持一定的安全間隔[7]，以確保行車安全，如式（13）、（14）所示.

式（13）、（14）中：i∈IX,j∈{1,2,···,n} ,s∈SG.

7）天窗時間范圍約束

天窗開設需滿足一定的時間范圍要求[7]，如式（15）、（16）所示.

式（15）、（16）中：j∈{1,2,···,n}，s∈SG.

式（15）表示天窗分段Dj的開設需在規定的天窗最早開始時間和最晚結束時間內.式（16）表示天窗結束時間等于天窗開始時間與天窗時長之和.

8）關鍵車站等價約束

由于本文假定列車在關鍵車站的轉線時間忽略不計，因此，列車在關鍵車站的到發時刻滿足式（17）、（18）所示等價約束.

式（17）、（18）中：i∈IX,s1∈(SG∪SK),s2∈ (SP∪SK).

9）列車開行模式選擇約束

當夕發朝至列車在高速鐵路運行，若在某個備選關鍵節點對應的天窗區段，其到發時間與天窗時間存在潛在沖突時，夕發朝至列車可選擇等線模式或者下線模式運行.圖2 表示夕發朝至列車i與天窗分段Dj存在潛在的時間沖突，列車i可以選擇等線或者下線運行，分別對應或者.則對應如式（19）所示的列車開行模式選擇約束.

圖2 沖突情形下列車模式選擇Fig.2 Mode selection of train in case of conflict

式中：φ (Tm,j,Ti) 為夕發朝至列車到發時間與天窗時間沖突判斷函數，取值為1 表示存在沖突，取值為0 表示不存在沖突，其中：Ti=[ti,s,c,ti,s+1,d].

同理，當高速鐵路夕發朝至列車在普速鐵路運行，若在某個關鍵車站對應的天窗區段，其列車運行時間與高速鐵路天窗沒有沖突，則夕發朝至列車可由普速鐵路上線至高速鐵路運行，對應約束如式（20）所示.

10）狀態變量約束

當高速鐵路夕發朝至列車在備選關鍵節點選擇不同的開行模式時，列車對應的開行狀態會發生變化，本文跟列車開行狀態相關的變量包括和 ρi,s，它們對應的約束如式（21）～（27）所示.

式（21）～（27）中：ρi,s∈{0,1}，i∈IX，s∈SK.

式（21）表示在每個備選關鍵車站，至多選擇一種列車開行模式.式（22）表示在備選關鍵車站，只有在 ρi,s-1=1 與 ρi,s=1 同時滿足的情況下，高速鐵路夕發朝至列車才會選擇等線模式.式（23）表示只有在 ρi,s-1=0 的情況下，高速鐵路夕發朝至列車才會選擇上線模式.式（24）、（25）表示高速鐵路夕發朝至列車如果選擇轉線開行模式，則在轉線前后車站的狀態變量是不同的.式（26）表示高速鐵路夕發朝至列車如果選擇轉線模式，則有 ρi,s=0.式（27）表示高速鐵路夕發朝至列車如果選擇上線模式，則有 ρi,s=1.

2.3 目標函數

本文主要從以下兩個方面對高速鐵路夕發朝至列車與天窗協調優化的目標進行考慮：

1）總的旅行時間最少

高速鐵路夕發朝至列車的開行要最大程度滿足旅客出行需求，除了列車到發時間需處在合理范圍以內，列車總的旅行時間也要盡可能短，以提升客運產品競爭力和吸引力.高速鐵路夕發朝至列車總的旅行時間可表示為

2）對既有列車運行圖的影響最小

高速鐵路夕發朝至列車的開行對既有列車運行圖的影響主要體現在兩個方面，一是對高速鐵路日間開行列車的影響，二是在高速鐵路列車下線情況下，對普速鐵路列車的影響.本文以受影響列車運行線數量來刻畫高速鐵路夕發朝至列車開行對既有列車運行圖的影響，則高速鐵路夕發朝至列車的開行對既有列車運行圖的影響可表示為

式（29）～（32）中：X、R、P分別為高速鐵路夕發朝至列車運行線集合、高速鐵路日間列車運行線集合和普速鐵路列車運行線集合；φ1(X,R) 與 φ2(X,P)用來判定不同類型列車運行線集合之間的影響關系，若運行線集合相交，說明存在影響，反之，則不受影響.

綜上，本文模型可表示為

3 求解算法

本文建立的高速鐵路夕發朝至列車與天窗協同優化模型是一個雙目標、非線性混合整數規劃模型，模型中變量、約束眾多，求解十分復雜.隨著問題規模的擴大，計算難度呈現指數增長，假定某高速鐵路線路備選的轉線車站數量為nS，則對任意一趟夕發朝至列車而言，對應的列車開行模式至多有 22nS-1種，若夕發朝至列車的開行數量為nI，則對應的列車開行與天窗設置方案共有種.可以看出，若對式（33）直接求解，難度很大.因此，本文首先采取雙目標轉換[9]、約束線性化處理、無約束處理、模型約簡等策略[10]（具體過程見附加材料1～4）來降低模型復雜度，再結合高速鐵路夕發朝至列車與天窗協同優化問題的雙層循環特性，設計了一種基于自適應大鄰域搜索（adaptive large neighborhood search algorithm，ALNS）的啟發式求解算法，算法包括內外兩重循環：內循環由破壞鄰域和修復鄰域組成，用于進行局部搜索；外循環通過模擬退火機制控制，用于解的更新，并能夠根據算子表現自適應調整算子權重.基于ALNS 的啟發式求解算法主要內容包括鄰域算子設計、自適應策略設計以及算法終止條件確定等幾個方面（見附加材料5）.具體求解流程如下：

步驟1初始化算法參數.以現圖中的高速鐵路夕發朝至列車與天窗方案作為初始解e0，對應目標函數值為f(e0)，并令初始解為當前解e和最優解ebest：e0賦予e，e0賦予ebest，f(e0) 賦予f(e)，f(e0)賦予f(ebest).

步驟2初始化全部算子的分數與權重.將所有算子權重設為1，所有算子分數設為0.

步驟3根據式（34），從破壞鄰域中選擇一個刪除算子，得到破壞解，并將從當前解中刪除的列車置于設定的存儲集合中.該存儲集合包含了所有未安排的列車.

式中：pu為算子u被選中的概率；ωu為算子u的權重；H為算子的數量.

步驟4根據式（34）選擇修復鄰域中的一個插入算子，從設定的存儲集合中選出部分列車，插入被破壞的解中，得到新解e’.

步驟5計算新解e’ 的目標函數值并與當前解e對應的目標函數值進行比較.如果e’ 對應的目標函數值f(e’) 優于e對應的目標函數值f(e)，則令e’ 為e，f(e’) 為f(e)；否則，使用模擬退火準則決定是否接受e’，同時相應更新e和f(e).

步驟6更新全部所選擇算子的分數與權重.結合步驟5 中計算的新解的目標函數值，自適應策略部分給出的算子分數計算規則進行更新[11]，并根據式（35）更新算子的權重.

式中：θu為算子u的分數；λ ∈[0,1] 為算子權重更新參數.

步驟7判斷是否滿足算法終止條件.如果滿足，轉步驟8，如果不滿足，轉步驟3.

步驟8輸出最優解ebest和最優解對應的目標函數值f(ebest)，算法結束.

4 算例分析

以京廣高速鐵路夕發朝至列車與天窗設置為例驗證本文模型與算法的有效性.京廣高速鐵路全長2 298 km，包含36 個車站，從北京南站開始，依次編號為1～36，與京廣高速鐵路平行的京廣線全長2 342 km，包含248 個車站，京廣高速鐵路與京廣線共同構成京廣運輸通道.京廣高速鐵路夕發朝至列車始發時間域為18∶00—22∶00，終到時間域06∶30—09∶30，列車追蹤間隔為5 min，車站到達和出發間隔均取5 min，最小停站時間為2 min，起停附加時分為2 min，同方向列車不同時到發間隔時間與發到間隔時間均為3 min；在京廣普速鐵路上，列車追蹤間隔為5 min，車站到達和出發間隔均取5 min，最小停站時間為3 min，起停附加時分為2 min.天窗合理開設時間范圍為00∶00—06∶00，天窗時長為240 min，天窗安全間隔時間為5 min.考慮車站能力及客流特點，選取石家莊、鄭州東、武漢、長沙南、郴州西5 個大站作為備選的轉線車站集合，對應的到發線總數分別為11、16、24、16、6 條.

京廣通道內高速鐵路和普速鐵路區段距離和運行時間如附加材料6 中表S1 所示，由于上、下行方向信息基本一致，僅以下行方向為例給出.根據2018 年年底列車運行圖數據[12]，京廣高速鐵路總共開行14 列夕發朝至列車，其中上行與下行方向各7 列.京廣高速鐵路夕發朝至列車，具體開行信息如附加材料6 中表S2 所示，包括列車始發、終到車站、運行方向、開行距離、旅行時間、合理出發、到達時間范圍以及列車停站方案.

以2018 年年底列車運行圖[12]為基準，根據本文提出的模型方法，將14 列高速鐵路夕發朝至列車插入既有列車運行圖框架.在19∶00—10∶00 這個時間段內，共包含73 列下行高速鐵路日間列車，58 列上行高速鐵路日間列車，在平行的普速鐵路上，這個時間段共開行32 列下行普速列車，23 列上行普速列車.列車開行統計信息見附加材料6 中表S3.

采用MATLAB 7.0 編程實現設計的啟發式求解算法，設最大迭代次數為200，ALNS 算法大約平均經過40 次便可收斂至最優解.在目標函數分別賦權0.5 的情況下，無量綱目標函數最小值為0.21，對應求解時間為784 s.目標函數最小值對應的最佳天窗設置方案和夕發朝至列車到發時刻表分別如表1和表2 所示.表2 中“/”兩側分別表示車站到達和出發時刻.

表1 最優天窗方案Tab.1 Optimal maintenance window scheme

表2 京廣高鐵夕發朝至列車最優解對應的到發時刻表Tab.2 Optimal arrival and departure time table of Beijing-Guangzhou high-speed railways

為進一步分析不同列車開行模式對夕發朝至列車開行和天窗設置的影響，分別限定列車開行模式對目標函數進行求解，結果如表3 所示，表中第3 列中“/”左、右兩側分別表示在研究時間段內受影響的高速鐵路列車數、普速列車數.對比可知，在不同列車開行模式下，高速鐵路夕發朝至列車總的旅行時間、高速鐵路夕發朝至列車對既有列車運行圖的影響以及對應的計算時間均存在差異.

表3 不同列車開行模式下的目標函數值Tab.3 Objective function values under different overnight train operation modes

圖3 給出了限定不同列車開行模式對應的最優天窗設置方案和夕發朝至列車運行方案，圖中紅線、藍線分別表示列車在高速鐵路、普速鐵路運行.可以發現：不同列車開行模式下天窗較優方案均為分段矩形天窗，這是由于分段矩形天窗要比垂直矩形天窗設置更為靈活；上行方向列車轉線運行通常是在鄭州東站，而下行方向列車轉線運行通常是在長沙南站，主要是因為這些車站能力相對充裕，且具備組織列車跨線運輸條件.