面向鲁棒性的高速铁路网络列车运行调整计划优化模型

针对高速铁路路网中出现区间封锁事件,考虑事件持续时间的不确定性,以列车运行时间和安全间隔时间为约束条件,引入路径选择唯一性约束保证列车运行调整计划的鲁棒性,以所有列车晚点时间之和的期望值最小为目标函数,建立高速铁路列车运行调整计划优化整数规划模型.设计基于优先级规则的启发式算法,求解原模型的可行解.运用拉格朗日松弛算法和最短路径算法求解该模型的松弛模型,得到原模型最优解的下界.根据可行解与最优解下界之间的距离,可以定量地衡量可行解的质量.结果表明,相较于CPLEX数学求解软件,算法求解效率较高;模型与算法能够有效生成鲁棒的列车运行调整计划,为调度员提供必要辅助决策信息.

A robustness-oriented train dispatching optimization model on a high-speed rail network

Aiming at the incidents in which segments are blocked,we propose a robust train dispatching model to solve the network train dispatching problem with stochastic information of capacity breakdown duration. The objective is to minimize expected total train delay time. Train running times and station dwell times,as well as safety headway times are considered as constraints. Moreover,unique route selection constraints are introduced to guarantee the robustness of dispatching solutions. Then we develop a Lagrangian relaxation based solution method to solve the proposed mixed-integer programming model. A lower bound is obtained by solving the dualized subproblems through a time-dependent shortest-path algorithm. An upper bound is generated by solving the original problem through a priority-rule based algorithm. A quantitative assessment of obtained solutions is then obtained by comparing the gap between lower bound and upper bound. Numerical experiments are conducted to validate the proposed models and algorithms.