高速旅客列车运行调整问题的图论模型与启发式算法

刘伟斌　孙磊　王林

摘 要：如果列车发生晚点就需要启动列车运行调整，对列车的区间运行时分和到发时间进行合理的改变和调整，从而使列车的正点率得以提升，这就是所谓的列车运行调整。本文与我国的铁路运行现状和发展趋势相结合，将调整列车运行的图论模型提了出来，并且选择C语言的方式对启发式算法进行编制，对算例进行求解，最终分析并且比较了算例。

关键词：高速旅客列车；运行调整；启发式算法

中图分类号： U29 文献标识码： A 文章编号： 1673-1069（2016）12-149-2

0 引言

调整列车运行的最为主要的目的就是确保列车能够最大限度地依据计划时间表进行运行，作为一个非常复杂的问题，调整列车运行的工作需要对很多因素进行综合考虑，其从本质上来说是一个超大规模的组合优化问题。因为列车运行调整问题具有较广的涉及范围和较多的涉及因素，所以必须要深入和细致地研究其中存在的各种问题。与此同时，在运营模式和运行调整等各方面我国的铁路列车都存在着一定的特殊性，因此不可以对国外的研究成果进行全盘利用，需要与我国的国情相结合，制定与我国铁路情况相适应的列车运行调整技术。

1 高速旅客列车运行调整问题的图论模型

在2002年Caprara提出了关于调整列车运行问题的相关算法和图论模型，同时其有效地完善了传统列车的运行图。Caprara的基本思路为：将一个非循环有向多边图建立起来，对其中的虚拟的终端节点和虚拟的源节点进行设置，从虚拟的源节点中驶出每列列车，最终达到虚拟终端节点，也就是采用到达和出发两条线对列车运行图中车站一条线进行表达，通过时间轴的方式给出到达出发线。因为用分钟为单位表示一整天，也就是1到1440，采用1440个点的方式对到达和出发线进行划分，这样每个线上特定的点就能够将车站内列车的通行、停止和到达情况准确地反映出来。可以通过一条有向弧表示每列列车的运行情况，每条弧主要包括终止弧集合、区间弧集合、车站弧集合和起始弧集合。在有向图中包含了相关的每辆列车的可行性约束，这样通过可有向图就能够将每列列车的在具体的运行区间的晚点情况和到发晚点情况清楚地观察到，从而更好地开展高速旅客列车的运行调整工作。

2 高速旅客列车运行调整问题的算法研究

2.1 高速旅客列车运行调整问题的启发式算法

不同的晚点列车在列车运行调整中在调整优选级方面存在着一定的差异，在恢复正点运行的要求方面不同等级的列车也存在着一定的差异。比如，普通列车和特快列车具有相同时分的晚点情况，这时候就需要对特快列车进行优先调整，确保其能够以最快的速度实现恢复正点运行。调整列车运行的问题属于一个非常难的问题，而且其与列车运行图的编制问题并不相同，往往要很短的时间进行求解。所以必须要采用具有较高精度和较快捷速度的近似算法对列车的运行调整问题进行计算。本文修改了传统的贪婪算法，将一种新的求解算法提了出来。在这种算法中需要输入的已知参数主要包括列车等级信息、列车的到发间隔时分、列车的晚点信息以及列车的计划时刻表等，在各站各列车的最优到发时间是列车运行调整的目标输出，高速旅客列车运行调整启发式算法主要包括以下的求解流程：①初始化处理。要将已知的各项参数输入进去。②将发生晚点的车站和首次晚点的列车确定下来，并且要将首次晚点的列车影响的其他相关列车确定下来。③在确定满足首次晚点列车和首次晚点的列车影响的其他相关列车的越行车对，同时对交换发车顺序进行合理的调整，并且将发车时间确定下来。④以计划运行时分和最小运行时分等为根据将需要“赶点”运行的列车确定下来。如果不符合终止条件，就要返回到第二步中，如若不然，就需要将运算停止，选择现在的最优解作为最终解，并且将运算结果输出，最终形成科学的列车运行调整方案。

2.2 高速旅客列车运行调整的优化对策分析

在调整列车运行的时候必须要严格遵循以下的原则：①在每个站点都要调整在本站经过的列车的到发时间。晚点列车只会对后续各站和本站的列车产生影响，而利用区间调整冗余的方式则能够减少这种影响。②先旅客列车后货物列车是调整列车运行的优先级。要先对重点列车、快速列车、正点列车和离终点站远的列车进行先行调整，然后再对一般列车、低速列车、晚点列车和离终点站近的列车进行调整。③列车具有固定不变的优先级，而且运行的情况一般不会出现在同等级别的列车之间，而低级别的列车会被高级别的列车越行。④对列车在每站的到发时间进行调整，利用慢行和赶点的方式在区间运行时控制晚点时间。

3 高速旅客列车运行调整问题的算例求解

3.1 列车的晚点信息

以晚点情况为根据共计加3个参数设置了出来：i指的是首次晚点的时间，j指的是该区间初始晚点的列车，wd指的是列车晚点的时间。在区间运行的时候列车多出计划运行时间的实际运行时间用晚点时间wd来表示。通过计算和求解列车晚点时间wd、该区间初始晚点的列车j、首次晚点发生的区间i，这样就要能够将目标函数值和相应的晚点列车时刻表计算出来。

3.2 列车的晚点分析

在这里通过几组晚点数据分析讨论上述的数学模型，同时总结相应的晚点数据所导致的影响。在wd分别为25分钟、15分钟和5分钟，j=3，i=2的情况下，就能够将目标函数值和相应的晚点时刻表计算出来。目标函数值在晚点时间不断增大的同时也会变得越来越大，目标函数值在wd在大于15分钟的情况下会呈现出一种线性增长的趋势；wd在小于15分钟的情况下具有越来越多的受影响的列车，然而却不会影响到后续的高等级列车，而且应不应该影响到后续的高等级列车，这时候目标函数就会具有越来越快的增长速度，其增长趋势呈抛物线状。

通过上述的已知条件进行分析，我们可以发现当中等级列车具有较少的晚点时间时，不会影响到后续的高等级列车和其他的中等级列车，如果中等级列车具有较多的晚点时间时，因为越行的情况不能出现在同等级列车中，因此会影响到后续的中等级列车。如果同等级列车具有过大的晚点时间，就会影响到后续的高等级列车，然而在不断推进站点的同时，高等级列车差不多能够恢复到正点。如果高等级列车出现晚点，因为其具有较快的速度，因此基本上不会影响到后续的列车或者只会产生较小的影响。如果中等级列车的后行高等级列车出现晚点的情况，那么在这种情况下中速列车也不会被高等级列车提前越行。从整体上来看，对上述高速旅客列车调整的结果进行分析，我们认为这种算法能够对

区间和站间的冗余时间进行有效利用，从而更好地调整列车，并且进一步地降低后续列车和晚点列车本身的晚点损失。

4 结语

本文通过一种比较直观的方式将列车运行问题的图论模型提了出来，随后与我国铁路运行现状相结合，建立了初步的整数规划模型。通过对给定算例的启发式算法进行编制，就可以对区间和站间的冗余时间进行有效利用，从而科学合理地调整列车，确保列车能够尽可能的恢复正点。在本文中主要对双线自动闭塞的单方向高速旅客列车进行了考虑，所以下一步工作的主要目标就是解决单线列车的运行调整问题。

参 考 文 献

[1] 蔡涛.高速铁路列车运行调整优化模型研究[J].铁道运输与经济，2016（03）.

[2] 刘莉，王长林.城市轨道交通列车运行调整的粒子群算法研究[J].铁路计算机应用，2013（06）.

[3] 陈雍君，周磊山.基于序优化方法的列车运行调整算法研究[J].铁道学报，2010（03）.

[4] 张翠平，曹成铉，滕宇蛟，刘苏庆，陈磊.列车运行调整问题的图论模型与启发式算法[J].科学技术与工程，2010（10）：2560-2564+2573.

[5] 石雨.客运专线列车运行调整的策略、模型与算法[D].北京交通大学，2010.

[6] 秦胜.基于周期事件系统的高速铁路列车运行图编制模型及算法研究[D].北京交通大学，2013.