最大通过能力下高速铁路运行图优化研究

路超，周磊山，陈然



最大通过能力下高速铁路运行图优化研究

路超，周磊山，陈然

(北京交通大学 交通运输学院，北京 100044)

为最大限度地利用多等级列车共存的高速铁路繁忙线路通过能力，同时保证运输质量，构建高速铁路网通过能力最大化条件下的列车运行图优化模型。根据列车运行过程中不得有冲突的特点将该问题抽象为时空网络中带约束的最大独立集问题。通过D-W分解将模型进行转化及线性松弛。采用列生成算法对有大规模决策变量的松弛问题进行求解。在松弛解的基础上设计分支定界算法求得最优可行列车最大独立运行线集。研究结果表明：所建模型具有在不同参数表示的需求场景下灵活求得兼顾运能和运输质量的有效运行图的功能。通过与求解独立集问题的常用启发式算法对比，本文方法可在保持旅行时间平均1.33%波动条件下使得通过能力值目标提高2.56%、总目标值提高4.6%。

高速铁路；能力利用；运行图；优化模型

随着高速铁路网络以及客运需求的日渐扩大，高速铁路尤其是多条列车径路汇集、多种列车等级共存的繁忙干线的运能供给受到了严峻的挑战。如何在满足一定客运产品结构以及运输服务质量条件下，掌握并发掘路网有效通过能力具有重要的实际意义。目前铁路通过能力的文献主要研究铁路区段一个周期内理论上能通过的最大列车数，例如扣除系数法[1−2]。随着铁路通过能力计算方法的变革，直接计算法为新的研究方向。Abril等[3]在考虑列车速度、越行站等条件下采用模拟仿真的方法分析周期运行图的通过能力。Heydar等[4−5]提出了一组列车所占用的最小时间周期的概念对双线铁路的通过能力进行研究。Kort等[6]采用随机极大加代数法研究需求不确定条件下的铁路通过能力。赵欣苗等[7]分析了列车追踪间隔对高速铁路通过能力利用的影响。王华[8]以列车速度组合为核心,分别提出2种和3种速度等级混合运输的通过能力计算方法。现有列车运行图编制模型中通常将各个等级的列车数作为输入条件，从而对已知数量的列车运行线分布进行优化决策[9−10]。由于列车运行图的编制需要考虑满足安全间隔等要求，当不存在充足的可行运行线铺画空间时，需要将相应的列车取消[11−13]。因此列车运行图铺画问题和能力利用问题有直接的内在联系。在多种等级列车共存条件下，每种速度等级或停站方案的列车都对应于一种运输产品，仅仅追求列车总数最大还不能满足市场和实际运营需要，还需兼顾不同等级列车的开行比例。此外，在通过能力的计算过程中同步考虑运行图的优化编制可以使通过能力的计算结果得到运行图的铺画检验，从而克服理论计算能力与实际可用能力产生偏离的缺陷，使得铁路通过能力得到有效优化利用。为此，本文协调考虑通过能力的充分利用以及列车运行过程的平均旅行时间、稳定性等运行图质量要求，构建多种等级列车共存的高速铁路网最大通过能力条件下的运行图优化模型。

1 问题描述

图1 铁路线路的时空网络

图2 时空运行弧候选无向图

2 运能优化模型

2.1 模型建立

给定时空网络以及相应的参数集合，若以0-1决策变量x表示时空有向弧被选作运行图的时空路径，间接0-1决策变量y,p表示时间节点被等级列车的时空路径占用，则建立最大通过能力条件下高速铁路运行图优化模型如下。

M1：

其中目标函数(1)的第1项表示尽可能多地将列车时空运行弧选入运行图中，即所铺画的运行线数量最大。为兼顾服务质量，后2项表示所铺画运行线的总旅行时间最小。约束条件(2)为各径路铺画不同等级列车运行线数量的最小比例限制约束。约束条件(3)为列车运行线对应时空路径的流平衡约束。约束条件(4)为各等级列车在各车站的停站时间不应小于所需的最小停留时间。约束条件(5)为决策变量x与间接决策变量y,p的关联约束。约束条件(6)为避免运行弧之间有冲突干扰的约束，即候选运行弧集的独立集约束。约束条件(7)为变量取值约束。

2.2 基于D-W分解的模型转化

其中：为模型M2的决策变量。目标函数(9)是将x和k代入(1)后的等价变换。约束条件(10)是用转化后的决策变量进行描述的列车开行比例约束，是将w,r,e和x代入(2)后的等价变换。

3 模型求解

3.1 求解限制主问题的列生成算法

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

求解线性松弛主问题M2的列生成算法步骤如下(算法1)。

Step 1：任意生成若干组初始列车独立时空径路集，初始化为集合′；

Step 2：调用MATLAB线性规划工具求解限制主问题，得当前最优解(1,…,|Q′|)*。求解限制主问题的对偶问题；

3.2 价格子问题求解算法

PLS算法求解原问题M1时，为在寻找可行的最大独立列车径路集的过程中剔除因被多次越行而产生较大额外中间站停留时间的列车，可以在M1中添加辅助的越行限制约束：

为很大的正数。

3.3 基于限制主问题的分支定界算法

线性松弛问题M2的最优解可能不满足整数约束(7)，但提供了原问题的一个下界。为求解出模型M1满足整数约束的最优可行解，本文设计基于限制主问题的分支定界算法。

其中：FK表示当前可行域X中已经固定的列车时空路径所包含的弧集。EK表示当前可行域X中已经剔除的列车时空路径所包含的弧集。表示当前分支定界树中存储的节点集，即子问题M1(X)的集合。具体地分支定界算法步骤如下(算法3)：

4 算例分析

为验证本文方法的有效性，在图3所示的铁路区段进行算例测试。该铁路区段可视为包含3个相关联列车运行径路的小规模路网。在此考虑300 km/h和250 km/h2种不同等级列车共线运行时该路网通过能力的优化。

图4对比了本文分支定界(B & B)算法和PLS算法的求解过程。从图4可见，B & B算法最优解的总目标值(上界)与其下界的间隙非常小且明显优于PLS算法。PLS算法曲线1，2表示PLS算法迭代时调整高速列车发车间隔会改善优化结果，但程度有限。

图3 算例路网列车停站方案

图4 B & B算法及PLS算法迭代过程

图5 PLS算法运行图

图6 考虑越行限制B & B算法运行图

在图7中，由于B & B算法结果的能力值目标大于PLS算法的能力值目标，因此会出现B & B算法的旅行时间目标值大于PLS算法的情况，但B & B算法的在不同场景下的总目标平均比PLS算法改善4.6%。

图7 旅行时间权重变动条件下2种目标对比

当考虑越行限制时优化结果如图8所示，其总体特征与图7类似，但所得运行图的结构发生了明显的变化。B & B算法所得结果中高速列车数的能力目标值减少而中速列车能力目标值增加，但总体优于PLS算法的结果，如图9和图10所示。

图8 限制越行次数时求解结果

表1列出中速列车最小比例中速,r变化时各种算法优化解的灵敏度分析结果。该组结果表示B & B算法可以在满足列车数比例的同时得到比PLS算法总目标平均提高3.85%的解。

图9 有越行限制时高速列车能力值目标对比

图10 有越行限制时中速列车能力值目标对比

图11 单弧缓冲时间变化时求解结果对比

将时空网络中每个列车弧的旅行时间费用加入缓冲时间时(在此取0.2~1.6 min)求解结果如图11所示。B & B算法在不同的缓冲时间的目标值比PLS算法平均改善5.12%(表2)。此外，B & B算法的各区段总的平均旅行时间同样少于PLS算法的总平均旅行时间。

表1 中速列车最小比例变化时目标值对比

表2 单弧缓冲时间变化时目标值及平均旅行时间差对比

5 结论

1) 考虑多等级列车共存铁路网通过能力最大条件下运行图优化模型。该模型对于提高繁忙路网运输效率、缓解供需平衡具有实际意义。

2) 对模型采用D-W分解转化。采用列生成算法处理变量规模过大的问题并求得原问题线性松弛问题的解。在此基础上设计分支定界算法实现松弛解的最优整数化处理。以小规模路网为例验证了本文方法求得较好质量解的灵活性。

3) 为使得运输能力的时间分布与客流需求更为吻合，可以在本文方法的基础上结合客流需求的时间波动性和运行图的周期性等因素开展进一步研究。

[1] 赵丽珍. 高速铁路区间通过能力计算与分析[J]. 中国铁道科学, 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]. 中国铁道科学, 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]. 铁道科学与工程学报, 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] 王华. 基于规格运行图的铁路运输能力探讨[J]. 交通运输工程与信息学报, 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

中国铁路总公司科技研究开发计划资助项目(KTD16011531)；中央高效基本科研业务费专项资金资助项目(2014JBZ2008)

周磊山(1962−)，男，湖南洞口人，教授，博士，从事运输组织现代化理论与技术研究：E−mail：lshzhou@bjtu.edu.cn

(编辑 蒋学东)