Abstract:

Give ideal departure time and initial profit for each new train path, consider the penalties caused by departure time adjustment and total stop time prolong, based on a time-space graph build an ILP model which take the maximum total profit of the timetable as object function, relax the model in a Lagrangian way, take consideration of the relaxation dual information to design a heuristic algorithm to get the practical solution of each train path, optimize the global solution by updating the Lagrangian multipliers. JingHu high-speed railway was taken as a verification case, the results show: under the given case, compared with the existing timetabling method that search the train path according to the departure time instant, the proposed method scheduled 6 more train paths; with the departure time window expanded from 10 min to 60 min, the solving time of CPLEX increased dramatically, while Lagrangian method had a shorter solving time and could get better solutions than CPLEX except the 10 min scenario. Prolong the departure time window to 4 h, at most 18 new trains are scheduled, which proved that the capacity of JingHu high-speed railway is nearly saturated under the case-study situation.

Key words: railway transportation, train timetable, Lagrangian relaxation, JingHu high-speed railway, capacity

摘要：

给定新增列车理想始发时刻及初始利润，考虑始发时刻调整及全程停时延长造成的罚数，基于时空网络构建以全图运行线总利润最大为目标的整数规划模型，进行拉格朗日松弛，根据松弛解对偶信息设计启发式算法求解各运行线可行解，并通过更新拉格朗日乘子进行迭代优化.以京沪高铁为例进行了验证，结果表明：在算例条件下，相较以理想始发时刻推线求解，该方法能够多增铺6条运行线；随着始发时刻可调整度由10min增加至60min，CPLEX的求解时间快速增长，而拉格朗日松弛启发式算法能快速求得高质量的解，除始发时刻可调整度10min情景，求解效率均高于CPLEX；延长始发时刻可调整度至4h，最多增铺18条运行线，说明现有框架下京沪高铁能力已接近饱和.

关键词: 铁路运输, 列车运行图, 拉格朗日松弛, 京沪高铁, 通过能力