列车运行图天窗分段与衔接优化技术研究

徐长安，李晟东，陈钉均，3，倪少权，3

(1.西南交通大学交通运输与物流学院，四川 成都 610031；2.西南交通大学全国铁路列车运行图编制研发培训中心，四川 成都 610031；3.西南交通大学综合交通运输智能化国家地方联合工程实验室，四川 成都 610031)

1 引言

天窗是列车运行图中不铺画列车运行线或调整、抽减列车运行线为施工和维修作业预留的时间[1]。主要用于对现有铁路设备进行有计划的维修和技术改造，是协调列车运行与线路施工维修矛盾的有效措施，对保障铁路运输安全至关重要。

我国铁路具有高铁与既有线贯通成网、既有线客货混跑、运能与运量矛盾突出等特点，天窗设置的困难性较其它国家更加突出，根据现行的中国铁路总公司2014年颁布的《列车运行图编制规则》，我国高速铁路设置全线垂直矩形天窗，既有线单线铁路采用分段矩形天窗，既有双线铁路一般采用V型或者X型天窗，天窗要求尽量设置在白天，以方便维修施工。整体而言，我国高铁天窗设置比较固定，而既有线天窗设置具有影响因素复杂、计划性强、局部变化大等特点，是一个十分复杂的组合优化过程。

既有线天窗设置的一个关键问题是如何进行线路天窗的分段和合理衔接，使得天窗设置对铁路能力的影响降到最低。由于天窗分段和衔接的可选方案很多，灵活性比较大。如何立足整条线路，统筹考虑路网因素，对线路天窗区段进行划分，并以合适的时间、倾斜角度进行衔接组合，对优化运行图结构，释放铁路能力具有重要意义[1]。

从实践层面看，我国铁路列车运行图天窗设置采用计算机辅助系统，天窗分段与衔接主要依赖于编图人员的经验判断。这种基于人工经验的天窗设置模式在铁路能力充裕的情况下尚能基本满足铁路生产需要，但当铁路能力紧张时，人机交互调整的工作量仍然很大。

从理论研究看，国内外关于天窗分段与衔接的研究很少，大多数研究集中在运行图既定情形下天窗设置优化[2]，天窗开设时段优化[3]，天窗与开行方案协同优化[4]等几个方面，仅有少量文献部分涉及了天窗分段与衔接，文献[5]运用情景分析法构建了天窗设置模型，能够根据成本收益比选出最优天窗分段。文献[6]提出了根据车站等级、客流区段以及是否衔接站进行天窗分段的思路。文献[7]考虑了路网条件下不同线路之间天窗方案的衔接匹配问题。总体而言，现有文献通常将天窗分段与天窗衔接作为两个相对独立的问题进行研究，且在研究过程中只关注天窗设置对列车运行的影响，未充分考虑由于天窗分段与衔接产生的天窗错位对车站能力的影响。

鉴于此，本文从天窗设置对列车运行方案的影响以及不同天窗分段时间配合两个方面考虑，提出了既有线列车运行图天窗分段与衔接优化模型，并设计并行蚁群算法进行求解。最后通过实例对模型算法的有效性进行了验证。

2 问题分析与描述

2.1 问题分析

天窗单元是实现维修施工作业的最小基本单位，既有电气化铁路一般以供电臂停电单元作为为天窗单元，非电气化铁路一般以施工区间为天窗单元。天窗分段是为了兼顾施工维修作业和运输工作的连续性需求，对天窗单元进行的合理组合。天窗分段可以用车站集合进行表示，出现在相邻两个天窗分段中的车站称为相邻天窗分段的分界站。天窗分段会导致分界站出现两个以上的天窗，形成天窗错位，影响车站和线路能力利用。而天窗衔接正是为了协调不同天窗分段在分界站的起始时间，以减少天窗错位对车站和线路能力的影响。可以说，天窗分段主要解决“在哪儿分”的问题，是从空间维度对天窗单元进行组合。而天窗衔接主要解决“在哪儿接”的问题，是研究横向时间带上不同天窗分段的配合。本质上讲，天窗分段与衔接研究是一个二维时空组合优化问题。

2.2 符合说明

3 问题建模

3.1 模型假设

本文研究基于以下前提：

1)旅客列车运行方案已知；

2)天窗时间不能横向分割；

3)天窗分段分界站的到发线数量充足；

4)时间以分钟为单位，取值范围为[0，1440)。

3.2 目标函数

天窗分段与衔接优化的主要目有两个：一是减小天窗设置对列车运行的影响，二是尽可能缩短相邻天窗分段的错位时间。

本文定义如式(1)所示的示性函数来表征天窗设置对列车运行的影响，∀di∈u，如果天窗时间与列车运行时间有交集，则称天窗分段对该列车运行有影响，反之，则称天窗分段对该列车运行无影响。

R(Tp，s，Mi)=1|Tp，s∩Mi≠∅

R(Tp，s，Mi)=0|Tp，s∩Mi=∅

(1)

则天窗分段方案u对列车运行的影响可表示为

(2)

图1 天窗错位时间

(3)

式(3)中，δ(s)表示分界站s可接受的天窗错位时间阈值，则天窗分段方案u下任意两个相邻天窗分段错位时间可表示为

综上，本文的两个目标函数可表示为

min{Z1(u，v)|∀u∈U，v∈V}

(4)

min{Z2(u，v)|∀u∈U，v∈V}

(5)

式(4)与式(5)表示遍历所有可能的天窗分段及衔接方案组合，取其中对列车运行影响最小以及天窗分段错位时间最短的方案即为最佳天窗分段及衔接方案。

3.3 约束条件

1)天窗分段完整性约束

天窗分段要求涵盖线路上所有车站，并且除了分界站，其它车站只能属于一个天窗分段。

{d1/sn1}∪{d2/sn2}∪…∪{de-1/sne-1}∪{de}=L

(6)

{d1/sn1}∩{d2/sn2}∩…∩{de-1/sne-1}∩{de}=∅

(7)

2)天窗分段时间范围约束

任意车站天窗开始时间与持续时间必须位于允许时间范围内，并且分界站总的天窗占用时间不能超过该站总的天窗可用时间范围。

(8)

|Mi|+|Mi+1|-(|Mi+1-Mi|)≤Ts

(9)

3)遍历性约束

所有可能的天窗分段方案以及不同天窗分段的衔接方案都应该遍历搜索一遍。

(10)

(11)

4)变量取值约束

R(Tp，s，Mi)∈{0，1}

(12)

φu，φv∈{0，1}

(13)

4 算法设计

4.1 双目标转化

上述模型是一个双目标优化问题，采用线性加权法[8]将双目标转换为单目标进行求解。引进目标值权重系数ω1、ω2，且ω1+ω2=1，将上述模型转化成单目标模型问题：

(14)

4.2 变量降维

对于一个由n个车站组成的线路而言，天窗分段与衔接问题的复杂度为O(((1440-Δt)/σ)·2n-2)。当车站数量较多时，问题的规模会以指数形式增长，造成组合爆炸现象。因此，有必要通过变量降维来降低问题求解的复杂度。

根据天窗分段与衔接问题的复杂度计算表达式，可以从两个方面对该问题进行降维处理。一是减少车站数量n；二是降低搜索粒度σ。基于历史列车运行图资料分析可知，天窗分段往往发生在一些大站和衔接站，因此，可以根据线路车站的到发运量，停站列数，线路衔接情况等属性，判定可能发生天窗分段的备选车站集，然后在备选车站集中进行迭代搜索，这样可以大大降低搜索空间，提高搜索效率。另外，根据运行图铺画要求，可以适当增大横向搜索的时间粒度，减少搜索次数。

4.3 并行蚁群搜索算法

考虑到天窗分段与衔接问题的复杂性，一种可行的思路是采用分治思想，将原问题分解为多个规模较小的子问题，各个子问题可使用同一种算法求解，然后再做综合优化。并行蚁群算法是体现“分治思想”的智能优化方法之一，本文采用并行蚁群算法进行求解，其关键步骤包括转移概率计算、信息素更新和并行策略选取。

1)转移概率计算

(15)

式(15)中，τij(t)为信息素强度；ηij为启发式信息，是指天窗分段di选择衔接天窗分段开始时间tj的启发式期望度。0≤β≤1表示τij(t)和ηij在构造解时的作用程度。

2)信息素更新

信息素更新是蚁群算法的核心。本文采用最小最大蚂蚁系统的思想[8]，只有迭代最优蚂蚁才被允许释放信息素，为了避免迭代停滞，将信息素的取值限制在区间[τmin，τmax]，其中τmax和τmin可根据文献[9]中的方法确定。蚂蚁在完成一次循环后，每条边上的信息素浓度将依据下式更新

τij(t+1)=ρτij(t)+Δτij

(16)

式(16)中，ρ为信息素的挥发系数ρ<1，且；t为迭代次数；Δτij为本次迭代后信息素增量。计算出τij(t+1)后，还需判断其值是否在区间[τmin，τmax]，因此，本文算法信息素更新原则如下

(17)

3)并行策略

在蚁群算法并行化时，选择何种并行策略是由问题规模及运行环境决定的。本文选择粗粒度并行策略[10]，该种策略将原蚁群划分成若干个子群，每个子蚁群相互独立地并发执行串行蚁群算法，经过指定次数的迭代后，各子蚁群间会交换若干信息，丰富各子蚁群的多样性，防止未成熟收敛的发生。粗粒度并行策略的过程如图2所示。

图2 粗粒度并行策略

4.4 算法流程

应用并行蚁群算法进行天窗分段与衔接问题求解的算法描述如下：

Step1：初始化参数。确定蚂蚁总数，子群个数以及各子群的蚂蚁数目，并为每个蚂蚁选择一个初始的解构成，设定各子群内的初始信息素浓度为τij(0)，计算信息素的上下界τmin，τmax。将循环次数设定为0。

Step2：状态转移规则。每个蚂蚁在其所在子群中使用伪随机比例原则选择下一个解的构成，并根据式(15)计算其转移概率。

Step3：局部更新规则。每个蚂蚁在构造一个解的过程中，根据局部更新规则更新解的各构成部分信息素浓度。

Step4：目标函数值评价。计算每个子群内各个蚂蚁所得到的目标函数值，并比较其大小。

Step5：全局更新规则。在各个子群中全局更新只是对每次循环中得到最优解的蚂蚁，全局更新依据式(16)—(17)进行。

Step6：子群间信息素交流。将更新后的信息素同时传送给其它q-1个子群。

Step7：终止条件判定。如果满足终止条件，则输出全局最优解并结束程序；否则，转向step2继续执行。

图3为并行蚁群算法流程图，图中，I为迭代次数，R为迭代次数上限。

图3 并行蚁群算法流程图

5 算例分析

以达万铁路为研究对象，验证本文提出模型算法的有效性。达万铁路为单线铁路，全长157km，共有18个车站，依次编号为1—18。根据路局天窗设置原则，需预留不少于90min的分段矩形天窗。综合考虑车站等级、线路衔接、停站方案等因素，选定万州，万州西，三正，关龙桥，梁平，文化，葫芦潭，亭子和达州9个车站作为可能的天窗分界站。根据达万铁路2018年列车开行方案，该线共运行22列各等级旅客列车。各类列车的权重系数见表1。

表1 不同种类列车权重值

利用MATLAB 7.12.0 编程实现并行蚁群算法，将蚁群平均分为4组，算法中蚂蚁个数M=40，每个群组初始信息浓度设为τij(0)=0.01，ρ=0.8，β=0.5，时间粒度σ=5。算法迭代过程中，可行解收敛情况见图4，可以看出，算法迭代到150次左右开始收敛，得到全局最优函数转化值为143，耗时25s。达万线天窗分段与衔接最优方案见表2。

图4 算法收敛曲线图

为进一步说明本文所提方法的有效性，将本文结果与2018年达万线天窗设置情况(人工经验编制)进行对比，本文方法将达万线的天窗划分为5个天窗分段，分别为万州—三正、三正—梁平、梁平—开江、开江—亭子、亭子-达州，总的天窗错位时间为120min。人工设置的结果共有8个天窗分段，总的天窗错位时间为250min。可以看出，相较于人工经验设置的结果，本文方法能够有效减少分界站的天窗错位时间，而且可以在较短时间内求得全局满意解，能够满足计划编制的实时性要求。

表2 天窗分段与衔接结果

6 结束语

我国铁路贯通成网运营条件下，大量长途跨线列车对天窗设置的制约十分明显，合理进行天窗分段与衔接对优化列车运行线时空布局，提高铁路能力利用至关重要。本文基于列车开行方案给定情形，研究了既有线天窗分段与衔接优化问题，并设计了并行蚁群算法进行求解，最后以达万铁路实际数据为例验证了本文提出模型及算法的有效性。本文研究未考虑货物列车对天窗分段与衔接的影响，在今后研究中将继续对这一问题进行深化。