Integrated Metro Train Rescheduling Optimization Based On Approximate Dynamic Programming

Urban rail transit plays an important role in the transportation systems of large cities due to its safety,efficiency,high carrying capacity and environmental friendly characteristics.As the main artery of public transportation networks,urban transit systems have been rapidly developed in many large cities in China.As urban rail transit continues to expand into a giant and networked systems,the practical operation environment has become much more complex,which evidently increases the difficulty for managing such huge systems.In daily operations,the real-time operations of a metro system are inevitably disrupted by some unexpected disturbances,which are usually caused by passenger demand variation,equipment failures and incidents,etc.These disturbances may cause serious interferences that require to reschedule the train operations as soon as possible.Typically,the train regulation for urban rail transit contains train timetable reschedule on the dispatching level and train control strategy adjustment on the train control level.With the rapid development of Communication,Computer science and Control(3C)technologies,the automation level of metro systems has been greatly improved into a very high-level.Under such background,how to realize flexible,high-efficient and intelligent train regulation that combines train dispatching level and train operation level has become an active research topic in recent years.In this thesis,we investigate the real-time train regulation problem to simultaneously adjust the macroscopic train timetable and microscopic train speed profiles based on Approximate Dynamic Programming(ADP)theory.In particular,we rigorously consider three different scenarios with slight disturbances,normal disturbances and serious disruptions in order to customize the efficient real-time ADP based method.The aim is to reduce the delay time of trains and passengers,recover to the original timetable,ensure the train order and keeping the energy consumption of trains.Specifically,this thesis aims to make the following contributions to the study of metro train rescheduling problem.1.This thesis first establishes the fundamental model for the integrated train rescheduling problem.By introducing the basic structure,functions and objectives of Automatic Train Control(ATC)system and Automatic Train Regulation(ATR),an integrated metro train rescheduling model is constructed based on a discrete state-space-time network.This model simultaneously considers the optimization of train schedule,speed profiles and dynamic passenger demands,resulting into an integrated strategy for metro train rescheduling with systematic optimization.Based on this mathematical model,we further discuss how to apply ADP for solving the integrated train rescheduling problem for urban rail transit systems.2.With the consideration of slight disturbances that do not affect multiple trains,this study proposes a single-train rescheduling method.By analyzing the train delay propagation process,this problem is formulated into a stochastic Markov Decision Process(MDP).Then,an expert system and Q-learning algorithm are proposed for the adjustment of train schedule and speed profile on each segment.The aim is to minimize the expected train delay time in a total cycle and energy consumption.Based on the real-world operation data in Beijing Subway Yizhuang Line,a simulation platform is built as the learning environment in Q-learning.Simulation results indicate that,this method is able to evidently improve the punctuality of trains in peak hours and reduces the negative impacts.3.On the basis of above research,this study further considers the metro train rescheduling problem in case of relatively large delays in order to recovery the trains from delays and reduce the negative impacts on passengers.In specific,we propose a non-homogeneous Poisson distribution to model the uncertain time-variant passenger demands and construct a stochastic programming model for the metro train rescheduling problem.Then,a look-ahead policy based ADP and a value function approximation based ADP are respectively designed to generate near-optimal solutions in a very short time,recovery the trains from delays and reduce the passengers' waiting time,travelling time and train energy consumption.4.Finally,this study considers the train rescheduling problem with variable train numbers in case of complete disruptions that causes the disorder of trains and delay of passengers.In such cases,dispatchers can use backup trains in storage lines to evacuate the delayed passengers and recover the line capacity.A mixed-integer programming model is constructed to reschedule the timetable of existing and backup trains.To tackle the train order adjustment issue,we propose several IF-THEN based constraints.In addition,we propose three Lemmas to transform the original nonlinear model into equivalent linear models by introducing a big-M method,redundant variables and constraints.Finally,rigorous proof is presented to prove our conclusions.