考虑动车组接续的区域城际网运行图加线模型

曲云腾，姚向明，赵 鹏，赵雅峰，邹庆茹

(1.北京交通大学 交通运输学院，北京 100044；2.中国国家铁路集团有限公司 科技和信息化部，北京 100844；3.中国铁路设计集团有限公司 交通运输规划研究院，天津 300308；4.重庆交通大学 交通运输学院，重庆 400074)

我国高速铁路(以下简称“高铁”)大力推动“一日一图”行车组织模式以适应客运需求波动、满足旅客高质量出行服务需求。运力供给侧改革导致运行图调整十分频繁,对编图效率及质量提出了很高的要求。实践中在既有运行图上“加线”“抽线”“调线”是调图的重要手段。一般情况下编图或调图不考虑动车组运用问题,但动车组合理运用对行车组织效率、运输成本有着重要影响,编图阶段若能协同考虑动车组运用将具有重要意义。为此,本文聚焦运行图“加线”技术,建立考虑动车组周转接续的多线路运行图协同加线优化方法,为运行图的高频调整提供技术支持。

加线是在既有运行图上安排额外列车以满足新增运输需求,本质是对运行图剩余能力的统筹规划。加线属于特定条件下的时刻表编制问题[1],既有研究领域主要包括3方面:①货物列车开行问题,如Cacchiani等[2]在保持客车运行线严格不变的前提下,构建以运行图总利润最大为目标的运行图加线模型,解决货物列车开行问题;Iswardani等[3]以单线铁路为背景,基于加线技术研究如何最大化插入货物列车数量;王锴楷等[4]针对货运班列发车延迟问题,以调整后总延迟时间最小为目标构建货车运行图加线优化模型。②客运需求导向的列车开行问题,如Zhao等[5]为满足不可预知大客流下的增量运输需求,基于加线技术提出适于高铁运输通道的列车开行优化方法;Liu等[6]针对轨道交通高峰客流量大、运输能力不足问题,基于加线技术提出一种确定新增列车运行线的多目标优化模型;李晓娟等[7]针对定制化列车开行问题构建双层协同优化模型,下层以列车运行区段剩余可用能力最大化为目标,向原列车运行图中插入定制列车运行线;高如虎等[8]研究了增开列车条件下的运行图调整问题。③通过能力测算:部分学者运用加线技术来测定运行图的最大通过能力,如张红斌等[9]基于整数规划建立通过能力最大化的运行图加线模型,提出启发式组合算法求解模型;Delorme等[10]利用加密运行图评价基础设施能力,采用贪心算法和贪心随机可调整搜索算法对求解效率进行深入分析;毛万华等[11]以加线列车数量最大为目标,充分利用运行图剩余能力来确定加线列车的运行线组合。此外,在提高加线模型求解效率方面也开展了较丰富的工作,如Burdett等[1]将加线问题转换为带时间窗约束的混合作业车间调度问题,提出一种采用构造性算法与模拟退火程序相结合的启发式算法;Gao等[12]建立混合整数线性规划模型解决运行图加线问题,并提出三阶段求解策略;高如虎等[13]分别利用拉格朗日松弛算法和交替方向乘子法对加线模型进行求解,对比分析了算法性能;Jiang等[14]在进行运行图加线时将列车时刻表与停站方案设计结合,提出基于拉格朗日松弛的启发式算法。可以看出,加线技术具有丰富的应用场景及实用价值,在货车开行、通过能力测算及客车开行等领域被广泛运用。然而既有研究主要应用于单条线路,且聚焦于运行线“插入”本身,鲜有研究同步考虑车底运用问题。

为此,本文以区域城际高铁网络化运营条件下动车组不固定运用模式为背景,针对客流需求激增带来的临客或短期客车开行需求,运用加线技术研究新增列车的运行线铺画问题。本文研究特点体现在:①研究范围由既有单条线路拓展为区域多条线路,问题规模及难度大幅提升;②加线过程中协同考虑动车组的周转接续关系,以期提升动车组运用效率、降低运输成本;③基于滚动时域算法设计求解策略,提高长时段(全日)多线路大规模列车开行条件下的求解效率。

1 问题描述

区域城际网示例见图1,由3条线路组成三角网络(均为双线)。假设受节假日或其他因素影响,区域内客运需求明显增加,既有运力难以满足客运需求。运营管理者结合客流需求预测、剩余运力资源等要素编制客流计划,确定增开列车的开行方案(列车开行时段、交路、对数等)。区域城际列车开行具有成对运行特点,动车组主要采用固定交路循环运用模式(少部分实施套跑、多交路混用)。考虑到客流需求往往具有明显的方向性,若成对开行易造成轻客流方向运力浪费。为此,本文假定动车组采用不固定灵活运用模式,可在区域内不同线路上跨线运行,担当不同交路的运输任务。该前提使得所构建的增开列车开行方案可按运行方向独立编制,新增列车开行方案示例见图2。理论而言,若线路1、2、3上增开列车的发车时间设置有序,最少仅需3组动车组即可完成运输任务;若动车组采用单线固定交路运行模式,则需6组(各线路开行2对列车)。

图1 区域城际高铁网示例

图2 新增列车开行方案示例

运行图加线及动车组接续示例见图3,线路2上S3→S6方向增开2列列车,若插入运行线的时间点布设合理,那么新增列车1可接续线路3上的列车4,列车2可反向接续列车3,从而减少动车组运用数。本文即在明确增开列车开行方案的前提下,研究如何在既有运行图中插入运行线,同时考虑动车组接续关系以提升运用效率。该问题是一个复杂的难题,插入运行线时考虑因素主要包括:①新增列车开行方案;②既有运行图剩余能力;③动车组接续时间要求;④动车组技术条件满足车底共用需求。考虑到新增列车往往仅担当短期运输任务,为保障既有运行图的稳定性和行车组织便捷性,假设原动车组运用计划不变,担当新增列车任务的动车组与原动车组间互不干扰。

图3 运行图加线及动车组接续示例

运行图加线模式见图4,根据既有运行图的能力利用程度,加线模式包含两类:①插空加线模式:当既有运行图剩余能力充足时直接利用运行线间隙插入新运行线,见图4(a);②调整加线模式:允许对既有运行线进行一定程度地微调,利用调整后运行图间隙添加新运行线,见图4(b)。调整加线模式通过整合运行图中分散的剩余能力以实现运行图能力的充分利用,提高加线可行性,同时也能保证新增运行线的质量。本研究假定既有运行图能力较为饱和,可对原运行线进行微调。

图4 运行图加线模式

2 模型构建

2.1 假设及定义

根据行车组织实践做如下合理性假设:①铺画新增运行线之前已编制新增开行方案,明确增开列车的开行时间域、交路、列数、编组、列车等级等要素;②动车组采用不固定运用模式,满足在区域城际高铁网范围内跨线行车技术条件;③允许对原运行线进行到发时刻微调,不允许调整列车顺序及停站方案;④考虑到城际列车交路较短,建立动车组周转接续方案时不考虑日常检修约束。便于模型描述,定义相关参数及变量符号,见表1。

表1 参数及变量符号定义

2.2 优化目标

1)对原运行图的影响程度最小化

加线势必导致对原行车计划造成影响,如车站作业计划、车底运用计划等。为保障行车组织稳定性、降低加线后行车组织难度,宜尽可能减少对原运行图的影响。采用调整后列车的到发时刻与原到发时刻的偏差z1来刻画影响程度(仅考虑原图定列车),即

(1)

2)动车组接续数量最大化

新增多条运行线时若其到发时刻及起讫站能够协调以满足动车组接续条件,那么可有效减少动车组运用数。以动车组可接续次数最大化z2为目标,即

(2)

需要注意的是,本研究仅考虑新增列车间的车底接续关系。为方便后续模型求解,添加负号将最大化转换为最小化目标z3,即

(3)

2.3 约束条件

1)列车到发时间及停站时间约束

列车经由各站的到发时刻与区间运行时间、停站时间相关。为提高运行图加线的可行性,允许对原运行线进行微调(即列车区间运行时间、停站时间的调整)。考虑启停附加时分,列车在相邻车站的到发时刻与区间运行时间约束关系为

(4)

(5)

列车停站时间需满足旅客乘降需求,且不能长时间停站,即

(6)

(7)

若列车不停站通过则βk,i=0,列车到站时刻等于发车时刻。

2)始发站发车时间约束

原图定列车容许其发车时间在一定阈值内调整,即

(8)

新增列车发车时间需位于发车时间域,该时间域在开行方案制定阶段已确定,范围设置较为宽泛以提高加线可行性,如8:00—10:00,约束为

(9)

3)行车安全间隔约束

列车到达各站的时间需满足追踪间隔要求以保障行车安全,相邻列车在车站的到达间隔时间约束为

∀k∈Km∈Ki∈Nk∩Nm

(10)

同理,相邻列车在车站的发车时间间隔约束为

∀k∈Km∈Ki∈Nk∩Nm

(11)

可以看出,列车先后关系确定时利用了关联系数yk,m,i。原图定列车间相互关系已知,而新增列车的相互关系为决策变量。为保证列车先后关系的唯一性,添加约束

yk,m,i+ym,k,i=1 ∀k∈Km∈K

i∈Nk∩Nm

(12)

4)车站接发车能力约束

车站到发线数量决定了接发车能力,若车站接发车能力较为紧张,则有必要在运行图加线时考虑接发车能力限制。列车占用车站到发线的唯一性约束为

(13)

当两列车占用车站同一到发线时,占用时间间隔需大于站线利用最小间隔时间,即

∀k∈Km∈K

i∈Nk∩Nmp∈Pizk,i,p=zm,i,p=1

(14)

5)动车组周转接续约束

动车组能够接续应满足:①列车类型(速度等级)相同;②前车终到站与后车始发站一致;③满足接续作业时间要求。动车组接续约束为

(15)

(16)

接续时每列车只能向后接续一列列车,同时只能被一列前向列车接续,接续关系具有唯一性,即

qk,m+qm,k≤1 ∀k∈K″m∈K″

(17)

(18)

(19)

3 模型求解

3.1 多目标处理

上述方法为非线性多目标整数规划模型,采用ε约束法将其转化为单目标问题进行求解。ε约束法无需额外设置参数、无需统一目标量纲,是处理多目标模型的重要方法之一。其核心思想是根据决策者对目标的重视程度,依次选取单目标作为目标函数,并设置缩放范围ε,再将该目标转化为约束加入原模型,求解下一个目标在新约束下的最优值,依次循环,直至所有目标被遍历。通过不断调整ε的取值,该方法能够生成多组不同条件下的最优解,即Pareto边界,能够支撑管理者进行综合决策。本文选取目标1(对原运行图的影响程度最小化)为最终目标,将目标3转换为动车组接续次数约束,即

(20)

通过不断更新ε的取值求得目标1的最优值,生成近似Pareto边界。

3.2 求解算法

区域城际高铁网具有多线路、开行列车数量大、新增列车开行方案复杂等特点,模型求解难度大。本文采用滚动时域算法对模型求解,滚动时域算法在时刻表编制或运行图调整领域被广泛应用。基本思想是将大规模问题按时间分解为多个较小规模的子问题,按时间先后顺序依次对子问题进行求解,且上一阶段的结果作为下一阶段的输入进行逐步求解。

H为研究时间范围;Ts为开始时刻;Te为结束时刻;h为每阶段求解过程包含的时间范围;r为每个阶段结束向后滚动的步长(r≤h)。滚动时域算法流程如下:

Step1输入模型相关参数,确定研究时间范围H=[Ts,Te]。

Step2设置滚动步长r、求解时间窗h的长度,初始滚动阶段g=1。

Step3求解所需滚动阶段总数G,将G取值从1开始以1为步长逐渐增加,当其满足条件H-(G-1)·r≤h的最小值时,G即为滚动阶段总数。

Step4判断g是否小于G。若是,则进入Step5;否则,进入Step7。

Step7当g=G(最后阶段),对模型求解并固定所得结果。

Step8整合各阶段固定结果,输出最终方案。

时域滚动过程中会产生运行线跨越两个时间窗的情形,对应列车称为跨时域列车,如图5中的列车k2、k3。时域滚动过程会割裂跨时域列车与后序列车间的约束关系,针对该问题进行如下处理:①当求解处于阶段g时,若所得结果中列车在各站的到发时刻位于时段r内,则记录相应时间和列车接续关系,固定为最终结果;②若列车在部分车站到发时刻位于时段h-r内,则清除对应的时间和接续关系(保留部分结果),下一阶段对其重新求解;③每当时域滚动后,对该阶段内第一列车与上一阶段最后一列跨时域列车添加始发站发车间隔约束,以保证行车安全要求。跨时域列车见图5,跨时域列车k3的始发时间已经固定,阶段g+1时列车k4与k3需添加始发站发车间隔约束。

图5 跨时域列车示意

时域滚动过程同样会对动车组的接续造成影响。时域分割对列车接续影响见图6,当完成阶段g的求解后,列车k1、k2的运行线已固定,列车k3相关信息被舍弃;当进入阶段g+1时,前一阶段被舍弃列车k3与k4等新囊括列车一并重新求解。由于上一阶段列车k1、k2已被固定,无法与k4所在时间范围(h-r)的列车进行接续(将会被舍弃)。针对该问题,设置参数时令h-r大于等于动车组最大允许接续时间。此时,受时域分割影响无法进行接续的两类列车就不能满足接续约束式(17),故不会对结果产生影响。

图6 时域分割对列车接续影响示意

4 案例分析

4.1 基本信息

选取宁杭高铁、京沪高铁(南京南至上海虹桥段)和沪昆高铁(上海虹桥至杭州东段)组成的环形网络为案例对象,见图7。总计25座客运站,其中枢纽站为南京南、上海虹桥和杭州东,均配有动车运用所,满足列车发车条件。以2020年12月某日实际运行图为原运行图(6:00—24:00),共开行列车730列,其中宁杭高铁200列、京沪高铁261列、沪昆高铁269列。受节假日影响,预计客流需求明显增长。基于客流计划确定新增列车开行方案,共新增列车25列,其中宁杭高铁增开11列,沪昆高铁增开6列,京沪高铁增开8列。增开列车均为最高速度为300 km/h的高等级列车,详细的列车开行方案见表2,分线路及方向依次对列车进行编号。为提高加线可行性,设置发车时间域较为宽泛。

图7 区域城际高铁网络

表2 加线列车详细开行方案

模型参数取值见表3。实际中各站接发车能力较为充裕,本案例暂不考虑车站到发线接发车能力约束。受篇幅限制,其他参数诸如区间运行时间不在此详尽罗列。

表3 模型基本参数

4.2 案例结果

采用Python编写滚动时域算法,每一子时段调用优化求解器Gurobi进行求解。将ε从1开始以0.05的步长递减,不断求解模型,得到目标z1(对原图的调整量)和目标z3(接续次数)的关系曲线,见图8。分析可知,列车接续次数与动车组数之和即为加线总数,而加线列车总数为25。将目标间关系曲线转换为z1与动车组运用数间相互关系,见图9。可以看出:①当动车组数大于10时,z1不再减小,表明在能够插入所有列车前提下该值为调整量最小值;②当ε=0.95时需4列动车组,此时若增加一列动车组,z1降幅较少;若减少一列动车组则z1大幅提升。因此,选取ε=0.95作为模型最终参数,此时所需动车组数为4列,对原图的调整量为481 min。

图8 目标z1与z3间相互关系

图9 目标z1与所需动车组数相互关系

加线后全日运行图见图10,其中红色运行线为加线列车,不同线路的运行线采用不同颜色区分。从动车组接续方案来看,共实现21次有效接续,需4组动车组完成运输任务,动车组接续方案见图11,由图11可知,每组动车组的接续方案及担当的车次任务。

图10 加线后列车运行图

图11 动车组接续方案

4.3 结果讨论

1)加线后运行图质量评估

定义方向1～6分别为宁杭高铁上下行、沪昆高铁上下行、京沪高铁上下行。加线前、加线后运行图质量指标见表4、表5。由表4、表5可见:①加线后列车平均旅行速度略微降低,旅行时间略有上升;②列车平均站停时间基本不变;③总体而言,加线后运行图质量并未明显降低,表明所提出方法能够在对原图较小影响的前提下实现新增列车的“插入”。

表4 加线前运行图质量指标

表5 加线后运行图质量指标

2)动车组运用效率评价

为更好地说明动车组运用效率的变化,以单线运营模式为对比场景(动车组固定运用、不可跨线行车)。利用加线模型分别对3条线路进行加线,该模式下需6组动车组完成运输任务。两种不同运营模式下的动车组运用效果见表6、表7,由表6、表7可以看出:①网络运营模式下所需动车数少2组,有效节省了列车开行成本;②网络运营模式下动车组接续时间较短,且各动车组运用时间相对均衡,利于动车组运用与维修;③以动车组运用时间占加线列车的总时间跨度范围(本案例取810 min,亦可取全日运营时段)的比值作为动车组利用率指标,网络运营模式下动车组利用率平均提高了9.7%,动车组运用效率提升效果明显。

表6 动车组运用效果(网络运营模式)

表7 动车组运用效果(单线运营模式)

5 结论

1)本文以区域城际高铁网络化运营为背景,针对客运需求波动下的运行图快速调整需求,建立考虑动车组接续的运行图加线模型,以实现多条线路上新增列车运行线的科学高效铺画;所提出方法能够有效提高运行图调图质量和效率,具有一定的应用价值。

2)案例分析验证了所提出方法的准确性与有效性,结果表明本模型能够同时满足区域内多条线路的运行图加线需求,且协同考虑了动车组的接续关系;对比既有单线运营模式下的加线问题,所需动车组减少,动车组利用率平均提高了9.7%,有效减少了运输组织成本。

3)本文仅以区域城际网为对象进行了模型验证,大规模高铁干线网的适用性尚未验证。此外,模型中仅考虑了动车组周转接续时间要求,而动车组在长大干线运行时检修是有必要考虑的因素。