Study On Optimization Models And Algorithms For Railway Train Timetabling Problems Under Complex And Typical Scenarios

As the railway passenger demand grows each year,some of the railway lines in China need to operate more and more trains with limited infrastructure capacity to satisfy the passenger travel demand.Meanwhile,China’s economy has developed rapidly in recent years,such that passengers have higher and higher requirements on travel quality,and railway transportation is also facing increasingly fierce competition from other transportation modes in the passenger transport market.Train timetable serves as the product of the railway transport service and it is the core technical document for guiding the railway operations,and thus the quality of the train timetable not only has a fundamental impact on the operating efficiency and costs of the railway transportation system but also directly determines the passenger travel satisfaction levels.At present,the preparation of train timetables in China is mainly performed manually by the train movement planners,where the preparation processes are assisted by the computer systems.As a result,the train movement planner usually generates the train timetables at the macroscopic level,and the line plans serve as the given input information,where the feedback loop from the train timetable to line plan is generally not considered.Therefore,it is necessary to develop highly efficient and practical optimization models and algorithms for the train timetabling problems to resolve the above issues,and thus the automation level of the railway operation management department in preparing the high-quality train timetables is also improved.This paper first systemically reviews the literature on the train timetabling problems and analyzes the shortcomings of the previous works.Considering the conditions and operating characteristics of the railway lines in China,this paper then studies the train timetabling problems under complex and typical scenarios for the passenger transport system in China.Specifically,the complex and typical scenarios include the cyclic train timetabling problem for high-speed railway corridors at the macroscopic level,and the integrated optimization of line planning and train timetabling problems for high-speed railway corridors at the macroscopic level,and the integrated optimization of non-cylic train timetabling and track maintenance task scheduling problems for a normal-speed railway network at the microscopic level.At the same time,this paper develops integer linear programming(ILP)models and efficient decomposition algorithms for the above train timetabling problems,which are aimed to simultaneously improve the railway infrastructure capacity utilization rate and transport service quality.More specifically,this paper has completed the following tasks:(1)Based on the train timetable preparation procedures under the railway transportation system management mode in China,this paper performs qualitative analysis on the preparation elements and connotations of the macroscopic train timetable,microscopic train timetable,noncyclic train timetable,and cyclic train timetable.Subsequently,this paper briefly introduces several modeling methods for the train timetabling problems that are commonly used by the researchers,including the big-M formulation,time discretized space-time network,and periodic event scheduling problem(i.e.,PESP),and this paper also summarizes the connotations and characteristics of the studied train timetabling problems under complex and typical scenarios,which lays the theoretical modeling foundation for building the ILP models in the subsequent sections.(2)Taking a double-track high-speed railway corridor at the macroscopic level as the research object,this paper builds a new ILP model for the cyclic train timetabling problem based on the extended space-time network modeling framework.Specifically,the existing mathematical programming model based on the PESP modeling framework is transformed into a multicommodity network flow model with two coupled schedule networks and side track capacity constraints.In addition,two dual decomposition methods,including Lagrangian relaxation and Alternating Direction Method of Multipliers(ADMM),are adopted to dualize the side track capacity constraints.For each train-specific sub-problem in an iterative primal and dual optimization framework,an enhanced version of forward dynamic programming is developed to find the time-dependent least cost master schedule across the space-time network over multiple periods.ADMM-motivated heuristic methods with adjusted penalty parameters are also developed to obtain good upper bound solutions.Finally,based on real-world instances from the BeijingShanghai high-speed railway corridor,the superiority of the proposed reformulation and ADMMbased solution algorithm is proved compared with the PESP model that involves the standard optimization solver.(3)The iterative heuristic algorithmic frameworks in most of the existing studies rely on the heuristic rules to dynamically adjust the line plan after evaluating the performance of the train timetable.Therefore,by introducing two types of binary variables,this paper first builds a 0-1 ILP model with a unified form for integrating the optimization of high-speed railway line planning and cyclic train timetabling problems.Specifically,the two types of binary decision variables are coupled by a cross-resolution consistency constraint,which guarantees the conformity of the line planning and cyclic train timetabling decisions.Furthermore,an ADMM-based dual decomposition mechanism is developed to dualize the cross-resolution consistency constraint and track capacity constraint,such that the original ILP model is decomposed into a line planning sub-problem and a set of train-specific sub-problems.After linearizing the quadratic penalty terms in ADMM,each of the sub-problem contains the information of the cross-resolution consistency constraint-based Lagrangian relaxation prices.Moreover,the satisfactory primal and dual solutions are obtained by iteratively and efficiently solving the line planning sub-problem with a commercial solver and each train-specific sub-problem through a tailored forward dynamic programming algorithm.The computation results of the numerical experiments show that the integrated optimization approach can improve the objective value by 5.78% on average compared with the sequential optimization approach.(4)Given the normal-speed railway network data at the microscopic level as well as the relevant information of the trains and track maintenance tasks,this paper builds an optimization model for integrating the non-cyclic train timetabling and track maintenance task scheduling problems,and an iterative algorithm is designed for solving this problem efficiently.Specifically,block sections are considered as the basic microscopic elements for train movements in a railway network.An ILP formulation is proposed for the integrated optimization problem in which train timing,sequencing,and routing are the timetabling variables,while timing and sequencing of track maintenance tasks are the track maintenance variables.The objective function is to minimize the weighted-sum of total train travel times and the maintenance tardiness costs while ensuring the train running safety and normal completion of track maintenance tasks.Since the integrated optimization problem is strongly NP-hard,an iterative algorithm based on a commercial solver is proposed to decompose the overall problem into sub-problems related to train scheduling and/or routing with or without track maintenance task scheduling.The computation results on the real-life and largescale test instances show that the iterative algorithm has satisfactory performance on the solution quality and solving efficiency.