列車晚點下高速鐵路車站到發(fā)線運用計劃調整方法

廉志斌 ，帥 斌 ，許旻昊

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

0 引言

高速鐵路列車在運行過程中可能因災害天氣、設備故障等因素而發(fā)生晚點，前行列車晚點或將導致后行列車的連帶晚點。列車晚點發(fā)生后，原定的列車到發(fā)線運用計劃很可能存在沖突，如果按原定計劃安排列車的接發(fā)車作業(yè)，很可能會降低局部路網的運輸效率。此時，列車調度員可以調整列車的到發(fā)線運用計劃，疏解列車到發(fā)線運用沖突，從而減少列車的晚點。

在關于列車到發(fā)線運用計劃調整的研究中，Chakroborty 等[1]假定車站在列車到達車站前60 min得知其晚點時長，以列車延誤成本、列車變更到發(fā)線造成不便的費用最小化為目標，構建混合整數(shù)規(guī)劃模型。Jáno?íková 等[2]將出發(fā)列車延誤時間最小和乘客不便最小作為目標，構建到發(fā)線調整模型。在此基礎上，Jáno?íková 等[3]以最小化到達和出發(fā)晚點時間、最大化列車占用到發(fā)線的可取性為目標，構建混合整數(shù)規(guī)劃模型。Zeng 等[4]根據混合整數(shù)線性規(guī)劃和車站調度理論，分別針對正常情況和晚點情況構建多準則車站進路選擇模型。王韓冬[5]通過建立兩階段規(guī)劃模型，首先為車站到發(fā)線賦予不同的權重，然后求解列車晚點最小和列車變更到發(fā)線數(shù)目最少的到發(fā)線運用計劃。喬瑞軍[6]以列車在站內走行時間最小、到發(fā)線均衡使用為目標，建立到發(fā)線調整的多目標優(yōu)化模型。朱昌鋒[7]將列車實際出發(fā)時刻與圖定時刻差值最小、列車實際占用股道偏離原計劃程度最小為目標，構建到發(fā)線調整模型。劉偉[8]通過對列車賦權，進而構造列車進路選擇和到發(fā)線調整模型。鄧遠冬[9]通過累積流變量刻畫列車占用咽喉區(qū)進路與到發(fā)線的過程，建立考慮列車權重的高速鐵路車站到發(fā)線運用計劃調整0-1 整數(shù)規(guī)劃模型，利用拉格朗日松弛算法求解。這些研究中，到發(fā)線調整的目標和列車權重的設置比較簡單，且只考慮單側車場作業(yè)，沒有考慮上、下行車場的股道靈活運用，導致車站到發(fā)線運用計劃與實際情況偏差較大。為此，以所有列車的連帶晚點時間之和最少、所有列車實際占用到發(fā)線偏離原計劃程度最小為目標，構建列車晚點下高速鐵路車站到發(fā)線運用計劃調整模型。該模型綜合考慮了列車等級、作業(yè)類型及初始晚點時間3 類屬性，提出更合理的晚點下列車權重設置方法，可以提升車站到發(fā)線運用計劃的編制質量。

1 高速鐵路車站到發(fā)線運用計劃調整問題

1.1 問題描述

正常情況下，高速鐵路車站按照圖定時刻接發(fā)列車，并按原計劃為列車安排到發(fā)線，而當列車發(fā)生晚點時，如果列車作業(yè)之間的緩沖時間無法完全吸收晚點，車站原到發(fā)線運用計劃有可能存在沖突，需要調整原到發(fā)線運用計劃，以減少連帶晚點等負面情況。例如，某車站設有6 條到發(fā)線，其中2 條正線，車站平面布置如圖1 所示。該車站接發(fā)A，B，C 方向的列車。列車原始到發(fā)時刻表及占用到發(fā)線信息如表1 所示。

表1 列車原始到發(fā)時刻表及占用到發(fā)線信息Tab.1 Original train arrival and departure timetable and information of occupied arrival and departure tracks

圖1 車站平面布置圖Fig.1 Layout plan of station

如果D4 次列車晚點9 min，最早到達時刻為11 :23，停在6 道。而D6 次列車原計劃11 :24 到達且停放在6 道，因而需要為D6 次列車分配其他空閑到發(fā)線或使其晚點直至6 道空閑再將其接入。

到發(fā)線運用計劃調整的目的是盡快為存在時間沖突的列車分配無沖突的空間資源。列車晚點下高速鐵路車站到發(fā)線運用計劃調整問題，是在已知列車晚點的條件下，考慮到發(fā)線、進路沖突等因素，通過優(yōu)化列車的到發(fā)線分配計劃，使所有列車的連帶晚點時間和列車實際占用到發(fā)線偏離原計劃程度最小。

1.2 列車潛在沖突判斷

為了判斷列車間的時間沖突，可事先計算出列車在車站可能停留的時間范圍[10]，基于此可以分析得到所有可能存在沖突的列車對，既保證不會遺漏列車之間的沖突，又不必檢查任意兩列車之間是否存在沖突，提升求解效率。當車站某時間段發(fā)生列車晚點時，仍可以根據列車運行圖及追蹤列車最小間隔時間得出該時間段內每列車最早到站時間，然后根據每列車在站的進路走行時間和停留時間，可以得出每列車占用車站空間資源的時間跨度。以上小型晚點場景可以得到晚點后的列車沖突識別圖[10]如圖2 所示。

圖2 列車沖突識別圖Fig.2 Train conflict recognition diagram

由圖2 可知，左側的矩形長度分別代表D1—D6 列車占用車站空間資源的時間范圍，在時間軸上存在時間重疊的兩列車有可能發(fā)生沖突。將列車看作無向圖的節(jié)點，并將可能存在沖突的列車對用邊連接，得到表示列車沖突的識別圖。根據列車沖突識別圖可以構造列車沖突識別鄰接矩陣如下。

矩陣Cn×n中的元素可表示2 列車之間是否可能存在沖突，可減少冗余的約束條件檢驗，提高求解效率。例如，元素c21=1 表示D2 次列車與D1 次列車可能存在沖突；c32=0 表示D2 次列車與G3 次列車不可能沖突。

1.3 晚點下列車權重設置方法

晚點情況下，列車的權重主要受到初始晚點時間、列車等級(如高速動車組旅客列車等級高于動車組旅客列車)和列車作業(yè)類型3 方面的影響。關于列車作業(yè)類型，采用賈文崢等[10]中的方法，根據列車作業(yè)類型設置權重規(guī)則如表2 所示。由于跨線列車的晚點會傳播至其他線路，因而跨線列車的權重值需要在上述基礎上加2。根據列車等級設置權重規(guī)則如表3 所示。采用min-max 方法分別對以上3 項指標進行歸一化處理，計算公式為

表2 根據列車作業(yè)類型設置權重規(guī)則Tab.2 Weighting rules setting based on train operation type

表3 根據列車等級設置權重規(guī)則Tab.3 Weighting rules setting according to train class

式中：x′表示個體歸一化后的指標值；x表示個體歸一化之前的數(shù)值；X表示一組同類型樣本數(shù)據；min (X)表示X中最小值；max (X)表示X中最大值。

計算得到晚點條件下列車權重為

1.4 列車晚點下高速鐵路車站到發(fā)線運用計劃調整模型

設高速鐵路車站在某時段內接發(fā)的列車總數(shù)為m；列車集合TR=[TRi]，i∈N+，i≤m。車站設有n條到發(fā)線，設車站到發(fā)線集合D=[Dj]，j∈N+，j≤n。設車站進路集合為J=[Jj]，j∈N+，j≤l。

模型有2 個目標函數(shù)，目標函數(shù)M1為所有列車的連帶晚點時間之和最小，計算公式為

目標函數(shù)M2為所有列車實際占用到發(fā)線偏離原計劃程度最小。既有文獻多通過設置到發(fā)線懲罰值的方法描述，較為復雜且不夠直觀。為此，將車站的到發(fā)線從一側開始由小到大編號(如圖1 所示)。考慮到列車發(fā)生晚點時，車站工作人員會盡可能安排列車占用原計劃到發(fā)線，如果必須變更到發(fā)線，則應盡可能選擇距離原計劃到發(fā)線較近的到發(fā)線，以減少旅客在候車大廳的走行距離，避免大批旅客更換檢票口造成的擁堵，計算公式為

采用線性加權的方式整合目標M1和M2，得到總目標函數(shù)的計算公式為

式中：α和β分別為目標M1和M2的權重，用于權衡2 個目標的重要程度。

模型包括以下約束條件。

（1）到站時刻約束。晚點發(fā)生后，列車實際到達時刻不得早于列車最早到達時刻。

（2）出發(fā)時刻約束。列車實際出發(fā)時刻不得早于圖定出發(fā)時刻。

（3）到發(fā)線唯一占用約束。設占用到發(fā)線時間存在沖突的列車所構成的集合為對于任意列車對于某一條到發(fā)線，存在到發(fā)線占用時間沖突關系的列車集合中，至多有1 列車可以占用此到發(fā)線。

（4）通過列車只能占用正線。

式中：TRXB表示下行不停站通過列車集合，TR；TRSB表示上行不停站通過列車；DXZ表示下行正線集合表示上行正線集合，。

（5）進路唯一占用約束。設占用進路時間存在沖突的列車所構成的集合為潛在列車——進路沖突集合，對于任意列車同一時間同一條進路至多被一列車占用。

（6）占用進路時間存在沖突的列車不能同時占用敵對進路。對于任意列車不能同時占用敵對進路。

式中：JH表示某個敵對進路集合。

（7）到發(fā)線最小作業(yè)時間間隔約束。同一到發(fā)線上相鄰進行作業(yè)的兩列車的時間間隔需要滿足最小安全間隔時間要求。

式中：DT表示到發(fā)線最小作業(yè)時間間隔；如果則t時刻列車TRi占用到發(fā)線j，如果0 則t時刻列車TRi未占用到發(fā)線j。

2 到發(fā)線運用計劃調整模型求解算法

到發(fā)線運用計劃調整問題屬于大規(guī)模組合優(yōu)化問題，屬于NP-hard 問題。目前求解這類問題一般采用智能算法?？紤]到遺傳算法具有良好的全局搜索能力，可以快速地進行解空間的全局搜索。此外，列車占用到發(fā)線的決策變量屬于0-1 變量，可以利用遺傳算法中的交叉和變異算法實現(xiàn)解空間的搜索，因而采用遺傳算法求解模型。遺傳算法求解模型的步驟如下。

步驟1：設置初始參數(shù)。首先設置列車權重的3 項參數(shù)，然后設置目標函數(shù)中α和β。設置遺傳算法初始參數(shù)：種群大小N值，迭代代數(shù)NP，算法停止條件參數(shù)NP_S，變異概率pm。

步驟2：編碼。假設高速鐵路車站在某時間段內存在m列車，以每列車占用到發(fā)線編號和連帶晚點時間為基礎，將種群中每個個體編碼為1×2m的行向量，前m列代表m列車分別占用到發(fā)線的編號，后m列代表m列車各自的連帶晚點時間。

步驟3：適應度函數(shù)值計算。遺傳算法的適應度函數(shù)值即為目標函數(shù)值。

步驟4：約束條件檢驗。對種群中每個個體進行模型約束條件檢驗，并記錄其是否為可行解。

步驟5：選擇，交叉、變異。算法選擇，交叉、變異規(guī)則如下：選擇當前種群中目標函數(shù)值最大的個體La(Largest)及第二大的個體S-la(Second Largest)，對二者前m列的列車占用到發(fā)線信息進行交叉；選擇目標函數(shù)值最大的個體La，根據變異概率，再隨機對同一條線路上追蹤運行的列車的連帶晚點時間同時進行變異。

步驟6：判斷是否滿足終止條件。根據算法停止條件參數(shù)NP_S，若連續(xù)NP_S代的可行解中最小目標函數(shù)值無變化，則算法停止，或迭代至NP代，算法停止。

步驟7：得到滿意解。程序循環(huán)至滿足終止條件，算法結束，得到滿意解。

3 案例分析

以圖1 所示的高速鐵路車站為例進行案例分析。該站設有2 個站臺，6 條到發(fā)線(其中的2 條為正線)。以某日11 :00—12 :00 為案例分析時段。列車基本信息及原始時刻表如表4 所示。其中，D1 次列車為本線折返列車，D2，G7 和G12 次列車為不停站通過列車，其他列車為停站通過列車。

表4 列車基本信息及原始時刻表Tab.4 Original train arrival and departure timetable and basic information

案例假設D2 次列車晚點10 min，G3 次列車晚點10 min。在不考慮分段解鎖的情況下，車站各項作業(yè)時間標準為：追蹤間隔時間取4 min；停站通過列車接車進路開始時刻為到達時間前4 min，終止時刻為到達時間；停站通過列車發(fā)車進路開始時刻為列車發(fā)車前30 s，終止時刻為列車出發(fā)后3 min。不停站通過列車接車進路開始時刻為到達前2 min，發(fā)車進路終止時刻為到達后1.5 min。到發(fā)線最小安全間隔時間DT為5 min。

基于以上基礎數(shù)據，利用上述模型和算法求解。其中，初始參數(shù)設置為：目標函數(shù)中α和β值分別設為0.7 和0.3，設置列車權重的系數(shù)λ1，λ2，λ3分別設為0.2，0.3，0.5。遺傳算法種群大小N取60，迭代代數(shù)NP取1 000，算法停止條件參數(shù)NP_S取200，變異概率pm取0.85。遺傳算法一般將變異概率設置為小于0.1 的數(shù)值，但由于編碼的特殊性，將初始種群中的列車連帶晚點時間設置為較大的數(shù)值，而變異的目的之一是不斷減小列車的連帶晚點時間。因此，為了快速減少列車連帶晚點時間，找出滿意解，將變異概率設置為較大的數(shù)值。

通過求解得到晚點后列車到發(fā)時刻及到發(fā)線調整信息如表5 所示。對比表4 和表5 可知，晚點發(fā)生后，模型求解得到的滿意解中，有10 列車發(fā)生晚點，8 列車未占用原計劃到發(fā)線。對此結果進行分析可知：D4 次列車和D5 次列車晚點的原因是與前方晚點列車追蹤運行；D6 次列車、K9 次列車和D11 次列車晚點原因是到發(fā)線沖突；G7 次列車、C10 次列車和G12 次列車晚點原因是進路沖突；而D1次列車和C8次列車未發(fā)生晚點。

表5 晚點后列車到發(fā)時刻及到發(fā)線調整信息Tab.5 Train arrival and departure time and adjustment information of arrival and departure tracks after delay

遺傳算法所得所有可行解的散點圖如圖3 所示，“最優(yōu)”可行解與“最差”可行解如圖4 所示。

圖3 可行解的散點圖Fig.3 Scatter plot of feasible solutions

圖4 “最優(yōu)”可行解與“最差”可行解Fig.4 “Optimal” feasible solution and “worst” feasible solution

以上求解結果為α取0.7 時得到的滿意解。基于以上案例，在α不同取值的情況下分別進行計算，以比較目標函數(shù)中兩部分優(yōu)化目標的重要程度。α不同取值下“最優(yōu)”滿意解到發(fā)線偏離原計劃列車數(shù)、列車總連帶晚點時間變化如圖5 所示。

圖5 α 不同取值下“最優(yōu)”滿意解到發(fā)線偏離原計劃列車數(shù)、列車總連帶晚點時間變化Fig.5 Changes in the number of trains on arrival and departure tracks deviating from the original plan and the total delay time of the “optimal”satisfactory solution under different α values

由圖5 可知，隨著α取值不斷增加，算法所得“最優(yōu)”滿意解到發(fā)線偏離原計劃列車數(shù)呈上升趨勢，而“最優(yōu)”滿意解的列車總連帶晚點時間呈下降趨勢。這是因為α作為目標函數(shù)中列車連帶晚點時間的線性相關系數(shù)，其側重于尋找列車連帶晚點時間更小的解，因而隨著α取值不斷增加，列車總連帶晚點時間呈下降趨勢。相反，“最優(yōu)”滿意解的到發(fā)線偏離原計劃列車數(shù)呈上升趨勢。在上述案例中，如果從降低車站工作組織紊亂程度的角度出發(fā)，可將目標函數(shù)中α設置為較小數(shù)值；如果從減少旅客候車時間的角度出發(fā)，可將α設置為較大數(shù)值。

4 結束語

針對列車晚點下高速鐵路車站到發(fā)線運用計劃調整問題，構造到發(fā)線運用計劃調整模型，設計遺傳算法求解，并通過案例計算驗證模型的有效性。在到發(fā)線運用計劃調整模型中，基于列車初始晚點時間、列車等級、列車作業(yè)類型3 種屬性為晚點列車賦予權重，以所有列車的連帶晚點時間之和最少、所有列車實際占用到發(fā)線偏離原計劃程度最小為優(yōu)化目標，并采取線性加權的方式對2 部分目標進行整合，在案例中為2 部分目標的權重系數(shù)賦予不同的取值組合，通過計算結果分析2 部分目標的重要程度與權重系數(shù)取值的關系，表明到發(fā)線運用計劃調整的模型和算法可以減輕由于晚點導致的車站作業(yè)成本增加，有效遏制列車晚點在路網中的蔓延趨勢，保證旅客服務質量。