基于灵活接续的周期性列车运行图加线模型

徐涵，聂磊，谭宇燕



基于灵活接续的周期性列车运行图加线模型

徐涵1, 2，聂磊1，谭宇燕1

(1. 北京交通大学 交通运输学院，北京 100044； 2. 中国铁路经济规划研究院，北京 100038)

周期性列车运行图的编制技术在国内外已有较多研究，在周期图的基础上，如何合理加入非周期列车运行线成为“周期+非周期模式”列车运行图在我国铁路网大规模应用中亟待解决的问题之一。此外，“周期+非周期模式”下列车接续关系更为复杂，而我国高速铁路发展迅速，列车运行图随线路的开通不断调整，短时间内难以形成符合市场运营需要的接续关系。针对上述问题，基于周期图的加线模型，考虑周期结构和灵活接续等约束，构建基于灵活接续的周期性列车运行图加线的混合整数规划模型，以实现列车接续方案设计与“周期+非周期”运行图编制的综合优化，并通过算例分析，验证了模型的有效性，提高了“周期+非周期模式”列车运行图的可实施性。

高速铁路；周期性列车运行图加线；灵活接续；事件活动图

列车运行图是铁路组织列车运行的基础，它规定各次列车占用区间的顺序，是规定列车与车站、铁路线路区间之间时空关系的重要技术文件[1]。周期性列车运行图由于服务频率高、列车车站到发和列车停站方案比较规律等特点，成为国外高速铁路普遍采用的运行图模式[2−5]，但由于我国高速铁路“点多、线长、面广、跨线列车多”的特点，一些线路只能采用部分列车周期运行、部分列车非周期运行的模式，即周期与非周期相结合的模式。“周期+非周期模式”列车运行图编制是指在周期图的基础上，添加一些开行频率低、运行时间长非周期运行线，以实现周期图与非周期图的综合优化[6]。如果采用周期与非周期一体化编制列车运行图，构建的模型中变量关系较为复杂，求解难度较大，且不能保证求解结果中周期性列车运行线的周期性。此外，国内外对纯周期运行图编制已有完善的编制理论和系统，故可以采用分阶段编制列车运行图的思想，在周期图的基础上加入非周期列车运行线，尽最大可能保证周期性列车运行线的周期结构，以实现周期与非周期列车运行图的综合优化。本文研究基于周期图的加线技术，这是“周期+非周期模式”列车运行图编制的一个重要方面，是实现周期与非周期相结合的列车运行图编制的关键技术之一。列车运行图加线问题是一个集列车运行图优化编制与优化调整的综合优化问题。Burdett等[7]基于Alternative Graph提出以最小破坏加权时间窗、最小完成时间为目标的旅客列车插线模型，并用元启发式方法求解。Tan等[6, 8−9]针对周期性列车运行图的加线问题，使用Event-Activity Graph建立周期图加线模型，将接续方案固定并把接续作为约束在模型中考虑。张红斌等[10]通过对运行图加密来研究客运专线的能力问题，建立整数规划模型，并构建运行图加密系统进行求解。目前，既有加线模型都是采用固定的接续关系作为约束条件，即在加线模型中列车接续关系是确定的，接续方案中某列车的后续列车是固定不变的。在运行图编制模型中，Peeters等[11−12]在周期图编制模型的基础上提出了灵活接续的概念，即事先不给定列车接续的后续列车，将接续列车的确定嵌入到运行图编制过程中，证明了在周期图的编制过程中考虑灵活接续增加了接续形成的可能性。然而，“周期+非周期模式”下的列车接续关系除了周期线之间的接续关系还包括周期线与非周期线的接续关系、非周期线之间的接续关系，接续关系非常复杂。在加线过程中，如采用固定接续关系，将很大可能性无法得到最优解甚至无解。并且我国高速铁路发展迅速，列车运行图随线路的逐步开通不断调整，短时间内形成符合市场运营需要的固定接续关系难度较大[13]。因此，在“周期+非周期模式”下采用灵活接续的接续方式很有必要。本文首先建立基于固定接续的周期图加线模型，在此基础上综合考虑灵活接续约束，即在接续方案中事先不给定列车接续的后续列车，将接续列车的确定嵌入到运行图加线模型中，建立基于灵活接续的周期图加线模型，在满足接续条件的备选列车中选择最优接续方案以实现列车接续方案设计与列车运行图编制的综合优化。

1 基于固定接续的周期性列车运行图加线模型

为了更好地表示运行图中特殊的拓扑结构，本文基于事件活动图(Event-Activity Graph)[12]，考虑原周期图的调整约束和周期图的结构约束，建立了基于固定接续的周期性列车运行图加线模型，以实现周期运行线和非周期运行线的全局优化。

1.1 事件活动图(Event-Activity Graph)

事件集合中的元素由弧()连接起来，称之为活动。每个活动都被定义了上限和下限，用来定量化的表示该活动的时间窗。本文涉及到的活动按照表达内容可以分为以下4种。

图1 事件活动图

1.2 变量及参数说明

模型涉及到的集合，参数和变量及相应的说明见表1~3。

表1 模型中涉及的集合及说明

表2 模型中涉及的参数及说明

表3 模型中涉及的决策变量及说明

1.3 模型描述

以对原图总调整时间最小为目标，建立基于固定接续的周期性列车运行图加线模型(以下简称“M1模型”)。

式(1)为模型的目标函数，表示对原图总调整时间最小。

式(6)~(7)为安全间隔约束，表示2相邻列车在同一车站的到达、通过、出发的最小时间间隔，h为安全时间间隔。实际上，式(6)~(7)保证了任意安全间隔弧两端的事件和事件满足约束：

式(8)为区间越行约束，表示同一区间内2出发事件的先后顺序，()和()分别为事件和事件的后续事件。该约束用来表示在每个区间内，任意2列车的在区间起点发车的先后顺序要与这2列车在区间终点的到达顺序保持一致，即任意2列车在区间内的到发顺序不能发生改变，禁止在区间内发生越行行为。

式(9)为固定接续约束，表示接续后续列车在接续车站的出发时间与前续列车在接续列车的达到时间要满足接续的时间范围。

式(12)表示周期图结构约束，为了最大限度的发挥原周期性运行图的优势，保证在加入非周期运行线之后原周期图之间存在的接续关系不受到破坏，规定在新图中，原周期图中包含的运行线必须保持原图的周期结构。

2 基于灵活接续的周期性运行图加线模型

相比固定接续，灵活接续有接续的后续列车不固定、需要在满足条件的备选列车中选择后续列车的特点，基于灵活接续的周期性运行图加线模型，在基于固定接续的周期图加线模型(M1)的基础上，以对原图总调整时间和未满足的接续数量加权之和最小为目标，约束上采用考虑灵活接续的相关约束条件取代固定接续约束，来适应“周期+非周期”模式下的列车接续问题。

2.1 “周期+非周期模式”下的灵活接续问题

“周期+非周期”运行图模式下存在的列车接续关系按列车种类不同可以分为周期运行线之间的接续关系，周期运行线与非周期运行线之间的接续关系，非周期运行线之间的接续关系。在加线的过程中既要满足对原周期列车的调整程度最小，同时还要满足不同种类的接续关系，并减少列车接续时间，确定最优的接续方案。

图2 “周期+非周期”运行模式下灵活接续图

“周期+非周期”运行图模式下列车的灵活接续如图2所示，图中1，2和3表示列车Train1可能的加线位置。

1) 如果采取固定接续，即指定Train1接续的后续列车为Train2，则列车Train1的加线位置只能在位置1；

2) 如果采用灵活接续，即任意满足接续条件的列车都可以作为Train 2的后续列车，则加线列车Train1可以加在位置1，此时接续列车Train2；或加在位置2，此时接续列车Train3；或加在位置3，此时接续列车Train4。

由此可见，灵活接续较固定接续，扩大了加线范围，可以在满足接续约束的条件下选择最合适的加线位置，从而实现列车接续方案设计与列车运行图编制的综合优化。

2.2 模型描述

在周期图加线模型(M1)的基础上，将M1模型中式(9)固定接续约束改写为灵活接续约束(14)~(23)，建立基于灵活接续的周期性列车运行图加线模型(以下简称“M2模型”)。灵活接续约束涉及到的变量如表4所示。

表4 灵活接续约束中涉及的决策变量及说明

s. t.

式(13)为模型的目标函数，表示原图总调整时间和求解结果中未满足的接续数量加权之和最小。

约束(22)~(23)为变量c的约束，变量c表示最终选择的接续，式(22)表示接续弧需满足接续条件才有可能被选择。式(23)表示对于每一个接续而言，最终选择唯一列车作为最优接续提供给旅客或者该接续在求解过程中得不到满足。

基于灵活接续的周期性列车运行图加线模型为混合整数规划模型，可采用IBM ILOG CPLEX 12.5软件求解。

3 案例分析

根据“基于灵活接续的周期性列车运行图加线模型”，本文开发了基于.net的周期性列车运行图加线系统。

3.1 数据准备

1) 车站线路数据。以京沪高速铁路单方向列车运行图铺画为例，涉及到京沪高铁沿线23个车站。

2) 周期性列车运行图。选择以2 h为周期，周期数为5，单周期列车数为13列，5个周期共60列车的周期性运行图作为加线之前的原周期列车运行图。单周期的列车开行方案如图3所示。

3) 非周期运行线及接续信息。设计加入10条非周期运行线，列车车次为101~110，并将非周期运行线的停站方案、列车始发时间窗及非周期列车的换乘车站和换乘目的地作为模型的输入。

4) 参数选择。设置停站时间范围为1~6 min，接续时间范围为15~30 min，相对于原图的最大调整程度Δ=3 min，对原周期结构最大的调整程度=3 min。

目标函数中，为统一量纲，考虑到多满足一个列车接续与周期性列车运行线调整1 min相比，多满足一个列车接续对运行图服务水平的影响大，因此，满足列车接续的惩罚值相对比较大。根据优化目标，分别对周期图调整和未满足列车接续系数12设置不同的取值，求解结果如表5所示，其中(1,1)表示1取值为1且2取值为1。

图3 周期性列车运行图开行方案

表5 不同目标函数系数求解结果对比

分析可得，12取值为(1,10)，(1,15)和(1,20)时，10个接续全部满足，且取值为(1,15)在10个接续全部满足的3组方案中平均接续时间最短、列车总停站次数和总停站时间最少，列车平均旅行速度最快。因此，本案例中目标函数系数12取值为(1,15)。

5) 固定接续对照。为了将灵活接续和固定接续结果进行对比，特设置了3组固定接续的情景与灵活接续进行对照，3组固定接续的接续需求与灵活接续相同，且原图、加线列车和各参数设置相同，每个接续分别设置了不同的后续列车，如表6所示，并用M1模型对固定接续进行求解。

3.2 案例结果及分析

运用周期性列车运行图加线系统对M2模型精确求解，得到基于灵活接续的周期与非周期结合的列车运行图，如图4所示，图中灰线代表原周期性列车运行线，红线代表新加入的非周期运行线，蓝色横线代表模型求解出的列车接续。求解得到列车总调整时分为12 min，求解得到所有接续都得到满足，平均接续时间为23.0 min。原周期图列车平均旅行速度为232.1 km/h，插入非周期运行线后的周期线的列车平均旅行速度为232.1 km/h，加线列车的平均旅行速度为226.4 km/h。可见，本案例加入非周期运行图对原图的影响较小，接续都得到满足，加线效果较好。采用灵活接续求解的接续方案如表7所示。

表6 不同情况下固定接续设置

图4 基于列车接续的周期与非周期结合的列车运行图求解结果

表7 采用灵活接续最优接续方案

将该案例采用M2模型(基于灵活接续)的求解结果与M1模型(基于固定接续)不同情景下的求解结果进行对比，如表8所示。分析可得，采用M2模型所求得的运行图对原图调整和平均接续时间均小于M1模型。虽然M1模型中情景1的平均接续时间与M2相差1.5 min，但是相对于原图的调整时间要比M2多13 min。此外，其他指标(总停站次数、总停站时间和平均旅行速度等指标)M2的求解结果也优于M1，M2优于M1的求解得到的结果，说明采用灵活接续在满足列车接续最多和对原周期图调整程度小的前提下并没有影响运行图的其他特征。

因此，综合对比分析灵活接续的求解结果和不同情景下固定接续的求解结果，在周期性列车运行图的加线问题中考虑灵活接续扩大了解空间，提高了求解质量。

表8 灵活接续与不同情景下固定接续求解结果对比

4 结论

1) 在周期图加线问题的基础上，基于事件活动图(Event-Activity Graph)，以对原周期图调整时间和未满足的接续数量加权和最小为目标函数，构建基于灵活接续的周期图加线的整数规划模型。

2) 通过算例求解并与固定接续的求解结果进行对比，验证模型的实用性和有效性，提高了“周期+非周期”模式列车运行图的可实施性，并为“周期+非周期”模式下的列车接续设计提供决策参考。

3) 列车接续方案的选择与客流需求密切相关，列车接续方案的确定也必须有客流依据。为此，需要进一步根据客流因素确定列车接续需求。同时，下一步研究方向应重点考虑车站股道数约束与动车组运用等因素，以完善列车接续方案设计与列车运行图编制的综合优化。

[1] 孟学雷, 徐杰, 贾利民. 列车运行图稳定性研究综述[J]. 铁道科学与工程学报, 2013, 10(2): 96−102. MENG Xuelei, XU Jie, JIA Limin. Review on train timetable stability[J]. Journal of Railway Science and Engineering, 2013, 10(2): 96−102.

[2] 汪波. 基于周期化运行的轨道交通列车开行方案和运行图研究[D]. 北京: 北京交通大学, 2007. WANG Bo. Research on operation plan and working diagram of rail traffic based on periodic running mode[D]. Beijing: Beijing Jiaotong University, 2007.

[3] 郭根材, 聂磊, 佟璐, 等. 基于备选列车接续的周期性列车运行图编制模型研究[J]. 铁道学报, 2016, 38(8): 8−15. GUO Gencai, NIE Lei, TONG Lu, et al. A new timetabling model for potential connections[J]. Journal of the China Railway Society, 2016, 38(8): 8−15.

[4] 胡滨玺. 客运专线周期化列车运行图铺画方法研究[D]. 成都: 西南交通大学, 2014. HU Binxi. Study on the method of periodic diagram generation for high speed railway[D]. Chengdu: Southwest Jiaotong University, 2014.

[5] ZHANG X, NIE L. Integrating capacity analysis with high-speed railway timetabling: A minimum cycle time calculation model with flexible overtaking constraints and intelligent enumeration[J]. Transportation Research Part C Emerging Technologies, 2016, 68: 509−531.

[6] Tan. Techniques for inserting additional train paths into existing cyclic timetables[D]. TU Braunschweig, 2015.

[7] Burdett R L, Kozan E. Techniques for inserting additional trains into existing timetables[J]. Transportation Research Part B: Methodological, 2009, 43(8−9): 821−836.

[8] Tan Y, Jiang Z. A branch and bound algorithm and iterative reordering strategies for inserting additional trains in real time: A case study in Germany[J]. Mathematical Problems in Engineering, 2015(2015−03 −22), 2015, 2015: 1−12.

[9] Jiang Z, Tan Y, Özgür Yalçınkaya. Scheduling additional train unit services on rail transit lines[J]. Mathematical Problems in Engineering, 2014(2014−09−25), 2014, 2014: 13.

[10] 张红斌, 董宝田. 基于能力计算的运行图加密问题研究[J]. 交通运输系统工程与信息, 2011, 11(4): 129−134. ZHANG Hongbin, DONG Baotian. Railway timetable saturation based on capacity calculation[J]. Journal of Transportation Systems Engineering and Information Technology, 2011, 11(4): 129−134.

[11] Peeters L W P. Cyclic railway timetable optimization[D]. Erasmus University Rotterdam, 2003.

[12] Kroon L G, Peeters L W P, Wagenaar J, et al. Flexible connections in pesp models for cyclic passenger railway timetabling[J]. Transportation Science, 2014, 48(1): 136−154.

[13] 郭根材. 高速铁路周期性列车接续方案编制理论和方法[D]. 北京: 北京交通大学, 2015. GUO Gencai. Theory and method of cyclic train connection plan for high speed railway[D]. Beijing: Beijing Jiaotong University, 2015.

[14] Schöbel A. A model for the delay management problem based on mixed-integer-programming[J]. Electronic Notes in Theoretical Computer Science, 2001, 50(1): 1− 10.

[15] Bel A. Integer programming approaches for solving the delay management problem[C]// International Dagstuhl, Atmos Conference on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems. Springer-Verlag, 2004: 145−170.

(编辑 阳丽霞)

The adding train paths model on cyclic timetable based on flexible connection

XU Han1, 2, NIE Lei1, TAN Yuyan1

(1. School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China; 2. China Railway Economic and Planning Research Institute, Beijing 100038, China)

Cyclic train timetable has already been adopted on many high-speed railway countries. Then a hybrid timetable mode named “cyclic +non-cyclic” timetable which consists of both cyclic and non-cyclic timetable is possible. Nowadays, the models and algorithms for cyclic timetabling is well developed, but the technique to insert extra train paths into a cyclic timetable is still in a significant demand for research. In addition, as a distinctive feature of cyclic timetable, the convenient transfer connection plan is still not determined in China HSR due to the rapid development of the network. This paper constructed an adding train paths model based on an existing cyclic timetable by considering the constraints of periodic structure and flexible connection, in order to get integrated optimization on both connection planning and “cyclic+non-cyclic” timetable scheduling. At last, a case study of Beijing- Shanghai HSR was used to verify the effectiveness of proposed model and method.

high-speed railway; adding train paths to cyclic train timetable; flexible connection; event-activity graph

10.19713/j.cnki.43−1423/u.2018.09.034

U292.4

A

1672 − 7029(2018)09 − 2439 − 09

2017−06−30

国家自然科学基金资助项目(U14342207)；中国铁路总公司科技研究开发计划资助项目(2016X005-D)

聂磊(1970−)，女，湖南长沙人，教授，博士，从事运输组织理论与技术研究；E−mail：lnie@bjtu.edu.cn