基于突发故障的高速列车运行调整研究

彭其渊，陆柳洋，占曙光

（西南交通大学，交通运输与物流学院，成都 610031）

0 引 言

高速铁路因其速度快，运行平稳性好，晚点率低等特性，在我客运市场上占据一定份额。铁路系统内部子系统之间具有较强的耦合性，如果铁路区间突发故障之后列车运行调整处理不当，则会出现大面积列车晚点等不良影响。

近年来，如文献[1]所述，国内外学者对于列车运行调整产生了极大的兴趣，并深入研究微干扰情景下的调整方案；文献[2-6]从微观角度对微干扰下的列车运行调整问题进行系统研究，采用替代图的方法构建模型，并基于此开发了ROMA系统；文献[7]分析区间封锁或半封锁状态的列车运行调整研究；文献[8]在文献[7]的基础上同时考虑车底运用与运行图调整，最后结合实例验证。

国内方面，文献[9-11]研究区间故障全失效的情况下，利用事件-活动网络建立混合整数线性规划模型，并用京沪高铁实例进行验证。不过文中并没有详细考虑故障发生后，区间运行列车由于车站能力限制而无法停靠车站的情景；文献[12]对于不能确定故障持续时间的列车运行调整问题设计了“两阶段带补偿随机期望模型”，并在讨论多阶段递归决策概念模型复杂度的基础上最终给出了不完全连续多阶段决策模型；文献[13]研究了动态随机环境中的铁路调度鲁棒性问题，建立单线铁路故障调整模型并采用滚动时域方法求解；文献[14]在文献[13]的基础上，对双线铁路网络进行模糊可靠性优化并通过两阶段0-1整数规划模型进行求解。

高速铁路列车由于运行速度高，除了枢纽站等大站外，中间站只配有少量到发线。因此在行车密度较大时，极易发生以下情形：当故障发生时，在故障区间（e，e+1）内运行的列车若已经越过故障区域，则该列车仍按计划运行，否则该列车必须返回后方站e停车，并占用该站到发线；与此同时，按图定计划在相邻后方区间（e-1，e）内运行并即将驶入站e的多列列车可能因为车站e没有足够的到发线供其停车而返回后方站e-1停车或区间停车。

在满足列车安全运行各项约束的前提下，本文系统考虑了故障发生时区间运行列车的停车问题，并基于此做出调整方案，协助调度员的调度决策。

1 问题描述与界定

问题假设：由于列车运行调整涉及因素复杂，为研究方便，作以下假设（下述假设可以根据现场实际情况进行适当的松弛或修改）：

（1）故障一旦发生，可以预测故障结束时刻；

（2）所有列车均允许区间停车且每一区间内区间停车列车数量至多为1列；

（3）列车返回后方车站运行时间可预知。

对于假设（2），根据广铁集团《调度所管理工作细则》第227条规定，调度员不能以机外停车作为列车运行调整手段，除非遇到行车设备临时故障、交通事故、自然灾害等特殊情况。不过当上述特殊情况发生时，《调度所管理工作细则》并没有对列车区间停车的数量做出详细规定。因此，本文假设每一区间内区间停车列车数量至多为1列。

问题描述：本文定义区间运行列车特指在某一时刻正在某区间内运行的列车。本文为处理区间运行列车停车问题，在故障发生时区间运行列车所在位置处设置虚拟站，将列车区间停车视为虚拟站停车。为了更清楚地描述本文所要研究的问题，下面用一个简单例子进行说明，见图1。

图1 列车区间停车运行调整示意图Fig.1 The diagram of train interval parking rescheduling

已知下行方向有4列列车t1、t2、t3和t4，分别用实线表示其运行线；设置7个车站，横向实线表示实际存在的车站s1，s2，s5，s7；横向虚线表示虚拟站s3，s4，s6。假设在时刻h1，车站s5和s7之间的区间内发生故障，导致该区间丧失通过能力，并初步估计故障将持续到h2。故障发生时，列车t1、t2和t3仍在区间内运行。若此时车站s2，s5剩余可用到发线数量分别2条和1条。为了避免列车停在故障区间影响救援，列车t1需返回后方站s5停车，虚线运行线表示返回过程。根据车站能力，车站s5则无法再停靠其他列车。由此，列车t2可根据晚点影响最小化目标，选择区间停车或返回后方车站停车，此处，列车t2可选择区间停车，即停留在虚拟站s4。按照假设规定，列车区间停车数至多为1列，因此列车t3返回车站s2，并占用1条到发线。此时车站s2仍有1条到发线剩余，因此相邻后方车站可向区间(s1,s2)发车，那么列车t4从站s1出发，并运行至车站s2停车。故障结束后调度员还需合理调整列车t1、t2、t3和t4的出发顺序和到发时刻，减少故障带来的影响。

2 模型建立

2.1 符号说明

在模型中未解释的参数符号与变量将分别在表1与表2中统一说明。

表1 参数符号及意义Tab.1 Parameter notations

表2 变量符号及意义Tab.2 Variable notations

2.2 模型构建

一般情况下，故障发生时仍在区间内运行的列车能够在前方站停车。但考虑车站能力限制和故障随机性，可能出现区间运行列车不能进入前方车站停车，模型构建时定义虚拟车站集合Sf和真实车站集合SF，S=Sf∪SF。

2.2.1 基本模型

目标函数式（1）表示列车到达晚点最小化；式（2）表示调整后列车发车时刻不早于图定时刻；式（3）限定列车在某一区间的运行时分并考虑起停附加时分，其上下限可根据实际情况更改，本文限定运行时分上限为列车区间纯运行时分加起停附加时分，下限为列车区间运行时分加实际起停附加时分；式（4）表示如果列车t在车站s停站，则其在该站的停站时间必须大于最小停站时间，如果该列车在车站s不停车，则列车在该站的停站时间为0；式（5）表示如果某列车按计划运行图在某站停车（αts=1），则调整后该列车也必须在该站停车（θts=1）；式（6）中e表示故障区间（e,e+）端点站的索引号，该式表示：如果列车t在故障发生时尚未进入故障区间（dte≥h1），那么，列车需等到故障结束后尚可从e站出发；式（7）和（8）表示干扰发生之前，列车按照计划运行图运行，但是不包含在h1时刻的区间运行列车；式（9）限定变量的取值范围。

2.2.2 列车间隔与能力约束

（1）相邻列车运行间隔约束

根据自动闭塞要求，相邻列车运行过程中必须满足一定的间隔时间约束。间隔时间主要有三种：出发间隔时间I1、到达间隔时间I2及发到间隔时间I3。正常情况下，列车运行顺序在计划运行图中已经给定，但是在故障情况下，相邻列车之间的运行顺序可能会改变。因此，对于每个区间内相邻列车之间的先后顺序，定义0-1变量

① 列车之间的出发间隔约束与到达间隔约束

对于任意两列列车t和t′在任意区间（s,s+）的端点站s和s+的出发与到达之间满足如下关系：

式（10）～（12）分别保证同一区间内两列车t和t′在区间两端点站的出发间隔时间和到达间隔时间满足最小间隔时间要求，且该相邻列车在区间一端点站的出发顺序和在同区间下一端点站的到达顺序保持相同，那么列车在区间不发生越行。

② 相邻列车发到间隔约束

对于在某一车站某出发列车与后续某到达列车之间的先后顺序，文中定义0-1变量利用该变量建立列车发到时间约束。

式（13）保证每个车站内，列车t从车站出发先于后续列车t′到达同一车站的发到间隔时间满足最小间隔时间要求。

（2）车站能力约束

本文以车站到发线数量代表车站能力。现实中若列车在站停车，那车站需提前预留一条到发线供列车占用；不停站通过的列车从车站正线通过，此时车站不需要提前预留空闲到发线。因此表达车站s到发线占用情况约束如下：

式（14）表示：列车t′即将进入车站s停车时该站必须预留空闲到发线。列车t′通过车站时则该站不需预留空闲到发线。

（3）有效不等式

① 列车越行与停站之间的关系约束

式（15）表示列车t被列车t′越行时，列车t必须在车站s停车（θts=1）。

② 列车发到顺序与区间运行顺序之间的关系约束

列车t从s发车先于t′到达该站，则列车t到达s站必定先于列车t′到达该站则建立如下约束：

2.2.3 故障时刻区间内运行列车停车约束

当区间故障发生时，由于车站能力限制，列车前方站并不能容纳所有区间运行列车，此时应考虑组织某些列车在区间停车或返回后方站停车。区间（e,e+）内发生故障时，若列车t仍在某区间内运行，则列车t所处位置设虚拟车站s，且仅允许列车t停车。由定义可知，虚拟站s与列车t之间存在一一对应关系，所以定义虚拟站s所对应列车记为t(s)。上述列车集合为设置0-1变量φts，定义如下：时刻h1,安排区间运行列车t在车站s停车否则

（1）虚拟车站属性约束

为了表示列车区间停车，模型设置虚拟车站。虚拟站实际上为某运行方向（上行或下行）上的一段铁路线路，不具有车站全部功能。如虚拟车站不组织列车越行；虚拟车站能力可视为1；由此建立如下约束：

式（17）规定虚拟站只允许1列列车停车；式（18）和（19）表示每个虚拟站（s∈Sf）不允许其他列车停车，除了对应列车t(s)；式（20）表示虚拟站（s∈Sf）不组织列车越行。

（2）单列列车停车方案唯一性约束

故障发生时列车必须要在故障区域之前停车，假如此时某一列车（t∈）在区间内运行，则该列车必须在某一车站停车。建立约束如下：

式（21）表示故障发生时区间运行列车t(s′)在某一车站停车。

（3）车站能力约束

（4）区间停车数量约束

区间停车数量可根据现场实际情况进行确定。本文规定，相邻真实车站组成的区间内至多允许1列列车区间停车，则

式（23）中{s'|s-＜s'＜s}表示相邻真实车站组成的区间(s-,s)内的虚拟车站集合。那么该式表示某一区间内的区间停车数不超过1列。

（5）单列列车返回后方站停车后再次出发的时刻约束

由于故障引起区间通过能力丧失，前方站能力限制以及区间停车数量限制，极可能需要组织故障时刻区间运行列车（t∈）返回后方实际车站停车。那么考虑如下情景：如果φts(′s)=1，s′∈SF，且车站索引号s′小于列车t(s)所对应的虚拟站索引号s，即s′＜s，那么列车t(s)返回后方车站s′停车。这说明列车t(s)的前方车站能力已经饱和，所以列车t(s)返回车站s′后的出发时刻至少为故障结束时刻h2，做如下约束：

式（24）表示若列车返回后方站停车，那么列车从该站再次出发的时刻至少为h2。

3 算法设计

由于列车运行调整属于NP-hard问题，随着列车和车站数的增加，模型求解呈指数型增长，直接求解模型十分困难。目前既有算法有时域滚动算法[15]，二阶段算法[10]以及其他启发式算法。前两种算法的本质思想是在保障解的质量的情况下，减小求解规模并提高求解速度。本文采用二阶段算法进行求解。算法步骤如下：

第一阶段：首先输入列车参数、车站参数以及故障信息：包括列车运行时刻X，车站到发线数目C，车站间隔时分I，起停附加时分τ，故障区间(e,e+)，故障起止时刻h1,h2。然后运用CPLEX计算式（1）～（24）。其中式（14）只对故障发生时段内的列车起作用，并输出初始方案。

第二阶段：输入第一阶段的初始方案，接着固定h2之前的运行图，然后用式（14）检验h2之后的调整方案是否可行。若可行，则该方案为整体最优解；若不可行，调度员可先执行h2之前的调整方案，然后基于初始方案，运用CPLEX计算式（1）～（16）调整h2之后的运行方案。

分析算法特性：故障结束时刻h2之前的调整方案可以快速求得，且必定满足车站能力要求；而h2之后的调整方案则需要车站能力约束检验。

4 算例分析

本文用武广客运专线实例来验证模型有效性。实例包含全天列车63列，车站16个。参数取列车发到间隔时间2min，发车间隔和到达间隔时间2min，列车的起停附加时分别为2min，3min。

本文根据不同区间故障和故障持续时间，设置以下3个场景进行算例分析：

场景1：下行方向第7个区间故障，故障发生时间为上午9：00，记为（7，9：00）；

场景2：下行方向第10个区间故障，故障发生时间为下午13：30，记为（10，13：30）；

场景3：下行方向第8个区间故障，故障发生时间为下午15：40，记为（8，15：40）。

模型使用CPU为Inter（R）Core（TM）i5-45903.30GHz、内存为8GB的计算机求解。求解软件为CPLEX并设定计算时间为300 s。各场景列车运行图调整结果如表3所示。

表3 运行图调整结果Tab.3 Train rescheduling result

当调整目标为列车到达晚点时间最小时，列车区间停车总比列车返回后方站停车节省时间。因此如表3所示，同一故障场景下不同故障情景的区间运行列车停车方案是相同的，即不随故障持续时间变化而变化。当然如果在目标函数中加入列车区间停车惩罚值，那么不同故障情景可能会有不同的区间列车停站方案，但列车区间停车惩罚系数难以确定，本文暂不讨论。

表3统计了场景1至3的关键数据，分别包括目标值、计算时间以及误差。

文章认为误差不大于10%的解是可以接受的近似最优解。当计算结果的误差超过10%时，例如情景（7，9：00，120），则用二阶段算法进行求解。第一阶段计算结果误差为9.58%，不过h2之后的调整方案不满足车站能力约束；然后进行第二阶段的计算，结果表明目标值在第一阶段基础上增加13min，且比CPLEX正常求解至误差为10%的目标值小1.9%，求解质量良好。

下面以故障情景（7，9：00，60）和（8，15：40，90）为例，给出调整后的运行图如图2、3所示。图中横坐标表示时间；纵坐标表示车站；列车运行图中实线运行线代表列车未偏离计划运行图，虚线运行线代表列车偏离计划运行图。

图2 列车运行调整方案Fig.2 Train rescheduling scheme

图2是情景（7，9：00，60）通过模型调整之后的运行图。区间8中的矩形是故障区域。

图3是情景（8，15：40，90）通过模型调整之后的运行图。区间8中的矩形是故障区域。列车在虚拟站（横向虚线表示）停车，即列车29在区间7停车；列车30返回车站8停车。

图3 列车区间停车运行调整方案Fig.3 Rescheduled interval parking

5 结束语

列车运行过程中不可避免会受到来自铁路系统内部和外部的干扰，而导致区间丧失通过能力，此时需要让区间运行列车在故障区域前停车。但是故障发生的时间和地点具有随机性，因此区间运行列车很有可能因为车站能力限制而不能在前方站停车。当前方车站能力不足时，本文考虑组织列车返回后方车站或区间停车，并且在模型中加入列车起停附加时分参数，更贴近列车运行实际，具有更好的现场适用性。最后模型采用武广63列车16个车站的高速铁路列车数据进行测算，当模型规模较大时，采用二阶段算法进行求解，求解质量有明显提高。

[1] CACCHIANI V，HUISMAN D，KIDD M，et al. An overview of recovery models and algorithms for real-time railway rescheduling [J]. Transportation Research Part B Methodological，2014，63（2）：15-37.

[2] D’ARIANO A，PRANZO M，HANSEN I A. Conflict resolution and train speed coordination solving real-time timetable perturbations [J]. IEEE Transactions on Intelligent Transportation Systems，2007，8（2）：208-222.

[3] CORMAN F，D’ARIANO A，PACCIARELLI D，et al.Bi-objective conflict detection and resolution in railway traffic management [J]. Transportation Research Part C Emerging Technologies，2012，20（1）：79-94.

[4] CORMAN F，D’ARIANO A，PACCIARELLI D，et al.Centralized versus distributed systems to reschedule trains in two dispatching areas [J]. Public Transport，2010，2（3）：219-247.

[5] D’ARIANO A，PACCIARELLI D，PRANZO M. A tabu search algorithm for rerouting trains during rail operations [J]. Transportation Research Part B Methodological，2010，44（1）：175-192.

[6] CORMAN F，D’ARIANO A，HANSEN I A，et al. Optimal multi-class rescheduling of railway traffic [J]. Journal of Rail Transport Planning & Management，2011，1（1）：14-24.

[7] LOUWERSE I，HUISMAN D. Adjusting a railway timetable in case of partial or complete blockades [J].European Journal of Operational Research，2014，235（3）：583-593.

[8] VEELENTURF L P，KIDD M P，CACCHIANI V，et al.A railway timetable rescheduling approach for handling large scale disruptions[J]. Transportation Science，2016，50（3）：841-862.

[9] ZHAN S，KROON L G，VEELENTURF L P，et al.Real-time high-speed train rescheduling in case of a complete blockage[J]. Transportation Research Part B Methodological，2015，78：182-201.

[10] 占曙光，赵军，彭其渊，等. 高速铁路区间能力失效条件下列车运行实时调整研究[J]. 铁道学报，2015，37（11）：1-9.

[11] 占曙光. 区间通过能力临时失效下高速铁路列车运行实时调整模型与算法研究[D]. 成都：西南交通大学，2016.

[12] 孟令云，杨肇夏，李海鹰. 单线铁路区间能力失效条件下列车运行调整模型[J]. 系统工程理论与实践，2012，32（4）：885-894.

[13] MENG L，ZHOU X. Robust single-track train dispatching model under a dynamic and stochastic environment：a scenario-based rolling horizon solution approach [J].Transportation Research Part B Methodological，2011，45（7）：1080-1102.

[14] YANG L，ZHOU X，GAO Z. Credibility-based rescheduling model in a double-track railway network：a fuzzy reliable optimization approach [J]. Omega，2014，48（10）：75-93.

[15] 彭其渊，杨明伦，聂勋煌. 单线区段实用货物列车运行图的优化模型及算法[J]. 铁道学报，1995（03）：15-20.