高速铁路列车运行图一体化自动编制方法研究

安 迪，武晋飞，张宇墨

(1.中国铁道科学研究院 研究生部，北京 100081；2.中国铁道科学研究院集团有限公司 运输及经济研究所，北京 100081；3.中国铁道科学研究院集团有限公司 电子计算技术研究所，北京 100081；4.中国铁路经济规划研究院有限公司 科技管理部，北京 100038)

高速铁路(以下简称“高铁”)列车运行图编制一直以来都是高铁运输组织的核心问题之一。目前,全路采用的列车运行图编制系统仍以人工编制为主,究其原因,高铁列车运行图除包含列车时刻表外,还包含车底交路方案、运行图结构方案、车站股道运用方案等,是运输需求与运输供给的集中体现。由于高铁列车运行图编制影响因素都具有一定的复杂性,且相互耦合,一体化自动编制的难度则更大。

针对运行图编制的复杂问题,国内外学者对列车运行图自动编制问题进行过很多研究。部分学者采用简化或分步式方法求解。马建军等[1]针对不同速度列车,建立高中速列车运行图数学模型,设计高中速列车分层始发区域滚动铺画算法;许红等[2]研究不同种类列车的布点模型,设计基于改进型遗传算法的优化策略和算法;Castillo等[3]基于单双线混合铁路,提出基于二分法的优化算法,将运行图编制问题进行简化从而求解;张小炳等[4]将列车运行图结构优化问题转化为旅行商问题,以巡回路径总费用最小化为目标建立0-1整数规划模型,利用遗传算法求解;张琴等[5]提出区间—咽喉区—到发线三段式列车运行图编制框架,以列车运行总费用最小为目标建立0-1整数规划模型;Feng等[6]针对高铁提出一种在日常需求波动下的运行线合并与新增方法,并采用组合启发式局部搜索算法求解。部分学者针对运行图编制的多个阶段,研究一体化(或协同)编制的技术和方法。Kaspi等[7]以旅客全程旅行时间和运营成本最小化为目标,建立运行图优化模型,并采用交叉熵元启发式方法求解;张宁[8]按照协同学相变理论,提出协同优化思路和方法;于汝滨等[9]以列车停站方案数、越行次数、区间群数、运行图四边形平均面积、运行线距离作为运行图结构指标,批量铺画列车运行图;Barrena等[10]基于旅客动态需求,提出单条线路上的非周期性列车时刻表一体化编制方法;Martin-iradi等[11]基于旅客出行时间提出期性列车运行图编制算法,并结合丹麦铁路进行实例验证;张新等[12]考虑运行图参数、车站停站次数等因素,构建列车停站方案与运行图协同编制模型,并以京沪高铁为例求解。

国内外学者对铁路运行图自动编制问题进行了大量探索,特别是对分阶段思路下的高铁列车运行图编制技术方面的研究有一定基础,但由于运行图编制涉及因素较多,针对运行图一体化自动编制仍处于探索阶段,运行图编制自动化程度仍不高。为此,本文面向高铁运行图编制,在不改变现有编图模式的前提下,提出基于车底交路方案、列车结构方案、人工与自动调整在内的一体化自动编制流程,并考虑微观站场进路占用策略,提出运行图优化编制模型,以京沪高铁作为案例进行验证,为提升我国高铁列车运行图编制效率、提高列车运行图编制质量提供技术支撑。

1 人工运行图编制流程及原则概述

目前,我国铁路列车运行图的编制均由人工操作计算机铺画完成,全年一共编制4次季度运行图、1次春运运行图、1次暑运运行图,按运行图编制需求可分为新图铺画和现图调整2类,新图铺画是在开通新线路后第一次进行运行图铺画,现图调整是在上一季度运行图基础上进行增加、删除和修改,我国高铁运行图编制大部分情况下为现图调整。

高铁运行图编制流程可分为基础资料收集、开行方案确定、高等级与长交路列车运行线铺画、较低等级与短交路列车运行线铺画、运行图输出等步骤,各步骤具体含义如下:

1)基础资料收集。由工务、电务、供电等部门在新图铺画时提供新开通线路的基础数据,由机务部门提供运行图标尺,由车辆部门提供车型、配置、编组、数量、检修地点等数据,由客运部门提供车底交路方案及停站需求,以上资料都提供给运输部门作为编图依据。

2)开行方案确定。中国国家铁路集团有限公司(以下简称“国铁集团”)组织各路局、各专业部门协商,下达本次调图的轮廓性计划,并通过沟通协调,确定具体列车开行方案,在现图调整时主要为上一季度运行图的车底交路方案和修改计划。

3)高等级与长交路列车运行线铺画。根据国铁集团确定的开行方案或车底交路方案修改计划,铺画繁忙干线、跨局的长交路高速度等级列车运行线。

4)较低等级与短交路列车运行线铺画。根据国铁集团、本局客运部门确定的开行方案或车底交路方案修改计划,铺画与繁忙干线相衔接的其他线路、局管内、短交路以及较低速度等级列车运行线。

5)运行图输出。运行图编制完成后,客运、车辆、机务人员都需要对涉及自身的运行图要素进行验证,然后根据运行图输出自己专业的相关信息。

高铁运行图编制原则有以下几项:

1)适应客流。高铁运行图编制要适应高铁沿线各站客流特点,满足旅客出行的需要,尽可能均衡停站,并按时段、频率安排列车运行线。

2)提高能力。高铁运行图编制要尽可能利用线路和车站的通过能力,减少不必要的越行与避让,同时还要有一定冗余时间。

3)顺序铺画。从列车速度等级看,列车按速度等级和交路长度进行划分,旅行速度越高、交路越长、所跨路局越多的列车,其铺画的越优级越高,铺画好高等级列车运行线后再铺画较低等级列车运行线。从能力运用看,优先编制能力最为紧张的线路和区间,再铺画其他线路和区间。

4)合理运用。充分提高动车组车底运用效率,降低动车组运用数量,同时兼顾列车旅行速度、动车组检修、司机换班等因素。

5)影响最小。当列车运行线铺画遇到冲突时,采用影响最小的改动方式协调运行线间的冲突,对于跨局列车来说,尽量不改动分界站列车到发时刻。

由人工运行图编制流程及原则可见,高铁运行图编制涉及多专业、多部门,在编制过程中往往需要多方协调才能完成,且某条运行线一经修改,可能“牵一发而动全身”。因此,为实现列车运行图的计算机自动编制,需要借鉴人工编制经验,在目前编图机制的基础上尽可能实现自动化。

2 运行图一体化自动编制流程

2.1 总体流程

高铁列车运行图一体化自动编制充分考虑高速铁路运行图人工编制机制和经验,考虑现有运行图编制流程和原则,提出迭代加入带有车底交路的运行线自动编制方法,并结合调整策略,以全面适应现有列车运行图调整、加密或重新编制等需求。高铁列车运行图一体化自动编制总体流程见图1。

图1 高铁列车运行图一体化自动编制总体流程

1)数据准备

与人工运行图编制类似,一体化自动编制流程需要数据准备作为支撑。数据主要包含高速铁路基础设施、运行图要素、运输组织方案、模型参数4类。其中,高铁基础设施数据主要包含线路和站场数据;运行图要素包含各类列车追踪间隔时间及各类车站间隔时间;运输组织方案数据主要包含上一季度列车时刻表、车底交路方案、本次调图的相关列车结构方案;模型参数指与优化编制模型求解、自动调整等相关的参数。

2)数据处理

数据处理阶段实现列车运行图的生成,包括迭代加入车底交路、迭代加入列车结构方案、自动调整等等。其中,一体化指自动编制生成的列车运行图完整包含列车时刻表、车底交路方案、车站股道运用方案,无需分阶段生成;人工与自动调整指可人工或自动中断自动编制过程,利用专家知识和经验,调整相关内容后,继续进行。

3)数据输出

数据输出结果为完整的列车运行图,主要包含列车时刻表、车底交路方案、车站股道运用方案3类。

2.2 车底交路方案与列车结构方案

车底交路方案是高铁列车运行图一体化自动编制过程的重要基础资料之一。利用车底交路方案自动编制运行图的基本思路是,依据上一季度与新一季度运行图车底交路方案,按优先级顺序,依次将车底交路改动方案进行铺画。为控制求解规模,保持已加入列车的停站方案、路径方案和开行顺序,一体化生成待加入列车的时刻、停站方案和路径方案。

列车结构方案是列车结构的集合,1个列车结构是1组列车的共同结构信息,主要内容包括:

1)车底信息。包括速度级、编组方案等。

2)停站方案信息。指在每个车站的停站方案,包括是否必停、禁停或停站比例、是否整点发车、出发和到达时间范围、最小出发和到达间隔时间等。

3)分区段方案。对开行路径上的某个区段,设置越行、停站数量、慢行时分等要求。

2.3 人工与自动调整

人工与自动调整策略主要用于解决列车运行图结构优化问题,包括以下典型情形:①在一个时空范围内,组织多列车的停站方案规律化,包括交错停站、成组交错停站、集中停站或通过等模式,优化利用通过能力;②对特定OD,使时段服务频率与时段客流量分布相匹配。人工调整的因素主要为迭代车底交路或列车结构加入运行图时存在随机性、迭代间隔时间过长等。

当前的数学规划方法均难以描述多列车的停站方案组合优化以及开行时段分布优化等要求,即在列车开行顺序以及时段均不确定的情况下,难以构建线性约束或优化目标。对于①类问题,需要在保持列车开行顺序的情况下,人工或自动调整列车停站方案。对于②类问题,需要人工调整列车开行顺序。

3 微观站场进路占用策略

3.1 备选路径

列车在每个车站或线路所均有一个备选路径集合,每条备选路径由列车作业的进路依次连接构成。基于正线通过、侧线停站的一般规则,备选路径和停站方案有对应关系。

考虑进路占用时间不同,将进路分为股道区段和咽喉区段,统称为进路区段。每个进路区段的占用开始和结束时刻基本均以列车到达或出发时刻为基准,提前或推迟固定的时长表示,进路占用时间示意见图2。

图2 进路占用时间示意

图2中,对于发车和通过作业,由于发车进路释放与第一离去出清时刻存在较小的冗余时间,对运行图编制的影响很小,因而每个进路区段的占用时间与列车到达或出发时刻关联最为紧密。每条备选路径由股道方案、停站方案、进路区段集合与进路区段占用时间所决定。

3.2 间隔时间

间隔时间作为运行图编制的重要参数,是运行线铺画的主要限制条件之一。高速铁路列车运行图一体化自动编制流程中主要考虑以下两种间隔时间情形。

1)一般间隔时间

根据Q/CR 471—2015《高速铁路列车间隔时间查定办法》[13],除具体需要确定的间隔时间以外,列车追踪间隔类型共含6种,车站间隔时间共含4种。由于运行图编制属于中观列车运行体现,流程中主要考虑列车出发追踪间隔、列车到达追踪间隔、列车通过追踪间隔、同方向列车到通间隔、同方向列车通发间隔、敌对进路相对方向不同时到发间隔以及不同时发到间隔等8种。理论上,只要进路占用时间参数取值准确,运行图编制无需额外考虑间隔时间要求。

2)动车所出入库特殊情形

对于动车所出入库线(或可双向开行的任意单线区间),需额外考虑先发后到与先到后发间隔时间要求,动车所出入库线先发后到与先到后发间隔时间示意见图3。

图3 动车所出入库线先发后到与先到后发间隔时间示意

情形A时,只有前行出发列车出清区间且邻站进路释放后,后行到达列车才可办理邻站发车作业进入动车所出入库线。情形B与一般敌对进路相对方向不同时到发间隔基本相同。由于动车所在列车运行图上也作为车站节点之一,当铺画动车所出入库运行线时,需额外考虑先发后到间隔时间。

4 运行图优化编制模型与求解

4.1 问题描述

为实现运行线自动编制,运行图优化编制模型的问题描述如下:在已有基本图或空白图基础上,根据需求建立车底交路方案,将每个车底交路依次迭代加入列车运行图,为待加入列车一体化生成时刻、停站方案和路径方案,同时待加入列车运行线、交路满足微观站场占用约束。迭代加入车底交路失败时,采用人工或自动调整方法,直至所有车底交路铺完为止。

4.2 参数和变量

运行图优化编制模型参数与变量定义见表1。

表1 运行图优化编制模型参数与变量定义

4.3 优化目标

1)最大化车站股道运用方案的性能

使车站股道运用方案的性能值之和最大,对于大型客运站,尽可能选用平行进路接发车,即

(1)

2)最小化期望停站方案的偏差

使车站停站方案尽可能按照预先设置的列车结构进行停站,即

(2)

3)最小化车底周转时间

使动车组车底周转时间尽可能小,最大化利用动车组车底,即

(3)

4.4 基本约束

1)列车停站方案约束

对当前列车,保持停站方案;对待加入的列车,除指定必停站和禁停站外,其他车站的停站方案通过模型优化生成,即

(4)

2)列车路径方案约束

对已加入的列车,保持路径方案;对待加入的列车,路径方案通过模型优化生成,即

(5)

3)列车区间开行顺序约束

对已加入的任意两列车,保持区间开行顺序;待加入列车与已加入列车的区间开行顺序通过模型优化生成,即

(6)

4)列车停站时间约束

列车停站时间与停站方案有关,即

(7)

5)列车区间运行时间约束

列车区间运行时间由纯运行时间、慢行时分、起车和停车附加时间构成,与列车在两端车站的停站方案有关,即

(8)

6)列车接续时间约束

列车接续时间与接续方式有关,即

(9)

7)列车跨线运行时间约束

对列车的始发站和终到站,若不在优化编制模型的路网区域内,应考虑列车在区域外的运行时间,满足始发站和终到站的开行时间范围要求,即

8)车站路径选择约束

路径方案与停站方案存在对应关系,即

9)车站进路占用约束

10)禁止同时办理列车作业约束

对特定条件的车站,如进站信号机外方为6‰下坡道,且股道无隔开设备时,尽管两条进路在空间上不冲突,仍禁止同时办理列车作业。用符号≠表示两个进路区段位于禁止同时办理的两条进路上。不失一般性,禁止同时办理可表示为:一个进路区段的占用开始时刻与另一个进路区段的占用结束时刻存在最小间隔时间要求。用常量t常表示进路区段占用的最小间隔时间,即

11)列车结构约束

(20)

(21)

4.5 求解流程

针对固定数量的车底交路,按优先级顺序,每次将1个车底交路加入列车运行图,每个车底交路中的列车带有列车结构,一体化生成待加入列车的时刻、停站方案和路径方案。在数据准备完成后,运行图编制流程如下:

Step2遍历车底交路ci,若C=∅时,结束。

Step3对车底交路ci进行排序,若选择人工调整转Step4,否则转Step5。

Step4人工调整列车运行图或车底交路。

Step5选择车底交路ci,加入列车运行图,成功时转Step2,失败时转Step6。

Step6自动调整,若选择人工调整转Step3,否则转Step5。

运行图优化编制模型属于多目标MIP问题,同时包含整数和连续变量,而整数变量的数量直接影响模型求解速度。为控制求解规模,使模型每一步迭代过程中的约束和变量数量可控,在新加入列车时,保持已加入列车L当前的停站方案、路径方案和开行顺序不变,仅调整列车时刻。针对3个优化目标,采用加权叠加方法将原问题转化为单目标优化问题求解,根据以往研究经验,通用算法中如列生成算法、分支切割法可有效求解大规模线性规划问题,使用商业计算软件对该问题进行求解。

5 案例研究

根据以上运行图优化编制模型,完整集成一体化自动编制技术,并以京沪高速铁路某季度季度列车运行图为基础,采用运行图一体化自动编制流程编制下一季度列车运行图。

5.1 数据准备

1)线路数据。建立京沪高速铁路全线数据,包含站间距、线路属性等。

2)站场数据。建立京沪高铁23个车站及6个线路所站场拓扑图,关联各站到发线、正线关系,输入进路连接关系。因篇幅有限,对北京南站、济南西站、南京南站、上海虹桥站4个站场数据进行展示,见图4～图7。

图4 北京南站站场数据

图5 济南西站站场数据

图6 南京南站站场数据

图7 上海虹桥站站场数据

3)运行图要素数据。包含不同速度等级列车区间运行时分(含起停附加时分)、车站进路占用时分、车站进路间隔时分、区间运行间隔时分、车站停时等。

4)运输组织方案数据。输入上一季度运行图车底交路方案与列车时刻表,根据本季度运行图修改计划,建立新列车开行结构方案。本次案例研究共输入362个车底交路方案,通过分析上一季度列车运行图开行结构,本次案例研究共输入104个列车开行结构方案。

5.2 案例计算结果

通过基于车底交路方案和列车结构方案的运行图一体化自动编制流程,编制过程中适时人工中断调整,用时48h,完成京沪高铁案例运行图。

京沪高速铁路案例下行各站列车数统计见表2。

表2 京沪高速铁路案例下行各站列车数统计 列

京沪高铁案例上行各站列车数统计见表3。京沪高铁案例部分下行列车停站方案见图8。京沪高铁案例部分动车组车底交路方案见图9。

表3 京沪高铁案例上行各站列车数统计 列

图8 京沪高铁案例部分下行列车停站方案

图9 京沪高铁案例部分动车组车底交路方案

案例计算所得到运行图,铺画运行线共585列,其中下行292列,上行293列,包含京沪高速铁路各车次车底交路方案以及各车站股道运用方案。京沪高速铁路案例与真实运行图统计指标比较见表4。

表4 京沪高速铁路案例与真实运行图统计指标比较

由表4可见,在上一季度运行图基础上,案例计算所得到的京沪高速铁路列车运行图,相比下一季度真实运行图多铺画列车24列,旅行速度、技术速度、速度系数、平均停站时分等统计指标均与真实运行图相近,验证了一体化自动编制方法的有效性。由于列车结构方案参数存在一定随机性,列车结构方案越细致、具体,所计算得到的运行图越满足编图需求。

6 结论

高速铁路列车运行图一体化自动编制方法实现了列车时刻表、车站股道运用方案、车底交路方案的一体化自动编制,充分借鉴人工运行图编制经验,将人工与自动调整流程嵌入一体化自动编制流程,为列车运行图结构优化提供了切实可行的途径,通过京沪高速铁路案例研究,验证了运行图一体化自动编制技术的可行性。研究结果表明,高速铁路列车运行图一体化自动编制方法所计算得到的运行图与人工编制的真实运行图相近,可显著减少人工运行图编制流程中的人力和物力。现阶段,为使高速铁路列车运行图一体化自动编制所得结果更为理想,还需要进一步细化列车结构,同时适时采用人工调整策略,未来仍需要对高速铁路列车运行图一体化自动编制流程进行优化。