交通运输系统工程与信息

交通运输系统工程与信息 ›› 2018, Vol. 18 ›› Issue (1): 179-185.

• 系统工程理论与方法 • 上一篇    下一篇

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

兰泽康，何世伟*，黎浩东   

  1. 北京交通大学 城市交通复杂系统理论与技术教育部重点实验室，北京 100044
  • 收稿日期:2017-07-12 修回日期:2017-08-30 出版日期:2018-02-25 发布日期:2018-02-26
  • 作者简介:兰泽康(1993-)，男，福建宁德人，博士生.
  • 基金资助:

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

Optimization Model and Branch-and-price Algorithm for Train Dispatching on a Railway Network

LAN Ze-kang，HE Shi-wei，LI Hao-dong   

  1. MOE Key Laboratory for Urban Transportation Complex Systems Theory and Technology， Beijing Jiaotong University，Beijing 100044，China
  • Received:2017-07-12 Revised:2017-08-30 Online:2018-02-25 Published:2018-02-26

PDF

被引次数

1

摘要：

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

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

Abstract:

This paper investigates train dispatching that train can change its driving line in a railway network，in order to minimize the total arrival deviation time of all trains. Firstly，a network flow model based on train arrivaldeparture time is built by introducing the flow balance constraint，and using commercial software GUROBI to solve it. This paper also develops an integer programming model based on time- space path，and a branch- andprice solution framework is proposed，using pseudocost branching and best-node first search strategy to speed up the convergence. The results of numerical experiments show that in comparison with GUROBI，the algorithm is effective. When the number of trains is 20，the computational time is reduced by 91.6%，and the gap between the final feasible solution and the optimal solution is 9.72%. The branching strategy in this paper is better than most fractional branching，and the objective value of train rescheduling with flexible driving line relative to only with original driving line falls by 37.4% on average.

Key words: railway transportation, train dispatching, branch-and-price algorithm, railway network, integer programming

中图分类号: