基于列车到发分布的高速铁路车站到发线运用优化

任禹谋，张 琦，袁志明，王 涛，丁舒忻，李 智

(1.中国铁道科学研究院 研究生部，北京 100081；2.中国铁道科学研究院集团有限公司 通信信号研究所，北京 100081)

现有铁路运输体系中，大型高速铁路车站作业交叉干扰是限制列车运行图能力的重要因素，其中到发线资源对此尤为敏感。编制高水平到发线运用计划能够满足列车正点出发和车站作业不冲突的要求，提高设备资源的利用率和抗干扰性，为车站调度员提供决策支持，具有重要的实际意义。

到发线运用优化问题是一个典型的半结构化问题，模型构建繁琐，且与到发线相连的咽喉区进路结构错综复杂，进一步加剧了问题的求解难度[1]。Cacchiani等[2]从列车到发时间和到发线选择两个角度详细阐述车站作业问题，并为之提供通用模型和解决方案。Cardillo等[3]首次提出采用增量约束着色图模型解决列车到发时间不能改变的车站径路使用问题。Sels等[4]为了解决无法排列全部列车进路的情况，在构建的到发线模型中提出了虚拟站台的概念并应用于比利时铁路系统，最大限度地增加了可以在无冲突站台通行的列车数量。Petering等[5]构建了列车时刻表和到发线作业组合优化的混合整数规划模型，并采用CPLEX求解器求解实际问题进行验证。近年，国内学者更多地考虑现场因素，并将启发式算法应用于求解过程，降低问题的求解难度[6]。Zhang等[7]对车站到发线时空资源进行微观描述，并建立数学规划模型后用模拟退火算法进行求解。赵鹏等[8]将到发线和咽喉区进路作为整体问题综合研究，完善了到发线运用模型。鲁工圆等[9]以进路冲突图为基础构建赋时有色Petri网仿真模型解决车站作业计划建模过程复杂的问题，有效提高了建模效率。也有部分学者从客运服务质量[10]、车站作业计划鲁棒性[11]、到发线利用均衡程度[12-13]等角度出发，详细分析车站的优化方向以解决到发线运用问题。

既有研究在解决到发线运用优化问题时，通常采用加权的方式将多个优化目标合并为单个优化目标求解，并未以多目标的视角考虑不同方案的适用性，并且在现实中几乎不可能精确测定各优化目标的先验权重。因此，到发线运用优化问题的解应该是一组从不同角度计算分析得出的Pareto解，供调度员决策备用。同时既有研究在目标制定过程中，往往忽略了列车到发分布特征的影响，采用固定化的优化目标，这样难以有针对性地解决车站通过能力与鲁棒性之间存在的矛盾。因此，在满足列车安全运行约束的条件下，针对列车到发分布特征，提出一种基于分时段多目标的到发线运用整数规划模型，并设计改进的NSGA-Ⅱ算法求解，为车站列车调度工作提供策略支持。

1 问题描述与建模

1.1 问题描述

到发线运用优化问题可以描述为:对于即将进站的列车集合和车站到发线集合，已知列车的图定到发时间和车站站场布置，在满足多个作业约束的情况下，求出一个使问题所有目标均尽可能为优的合理到发线分配方案，以达到降低列车晚点传播风险、提高车站作业能力和安全运营的目的。高速铁路车站作业过程主要包含出段作业、入段作业、接车作业、发车作业、通过作业和折返作业等，每项作业对应由列车在站内走行进路完成，这些进路又可以分为接车进路和发车进路。在编制到发线运用计划时，根据列车到发时间、出入段时间和其他作业时间标准，有序安排到发线的占用，减少空费时间，并预留一定的时间裕度，便于突发事件发生时计划的调整[14]。同时合理利用咽喉区的列车进路，避免作业间的冲突，保证车站的作业效率和安全性。

1.2 模型假设

1)假设列车到发时间和车站站场布置均为已知条件；

2)假设车站作业过程完成时间均严格参照作业时间标准；

3)假设列车在接发车时只选择基本进路，且所有到发线均能停靠列车；

4)不考虑列车进路的分段解锁，只采用一次性解锁；

5)假设折返列车不变更到发线，并采用顺接反发的进出站方式。

1.3 符号定义

1)集合。I为到站列车集合，i和h为列车的序号，n为到站列车的总数；J为车站到发线集合，j和l为到发线的序号，m为到发线的总数；Rj为连接到发线j的接车进路集合，rjs为集合中的接车进路，s为集合中接车进路的序号，a为集合中包含的接车进路总数；Pj为连接到发线j的发车进路集合，pjg为集合中的发车进路，g为集合中发车进路的序号，d为集合中包含的发车进路总数。

3)决策变量。xij为0-1决策变量，当xij=1时表示列车i占用到发线j，否则xij=0；yijs为0-1决策变量，当yijs=1时表示列车i占用到发线j选择第s条接车进路，否则yijs=0；zijg为0-1决策变量，当zijg=1时表示列车i占用到发线j选择第g条发车进路，否则zijg=0。

1.4 到发线运用分时段优化模型构建

高速铁路车站接发列车的分布特征较为明显，分为高峰时段和平峰时段，从定量的角度可以界定两类时段对应的列车密集程度，进而制定差异化的优化目标。定义车站接发列车的分布特征参数为θ，设车站一天中单个小时最大接发列车数为M,则高峰和平峰时段对应的接发列车数量范围分别为[0,θM]和(θM,M]。平峰时段，在保证到发线作业鲁棒性的同时，仍需考虑到发线固定作业方式等多方面影响因素；高峰时段，不仅要满足到发线作业鲁棒性的要求，更要提升到发线的利用效率。对于到发线运用优化问题的鲁棒性[15]，首先引入“冲突系数”的概念，即相邻两列车占用相同到发线时间间隔的倒数，用列车总冲突系数描述鲁棒性；到发线利用效率可通过到发线占用时间方差衡量；到发线固定作业方式和乘客便捷乘降等影响因素折算成到发线占用费用来表征。到站列车分布特征与优化目标的关系见图1。

图1 列车分布特征与优化目标关系Fig.1 Relation between train distribution characteristics and optimization objectives

模型为：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

uskρih(yijs+yhlk)≤1,∀i,h∈I;j,l∈J;s∈Rj;k∈Rl

(10)

ugqρih(zijg+zhlq)≤1,∀i,h∈I;j,l∈J;g∈Pj;q∈Pl

(11)

usqρih(yijs+zhlq)≤1,∀i,h∈I;j,l∈J;s∈Rj;q∈Pl

(12)

(13)

xij,yijs,zijg∈{0,1}

(14)

式(1)针对高峰时段到站列车，表示最小化到发线占用时间方差；式(2)针对所有时段的到站列车，表示列车总冲突系数；式(3)针对平峰时段到站列车，表示最小化到发线占用费用；式(4)为到发线指派的唯一性约束；式(5)和式(6)为接发车进路指派的唯一性约束；式(7)和式(8)为到发线和咽喉区进路的连通性约束；式(9)为同一到发线的占用时间间隔约束；式(10)～(12)为咽喉区进路冲突约束，分别表示接车进路之间、发车进路之间以及接发车进路之间在时间和空间上不能存在共同的交集；式(13)为列车折返约束。

2 算法设计

到发线运用问题是典型的多目标约束优化问题，采用进化多目标优化算法可以求出一组Pareto最优解集供决策者针对不同的条件制定对应的方案。进化算法中的NSGA-Ⅱ可以有效解决多目标优化问题，但其在进行支配排序时仅通过适应度函数选择，并未考虑解的可行性，如果在进化全过程周期中加入约束限制则会导致解的搜索区域急剧减小，最后陷入局部最优[16]。因此在进化的后期加入约束准则改进NSGA-Ⅱ算法中的个体选择策略，既能在进化前期保持种群的多样性，又能在进化后期提高种群的收敛性。基本步骤如下：

Step1编码。采用自然数编码方式，染色体长度等于研究时段内到站列车的数目，基因位置代表列车到站的顺序，基因所对应内容则为到发线编号。

Step2种群初始化。随机生成一组规模为N的初始种群作为初代父代种群E(s)，s=0，s为迭代次数。

Step3非支配排序。针对已经生成的种群，计算每个个体对应不同目标函数的值，然后根据个体间是否存在支配关系对种群内所有个体进行分层，层级越小的解越优秀，再对同一层内的解计算拥挤距离，计算公式如下

(15)

Step4约束准则排序。引入约束违反度[17]概念，并根据约束支配原则对种群内个体进行排序，有效改善NSGA-Ⅱ进化后期可行解不足的问题。定义如果以下任何一个条件成立，则种群中任意两个解比较时解1约束支配解2。

1)解1为可行解，解2为不可行解；

2)解1和解2都是不可行解，但解1的约束违反度小；

3)解1和解2都为可行解，且解1优于解2，使用Step 3中拥挤距离的计算规则来解决。

约束违反度值计算公式如下

(16)

式中：G(X)为约束违反度，X为决策向量，ge(X)为模型中的10个约束条件。当ge(X)≤0，〈ge(X)〉返回其绝对值，否则返回0。由此可知当X为可行解时约束违反度值为0，当X为不可行解时，约束违反度值大于0。

Step5遗传操作。将父代种群E(s)执行传统遗传算法中的交叉和变异操作，生成一个规模为N的子代种群F(s)。

3 算例分析

3.1 数据准备

以京沪高速铁路某车站为例进行仿真验证。车站从3个方向接发列车，并与一个动车所相连通，站型图见图2，站内共有10个到发线，48条基本接发车进路，8条入段进路和8条出段进路，车站作业时间标准见表1。对该站某日全天接发列车数量进行统计，单小时最大接发车数量M为20，到站列车的分布特征参数θ取0.85，则平峰和高峰时段对应的接发列车数量范围分别为[0,17]和(17,20]。综合考虑方便旅客乘降和到发线固定作业方式的影响，制定到发线占用费用矩阵，见表2。选取16:00～18:00内的进站列车作为研究对象，16:00～17:00接发列车16列，处于平峰时段，17:00～18:00接发列车20列，处于高峰时段，取种群大小N=200，最大进化代数Smax=300，交叉概率为0.9，变异概率为0.2，分别对两种列车分布状态下的到发线运用问题进行建模计算。

表1 作业时间标准Tab.1 Operating time standard min

表2 到发线占用费用矩阵Tab.2 Occupancy cost matrix of train platform

图2 某高速铁路车站平面站型Fig.2 Layout of a high-speed railway station

3.2 仿真结果验证

16:00～17:00平峰时段，计算结果在进化至220代时逐渐收敛于Pareto前沿，共得到5组解，方案见表3。列车总冲突系数与到发线占用费用见图3。可以看出，方案之间均不存在支配关系，且列车总冲突系数的减少需要以增加到发线占用费用为代价。全部可行方案中列车总冲突系数最低至0.007 4，到发线占用费用最小为44。该时段到站列车数量未达峰值，从客运服务角度来看，优先满足旅客乘降便捷和客运员固定到发线接发列车，则选择方案2，对比原计划方案，总冲突系数降低了12.62%，到发线占用费用降低了16.98%；从车站调度安全角度来看，优先提升到发线作业鲁棒性，选择方案1，进一步考虑同一到发线相邻列车最小间隔时间可能成为限制计划强壮性的瓶颈因素，验证方案1的最小间隔时间为11 min，该值同样是5个方案中的最大值，符合要求，对比原计划方案，总冲突系数降低了33.82%，到发线占用费用降低了5.66%。

图3 16:00～17:00到发线运用方案的Pareto解分布Fig.3 Pareto front distribution in train platform utilization scheme during 16:00—17:00

表3 16:00～17:00平峰时段到发线分配方案Tab.3 Train platform utilization scheme during normal peak period 16:00—17:00

17:00～18:00高峰时段，仿真计算共得到4组Pareto解，种群进化至250代时趋于收敛，限于篇幅，只展示各方案中列车分配不同的到发线，见表4。各方案目标函数对比结果见图4。与平峰时段分配方案对比发现，4个方案中只有40%列车分配的到发线有区别，说明到站列车密集，满足约束的可行性方案不多，同时各方案的最小间隔时间均为3 min，且该瓶颈时间位于列车19和24之间。方案1到发线使用效率最高，到发线占用时间方差104.85，比原计划方案降低48.57%，总冲突系数也降低了18.71%，明显提高了车站设备的利用效率；方案4在总冲突系数比原计划方案降低了29.81%的同时，到发线使用效率基本与方案1持平，既保证了车站的通过效率，又提高了到发线运用计划的鲁棒性。

图4 17:00～18:00到发线运用方案的Pareto解分布Fig.4 Pareto front distribution in train platform utilization scheme during 17:00—18:00

表4 17:00～18:00高峰时段到发线分配方案(部分)Tab.4 Train platform utilization scheme during rush hour 17:00—18:00 (part)

与此同时，为了研究分时段优化与传统优化方法的区别，本文对全部研究时间段内36列列车的三目标整数规划模型进行计算生成了整体优化方案，从解的Pareto前沿中均匀选取与分时段优化方案等量的解进行对比，见图5，方法1和方法2分别代表本文方法和整体优化方法。可以看出，平峰时段整体优化和分时段优化方法在到发线占用费用方面比较接近，但列车总冲突系数方面却明显降低，两种方法同一到发线相邻列车间隔时间的最小差值为19 min，说明在车站作业不紧张时分时段优化方案能够在保证到发线合理选择的同时有效提高到发线作业的鲁棒性；高峰时段，整体优化方法中到发线占用时间方差和列车总冲突系数均有较大波动，且两个目标函数值变化趋势相同，分时段优化方法则情况相反，分析原因可知，整体优化主要考虑了到发线空间上的运用均衡性，分时段优化则进一步将分段时间内的到发线占用时间均匀分布，使得列车总冲突系数也可以保持在较低水平。当突发事件发生,导致列车晚点时，同一到发线列车间的时间间隔越长表示吸收晚点时间的能力越强，说明分时段优化方法能够增强车站的抗干扰能力，具有一定的优越性。

图5 全部研究时段整体和分时段优化方法结果对比Fig.5 Comparison of results of overall and segment optimization methods throughout the period of study

为检验改进算法的求解效率和质量，以高峰时段2 h车站数据为例，将改进算法与文献[6]中标准NSGA-Ⅱ算法进行对比实验，结果见表5。实验结果表明本文的改进NSGA-Ⅱ算法可以获得更多的可行解，目标值有一定程度的优化，同时改进算法的求解时间降低了48.17%。改进后NSGA-Ⅱ算法在解的质量和求解效率方面均有提升，说明该算法具有良好的适应性和有效性。

表5 本文算法与对比算法的比较结果Tab.5 Comparison of results of the proposed algorithm and the comparison algorithm

4 结 论

在考虑列车到发分布特征，分时段差异化制定目标的基础上，构建了一种到发线运用多目标优化模型，并设计了包含约束处理的改进NSGA-Ⅱ算法进行求解。与整体优化方法相比，分时段优化方法从车站资源利用的角度增加了目标的针对性和多样性，引入列车总冲突系数加强了到发线运用计划的抗干扰性。实验结果表明，相比整体优化方法，分时段优化方法的目标值有大幅降低，说明该方法有更好的鲁棒性和有效性，同时本文算法在解的质量和求解效率方面比NSGA-Ⅱ算法均有所提升，说明该模型和算法可以适用于不同时段车站到发线运用计划制定过程，对提升车站的抗干扰能力和客运服务质量具有重要意义。