基于约束规划方法的高速铁路调整优化模型

曾 壹，张 琦，陈 峰

(1.中国铁道科学研究院集团有限公司 研究生部，北京 100081；2.中国铁道科学研究院集团有限公司 通信信号研究所，北京 100081；3.国家铁路智能运输系统工程技术研究中心，北京 100081)

运行图是列车调度员使用的铁路运输综合计划，是行车组织工作的基础。高速铁路列车运行调整属于大规模组合优化问题，在有限时间内求出最优解是问题的难点。国内外学者在调整理论建模方面开展了大量研究实验，然而数学规划[1-2]和图论[3-4]方法都难以达到调度支持系统实时计算要求。为提高计算效率，本文将列车调整计划的组合优化问题转化为多个宏观事件节点在运行图间隔时间规定下求出可行解的约束满足问题[5]CSP(Constraint Satisfaction Problem)求解。

约束规划方法是求解约束满足问题的高速计算方法，特点是使用约束传递机制在约束条件划定的解空间内迭代搜索并调整变量取值。在变量无法求出可行解时，算法将不进行约束传递，而是使用试错回退机制重新计算。列车计划调整问题中的约束规划方法根据运行图间隔时间条件[6-8]或线路设备占用条件[9-10]定义检查方法与解空间。当扰动发生后，约束传递算法迭代检查被扰动事件并且只改变变量取值，而列车到开事件关系的调整由试错回退机制根据列车越行[6]、分解[7]等调度措施的运行图样式确定，从而有效限制了单次调整需要考虑的变量个数和取值范围。约束规划方法在列车计划调整问题中作为辅助方法提供混合整数规划模型的初始解[8]，或应用于宏观[6-7]与微观[9-10]规模的扰动管理，达到降低计算耗时的效果。

本文在学习上述方法特性的基础上，设计一种列车调整计划的约束规划优化模型。模型将调整问题转化为CSP问题，通过制约传播方法检查运行图间隔时间、股道占用条件并触发使用线路缓冲时间或越行策略改变运行计划，调整过程可使用人机交互参数配置。模型与同等约束条件下的整数规划模型进行对比，验证了在多种干扰条件下的晚点总时长减少与计算效率提高。

1 约束满足问题建模与约束规划算法设计

1.1 CSP问题构建与间隔时间条件

约束满足问题是探索满足有限个制约条件限制的多变量组合可行解的数学问题[5]，具备以下特征：

(1)问题描述可等效为多个约束条件的集合。

(2)所有约束条件使用等式、不等式、逻辑表达式的形式表述。

(3)所有变量均具备特定的取值范围。

阶段计划受到运行图间隔时间条件的约束并具有一定的时间范围，能够相应转化为符合以下特征的CSP问题：

(1)问题的约束条件为多个运行图间隔时间条件的集合。

(2)所有约束条件使用不等式表述。

(3)所有变量的时间取值来自一定时间范围的阶段计划。

表1 运行图间隔时间条件的分类

1.2 约束传递方法与间隔条件整合

约束传递是约束规划算法判定变量值是否实现约束满足并修正不符合制约关系式要求变量值的子方法。方法最大的特点是通过修正变量值触发下一个关联变量检查，从而将所有潜在不满足条件设置变量的检查流程转化为方法自身的内部触发与迭代流程。约束传递的举例说明如图 1所示。

图1 列车i出发晚点的制约传播

流程从列车i在车站1出发的事件发生晚点开始，晚点将触发约束传递方法检查出发事件与i车到达车站2的时间之间是否满足最小区间运行时间Tt(i,1)，如果约束条件不满足，约束传递方法将调整i车在车站2的到达时间。由于到达事件时刻的变动，该变动又将触发约束传递方法检查i车在车站2的到达事件。如果该事件与列车i*在车站2的到达事件不满足最小同向到达间隔时间Ta(i,i*,2)，约束传递方法又将调整列车i*在车站2的到达时间，进一步触发其他相关事件的约束传递方法检查。

( 1 )

表 1中最小停车时间Ts(i,j)和技术作业标准时间To(i,j)的事件对关系一致，两个条件只要取最大的约束值代入式( 1 )并达成约束满足，即可判定较小约束值的条件也达到约束满足。另外，车站会车约束Tm(i,i*,j)可被分解为最小不同时到达间隔时间Da(i,i*,j)与最小停车时间Ts(i,j)的组合，Tm(i,i*,j)与Da(i,i*,j)同理也只需代入最大约束值即可达成两者的约束满足判定。上述条件可表述为约束传递范式的极大加代数条件整合结果如式( 2 )所示。

( 2 )

此分类方式不仅降低了大规模计划调整问题的计算量，还表明同站间隔类约束条件除终到站最小折返时间约束Tr(i,i*,j)与股道最小发到间隔Le(i,i*,j)外，均为同类事件之间的间隔关系。

1.3 试错回退机制与股道冲突建模

试错回退机制是由特定解或解空间不存在作为条件触发可行解样式的约束规划算法子方法。在运行图间隔时间条件的CSP问题构建中，试错回退机制提供了列车到开事件关系变化的备选调度方案。以越行方案为例，试错回退机制的操作可描述为由线路条件触发并确定图 2所示列车事件时间序列的过程。

图2 回退检索与列车越行时序

图 2中，列车i在车站2通过到达事件最小同向到达时间约束Ta(i,i*,j)的约束传递判定项，触发回退检索并在车站1停车等待列车i出发。依据式( 2 )条件得出列车i序列后移在车站1引起的事件关系变动如图 3所示。

图3 回退检索引起的出发事件关系变动

( 3 )

式中：SL、SU分别为影响区域下界、上界的搜索函数。文献[6，13]提出的搜索方法将回退检索的影响范围固定为同站30 min内的列车事件，本文在该方法的基础上改进并采用同站间隔关系的运行图间隔时间条件定义受影响的事件范围搜索函数为

( 4 )

越行操作未增删列车运行事件，但局部改变了列车到发关系。设iU、iL为图 3上下界事件的车次号，则保持CSP问题在事件关系变更后间隔时间条件值正确调用的出发事件同站间隔关系参数更新方法可陈述为替换与赋值关系。

( 5 )

由于高铁双线区段不需考虑会车条件，折返条件只在列车终到站应用，出发事件的同站间隔关系变更只需更新最小同向出发间隔时间Td(i,i*,j)。列车i在其他车站出发事件后移引起的事件关系变动与间隔关系参数变更情况可分别参考图 3、式( 5 )。

同样的，越行操作引起的列车i在其他车站到达事件之间的关系变动可整理为图 4，事件关系变更后的到达时间同站间隔关系更新方法可参考式( 5 )。

图4 回退检索引起的到达事件关系变动

( 6 )

( 7 )

函数Lc(j,m)检测到股道计划冲突后，约束传递方法的调整规则如下：

(1)车站主股道只用于排列通过进路，不用于待避。

(2)营业站的到开可以晚点，但不能更换计划使用的股道。

(4)如果调整策略要求并且站细允许，就进行股道更换。

( 8 )

2 调整策略设计与约束规划总体流程

约束规划算法通过约束传递子方法检查运行图间隔时间、越行和股道冲突条件并触发运行计划的改动。为加强算法可控性，本文在约束规划算法中量化处理了缓冲时间和越行的自动触发关键参数，建立两类调整方法的人机交互参数控制方式以及无缓冲时间和越行调整策略的PERT仿真方法[14]。

2.1 缓冲时间建模设置与约束传递整合

表2 一种缓冲时间的分配方法

( 9 )

2.2 越行调整模式与参数设置

约束规划算法通过约束传递检查最小同向到达时间约束Ta(i,i*,j)的方式触发回退检索子方法和运行线越行操作。图3、图4的单站出发、到达事件变动能够表达为如图5所示的越行样式。图5中还包含晚点顺序传递样式，对应回退检索未被触发情况下的约束传递检查情况。

图5 运行线调整模式

(10)

当δD≤δ

调度区段内不同类型列车依据承担运输组织任务的重要程度分为不同的优先级别[15]。在高铁调度区段内，除城际动车组外还存在高速动车组、少量直通货车(部分区段运行图中存在车次规划)、检测车与回送车底。由于高速动车组跨多个调度区段行车，其优先级应为最高，其次是城际动车组与直通货车。检测车通常编制在第一班末，而回送车底多在动车段与车场间行车，故这两类车不做进一步讨论。

综上所述，高铁调度区段的越行模式可归纳如下：

(1)同级别列车发生晚点后，根据δ值确定的晚点情况，δ大于δD1通过缓冲时间处理，小于δD1需组织晚点车待避。δD1为同级别列车之间的调整阈值。

(2)高级别列车发生晚点影响低级别列车时，通过缓冲时间处理。

(3)低级别旅客列车发生晚点影响高级别列车时，δ小于δD2的晚点需组织晚点车待避，δ大于δD2则通过缓冲时间处理，部分晚点可以传播到高级别列车。δD2为不同级别列车之间的调整阈值。

(4)低级别直通货车发生晚点影响高级别列车时，需组织晚点车待避。

(5)待避晚点列车的级别低于同类型列车，但相对其他类型列车的优先级别设置不变。同类型的待避晚点列车按照同级别列车的场景处理。

(6)为减少旅客不满，旅客列车在调度区段内最多只能待避一次，且时长不超过δD3。δD3为设置的最长待避时间。

在越行模式内，相同与不同列车级别的调整阈值δD1、δD2以及最长待避时间δD3能够根据实际应用需要设置。

2.3 调整优化总体流程与约束条件判定次序

约束规划算法通过整合缓冲时间与越行样式实现了可调参数的自动调整功能。在该功能关闭时，算法将不会进行调整策略输出，而是按照文献[6]描述的PERT方法，进行不断将间隔约束时长加算到邻接事件的仿真计算。由于不涉及运行计划节点增删或到发次序变动，仿真计算能够满足CSP问题的前置条件。调整优化模型的总体流程如图 6所示。

图6 调整优化模型的总体流程

约束条件检索方法内部设计为优先检查触发大计算量以及同站间隔关系的条件，能起到防止小规模变动频繁触发的效果。模块的约束条件检测按照表3的固定次序进行。

表3 约束条件的判定次序

3 等效整数规划模型设计

列车运行调整问题的传统方法是建立整数规划模型求解，除了运行图间隔时间和车站能力的安全条件约束外，列车到站、出站时刻还受到决策变量规定的到发次序约束。离散型决策变量的排列组合包含列车越行、车次取消等调度措施的所有可能情况，使模型能够算出最优解，然而也导致算法时间复杂度随着决策变量的增加而呈现出指数型增长。相比之下，约束规划算法的到发次序变动样式由试错回退机制固定，虽然无法遍历所有可能的到发次序调整情况，但解空间冗余度小，能用于高速计算可行解。为对比验证约束规划算法可行解趋近最优解的程度以及计算效率的改善情况，本文设计同等运行图间隔时间、车站能力以及调度措施条件约束下的整数规划算法。式(11)为整数规划模型的目标函数。

(11)

单列列车的区间运行、车站停车和技术作业条件可表述为式(12)～式(14)。j*用于标示运行图车次i通过车站j后到达的车站。车次i在车站j不存在技术作业时，To(i,j)→-∞。

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

整数规划模型相应的变量值域定义如式(27)～式(30)所示。模型中的列车事件关联关系来自运行图GPlan。

(27)

(28)

(29)

(30)

4 模型应用案例与分析

模型采用京津城际某月的运行图进行列车调整计算，运行图包含20个节点，约250列车。场景设置的具体情况见表4。在调度区段扰动时长较大时，调度员进行的列车取消、加开等调度措施会破坏列车调整问题的CSP建模条件，故扰动时长限定在10、20、 30 min的情景下。

表4 扰动场景的参数设置

案例采用整数规划模型与PERT仿真方法作为对照组，验证约束规划模型的晚点总时长和计算时间。线路缓冲时间按照表 2设置并应用于区间运行时间、折返时间以及两类追踪间隔时间。调整模式的构建参数δD1、δD2、δD3分别为5、5、20 min。三类算法均使用C++编码，整数规划模型通过调用ILOG CPLEX求解，CPU主频为2.5 GHz，所有计算时间由Windows平台下的查询性能计数器统计。9种场景下的约束规划模型、PERT仿真和整数规划模型计算结果见表5。

表5 不同干扰情况下调整计算结果

表5计算结果表明，整数规划模型的晚点总时长缓解效果最好，原因是问题构建中每个列车事件都有对应的不等式描述越行与股道变更情况。大规模的问题描述保证了求解精度，也带来了算法复杂度问题。而在同等问题规模与约束条件下，约束规划模型在所有场景内的计算效率均高于整数规划模型，原因为内部约束传递与试错回退机制能够有效限定列车运行调整问题的解空间，只要依据调度措施合理设计，就能实现可行解的高速计算。

约束规划与整数规划模型的计算结果如图 7、图8所示，计划线为实线，调整线为虚线。由于场景3比场景1、2的扰动规模大，调整效果也更显著，案例只给出场景3的图示。图中未列出部分仅用于车底与直通列车接入的车站，故节点总数量小于20个。约束规划模型在同等约束条件下的计算效率远高于整数规划模型，然而整数规划模型的调整结果与计划线差别与晚点整体的影响范围都表现最优，说明约束规划模型的检索机制只能有限地趋近最优解，内部机制还需要完善。

图7 场景3的约束规划列车调整模型计划生成结果

图8 场景3的整数规划列车调整模型计划生成结果

约束规划模型调整策略的有效性还能通过晚点比率考察，晚点比率是约束规划模型与PERT仿真晚点总时长的百分比，该比率越低，调整策略的效果越好。约束规划模型场景1～3的调整结果与文献[6]的晚点比率分析如图 9所示，两者分别为实线、虚线。图9中5、15、25 min的晚点比率由亦庄—永乐下行方向区间封锁8：25—8：30、8：25—8：40、8：25—8：50的扰动场景算出。

图9 不同约束规划调整优化模型的比较分析

由于约束规划优化模型处理的调度区段内多为城际列车，高等级直通列车只占很小比例，使得不同级别间越行现象发生的频次少于文献[6]。而文献[6]处理的调度区段内高、低等级列车数量各占一半，不同级别间越行的频次多，从而达到更好的调整效果。得益于缓冲时间的有效利用，约束规划模型在5 min干扰程度下的调整效果优于文献[6]。

5 结束语

本文在列车运行调整问题构建为CSP问题的基础上，建立了基于约束规划方法的高速铁路调整优化模型。优化模型的最大特点是高效率计算，相比与同等运行图间隔时间、车站能力以及调度策略条件约束下的整数规划算法，该模型具备更强的计算效率，但晚点总时长的优化效果不及整数规划算法，其内部机制仍需进一步改善。优化模型算法计算效率高，具备较强的拓展潜力，后期研究可考虑将换乘、分解等调度手段引入约束传递方法，进一步增强自动调整功能，为智能调度业务的系统集成提供有力的支持。