廉志斌 ，帥 斌 ，許旻昊

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

0 引言

高速鐵路列車在運(yùn)行過程中可能因?yàn)?zāi)害天氣、設(shè)備故障等因素而發(fā)生晚點(diǎn)，前行列車晚點(diǎn)或?qū)?dǎo)致后行列車的連帶晚點(diǎn)。列車晚點(diǎn)發(fā)生后，原定的列車到發(fā)線運(yùn)用計(jì)劃很可能存在沖突，如果按原定計(jì)劃安排列車的接發(fā)車作業(yè)，很可能會(huì)降低局部路網(wǎng)的運(yùn)輸效率。此時(shí)，列車調(diào)度員可以調(diào)整列車的到發(fā)線運(yùn)用計(jì)劃，疏解列車到發(fā)線運(yùn)用沖突，從而減少列車的晚點(diǎn)。

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

1 高速鐵路車站到發(fā)線運(yùn)用計(jì)劃調(diào)整問題

1.1 問題描述

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

表1 列車原始到發(fā)時(shí)刻表及占用到發(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 次列車晚點(diǎn)9 min，最早到達(dá)時(shí)刻為11 :23，停在6 道。而D6 次列車原計(jì)劃11 :24 到達(dá)且停放在6 道，因而需要為D6 次列車分配其他空閑到發(fā)線或使其晚點(diǎn)直至6 道空閑再將其接入。

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

1.2 列車潛在沖突判斷

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

圖2 列車沖突識(shí)別圖Fig.2 Train conflict recognition diagram

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

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

1.3 晚點(diǎn)下列車權(quán)重設(shè)置方法

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

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

表3 根據(jù)列車等級(jí)設(shè)置權(quán)重規(guī)則Tab.3 Weighting rules setting according to train class

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

計(jì)算得到晚點(diǎn)條件下列車權(quán)重為

1.4 列車晚點(diǎn)下高速鐵路車站到發(fā)線運(yùn)用計(jì)劃調(diào)整模型

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

模型有2 個(gè)目標(biāo)函數(shù)，目標(biāo)函數(shù)M1為所有列車的連帶晚點(diǎn)時(shí)間之和最小，計(jì)算公式為

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

采用線性加權(quán)的方式整合目標(biāo)M1和M2，得到總目標(biāo)函數(shù)的計(jì)算公式為

式中：α和β分別為目標(biāo)M1和M2的權(quán)重，用于權(quán)衡2 個(gè)目標(biāo)的重要程度。

模型包括以下約束條件。

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

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

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

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

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

（5）進(jìn)路唯一占用約束。設(shè)占用進(jìn)路時(shí)間存在沖突的列車所構(gòu)成的集合為潛在列車——進(jìn)路沖突集合，對(duì)于任意列車同一時(shí)間同一條進(jìn)路至多被一列車占用。

（6）占用進(jìn)路時(shí)間存在沖突的列車不能同時(shí)占用敵對(duì)進(jìn)路。對(duì)于任意列車不能同時(shí)占用敵對(duì)進(jìn)路。

式中：JH表示某個(gè)敵對(duì)進(jìn)路集合。

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

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

2 到發(fā)線運(yùn)用計(jì)劃調(diào)整模型求解算法

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

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

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

步驟3：適應(yīng)度函數(shù)值計(jì)算。遺傳算法的適應(yīng)度函數(shù)值即為目標(biāo)函數(shù)值。

步驟4：約束條件檢驗(yàn)。對(duì)種群中每個(gè)個(gè)體進(jìn)行模型約束條件檢驗(yàn)，并記錄其是否為可行解。

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

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

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

3 案例分析

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

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

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

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

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

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

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

圖3 可行解的散點(diǎn)圖Fig.3 Scatter plot of feasible solutions

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

以上求解結(jié)果為α取0.7 時(shí)得到的滿意解?；谝陨习咐讦敛煌≈档那闆r下分別進(jìn)行計(jì)算，以比較目標(biāo)函數(shù)中兩部分優(yōu)化目標(biāo)的重要程度。α不同取值下“最優(yōu)”滿意解到發(fā)線偏離原計(jì)劃列車數(shù)、列車總連帶晚點(diǎn)時(shí)間變化如圖5 所示。

圖5 α 不同取值下“最優(yōu)”滿意解到發(fā)線偏離原計(jì)劃列車數(shù)、列車總連帶晚點(diǎn)時(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ā)線偏離原計(jì)劃列車數(shù)呈上升趨勢(shì)，而“最優(yōu)”滿意解的列車總連帶晚點(diǎn)時(shí)間呈下降趨勢(shì)。這是因?yàn)棣磷鳛槟繕?biāo)函數(shù)中列車連帶晚點(diǎn)時(shí)間的線性相關(guān)系數(shù)，其側(cè)重于尋找列車連帶晚點(diǎn)時(shí)間更小的解，因而隨著α取值不斷增加，列車總連帶晚點(diǎn)時(shí)間呈下降趨勢(shì)。相反，“最優(yōu)”滿意解的到發(fā)線偏離原計(jì)劃列車數(shù)呈上升趨勢(shì)。在上述案例中，如果從降低車站工作組織紊亂程度的角度出發(fā)，可將目標(biāo)函數(shù)中α設(shè)置為較小數(shù)值；如果從減少旅客候車時(shí)間的角度出發(fā)，可將α設(shè)置為較大數(shù)值。

4 結(jié)束語

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