基于改進列生成算法的高速列車開行方案優化研究

蒲 松， 呂紅霞,2,3， 陳釘均,2,3， 倪少權,2,3

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

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

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

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

1 建立HSRPTLP模型

1.1 基本概念

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

鐵路網：以車站為節點，路段為邊構成的網絡。

列車運行路徑：由列車始發站、途經路段及列車終到站構成的路徑。

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

客流OD：起訖站間客流。

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

客流徑路：旅客的乘車方案，由客流的起點站、列車的非停站弧、客流的終點站構成。

1.2 目標函數

HSRPTLP需要考慮運輸企業與旅客雙方的利益。因此，優化開行方案目標為

目標1 盡可能減小運輸企業運營成本；

目標2 盡可能減小旅客的旅行成本。

運輸企業的成本主要由列車開行的數量和列車總運行公里組成，可以分為固定成本和可變成本。其中固定成本包括鐵路線路、車站等各種固定設備和動車組等移動設施的投資費用。多數研究[1-6,8-10]都對固定成本進行簡化處理：由于開行方案的研究對象是列車，所以固定成本僅和列車開行數量有關，即固定成本是開行1列列車必須產生的成本。可變成本主要與列車運行里程有關，即列車每公里所產生的成本。因此，目標1可以表示為

( 1 )

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

( 2 )

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

1.3 約束條件

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

客流守恒，各支客流OD途經各車站的客流量守恒，即

( 3 )

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

( 4 )

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

l∈Lij∈r(l)

( 5 )

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

( 6 )

( 7 )

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

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

( 8 )

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

( 9 )

(10)

式中：N為非負整數集合。

1.4 模型的復雜度分析

HSRPTLP的優化模型是多目標規劃模型，而多目標規劃模型將大大增加問題的復雜度。同文獻[4-9]，利用權重法將多目標規劃轉化為單目標規劃，即

(11)

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

約束條件個數為

模型的約束與變量隨著路網規模的增大而呈指數規模的增長，即使是對小規模的實例，也很難在有限的時間內找到高質量的解，甚至連找到可行解都很困難。因此，根據模型特點，設計基于列生成與行生成的啟發式算法。

2 列生成算法求解模型

2.1 主問題的構造

設Ω=(L,F,v(L),Cap(L))為主問題的解空間，L、F、v(L)、Cap(L)分別表示列車集合、對應列車的開行對數集合、列車的非停站弧集合及編組方式集合。因規模較大，所以在求解的過程中給出Ω的1個子集，其規模遠遠小于Ω，并且在每次迭代中逐漸生成。此時，主問題變為限制的主問題(Restricted Master Problem, RMP)，相應的子問題變為限制的子問題(Dual Restricted Master Problem,DRMP)。

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

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

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

(12)

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

2.2 子問題的構造

(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 )不能預先確定，則DRMP(Ωt)中含有對偶變量缺失的約束，標準的列生成算法可能在達到最優解前終止運算[14]。因此，需要在RMP(Ωt)中同時增加新的列車與相應的式( 4 )～式( 7 )，即列生成與行生成。

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

根據強對偶理論可得以下定理

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

類似于文獻[15]，構造虛擬列車l*，其非停站弧集合r(l*)包括所有的非停站弧(該虛擬列車并沒有實際意義，只是為了產生對偶解)，則可由r(l*)構造任意列車l∈L/Lt的非停站弧集合v(l)，從而構造Ω/Ωt內的任意解。然后，建立以下線性規劃模型(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)

根據定理1及文獻[15]的討論容易得到定理2。

定理2若LP的目標函數值為0時，MP達到最優解，否則MP不能達到最優解。

2.4 子問題的求解

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

2.5 列車起訖站的調整

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

2.6 求解HSRPTLP

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

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

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

2.7 算法的綜合步驟

改進列生成算法的主要步驟如下

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

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

Step4根據2.5節所述方法對列車起訖站進行調整；

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

3 案例分析

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

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

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

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

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

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

表2 與實際數據指標對比

4 結論

本文在Park等[9]研究基礎上拓展，建立確定列車開行對數、運行區段、停站方案、編組方式的多目標規劃模型，設計基于改進的列生成算法求解模型。案列分析表明，本算法能夠在有效時間內獲得優于實際結果的較高質量解，誤差率為2.13%。

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

參考文獻：

[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] 杜欣，牛永濤，韓寶明，等. 基于節點重要度的客運專線旅客列車開行方案[J].北京交通大學學報，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] 付慧伶，聶磊，楊浩，等.基于備選集的高速鐵路列車開行方案優化方法研究[J].鐵道學報，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] 佟璐，聶磊，付慧伶.基于復雜列車服務網絡的客流分配方法研究[J].鐵道學報，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] 史峰，鄧連波，霍亮．旅客列車開行方案的雙層規劃模型和算法[J]．中國鐵道科學，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] 馬超.京滬高速鐵路開行方案評價及優化調整方法研究[D].北京：北京交通大學，2014：36-60.