高速列车停站优化问题的两阶段求解算法

Two-Stage Optimization Algorithm for Stop Schedule Plan of High-Speed Train

为了提高高速列车停站优化问题的求解效率,以高速列车停站设置原则为基础,分析了影响列车停站的主要因素,从方便旅客出行及减少旅客出行广义费用两方面考虑,建立了列车停站方案综合优化模型.结合列车停站优化问题的特点,提出了包含初步优化和综合优化的两阶段优化算法,初步优化阶段采用基于先验知识的局部优化方法,可以快速有效的获得问题的较优解,综合优化阶段利用具有较强爬山能力的禁忌搜索算法进行全局优化.最后对某高速铁路高峰小时开行列车的停站优化问题进行求解.结果表明,两阶段优化算法比一般禁忌搜索算法效率提高约30%.

To improve optimization efficiency of the stop schedule plan of high-speed trains, the main factors influencing train stop schedule plans were analyzed based on the principles of stop schedule plan of high-speed trains. An optimization model was proposed, in which passengers＂ traveling convenience and generalized cost were considered. A two-stage algorithm was designed to solve the optimization model. Prior knowledge was used to find a local optimum solution quickly at the first stage, and Tabu search was applied to find a global optimal solution at the second stage where the local optimum solution obtained at the first stage was taken as its input. An optimization example of train stop schedule plan of a high-speed railway was presented. The result shown that the efficiency of the proposed two-stage algorithm was 30% higher than that of Tabu search only.