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

路超，周磊山，陳然

?

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

路超，周磊山，陳然

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

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

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

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

1 問題描述

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

圖2 時空運行弧候選無向圖

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

2.1 模型建立

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

M1：

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

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

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

3 模型求解

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

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

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

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

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

3.2 價格子問題求解算法

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

為很大的正數(shù)。

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

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

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

4 算例分析

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

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

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

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

圖5 PLS算法運行圖

圖6 考慮越行限制B & B算法運行圖

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

圖7 旅行時間權(quán)重變動條件下2種目標對比

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

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

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

圖9 有越行限制時高速列車能力值目標對比

圖10 有越行限制時中速列車能力值目標對比

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

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

表1 中速列車最小比例變化時目標值對比

表2 單弧緩沖時間變化時目標值及平均旅行時間差對比

5 結(jié)論

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

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

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

[1] 趙麗珍. 高速鐵路區(qū)間通過能力計算與分析[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] 蘇順虎, 田長海, 陳治亞. 客運專線通過能力的分析計算[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] 趙欣苗, 尹相勇, 李茜, 等. 列車追蹤間隔時間對高速鐵路通過能力利用的影響分析[J]. 鐵道科學(xué)與工程學(xué)報, 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ī)格運行圖的鐵路運輸能力探討[J]. 交通運輸工程與信息學(xué)報, 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ā)計劃資助項目(KTD16011531)；中央高效基本科研業(yè)務(wù)費專項資金資助項目(2014JBZ2008)

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

(編輯 蔣學(xué)東)