高铁列车运行图和到发线分配的协同编制方法

张 琴，朱晓宁，王 力，商 攀

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

高速铁路(以下简称“高铁”)多条线路相交时，传统列车运行图铺画采用“先单独铺画每条线路，再协调车站到发线分配”的方法.随着高铁不断建设，线路交叉频率越来越大，衔接枢纽站的车站通过能力成为限制路网通过能力的瓶颈，多线路列车运行图在衔接枢纽站的协调问题 “牵一发而动全身”，获得高效可行的列车运行图愈加困难.考虑车站到发线和咽喉区资源，同时编制列车运行图和到发线分配方案能够更好地协调多线路、多车站资源利用，具有重要研究意义.

编制列车运行图和到发线分配方案是铁路运输组织的经典问题，既有研究主要将两类问题单独求解及优化[1-2].针对列车运行图编制问题，大多数学者基于宏观角度，将铁路运输网络划分为区间和车站两部分[3]，Zhang等[4]建立了高铁周期列车运行图优化模型，车站主要考虑到发线数量约束，未涉及车站内部结构及具体到发线分配，假设列车上下行独立运行，互不干扰.扰动情况下调整优化列车运行图通常以闭塞分区或者轨道区段为最小研究单位，造成决策变量的增加，对求解算法提出了极高的要求[5-6].为了解决到发线分配问题，大多数学者通过建立不同的多目标规划模型进行优化[7-8]，其中部分学者并未考虑车站咽喉区资源利用情况[9-10]，乔瑞军等[11]假设上下行系统相互独立，但成网条件下不同方向列车在衔接枢纽车站相互干扰，无法分解.

针对高铁成网条件下，考虑车站到发线和咽喉区资源利用的多线路列车运行图协同编制方法的研究尚不多见.本文作者基于灵活使用到发线的规则，提出区间-咽喉区-到发线三段式列车运行图编制框架，从中观角度，构建基于时空网络的高铁列车运行图和到发线分配方案协同编制0-1整数规划模型，编制多线路、多车站的列车运行计划，并使用整数规划商业求解器CPLEX进行模型求解.算例结果验证了模型的有效性，同时表明中观层面建模既能够考虑到发线的具体分配，又能够有效降低模型规模.

1 问题描述

1.1 列车运行图和到发线分配问题

列车运行图规定了各列车在物理网络中的运行路径以及在各车站等关键节点的到、发和通过时刻.编制过程中，通常将车站视为一个具有到发线数量约束的点，不考虑车站资源的利用，将两站之间的区间线路视为一个整体，同时，上下行列车通常单独规划，互不干扰.

到发线分配问题通常以列车运行图为输入，将其规定的当前车站所有列车合理地分配到到发线上，使其进路无冲突且满足各项安全技术要求[8].因此，到发线分配问题不仅要考虑到发线资源，还应考虑咽喉区资源.

列车运行图编制和到发线分配是密不可分的，传统分步式编制方法生成的列车运行图可能无法生成可行的到发线分配方案，需要重新进行列车运行图的调整，并重复循环该过程直至两类方案均可行.

1.2 协同编制时空网络构建

为了考虑车站咽喉区占用和到发线的具体分配，将列车运行图传统的区间-车站的宏观图形表示方法重构成区间-车站咽喉区-车站到发线的中观图形表示模式，构建如图1左侧所示的物理网络.从中观角度将高速铁路运输网络中的车站划分出到发线资源，而区间线路保持为一个整体.高铁物理网络由点和边构成，其中点主要用来表示列车进站点(图1左侧点1、8)、列车出站点(图1左侧点2、7)、车站中心线所在的各到发线上的点(图1左侧点3—6)以及列车在区间需要进行径路选择的关键性节点(区间正线和联络线的交点)，边用来表示衔接两个点的线路.

图1 高铁时空网络示意图Fig.1 Space-time network diagram for high-speed railway

高铁时空网络由点和时空弧构成，见图1右侧.其中，时空网络中的点是物理网络中的点在时间上的拓展，时空弧包括区间运行弧、咽喉区运行弧和到发线等待弧三类，分别表示列车在区间、咽喉区和到发线上的时空轨迹.根据列车运行方向，区间运行弧和咽喉区运行弧可以进一步划分为上行运行弧和下行运行弧两类；根据作业类型，咽喉区运行弧可以分为进站运行弧和出站运行弧两类；根据进路是否切割正线，咽喉区运行弧可以分为一般运行弧和反向占用运行弧.

给定带有冲突的理想列车运行图，为了生成无冲突、安全的基本列车运行图，假定铁路旅客运输计划编制部门可采取以下调整措施：①延迟列车在起点的理想发车时间；②延长列车在车站到发线上的停留时间；③调整车站到发线分配方案；④取消列车.为了表示列车在起点的延迟和取消，本文同时引入了列车起点等待弧和列车虚拟运行路径.

2 协同编制模型的建立与求解

2.1 模型假设

模型假设如下：

① 理想列车运行图(有冲突)、线路运行(包括安全间隔时间)等基本资料已知；

②列车在起点的允许调整时间窗长度以及在各车站的最小、最大停站时间给定；

③ 车站咽喉区道岔同时解锁，同一列车在车站咽喉区的接、发车进路走行时间相同；

④ 列车的长度忽略不计；

⑤ 时间精度为1 min.

2.2 模型的构建

(1)

单一列车径路的时空网络流平衡约束条件为

(2)

(3)

列车在车站的最小和最大停站时间约束为

∀f∈F,∀k∈Kf

(4)

安全间隔约束条件是列车运行图编制和到发线分配问题的复杂约束条件，主要包括区间安全间隔约束、车站咽喉区进路安全间隔和到发线使用安全间隔约束.

区间安全间隔约束包括接、发车安全间隔两类约束，假设Ta、Td分别表示接、发车安全间隔时间，对于任意的时空点v∈Vd∪Vse，定义其发车不兼容弧集为

对于任意的时空点v∈Va∪Vse，定义其接车不兼容弧集为

任一不兼容弧集中的所有时空弧仅可被一列列车占用，因此，区间安全间隔约束为

(5)

(6)

则对于所有车站从同一进站点接入或者从同一发车点发出的列车应满足的咽喉区进路安全间隔约束条件为

(7)

(8)

图2 车站接车进路冲突及发车进路冲突示意图Fig.2 Schematic diagram of receiving-receiving and departure-departure conflicts

为了避免图2中接车进路之间以及发车进路之间的冲突，对于衔接多线路的车站，其咽喉区不同起点接车、不同终点发车安全间隔约束条件为

(9)

(10)

(11)

因此，车站到发线安全间隔约束可转化为任意到发线等待弧最多能被一列列车实际占用或者隐含占用，约束式为

∀g∈Ast

(12)

2.3 模型求解

中观层面时空网的合理构建，不仅减少了决策变量个数，同时也减少了一定数量的约束条件，主要包括：①车站正线通过约束[11]；②到发线占用唯一性约束[12].

各类不兼容弧集合或者不兼容边集合的构建，能够实现对复杂安全约束条件的预处理，方便了复杂安全约束条件的构建，使得本文能够直接采用CPLEX12.9 对模型进行求解.

3 算例研究

高速铁路路网示意图见图3.图3中有两条高铁线路，3个车站，中观线路物理网络共37个点，75条边，研究时长为100 min，研究列车共44列，区间正线各段运行时间为4 min，联络线运行时间为2 min，车站1进路走行时间为2 min，车站2、3进路走行时间为1 min.

3.1 中、微观层面下构建网络的规模对比

假设图3中微观层面区间单方向闭塞分区个数为10个，每个车站咽喉区列车径路选择点为轨道区段的起讫点.从中观和微观层面构建图3的线路物理网络的规模对比见表1.由表1可见，相较于微观层面构建的网络规模，从中观层面构建网络使得点的数量减少了70%以上，边的数量减少了75%以上，很大程度上减少了模型的决策变量个数.

图3 高速铁路路网示意图Fig.3 Schematic diagram of high-speed railway network

表1 中、微层面构建线路物理网络的规模对比Tab.1 Comparison of the railway network scale from microscopic and macroscopic perspectives

3.2 列车数量同求解时间的变化

假设列车在起点的出发时间窗长度为5 min，停站列车最小停站时间为1 min，停站时间范围为4 min(即最大停站时间和最小停站时间的差值)，不同列车数量下求解时间对比见表2.由表2可以看出，随着列车数量的增加，求解时间整体呈现出增长的趋势，但是所有场景仍然能够在较短的时间内求得最优解.

表2 不同列车数量下求解时间对比Tab.2 Comparison of solution time under different train numbers

场景2-9下不同车站区段列车运行图见图4.由图4可见，车站1、2区段以及车站1、3区段的最优列车运行图和到发线分配方案均满足各项安全技术作业需要，验证了模型的有效性.相较于已知的有冲突存在的理想列车运行图，有3列列车取消.

图4 场景2-9下不同车站区段列车运行图Fig.4 Train operation diagram for different station sections under scenarios 2-9

3.3 列车路径规模同求解时间的变化

对于每列列车的可行路径规模主要取决于列车起点出发时间窗长度和停站时间范围两个因素，两种因素的改变对模型求解时间有不同的影响，不同列车路径规模下求解时间对比见表3.设定两种环境，环境一下列车停站时间范围相同，其他条件保持不变，共5种场景(3-1至3-5)；环境二下改变车站停站时间范围，其他条件同样保持不变，共5种场景(3-2、3-6至3-9).由表3可以看出，在环境一下，求解时间随着起点时间窗长度的增长，整体呈现增长的模式，且变化较大；在环境二下，求解时间随着停站时间范围的增加，几乎保持不变.

表3 不同列车可行路径规模下求解时间对比Tab.3 Comparison of solution time under different train feasible path numbers

4 结论

在列车运行图编制过程中考虑车站到发线的具体分配及咽喉区资源的占用，研究了多线路列车运行图和多车站到发线分配协同编制问题.通过设计算例，比较了不同影响因素对模型求解时间的影响，验证了模型有效性.本文直接使用CPLEX方法求解对于中小规模问题有效，大规模问题下，研究更加快速有效的求解算法是今后的重点工作.具体结论如下：

1)中观层面高速铁路网络的构建，相较于宏观层面能够具体考虑车站资源利用情况，相较于微观层面网络规模能够减少70%以上，很大程度上减少了决策变量个数.

2)模型求解时间同列车数量和列车可行路径规模整体呈正相关，可行路径中，列车起点时间窗长度影响较大，车站停站时间范围影响相对较小.