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

摘要：

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

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