基于拉格朗日松弛的高速铁路列车运行图新增运行线局部调整模型

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

A High-speed Railway New-added Train Timetable Partial Adjustment Model Based on Lagrangian Relaxation

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.