Research On Optimization Methods For Train Scheduling And Rescheduling Problems In Railway Network

As an important transportation mode,railway transportation undertakes more and more services due to its advantages of large traffic volume,high speed,low energy consumption,punctuality and safety.With the gradual expansion of the railway network and the rapid increase of passenger demand,how to provide higher quality transportation services for passengers has become an urgent problem that needs to be solved by the railway companies.As the basis of railway operations,the quality of train schedule directly affects the operating efficiency,costs and service quality of railway transportation system.Therefore,based on the actual situation of railway transportation in China,this thesis focuses on the optimization methods for train scheduling and rescheduling problems in railway network.With different considerations,this thesis formulates different mathematical models and develops some efficient solution algorithms,in order to effectively improve the utilization of railway infrastructure capacity and transport service quality.Specifically,the main content of this thesis includes the following aspects:(1)Two-stage distributionally robust optimization for integrated train scheduling and stop planning problems.In order to improve the robustness of the operation scheme,this thesis studies the integrated optimization of train scheduling and stop planning problems based on demand distributional ambiguity in a railway network.Specifically,considering the constraints of track and station capacity,a two-stage distributionally robust optimization(DRO)model for integrated train scheduling and stop planning problems is proposed,in which the time-space network representation is adopted to characterize the movements of trains and passengers,and the DRO method is applied to handle the ambiguity in the probability distribution of passenger demand.For computational convenience,this model is first reformulated as a mixed integer linear programming(MILP)with a ∞-norm-based ambiguity set,and then a heuristic iterative algorithm based on train schedule and passenger assignment is proposed to solve the problem.Finally,two sets of numerical experiments,including an illustrative instance and a real-world instance in a railway network,are carried out to verify the effectiveness of the proposed methods.(2)Integrated optimization of sunset-departure and sunrise-arrival train(SDSAtrain)scheduling and maintenance planning problems on high-speed railway corridors.In the railway network,considering the passenger demand traveling at night,this thesis focuses on the integrated optimization of the SDSA-train scheduling and maintenance planning problems on high-speed railway corridors,so as to enhance the attraction of the SDSA-trains.In order to reduce the influence of regular maintenances on SDSAtrains,an integrated optimization mathematical model of these two problems is formulated with the help of big-M method.The model takes many practical factors into considerations,such as station track assignment,departure/arrival time window,train stop plan,maintenance window width,maintenance duration and mode selection of SDSA-trains.Furthermore,the model is reformulated into a MILP model by using some linearization techniques,and the proposed optimization method is verified by a series of numerical experiments based on the real data of Beijing-Guangzhou high-speed and normal-speed railway corridors in China.(3)Integrated optimization of train scheduling and maintenance planning problems in a railway network.In the railway system,the railway maintenance task will reduce the utilization of railway infrastructure capacity,which avoidably affects the train operation plan and reduces the service quality.In this thesis,we propose an integrated optimization model for these two problems in a railway network,to simultaneously minimize the total travel time of passengers and maintenances cost.In particular,a layered space-time network is proposed,and the concept of incompatible set is used to represent the occupation conflict of resources between the train schedule and maintenance task.In order to solve the model effectively,a heuristic algorithm based on Lagrangian relaxation is proposed to decompose the problem into a series of independent train-based and maintenance-based sub-problems.Due to the large number of constraints,we use a dynamic constraint-generation technique in the iterations of the sub-gradient optimization procedure.Finally,the experimental results show that the proposed method can effectively optimize the train schedule and maintenance task in a high-speed railway with SDSA-trains.(4)Train rescheduling problem for large-scale disruptions in a large-scale railway network.Under the emergency situation,considering the satisfaction of passengers,the train rescheduling problem for large-scale disruptions in a railway network is studied to ensure the service quality of railway system.As rescheduling measures,we consider train reordering,retiming and cancellation of some train services as well as the option of rerouting trains along alternative paths in the railway network,so as to quickly adjust train operations to minimize the impact of disruption on passengers.In particular,with the space-time network,the train path is transformed into space-time trajectory,and the incompatible arc set is defined to characterize the conflict between trains on the occupation of railway resources.Then,a train rescheduling model based on train path selection in a railway network is formulated.In order to effectively solve the model for real-world instances,a heuristic algorithm based on Lagrangian relaxation is designed to decompose the problem into a series of independent train-based subproblems.Due to the large number of constraints and in order to cope with the real-time requirement,a dynamic constraint-generation is also applied.Finally,the effectiveness of the proposed methods is verified by several numerical experiments based on two different railway networks under several disruption scenarios.This thesis includes 74 figures and 52 tables and refers to 157 pieces of literature.