High-speed railway train timetable optimization model and improved column generation algorithm

摘要

Scheduling good train timetable can enhance the quality of the train service of the Railway Company. In China, high-speed railway network has expanded quickly during the last decade, to schedule a feasible train timetable more efficiently or seeking the optimal solution is urgent demand to the technicians on the railway industry. This paper proposes anew optimization mathematical model for train working diagram scheduling and designs an improved column generation method to solve it. Firstly,transfer the mathematical model into a linear problem with Lagrangian relaxation. Then, simplify the original linear problem by modifying the objective function and decision variables, search for an optimum solution by updating restricted master problem and the price problem during the column generation iterations. Branch and bound methods are used to eliminate bad solutions. Finally, take the real world Beijing-Shanghai high-speed railway datumas the case study,the computation results prove that the optimization model and algorithmareeffective andefficient;they have the potential practical usage.