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

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

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

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.