高铁夕发朝至列车开行与天窗设置协同优化

徐长安 ，李晟东 ，李斯涵 ，倪少权 ,2,3

（1.西南交通大学交通运输与物流学院，四川 成都 610031；2.西南交通大学综合交通运输智能化国家地方联合工程实验室，四川 成都 610031；3.西南交通大学综合交通大数据应用技术国家工程实验室，四川 成都 610031）

高速铁路夕发朝至列车是我国铁路部门为满足部分地区间旅客的夜间出行需求，在普速铁路夕发朝至列车基础上发展而来的一种客运产品，通常是指当日19∶00—23∶00 始发，次日06∶00—10∶00 终到，总在途时间7～15 h 的高速动车组列车.由于高速铁路夕发朝至列车的开行需要占据运行图中的夜间运行时分，会与天窗设置产生冲突，使得高铁夕发朝至列车开行计划编制难度很大.随着高速铁路夕发朝至客流的不断增长，实现高速铁路夕发朝至列车开行的网络化与日常化，是顺应铁路客运市场发展的必然趋势.在这种背景下，如何选择高速铁路夕发朝至列车开行模式，并实行天窗与高速铁路夕发朝至列车的协同优化，是今后高速铁路夕发朝至列车品牌发展所面临的重要问题.

许多学者从不同视角分析和研究了高速铁路夕发朝至列车开行与天窗设置协调优化问题，并取得了许多有意义的成果.赵丽珍等[1]以京沪高速铁路天窗方案设置为例，首次系统阐释了高速铁路列车开行方案与天窗的协调优化问题.朱健梅等[2]深入研究了客运专线夕发朝至列车合理开行时间域与天窗方案的协调优化问题，并指出单向隔日矩形天窗是我国客运专线天窗设置的较优方案.聂磊等[3]在分析客运专线矩形天窗开设与夜间行车相互影响的基础上，建立线性规划模型求解最佳矩形天窗位置.杨奎等[4]通过分析高速铁路综合维修天窗与夜间运行列车之间的动态影响关系，构建了天窗设置与夜间列车开行的协同优化模型.李博[5]研究了成网条件下高速铁路夕发朝至列车开行方案编制关键问题，提出了等天窗模式下的高速铁路夕发朝至列车开行方案编制理论与方法.Zhang 等[6]基于通道型高速铁路提出了列车运行方案与天窗设置的一体化编制模型.徐长安等[7]设计了基于优化进程分层的两阶段算法，求解天窗与列车运行图协同优化问题.

然而，既有研究多是基于列车开行模式已知情况，少有研究考虑列车开行模式未定情形下天窗设置与列车运行图的协同优化.本文以通道型高速铁路为研究对象，引入状态变量来刻画不同类型列车开行模式，进而构建了高速铁路夕发朝至列车开行与天窗设置协同优化模型，设计了基于自适应大邻域搜索的启发式求解算法，最后以京广高速铁路夕发朝至列车开行与天窗设置为例，验证了模型算法的有效性.

1 问题描述和参数说明

目前，我国高速铁路夕发朝至列车主要有3 种开行模式：等线模式、下线模式和下线-上线模式[8].等线模式是指夕发朝至列车始终在高速铁路上运行，遇到天窗则在车站待避，等天窗结束后继续运行.下线模式指夕发朝至列车在高速铁路运行一段距离后，为了避开天窗，转线至平行普速铁路继续运行，直至结束.下线-上线模式是指夕发朝至列车在高速铁路上运行一段时间后，为了避开天窗，转线至平行普速铁路运行，等天窗结束后，又从普速铁路转线至高速铁路继续运行的过程.图1 给出了3 种天窗开设模式在时空网络图中的对应表示，图中：s1～s7为车站；i1、i2为高铁夕发朝至列车；图中实线表示在高速铁路上运行，虚线表示在普速铁路上运行，阴影部分表示天窗.由于高速铁路列车转线至普速铁路运行后，运行速度不能超过普速铁路设计速度，因此，图1 中虚线的斜率小于实线的斜率.

图1 高速铁路夕发朝至列车开行模式Fig.1 Overnight train operation modes of high-speed railways

高速铁路夕发朝至列车与天窗协同优化主要解决两个层面的问题：一是根据线路条件与线路能力利用情况，确定选择何种类型的高速铁路夕发朝至列车开行模式.二是在选定列车开行模式后，如何安排天窗与列车在列车运行图中的位置，使得天窗对列车运行的影响最小.因此，高速铁路夕发朝至列车与天窗协同优化本质上是一个包含多变量多约束的组合优化问题.建模涉及的参数及变量定义如下：

1）常量.S为研究运输通道上所有车站集合，S=SG∪SP，SG和SP分别为高速铁路车站集合和普速铁路车站集合.在运输通道内，部分高速铁路车站和普速铁路车站通过联络线相连，具备高速铁路列车转线的可能，定义这类车站为关键车站，记为SK.IG、IP分别为高速铁路列车集合与普速铁路列车集合.IX、IR分别为高速铁路夕发朝至列车集合和高速铁路日间开行列车集合，则有IX⊂IG，IR⊂IG.ti(s,s+1)为列车i在区间 (s,s+1) 的运行时间，s为车站.Δta,a、Δtd,d、Δta,d和 Δtd,a分别为同方向列车同时到达、同时发车、不同时到发和不同时发到最小间隔时间[7].δs为车站s的到发线数目.zi,s为列车i在车站s的最小停站时间.分别为列车i在车站s的合理出发时间范围、合理到达时间范围.设DG={D1,D2,···,Dn} 为高速线路的n个天窗分段的集合，当n=1 时表示开设全线垂直矩形天窗.天窗分段可以用车站集合表示，出现在相邻两个天窗分段中的车站称为相邻天窗分段的分界站，分界站必属于关键车站.对任意的Dj，Dj+1∈DG，当=1时，Dj和Dj+1为相邻天窗分段，该车站为Dj和Dj+1的分界站.τb,j、τe,j分别为天窗分段Dj对应的天窗最早开始时间和最晚结束时间.Tm为天窗开设时长，ΔTm,b、ΔTm,e分别为天窗开始前和天窗结束后安全间隔.ζ 为足够大的正数.

2）状态变量.ρi,s表示当列车运行线与天窗发生冲突时，列车i在高速铁路线路上是否从车站s运行到车站s+1，取值1 表示是，取值0 表示否.表示当列车运行线与天窗发生冲突时，列车i在车站s是否等线，取值1 表示是，取值0 表示否.表示当列车运行线与天窗发生冲突时，列车i是否从车站s转到普速铁路运行，取值1 表示是，取值0表示否.=1 表示在列车运行线与天窗发生冲突时，列车i在车站s是否从普速铁路转到高速铁路线运行，取值1 表示是，取值0 表示否.xi,s为列车i在车站s是否停站，取值为1 表示停站，反之表示通过.

3）决策变量.ti,s,c、ti,s,d分别为列车i在车站s的出发时间、到达时间.Tm,j为第j个天窗分段对应的天窗开设时段.tj,b，tj,e分别为第j个天窗分段对应的天窗开始时间和结束时间，则Tm,j=[tj,b,tj,e].vi1,i2,s表示列车i1是否比列车i2更早从车站s出发，取值1 表示是，取值0 表示否.

2 模型构建

2.1 模型假设

本文研究基于以下前提进行：

1）高速铁路夕发朝至列车开行方案、停站方案以及各类作业时间标准均已知；

2）高速铁路在夜间00∶00—06∶00 开设分段矩形天窗，天窗分段划分情况视为已知条件；

3）高速铁路线路各个天窗分段时长相同，且各个天窗分段时长具有整体性，不能分割；

4）由于普速铁路天窗设置比较灵活，在夕发朝至列车下线运行时，不考虑对普速铁路天窗的影响；

5）相较于列车运行时间，夕发朝至列车通过衔接站下线或者上线都时间都很短，可忽略不计；

6）考虑高速铁路夕发朝至列车的到发时间段，设定本文研究时间范围为[19∶00，10∶00].

2.2 约束条件

1）列车合理到发时刻约束

为给旅客出行提供最大便利，夕发朝至列车在始发站的出发时间和在终到站的到达时间，以及在中间大站的到发时间均应处在合理时间范围内[7]，表示为式（1）、（2）所示.

2）区间运行时分约束

夕发朝至列车i在车站s与车站s+1 构成区间的运行时分等于列车到达车站s+1 的时间与列车从车站s出发的时间之差[7]，如式（3）所示.

3）列车停站时间约束

夕发朝至列车在车站的停站时间不能小于规定的最小停站时间要求[5,7]，如式（4）所示.

4）列车间隔时间约束

夕发朝至列车在车站的到达、出发以及通过均需满足一定的时间间隔要求[7]，如式（5）～（9）所示.

5）车站能力约束

在任意时刻t，车站被占用的到发线数量不能超过该站到发线能力[5].则车站到发线能力约束为

式中：i∈IX，s∈S；ω(ti,s,d,t) 和ω(ti,s,c,t) 为0-1 变量，分别表示车站s的到发线在时刻t是否被列车 占用，取1 表示被占用，反之表示未被占用，具体定义如式（11）、（12）所示.

6）列车运行与天窗安全间隔约束

对天窗分段Dj，其天窗开始时刻和结束时刻均需与列车运行保持一定的安全间隔[7]，以确保行车安全，如式（13）、（14）所示.

式（13）、（14）中：i∈IX,j∈{1,2,···,n} ,s∈SG.

7）天窗时间范围约束

天窗开设需满足一定的时间范围要求[7]，如式（15）、（16）所示.

式（15）、（16）中：j∈{1,2,···,n}，s∈SG.

式（15）表示天窗分段Dj的开设需在规定的天窗最早开始时间和最晚结束时间内.式（16）表示天窗结束时间等于天窗开始时间与天窗时长之和.

8）关键车站等价约束

由于本文假定列车在关键车站的转线时间忽略不计，因此，列车在关键车站的到发时刻满足式（17）、（18）所示等价约束.

式（17）、（18）中：i∈IX,s1∈(SG∪SK),s2∈ (SP∪SK).

9）列车开行模式选择约束

当夕发朝至列车在高速铁路运行，若在某个备选关键节点对应的天窗区段，其到发时间与天窗时间存在潜在冲突时，夕发朝至列车可选择等线模式或者下线模式运行.图2 表示夕发朝至列车i与天窗分段Dj存在潜在的时间冲突，列车i可以选择等线或者下线运行，分别对应或者.则对应如式（19）所示的列车开行模式选择约束.

图2 冲突情形下列车模式选择Fig.2 Mode selection of train in case of conflict

式中：φ (Tm,j,Ti) 为夕发朝至列车到发时间与天窗时间冲突判断函数，取值为1 表示存在冲突，取值为0 表示不存在冲突，其中：Ti=[ti,s,c,ti,s+1,d].

同理，当高速铁路夕发朝至列车在普速铁路运行，若在某个关键车站对应的天窗区段，其列车运行时间与高速铁路天窗没有冲突，则夕发朝至列车可由普速铁路上线至高速铁路运行，对应约束如式（20）所示.

10）状态变量约束

当高速铁路夕发朝至列车在备选关键节点选择不同的开行模式时，列车对应的开行状态会发生变化，本文跟列车开行状态相关的变量包括和 ρi,s，它们对应的约束如式（21）～（27）所示.

式（21）～（27）中：ρi,s∈{0,1}，i∈IX，s∈SK.

式（21）表示在每个备选关键车站，至多选择一种列车开行模式.式（22）表示在备选关键车站，只有在 ρi,s-1=1 与 ρi,s=1 同时满足的情况下，高速铁路夕发朝至列车才会选择等线模式.式（23）表示只有在 ρi,s-1=0 的情况下，高速铁路夕发朝至列车才会选择上线模式.式（24）、（25）表示高速铁路夕发朝至列车如果选择转线开行模式，则在转线前后车站的状态变量是不同的.式（26）表示高速铁路夕发朝至列车如果选择转线模式，则有 ρi,s=0.式（27）表示高速铁路夕发朝至列车如果选择上线模式，则有 ρi,s=1.

2.3 目标函数

本文主要从以下两个方面对高速铁路夕发朝至列车与天窗协调优化的目标进行考虑：

1）总的旅行时间最少

高速铁路夕发朝至列车的开行要最大程度满足旅客出行需求，除了列车到发时间需处在合理范围以内，列车总的旅行时间也要尽可能短，以提升客运产品竞争力和吸引力.高速铁路夕发朝至列车总的旅行时间可表示为

2）对既有列车运行图的影响最小

高速铁路夕发朝至列车的开行对既有列车运行图的影响主要体现在两个方面，一是对高速铁路日间开行列车的影响，二是在高速铁路列车下线情况下，对普速铁路列车的影响.本文以受影响列车运行线数量来刻画高速铁路夕发朝至列车开行对既有列车运行图的影响，则高速铁路夕发朝至列车的开行对既有列车运行图的影响可表示为

式（29）～（32）中：X、R、P分别为高速铁路夕发朝至列车运行线集合、高速铁路日间列车运行线集合和普速铁路列车运行线集合；φ1(X,R) 与 φ2(X,P)用来判定不同类型列车运行线集合之间的影响关系，若运行线集合相交，说明存在影响，反之，则不受影响.

综上，本文模型可表示为

3 求解算法

本文建立的高速铁路夕发朝至列车与天窗协同优化模型是一个双目标、非线性混合整数规划模型，模型中变量、约束众多，求解十分复杂.随着问题规模的扩大，计算难度呈现指数增长，假定某高速铁路线路备选的转线车站数量为nS，则对任意一趟夕发朝至列车而言，对应的列车开行模式至多有 22nS-1种，若夕发朝至列车的开行数量为nI，则对应的列车开行与天窗设置方案共有种.可以看出，若对式（33）直接求解，难度很大.因此，本文首先采取双目标转换[9]、约束线性化处理、无约束处理、模型约简等策略[10]（具体过程见附加材料1～4）来降低模型复杂度，再结合高速铁路夕发朝至列车与天窗协同优化问题的双层循环特性，设计了一种基于自适应大邻域搜索（adaptive large neighborhood search algorithm，ALNS）的启发式求解算法，算法包括内外两重循环：内循环由破坏邻域和修复邻域组成，用于进行局部搜索；外循环通过模拟退火机制控制，用于解的更新，并能够根据算子表现自适应调整算子权重.基于ALNS 的启发式求解算法主要内容包括邻域算子设计、自适应策略设计以及算法终止条件确定等几个方面（见附加材料5）.具体求解流程如下：

步骤1初始化算法参数.以现图中的高速铁路夕发朝至列车与天窗方案作为初始解e0，对应目标函数值为f(e0)，并令初始解为当前解e和最优解ebest：e0赋予e，e0赋予ebest，f(e0) 赋予f(e)，f(e0)赋予f(ebest).

步骤2初始化全部算子的分数与权重.将所有算子权重设为1，所有算子分数设为0.

步骤3根据式（34），从破坏邻域中选择一个删除算子，得到破坏解，并将从当前解中删除的列车置于设定的存储集合中.该存储集合包含了所有未安排的列车.

式中：pu为算子u被选中的概率；ωu为算子u的权重；H为算子的数量.

步骤4根据式（34）选择修复邻域中的一个插入算子，从设定的存储集合中选出部分列车，插入被破坏的解中，得到新解e’.

步骤5计算新解e’ 的目标函数值并与当前解e对应的目标函数值进行比较.如果e’ 对应的目标函数值f(e’) 优于e对应的目标函数值f(e)，则令e’ 为e，f(e’) 为f(e)；否则，使用模拟退火准则决定是否接受e’，同时相应更新e和f(e).

步骤6更新全部所选择算子的分数与权重.结合步骤5 中计算的新解的目标函数值，自适应策略部分给出的算子分数计算规则进行更新[11]，并根据式（35）更新算子的权重.

式中：θu为算子u的分数；λ ∈[0,1] 为算子权重更新参数.

步骤7判断是否满足算法终止条件.如果满足，转步骤8，如果不满足，转步骤3.

步骤8输出最优解ebest和最优解对应的目标函数值f(ebest)，算法结束.

4 算例分析

以京广高速铁路夕发朝至列车与天窗设置为例验证本文模型与算法的有效性.京广高速铁路全长2 298 km，包含36 个车站，从北京南站开始，依次编号为1～36，与京广高速铁路平行的京广线全长2 342 km，包含248 个车站，京广高速铁路与京广线共同构成京广运输通道.京广高速铁路夕发朝至列车始发时间域为18∶00—22∶00，终到时间域06∶30—09∶30，列车追踪间隔为5 min，车站到达和出发间隔均取5 min，最小停站时间为2 min，起停附加时分为2 min，同方向列车不同时到发间隔时间与发到间隔时间均为3 min；在京广普速铁路上，列车追踪间隔为5 min，车站到达和出发间隔均取5 min，最小停站时间为3 min，起停附加时分为2 min.天窗合理开设时间范围为00∶00—06∶00，天窗时长为240 min，天窗安全间隔时间为5 min.考虑车站能力及客流特点，选取石家庄、郑州东、武汉、长沙南、郴州西5 个大站作为备选的转线车站集合，对应的到发线总数分别为11、16、24、16、6 条.

京广通道内高速铁路和普速铁路区段距离和运行时间如附加材料6 中表S1 所示，由于上、下行方向信息基本一致，仅以下行方向为例给出.根据2018 年年底列车运行图数据[12]，京广高速铁路总共开行14 列夕发朝至列车，其中上行与下行方向各7 列.京广高速铁路夕发朝至列车，具体开行信息如附加材料6 中表S2 所示，包括列车始发、终到车站、运行方向、开行距离、旅行时间、合理出发、到达时间范围以及列车停站方案.

以2018 年年底列车运行图[12]为基准，根据本文提出的模型方法，将14 列高速铁路夕发朝至列车插入既有列车运行图框架.在19∶00—10∶00 这个时间段内，共包含73 列下行高速铁路日间列车，58 列上行高速铁路日间列车，在平行的普速铁路上，这个时间段共开行32 列下行普速列车，23 列上行普速列车.列车开行统计信息见附加材料6 中表S3.

采用MATLAB 7.0 编程实现设计的启发式求解算法，设最大迭代次数为200，ALNS 算法大约平均经过40 次便可收敛至最优解.在目标函数分别赋权0.5 的情况下，无量纲目标函数最小值为0.21，对应求解时间为784 s.目标函数最小值对应的最佳天窗设置方案和夕发朝至列车到发时刻表分别如表1和表2 所示.表2 中“/”两侧分别表示车站到达和出 发时刻.

表1 最优天窗方案Tab.1 Optimal maintenance window scheme

表2 京广高铁夕发朝至列车最优解对应的到发时刻表Tab.2 Optimal arrival and departure time table of Beijing-Guangzhou high-speed railways

为进一步分析不同列车开行模式对夕发朝至列车开行和天窗设置的影响，分别限定列车开行模式对目标函数进行求解，结果如表3 所示，表中第3 列中“/”左、右两侧分别表示在研究时间段内受影响的高速铁路列车数、普速列车数.对比可知，在不同列车开行模式下，高速铁路夕发朝至列车总的旅行时间、高速铁路夕发朝至列车对既有列车运行图的影响以及对应的计算时间均存在差异.

表3 不同列车开行模式下的目标函数值Tab.3 Objective function values under different overnight train operation modes

图3 给出了限定不同列车开行模式对应的最优天窗设置方案和夕发朝至列车运行方案，图中红线、蓝线分别表示列车在高速铁路、普速铁路运行.可以发现：不同列车开行模式下天窗较优方案均为分段矩形天窗，这是由于分段矩形天窗要比垂直矩形天窗设置更为灵活；上行方向列车转线运行通常是在郑州东站，而下行方向列车转线运行通常是在长沙南站，主要是因为这些车站能力相对充裕，且具备组织列车跨线运输条件.

图3 不同高速铁路夕发朝至列车开行模式下的天窗设置方案Fig.3 Maintenance window setting scheme under different overnight train operation modes of high-speed railways

5 结 论

1）通过引入状态变量，有效刻画了高速铁路夕发朝至列车的3 种开行模式，并据此建立了列车开行模式未定情形下高速铁路夕发朝至列车开行与天窗设置协同优化模型；

2）考虑构建模型特征，提出了双目标转化、约束线性化处理等模型约简策略，并结合优化问题的双层循环特性，设计了基于自适应大邻域搜索的启发式求解算法.

3）算例结果表明：本文算法大约平均经过40 次便可收敛至最优解，耗时784 s，具备较好的实用性.

4）未来研究可进一步考虑天窗设置与维修计划一体化编制，以提高天窗方案的可实施性.

备注：附加材料在中国知网本文的详情页中获取.