基于改進(jìn)列生成算法的高速列車開行方案優(yōu)化研究

蒲 松， 呂紅霞,2,3， 陳釘均,2,3， 倪少權(quán),2,3

(1. 西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031；2. 西南交通大學(xué) 全國鐵路列車運(yùn)行圖編制研發(fā)培訓(xùn)中心，四川 成都 610031；3. 綜合交通運(yùn)輸智能化國家地方聯(lián)合工程實(shí)驗(yàn)室，四川 成都 610031)

高速旅客列車開行方案編制計劃(High Speed Railway Passenger Train Line Planning Problems,HSRPTLP)是旅客列車運(yùn)行計劃的核心環(huán)節(jié)，簡稱開行方案。開行方案在給定路網(wǎng)設(shè)施的條件下，根據(jù)起訖站間客流量確定列車的運(yùn)行路徑、開行對數(shù)、等級與停站方案等要素，并盡可能地降低運(yùn)輸企業(yè)的運(yùn)營成本與旅客的出行成本。

影響HSRPTLP因素眾多，優(yōu)化內(nèi)容包括多個方面，因而建模和求解均存在一定難度。既有研究幾乎均對HSRPTLP進(jìn)行簡化，如Bussieck、 Claessens、杜欣等[1-4]在已知列車停站方案與客流分配的基礎(chǔ)上，建立整數(shù)規(guī)劃模型優(yōu)化列車運(yùn)行路徑、開行對數(shù); Borndorfer、付慧伶、佟璐等[5-7]預(yù)先給定停站方案，協(xié)同優(yōu)化列車運(yùn)行路徑與客流徑路;Chang、Park等[8-9]預(yù)先確定列車的起訖站，從運(yùn)輸企業(yè)與旅客兩方面出發(fā)，建立多目標(biāo)整數(shù)規(guī)劃模型確定列車開行對數(shù)、運(yùn)行路徑、停站方案及客流分配，并分別用于研究臺灣、韓國高速列車開行方案問題;史峰等[10-11]考慮運(yùn)輸企業(yè)與旅客之間不對等的博弈關(guān)系(Stackelber博弈)，建立雙層規(guī)劃模型，但因結(jié)構(gòu)較復(fù)雜，很難得到全局最優(yōu)解[12]。HSRPTLP屬于NP-hard問題[1-3，5]，沒有有效的多項(xiàng)式算法，傳統(tǒng)的分支定界算法、拉格朗日松弛算法等很難在有效時間內(nèi)獲得最優(yōu)解。蟻群算法、模擬退火算法、遺傳算法等智能算法雖然能在有效時間內(nèi)獲得滿意解，但很難保證解的質(zhì)量。

實(shí)際上，HSRPTLP模型中蘊(yùn)含著多商品流結(jié)構(gòu),而列生成算法可以將具有多商品流結(jié)構(gòu)的模型分解為主問題(Master Problem,MP)與其對偶問題(Dual Master Problem, DMP)，也稱為子問題，有效地降低HSRPTLP的復(fù)雜度，并得到全局最優(yōu)解[5,13]。但若使用標(biāo)準(zhǔn)的列生成算法求解HSRPTLP，DMP是基于客流分配的網(wǎng)絡(luò)設(shè)計，仍然比較復(fù)雜，求解比較困難[9]。鑒于此，本文對Park等[9]的研究拓展，并考慮高速鐵路線路上的列車開行方案(一般要求客流均應(yīng)有直達(dá)列車提供服務(wù)，不需考慮客流換乘)。模型上，將列車運(yùn)行路徑與客流徑路的生成合并，簡化現(xiàn)有模型中多商品流結(jié)構(gòu)，并且增加列車編組的情形；算法上，改進(jìn)列生成算法，綜合使用行生成與列生成策略，有效將DMP分解，彌補(bǔ)標(biāo)準(zhǔn)列生成算法的不足?，F(xiàn)有研究表明[1-3,9]，系統(tǒng)分離方法可以通過預(yù)先分離客流，有效將多等級(不同速度)的列車開行方案轉(zhuǎn)化為多個1種等級列車的開行方案。因此，只需考慮1種等級的列車開行方案。

1 建立HSRPTLP模型

1.1 基本概念

路段：相鄰車站間的軌道。

鐵路網(wǎng)：以車站為節(jié)點(diǎn)，路段為邊構(gòu)成的網(wǎng)絡(luò)。

列車運(yùn)行路徑：由列車始發(fā)站、途經(jīng)路段及列車終到站構(gòu)成的路徑。

列車非停站弧：列車直接經(jīng)過車站i、j，并且在i、j間所有中間站不停站，則稱弧ij為列車的非停站弧。因此，列車的所有非停站弧構(gòu)成列車的停站方案，同時確定列車的運(yùn)行路徑。

客流OD：起訖站間客流。

列車OD：列車起訖站簡稱。

客流徑路：旅客的乘車方案，由客流的起點(diǎn)站、列車的非停站弧、客流的終點(diǎn)站構(gòu)成。

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

HSRPTLP需要考慮運(yùn)輸企業(yè)與旅客雙方的利益。因此，優(yōu)化開行方案目標(biāo)為

目標(biāo)1 盡可能減小運(yùn)輸企業(yè)運(yùn)營成本；

目標(biāo)2 盡可能減小旅客的旅行成本。

運(yùn)輸企業(yè)的成本主要由列車開行的數(shù)量和列車總運(yùn)行公里組成，可以分為固定成本和可變成本。其中固定成本包括鐵路線路、車站等各種固定設(shè)備和動車組等移動設(shè)施的投資費(fèi)用。多數(shù)研究[1-6,8-10]都對固定成本進(jìn)行簡化處理：由于開行方案的研究對象是列車，所以固定成本僅和列車開行數(shù)量有關(guān)，即固定成本是開行1列列車必須產(chǎn)生的成本?？勺兂杀局饕c列車運(yùn)行里程有關(guān)，即列車每公里所產(chǎn)生的成本。因此，目標(biāo)1可以表示為

( 1 )

由于高速旅客列車的上座率有嚴(yán)格的限制，擁擠費(fèi)用[10]影響比較小，旅客的旅行成本主要由旅行時間刻畫[1-6,8-9]。因此，目標(biāo)2可以表示為

( 2 )

其中，tsi為列車在i站的停站時間。

1.3 約束條件

HSRPTLP的約束主要有滿足客流需求與運(yùn)輸能力限制兩大類約束。滿足客流需求是開行方案編制的基本原則，運(yùn)輸能力主要指各路段(區(qū)間)的最大通過能力、各車站接發(fā)列車能力等，基本的約束條件表述為

客流守恒，各支客流OD途經(jīng)各車站的客流量守恒，即

( 3 )

滿足客流需求，經(jīng)過列車l的非停站弧ij的所有客流OD不超過列車l的載客總量，即

( 4 )

最小載客量限制，經(jīng)過列車l的非停站弧ij的所有客流OD不低于列車l的最小載客量，即

l∈Lij∈r(l)

( 5 )

受列車編組方式的單一性限制，旅客列車的編組是固定編組。因此，每列列車的編組模式為單組或者重聯(lián)，即

( 6 )

( 7 )

式中：yl為0-1變量，表示列車的編組方式，當(dāng)列車編組方式為單組時，取1，否則為0；M為一個較大的常數(shù)。

路段(區(qū)間)通過能力的限制，主要是從安全、資源限制等因素考慮，經(jīng)過各路段(區(qū)間)的列車總數(shù)不超過其最大通過能力，即

( 8 )

車站接發(fā)車(包括辦理始發(fā)、終到與中間停站列車業(yè)務(wù))能力約束，即

( 9 )

(10)

式中：N為非負(fù)整數(shù)集合。

1.4 模型的復(fù)雜度分析

HSRPTLP的優(yōu)化模型是多目標(biāo)規(guī)劃模型，而多目標(biāo)規(guī)劃模型將大大增加問題的復(fù)雜度。同文獻(xiàn)[4-9]，利用權(quán)重法將多目標(biāo)規(guī)劃轉(zhuǎn)化為單目標(biāo)規(guī)劃，即

(11)

HSRPTLP是NP-hard問題，假設(shè)路網(wǎng)是僅含n個車站的客運(yùn)專線，則共有非停站弧n!條，整數(shù)變量個數(shù)為

約束條件個數(shù)為

模型的約束與變量隨著路網(wǎng)規(guī)模的增大而呈指數(shù)規(guī)模的增長，即使是對小規(guī)模的實(shí)例，也很難在有限的時間內(nèi)找到高質(zhì)量的解，甚至連找到可行解都很困難。因此，根據(jù)模型特點(diǎn)，設(shè)計基于列生成與行生成的啟發(fā)式算法。

2 列生成算法求解模型

2.1 主問題的構(gòu)造

設(shè)Ω=(L,F,v(L),Cap(L))為主問題的解空間，L、F、v(L)、Cap(L)分別表示列車集合、對應(yīng)列車的開行對數(shù)集合、列車的非停站弧集合及編組方式集合。因規(guī)模較大，所以在求解的過程中給出Ω的1個子集，其規(guī)模遠(yuǎn)遠(yuǎn)小于Ω，并且在每次迭代中逐漸生成。此時，主問題變?yōu)橄拗频闹鲉栴}(Restricted Master Problem, RMP)，相應(yīng)的子問題變?yōu)橄拗频淖訂栴}(Dual Restricted Master Problem,DRMP)。

線性規(guī)劃中一般含有耦合約束與塊狀約束，標(biāo)準(zhǔn)列生成算法運(yùn)用DW分解法分解耦合式( 8 )、式( 9 )構(gòu)造RMP，其對偶問題與塊狀約束一起構(gòu)成DRMP。DRMP為RMP提供新增列車的信息(運(yùn)行路徑、停站方案)，并將列車的信息以“列”的形式增加到主問題的約束中[9,13]。列車生成算法能有效的將原問題進(jìn)行分解，從而減小原問題計算的復(fù)雜度，但對于HSRPTLP，DRMP仍然比較復(fù)雜[9]。因此，本文采用另一種方式生成主問題，即將所有約束(耦合約束、塊狀約束)均放入RMP中，則可以為DRMP提供較多的信息，從而降低DRMP求解的復(fù)雜度[5,14-16]。

設(shè)t次迭代限制主問題的解空間為Ωt=(Lt,Ft,v(L)t,Cap(L)t)，其規(guī)模遠(yuǎn)遠(yuǎn)小于Ω，只需將式( 3 )～式( 9 )中L替換為Lt，并將整數(shù)變量(式(10))松弛為連續(xù)變量，即構(gòu)成限制的主問題RMP(Ωt)

RMP(Ωt)：式(11)、式( 3 )～式( 9 )

(12)

RMP(Ωt)是線性規(guī)劃問題，可以用單純形算法求解。

2.2 子問題的構(gòu)造

(13)

o,d∈Vi,j∈v(l)

(14)

l∈Ltij∈r(l)

(15)

l∈Ltij∈r(l)

(16)

(17)

(18)

(19)

εl≥0l∈L

(20)

σl≥0l∈L

(21)

γe≥0e∈E

(22)

ηv≥0v∈V

(23)

2.3 列生成與行生成

RMP(Ωt)中，約束( 4 )～約束( 7 )不能預(yù)先確定，則DRMP(Ωt)中含有對偶變量缺失的約束，標(biāo)準(zhǔn)的列生成算法可能在達(dá)到最優(yōu)解前終止運(yùn)算[14]。因此，需要在RMP(Ωt)中同時增加新的列車與相應(yīng)的式( 4 )～式( 7 )，即列生成與行生成。

多數(shù)學(xué)者采用兩階段方法處理列生成與行生成問題，需要進(jìn)行兩階段的反復(fù)迭代，計算比較復(fù)雜[14,16]。文獻(xiàn)[15]采取增加虛擬路徑的方法處理對偶變量缺失，避免進(jìn)行兩階段的反復(fù)迭代。

根據(jù)強(qiáng)對偶理論可得以下定理

定理1若對所有的列車l∈L/Lt，約束(13)～約束(16)均滿足，則MP達(dá)到最優(yōu)解，否則，不能達(dá)到最優(yōu)解。

類似于文獻(xiàn)[15]，構(gòu)造虛擬列車l*，其非停站弧集合r(l*)包括所有的非停站弧(該虛擬列車并沒有實(shí)際意義，只是為了產(chǎn)生對偶解)，則可由r(l*)構(gòu)造任意列車l∈L/Lt的非停站弧集合v(l)，從而構(gòu)造Ω/Ωt內(nèi)的任意解。然后，建立以下線性規(guī)劃模型(Linear Programme,LP)

(24)

o,d∈Vi,j∈v(l*)ij∈r(l*)

(25)

ij∈r(l*)

(26)

ij∈r(l*)

(27)

(28)

(29)

εl*≥0

(30)

σl*≥0

(31)

(32)

(33)

根據(jù)定理1及文獻(xiàn)[15]的討論容易得到定理2。

定理2若LP的目標(biāo)函數(shù)值為0時，MP達(dá)到最優(yōu)解，否則MP不能達(dá)到最優(yōu)解。

2.4 子問題的求解

當(dāng)LP的目標(biāo)函數(shù)值為正數(shù)時，約束(14)不被滿足，即(o,d)客流間的非停站弧ij需要增加到RMP中。因此需要將含有非停站弧ij的列車l及相應(yīng)的式( 4 )～式( 7 )，增加到RMP(Ωt+1)中。

2.5 列車起訖站的調(diào)整

由2.1～2.4節(jié)，可以確定列車集合L及其非停站弧集合v(F)。實(shí)際上，并不是任意車站均可以作為列車的起訖站，列車起訖站的設(shè)置不僅需要考慮車站的客運(yùn)需求，而且還需要考慮車站的動車布局、路網(wǎng)屬性、社會屬性等因素[5]。因此，可以預(yù)先確定列車的起訖站集合SF，然后將列車l∈L的運(yùn)行路徑延伸到最近的起訖站。該問題可以轉(zhuǎn)化為含固定弧l的最短路徑問題，可以用2.4的方法進(jìn)行求解。

2.6 求解HSRPTLP

根據(jù)2.1～2.5節(jié)，在松弛整數(shù)式(10)的條件下，確定列車集合L及其非停站弧集合v(F)，并且得到的1個下界ZLP。然后，恢復(fù)模型的整數(shù)式(10)，以L、v(F)作為已知條件代入HSRPTLP，并運(yùn)用分支定界算法得到解ZIP，ZIP不一定是他的最優(yōu)解，只是他的1個上界。

將L、v(L)作為已知條件代入HSRPTLP后，其求解難度遠(yuǎn)遠(yuǎn)小于原問題的難度，可以用分支定界算法進(jìn)行求解，但傳統(tǒng)的分支定界算法耗時較長，需要對分支定界算法進(jìn)行局部的改進(jìn)。

在定界剪支階段，仍采用松弛整數(shù)約束的方法定下界，并根據(jù)下界剪支。

2.7 算法的綜合步驟

改進(jìn)列生成算法的主要步驟如下

Step1令t=0、Lt={l0}，其中列車l0以高速線路的起點(diǎn)、終點(diǎn)為起訖站，停站方案為站站停。根據(jù)2.1節(jié)、2.2節(jié)生成RMP、DRMP，并用單純形算法進(jìn)行求解；

Step2根據(jù)2.3節(jié)構(gòu)造包含所有非停站弧的虛擬列車l*，生成LP問題，并用單純形算法進(jìn)行求解，若LP問題的目標(biāo)函數(shù)小于ε(ε取10-6)，則進(jìn)行step4，否則進(jìn)行step3；

Step4根據(jù)2.5節(jié)所述方法對列車起訖站進(jìn)行調(diào)整；

Step5根據(jù)2.6節(jié)，將L、v(L)作為已知條件代入HSRPTLP，并運(yùn)用改進(jìn)的分支定界算法求解。

3 案例分析

以京滬高鐵本線客流數(shù)據(jù)(2013-07～2013-08)為依據(jù)進(jìn)行案例研究[18]。京滬高鐵主要跨越23個站，由北向南各站名及序號依次為1北京南、2廊坊、3天津南、4滄州西、5德州東、6濟(jì)南西、7泰安、8曲阜東、9滕州東、10棗莊、11徐州東、12宿州東、13蚌埠南、14定遠(yuǎn)、15滁州、16南京南、17鎮(zhèn)江南、18丹陽北、19常州北、20無錫東、21蘇州北、22昆山南、23上海虹橋。

現(xiàn)開行方案實(shí)際運(yùn)行2種速度等級的列車，即G類列車(G字頭列車)與D類列車(D字頭列車)，鑒于系統(tǒng)分離法分離客流不屬于本文研究的內(nèi)容，且D類列車所占比例較少(約占13.8% )，為計算方便，假設(shè)僅開行G類列車。

主要參數(shù)：G類列車速度為300 km/h，停站時間6 min(含起停附加時間)，固定成本42 000元/列，可變成本150元/列·km(參考武廣高鐵)，單組列車定員500人，重聯(lián)1 000人，列車最大席位利用率為100 %，最小席位利用率為40 %，時間價值vot為30元/h。列車的起訖站集合SF包含北京南、天津南、濟(jì)南西、徐州東、南京南、上海虹橋[6-7,18]。

首先使用規(guī)劃軟件Cplex12.5和AMDA6處理器，頻率1.5 Hz、內(nèi)存4 G的個人計算機(jī)測試案例，運(yùn)行2 h后未獲得最優(yōu)解。采用Matlab實(shí)施改進(jìn)的列生成算法測試案例，其中所有線性規(guī)劃問題用Cplex12.5處理，20 min得出結(jié)果，詳見表1，迭代25次后達(dá)到穩(wěn)定值，見圖1。

表1 京滬高速本線列車開行方案結(jié)果

基于改進(jìn)列生成算法解的誤差率為Gap=(ZIP-ZLP)/ZLP×100%=2.13%，將計算結(jié)果與實(shí)際采用的開行方案[18]進(jìn)行比較，見表2，從列車開行對數(shù)與開行區(qū)段上分析，計算結(jié)果中日開行列車52對，其中重聯(lián)列車24對，單組列車28對，比實(shí)際減少4對(實(shí)際日開行56對列車，含10對D類列車)，運(yùn)行區(qū)段為3個，比實(shí)際減少3個；從停站次數(shù)分析，計算結(jié)果的停站次數(shù)比實(shí)際減少95次;從上座率分析，計算結(jié)果的上座率范圍為86.21%～99.75%，平均上座率為92.87%，實(shí)際上座率范圍為23.10%～105.50%，平均上座率為85.00%。由此可見，本算法得到的開行方案能更好地與客流需求相吻合，并且優(yōu)于實(shí)際采用的開行方案。

表2 與實(shí)際數(shù)據(jù)指標(biāo)對比

4 結(jié)論

本文在Park等[9]研究基礎(chǔ)上拓展，建立確定列車開行對數(shù)、運(yùn)行區(qū)段、停站方案、編組方式的多目標(biāo)規(guī)劃模型，設(shè)計基于改進(jìn)的列生成算法求解模型。案列分析表明，本算法能夠在有效時間內(nèi)獲得優(yōu)于實(shí)際結(jié)果的較高質(zhì)量解，誤差率為2.13%。

本文的研究可進(jìn)一步改進(jìn)：首先，高速路網(wǎng)比高速線路更為復(fù)雜，需要考慮客流的換乘問題，基于路網(wǎng)的高速列車開行方案是下一步研究的重點(diǎn)內(nèi)容；其次，沒有考慮列車頻率對旅客出行的影響，只是規(guī)定列車的最小、最大席位利用率，防止模型求出的列車編組嚴(yán)重趨向于有利于運(yùn)輸企業(yè)的重聯(lián)情形，一般列車開行頻率越大，旅客的廣義出行成本將減少，但這種關(guān)系的準(zhǔn)確描述很難確定；最后，單層模型中客流分配與標(biāo)準(zhǔn)客流分配還存在一定偏差，不能完全反映旅客的實(shí)際選擇行為。因此，單層模型中客流分配問題還需繼續(xù)研究。

參考文獻(xiàn)：

[1] BUSSIECK M R. Optimal Lines in Public Transport[D]. Germany: Technical University Braunschweig,1998:11-17.

[2] CLAESSENS M T, DIJK N M, ZWANEVELD P J . Cost Optimal Allocation of Rail Passenger Lines[J]. European Journal of Operational Research, 1998,110(3):474-489.

[3] BUSSIECK M R, KREUZER P, ZIMMERM U T. Optimal Lines for Railway Systems[J]. European Journal of Operational Research, 1997, 96(1):54-63．

[4] 杜欣，牛永濤，韓寶明，等. 基于節(jié)點(diǎn)重要度的客運(yùn)專線旅客列車開行方案[J].北京交通大學(xué)學(xué)報，2010，34(6)：5-10.

DU Xin, NIU Yong-tao, HAN Bao-ming, et al. Train Service Planning for Passenger Dedicated Railway Line Based on Analyzing Importance of Nodes[J]. Journal of Beijing Jiaotong University, 2010, 34(6): 5-10.

[5] BORNDORFER R, GROTSCHEL M,PFETSCH M E. A Column Generation Approach to Line Planning in Public Transport[J]. Transportation Scinece, 2007, 41(1):123-132．

[6] 付慧伶，聶磊，楊浩，等.基于備選集的高速鐵路列車開行方案優(yōu)化方法研究[J].鐵道學(xué)報，2010，32(6)：1-8.

FU Hui-ling, NIE Lei, YANG Hao, et al. Research on the Method for Optimization of Candiate Train Set Based Train Operation Plans for High Speed Railways[J]. Journal of the China Railway Society, 2010,32(6):1-8.

[7] 佟璐，聶磊，付慧伶.基于復(fù)雜列車服務(wù)網(wǎng)絡(luò)的客流分配方法研究[J].鐵道學(xué)報，2012，34(10)：7-15.

TONG Lu, NIE Lei, FU Hui-ling. Research on Passenger Flow Assignment Method Based on Complex Train Service Network[J]. Journal of the China Railway Society, 2012, 34(10): 7-15.

[8] CHANG Y H, YEH C H, SHEN C C. A Multiobjective Model for Passenger Train Services Planning: Application to Taiwan’s High-speed Rail Line[J]. Transportation Research Part B, 2000, 34(2): 91-106．

[9] PARK B H, SEO Y I, HONG S P, et al. Column Generation Approach to Line Planning with Various Halting Patterns-application to the Korean High Speed Railway[J]. Asia-pacific Journal of Operational Research, 2013, 30(4): 1-19.

[10] 史峰，鄧連波，霍亮．旅客列車開行方案的雙層規(guī)劃模型和算法[J]．中國鐵道科學(xué)，2007，28(3)：110-116.

SHI Feng, DENG Lian-bo,HUO Liang.Bi-level Programming Model and Algorithm of Passenger Train Operation Plan[J].China Railway Science, 2007,28(3):110-116.

[11] WANG L, JIA L M , QIN Y, et al. A Two-layer Optimization Model for High-speed Railway Line Planning[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2011,12(12):902-912.

[12] GAO Z Y , WU J J, SUN H J. Solution Algorithm for the Bi-level Discrete Network Design Problem[J]. Transportation Research Part B, 2005 , 39(7): 479-495.

[13] LUBBECKE M E, DESROSIERS J. Selected Topics in Column Generation[J]. Operations Research, 2005, 53 (6) ,1007-1023.

[14] AVELLA P, DAURIA B, SALERNO S. A LP-based Heuristic for A Time-constrained Routing Problem[J]. European Journal of Operational Research, 2006, 173(1):120-124.

[15] FEILLET D, GENDREAU M, MEDAGLIA A L, et al. A Note on Branch-and-cut-and-Price[J]. Operations Research Letters, 2010 , 38(5):346-353.

[16] MUTER I, BIRBIL S I, BULBUL K, et al. Solving A Robust Airline Crew Pairing Problem with Column Generation[J]. Computers & Operations Research, 2013, 40(11): 815-830.

[17] GOOSSENS J W, HOESEL S, KROON L. A Branch and Cut Approach for Solving Railway Line Planning Problems[J]. Transportation Scinece, 2004, 38(3):379-393.

[18] 馬超.京滬高速鐵路開行方案評價及優(yōu)化調(diào)整方法研究[D].北京：北京交通大學(xué)，2014：36-60.