大型高速鐵路車(chē)站作業(yè)計(jì)劃 自動(dòng)編制技術(shù)研究

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

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

0 引言

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

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

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

1.1 列車(chē)作業(yè)類(lèi)型

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

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

1.2 車(chē)站路徑選擇

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

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

圖1 車(chē)站路徑1Fig.1 First itinerary of the train station

圖2 車(chē)站路徑2Fig.2 Second itinerary of the train station

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

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

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

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

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

2.1 基本模型

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

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

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

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

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

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

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

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

2.1.2 約束條件

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

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

（2）股道停站時(shí)間約束。

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

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

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

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

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

2.2 車(chē)站間隔時(shí)間約束

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

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

2.3 動(dòng)車(chē)所出入庫(kù)線(xiàn)先發(fā)后到間隔時(shí)間約束

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

圖5 動(dòng)車(chē)所出入庫(kù)線(xiàn)先發(fā)后到間隔時(shí)間示意圖Fig.5 Train headway of entry and exit line of EMU depot under condition of departuring train first and then arriving train

動(dòng)車(chē)所出入庫(kù)線(xiàn)先發(fā)后到間隔時(shí)間約束如下。

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

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

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

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

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

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

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

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

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

圖7 自動(dòng)編制流程Fig.7 Automatic track planning process

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

（2）求初始解，即重新安排所有列車(chē)的路徑，每次選擇少量列車(chē)安排路徑，保持其他列車(chē)的路徑方案?？赡艽嬖诓糠至熊?chē)不能安排路徑的情形。

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

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

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

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

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

3.2 實(shí)例研究

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

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

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

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

4 結(jié)束語(yǔ)

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