铁路网络列车运行调整的优化模型 及其分支定价算法

来源：交通运输系统工程与信息杂志2018年第1期北京时间：

作者：兰泽康，何世伟，黎浩东

单位：北京交通大学 城市交通复杂系统理论与技术教育部重点实验室，北京 100044

摘要：研究了铁路网络中列车可变更运行线路下的列车运行调整问题，目标是使得所有 列车偏离终到时间之和最小化.首先引入流平衡约束建立基于列车到发时刻的网络流模型，采 用商业软件GUROBI求解.同时构建了基于列车时空路径的整数规划模型，并给出了分支定 价算法，采用伪费用分支和最佳优先搜索策略加快算法的收敛.最后设计算例进行验证，通过 与GUROBI对比说明本文算法是有效的.当列车数为20 列时，求解时间减少91.6%，得到的最 终可行解距离最优解的间隔为9.72%.验证了本文分支策略较最为分数分支策略更优，列车运 行调整可变更线路相比于只能按原始线路行驶平均可降低目标函数值37.4%.

关键词：铁路运输,列车运行调整,分支定价算法,铁路网络,整数规划

基金资助：国家自然科学基金/ National Natural Science Foundation of China(U1434207, 61374202)；北京市自然科学基金/ Beijing Natural Science Foundation (9164032).