劉 敏，張伯駒，林 楓，安 迪，劉曉溪

（1.中國鐵道科學(xué)研究院集團(tuán)有限公司 運(yùn)輸及經(jīng)濟(jì)研究所，北京 100081； 2. 中國鐵路信息科技集團(tuán) 有限公司，北京 100844）

0 引言

編制車站作業(yè)計(jì)劃是傳統(tǒng)的運(yùn)輸組織方案優(yōu)化問題，是列車運(yùn)行圖編制的重要環(huán)節(jié)。劉敏等[1]依據(jù)車站辦理的列車結(jié)構(gòu)，考慮一定的緩沖時間要求，通過仿真編制高速鐵路車站作業(yè)計(jì)劃，測算車站通過能力。任禹謀等[2]引入滾動時域調(diào)度策略建立高速鐵路車站到發(fā)線動態(tài)調(diào)整模型，采用遺傳算法求解。應(yīng)恒[3]在車站軌道電路分段解鎖、列車密集到發(fā)、緊湊作業(yè)的場景下，以車站單方向追蹤列車到達(dá)方向列車間隔時間總和最小為優(yōu)化目標(biāo)，以到發(fā)線與進(jìn)路占用唯一性、整體性、到發(fā)線安全使用間隔、列車間隔時間、進(jìn)路沖突疏解等為約束，構(gòu)建高速鐵路列車進(jìn)路分配優(yōu)化模型。馬駟等[4]考慮列車晚點(diǎn)的情況，以車站作業(yè)過程占用車站設(shè)備的不均衡性最小和列車進(jìn)站延誤時間最短為目標(biāo)，建立后續(xù)列車進(jìn)路分配方案的動態(tài)調(diào)整模型。劉杰等[5]以作業(yè)計(jì)劃穩(wěn)定性強(qiáng)和接發(fā)車進(jìn)路條件優(yōu)為目標(biāo)，構(gòu)建高速鐵路車站股道與咽喉區(qū)運(yùn)用多目標(biāo)優(yōu)化模型，采用改進(jìn)的帶精英策略的非支配排序遺傳算法求解。甘志良[6]建立以符合股道固定使用方案、提高車站作業(yè)效率和計(jì)劃穩(wěn)定性為目標(biāo)的高速鐵路車站股道綜合運(yùn)用優(yōu)化模型，提出綜合考慮列車運(yùn)行方向、列車在站作業(yè)方式、列車種類3方面因素確定股道占用費(fèi)用的方法，基于多目標(biāo)遺傳算法的思想設(shè)計(jì)求解算法。鄧遠(yuǎn)冬[7]構(gòu)建列車晚點(diǎn)下高速鐵路車站股道運(yùn)用調(diào)整模型，設(shè)計(jì)基于拉格朗日松弛的求解算法。黃全等[8]以股道運(yùn)用和檢票口作業(yè)量均衡、接發(fā)列車交叉干擾程度最小為優(yōu)化目標(biāo)，建立高速鐵路車站作業(yè)計(jì)劃0-1整數(shù)規(guī)劃模型，設(shè)計(jì)蟻群算法求解。

大型高速鐵路車站一般與動車所相鄰，始發(fā)、終到、出入庫等各種類型的列車較多，存在大量的進(jìn)路交叉，人工編制方案的難度較高。給定列車時刻表和車底交路方案的情況下，全面考慮列車到發(fā)時刻調(diào)整，上水、吸污和轉(zhuǎn)線等作業(yè)安排，以及動車所出入庫等情形，提出優(yōu)化編制模型以及以自動編制過程為主、人機(jī)交互過程為輔的自動編制流程。采用自主開發(fā)的自動編制系統(tǒng)，實(shí)例驗(yàn)證優(yōu)化編制模型和自動編制流程。

1 大型高速鐵路車站作業(yè)分析

1.1 列車作業(yè)類型

在編制大型高速鐵路車站作業(yè)計(jì)劃時，一般將與其相鄰的動車所看作車站的一個接車和發(fā)車方向，將車站內(nèi)的列車作業(yè)類型分為接車（包括出庫）、發(fā)車（包括入庫）、通過、轉(zhuǎn)線4類，不同列車在車站的作業(yè)類型如表1所示。在站場條件允許（如啟用牽出線）的情況下，除通過和停站列車外，其他類型的列車均可考慮安排轉(zhuǎn)線作業(yè)。

表1 不同列車在車站的作業(yè)類型Tab.1 Types of train operation at station

1.2 車站路徑選擇

將列車作業(yè)的進(jìn)路依次連接，構(gòu)成列車在車站內(nèi)的路徑。大型高速鐵路車站的股道數(shù)量較多，每列車一般存在多條路徑，若該列車在車站有上水和吸污等作業(yè)要求，其車站路徑需滿足該要求。

安排轉(zhuǎn)線作業(yè)可在一定程度上優(yōu)化車站作業(yè)秩序，也在一定程度上增加車站作業(yè)負(fù)擔(dān)。以北京南站高速場為例，假定可利用牽出線組織轉(zhuǎn)線作業(yè)，19道具備吸污作業(yè)條件。對需進(jìn)行吸污作業(yè)的廊坊站立折列車，路徑1利用19道接發(fā)，不安排轉(zhuǎn)線作業(yè)，但發(fā)車進(jìn)路切割咽喉，與接車進(jìn)路產(chǎn)生交叉，車站路徑1如圖1所示；路徑2利用19道接車，利用牽出線轉(zhuǎn)線，利用11道發(fā)車，安排轉(zhuǎn)線作業(yè)，發(fā)車進(jìn)路不切割咽喉，車站路徑2如圖2所示。

圖1 車站路徑1Fig.1 First itinerary of the train station

圖2 車站路徑2Fig.2 Second itinerary of the train station

1.3 進(jìn)路占用時間

由于占用時間存在差異，將進(jìn)路分解為空間上互不包含的股道區(qū)段和咽喉區(qū)段，均稱為進(jìn)路區(qū)段，進(jìn)路區(qū)段的占用開始和結(jié)束時刻基本均可以列車到發(fā)時刻（或轉(zhuǎn)線作業(yè)的發(fā)到時刻）為基準(zhǔn)，提前或推遲固定的時長表示，進(jìn)路占用時間示意圖如圖3所示。其中，對于發(fā)車和通過作業(yè)，考慮出發(fā)追蹤要求，以出清區(qū)間第一離去閉塞分區(qū)為進(jìn)路占用結(jié)束時刻，對比進(jìn)路釋放時刻存在較小的冗余時間，對編制車站作業(yè)計(jì)劃的影響很小。

圖3 進(jìn)路占用時間示意圖Fig.3 Route occupation time

2 車站作業(yè)計(jì)劃優(yōu)化編制模型

大型高速鐵路車站作業(yè)計(jì)劃優(yōu)化編制的基本思路，是通過給定列車時刻表、車底交路方案以及列車到發(fā)時刻的調(diào)整范圍，全面考慮列車到發(fā)時刻調(diào)整、上水、吸污和轉(zhuǎn)線等作業(yè)安排，以及動車所出入庫等情形，優(yōu)化編制車站作業(yè)計(jì)劃，盡量為更多列車安排路徑，提高車站作業(yè)計(jì)劃的性能。因此，提出優(yōu)化編制模型的基本模型，考慮車站間隔時間、動車所出入庫先發(fā)后到間隔時間、限制連續(xù)追蹤列車數(shù)量約束，完善優(yōu)化編制模型。

2.1 基本模型

2.1.1 目標(biāo)函數(shù)

基本模型是從車站作業(yè)計(jì)劃的安排列車數(shù)量和整體性能2方面構(gòu)建目標(biāo)函數(shù)，其具體如下。

（1）盡量為更多列車安排路徑，考慮無法為所有列車安排路徑的可能性。

式中：L表示列車集合；Pa表示列車la∈L的備選路徑集合；xa,b為0-1變量，表示列車la是否選擇備選路徑pa,b。

（2）盡量提高車站作業(yè)計(jì)劃的性能。

式中：qa,b表示備選路徑pa,b的質(zhì)量，主要依據(jù)路徑所包含進(jìn)路的平行進(jìn)路數(shù)量。

（3）盡量減少轉(zhuǎn)線作業(yè)次數(shù)。式

中：da,b表示備選路徑pa,b安排轉(zhuǎn)線作業(yè)的次數(shù)。

2.1.2 約束條件

基本模型主要是從路徑選擇、股道停站時間、轉(zhuǎn)線作業(yè)走行時間、進(jìn)路區(qū)段占用4個方面考慮設(shè)置約束條件，其具體如下。

（1）路徑選擇約束，每列車最多選擇1條備選路徑，可能存在無法安排路徑的情況。

（2）股道停站時間約束。

式中：Sa,b表示備選路徑pa,b∈Pa的進(jìn)路區(qū)段集合，表示類型為股道（咽喉進(jìn)路）的進(jìn)路區(qū)段集合；和表示列車la在股道上的最小和最大停站時間；變量和表示列車la在股道上的到達(dá)和出發(fā)時刻。

（3）轉(zhuǎn)線作業(yè)走行時間約束。

式中：若備選路徑pa,b的進(jìn)路區(qū)段sa,b,c和sa,b,d對應(yīng)轉(zhuǎn)線進(jìn)路的出發(fā)和到達(dá)股道，用sa,b,c→sa,b,d表示；參數(shù)表示走行時間。

（4）進(jìn)路區(qū)段占用約束。

式中：常量M表示1個大數(shù)；常量d表示1 d時長；z為0-1變量，表示占用順序，僅當(dāng)2條路徑均被選擇時，約束有效，股道區(qū)段的占用時間范圍不能重疊，否則約束無效（恒成立）。若備選路徑pa,b的進(jìn)路區(qū)段sa,b,c和備選路徑pi,j的進(jìn)路區(qū)段si,j,k在空間上沖突，用sa,b,csi,j,k表示。

2.2 車站間隔時間約束

在進(jìn)路占用不沖突的情況下，車站各項(xiàng)間隔時間示意圖如圖4所示，虛線方框表示時刻相同。理論上，只要圖3所示的進(jìn)路占用時間參數(shù)取值準(zhǔn)確，則相互沖突的股道和進(jìn)路的占用時間范圍不會重疊，保證行車安全所要求的車站各項(xiàng)間隔時間。以先到后通間隔時間為例，前行停站列車的接車進(jìn)路釋放后，才可為后行通過列車準(zhǔn)備進(jìn)路，前行列車的到達(dá)時刻與后行列車的通過時刻的間隔時間為先到后通間隔時間。

圖4 車站各項(xiàng)間隔時間示意圖Fig.4 Train headway under different conditions at station

2.3 動車所出入庫線先發(fā)后到間隔時間約束

對于可接發(fā)列車的動車所出入庫線，需額外考慮先發(fā)后到間隔時間要求，動車所出入庫線先發(fā)后到間隔時間示意圖如圖5所示。情形A滿足車站內(nèi)的進(jìn)路占用無沖突，但兩車在動車所出入庫線上的運(yùn)行必然沖突。情形B為兩車的動車所出入庫線先發(fā)后到間隔時間構(gòu)成，只有前行出發(fā)列車出清區(qū)間且動車所進(jìn)路釋放后，后行到達(dá)列車才可辦理動車所發(fā)車作業(yè)。

圖5 動車所出入庫線先發(fā)后到間隔時間示意圖Fig.5 Train headway of entry and exit line of EMU depot under condition of departuring train first and then arriving train

動車所出入庫線先發(fā)后到間隔時間約束如下。

式中：變量和表示列車la的到達(dá)和出發(fā)時刻；表示該動車所出入庫的先發(fā)后到間隔時間；z為0-1變量，表示到發(fā)順序。若路徑pa,b的進(jìn)路區(qū)段sa,b,c位于接車進(jìn)路上，路徑pi,j的進(jìn)路區(qū)段si,j,k位于發(fā)車進(jìn)路上，從同一動車所出入庫線接發(fā)，用si,j,k?sa,b,c表示。

2.4 限制連續(xù)追蹤列車數(shù)量約束

基本模型通過選擇質(zhì)量更好的路徑（主要依據(jù)路徑所包含進(jìn)路的平行進(jìn)路數(shù)量）、減少轉(zhuǎn)線作業(yè)次數(shù)來提高方案的性能。在列車到發(fā)順序確定的情況下，可通過分配必要的緩沖時間，限制連續(xù)追蹤列車數(shù)量，提高方案的穩(wěn)定性，連續(xù)追蹤發(fā)車最多3列示意圖如圖6所示。

圖6 連續(xù)追蹤發(fā)車最多3列示意圖Fig.6 Consecutive departure of no more than three trains

限制連續(xù)追蹤列車數(shù)量約束如下。

式中：若連續(xù)追蹤發(fā)車（或接車）數(shù)量最多為m，考慮連續(xù)追蹤發(fā)車（或接車）數(shù)量大于m的列車群，假定列車數(shù)量為n，n＞m，順序編號為l1—ln， 追蹤間隔時間為t追蹤，必要的緩沖時間為t緩沖。

3 車站作業(yè)計(jì)劃自動編制技術(shù)

3.1 自動編制流程設(shè)計(jì)

優(yōu)化編制模型為混合整數(shù)規(guī)劃模型，采用分支切割或列生成算法求解。針對大型高速鐵路車站，列車數(shù)量較多，備選路徑集合的規(guī)模較大，0-1變量的數(shù)量較多，直接求解時間較長。為此，自動編制流程采用迭代的思路，在每次迭代過程中盡量縮小求解規(guī)模。自動編制流程以自動編制過程為主，人機(jī)交互過程為輔，自動編制流程如圖7所示。其中，自動編制過程包含求初始解、時段優(yōu)化、隨機(jī)優(yōu)化、性能優(yōu)化等功能，均利用優(yōu)化編制模型求解；設(shè)計(jì)人機(jī)交互過程，以利用專家知識和經(jīng)驗(yàn)，同時提供智能輔助功能。

圖7 自動編制流程Fig.7 Automatic track planning process

（1）驗(yàn)證路徑，即驗(yàn)證每個列車的每條備選路徑是否可用。例如，對終到—始發(fā)列車，若備選路徑包含轉(zhuǎn)線作業(yè)，但停站時間較短，該備選路徑不可用。

（2）求初始解，即重新安排所有列車的路徑，每次選擇少量列車安排路徑，保持其他列車的路徑方案?？赡艽嬖诓糠至熊嚥荒馨才怕窂降那樾?。

（3）時段優(yōu)化，即按照時段順序，每次選擇一定時間范圍內(nèi)的所有列車，調(diào)整選定列車的路徑方案，保持其他列車的路徑方案。

（4）隨機(jī)優(yōu)化，即設(shè)置一定的迭代次數(shù)，每次隨機(jī)選擇少量未安排路徑的列車和已安排路徑的列車，調(diào)整選定列車的路徑方案，保持其他列車的路徑方案。

（5）性能優(yōu)化，即完成所有列車的路徑安排后，保持所有列車的路徑方案和到發(fā)順序，僅調(diào)整到發(fā)時刻，通過分配緩沖時間，限制連續(xù)追蹤列車數(shù)量，提高方案的穩(wěn)定性。

（6）人機(jī)交互，人機(jī)交互過程分為即時調(diào)整和全局調(diào)整，提供智能輔助功能，人機(jī)交互過程如圖8所示。即時調(diào)整指每次人工調(diào)整1列車的方案（包括調(diào)整時刻或股道、安排或取消轉(zhuǎn)線作業(yè)等）后，自動檢測和提示沖突，調(diào)用優(yōu)化編制模型，使車站作業(yè)計(jì)劃可行；全局調(diào)整指人工調(diào)整多列車的方案后，人工調(diào)用優(yōu)化編制模型，使車站作業(yè)計(jì)劃可行。

圖8 人機(jī)交互過程Fig.8 Human-computer interactive process

3.2 實(shí)例研究

根據(jù)前述優(yōu)化編制模型和自動編制流程，自主開發(fā)完成“高速鐵路車站作業(yè)計(jì)劃自動編制系統(tǒng)V1.0”。以北京南站高速場為實(shí)例，假定啟用牽出線（目前未啟用），測試方案共143列車，包含終到—始發(fā)（立折）列車84列、終到—入段列車19列、出段—始發(fā)列車40列，包含時速300 km和350 km 2種速度級，滿足車站到發(fā)間隔時間要求，但未考慮車站作業(yè)計(jì)劃的可行性。列車到發(fā)時刻調(diào)整幅度設(shè)為2 min，在接車股道、發(fā)車股道、牽出線的最小停留時間分別設(shè)為16 min，20 min，12 min，轉(zhuǎn)線進(jìn)路走行時間設(shè)為5 min，動車所出入庫線先發(fā)后到間隔時間設(shè)為20 min。車站間隔時間參數(shù)取值如表2所示。

表2 車站間隔時間參數(shù)取值 minTab.2 Parameter values of train headway at station

測試電腦為Intel Core i9處理器，64G內(nèi)存，采用的自動編制過程為：驗(yàn)證路徑—求初始解—時段優(yōu)化（多次）。在2 h內(nèi)完成137列車的路徑安排，剩余6列需人工調(diào)整，得到北京南站高速場作業(yè)計(jì)劃如圖9所示，其中與牽出線相關(guān)的連線表示轉(zhuǎn)線作業(yè)，測試顯示自動編制技術(shù)的全面性和可行性。

圖9 北京南站高速場作業(yè)計(jì)劃Fig.9 Operation planning of high speed yard at Beijing South Station

4 結(jié)束語

隨著高速鐵路網(wǎng)密度越來越高，大型高速鐵路車站的始發(fā)、終到、出入庫等各種類型的列車越來越多，采用人工方式編制車站作業(yè)計(jì)劃難以快速高效完成，亟需研究大型高速鐵路車站作業(yè)計(jì)劃自動編制技術(shù)。大型高速鐵路車站自動編制技術(shù)由優(yōu)化編制模型和自動編制流程構(gòu)成，其中優(yōu)化編制模型全面考慮大型高速鐵路車站的各種情形，特別考慮轉(zhuǎn)線作業(yè)安排、動車所出入庫等情形，實(shí)用性強(qiáng)；自動編制流程以自動編制過程為主，人機(jī)交互過程為輔，從而能在保證車站作業(yè)計(jì)劃質(zhì)量的同時，較快速地完成方案的編制。