周期模式下高速鐵路車站到發(fā)線運用優(yōu)化模型研究

單奕嘉，聶 磊，樂逸祥，徐瑞華，王鵬玲

(1.北京交通大學 交通運輸學院, 北京 100044；2.同濟大學 上海市軌道交通結構耐久與系統(tǒng)安全重點實驗室，上海 201804)

西歐、日本等地區(qū)和國家高速鐵路(以下簡稱“高鐵”)廣泛采用周期化列車運行圖，相應車站作業(yè)亦有周期化的特點。近年來國內學者更加關注“列車周期化開行”運輸組織模式，并以京滬高鐵、滬寧城際等線路為對象，研究更適應我國特點的周期化列車開行方案與周期化列車運行圖編制方法，但針對周期模式下車站到發(fā)線運用的優(yōu)化研究較少。

國外學者對咽喉區(qū)、到發(fā)線的研究起步于20世紀70年代，在研究初期，學者們往往將該問題簡化為在固定前序列車作業(yè)順序的基礎上對單列車安排進路的多個子問題，并通常采用啟發(fā)式算法求解[1]；后發(fā)展為兩者的綜合優(yōu)化，以及列車晚點下的動態(tài)調整，設計了線性化方法和精確求解算法[2-5]；目前，國外許多國家對周期化列車開行模式的研究已較為成熟，如德國柏林中央客運站[6]、海牙HS站，通常采用周期事件規(guī)劃問題(Periodic Event Scheduling Problem, PESP)構建周期化方案[4]。

國內學者在研究初期將咽喉區(qū)進路選擇和到發(fā)線運用分開考慮[7-10]；然后把咽喉區(qū)和到發(fā)線統(tǒng)一看作車站資源整體優(yōu)化[11-12]；最后提出到發(fā)線運用方案和運行圖同步調整的方法[13]。

綜上，考慮我國高鐵車站設備特點和多樣化、層次化出行需求的周期化車站到發(fā)線運用方案編制的研究非常少。本文結合國外車站到發(fā)線周期化運用的經驗，以我國周期化列車運行圖的特點和編制辦法為基礎，提出到發(fā)線周期化運用的編制流程，并建立多目標優(yōu)化模型。

1 周期模式下車站到發(fā)線運用分析

到發(fā)線周期化方案的編制可參考周期圖的編制方法。首先編制單周期車站到發(fā)線方案，保證按圖行車時列車的接、發(fā)車作業(yè)不沖突，得到單周期方案；在此基礎上，經過抽線調整，即把在其他周期內不開行的列車運行線剔除，拼接形成日周期方案。最后根據實際需要，插入非周期列車，加線調整得到全日方案，編制流程見圖1。

周期化運行圖是到發(fā)線周期化運用的基礎，但并不意味著運行圖實現(xiàn)周期化后即可形成到發(fā)線周期化運用方案，在方案編制過程中，需要在列車到發(fā)時刻周期化約束下，考慮：①相同到發(fā)時刻的同類列車在不同周期中應占用相同股道，即周期占用約束；②因同類列車在不同周期中占用相同的股道，除接發(fā)車進路不沖突外，還要滿足動車組交路接續(xù)對到發(fā)線占用的要求，即把動車組出入段進路納入考量；③為提高旅客換乘的便捷性，有中轉接續(xù)關系的列車盡可能股道相鄰或相近；④當車站銜接多個方向時，增加不同方向列車在車站的周期化接續(xù)約束；⑤在編制到發(fā)線運用方案時會出現(xiàn)部分列車的到發(fā)時刻不在同一個周期內，針對這類“過表列車”，需要確定合理有效的沖突疏解辦法確保周期拓展后無沖突；⑥若采用“周期+非周期運行圖”，在以高峰周期為基本單元構建的到發(fā)線運用方案可行的前提下，還需在其他周期出現(xiàn)非周期列車時保證非周期列車占用到發(fā)線的需求。

由于“周期+非周期運行圖”下到發(fā)線運用比“非周期運行圖”下到發(fā)線運用增加更多的到發(fā)線周期占用、中轉接續(xù)約束等，求解更為困難。在列車密度比較大時，周期占用導致兩列車間空擋時間增加，容易導致到發(fā)線能力不足而無解，鑒于此，提出以下3個關鍵問題。

圖1 周期化車站到發(fā)線運用方案編制流程

1.1 列車接續(xù)

周期化列車運行圖在編圖時有嚴格的頻率約束和接續(xù)約束以方便旅客的出行和換乘[14]。文獻[15]規(guī)定了最小列車接續(xù)時間(平均旅客換乘時間)h-和最大列車接續(xù)時間(平均旅客換乘時間加最大旅客等待時間)h+。

車站列車接續(xù)示意見圖2，列車i的OD為A—D，列車i+1的OD為B—D，旅客從A站出發(fā)前往D站，只能在E站換乘。當這類旅客的人數較多時，編圖人員會在編制周期圖時將列車i和列車i+1設為接續(xù)關系，使這兩列車的到發(fā)時刻盡量鄰近。

圖2 車站列車接續(xù)示意圖

圖3 到發(fā)線列車接續(xù)示意

若有旅客從列車i換乘至列車i+1，則必需滿足換乘所需時間小于列車接續(xù)時間，即

(1)

反之，從列車i+1換乘至列車i，需滿足

(2)

1.2 過表列車沖突消解與虛實時間窗

我國編圖時，一般安排1 d(24 h)內運行的列車，而周期化列車運行圖的周期一般為1 h或2 h，周期的縮短必然導致“過表列車”增加，即運行線跨多個周期的列車。

在編制車站到發(fā)線運用方案時，如果不考慮“過表列車”涉及的周期與研究周期的相互影響，在編完單周期方案拓展后很可能發(fā)生列車沖突，見圖4，其中G1、G2等為車次。該方案中單個周期內的列車并無沖突，但由于未考慮“過表列車”G5和列車G1之間的關系，導致方案拓展后G5與G1發(fā)生沖突。

圖4 過表列車沖突示意圖

對于給定的運行圖均有

(3)

式中：T為周期長度。

(4)

(5)

(6)

(7)

圖5 實時間窗和虛時間窗示意

由于采用周期化列車運行圖，研究周期內過表列車的到發(fā)時刻和鄰接周期同一列(指列車類型、運行區(qū)間、運行速度等均相同)過表列車的到發(fā)時刻相同，因此可將兩列車視為一列車處理。

1.3 非周期列車到發(fā)線安排

我國高鐵具有“點多、線長、面廣、跨線列車多”的特點，“周期+非周期”模式的運行圖更適合我國國情[16]，即首先編制高峰周期列車運行圖，對個別周期抽線后拼接形成日周期運行圖，然后以此為基礎，在全圖范圍內添加非周期運行線。

在周期模式到發(fā)線運用方案中加入非周期列車需要考慮的因素比較多，目標函數與周期模式到發(fā)線運用方案也有不同，本文暫不考慮非周期列車的到發(fā)線安排。

2 周期模式下車站到發(fā)線運用優(yōu)化模型

根據第1節(jié)分析，周期模式下車站到發(fā)線運用優(yōu)化是在已知周期化列車運行圖、車場平面布置圖、車站作業(yè)分工、時間標準的情況下，滿足方向性、到發(fā)線獨占性、正線通過、抽線停運列車、旅客換乘走行時間與列車接續(xù)時間等約束的優(yōu)化問題。由于要滿足方案周期化要求，為保證在一個周期內能開更多的車，優(yōu)化后的到發(fā)線運用方案應使列車的站內總走行時間最?。淮送?，考慮站內設備合理使用，將到發(fā)線均衡使用納入優(yōu)化目標。

2.1 符號說明

符號說明見表1。

表1 基礎數據

( 8 )

(2)δiejk計算方法

高鐵車站安排到發(fā)線方案時，需統(tǒng)籌考慮列車接發(fā)車、出入段進路，使走行時間存在重疊的列車避開敵對進路，即進路沖突需同時滿足兩個條件：①列車在進路走行時間上存在交叉；②兩條進路存在交叉。因此本文從時間維和空間維進行分析。

時間維上來看，接發(fā)列車時涉及接車走行時間、發(fā)車走行時間和站內作業(yè)時間，可能出現(xiàn)的沖突類型有3種，見圖6。

接車(出段)與接車(出段)走行時間重疊列車集合為

( 9 )

發(fā)車(入段)與發(fā)車(入段)走行時間重疊列車集合為

i,j∈Tmut}

(10)

接車(出段)與發(fā)車(入段)走行時間重疊列車集合為

i,j∈Tmut}

(11)

圖6 咽喉區(qū)進路時間沖突類型

圖7 咽喉區(qū)進路空間沖突類型

接車(出段)與接車(出段)敵對進路集合為

(12)

發(fā)車(入段)與發(fā)車(入段)敵對進路集合為

(13)

接車(出段)與發(fā)車(入段)敵對進路集合

(14)

因此，將走行時間存在重疊的列車集合與敵對進路集合作笛卡爾乘積，得到

Rin_outi,j∈Tmute,k∈Ladt}

(15)

2.2 目標函數

(1)列車站內總走行時間最小

接車走行范圍從進站信號機起至各到發(fā)線動車組停車位置止。為使后行列車具備良好接車條件，前行列車必須盡快出清進路中的軌道電路區(qū)段。盡端式樞紐站折返列車較多，無論采用正接反發(fā)還是反接正發(fā)的形式，都必須跨越正線，與其余列車的接發(fā)車進路發(fā)生交叉。因此，為保證安全和提高車站作業(yè)效率，必須盡可能縮短列車進路走行時間，即該目標要求在無沖突的情況下選擇距正線最近的到發(fā)線接發(fā)列車。

列車在站內的作業(yè)可分為3個環(huán)節(jié)：①接車(出段)作業(yè)；②列車停靠在到發(fā)線上進行的圖定作業(yè)；③發(fā)車(入段)作業(yè)。在列車到發(fā)時刻確定的情況下，環(huán)節(jié)②時間固定，環(huán)節(jié)①與環(huán)節(jié)③的時間與列車占用的到發(fā)線有關，因此考慮優(yōu)化環(huán)節(jié)①和環(huán)節(jié)③，即列車站內總走行時間Z1。

(16)

(2)到發(fā)線使用最均衡

到發(fā)線的利用率可用列車占用到發(fā)線的時間體現(xiàn)，用方差描述，即每一條到發(fā)線e的占用時間與到發(fā)線平均占用時間的偏離程度Z2。

(17)

2.3 約束條件

(1)到發(fā)線可達性約束。任意的列車i都受方向性的約束，即只能駛入可達的到發(fā)線進行作業(yè)。

(18)

(2)到發(fā)線獨占性約束。作業(yè)過程中，任意的列車i只能選擇一條到發(fā)線。

(19)

(3)正線通過約束。不停站通過列車必須由正線通過車站。

(20)

(4)占用同一條到發(fā)線會產生沖突的列車，即屬于沖突列車集合Sij的列車i和列車j，不能安排在同一條到發(fā)線上。

xie+xje≤1 ?(i,j)∈Sij?e∈Ladt

(21)

(5)走行時間有重疊部分的列車不能選擇敵對進路，即屬于δ(i,e,j,k)的列車i,j，不能選擇到發(fā)線e,k。

xie+xjk≤1 ?(i,e,j,k)∈δiejk

(22)

(6)上水、吸污約束。需要辦理上水、吸污作業(yè)的列車必需安排在具備辦理該作業(yè)條件的到發(fā)線上。

(23)

(7)在高峰周期內存在其他周期抽線停運的列車，為保證到發(fā)線的均衡使用，在其他周期會抽線停運的列車需與正常運營列車安排在同一到發(fā)線上。

?e∈Ladt?i∈Tmut

(24)

(8)列車接續(xù)約束。若列車i,j存在接續(xù)關系，則兩列車停靠到發(fā)線e、k之間的旅客換乘走行時間需小于兩列車的接續(xù)時間。

xie+xjk≤1 ?(i,e,j,k)∈φiejk

(25)

綜上，式(16)～式(25)構成周期模式下到發(fā)線運用優(yōu)化多目標模型；式(16)、式(18)～式(25)構成線性整數規(guī)劃P1;式(17)、式(18)～式(25)構成非線性整數規(guī)劃P2。

3 模型及算法分析

3.1 模型最優(yōu)值分析

模型P1為純整數線性規(guī)劃問題，可得到全局最優(yōu)解。

模型P2為二階可微非線性函數，對決策變量xie求二階偏導數，得到Hesse矩陣

(26)

因Aee的順序主子式

綜上，P1、P2均可求得全局最優(yōu)解。

3.2 基于Min-max Normalization的無量綱處理

目標函數式(19)指列車站內的總走行時間，量綱為時間；目標函數式(20)是到發(fā)線e占用時間和到發(fā)線平均占用時間的偏離程度，無量綱。采用Min-max Normalization(Min-max歸一化)進行無量綱處理。

通常地，Min-max 歸一化需分別單目標的極大值和極小值，即minZ1、maxZ1、minZ2、maxZ2，之后將x映射至(0,1)區(qū)間，得到

(27)

因此，

3.3 線性加權法

由最優(yōu)值分析可知，P1、P2均可求得全局最優(yōu)解，因此采用線性加權法，設置權重w1和w2，得到轉化后的模型為

(28)

(29)

(30)

(31)

xie+xje≤1 ?(i,j)∈Sij?e∈Ladt

(32)

xie+xjk≤1 ?(i,e,j,k)∈δiejk

(33)

(34)

(35)

?e∈Ladt?i∈Tmut

xie+xjk≤1 ?(i,e,j,k)∈φiejk

(36)

算法流程見圖8。

圖8 算法流程

4 算例驗證

選取北京南站京滬高速場(盡端式車站)、濟南西站(通過車站)為例，采用京滬高鐵周期化列車運行圖設計方案，以驗證模型、算法的有效性。

4.1 北京南站京滬高速場

北京南站京滬高速場共設12條到發(fā)線，其中14道、13道為京滬高速鐵路正線，其余為到發(fā)線，所有股道均能辦理旅客乘降作業(yè)。站場圖見圖9。

圖9 北京南站站場圖

表2 北京南站京滬高速場各到發(fā)線走行時間

由于無實際運營的周期化列車運行圖，采用以1 h為周期，單周期開行11對列車的理論周期化列車運行圖做案例研究。北京南站京滬高速場1 h周期化列車時刻表見表3。

表3 北京南站京滬高速場1 h周期化列車時刻表

(1)所有車底均按立折列車處理

圖10 車底交路

表4 北京南站京滬高速場列車到發(fā)時刻表Ⅰ

然而，實際運營中，北京南站京滬高速場的現(xiàn)有能力最多安排11列立折列車，且這些列車在到發(fā)線上的作業(yè)時間均為20 min，見圖11。

圖11 北京南站京滬高速場到發(fā)線運用方案

表4中11列立折列車在到發(fā)線上的作業(yè)時間超過30 min。將數據代入求解軟件為無解?？梢?，京滬高速場的能力不足以安排作業(yè)時間超過20 min的11列立折列車，因此，將其中部分立折列車改為始發(fā)、終到列車，并進行出入段處理。

(2)部分車底立折，部分車底出入段

因無法將時刻表中的11列立折列車全部安排完，所以進行小規(guī)模的遍歷，采用Matlab R2018b進行數據處理，利用Yalmip工具包調用Cplex求解，發(fā)現(xiàn)最多可安排8列立折列車。在此基礎上將其余3列立折列車分解得到6列始發(fā)終到列車，在到發(fā)時刻固定且到發(fā)線作業(yè)時間為15 min的前提下，始發(fā)列車看作于出發(fā)時刻前15 min從車輛段到達的立折列車，終到列車看作于到達時刻后15 min發(fā)往車輛段的立折列車。

以上述思路優(yōu)化得到最終結果見表5和圖12。由于站場能力限制，6列始發(fā)或終到列車仍然只能安排其中的2列終到列車(G6，G8)和1列始發(fā)列車(G17)，見表5。

表5 北京南站京滬高速場列車到發(fā)時刻表Ⅱ

圖14 北京南站京滬高速場到發(fā)線運用方案拼接

圖12 北京南站京滬高速場部分車底立折、部分車底出入段方案

后續(xù)可考慮將到發(fā)線作業(yè)時間定義為決策變量進行求解，而非固定成15 min；或是反饋回時刻表編制系統(tǒng)[18]，通過反饋調整列車時刻表和動車交路以減少對到發(fā)線的占用時間等來解決部分列車無法安排的問題。

在該算例中，模型P1和P2所得結果相同，見圖12，且兩方案的指標一致，即列車站內總走行時間均為79.7 min，方差均為38.99，因此該方案為最優(yōu)解，不再做協(xié)同優(yōu)化處理。

本文整理由程序得出的走行時間存在重疊的沖突列車集合，驗證集合的正確性和完整性后將求解方案映射至站場圖中，見圖13。手工校驗后，求解方案有效。

圖13 北京南站京滬高速場到發(fā)線運用方案(站場)

以圖12所示單周期方案進行拼接，結果見圖14，拼接后的方案未發(fā)生沖突，過表列車沖突成功消解。

求解方案單周期接發(fā)了8列立折列車、2列終到列車、1列始發(fā)列車。與理論上京滬高速場1 h內最多安排11列以20 min為標準進行作業(yè)的立折列車數量接近。但是在求解得到的方案中，列車對到發(fā)線的平均占用時間為33.73 min，而以20 min為標準進行作業(yè)的立折列車對到發(fā)線的占用時間為28 min，求解方案對到發(fā)線的總利用率更高。

η為到發(fā)線能力利用率即單周期內，各到發(fā)線被占用的時間與周期長度T的比值,其計算式為

(37)

求解方案與11列立折列車理論方案相比，各到發(fā)線的能力利用率總體更高，見表6。

表6 北京南站京滬高速場到發(fā)線能力利用率

4.2 濟南西站

由于北京南站為盡端式車站，以始發(fā)終到列車為主，顯示周期模式下能力緊張。進一步選取以通過列車為主的濟南西站進行分析，其站場圖見圖15。仍采用同一周期圖化列車運行圖，表7中列車種類4為通過列車。

圖15 濟南西站站場圖

求解方案單周期共接發(fā)了22列車，其中21列停站通過列車，1列不停站通過列車。以Z1和Z2的數值作為評判指標，將模型P1、模型P2方案、協(xié)同優(yōu)化方案進行比較。

該案例中，模型P1和P2所得方案不同，分別為圖16(a)和圖16(b)。將ω1和ω2取值0.5，即總走行時間和到發(fā)線均衡使用同等重要，使到發(fā)線運用方案在Z1最小和Z2最小之間協(xié)同，得到如圖16(c)方案，求解方案符合有效性和周期化運用要求。

表7 濟南西站1 h周期化列車時刻表

如圖17，模型P1方案的Z1為101.4 min，Z2為65.77；模型P2方案的Z1為112.4 min，Z2為13.83；協(xié)同優(yōu)化方案是對兩者的協(xié)同優(yōu)化，指標Z1與Z2介于兩者之間，分別是107.6 min和30.36。

圖16 濟南西站到發(fā)線運用方案

圖17 濟南西站目標函數值分析

4.3 不同站型下到發(fā)線運用方案對比

(1)到發(fā)線使用方案對比

北京南京滬高速場方案中無上下行車場區(qū)分，但因為始發(fā)、終到列車有出、入段作業(yè)，因此，終到列車G6、G8在18、19股道作業(yè)；始發(fā)列車G17在11股道作業(yè)。

濟南西站方案中有上下行車場區(qū)分，11列下行列車中有10列安排在車場1～6股道，為使到發(fā)線運用均衡將1列安排在12股道；11列上行列車中有10列安排在11～17股道，1列不停站列車由正線IX通過。

(2)咽喉區(qū)占用時間對比

咽喉區(qū)占用時間對比見表8，經計算，北京南站京滬高速場以1 h為周期的方案中對咽喉的總占用時間達到了79.7 min，其中11.8 min為出入段占用咽喉區(qū)的時間，67.9 min為接發(fā)列車占用咽喉區(qū)的時間；濟南西站以1 h為周期的方案中無出入段，對兩端咽喉區(qū)總占用時間均為53.8 min。

由于追蹤間隔時間大于列車站內的最大走行時間，所以接發(fā)車時并不會發(fā)生沖突；此外，濟南西站無出入段作業(yè)，因此接車與接車、發(fā)車與發(fā)車以及出入段進路不納入統(tǒng)計范圍。兩站咽喉區(qū)的敵對、平行進路數量見表9。

表8 咽喉區(qū)占用時間對比 min

表9 咽喉區(qū)進路交叉干擾數量對比(僅京滬高鐵方向) 條

算例中，濟南西站到發(fā)線能力相對富裕，兩站相比，主要原因有二：

(1)北京南站京滬高速場為盡端式車站，所有作業(yè)的進路均在一端咽喉區(qū)，且均是始發(fā)終到列車。做立折列車處理時，若列車接車時選擇14～19股道，則其相應的發(fā)車進路就會切割整個咽喉區(qū)；若接車時選擇8～13股道，雖緩解了發(fā)車時沖突多的問題，但其接車進路又橫跨了咽喉區(qū)。此外，因為以1 h為周期，導致在周期內一條到發(fā)線基本只能安排一列立折列車。

若做始發(fā)終到列車出入段處理，則終到列車可接入14～19股道，入段后由8～13股道發(fā)車，消除了立折列車必定會切割咽喉區(qū)的痛點。且因為出入段進路與接發(fā)車進路交叉的比例較低，可在一定程度上增加平行進路的數量，如表9中北京南站京滬高速場接車(出段)與接車(出段)、發(fā)車(入段)與發(fā)車(入段)和接車(出段)與發(fā)車(入段)的平行進路數較多的情況，便是因為考慮了出入段的進路。從案例中也可以看出，當部分列車做始發(fā)終到處理時，成功安排了相對更多的列車。

濟南西站為通過式車站，在本例中均為通過列車(包括停站通過和不停站通過)，且接發(fā)車進路分布在車站的兩端咽喉。因此通過濟南西站的列車只需要按照上、下行場的分布進行作業(yè)即可消除接、發(fā)車的沖突。

(2)北京南站京滬高速場的咽喉區(qū)能力與到發(fā)線能力不匹配。由(1)分析可知，北京南站京滬高速場中的立折列車一定會切割一次咽喉區(qū)，若使列車出入段可避免這類問題，但也由此出現(xiàn)始發(fā)、終到列車的接發(fā)車平行進路較少的情況。

如圖18(a)所示，若在8～13股道接車，列車必須且只能經由256-254-252-248去往到發(fā)線；然而，8～13股道的發(fā)車進路同樣需要經由248-252-254，導致這些股道無法同時進行接車作業(yè)和發(fā)車作業(yè)，限制了到發(fā)線的能力。

如案例中無法安排的G19，其出發(fā)時刻為44:32。G16_G9的到達時刻為47:38，兩者在走行時間上存在重疊部分。求解方案中，G16_G9的接車進路完全切割了8～13股道的接發(fā)車進路，因此即使股道8上沒有列車，G19也無法?？?。但若是在滿足車站設計條件的前提下增設如圖18(b)內紅線所示的道岔(300-302)即可疏解這類沖突，增加了8～13股道接車和發(fā)車的平行進路數量，從而提高咽喉區(qū)能力以進一步釋放到發(fā)線利用率。

圖18 北京南站京滬高速場咽喉區(qū)分析

5 結論

本文以周期化列車運行圖的特點和編制辦法為基礎，提出到發(fā)線周期化運用的編制流程，并指出3個技術難點；以列車在站內總走行時間最小、到發(fā)線運用最均衡構建了周期模式下車站到發(fā)線運用多目標優(yōu)化模型，利用Matlab、Cplex編程實現(xiàn)；以北京南京滬場和濟南西分別作為盡端式車站、通過式車站的代表進行算例研究，分析表明論文模型有效，過表列車沖突成功消解，為到發(fā)線運用方案周期化提供理論方法，但從算例也可以看出以始發(fā)終到為主的車站，周期模式下如果立折列車較多，折返之間較長時，到發(fā)線能力緊張。