基于动态影响关系的列车运行线与天窗协调编制方法研究

Research on Coordinated Compilation Method of Train Path and Skylight Based on Dynamic Influence Relationship

摘要

列车运行图中运行线和天窗共用时空资源，考虑两者的相互影响，有助于运力资源有效运用和运行图编制效率提升。为实现考虑天窗的运行线编制子问题和考虑运行线的天窗设置子问题协调优化，设计列车运行线与天窗协调编制流程、天窗方案生成比选算法、天窗分段设置与构型优化算法。基于区间天窗关联关系、天窗倾斜标尺等要素生成天窗方案备选集；使用多速度等级列车权重，计算各天窗方案影响值；通过天窗分段位置新增、天窗分段位置更新、天窗构型比选优化，实现天窗分段位置与构型优化。最后选取某客运专线为实例验证方法的有效性，结果表明，与人工实际方案图相比，达到了提升旅行速度、减少停时、维持停站的效果，实现了复杂场景快速协调编制，为实际编图工作提供参考。

Abstract

Considering the mutual influence of the spatial and temporal resources shared by train path and skylight in the train working diagram is crucial for effectively utilizing transportation capacity resources and enhancing the efficiency of train working diagram compilation. To achieve coordinated optimization between the subproblem of train path compilation considering skylight and the subproblem of skylight setting considering the train path, this paper designed a coordinated compilation process of train path and skylight, a skylight scheme generation comparison and selection algorithm, and a segmented skylight setting and configuration optimization algorithm. A candidate set of skylight schemes was generated based on elements such as section association relationships and skylight tilt scales. By using train weights with multiple speed levels, the impact values of each skylight scheme were calculated. By adding new skylight segment positions, updating skylight segment positions, and optimizing skylight configuration, the optimization of skylight segment positions and configurations was achieved. Finally, the effectiveness of the method was verified using the passenger dedicated line as an example. The results show that compared with the artificial actual scheme, it achieves the effect of improving travel speed, reducing stopping time, and maintaining the number of stops. It also achieves rapid coordination and compilation of complex scenes, providing a reference basis for the actual work of compiling train working diagrams.

Graphical abstract

关键词

列车运行图 / 运行线编制 / 天窗设置 / 天窗分段 / 动态影响 / 协调编制

Key words

Train Working Diagram / Train Path Compilation / Skylight Setting / Skylight Segment / Dynamic Influence / Coordinated Compilation

随着我国运输需求的逐年增长，列车运行图尤其是繁忙线路上的运输能力日益紧张，同时存在着多速度等级、本跨线列车混行的复杂场景，此时运行图中天窗开设时间的合理设置及其开设前后天窗三角区的充分利用成为能力进一步提升的关键所在。沿用以往的天窗设置编制列车运行线容易陷入能力瓶颈，而编制运行线后插入天窗又使维修时间无法得到保证，也就是说将运行线和天窗其中任意一项作为刚性约束都无法满足能力和维修的双重需求。目前，列车运行图编制问题中对于列车运行线和天窗设置协调优化的主要思路是将天窗开设时间作为变量，在编制运行线时同步确定，考虑不同的优化目标和约束，如减小旅行时间和维修成本目标^[1-2]、最小化列车运行计划偏差目标^[3-4]、最小化维修计划偏差目标^[5-6]、运行线经天窗降速约束^[7-8]、随机扰动约束^[9]等，或将维修计划作为虚拟列车进行最短路求解^[10]，实现运行线和天窗的一体化编制，但由于运行线编制问题本身已经考虑了众多要素，如果再加上可变的天窗开设时间，运行线和天窗之间的时空资源占用排序将呈现组合爆炸，影响求解效率，降低方法的适用性，同时一体化编制方式仍侧重降低天窗对于运行线的影响^[11-12]，仅少数研究讨论了考虑天窗与列车运行之间的动态影响关系^[13]和天窗分段问题^[14]，使用了禁忌搜索、蚁群搜索求解。因此有必要展开对运行线和天窗间耦合关系、天窗开设形式和天窗分段位置变化的讨论，针对考虑天窗的运行线编制子问题和考虑运行线的天窗设置子问题进行协调优化，为列车运行图能力充分运用和快速编制提供思路。

1　列车运行线与天窗协调编制流程设计

列车运行线与天窗协调编制流程框架如图1所示。首先调用列车运行线编制算法，基于列车开行方案、停站结构等输入，在无天窗条件下编制出列车运行线^[13]。在此基础上调用天窗方案生成算法，优化天窗分段位置与构型，进而提出天窗方案，并比选得到其中对运行线影响最小的方案，之后再次调用列车运行线编制算法，进入列车运行线与天窗两者协调迭代。迭代列车运行线时，依据当前天窗方案，在旅行时间最小目标的基础上，尽量避开天窗，铺画新的列车运行线。迭代天窗方案时，依据新铺画的列车运行线，将仍未避开天窗的列车权重增大，再生成新的影响最小的方案。两者协调迭代，直至所有列车运行线避开天窗，即完成运行图编制。其中，列车运行线编制方法使用文献[15]所提方法，构建基于时空网络的列车运行图编制模型，并使用ADMM分解算法求解；考虑运行线的天窗方案生成方法在第2章展开介绍。

2　考虑列车运行线的天窗方案生成方法

2.1　天窗方案生成模型

天窗设置需要确定3个基本要素，一是天窗的持续时间，与维修作业要求和内容相关，通常设置为一个给定常量；二是天窗的基本构型，即确定各区间天窗的相对位置，主要有垂直天窗和V型天窗2种，垂直天窗在各区间天窗开始时间相同，V型天窗除了具有关联关系的区间天窗需要合并作业外，其后序区间天窗的开始时间大于等于前序天窗开始时间+5 min的整倍数；三是确定天窗的开始时间，总体目标是对列车运行线的影响最小。基于天窗设置的基本要素，构建一套天窗方案生成模型，模型的目标函数及约束条件如下。

2.1.1　目标函数

（1）连续天窗三角区Z_{\mathrm{1}}最小化。如果将天窗看作虚拟运行线，缩小天窗倾斜线与列车运行线的差异更有利于运行图形成平行图，以此减少天窗三角区的能力空费。基于列车运行标尺给定天窗运行标尺作为输入，由于天窗倾斜标尺中的区间运行时间不一定符合天窗开设时间粒度，为补足时间粒度而产生余数时间，因此须尽可能地减少各区间天窗开设时间的余数时间，使天窗尽可能地贴近天窗倾斜线开设，以减少连续天窗中因各区间天窗错位产生的天窗三角区。

Z_{\mathrm{1}}=\mathrm{m}\mathrm{i}\mathrm{n}\sum _{q_i\in Q}{\beta }_{q_i}(1)

式中：{\beta }_{q_i}表示在区间q_i天窗开设时间为补足时间粒度而产生的余数时间，s；Q=\left\{q_{\mathrm{1}}，q_{\mathrm{2}}，\cdots ，q_{n-\mathrm{1}}\right\}表示区间q_i的集合。

（2）天窗对列车运行线的影响Z_{\mathrm{2}}最小化。同时尽可能减小天窗对列车运行线的影响，不同的天窗方案影响值是其各区间天窗方案影响值之和，各区间天窗方案影响值是受到天窗影响的运行线的列车权重之和，使用列车运行线权重计算天窗对列车运行线的影响值。

Z_{\mathrm{2}}=\mathrm{m}\mathrm{i}\mathrm{n}\sum _{q_i\in Q}{Z}_{q_i}=\mathrm{m}\mathrm{i}\mathrm{n}\sum _{q_i\in Q}\sum _{j\in J}{\mu }_j{\alpha }_{q_{i}j}(2)

式中：Z_{q_i}表示各区间天窗方案影响值；{\mu }_j表示列车权重；J=\left\{j_{\mathrm{1}}，j_{\mathrm{2}}，\cdots ，j_m\right\}表示列车j运行线的集合；{\alpha }_{q_{i}j}表示区间q_i天窗是否影响列车j，有影响为{\alpha }_{q_{i}j}=\mathrm{1}，否则为0。

2.1.2　约束条件

（1）天窗开设持续时间约束。天窗的持续时间，与维修作业要求和内容相关，通常设置为一个给定常量，如普速铁路天窗持续时间一般为180 min，高速铁路一般为240 min。

w_{q_i}^{\mathrm{e}}-w_{q_i}^{\mathrm{s}}={\tau }_{q_i}^{\mathrm{t}\mathrm{c}}\forall q_i\in Q(3)

式中：w_{q_i}^{\mathrm{s}}表示区间q_i的天窗开始时间，s；w_{q_i}^{\mathrm{e}}表示区间q_i的天窗结束时间，s；{\tau }_{q_i}^{\mathrm{t}\mathrm{c}}表示区间q_i的天窗持续时间，s。

（2）天窗开设时间范围约束。在允许时间范围内开设天窗，如普速铁路天窗开设时间一般为全天，高速铁路一般为夜间。

w_{q_i}^{\mathrm{s}}\in W_{q_i}^{\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}}\forall q_i\in Q(4)

w_{q_i}^{\mathrm{e}}\in W_{q_i}^{\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}}\forall q_i\in Q(5)

式中：W_{q_i}^{\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}}表示区间q_i允许开设天窗的时间集合。

（3）天窗开设时间粒度约束。为便于现场的行车指挥，天窗开设时间通常设置在0或5 min的整点分钟，此时的天窗时间粒度取5 min。

w_{q_i}^{\mathrm{s}}-⌊\frac{w_{q_i}^{\mathrm{s}}}{u}⌋u=\mathrm{0}\forall q_i\in Q(6)

w_{q_i}^{\mathrm{e}}-⌊\frac{w_{q_i}^{\mathrm{e}}}{u}⌋u=\mathrm{0}\forall q_i\in Q(7)

式中：u表示时间粒度，s。

（4）区间天窗关联关系约束。区间天窗间具有2种关系，一是区间天窗存在关联关系，二是区间天窗不存在关联关系。具有关联关系的区间天窗有2种关系，一是区间天窗存在合并关联关系，二是区间天窗不存在合并关系。前者的区间天窗开始时间按天窗倾斜标尺保持天窗开始时间错位时间差，后者的区间天窗开始时间保持一致。例如，垂直天窗在各区间天窗开始时间相同，V型天窗具有关联关系且需要合并作业的天窗开设时间相等。

w_{q_i}^{\mathrm{s}}-w_{q_{i-\mathrm{1}}}^{\mathrm{s}}=\left\{\begin{array}{c}\begin{array}{l}{\tau }_{q_i}^{\mathrm{v}}+{\beta }_{q_i}{\delta }_{q_{i-\mathrm{1}}{q}_i}=\mathrm{0},{\epsilon }_{q_{i-\mathrm{1}}{q}_i}=\mathrm{1},\\ {\beta }_{q_i}\ge \mathrm{0},\forall q_{i-\mathrm{1}}\in Q,\forall q_i\in Q\end{array}\\ \begin{array}{l}\mathrm{0}{\delta }_{q_{i-\mathrm{1}}{q}_i}=\mathrm{1},{\epsilon }_{q_{i-\mathrm{1}}{q}_i}=\mathrm{1},\\ \forall q_{i-\mathrm{1}}\in Q,\forall q_i\in Q\end{array}\end{array}\right.(8)

式中：{\tau }_{q_i}^{\mathrm{v}}表示区间q_i在天窗倾斜标尺下的区间运行时分，s；{\epsilon }_{q_{i-\mathrm{1}}{q}_i}表示区间q_{i-\mathrm{1}}和q_i的天窗关联关系，存在区间天窗关联关系{\epsilon }_{q_{i-\mathrm{1}}{q}_i}=\mathrm{1}，否则{\epsilon }_{q_{i-\mathrm{1}}{q}_i}=\mathrm{0}；{\delta }_{q_{i-\mathrm{1}}{q}_i}表示区间q_{i-\mathrm{1}}和q_i的关联天窗合并关系，存在区间天窗合并关联关系{\delta }_{q_{i-\mathrm{1}}{q}_i}=\mathrm{1}，否则{\delta }_{q_{i-\mathrm{1}}{q}_i}=\mathrm{0}。

（5）天窗对运行线影响约束。列车运行线进入天窗开设时间范围内，将产生天窗对运行线的影响，其影响程度根据列车速度等级给定列车权重。

{\alpha }_{q_{i}j}=\left\{\begin{array}{c}\mathrm{1}{\alpha }_{q_{i}j}^n=\mathrm{1},\forall n\in N,\forall q_i\in Q,\forall j\in J\\ \mathrm{0}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\end{array}\right.(9)

式中：{\alpha }_{q_{i}j}^n表示在列车运行线进入天窗时段的第n种情形下，若区间q_i天窗影响列车运行线为{\alpha }_{q_{i}j}^n=\mathrm{1}，否则为0。

天窗与运行线关系如图2所示，具体情形如下。

①运行线在天窗时间开始前进入区间，而后穿过区间天窗左边界，但未穿过天窗右边界，如图2a所示。

{\alpha }_{q_{i}j}^{\mathrm{1}}=\left\{\begin{array}{c}\mathrm{1}{t}_{q_{i}j}^{\mathrm{a}}\le w_{q_i}^{\mathrm{s}},t_{q_{i}j}^{\mathrm{d}}\ge w_{q_i}^{\mathrm{s}},t_{q_{i}j}^{\mathrm{d}}\le w_{q_i}^{\mathrm{e}},\forall q_i\in Q,\forall j\in J\\ \mathrm{0}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\end{array}\right.(10)

式中：t_{q_{i}j}^{\mathrm{a}}表示在区间q_i列车运行线j的到达时间，s；t_{q_{i}j}^{\mathrm{d}}表示在区间q_i列车运行线j的出发时间，s。

②运行线在天窗时间开始后进入区间，在天窗时间结束前离开区间，完全运行在天窗时间内，如图2b所示。

{\alpha }_{q_{i}j}^{\mathrm{2}}=\left\{\begin{array}{c}\mathrm{1}{w}_{q_i}^{\mathrm{s}}\le t_{q_{i}j}^{\mathrm{a}},t_{q_{i}j}^{\mathrm{d}}\le w_{q_i}^{\mathrm{e}},\forall q_i\in Q,\forall j\in J\\ \mathrm{0}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\end{array}\right.(11)

③运行线在天窗时间开始后进入区间，在天窗时间结束后离开区间，穿过天窗时间右边界，如图2c所示。

{\alpha }_{q_{i}j}^{\mathrm{3}}=\left\{\begin{array}{c}\mathrm{1}{t}_{q_{i}j}^{\mathrm{a}}\le w_{q_i}^{\mathrm{e}},t_{q_{i}j}^{\mathrm{d}}\ge w_{q_i}^{\mathrm{e}},t_{q_{i}j}^{\mathrm{a}}\ge w_{q_i}^{\mathrm{s}},\forall q_i\in Q,\forall j\in J\\ \mathrm{0}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\end{array}\right.(12)

④运行线在天窗时间开始前进入区间，在天窗时间结束后离开区间，同时穿过天窗左右边界，而现实中天窗时间通常是远远大于列车区间运行时间的，因此该情形在特定需求中出现，如考虑多区间合并计算场景，如图2d所示。

{\alpha }_{q_{i}j}^{\mathrm{4}}=\left\{\begin{array}{c}\mathrm{1}{t}_{q_{i}j}^{\mathrm{a}}\le w_{q_i}^{\mathrm{s}},t_{q_{i}j}^{\mathrm{d}}\ge w_{q_i}^{\mathrm{e}},\forall q_i\in Q,\forall j\in J\\ \mathrm{0}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}r\end{array}\right.(13)

2.2　天窗方案生成算法

考虑列车运行线的天窗开设问题实质上是组合优化问题，问题的规模随着列车数、车站数和天窗允许开设时间窗范围的增加指数式增长，为简化问题结构，降低计算复杂度，减少搜索空间，设计两阶段算法，把天窗问题视为天窗开设时间方案组合优化、天窗分段与构型方案组合优化2个子问题，分解天窗约束耦合关系，将区间天窗关联关系\epsilon和合并关联关系\delta在子问题2中求解，使2个子问题的输出互为输入进行反馈。

2.2.1　天窗方案比选生成算法

基于考虑列车运行线的天窗方案生成模型，设计天窗方案比选生成算法，求解天窗开设时间方案组合优化子问题，包括天窗基本构型生成和天窗方案比选2个部分，其实现的主要思路是：生成最贴近天窗倾斜线的天窗基本构型；在允许设置天窗的时间范围内，计算天窗方案备选集，给不同等级的运行线赋予不同的影响值权重^[16]，计算每个备选天窗方案对运行线的总影响值；对不同的天窗方案排序，选择其中对运行线影响最小的方案，进行下一步的运行线编制。具体步骤如下。

步骤1：输入基础路网(包括车站S=\left\{s_{\mathrm{1}}，s_{\mathrm{2}}，\cdots ，s_n\right\}、区间Q=\left\{q_{\mathrm{1}}，q_{\mathrm{2}}，\cdots ，q_{n-\mathrm{1}}\right\})、列车运行线(列车在车站s_i的到发时刻t_{s_i}^{\mathrm{a}}和t_{s_i}^{\mathrm{d}})、等级为j的运行线权重{\mu }_j、天窗持续时间{\tau }^{\mathrm{t}\mathrm{c}}、天窗分段与构型方案对应的区间天窗关联关系\epsilon和合并关联关系\delta、天窗倾斜标尺{\tau }^{\mathrm{v}}、允许设置天窗时间范围、天窗时间粒度u，时间粒度取5 min。

步骤2：根据天窗倾斜标尺下的区间运行时分{\tau }_{q_i}^{\mathrm{v}}生成天窗倾斜线l，将其作为虚拟列车运行线，即从前一个区间q_{i-\mathrm{1}}运行至后一个区间q_i的区间运行时间是{\tau }_{q_i}^{\mathrm{v}}，将其作为各区间天窗最小错位时间差。

步骤3：生成天窗基本构型。以天窗倾斜线起始车站为起点，设起始区间天窗开始时间为0，沿天窗倾斜线遍历各区间q_i。

确定相邻区间维修作业关系，当具有关联关系且存在合并关系时，{\epsilon }_{q_{i-\mathrm{1}}{q}_i}=\mathrm{1}且{\delta }_{q_{i-\mathrm{1}}{q}_i}=\mathrm{1}，此时前一天窗和后一天窗的开始时间存在时间差，关联后序区间的天窗开始时间应后移。使用前一区间天窗开始时间w_{q_{i-\mathrm{1}}}^{\mathrm{s}}和区间天窗最小错位时间差{\tau }_{q_i}^{\mathrm{v}}，计算后一区间天窗最小开始时间w_{q_i}^{\mathrm{s}\mathrm{*}}，即w_{q_i}^{\mathrm{s}\mathrm{*}}=w_{q_{i-\mathrm{1}}}^{\mathrm{s}}+{\tau }_{q_i}^{\mathrm{v}}。当具有关联关系且不存在合并关系时，{\epsilon }_{q_{i-\mathrm{1}}{q}_i}=\mathrm{1}且{\delta }_{q_{i-\mathrm{1}}{q}_i}=\mathrm{0}，此时前一天窗和后一天窗开始时间差是0，关联区间的天窗开始时间同步。

计算得到后一区间天窗开始时间w_{q_i}^{\mathrm{s}}=⌊\frac{w_{q_i}^{\mathrm{s}\mathrm{*}}}{u}⌋u，此时相邻区间天窗开始时间差的补足时间粒度最小余数时间是{\beta }_{q_i}=w_{q_i}^{\mathrm{s}}-w_{q_{i-\mathrm{1}}}^{\mathrm{s}}-{\tau }_{q_i}^{\mathrm{v}}。遍历各区间计算天窗开始时间，将各区间天窗开始时间依次后移，即可生成满足各连续区间天窗三角区最小化目标式(1)的各区间天窗开始时间。

使用各区间天窗开始时间w_{q_i}^{\mathrm{s}}和天窗开设持续时间{\tau }_{q_i}^{\mathrm{t}\mathrm{c}}，计算各区间天窗结束时间w_{q_i}^{\mathrm{e}}，得到天窗基本构型。

步骤4：依据约束条件式(4)—(7)，在天窗允许开设的时间范围内，以u为粒度，生成天窗开始时间w_{q_i}^{\mathrm{s}}的备选集。使用天窗基本构型中的各区间天窗开始时间差{\tau }_{q_i}^{\mathrm{v}}+{\beta }_{q_i}，生成满足天窗开设时间粒度的不同天窗开设时间点的天窗备选方案{\phi }_k，其中包含各区间天窗开始时间和天窗结束时间，形成天窗方案备选集\Phi =\left\{{\phi }_{\mathrm{1}}，{\phi }_{\mathrm{2}}，\cdots ，{\phi }_m\right\}。

步骤5：依据约束条件式(9)—(13)，遍历天窗方案备选集，根据输入的列车在车站的到发时刻，得到列车占用区间时刻t_{q_i}^{\mathrm{a}}和t_{q_i}^{\mathrm{d}}，比较天窗备选方案{\phi }_k的天窗开始时间w_{q_i}^{\mathrm{s}}和天窗结束时间w_{q_i}^{\mathrm{e}}，判断各运行线和天窗之间的位置关系。

步骤6：根据运行线和天窗位置关系判断，记录天窗备选方案中，在各区间天窗时间内的运行线j是否受到影响，若运行线受到天窗影响则{\alpha }_{q_{i}j}=\mathrm{1}，反之为0，使用列车运行线权重计算天窗对列车运行线的影响值，具体根据天窗和运行线是否跨天分为4种情况，使用\pm1 440 min进行跨天时间转换。

步骤7：完成遍历后，排序比较各天窗备选方案的影响值Z_k，输出影响值最小的天窗设置方案{\phi }_k，即可得到满足天窗对运行线影响最小化目标式(2)的天窗设置方案。

2.2.2　天窗分段位置与构型优化算法

在实际编图工作中，针对由于新增列车而需要调整天窗的场景，通常要求不可过多影响既有列车运行线。在一些里程较长的线路上，全线采用连续的垂直或V型天窗不能满足要求。天窗分段设置如图3所示。若全线采用连续V型天窗，如图3a所示，则无法完全避开既有列车运行线，而若在恰当的位置将天窗分段，对每个分段分别设计构型，如图3b所示，则能较好满足要求，生成优化的天窗方案。

天窗分段的目的是减少天窗对运行线的影响，目标是分段后天窗方案影响值最小，天窗分段的关键在于如何判断天窗分段的位置^[14]，如果仅仅搜索各区间的天窗影响值最小的位置，将会导致各天窗分段被切分的太细，最细化的天窗分段方案就是每一个区间为一个天窗分段，分别找到每个区间的天窗影响值最小值所在时间即为各区间天窗分段的天窗开始时间，但这显然不是合理的分段方式，因为天窗的实质是维修计划，用于预留工务、电务等部门维修作业的时间，如果将天窗分段划分得太细，将严重破坏天窗的连续性和维修计划的适用性。

基于对天窗方案比选生成算法的调用，设计天窗分段位置与构型优化算法，包括天窗分段位置新增、天窗分段位置更新、天窗构型比选优化3个部分，其实现的主要思路是：输入初始天窗方案的区间天窗关联关系和合并关系，采用连续垂直或V型天窗生成影响值最小的天窗方案，分析该方案中各区间影响值，寻找影响值跃变的区间，其中影响值跃变是指相邻区间天窗方案影响值的差分绝对值超出了跃变阈值，跃变阈值是指相邻区间天窗影响值的差分绝对值能够接受的最高值，影响值跃变点是指发生影响值跃变的相邻区间中共同的车站，将发生跃变的车站作为天窗构型中新增的天窗分段位置，更新区间天窗关联关系\epsilon。各区间天窗影响值跃变如图4所示，区间E—F和区间F—G、区间J—K和区间K—L的天窗影响值发生跃变，则选取车站F和车站K作为新增的天窗分段位置。更新天窗分段方案及区间天窗关联关系\epsilon，针对各天窗分段分别采用不同构型，即在不同的合并关联关系\delta下生成天窗方案，最终选取影响值最小的方案输出。具体步骤如下。

步骤1：输入天窗初始构型和分段方案及其区间天窗关联关系{\epsilon }^{\mathrm{*}}和合并关联关系{\delta }^{\mathrm{*}}、各构型连续的天窗分段方案在各区间的天窗影响值z_{q_{\mathrm{1}}}，z_{q_{\mathrm{2}}}，\cdots ，z_{q_n}、相邻区间天窗影响值的差分绝对值波动系数{\alpha }_{\mathrm{F}}(取{\alpha }_{\mathrm{F}}=\mathrm{2.5})，用于计算天窗影响值跃变阈值F。

步骤2：遍历天窗分段，计算相邻区间天窗影响值的差分绝对值d_{q_{\mathrm{1}}{q}_{\mathrm{2}}}，d_{q_{\mathrm{2}}{q}_{\mathrm{3}}}，\cdots ，d_{q_{n-\mathrm{1}}{q}_n}，例如起始区间的差分绝对值为d_{q_{\mathrm{1}}{q}_{\mathrm{2}}}=\left|z_{q_{\mathrm{1}}}-z_{q_{\mathrm{2}}}\right|，并找到其中的最大值maxd_{q_{m-\mathrm{1}}{q}_m}，同时计算相邻区间天窗影响值的差分绝对值的平均值\overline{d}和天窗影响值跃变阈值F=\overline{d}{\alpha }_{\mathrm{F}}。

步骤3：如果区间天窗影响最大差分值maxd_{q_{m-\mathrm{1}}{q}_m}小于跃变阈值F，转至步骤9，否则转至步骤4。

步骤4：定位跃变区间q_{m-\mathrm{1}}，q_m，记录本轮循环跃变车站s_{m-\mathrm{1}}，将跃变车站s_{m-\mathrm{1}}作为新增的天窗分段位置，更新天窗分段方案，同时区间天窗关联关系更新为{\epsilon }_{q_{\mathrm{m}-\mathrm{1}}{q}_{\mathrm{m}}}=\mathrm{0}。

步骤5：保持现有天窗构型，根据天窗分段方案，使用天窗方案比选生成算法，计算天窗方案影响值。

步骤6：如果当前为首次跃变，即r=0，转至步骤1，否则转至步骤7。

步骤7：如果第r轮循环跃变车站s_n^r和第r-1轮循环跃变车站s_m^{r-\mathrm{1}}为相邻车站，出现天窗分段位置连续新增现象，转至步骤8，否则转至步骤9。

步骤8：以第r-1轮循环跃变车站s_m^{r-\mathrm{1}}为起点，以车站s_m^{r-\mathrm{1}}\to s_n^r为方向，以车站o—d表示该天窗分段全程，遍历车站定位新增天窗分段位置车站p，形成天窗o—p分段和p—d分段，保持现有天窗构型，分别使用天窗方案比选生成算法，计算不同天窗分段位置方案的天窗方案影响值Z^p，得到一组天窗方案影响值Z^{p_{\mathrm{1}}}，Z^{p_{\mathrm{2}}}，\cdots ，Z^{p_n}，找到其中的最小值即为天窗分段位置的帕累托解，其最小值所在车站p^{\mathrm{*}}则替换跃变起始车站s_m^{r-\mathrm{1}}和s_n^r成为新增天窗分段位置，更新天窗分段方案，同时区间天窗关联关系更新为0。

步骤9：根据天窗分段方案，调用天窗方案比选生成算法，分别计算在不同天窗构型下的天窗分段方案影响值，对于垂直天窗构型方案，更新其区间天窗合并关联关系{\delta }_{q_{i-\mathrm{1}}{q}_i}=\mathrm{1}；对于V型天窗构型方案，当初始合并关系{{\delta }^{\mathrm{*}}}_{q_{i-\mathrm{1}}{q}_i}=\mathrm{1}时，更新其区间天窗合并关联关系{\delta }_{q_{i-\mathrm{1}}{q}_i}=\mathrm{1}，当初始合并关系{{\delta }^{\mathrm{*}}}_{q_{i-\mathrm{1}}{q}_i}=\mathrm{0}时，更新其区间天窗合并关联关系{\delta }_{q_{i-\mathrm{1}}{q}_i}=\mathrm{0}。完成各天窗分段遍历后，从不同天窗构型中比选出影响值最小的天窗设置方案{\phi }_k，输出区间天窗关联关系\epsilon和合并关联关系\delta。

3　案例分析

3.1　算例选取

为实施“客运提质，货运增量”战略，在某实际运营线路原运行线方案图的基础上，运输部门提出了某长大干线部分普速旅客列车更改运行径路至其平行通道客运专线上的开行需求，共涉及40个车站和193列列车。列车运行径路变更后客运专线上同时存在250 km/h，160 km/h，140 km/h，120 km/h等多速度等级列车，且动车组列车禁止进入同向和对向天窗，使得该客运专线原有的垂直天窗不再适用，需重新适配V型天窗，增加了列车运行线的编制难度。因此，选取该客运专线全线作为典型案例，根据实际需求，天窗持续时间取240 min，开设时间粒度取5 min，允许开设时间范围为全天1 440 min，天窗倾斜标尺取该线普通快速旅客列车运行标尺且精确到秒级运算，验证本研究所提列车运行线与天窗协调编制方法的可行性与适应性。

3.2　协调编制

对于运行线，将更改列车运行径路后的列车开行方案和停站方案作为输入，以列车上下线时刻为运行线编制时间窗，编制生成无天窗条件下的初始列车运行线，其中对于正常运营的旅客列车，输入的停站方案中的停站车站作为列车必停站，输入的停站方案中的通过车站作为列车灵活停站，最小停站时间设为2 min。对于其他列车，如DJ和0D列车，其已知停站方案不作为列车必停站考虑。

列车运行线与天窗协调编制如图5所示。对于天窗，将原运行线方案图的分段位置和各区间天窗关联关系和合并关系作为输入，如图5a所示，以车站4，14，20为3个天窗初始分段位置。同时，输入不同速度等级列车权重，列车权重使用文献[16]所提专家打分法确定，多速度等级列车权重如表1所示，由于客运专线要求动车组列车禁止进入同向和对向天窗，因此其列车权重不仅在同向天窗中使用也在对向天窗中使用，用于计算各区间天窗影响值。当以跃变点车站为界新增天窗分段时，分别按垂直天窗和V型天窗构型计算各天窗分段的天窗影响值进行比选，车站20—40天窗构型方案比选如表2所示，分段开设V型天窗比垂直天窗对运行线的影响更小。

经过4次迭代，先后定位天窗影响值跃变点为车站24，30和35，直至所有列车运行线均满足天窗约束，完成列车运行线和天窗协调编制，如图5b所示。

3.3　指标分析

为验证算法优化方案图的实现效果，将其与人工实际方案图对比，人工实际方案图是指编图现场实际应用的方案图。人工实际方案图与算法优化方案图运行线指标对比如表3所示，其中算法优化方案图的总旅行时间减少了32 h5 min，平均旅行速度提高了6.25 km/h，除DJ和0D列车停站减少48次外，其他正常运营列车停站次数不变，平均停站时间缩短了2 min50 s，总停站时间缩短了9 h8 min。其中，总停站次数的减少由DJ和0D列车停站次数减少引起，平均停站时间和总停站时间的减少是由于算法优化方案是一种理想方案，将最小停站时间设定为2 min，造成列车在各站的停站时间相较于人工实际方案图均有所减少。可以看出，算法优化方案图可以满足列车开行对数和停站方案的需求，并在一定程度上提升了列车旅行速度，基本达到与现场实际相近的运行图效果。

原运行线方案图、人工实际方案图与算法优化方案图天窗开设形式对比如表4所示，以原运行线方案图中的区间天窗关联关系与合并关系作为初始输入，其中车站26—40区段为垂直天窗，由于原运行线方案图和人工实际方案图中的列车开行方案不同，导致试验编制结果中车站26—40区段更改为V型天窗，算法优化方案图较人工实际方案图，除部分天窗分段位置与构型优化不同外，如算法优化方案图中在车站30和车站35分段、人工实际方案图中在车站31和车站37分段，其整体天窗开设效果与人工实际方案图基本一致。

实例验证表明，本研究所提列车运行线与天窗协调编制方法考虑了列车运行线与天窗开设方案间的相互影响，可以在不确定天窗如何变化的条件下，生成天窗开设方案，优化天窗分段与构型，在保证列车正常运行的开行对数和停站方案的需求下，进行列车运行线编制，实现了复杂场景下列车运行线与天窗协调编制的效果。

4　结束语

我国路网规模日益扩大，运输需求逐年增加^[17-18]，对列车运行图能力充分运用、运力资源合理配置提出更高的要求。研究通过构建列车运行线和天窗设置协调编制流程，设计天窗方案比选生成算法、天窗分段设置与构型优化算法，尝试解决列车运行图编制过程中运行线和天窗的协调优化问题。通过运行线问题和天窗问题的快速反馈、简便计算和累积影响，既有助于实现满足运输和维修需求的双重效果，也有利于现场编图人员的实践与应用。选取某客运专线为例验证方法的可行性，经案例测试分析，研究提出的方法，在天窗分段位置和天窗构型未定、列车运行线在规定时间窗内开行的列车运行图编制场景中，达到了提升旅行速度、维持停站、减少停时的效果，具备有效性和适用性，可以为多速度等级、本跨线列车混行的复杂场景列车运行图快速编制与调整提供参考。

参考文献

[1] ZHANG Y X， D’ARIANO A， HE B S，et al. Microscopic Optimization Model and Algorithm for Integrating Train Timetabling and Track Maintenance Task Scheduling[J]. Transportation Research Part B：Methodological，2019，127：237-278.

[2] ZHANG C T， GAO Y， YANG L X，et al. Joint Optimization of Train Scheduling and Maintenance Planning in a Railway Network：A Heuristic Algorithm Using Lagrangian Relaxation[J]. Transportation Research Part B：Methodological，2020，134：64-92.

[3] LIDÉN T， JOBORN M. An Optimization Model for Integrated Planning of Railway Traffic and Network Maintenance[J]. Transportation Research Part C：Emerging Technologies，2017，74：327-347.

[4] LIDÉN T， KALINOWSKI T， WATERER H. Resource Considerations for Integrated Planning of Railway Traffic and Maintenance Windows[J]. Journal of Rail Transport Planning & Management，2018，8(1)：1-15.

[5] ZHANG Q， LUSBY R M， SHANG P，et al. Simultaneously Re-Optimizing Timetables and Platform Schedules under Planned Track Maintenance for a High Speed Railway Network[J]. Transportation Research Part C：Emerging Technologies，2020，121：102823.

[6] ZHANG Q， LUSBY R M， SHANG P，et al. A Heuristic Approach to Integrate Train Timetabling，Platforming，and Railway Network Maintenance Scheduling Decisions[J]. Transportation Research Part B：Methodological，2022，158：210-238.

[7] 兰泽康，何世伟，黎浩东，等. 考虑维修天窗和到发线数量的复线铁路列车运行图优化[J]. 北京交通大学学报，2018，42(3)：30-36.

[8] LAN Zekang， HE Shiwei， LI Haodong，et al. Optimization for Double-Track Railway Train Timetabling Considering the Maintenance Skylight and the Number of Arrival-Departure Tracks[J]. Journal of Beijing Jiaotong University，2018，42(3)：30-36.

[9] 穆　策，孟令云，廖正文，等. 维修天窗与列车运行图一体化编制模型[J]. 铁道科学与工程学报，2018，15(8)：2155-2162.

[10] MU Ce， MENG Lingyun， LIAO Zhengwen，et al. Integrated Optimization Model on Maintenance Time Window and Train Timetabling[J]. Journal of Railway Science and Engineering，2018，15(8)：2155-2162.

[11] D’ARIANO A， MENG L Y， CENTULIO G，et al. Integrated Stochastic Optimization Approaches for Tactical Scheduling of Trains and Railway Infrastructure Maintenance[J]. Computers & Industrial Engineering，2019，127：1315-1335.

[12] LUAN X J， MIAO J R， MENG L Y，et al. Integrated Optimization on Train Scheduling and Preventive Maintenance Time Slots Planning[J]. Transportation Research Part C：Emerging Technologies，2017，80：329-359.

[13] 刘　敏，朱克非，李　博. 高速铁路夜行列车开行和天窗设置优化研究[J]. 铁道运输与经济，2015，37(11)：22-25，88.

[14] LIU Min， ZHU Kefei， LI Bo. Study on Optimization of Night Train Operation and Maintenance Window Configuration of High Speed Railway[J]. Railway Transport and Economy，2015，37(11)：22-25，88.

[15] 杨　奎，彭其渊，鲁工圆，等. 高速铁路天窗设置与夜间列车运行协调优化技术[J]. 铁道学报，2015，37(4)：1-7.

[16] YANG Kui， PENG Qiyuan， LU Gongyuan，et al. Co-Optimization between Maintenance Curfew and Overnight Train Plan in High Speed Railway[J]. Journal of the China Railway

[17] Society，2015，37(4)：1-7.

[18] 徐长安，倪少权，陈钉均. 基于两阶段算法的运行图与天窗协同优化[J]. 西南交通大学学报，2020，55(4)：882-888.

[19] XU Chang’an， NI Shaoquan， CHEN Dingjun. Collaborative Optimization for Timetable and Maintenance Window Based on Two-Stage Algorithm[J]. Journal of Southwest Jiaotong University，2020，55(4)：882-888.

[20] 徐长安，李晟东，陈钉均，等. 列车运行图天窗分段与衔接优化技术研究[J]. 计算机仿真，2021，38(3)：68-72，102.

[21] XU Chang’an， LI Shengdong， CHEN Dingjun，et al. Segmentation and Connection Optimization Technique for Maintenance Window in the Train Timetable[J]. Computer Simulation，2021，38(3)：68-72，102.

[22] 王宇强，魏玉光，林　枫. 成网条件下基于运行图铺画的高速铁路通过能力计算研究[J]. 铁道学报，2022，44(10)：1-8.

[23] WANG Yuqiang， WEI Yuguang， LIN Feng. Research on Capacity Calculation Based on Train Timetable Generating in High Speed Railway Network[J]. Journal of the China Railway Society，2022，44(10)：1-8.

[24] 赵　鹏. 双线电气化铁路综合维修“天窗”开设相关问题研究[D]. 成都：西南交通大学，2008.

[25] 姜良杰，袁晓军. 陕北地区铁路煤炭运输需求分析及预测[J]. 铁道货运，2024，42(10)：39-48.

[26] JIANG Liangjie， YUAN Xiaojun. Analysis and Forecast of Railway Coal Transportation Demand in Northern Shaanxi Region[J]. Railway Freight Transport，2024，42(10)：39-48.

[27] 宋浚哲，刘　畅. 联网、补网、强链背景下货车车流径路优化方案及效益研究[J]. 铁道货运，2024，42(10)：23-32.

[28] SONG Junzhe， LIU Chang. Optimization Plan and Economic Benefit of Wagon Routes Against a Background of China Railway Network Capacity Enhancement Plan[J]. Railway Freight Transport，2024，42(10)：23-32.

基金资助

中国国家铁路集团有限公司科技研究开发计划课题(P2024X002)

中国铁道科学研究院集团有限公司科研项目(2023YJ160)