大規(guī)模貨物列車運(yùn)行圖優(yōu)化編制的一種拉格朗日松弛啟發(fā)式算法

江 峰，倪少權(quán)

(1. 西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院， 四川 成都 610031；2. 西南交通大學(xué) 全國鐵路列車運(yùn)行圖編制研發(fā)培訓(xùn)中心， 四川 成都 610031)

編制列車運(yùn)行圖需考慮各類約束條件限制，其實(shí)質(zhì)是疏解各列車運(yùn)行線對運(yùn)輸資源的潛在占用沖突，進(jìn)而確定各列車運(yùn)行線的時空位置，是NP-hard問題[1-3]。目前貨物列車運(yùn)行圖編制依靠人工推線求解，結(jié)果依賴始發(fā)時刻[1-2]，自動化水平較低。

作為鐵路運(yùn)輸組織的核心問題，列車運(yùn)行圖優(yōu)化引起了國內(nèi)外學(xué)者的廣泛關(guān)注。文獻(xiàn)[4-5]以列車運(yùn)行圖排序模型研究單線貨物列車運(yùn)行圖的優(yōu)化編制方法。文獻(xiàn)[6]考慮相鄰區(qū)間銜接關(guān)系及車站間隔時間，優(yōu)化單線非追蹤平行列車運(yùn)行圖。文獻(xiàn)[7]根據(jù)列車運(yùn)行軌跡的有限性和相鄰列車的強(qiáng)約束性構(gòu)造時空域窗口，滾動求解列車運(yùn)行圖。文獻(xiàn)[3]給定列車優(yōu)先級，以追蹤間隔時間和連發(fā)間隔時間為約束，提出多目標(biāo)綜合函數(shù)，建立列車運(yùn)行圖優(yōu)化編制模型并求解。文獻(xiàn)[8]采用廣度搜索法生成高峰小時周期列車運(yùn)行圖，以深度搜索法添加非周期列車運(yùn)行線，研究計(jì)算機(jī)編制周期性列車運(yùn)行圖關(guān)鍵技術(shù)。文獻(xiàn)[9]以總效益最大為目標(biāo)建立整數(shù)規(guī)劃模型，對其進(jìn)行拉格朗日松弛，以動態(tài)規(guī)劃方法求解了包含17個車站，18列旅客列車及8列貨物列車的列車運(yùn)行圖。文獻(xiàn)[10]考慮路網(wǎng)中總旅行時間最優(yōu)，基于時空網(wǎng)絡(luò)構(gòu)建貨物列車徑路優(yōu)化模型，采用基于拉格朗日松弛的啟發(fā)式算法求解。

大規(guī)模條件下列車運(yùn)行圖優(yōu)化編制問題無多項(xiàng)式時間有效算法，通常需對原問題進(jìn)行分解以縮小規(guī)模、加快求解速度[4-5,7,9-10]?，F(xiàn)有研究主要通過列車始發(fā)時刻及沿途總停時優(yōu)化列車旅行速度[2,4-7,9-10]，但部分研究簡化了約束條件(如忽略天窗約束)[9-10]，部分研究解決問題規(guī)模較小[3,6,8-9]，部分研究缺乏對所得解的優(yōu)劣評價[4-5,7-8]。

貨物列車運(yùn)行圖受旅客列車運(yùn)行圖限制，是典型的非周期列車運(yùn)行圖，現(xiàn)有基于拉格朗日松弛的列車運(yùn)行圖優(yōu)化編制方法具有優(yōu)化解質(zhì)量可評估、模型拓展性好等優(yōu)點(diǎn)，是非周期列車運(yùn)行圖優(yōu)化編制的有效方法[9-10]。

本文根據(jù)我國貨物列車運(yùn)行圖優(yōu)化編制需要，以時空網(wǎng)絡(luò)中的路徑優(yōu)化描述列車運(yùn)行圖優(yōu)化編制問題，通過對時空網(wǎng)絡(luò)時間軸的離散化處理，將出發(fā)、到達(dá)間隔時間等線路能力約束及停站需求、天窗限制等運(yùn)輸組織約束表示為時空網(wǎng)絡(luò)中的節(jié)點(diǎn)選擇限制，從而疏解不同列車運(yùn)行線對運(yùn)輸資源的潛在占用沖突。上述問題的實(shí)質(zhì)是一類最短路徑求解問題，通過給定各列車運(yùn)行線初始利潤，并對始發(fā)時刻調(diào)整及總停時延長設(shè)置罰數(shù)，計(jì)算各列車運(yùn)行線實(shí)際利潤，以全圖所有列車運(yùn)行線總利潤最大為目標(biāo)構(gòu)建整數(shù)規(guī)劃模型，根據(jù)模型特點(diǎn)對其進(jìn)行拉格朗日松弛求解，基于拉格朗日松弛問題所得時空網(wǎng)絡(luò)中各節(jié)點(diǎn)罰數(shù)，以啟發(fā)式算法迭代優(yōu)化貨物列車運(yùn)行圖。通過參數(shù)設(shè)置提出不同優(yōu)化策略，對京九線北京西至阜陽區(qū)段內(nèi)439列貨物列車進(jìn)行運(yùn)行圖優(yōu)化編制實(shí)驗(yàn)并分析結(jié)果，驗(yàn)證了算法有效性。

1 問題描述

貨物列車運(yùn)行圖優(yōu)化編制是在旅客列車運(yùn)行圖基礎(chǔ)上，滿足各列車始發(fā)時間域及總停站時間限制，對各列車始發(fā)時刻及全程總停時進(jìn)行優(yōu)化的過程。

作為列車具體時刻時空位置的圖解，列車運(yùn)行圖可用有向時空網(wǎng)絡(luò)G=(N,A)描述，其中:點(diǎn)集N中元素代表時空域中某列車運(yùn)行線所有經(jīng)過的節(jié)點(diǎn)，在每個車站，可分為到達(dá)節(jié)點(diǎn)U及出發(fā)節(jié)點(diǎn)W；弧集A中元素代表列車運(yùn)行線組成部分，由車站到達(dá)及出發(fā)節(jié)點(diǎn)確定。S為全體車站集合;T=(1,…,t)為全體列車集合;Sj=(fj,…,lj)?S為列車j∈T所經(jīng)車站集合(共s站)，列車j的運(yùn)行線可表示為一定約束下G中自fj起，途經(jīng)fj+1,…,lj-1至lj止的一條路徑，其包含的弧集合為Aj,Aj?A、節(jié)點(diǎn)集合為Nj,Nj?N。

對全圖設(shè)置一個虛擬出發(fā)點(diǎn)σ和虛擬終到點(diǎn)ε標(biāo)注各列車的始發(fā)、終到，則有

N={σ,ε}∪

(W1∪…∪Ws-1)∪(U2∪…∪Us)

列車j的運(yùn)行線可用與其有關(guān)的弧子集Aj表示，其包含有：

(1) 由虛擬出發(fā)點(diǎn)σ至列車j始發(fā)站出發(fā)節(jié)點(diǎn)v∈Wfj的始發(fā)弧(σ,v)。

(2) 在中間站i,i∈Sj{fj,lj}由該站到達(dá)節(jié)點(diǎn)u∈Ui至該站出發(fā)節(jié)點(diǎn)v∈Wi的停留弧(u,v)，其中出發(fā)節(jié)點(diǎn)v∈Wi由該站到達(dá)節(jié)點(diǎn)及該列車運(yùn)行線在站停留時間確定。

(3) 在區(qū)間(i,i+1)內(nèi)由車站i出發(fā)節(jié)點(diǎn)v∈Wi至i+1站到達(dá)節(jié)點(diǎn)u∈Ui+1的運(yùn)行弧(v,u)，在出發(fā)節(jié)點(diǎn)確定情況下，到達(dá)節(jié)點(diǎn)u∈Ui+1由列車在區(qū)間內(nèi)的運(yùn)行時間確定。

(4) 從列車j終點(diǎn)站到達(dá)節(jié)點(diǎn)u∈Ulj至虛擬終到點(diǎn)ε的終止弧(u,ε)。

其中各弧的時間跨度含義為：運(yùn)行弧(v,u)時間跨度為列車j在區(qū)間(i,i+1)的運(yùn)行時分，由列車區(qū)間運(yùn)行標(biāo)尺確定；停留弧(u,v)時間跨度為列車j在車站i的停站時間，當(dāng)列車在該站通過時取值為0。

一個包含5個車站、5條列車運(yùn)行線的簡單示例，見圖1。其中，K1、K2為旅客列車，H1、H2、H3為貨物列車，A、B、C為技術(shù)站，其余為中間站，設(shè)貨物列車在技術(shù)站作業(yè)時間、各站出發(fā)、到達(dá)間隔時間均為4 min，以時空網(wǎng)絡(luò)中路徑表示各列車運(yùn)行線，由于旅客列車運(yùn)行線的限制，引起了H2、H3在b站的技術(shù)停站及H3在B站停時的延長。

由于運(yùn)輸資源時空分配的有限性，各列車運(yùn)行線可能產(chǎn)生占用運(yùn)輸資源的潛在沖突(如圖1中H3、K1次在B站，H2、K1次在b站，H2、H3次在b站)，貨物列車運(yùn)行圖優(yōu)化編制的關(guān)鍵是疏解上述潛在沖突，即在各類約束條件及旅客列車運(yùn)行線造成的時空網(wǎng)絡(luò)節(jié)點(diǎn)選擇限制下，受限時空網(wǎng)絡(luò)中的最短路徑求解問題[4,9-10]。

2 貨物列車運(yùn)行圖優(yōu)化編制模型

2.1 問題假設(shè)

列車運(yùn)行圖優(yōu)化編制需考慮多種影響因素，為更好地確定研究范圍，針對列車運(yùn)行線鋪畫這一列車運(yùn)行圖優(yōu)化編制本質(zhì)問題，做出如下假設(shè)：

(1) 我國主要干線均已復(fù)線化，因此以上下行線路固定使用的復(fù)線區(qū)間為背景；列車在區(qū)間內(nèi)可追蹤運(yùn)行，追蹤間隔時間由相鄰車站出發(fā)、到達(dá)間隔時間最大值決定。

(2) 車站間隔時間與列車運(yùn)行狀態(tài)有關(guān)，為簡化分析，假設(shè)各站出發(fā)、到達(dá)間隔時間固定且已知。

(3) 車站進(jìn)路安排與車站站型有關(guān)，暫不考慮進(jìn)路安排問題，忽略進(jìn)路沖突并假設(shè)各站能力充足。

(4) 不考慮列車運(yùn)行圖均衡性，假設(shè)各列車最優(yōu)始發(fā)時刻給定，并可在一定范圍內(nèi)調(diào)整。

(5) 旅客列車運(yùn)行線不可調(diào)整。

上述假設(shè)可簡化問題建模及數(shù)據(jù)存儲且不影響問題一般性。

2.2 約束條件

為確定時空網(wǎng)絡(luò)中各節(jié)點(diǎn)位置關(guān)系，將1 d以分鐘為單位離散為1到q，q=1 440，θ(v)為節(jié)點(diǎn)v∈N所處時刻，兩節(jié)點(diǎn)間時間差在θ(u)>θ(v)的情況下，可表示為Δ(v,u)=θ(u)-θ(v)；在θ(u)<θ(v)的情況下，可表示為Δ(v,u)=θ(u)-θ(v)+q，以uv表示Δ(v,u)>Δ(u,v)，即節(jié)點(diǎn)v在時空網(wǎng)絡(luò)中對應(yīng)時間早于節(jié)點(diǎn)u。

且Nj與Aj間一一對應(yīng)。

對列車j及其途徑節(jié)點(diǎn)v∈∪j∈TNj：xa為0-1變量，xa=1表示弧a為任意列車運(yùn)行線組成部分，其他為0；yv為0-1變量，yv=1表示節(jié)點(diǎn)v被某列車運(yùn)行線經(jīng)過，其他為0；zjv為0-1變量，zjv=1表示列車j的運(yùn)行線經(jīng)過節(jié)點(diǎn)v，其他為0。

對兩相鄰列車j、k，在車站i∈(Sj{lj})∩(Sk{lk})包含的運(yùn)行弧(v1,u1)∈Aj，(v2,u2)∈Ak，v1,v2∈Wi，u1,u2∈Ui+1需滿足行車組織約束、停站需求約束、天窗約束、列車運(yùn)行線唯一性約束及相關(guān)連接約束。行車組織約束包括：

(1) 列車在i站出發(fā)時間差不小于該站出發(fā)間隔時間di，即Δ(v1,v2)≥di,v1v2，見圖2。

設(shè)w為列車運(yùn)行線可選節(jié)點(diǎn)(下同)，相關(guān)約束可表示為對任意i∈S{s},v∈Wi，Δ(v1,v2)

( 1 )

(2) 兩列車在i站到達(dá)時間差不小于該站到達(dá)間隔時間ai，即Δ(u1,u2)≥ai,u1u2，見圖3。

相關(guān)約束可表示為對任意i∈S{1},u∈Ui，Δ(u1,u2)

( 2 )

(3) 兩列車運(yùn)行線在區(qū)間內(nèi)不相交，設(shè)v1v2,u2u1，見圖4。

設(shè)區(qū)間內(nèi)列車k速度高于列車j，相關(guān)約束可表示為對相鄰車站i和i+1，列車運(yùn)行線j、k相應(yīng)節(jié)點(diǎn)(v1,u1)∈Aj，(v2,u2)∈Ak，v1,v2∈Wi，u1,u2∈Ui+1的選擇限制，即圖4中4個節(jié)點(diǎn)中至多3個節(jié)點(diǎn)被選擇

zjv1+zju1+zkv2+zku2≤3

( 3 )

式(3)包括對出發(fā)節(jié)點(diǎn)及到達(dá)節(jié)點(diǎn)的選擇限制，在區(qū)間運(yùn)行標(biāo)尺固定情況下，可將其表示為對出發(fā)節(jié)點(diǎn)的選擇限制[10]。

θ(v3)=max[θ(v1)+di,θ(v1)+ai+1+tj-tk]

式中：tj、tk分別為列車j、k在區(qū)間(i,i+1) 內(nèi)的運(yùn)行時分。

由式( 1 )～式( 3 )可知，v1、v3及v2、v4至多有一個節(jié)點(diǎn)被列車j或k的運(yùn)行線選擇，見圖5。

同時到達(dá)節(jié)點(diǎn)可行性可由式( 2 )保證，則區(qū)間不相交約束可表示為

( 4 )

基于2.1節(jié)所做假設(shè)，列車追蹤間隔時間可由式( 1 )、式( 2 )保證。

各列車運(yùn)行線需滿足停站需求約束及天窗約束。

停站需求約束可表示為：

(4) 停站需求約束限制最短停時內(nèi)出發(fā)節(jié)點(diǎn)選擇

( 5 )

天窗約束保證天窗期內(nèi)任何列車不得從該站出發(fā)，見圖7。

天窗約束可表示為：

(5) 天窗約束限制v1與v2間出發(fā)節(jié)點(diǎn)的選擇

( 6 )

此外，列車運(yùn)行線還應(yīng)滿足唯一性約束：

(6) 各列車運(yùn)行線至多選擇1個始發(fā)弧

( 7 )

(7) 各列車運(yùn)行線進(jìn)入與離開節(jié)點(diǎn)v弧數(shù)量相等

( 8 )

(8) 各節(jié)點(diǎn)至多被一條列車運(yùn)行線選擇

( 9 )

相關(guān)連接約束為：

(9) 弧構(gòu)成約束

(10)

(10) 節(jié)點(diǎn)選擇約束

(11)

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

貨物列車運(yùn)行圖優(yōu)化目標(biāo)通常為減少全程總停時、提高旅行速度[4-5]，其他優(yōu)化目標(biāo)可在上述目標(biāo)下通過合理確定始發(fā)時刻實(shí)現(xiàn)。本文在各貨物列車運(yùn)行線理想始發(fā)時刻給定條件下，以始發(fā)時刻調(diào)整及列車全程停時總延長為主要考慮因素構(gòu)建目標(biāo)函數(shù)。

列車運(yùn)行線由Gj=(Nj,Aj)中弧構(gòu)成，需滿足2.2節(jié)所提出的各類約束條件。全圖列車運(yùn)行線總利潤最大為目標(biāo)構(gòu)建目標(biāo)函數(shù)為

(12)

pa=p(σ,v)+p(u,v)

p(σ,v)=πj-αjυ(v)

p(u,v)=-βjμ(u,v)

υ(v)=|θ(v)-θ(fj)|

式中：pa為列車j運(yùn)行線中所有構(gòu)成弧a∈Aj利潤和，由構(gòu)成該運(yùn)行線的始發(fā)弧和停留弧利潤之和表示；p(σ,v)為始發(fā)弧(σ,v)，v∈Wfj的利潤；p(u,v)為停留弧μ(u,v)，u∈Ui,v∈Wi,i∈Sj{fj,lj}的利潤；πj為給定列車j的運(yùn)行線的一個初始利潤；αj、βj為相應(yīng)參數(shù)；υ(v)為實(shí)際始發(fā)點(diǎn)v對應(yīng)出發(fā)時刻與計(jì)劃出發(fā)時刻θ(fj)的偏離；μ(u,v)為第i站實(shí)際停時與計(jì)劃停時的差值。

約束條件為式( 1 )、式( 2 )、式( 4 )～式(11)。

3 模型求解

3.1 約束條件處理

原模型中式( 5 )、式( 6 )與列車特征及編圖區(qū)段運(yùn)輸組織條件有關(guān)，求解過程中通過對列車信息及時空網(wǎng)絡(luò)的預(yù)處理考慮此部分約束，具體做法為：

同時，類似對式( 5 )、式( 6 )的處理方式，將列車運(yùn)行圖中旅客列車運(yùn)行線占用的節(jié)點(diǎn)及各旅客列車運(yùn)行線引起的不滿足式( 1 )、式( 2 )、式( 4 )、式( 9 )、式(11)的相關(guān)節(jié)點(diǎn)設(shè)為禁選。

3.2 原問題的拉格朗日松弛

式(12)及式( 1 )、式( 2 )、式( 4 )～式( 9 )構(gòu)成了一個0-1整數(shù)規(guī)劃模型，實(shí)際問題對應(yīng)規(guī)模龐大，無法在有效時間內(nèi)精確求解，通常以最優(yōu)可行解為求解目標(biāo)[9-11]。

拉格朗日松弛技術(shù)通過將影響問題求解的難約束添加拉格朗日乘子后吸收入目標(biāo)函數(shù)，從而減小問題規(guī)模、加速求解，廣泛應(yīng)用于大規(guī)模整數(shù)規(guī)劃的啟發(fā)式算法設(shè)計(jì)[11-12]。基于文獻(xiàn)[9]所述方法，對原問題進(jìn)行拉格朗日松弛加速求解，根據(jù)松弛問題所得對偶信息設(shè)計(jì)啟發(fā)式算法對原問題最優(yōu)可行解進(jìn)行迭代求解。

拉格朗日松弛的關(guān)鍵是確定松弛約束，即模型中影響求解速度的難約束[11-12]。原問題中行車組織約束式( 1 )、式( 2 )、式( 4 )反映列車運(yùn)行線間相互影響，是一類簇約束。以約束式( 1 )為例，對每一個可能出發(fā)節(jié)點(diǎn)w，違反約束式( 1 )的所有節(jié)點(diǎn)均不可被其他列車運(yùn)行線選擇，即與節(jié)點(diǎn)w不兼容，因此約束式( 1 )實(shí)際上包含多個約束條件，其數(shù)量與di有關(guān)。此類簇約束會使模型規(guī)模急劇增加，是影響模型求解的主要因素。

由此確定對原模型中的行車組織約束進(jìn)行松弛。對約束式( 1 )、式( 2 )、式( 4 )分別添加拉格朗日乘子后加入目標(biāo)函數(shù)得原問題的拉格朗日松弛問題

(13)

式中：C為與節(jié)點(diǎn)v不相容弧的集合，含義為由相應(yīng)約束決定的經(jīng)過與節(jié)點(diǎn)v不兼容節(jié)點(diǎn)的弧的集合；λC1、λC2為對應(yīng)的拉格朗日乘子。

對式(13)進(jìn)行整

(14)

拉格朗日松弛問題中行車組織約束被解除，在拉格朗日乘子一定的條件下其求解是一類簡單的最短路問題，可由線性規(guī)劃方法快速求解[9-11]，對應(yīng)各列車運(yùn)行線的解即為其拉格朗日松弛解，其利潤為拉格朗日利潤。計(jì)算全圖各列車運(yùn)行線拉格朗日利潤，若大于零則將其加入解集從而求得D(Z)。由于原問題進(jìn)行拉格朗日松弛后目標(biāo)函數(shù)增加、可行域擴(kuò)大，因此有D(Z)>Z，即D(Z)為原問題的一個上界[11-12]。

當(dāng)且僅當(dāng)拉格朗日乘子全部為0時，D(Z)最優(yōu)解與Z最優(yōu)解相等并達(dá)到全局最優(yōu)，此時各列車運(yùn)行線均為滿足約束條件的實(shí)際可行解，但該最優(yōu)解通常無法求得[11]。拉格朗日乘子不為0時，D(Z)中各列車運(yùn)行線的拉格朗日松弛解不完全符合行車組織約束，可能為實(shí)際非可行解。

3.3 基于拉格朗日松弛的啟發(fā)式算法

D(Z)中包含各節(jié)點(diǎn)拉格朗日罰數(shù)這一對偶信息，其意義是時空網(wǎng)絡(luò)中各節(jié)點(diǎn)的選擇“費(fèi)用”。當(dāng)某節(jié)點(diǎn)的拉格朗日罰數(shù)為0時，表明各列車運(yùn)行線在該節(jié)點(diǎn)不產(chǎn)生潛在占用沖突，即各列車運(yùn)行線在該節(jié)點(diǎn)的選擇“費(fèi)用”為0；當(dāng)某節(jié)點(diǎn)的拉格朗日罰數(shù)不為0時，表明多條列車運(yùn)行線在該節(jié)點(diǎn)存在潛在占用沖突，即各列車運(yùn)行線在該節(jié)點(diǎn)的選擇“費(fèi)用”不為0。列車運(yùn)行線鋪畫對運(yùn)輸資源占用的潛在沖突就以各節(jié)點(diǎn)拉格朗日罰數(shù)的形式體現(xiàn)，由此可根據(jù)各節(jié)點(diǎn)拉格朗日罰數(shù)作為啟發(fā)信息求解各列車運(yùn)行線實(shí)際可行解。

求解列車運(yùn)行線實(shí)際可行解需考慮行車組織約束并確定各列車運(yùn)行線的鋪畫順序。各節(jié)點(diǎn)選擇“費(fèi)用”會影響列車運(yùn)行線的拉格朗日利潤，列車運(yùn)行線拉格朗日利潤較高說明其與其他列車運(yùn)行線的潛在沖突較少，由此根據(jù)各列車運(yùn)行線拉格朗日利潤降序確定鋪畫順序，優(yōu)先鋪畫潛在沖突較少的列車運(yùn)行線。

在始發(fā)時間域內(nèi)考慮始發(fā)時刻調(diào)整、總停時延長引起的罰數(shù)并選擇拉格朗日罰數(shù)為0的節(jié)點(diǎn)規(guī)避運(yùn)輸資源占用沖突，以實(shí)際利潤最大為目標(biāo),根據(jù)深度搜索原則遍歷具體列車運(yùn)行線的所有可行解[8]，若該列車運(yùn)行線實(shí)際利潤大于零，說明其存在實(shí)際可行解并存儲所得結(jié)果，全圖各列車運(yùn)行線實(shí)際可行解之和即為原問題的一個可行解，記為F(Z)。上述求解過程考慮了拉格朗日罰數(shù)為0這一節(jié)點(diǎn)選擇限制，可行域縮小，因此有F(Z)≤Z，即F(Z)是Z的一個下界[11-12]。

D(Z)目標(biāo)函數(shù)值與拉格朗日乘子λh取值有關(guān)，可通過次梯度法更新λh優(yōu)化D(Z)[11-12]，λh的更新可由Fisher提出的公式進(jìn)行[12]

(15)

式中:UB、LB分別為算法當(dāng)前最優(yōu)上界和最優(yōu)下界，分別對應(yīng)D(Z)當(dāng)前最優(yōu)解及F(Z)當(dāng)前最優(yōu)可行解；ρ為給定的非負(fù)步長；τ為由當(dāng)前D(Z)決定的全局次梯度向量；τh為λh對應(yīng)約束的次梯度向量。

根據(jù)更新的拉格朗日乘子求解F(Z)即可對其進(jìn)行迭代優(yōu)化[9]。實(shí)際問題中，上述算法所得解的質(zhì)量可由最優(yōu)上界評估，滿足一定條件時可認(rèn)為已求得最優(yōu)可行解[12]。

算法開始時，以全圖所有列車初始利潤之和作為全圖總利潤并存儲為當(dāng)前最優(yōu)上界以開始迭代，上述啟發(fā)式算法的終止條件設(shè)置為：(1)迭代次數(shù)達(dá)到設(shè)定上限；(2)算法運(yùn)行時間達(dá)到設(shè)定上限；(3)當(dāng)前最優(yōu)上界與當(dāng)前最優(yōu)下界間差值小于設(shè)定值；(4)各拉格朗日乘子為0。算法流程見圖8。

4 實(shí)例驗(yàn)證

以京九線北京西至阜陽區(qū)段實(shí)際數(shù)據(jù)為例進(jìn)行驗(yàn)證。該區(qū)段包括55個車站，全長855 km，根據(jù)2015年5月編制的列車運(yùn)行圖數(shù)據(jù)，全線共開行列車711列，其中貨物列車439列，列車構(gòu)成見表1。

表1 列車構(gòu)成

“*”表示客車標(biāo)尺，歸類為旅客列車。

根據(jù)實(shí)際數(shù)據(jù)設(shè)定各貨物列車經(jīng)停站及停時。以添加起停車附加時分的松弛運(yùn)行標(biāo)尺作為列車區(qū)間運(yùn)行時分驗(yàn)證算法有效性，保證結(jié)果可行性的同時增加列車運(yùn)行線冗余度。需說明的是上述松弛運(yùn)行標(biāo)尺可能會影響旅行速度，但實(shí)驗(yàn)結(jié)果顯示原圖貨物列車平均旅行速度仍得到了不同程度改善，證明了算法有效性。

視各列車重要程度相同并設(shè)定初始利潤為10 000、總停時最大延長為210 min，以列車實(shí)際始發(fā)時刻為初始布點(diǎn)、始發(fā)時間域?yàn)槌跏疾键c(diǎn)的±20 min，次梯度法求解拉格朗日乘子時起始步長ρ為1，若迭代10次后最優(yōu)上界未發(fā)生改變則減半ρ值，當(dāng)前最優(yōu)上界與當(dāng)前最優(yōu)下界差值設(shè)為當(dāng)前最優(yōu)上下界差值的0.1%。

由2.3節(jié)知，算法計(jì)算與參數(shù)αj、βj有關(guān)。αj、βj除表示列車始發(fā)時刻偏離及總停時延長造成的罰數(shù)外，另一意義是列車始發(fā)時刻及全程停時總延長重要程度的界定，因此可根據(jù)優(yōu)化需要調(diào)整參數(shù)αj、βj以不同策略對列車運(yùn)行圖進(jìn)行優(yōu)化編制。本文采取3種參數(shù)設(shè)置策略分6組進(jìn)行測試并分析所得結(jié)果，其中1、2組為始發(fā)時刻優(yōu)先策略，3、4組為旅行速度優(yōu)先策略，5、6組為均衡策略。

列車運(yùn)行圖優(yōu)化編制對時效性要求不高，為得到更好的結(jié)果，設(shè)置算法運(yùn)行時間上限為12 h、迭代次數(shù)上限為500次，相關(guān)算法基于C語言編程實(shí)現(xiàn)，實(shí)驗(yàn)并在一臺Intel Core2 2.33 GHz，2 GB內(nèi)存的個人計(jì)算機(jī)上進(jìn)行。

4.1 始發(fā)時刻優(yōu)先策略

設(shè)置αj>βj優(yōu)先選擇列車運(yùn)行線可行方案中始發(fā)時刻總調(diào)整值較小的解。統(tǒng)計(jì)最優(yōu)上界、最優(yōu)下界、全圖貨物列車始發(fā)時刻總調(diào)整值、全程停時總延長值、算法迭代次數(shù)、計(jì)算時間、優(yōu)化后平均旅行速度、旅行速度改善比率等指標(biāo)見表2，算法因迭代次數(shù)達(dá)到上限而終止。

不同參數(shù)下算法上界、下界及約束數(shù)量隨迭代次數(shù)變化曲線見圖9。

表2 始發(fā)時刻優(yōu)先策略指標(biāo)統(tǒng)計(jì)

列車種類 參數(shù)設(shè)置 αjβj算法指標(biāo)優(yōu)化后平均旅行速度/(km·h-1)旅行速度改善比率/%技術(shù)直達(dá)始發(fā)直達(dá)煤炭、石油直達(dá)直通貨物區(qū)段貨物摘掛及小運(yùn)轉(zhuǎn)其他全圖平均101最優(yōu)下界7093799.039.590.03最優(yōu)上界7107354.558.9821.91始發(fā)時刻總調(diào)整值/min39935.6315.98全程停時總延長值/min1221140.9412.28迭代次數(shù)?50050.138.18計(jì)算時間/s3736141.7740.8340.440.0041.956.08技術(shù)直達(dá)始發(fā)直達(dá)煤炭、石油直達(dá)直通貨物區(qū)段貨物摘掛及小運(yùn)轉(zhuǎn)其他全圖平均201最優(yōu)下界7099557.039.56-0.05最優(yōu)上界7102647.559.1422.24始發(fā)時刻總調(diào)整值/min38135.6315.98全程停時總延長值/min1282340.9112.21迭代次數(shù)?50049.847.55計(jì)算時間/s3701141.6940.5640.440.0041.816.44

“*”表示算法因上下界差值達(dá)到設(shè)定標(biāo)準(zhǔn)而終止。

4.2 旅行速度優(yōu)先策略

設(shè)置αj<βj優(yōu)先選擇列車運(yùn)行線可行方案中總停時延長較小的解，結(jié)果見表3。

不同參數(shù)下算法上界、下界及約束數(shù)量隨迭代次數(shù)變化曲線見圖10。

表3 旅行速度優(yōu)先策略指標(biāo)統(tǒng)計(jì)

列車種類 參數(shù)設(shè)置 αjβj算法指標(biāo)優(yōu)化后平均旅行速度/(km·h-1)旅行速度改善比率/%技術(shù)直達(dá)始發(fā)直達(dá)煤炭、石油直達(dá)直通貨物區(qū)段貨物摘掛及小運(yùn)轉(zhuǎn)其他全圖平均110最優(yōu)下界?7021310.040.672.75最優(yōu)上界7021308.559.8923.79始發(fā)時刻總調(diào)整值/min239037.3321.52全程停時總延長值/min963043.1318.29迭代次數(shù)5653.4215.28計(jì)算時間/s458743.2345.7540.650.4943.7211.30技術(shù)直達(dá)始發(fā)直達(dá)煤炭、石油直達(dá)直通貨物區(qū)段貨物摘掛及小運(yùn)轉(zhuǎn)其他全圖平均120最優(yōu)下界?6922247.040.722.28最優(yōu)上界6922243.060.5425.13始發(fā)時刻總調(diào)整值/min243337.4021.74全程停時總延長值/min926643.3218.82迭代次數(shù)2853.1014.59計(jì)算時間/s216043.2245.7240.650.5243.7211.30

“*”表示算法因上下界差值達(dá)到設(shè)定標(biāo)準(zhǔn)而終止。

4.3 均衡策略

設(shè)置αj=βj忽略優(yōu)先級差異均衡選擇列車運(yùn)行線方案，結(jié)果見表4。

不同參數(shù)下算法上界、下界及約束數(shù)量隨迭代次數(shù)變化曲線見圖11。

表4 均衡策略全圖指標(biāo)統(tǒng)計(jì)

“*”表示算法因上下界差值達(dá)到設(shè)定標(biāo)準(zhǔn)而終止。

4.4 結(jié)果分析

實(shí)驗(yàn)結(jié)果顯示，與原圖相比拉格朗日松弛啟發(fā)式算法所得各類貨物列車旅行速度得到了不同程度的優(yōu)化，全圖貨物列車平均旅行速度由39.28 km/h提升至41.81～43.72 km/h(視優(yōu)化策略而定)。

算法性能受列車運(yùn)行圖編制策略的影響，具體體現(xiàn)在：

(1) 不同策略下全圖列車始發(fā)時刻總調(diào)整值、全程停時總延長值不同。始發(fā)時刻優(yōu)先策略下，全圖始發(fā)時刻總調(diào)整值較??；旅行速度優(yōu)先策略下全圖停時總延長值較小；均衡策略介于二者之間，同時相同策略下算法對參數(shù)不敏感，見圖12。

(2) 不同策略下全圖總利潤(最優(yōu)下界)、列車平均旅行速度不同。全圖總利潤最大值為7 099 557.0，最小值為6 882 300.0，分別在旅行速度優(yōu)先策略、均衡策略下達(dá)到；列車平均旅行速度最高為43.72 km/h，最低為41.81 km/h，分別在旅行速度優(yōu)先策略、始發(fā)時刻優(yōu)先策略下達(dá)到，見圖13。

(3) 旅行速度優(yōu)先及均衡策略下算法收斂較快；始發(fā)時刻優(yōu)先策略下計(jì)算時間較長。原因是始發(fā)時刻優(yōu)先策略下啟發(fā)式算法需遍歷的可行解數(shù)量增加，從而引起迭代步數(shù)及計(jì)算時間的增長。

5 結(jié)論

根據(jù)貨物列車運(yùn)行圖優(yōu)化編制需求，提出大規(guī)模貨物列車運(yùn)行圖優(yōu)化編制算法代替人工編圖，將貨物列車運(yùn)行圖優(yōu)化編制問題轉(zhuǎn)化為受限時空網(wǎng)絡(luò)中最優(yōu)路徑求解問題，考慮各類約束建立整數(shù)規(guī)劃模型，結(jié)合模型特點(diǎn)對原問題進(jìn)行拉格朗日松弛并以啟發(fā)式算法迭代求解貨物列車運(yùn)行圖。

基于3種不同策略的驗(yàn)證表明，該方法能考慮不同優(yōu)化需求，是大規(guī)模貨物列車運(yùn)行圖優(yōu)化編制的有效算法。

算法計(jì)算時間受優(yōu)化策略影響，問題規(guī)模增大時，可采用性能更好的計(jì)算機(jī)以提高計(jì)算效率。下一步將考慮車站能力約束，研究列車運(yùn)行圖及車站到發(fā)線運(yùn)用計(jì)劃一體化優(yōu)化編制方法。