高鐵站列車和調(diào)車作業(yè)計劃一體化編制方法

鐘明軒，樂逸祥，周磊山

(北京交通大學(xué)，交通運輸學(xué)院，北京100044)

0 引言

大型高鐵站是高速鐵路網(wǎng)中的關(guān)鍵節(jié)點，其作業(yè)質(zhì)量影響著整個高鐵路網(wǎng)的運輸效率。大型高鐵站通常站場規(guī)模大，接入方向多，結(jié)構(gòu)復(fù)雜，咽喉區(qū)平行進(jìn)路多，其接發(fā)車數(shù)量、站內(nèi)作業(yè)種類和作業(yè)復(fù)雜度都遠(yuǎn)超一般車站，站內(nèi)列車作業(yè)(進(jìn)出站、站臺停車等)和調(diào)車作業(yè)(轉(zhuǎn)線、出入段等)往往會相互影響，沖突頻繁，嚴(yán)重影響車站作業(yè)效率和質(zhì)量。雖然某些大站大多數(shù)情況下可以將各車場獨立考慮，并通過運行圖為不同方向列車給定列車徑路和站內(nèi)經(jīng)由車場，但是在各車場之間，特別是咽喉區(qū)，仍可能存在大量作業(yè)交叉干擾，因此，在考慮分方向指定列車作業(yè)方案的同時，仍需要將整個大站作為一個整體建模優(yōu)化。車站作業(yè)計劃作為車站運輸組織的主要依據(jù)，是保障車站運輸生產(chǎn)順利進(jìn)行的關(guān)鍵因素。車站作業(yè)計劃的編制和調(diào)整通常由人工完成，效率低，且質(zhì)量難以保證，特別是對于大型高鐵站，列車密度大、作業(yè)沖突繁雜且相互交織影響范圍廣，人工調(diào)整難度極大。因此，如何實現(xiàn)復(fù)雜高鐵站作業(yè)計劃的快速優(yōu)化編制，成為鐵路運輸生產(chǎn)中急需解決的關(guān)鍵問題之一。

本質(zhì)上，車站作業(yè)計劃的編制、調(diào)整和優(yōu)化屬于作業(yè)調(diào)度問題(Operation Scheduling Problem,OSP)，核心是根據(jù)列車運行圖或時刻表為每個列車的各項作業(yè)在規(guī)定的作業(yè)時間合理分配相應(yīng)的車站“資源”，包括：基礎(chǔ)設(shè)施(如軌道、站臺、閉塞區(qū)間等)、機車車輛/動車和人員等，以保證列車在車站按時、無沖突的完成各項技術(shù)作業(yè)，保障列車運行圖的實施。本文不考慮車站作業(yè)人員的調(diào)度調(diào)配問題，OSP 描述為在車站范圍內(nèi)為大量列車作業(yè)合理、高效地分配資源，同時，確保無作業(yè)沖突的作業(yè)調(diào)度問題。

本文針對復(fù)雜高鐵車站的作業(yè)優(yōu)化問題，綜合考慮列車和調(diào)車作業(yè)一體化的車站作業(yè)計劃編制的可行性、質(zhì)量和求解速度；基于車站平面圖和軌道電路構(gòu)建通用的高鐵站作業(yè)優(yōu)化模型(Operation Scheduling Model,OSM)；同時，針對實際OSM 具有巨量的變量及約束條件個數(shù)，提出一種基于拉格朗日松弛的求解算法，在不需要初始可行解的前提下，實現(xiàn)車站作業(yè)計劃的快速求解，并通過實例進(jìn)行驗證。

1 問題描述

根據(jù)列車在高鐵站的作業(yè)類型將其分為4類：終到列車、始發(fā)列車、通過列車和立折列車。主要調(diào)車作業(yè)包括：轉(zhuǎn)線、出入段、出入存車線，并基于列車方向、作業(yè)車場及股道的不同，細(xì)分為不同作業(yè)方案的列車。如圖1所示，每列列車在站內(nèi)至少進(jìn)行一組作業(yè)，根據(jù)作業(yè)類型將其分為靜態(tài)作業(yè)和動態(tài)作業(yè)。靜態(tài)作業(yè)指列車在股道停留完成的作業(yè)，在作業(yè)時間內(nèi)靜止；動態(tài)作業(yè)指列車在站內(nèi)的走行作業(yè)，通常會沿某條進(jìn)路從起點運行到終點。設(shè)定靜態(tài)作業(yè)的作業(yè)時間為一個可接受的作業(yè)時間窗；對于動態(tài)作業(yè)，考慮列車在走行過程中往往需要避免中途停止或刻意延長作業(yè)時間，實際生產(chǎn)中，作業(yè)時間雖然會在小范圍內(nèi)波動，但不會實時進(jìn)行調(diào)整，往往由調(diào)度人員給定作業(yè)完成時間便不再變化，故將動態(tài)作業(yè)時間設(shè)定為一個能夠充分完成作業(yè)的、適當(dāng)?shù)臉?biāo)準(zhǔn)時間值。

圖1 高鐵站作業(yè)工序示意Fig.1 Operations illustration for high-speed railway station

列車在站內(nèi)的列車作業(yè)和調(diào)車作業(yè)視為按照時間順序連續(xù)進(jìn)行的，為更好地描述列車的站內(nèi)作業(yè)集合，引入作業(yè)鏈的定義。

定義：列車i的作業(yè)集合{oi,j|0≤j≤τi}，若對于任意作業(yè)j(0≤j≤τi-1)，均有Ei,j=Si,j+1，則稱集合{oi,j|0≤j≤τi-1} 為列車i的作業(yè)鏈Ci。

其中，i為列車索引；j為列車作業(yè)索引；oi,j為列車i的作業(yè)j；τi為列車i的作業(yè)數(shù)目；Si,j、Ei,j分別為作業(yè)oi,j的開始、結(jié)束時間。如圖1所示，高鐵站內(nèi)各類列車的技術(shù)作業(yè)方案可以描述為將列車和調(diào)車等多個作業(yè)串聯(lián)的作業(yè)鏈，形成對應(yīng)的作業(yè)工序圖，每個作業(yè)的表現(xiàn)形式為資源或進(jìn)路的占用。根據(jù)實際情況，將立折列車視為共用車底的一次終到列車和一次始發(fā)列車的組合。基于列車種類及列車徑路，可匹配不同的作業(yè)鏈作為輸入條件之一，作業(yè)鏈與列車接發(fā)方向的進(jìn)站信號機位置及所銜接車場相關(guān)聯(lián)，從而確定每一項詳細(xì)作業(yè)內(nèi)容。此時，OSP可以描述為優(yōu)化站內(nèi)每次列車每項作業(yè)的作業(yè)時間和資源占用，在無沖突的情況下實現(xiàn)最大的作業(yè)效益或最低的資源使用成本，引入作業(yè)鏈概念后，可表示為按照作業(yè)鏈順序和時間約束，在解決進(jìn)路或資源占用沖突的情況下，依次為各項作業(yè)規(guī)劃作業(yè)時間、分配資源。

車站的OSP 問題屬于NP-hard 問題，在多項式事件范圍內(nèi)很難求到最優(yōu)解。目前，學(xué)者大多將其視為站臺分配問題[1-4]、復(fù)雜Job-shop問題[5-7]或資源分配問題[8-11]，目標(biāo)是基于現(xiàn)有車站作業(yè)方案優(yōu)化到發(fā)線運用，進(jìn)路分配或完成沖突疏解及最小化列車延誤等。部分學(xué)者研究車站作業(yè)計劃與列車時刻表的協(xié)同優(yōu)化問題[12-14]，以優(yōu)化車站資源運用或?qū)崿F(xiàn)計劃的協(xié)同編制。

通過對現(xiàn)有研究成果的總結(jié)分析發(fā)現(xiàn)：目前多數(shù)研究只針對到發(fā)線運用、接發(fā)車等常規(guī)列車作業(yè)安排，極少考慮站內(nèi)調(diào)車作業(yè)，大部分案例以簡單車站為主，車站的復(fù)雜度、列車作業(yè)數(shù)目遠(yuǎn)小于實際情況，對于存在轉(zhuǎn)線、出入段等調(diào)車作業(yè)的大型車站，模型和算法的適用性有限；大多數(shù)求解方法采用啟發(fā)式算法或結(jié)合啟發(fā)式算法和數(shù)學(xué)優(yōu)化算法，很少使用精確算法，較難評估解的質(zhì)量；絕大多數(shù)算法在求解時需要輸入初始解，求解效率依賴初始解的質(zhì)量，實際應(yīng)用效果有限。

2 車站作業(yè)優(yōu)化模型

目前，多數(shù)建模方法將站臺和到發(fā)線視為整體，進(jìn)路的沖突通過輪詢該進(jìn)路的敵對進(jìn)路進(jìn)行檢測和疏解，實現(xiàn)問題的簡化建模。本文根據(jù)車站軌道電路分布，將列車的各類作業(yè)進(jìn)路拆分為若干軌道電路區(qū)段(例如：股道、道岔和交叉渡線等)的集合，構(gòu)建基于微觀層面的車站作業(yè)優(yōu)化模型(OSM)，OSM通過微觀層面分配占用資源(進(jìn)路、股道等)，實現(xiàn)精細(xì)化的沖突判斷和占用成本計算。

2.1 符號含義

(1)引用下標(biāo)

i——列車索引，i∈I，I為列車集合；

N——站內(nèi)列車數(shù)目；

j——列車作業(yè)索引，j∈J，J為列車作業(yè)集合；

k——時間索引，k∈T，T為時間點集合；

h——股道索引，H為站內(nèi)股道數(shù)目；

r——進(jìn)路索引，r∈R，R為進(jìn)路集合，進(jìn)路由站內(nèi)資源構(gòu)成(股道，道岔，交叉渡線)，股道可視為特殊進(jìn)路；

l——道岔索引，L為站內(nèi)道岔數(shù)目；

m——交叉渡線索引，M為站內(nèi)交叉渡線數(shù)目；

w——列車作業(yè)方案索引；

n——迭代次數(shù)。

(2)參數(shù)定義

γ——本站列車作業(yè)計劃；

γi,w——列車i的作業(yè)方案w；

oi,j——列車i的作業(yè)j；

τi——列車i的作業(yè)數(shù)目；

Ai——列車i在本站的到達(dá)時間，對于始發(fā)列車Ai=-1；

Di——列車i在本站的出發(fā)時間，對于終到列車Di=-1；

——作業(yè)oi,j的最小作業(yè)時間；

——作業(yè)oi,j的最大作業(yè)時間；

μi——列車i的類型，1 為終到列車，0 為通過列車，-1為始發(fā)列車；

Rnext(r)——進(jìn)路r可銜接的下一進(jìn)路集合，Rnext(r)∈R；

Roperation(j)——列車作業(yè)j可占用的進(jìn)路集合，Roperation(j) ∈R。

(3)決策變量

Si,j——作業(yè)oi,j開始時間；

xi,j,k,r——列車i的作業(yè)j在時間點k占用進(jìn)路r狀態(tài)；

δi,j,k,h——列車i的作業(yè)j在時間點k占用股道h狀態(tài)；

θi,j,k,l——列車i的作業(yè)j在時間點k占用道岔l狀態(tài)；

Ei,j——作業(yè)oi.j結(jié)束時間；

νi,j,k——列車i的作業(yè)j在時間點k執(zhí)行狀態(tài)；

ρi,j,k,m——列車i的作業(yè)j在時間點k占用交叉渡線m狀態(tài)。

2.2 模型設(shè)計

設(shè)目標(biāo)函數(shù)為f(γ)，列車i在當(dāng)前車站作業(yè)方案的集合為γi，第w個作業(yè)方案γi,w的效益為ξw(γi,w)，γi,w={oi,j,r|0≤j≤τi,r∈Roperation(j)}，列車i的作業(yè)方案γi,w根據(jù)對應(yīng)作業(yè)鏈生成，各項作業(yè)oi,j,r已確定對應(yīng)占用進(jìn)路為r。令當(dāng)前站內(nèi)所有列車的效益之和為f(γ)，對應(yīng)目標(biāo)函數(shù)為

根據(jù)列車類型、接發(fā)方向等為列車匹配相應(yīng)的作業(yè)鏈，生成對應(yīng)的列車作業(yè)方案集合，并根據(jù)列車等級，為列車賦予效益值。當(dāng)列車在作業(yè)時間標(biāo)準(zhǔn)內(nèi)完成作業(yè)時，效益最大，不影響車站正常作業(yè)；當(dāng)列車作業(yè)時間過長，則會對其他列車作業(yè)產(chǎn)生負(fù)面影響，時間越長，影響越大，效益值越低；當(dāng)列車作業(yè)時間超過一定閾值，效益值為0，表示該列車作業(yè)對車站正常作業(yè)產(chǎn)生不可接受的負(fù)面影響。優(yōu)化目標(biāo)根據(jù)當(dāng)前時刻表，最小化站內(nèi)列車作業(yè)時間，減少作業(yè)成本，實現(xiàn)車站能力的最大化運用。列車效益與作業(yè)時間的關(guān)系通過函數(shù)表達(dá)。ξw(γi,w)與作業(yè)時間的關(guān)系如圖2所示，圖中，為列車某一作業(yè)的最大效益；為列車i作業(yè)j的標(biāo)準(zhǔn)作業(yè)時間，即不會對車站產(chǎn)生負(fù)面影響的時間點。對于動態(tài)作業(yè)，其作業(yè)時間固定，效益值為定值；對于靜態(tài)作業(yè)，在規(guī)定的標(biāo)準(zhǔn)作業(yè)時間內(nèi)，效益值不變，超過標(biāo)準(zhǔn)作業(yè)時間后，其效益值隨作業(yè)時間增加而降低。

圖2 列車i 作業(yè)j的效益曲線Fig.2 Profit curve for operation j of train i

令P表示原問題(Primal Problem)，Z表示目標(biāo)函數(shù)值，則OSM原始問題模型Model 1 (P)為

約束條件為

式(2)為OSM的目標(biāo)函數(shù)，表示站內(nèi)所有列車作業(yè)方案的效益之和。式(3)～式(5)為資源約束條件，表示在任意時間點，站內(nèi)資源都只能被不超過一個的列車作業(yè)占用，占用時間持續(xù)到該作業(yè)完成，當(dāng)某時間點k的資源占用次數(shù)大于1，表示包含該資源的作業(yè)進(jìn)路在此時存在沖突。式(6)～式(8)為當(dāng)進(jìn)路被某一列車作業(yè)占用時，該進(jìn)路上的所有資源(包括股道、道岔和交叉渡線等)均被占用。式(9)和式(10)為進(jìn)路與列車作業(yè)之間的關(guān)系，只有當(dāng)列車作業(yè)進(jìn)行時可以占用進(jìn)路。式(11)為需要接續(xù)的進(jìn)路之間的邏輯約束，表示列車只有在作業(yè)進(jìn)行中才可以占用股道或進(jìn)路。式(12)～式(15)為列車作業(yè)的時間約束：式(12)為作業(yè)時間窗，每項作業(yè)都必須在作業(yè)時間窗內(nèi)完成；式(13)和式(14)確保列車i的作業(yè)是按照作業(yè)鏈連續(xù)進(jìn)行的，即上一作業(yè)完成立即進(jìn)行下一作業(yè)，時間間隔與等待時間計入上一作業(yè)中；式(15)為站內(nèi)列車的作業(yè)方案必須滿足列車時刻表上列車在本站的到達(dá)/出發(fā)時間。

OSM 在實際問題中規(guī)模巨大，通過一般啟發(fā)式方法很難在合理的計算時間內(nèi)求得精確解，本文引入基于拉格朗日松弛的優(yōu)化算法求解問題，并通過可行化算法實現(xiàn)問題的精確求解。

3 基于拉格朗日松弛的算法設(shè)計

3.1 拉格朗日松弛對偶問題構(gòu)建

在Model 1 (P)中，式(3)～式(5)為資源約束，是問題最復(fù)雜的約束集合，定義不同列車之間的關(guān)系，確保最終解的可行性。采用拉格朗日松弛算法可以松弛式(3)～式(5)，表示可以在不考慮不同列車進(jìn)路沖突的情況下求解問題。令PLR表示拉格朗日松弛問題(Lagrangian Relaxation Problem),ZLR表示松弛問題函數(shù)值，則得到對應(yīng)松弛問題模型Model 2(PLR)為

滿足式(6)～式(15)

引入兩個新的變量，即

此時Model 2(PLRPLR)表示為

滿足式(6)～式(15)

令PLD表示拉格朗日松弛對偶問題(Lagrangian Relaxation Dual Problem),則Model 2(PLR)的松弛對偶問題模型Model 3(-PLD)表示為

滿足式(6)～式(15)

拉格朗日乘子λk,h，φk,l和εk,m分別為股道、道岔和交叉渡線在時間點k的資源占用懲罰。模型的上界為表示n次迭代中所有的松弛對偶問題解的函數(shù)值，下界為

Pbest=max{P(n)}，P(n)表示n次迭代中所有的原問題解的函數(shù)值。在對偶問題-PLD中，拉格朗日乘子λk,h，φk,l和εk,m的次梯度和資源懲罰乘子值更新公式為

式中：β——步長調(diào)節(jié)因子；

Z(n)——第n次迭代對偶問題PLD的目標(biāo)函數(shù)值；

——目標(biāo)函數(shù)值Z的期望，是當(dāng)前對偶問題最佳函數(shù)值和原問題最佳函數(shù)值的凸組合；

α(n)——初始值為1，當(dāng)多次迭代沒有改進(jìn)時可修改；

‖?‖——歐幾里得范數(shù)。

式(28)為步長計算公式。

3.2 拉格朗日松弛子問題求解

在Model 3(-PLD)中，每輪迭代都會更新乘子的值，但? 為常數(shù)，那么當(dāng)每個zi取最大值時，對應(yīng)目標(biāo)函數(shù)ZLR即為最大值。zi可以被視為單一列車i作業(yè)方案的效益。此時，主問題被分解為幾個求解單一列車最優(yōu)作業(yè)方案的子問題。對所有子問題求最優(yōu)解后，即可獲得對應(yīng)的松弛解。

單一列車作業(yè)方案的求解可以在可擴展的資源時空網(wǎng)絡(luò)上進(jìn)行描述，其所有作業(yè)方案進(jìn)路集合稱為限制進(jìn)路集合。如圖3所示，終到列車i自車站邊界點b1進(jìn)站的可行進(jìn)路有6條，每條股道停留時間為5～10 min，在每條進(jìn)站進(jìn)路的終點可鋪畫6條弧表示列車停站計劃(5～10 min)；若從列車所在股道到存車場有ω條進(jìn)路，則需要再分別鋪畫ω條弧表示這些調(diào)車作業(yè)進(jìn)路。圖3中增加了2個虛擬節(jié)點，作業(yè)起點和終點，在列車的限制進(jìn)路集合中，虛線弧對應(yīng)虛擬作業(yè)，表示作業(yè)接續(xù)，無權(quán)重；實線弧表示實際作業(yè)，權(quán)重等于作業(yè)方案效益值減去資源占用成本。根據(jù)作業(yè)鏈，可將列車的站內(nèi)列車作業(yè)和調(diào)車作業(yè)接續(xù)，形成作業(yè)方案，生成各類作業(yè)列車的限制進(jìn)路集合。

子問題求解需要尋找列車i效益值最大的作業(yè)方案，通過最短路算法，在圖3所示的限制進(jìn)路集合中尋找從起點到終點的最佳進(jìn)路及對應(yīng)的資源占用。

圖3 列車限制進(jìn)路集合Fig.3 Restricted route set based on a train operation plan

3.3 下界計算

目標(biāo)函數(shù)上界用拉格朗日松弛解計算，目標(biāo)函數(shù)下界需要將松弛解可行化后代入原問題求解。本文將啟發(fā)式規(guī)則與分支定界法相結(jié)合，在每輪迭代中快速對松弛解可行化，計算下界，計算過程如圖4所示。根據(jù)沖突檢測結(jié)果，依次篩選沖突點，構(gòu)建沖突點集合Q={q1,q2,…,qb}和各個點對應(yīng)的沖突列車作業(yè)方案子集qb={γ1,γ2,…,γi}，b表示沖突點索引。在沖突列車提取過程中，借鑒動態(tài)規(guī)劃思想，設(shè)置無后效性原則。

圖4 下界求解過程Fig.4 Procedure of lower bound generation

(1)將已提取的沖突列車作業(yè)方案設(shè)置為虛擬作業(yè)方案，不占用資源，后續(xù)其他沖突點和沖突列車的提取，不受已提取沖突列車的影響。

(2)每個沖突點對應(yīng)的沖突列車視為一組列車，不同組之間的列車作業(yè)方案求解相互獨立。

可行解求解過程如圖5所示，采用基于對稱性破缺的分支定界法依次求解各組沖突列車的可行作業(yè)方案。對稱性破缺的核心思想是通過增加一定的約束或其他方法來減少或消除等價解的個數(shù)，從而減少原問題的對稱性，加快求解速度。采用以下規(guī)則對列車可行解進(jìn)行剪枝：

圖5 可行解求解過程Fig.5 illustration of feasible solution generation

(1)列車作業(yè)方案與已有作業(yè)列車沖突，不可行；

(2)列車資源占用成本高，或使用占用次數(shù)過高的資源。

通過對單一列車可行解進(jìn)行剪枝，能夠在保留最優(yōu)解或近似最優(yōu)可行解的情況下，大幅度減少解空間的規(guī)模，提高求解速度。

絕大多數(shù)列車能夠快速獲得可行作業(yè)方案，但小部分列車在本輪迭代中可能存在無可行作業(yè)方案的情況。為保證車站作業(yè)方案整體可行性，確保數(shù)學(xué)意義可行解的存在，在本輪迭代中，當(dāng)列車無可行作業(yè)方案時，將其松弛解對應(yīng)作業(yè)方案設(shè)置為空，不占用資源，但作為懲罰，其效益值為0。將所有分組沖突列車的作業(yè)方案設(shè)置完畢后，即可獲得數(shù)學(xué)意義上的可行解，計算目標(biāo)函數(shù)下界。經(jīng)過多輪迭代和對比后即可獲得接近最優(yōu)解的可行解

3.4 基于拉格朗日松弛的算法流程

拉格朗日松弛算法求解過程如圖6所示。車站股道、道岔、交叉渡線設(shè)置拉格朗日乘子矩陣及資源占用次數(shù)矩陣(λk,h,Ck,h),(φk,l,Bk,l),(εk,m,Uk,m)，分別用于計算進(jìn)路占用成本和判斷作業(yè)沖突；迭代終止條件設(shè)置為達(dá)到最大迭代次數(shù)n=nmax或?qū)ε奸g隙Δ滿足要求。

圖6 算法流程Fig.6 Flow chat of heuristic algorithm

4 案例研究

本文以北京南站這一典型復(fù)雜繁忙的高鐵站為案例測試模型和算法。算法在Windows10 系統(tǒng)采用Visual Studio 2017 C#編程實現(xiàn)，并在Intel?Core?i7 CPU和4 GB 內(nèi)存的筆記本上進(jìn)行測試。北京南站車站平面如圖7所示，包括：29 條股道，118 個道岔，12 個交叉渡線，24 h 作業(yè)車數(shù)463 列，單一列車作業(yè)數(shù)3個以上。根據(jù)列車種類、列車徑路和接發(fā)方向，預(yù)先構(gòu)建22 類基礎(chǔ)作業(yè)鏈作為算法輸入條件之一，每類作業(yè)鏈包含多個作業(yè)方案，以京滬高速線終到入段的某次列車i為例，假設(shè)高速場列車停站作業(yè)oi,j的時間標(biāo)準(zhǔn)為20 min，30 min，其作業(yè)鏈包含374個作業(yè)方案。當(dāng)以分鐘為單位離散時間時，24 h的OSP 中包含(29+118+12)×1440 個乘子和463×3×(29+118+12)×1440個決策變量。

圖7 北京南站Fig.7 Layout of Beijing South Railway Station

假設(shè)列車效益值為1000，列車到發(fā)時間由時刻表確定，站內(nèi)作業(yè)時間根據(jù)實際數(shù)據(jù)和編圖規(guī)則確定，站內(nèi)作業(yè)包含調(diào)車作業(yè)。根據(jù)車站平面圖和基礎(chǔ)設(shè)施銜接關(guān)系，利用改進(jìn)Dijkstra 算法自動生成站內(nèi)所有列車進(jìn)路，構(gòu)建進(jìn)路集合R，通過簡單輪詢檢索規(guī)則生成進(jìn)路集合Rnext(r)，Roperation(j)，根據(jù)Rnext(r)和列車作業(yè)方案自動檢索。根據(jù)列車作業(yè)鏈，結(jié)合列車時刻表和車站技術(shù)作業(yè)規(guī)則，將作業(yè)鏈擴展為限制進(jìn)路集合，并生成作業(yè)方案集合γi，方法如圖3所示。

選擇3 個案例進(jìn)行測試，案例設(shè)置條件如表1所示。迭代過程的上界、下界變化如圖8所示。當(dāng)時間單位分別為1 min和15 s 時，時間索引為k∈[0,1440]和k∈[0,5760]。

圖8 最優(yōu)解迭代過程Fig.8 Iterative process of upper bound and lower bound

表1 案例參數(shù)設(shè)置Table 1 Parameter setting of cases

案例3 獲得的24 h 車站作業(yè)計劃資源利用率統(tǒng)計如圖9所示，高利用率資源統(tǒng)計如表2所示，并在圖7標(biāo)注。北京南站道岔分組如表3所示，道岔編號與實際一致。

表2 案例3高利用率資源統(tǒng)計Table 2 Resource statistics with high utilization rate for Case 3

表3 北京南站道岔分組Table 3 Turnout grouping of Beijing South Railway Station

圖9 案例3(24 h)車站作業(yè)計劃資源利用率統(tǒng)計Fig.9 Resource utilization statistics of 24-hour station operation plan for Case 3

如圖9所示，由于未考慮股道均衡運用，故早高峰7:00-10:00 股道平均利用率不高，高速場為45.93%(1 min)和45.51%(15 s)，城際場為54.76%(1 min)和57.06%(15 s)，甚至部分股道(高速場8、17、18、19)占用率為0。可見制約車站能力的主要因素為西側(cè)咽喉區(qū)通過能力，動車組出入存車線、出入段作業(yè)與廊坊、柳村方向接發(fā)車作業(yè)相互影響，導(dǎo)致西側(cè)咽喉區(qū)能力緊張。

所有案例均迭代至最大次數(shù)后，算法終止。案例計算結(jié)果如表4所示。當(dāng)時間單位為1 min 時，案例1，2，3的對偶間隙分別為1.17%，2.24%，1.94%；當(dāng)時間單位為15 s 時，對偶間隙分別為1.74%，1.94%，6.76%。所有計算結(jié)果的對偶間隙都小于10%，驗證了生成可行解的有效性。對于大規(guī)模高鐵站，在不需要初始可行解的前提下，在不超過20 min的時間內(nèi)，生成24 h的高質(zhì)量車站作業(yè)計劃是可以滿足實際需求的。案例結(jié)果表明了模型和算法的可行性和有效性。

表4 案例計算結(jié)果Table 4 Computation results of cases

5 結(jié)論

本文的研究目標(biāo)為實現(xiàn)復(fù)雜高鐵站高質(zhì)量車站作業(yè)計劃的快速求解。研究結(jié)果表明：OSM和拉格朗日松弛算法對大規(guī)模OSP求解效果良好，計算時間小于20 min，對偶間隙不超過10%；一體化的編制方法能夠在滿足列車到、發(fā)時刻的情況下，協(xié)調(diào)安排列車作業(yè)和調(diào)車作業(yè)，優(yōu)化站內(nèi)作業(yè)時間和瓶頸區(qū)域作業(yè)，提高作業(yè)效率，最大化車站能力；北京南站作業(yè)安排無沖突，表明基于微觀資源的進(jìn)路表示和作業(yè)鏈設(shè)置方法能夠處理復(fù)雜情況下的車站作業(yè)安排，無特殊條件設(shè)置，普適性強。