路超，周磊山，陳然

?

最大通過能力下高速鐵路運(yùn)行圖優(yōu)化研究

路超，周磊山，陳然

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

為最大限度地利用多等級(jí)列車共存的高速鐵路繁忙線路通過能力，同時(shí)保證運(yùn)輸質(zhì)量，構(gòu)建高速鐵路網(wǎng)通過能力最大化條件下的列車運(yùn)行圖優(yōu)化模型。根據(jù)列車運(yùn)行過程中不得有沖突的特點(diǎn)將該問題抽象為時(shí)空網(wǎng)絡(luò)中帶約束的最大獨(dú)立集問題。通過D-W分解將模型進(jìn)行轉(zhuǎn)化及線性松弛。采用列生成算法對有大規(guī)模決策變量的松弛問題進(jìn)行求解。在松弛解的基礎(chǔ)上設(shè)計(jì)分支定界算法求得最優(yōu)可行列車最大獨(dú)立運(yùn)行線集。研究結(jié)果表明：所建模型具有在不同參數(shù)表示的需求場景下靈活求得兼顧運(yùn)能和運(yùn)輸質(zhì)量的有效運(yùn)行圖的功能。通過與求解獨(dú)立集問題的常用啟發(fā)式算法對比，本文方法可在保持旅行時(shí)間平均1.33%波動(dòng)條件下使得通過能力值目標(biāo)提高2.56%、總目標(biāo)值提高4.6%。

高速鐵路；能力利用；運(yùn)行圖；優(yōu)化模型

隨著高速鐵路網(wǎng)絡(luò)以及客運(yùn)需求的日漸擴(kuò)大，高速鐵路尤其是多條列車徑路匯集、多種列車等級(jí)共存的繁忙干線的運(yùn)能供給受到了嚴(yán)峻的挑戰(zhàn)。如何在滿足一定客運(yùn)產(chǎn)品結(jié)構(gòu)以及運(yùn)輸服務(wù)質(zhì)量條件下，掌握并發(fā)掘路網(wǎng)有效通過能力具有重要的實(shí)際意義。目前鐵路通過能力的文獻(xiàn)主要研究鐵路區(qū)段一個(gè)周期內(nèi)理論上能通過的最大列車數(shù)，例如扣除系數(shù)法[1?2]。隨著鐵路通過能力計(jì)算方法的變革，直接計(jì)算法為新的研究方向。Abril等[3]在考慮列車速度、越行站等條件下采用模擬仿真的方法分析周期運(yùn)行圖的通過能力。Heydar等[4?5]提出了一組列車所占用的最小時(shí)間周期的概念對雙線鐵路的通過能力進(jìn)行研究。Kort等[6]采用隨機(jī)極大加代數(shù)法研究需求不確定條件下的鐵路通過能力。趙欣苗等[7]分析了列車追蹤間隔對高速鐵路通過能力利用的影響。王華[8]以列車速度組合為核心,分別提出2種和3種速度等級(jí)混合運(yùn)輸?shù)耐ㄟ^能力計(jì)算方法?，F(xiàn)有列車運(yùn)行圖編制模型中通常將各個(gè)等級(jí)的列車數(shù)作為輸入條件，從而對已知數(shù)量的列車運(yùn)行線分布進(jìn)行優(yōu)化決策[9?10]。由于列車運(yùn)行圖的編制需要考慮滿足安全間隔等要求，當(dāng)不存在充足的可行運(yùn)行線鋪畫空間時(shí)，需要將相應(yīng)的列車取消[11?13]。因此列車運(yùn)行圖鋪畫問題和能力利用問題有直接的內(nèi)在聯(lián)系。在多種等級(jí)列車共存條件下，每種速度等級(jí)或停站方案的列車都對應(yīng)于一種運(yùn)輸產(chǎn)品，僅僅追求列車總數(shù)最大還不能滿足市場和實(shí)際運(yùn)營需要，還需兼顧不同等級(jí)列車的開行比例。此外，在通過能力的計(jì)算過程中同步考慮運(yùn)行圖的優(yōu)化編制可以使通過能力的計(jì)算結(jié)果得到運(yùn)行圖的鋪畫檢驗(yàn)，從而克服理論計(jì)算能力與實(shí)際可用能力產(chǎn)生偏離的缺陷，使得鐵路通過能力得到有效優(yōu)化利用。為此，本文協(xié)調(diào)考慮通過能力的充分利用以及列車運(yùn)行過程的平均旅行時(shí)間、穩(wěn)定性等運(yùn)行圖質(zhì)量要求，構(gòu)建多種等級(jí)列車共存的高速鐵路網(wǎng)最大通過能力條件下的運(yùn)行圖優(yōu)化模型。

1 問題描述

圖1 鐵路線路的時(shí)空網(wǎng)絡(luò)

圖2 時(shí)空運(yùn)行弧候選無向圖

2 運(yùn)能優(yōu)化模型

2.1 模型建立

給定時(shí)空網(wǎng)絡(luò)以及相應(yīng)的參數(shù)集合，若以0-1決策變量x表示時(shí)空有向弧被選作運(yùn)行圖的時(shí)空路徑，間接0-1決策變量y,p表示時(shí)間節(jié)點(diǎn)被等級(jí)列車的時(shí)空路徑占用，則建立最大通過能力條件下高速鐵路運(yùn)行圖優(yōu)化模型如下。

M1：

其中目標(biāo)函數(shù)(1)的第1項(xiàng)表示盡可能多地將列車時(shí)空運(yùn)行弧選入運(yùn)行圖中，即所鋪畫的運(yùn)行線數(shù)量最大。為兼顧服務(wù)質(zhì)量，后2項(xiàng)表示所鋪畫運(yùn)行線的總旅行時(shí)間最小。約束條件(2)為各徑路鋪畫不同等級(jí)列車運(yùn)行線數(shù)量的最小比例限制約束。約束條件(3)為列車運(yùn)行線對應(yīng)時(shí)空路徑的流平衡約束。約束條件(4)為各等級(jí)列車在各車站的停站時(shí)間不應(yīng)小于所需的最小停留時(shí)間。約束條件(5)為決策變量x與間接決策變量y,p的關(guān)聯(lián)約束。約束條件(6)為避免運(yùn)行弧之間有沖突干擾的約束，即候選運(yùn)行弧集的獨(dú)立集約束。約束條件(7)為變量取值約束。

2.2 基于D-W分解的模型轉(zhuǎn)化

其中：為模型M2的決策變量。目標(biāo)函數(shù)(9)是將x和k代入(1)后的等價(jià)變換。約束條件(10)是用轉(zhuǎn)化后的決策變量進(jìn)行描述的列車開行比例約束，是將w,r,e和x代入(2)后的等價(jià)變換。

3 模型求解

3.1 求解限制主問題的列生成算法

s.t. (3)，(4)，(5)，(6)，(7)

求解線性松弛主問題M2的列生成算法步驟如下(算法1)。

Step 1：任意生成若干組初始列車獨(dú)立時(shí)空徑路集，初始化為集合′；

Step 2：調(diào)用MATLAB線性規(guī)劃工具求解限制主問題，得當(dāng)前最優(yōu)解(1,…,|Q′|)*。求解限制主問題的對偶問題；

3.2 價(jià)格子問題求解算法

PLS算法求解原問題M1時(shí)，為在尋找可行的最大獨(dú)立列車徑路集的過程中剔除因被多次越行而產(chǎn)生較大額外中間站停留時(shí)間的列車，可以在M1中添加輔助的越行限制約束：

為很大的正數(shù)。

3.3 基于限制主問題的分支定界算法

線性松弛問題M2的最優(yōu)解可能不滿足整數(shù)約束(7)，但提供了原問題的一個(gè)下界。為求解出模型M1滿足整數(shù)約束的最優(yōu)可行解，本文設(shè)計(jì)基于限制主問題的分支定界算法。

其中：FK表示當(dāng)前可行域X中已經(jīng)固定的列車時(shí)空路徑所包含的弧集。EK表示當(dāng)前可行域X中已經(jīng)剔除的列車時(shí)空路徑所包含的弧集。表示當(dāng)前分支定界樹中存儲(chǔ)的節(jié)點(diǎn)集，即子問題M1(X)的集合。具體地分支定界算法步驟如下(算法3)：

4 算例分析

為驗(yàn)證本文方法的有效性，在圖3所示的鐵路區(qū)段進(jìn)行算例測試。該鐵路區(qū)段可視為包含3個(gè)相關(guān)聯(lián)列車運(yùn)行徑路的小規(guī)模路網(wǎng)。在此考慮300 km/h和250 km/h2種不同等級(jí)列車共線運(yùn)行時(shí)該路網(wǎng)通過能力的優(yōu)化。

圖4對比了本文分支定界(B & B)算法和PLS算法的求解過程。從圖4可見，B & B算法最優(yōu)解的總目標(biāo)值(上界)與其下界的間隙非常小且明顯優(yōu)于PLS算法。PLS算法曲線1，2表示PLS算法迭代時(shí)調(diào)整高速列車發(fā)車間隔會(huì)改善優(yōu)化結(jié)果，但程度有限。

圖3 算例路網(wǎng)列車停站方案

圖4 B & B算法及PLS算法迭代過程

圖5 PLS算法運(yùn)行圖

圖6 考慮越行限制B & B算法運(yùn)行圖

在圖7中，由于B & B算法結(jié)果的能力值目標(biāo)大于PLS算法的能力值目標(biāo)，因此會(huì)出現(xiàn)B & B算法的旅行時(shí)間目標(biāo)值大于PLS算法的情況，但B & B算法的在不同場景下的總目標(biāo)平均比PLS算法改善4.6%。

圖7 旅行時(shí)間權(quán)重變動(dòng)條件下2種目標(biāo)對比

當(dāng)考慮越行限制時(shí)優(yōu)化結(jié)果如圖8所示，其總體特征與圖7類似，但所得運(yùn)行圖的結(jié)構(gòu)發(fā)生了明顯的變化。B & B算法所得結(jié)果中高速列車數(shù)的能力目標(biāo)值減少而中速列車能力目標(biāo)值增加，但總體優(yōu)于PLS算法的結(jié)果，如圖9和圖10所示。

圖8 限制越行次數(shù)時(shí)求解結(jié)果

表1列出中速列車最小比例中速,r變化時(shí)各種算法優(yōu)化解的靈敏度分析結(jié)果。該組結(jié)果表示B & B算法可以在滿足列車數(shù)比例的同時(shí)得到比PLS算法總目標(biāo)平均提高3.85%的解。

圖9 有越行限制時(shí)高速列車能力值目標(biāo)對比

圖10 有越行限制時(shí)中速列車能力值目標(biāo)對比

圖11 單弧緩沖時(shí)間變化時(shí)求解結(jié)果對比

將時(shí)空網(wǎng)絡(luò)中每個(gè)列車弧的旅行時(shí)間費(fèi)用加入緩沖時(shí)間時(shí)(在此取0.2~1.6 min)求解結(jié)果如圖11所示。B & B算法在不同的緩沖時(shí)間的目標(biāo)值比PLS算法平均改善5.12%(表2)。此外，B & B算法的各區(qū)段總的平均旅行時(shí)間同樣少于PLS算法的總平均旅行時(shí)間。

表1 中速列車最小比例變化時(shí)目標(biāo)值對比

表2 單弧緩沖時(shí)間變化時(shí)目標(biāo)值及平均旅行時(shí)間差對比

5 結(jié)論

1) 考慮多等級(jí)列車共存鐵路網(wǎng)通過能力最大條件下運(yùn)行圖優(yōu)化模型。該模型對于提高繁忙路網(wǎng)運(yùn)輸效率、緩解供需平衡具有實(shí)際意義。

2) 對模型采用D-W分解轉(zhuǎn)化。采用列生成算法處理變量規(guī)模過大的問題并求得原問題線性松弛問題的解。在此基礎(chǔ)上設(shè)計(jì)分支定界算法實(shí)現(xiàn)松弛解的最優(yōu)整數(shù)化處理。以小規(guī)模路網(wǎng)為例驗(yàn)證了本文方法求得較好質(zhì)量解的靈活性。

3) 為使得運(yùn)輸能力的時(shí)間分布與客流需求更為吻合，可以在本文方法的基礎(chǔ)上結(jié)合客流需求的時(shí)間波動(dòng)性和運(yùn)行圖的周期性等因素開展進(jìn)一步研究。

[1] 趙麗珍. 高速鐵路區(qū)間通過能力計(jì)算與分析[J]. 中國鐵道科學(xué), 2001, 22(6): 54?58. ZHAO Lizhen. Calculation and analysis of carrying capacity of high-speed railway section[J]. China Railway Science, 2001, 22(6): 54?58.

[2] 蘇順虎, 田長海, 陳治亞. 客運(yùn)專線通過能力的分析計(jì)算[J]. 中國鐵道科學(xué), 2008, 29(5): 119?124. SU Shunhu, TIAN Changhai, CHEN Zhiya. Analysis and calculation of the carrying capacity on passenger dedicated lines[J]. China Railway Science, 2008, 29(5): 119?124.

[3] Abril M, Barber F, Ingolotti L, et al. An assessment of railway capacity[J]. Transportation Research Part E Logistics & Transportation Review, 2008, 44(5): 774? 806.

[4] Heydar M, Petering M E H, Bergmann D R. Mixed integer programming for minimizing the period of a cyclic railway timetable for a single track with two train types[J]. Computers & Industrial Engineering, 2013, 66(1): 171?185.

[5] Petering M E H, Heydar M, Bergmann D R. Mixed-Integer programming for railway capacity analysis and cyclic, combined train timetabling and platforming[J]. Transportation Science, 2016, 50(3): 23?30.

[6] Kort A F D, Heidergott B, Ayhan H. A probabilistic (max, +) approach for determining railway infrastructure capacity[J]. European Journal of Operational Research, 2000, 148(3): 644?661.

[7] 趙欣苗, 尹相勇, 李茜, 等. 列車追蹤間隔時(shí)間對高速鐵路通過能力利用的影響分析[J]. 鐵道科學(xué)與工程學(xué)報(bào), 2016, 13(11): 2099?2106. ZHAO Xinmiao, YIN Xiangyong, LI Xi, et al. Influence of train tracking headways on carrying capacity utilization of high-speed railway[J]. Journal of Railway Science and Engineering, 2016, 13(11): 2099?2106.

[8] 王華. 基于規(guī)格運(yùn)行圖的鐵路運(yùn)輸能力探討[J]. 交通運(yùn)輸工程與信息學(xué)報(bào), 2010, 8(2): 11?16. WANG Hua. Research on the railway line carrying capacity based on pattern train work diagram[J]. Journal of Transportation Engineering and Information, 2010, 8(2): 11?16.

[9] ZHOU X, ZHONG M. Bicriteria train scheduling for high-speed passenger railroad planning applications[J]. European Journal of Operational Research, 2005, 167(3): 752?771.

[10] Cacchiani V, Caprara A, Toth P. A column generation approach to train timetabling on a corridor[J]. 4OR-A Quarterly Journal of Operations Research, 2008, 6(2): 125?142.

[11] Caprara A, Fischetti M, Toth P. Modeling and solving the train timetabling problem[J]. Operations Research, 2002, 50(5): 851?861.

[12] Br?nnlund U, Lindberg P O, N?u A, et al. Railway timetabling using lagrangian relaxation[J]. Transportation Science, 1998, 32(4): 358?369.

[13] Caprara A, Monaci M, Toth P, et al. A lagrangian heuristic algorithm for a real-world train timetabling problem[J]. Discrete Applied Mathematics, 2006, 154(5): 738?753.

[14] Pullan W. Phased local search for the maximum clique problem[J]. Journal of Combinatorial Optimization, 2006, 12(3): 303?323.

[15] Barnhart C, Johnson E L, Nemhauser G L, et al. Branch- and-price: Column generation for solving huge integer programs[J]. Operations Research, 1994, 46(3): 316?329.

Optimization of high-speed railway timetabling based on maximum utilization of railway capacity

LU Chao, ZHOU Leishan, CHEN Ran

(School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China)

In order to maximize the capacity utilization in busy high-speed railways with mixed trains and ensuring the transportation efficiency, this paper constructs the model of train timetabling with maximum capacity. Since there must be no conflicts between trains, the problem is abstracted into constrained maximum independent set in the space-time network. The model are transformed and linearly relaxed by D-W decomposition method. Column generation is applied to solve the relaxed problem. Based on the relaxed solution a branch and bound algorithm is designed to find the optimal feasible solution. The experiment results show that the proposed method is able to flexibly find timetables with balanced capacity and efficiency under each scenario of demand specified by different parameters. Compared with general heuristic algorithm, on average, the proposed method makes effort to improve the objective value of capacity by 2.56%, the total objective value by 4.6% while holding the fluctuation of the objective value of total travel time within 1.33%.

high-speed railway; capacity utilization; train timetable; optimization model

10.19713/j.cnki.43?1423/u.2018.11.004

U292.4

A

1672 ? 7029(2018)11 ? 2746 ? 09

2017?09?14

中國鐵路總公司科技研究開發(fā)計(jì)劃資助項(xiàng)目(KTD16011531)；中央高效基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(2014JBZ2008)

周磊山(1962?)，男，湖南洞口人，教授，博士，從事運(yùn)輸組織現(xiàn)代化理論與技術(shù)研究：E?mail：lshzhou@bjtu.edu.cn

(編輯 蔣學(xué)東)