高速铁路列车运行调整策略优化

戴杨铖，宋瑞，毕明凯，陈旭超

(北京交通大学 城市交通复杂系统理论与技术教育部重点实验室，北京 100044)

高速铁路列车运行调整策略优化

戴杨铖，宋瑞，毕明凯，陈旭超

(北京交通大学 城市交通复杂系统理论与技术教育部重点实验室，北京 100044)

在分析高速铁路列车运行调整问题及策略优化思想的基础上，以列车加权总晚点时间最小为目标，考虑列车运行时分、车站间隔时间等约束，建立了高速铁路列车运行调整策略优化模型 .针对不同适用情况，提出三种基础调整策略，构建情景-策略匹配表，并基于极大加代数的时刻表递推思路，运用 C#软件进行求解 .最后以京广高铁区段为例，随机假设晚点情景，分析调整结果 .优化后策略匹配度为100%， 晚点时间平均减少24.07 min，晚点幅度降低 4.2%～53.5%，求解效率显著提升，验证了模型和算法的有效性.

高速铁路；列车运行调整；策略优化；极大加代数

0 引言

高速铁路是指列车速度超过250 km/h的新建线路和超过200 km/h的既有线改造线路.一般情况下，列车是按照基本运行图来运行的.列车运行调整[1]是指当列车的运行状态偏离预定值时，通过重新规划列车运行时刻表，尽可能恢复有序运行状态的过程.

在高铁列车运行调整优化方面，许多专家学者进行了深入研究.石雨[2]将问题进行转化，针对局部调整和大面积调整分别提出了模型及算法.吴丽然[3]建立了以总晚点车数最少为优化目标的数学规划模型.李晓娟[4]及陈雍君[5]都使用了序优化方法进行列车运行调整，并取得了足够好的解.J.T.Krasemann[6-7]则使用了贪婪算法进行实时的列车调整，有效减少了后续列车的连带晚点现象.

现有研究多为静态分析，且侧重于建模和算法，使得求解结果过于理论化，实用性下降.策略优化思想则兼顾优化理论和实际经验，其基础调整策略均是基于实际经验给出，在此之上，进一步通过优化组合理论，确定多种随机晚点情况下最优调整策略，从而达到列车运行调整的目标.本文针对列车运行调整中的晚点情况，在已有研究基础上构建高铁列车运行调整策略优化模型，提出三种基础调整策略，并构建情景-策略匹配表进行研究分析.

1 问题描述

策略是指对将来任意可能的状态采取行动的规则[8]，如在生产调度工作中，策略是指推迟加工设备的开、完工时间或调整加工设备的加工顺序等[9].列车运行调整问题的原理亦是如此.如发生晚点，调度员采用的调整方法是后续列车依次开行，还是快速列车对中速列车进行越行，就类似于调整计划工作时间、变更工序的策略.传统优化方法以某些指标为优化目标，采用固定的算法(或称单一策略)进行仿真求解.但实际运用中，晚点情况纷繁不一，当晚点复杂时，采用简单的算法求解便得不到最优结果；当晚点轻微时，采用复杂的算法势必影响求解效率.而策略优化方法是以策略而非传统目标值为对象的优化方法，能够根据实际情况匹配最为合理的策略进行求解，更好地适应环境的多变性和随机性，满足高铁调度准确性、高效性的要求.策略优化方法的求解思路如图1.

图1 策略优化方法

文献[10-11]把列车运行调整原则和措施的结合作为列车运行调整策略，这也是现有研究的常用定义方式.本文结合可选越行原则及调整列车到发时间、顺序的措施，根据晚点列车的实际情况，增添不同的越行判断，进行相应的策略分析.

2 高速铁路列车运行调整策略优化模型

2.1模型假设

高速铁路列车运行调整策略优化模型的基本假如下：

(1)调整区段为快、中速列车混行，所有列车均不发生早点情况;

(2)后续列车需要越行时，避让和越行只发生在车站内，且调整区段首尾站不进行越行;

(3)列车在区间内运行速度不变(安排额外的停站时不考虑起停车附加时分).

2.2定义相关参数及决策变量

设Q为调整区段上车站的集合，共q个车站；E为相邻车站的区间集合，共q-1个区间；P为开行的列车集合，共p辆列车；li表示列车i的等级，由列车的种类决定；Z表示运行调整的周期；分别表示车站k的不同时到发、发到、到达、发车的作业间隔时间；表示列车i在车站k的停站情况，若停站，则否则；表示列车i在车站k的停站时间最小值；表示列车i在区间e上的纯运行时分最小值；表示列车在车站k的起车附加时分；表示列车在车站k的停车附加时分；为基本图中列车i在车站k的出发时刻；为基本图中列车i在车站k的到达时刻.

定义：Θ为设定的计算符号，当a≥b时，aΘb=a-b，当alt;b时，aΘb=a-b+Z.

2.3模型构建

目标函数：

(1)

约束条件：

越行约束：

lj≥li，(i、j∈P)

(10)

其中，式(1)为目标函数，表示调整区间、时段内所有列车加权总晚点时间最小，式(2)～(5)分别为车站不同时发车、到达、到发、发到作业间隔时间约束，式(6)为列车区间运行时间约束，根据区间运行时分及图定停站情况决定，式(7)为列车停站时间约束，式(8)为不早点约束，式(9)为调整时间范围约束及整数约束，式(10)为基本越行原则下前后车等级约束.

3 列车运行调整策略匹配分析

3.1基础调整策略适用分析

策略1：

策略1为依次开行策略，即列车发生晚点后，后续列车依次顺延，利用运行图缓冲时间恢复正点.如图2所示，记tw为列车i在k+1站的晚点时间，后车j根据车站间隔时间调整至当前可行的最早到达时间即可，tt为调整时间.该策略施行难度小，求解速度最快，是调度工作中最常用的调整策略.

图2 策略1调整情况

策略2：

当中速列车发生晚点时，可能会与后续快速列车形成如图3所示的冲突，记t0为列车i与列车j在k站的发车时间差，此时若仍采取策略1进行调整，将造成严重的连带晚点现象.针对这种情况，策略2新增了快速列车可越行中速列车的越行判断(其余情况同策略1)，此时必须满足ljgt;li.

图3 策略2针对冲突基本情况

图4 k站越行情况

图5 k+1站越行情况

(11)

(12)

策略3：

图6 策略3针对基本情况

图7 策略3新增越行情况

3.2构建列车晚点情况与基础策略匹配关系

因策略3考虑的情况较为全面，因此，无论晚点情景如何，理论上均可采用策略3得到最优调整结果.但随着求解规模扩大至路局，甚至路网，单独采用策略3也会极大地影响调度效率.而传统的人工调度多采用策略1进行调整，少数的越行操作仅凭借经验进行判断，不具备足够的前瞻性和规划性.因此，必须构建合理的情景-策略匹配表，确定综合调整方案，达到最优的求解效果.

表1 情景-策略匹配表

本文将晚点情景分为两大类：局部晚点及大面积晚点.局部晚点指的是单一列车自发晚点的情景，此时，应依据晚点列车和周围(如临近1-2位)列车的种类、图定运行情况及晚点程度(如轻微：5 min及以下，严重：5 min以上)来预测是否需要越行，并针对性地匹配调整策略.大面积晚点指的是由于天气、自然灾害等因素，导致所有列车在某区间内集体限速的情况.此时由于各列车之间不存在速差，因此均采用依次开行策略.结合3.1中各策略适用情况，得到情景-策略匹配结果，如表1.其中，“轻微”、“严重”、“周围”等要素均可根据运用实例进行调整.

4 算法设计

4.1算法的数据表示及求解思路

采用文献[12]给出的基于极大加代数的时刻表递推思路，运用矩阵表示相关数据，定义自发晚点列车为列车n，发生晚点的车站为站m，晚点时间为delta，使用C#软件进行求解.具体步骤为：

Step1：列车n在站m的到发时间；

Step2：后续列车在站m的到发时间；

Step3：后续车站的列车的到发时间；

Step4：终到站q的列车的到达时间.

对于大面积晚点情况，则根据限速值对应转换区间最小运行时分数据，同理求解即可.

4.2算法流程

如图8，首先输入已知数据、晚点情况及情景-策略匹配表，然后根据m的值进行下一步计算并循环，直至m=q，得到完整的调整时刻表及F，结束算法.

图8 算法流程图

5 实例分析

以京广高铁许昌东至安阳东区段上行方向的列车运行图为例，该区段内共有6个车站，调整时段为某日的18∶00-21∶20，时段内有15列车，按上行顺序及列车进入区段的先后顺序将其采用自然数编号.其中，8车(G506)、12车(D2202)为中速列车，列车等级定义为1，一般快速列车按速度比定义为1.25，3车(G504)、9车(G70)为重点车，根据调研结果将其等级定为2.5.调整区段的基本运行图如图9所示，区间运行时分、车站间隔时间、列车停站情况等已知数据可参见京广高铁列车运行图资料.

随机给出20个局部晚点(列车n在站m自发晚点delta)情况和2个大面积晚点(h区间内列车集体限速为speed)情况.将晚点情况代入表1进行匹配，得到对应策略，然后分别采用三种策略进行调整，得出不同策略下的加权总晚点时间F1～F3(单位为min)，调整结果如表2所示.

图9 调整区段基本运行图

表2 假设晚点调整结果

(1)策略匹配度分析

定义“最优策略F优”为F值最小且最简便的策略，“策略匹配度”为某种调整方法下最优策略所占的比例.对比表2中F1～F3的值，可得单独采用某种策略进行调整的方法(传统方法)和综合策略优化方法的策略匹配度，如表3.传统方法无法兼顾调整结果和求解效率，而策略优化方法可以很好地解决这个问题，策略匹配度达100%.

表 3 单一策略调整与综合策略优化方法的匹配度对比

此外，局部晚点时，匹配策略1的情况为65%，策略2为25%，策略3为10%；大面积晚点时，均匹配策略1.可见，基本运行图已经充分考虑了列车到发顺序、运行缓冲时间等，对于大部分晚点情况，依次开行策略即为最优策略，符合策略1～策略3针对情况依次复杂化的设计思路.

(2)晚点时间降低分析

在假设晚点情况下，将采用综合策略(匹配策略2和策略3)所得的F优与采用单独策略1(传统调度策略)所得F1进行对比，得到晚点时间减少量F减.此时，加权晚点时间平均减少24.07min，晚点幅度降低4.2%～53.5%，具体如表4.实际工作中，由于自发晚点列车周围运行线的密集程度和办理越行的车站位置等因素，均对策略调整后的晚点优化效果产生直接影响，因此F减的分布呈无固定规律性.

表4 优化后晚点降低情况

(3)调整效率分析

针对本文使用的6车站、15列车、200 min调整时段的实例，使用计算机进行各种策略下的求解，并模拟人工调度过程，耗时如表5所示.综合策略下，相比单独采用策略2或3，求解效率可分别提升20%和31.4%，且所有策略算法均具备良好的计算机适应性，求解效率较人工调度大幅提升.未来随着求解规模的扩大，策略优化对于高铁调度工作效率的意义将愈发显著.

表 5 各策略下求解效率对比

6 结论

将策略优化思想运用于高铁列车运行调整，结合优化理论和实际经验，解决了传统优化方法无法兼顾调整结果与求解效率的问题.在区间运行时分及车站间隔时间等基础约束上，以列车加权总晚点时间最小为目标函数，构建高铁列车运行调整策略优化模型.针对不同的适用情况，设计策略，并构建情景-策略匹配表.基于极大加代数的时刻表递推思路，编写算法，运用C#软件求解.最后，以京广高铁区段为例，随机假设多种晚点情况，计算得到优化调整结果，分析得：优化后策略匹配度为100%，晚点时间平均减少24.07 min，晚点幅度降低4.2%～53.5%，验证了模型及策略匹配的可行性.同时，求解效率显著提高，为进一步研究列车运行调整中的计算机智能决策问题奠定基础.

[1]张翠平. 高速旅客列车运行调整问题的图论模型与启发式算法[D]. 北京:北京交通大学,2010.

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

[3]吴丽然.高速铁路列车运行调整问题研究[D]. 成都:西南交通大学,2011.

[4] 李晓娟,韩宝明,李得伟,等.基于转换极大代数和序优化的高速列车运行调整方法[J].中国铁道科学,2013(6):124-130.

[5] 陈雍君,周磊山.基于序优化方法的列车运行调整算法研究[J].铁道学报,2010(3):1-8.

[6]KRASEMANN J T. Design of an effective algorithm for fast response to the re-scheduling of railway traffic during disturbances [J]. Transportation Research Part C,2012.

[7]KRASEMANN J T. Greedy algorithm for railway traffic re-scheduling during disturbances: a Swedish case [J]. IET Intelligent Transport Systems,2010,4(4):1-12.

[8]刑锦江.虚拟现实环境中的策略生成[D].北京:北京航空航天大学,2008.

[9]WHITE D J. Markov Decision Processes [M]. Chi Chester: Wiley Press, 1993.

[10]贺振欢,李海鹰,苗建瑞,等.铁路客运专线列车运行调整策略仿真分析[J].系统仿真学报,2010(1):262-265.

[11]聂磊,张星臣,赵鹏,等.高速铁路列车运行调整策略的研究[J].铁道学报,2001(4):1-6.

[12]李传宾.基于矩阵表示和极大代数法的高铁周期列车运行图编制方法研究[D]. 北京:北京交通大学,2012.

下期待发表文章摘要预报

激波矢量控制喷管性能分析与结构优化设计

李丽，张琳琳，吕锡昌，李东明

(大连交通大学 机械工程学院,辽宁 大连 116028)

摘要：采用试验设计方法进行激波矢量控制喷管气动性能数值分析与优化设计，综合研究了二次流几何参数对二元收扩喷管气动性能的影响.基于超拉丁立方设计方法得到喷管二次流参数近似拟合模型和最优解区域，并利用多岛遗传算法寻找最优解.研究的设计参数包括二次流口距离、二次流口宽度及二次流长度.数值仿真结果表明，二次流口距离对矢量偏转角的影响最大，二次流口宽度次之，二次流长度对矢量偏转角的影响最小.

OptimizationMethodforRe-SchedulingStrategyofHigh-SpeedRailway

DAI Yangcheng，SONG Rui，BI Mingkai，CHEN Xuchao

(Moe Key Laboratory for Urban Transportation Complex Systems Theory and Technology, Beijing Jiaotong University, Beijing 100044, China)

In order to analyze operation problem of high-speed train and strategy optimization, a strategy optimization model is constructed to minimize the total weighting delay time with the constraints of operation time and station interval time. Based on multiple types of delay scenarios, three basic adaptive adjustment strategies are proposed, and situation-strategy matching forms are built using the idea of max-plus algebra to derive the timetable and computed the results with a software based on C sharp. Besides, the case of a high speed section of Jingguang railway administration which is from Xuchang East Station to Anyang East Station is used and the optimized results of delay adjustment under the randomly simulated scenarios are obtained. The results show that after the optimization, the strategy matching degree reachs 100%, the delay time is reduced by 24.07 min equally, and the range of delay is decreased by 4.2-53.5%. The computational efficiency is enhanced significantly, and the effectiveness of the strategy matching model is validated.

high-speed railway；train regulation；strategy optimization；max-plus algebra

1673- 9590(2017)06- 0012- 07

2017- 03- 02

中国铁路总公司科技开发计划资助项目(2016F023)

戴杨铖(1992-)，男，硕士研究生；

宋瑞(1971-)，女，教授，博士，主要从事交通运输管理的研究

E-mail15120941@bjtu.edu.cn.

A