Slack Time Allocation In Robust Double-Track Railway Timetable Optimization

Railway transportation being an important mode of transportation in many countries especially in Asia and Europe plays a key role in passenger and freight transportation markets. The railway industries strive to continuously improve their level of service in the increasingly competitive and rapidly changing multi-mode transportation market. The competition among the different transportation modes mainly depends on the level of service it provides. Punctuality and reliability are the two key determinants of the quality of scheduled railway services which play vital role for passengers and freight shippers in choosing the desirable mode. Reliability of railway system is determined by the overall performance of the railway timetables and is calculated in terms of the mean or variance of the train's lateness from its scheduled time. Therefore, it is essential to design the robust railway timetables that can cope with real-time disturbances and provide reliable railway services.This dissertation is concerned with a generation of robust railway timetable in a medium-term planning that incorporates the effects of stochastic disturbances unfolding in the real-time dispatching stage. More specifically, the underlying topics mainly include, (1) formulating a two-stage recourse optimization model and (2) to propose efficient solution algorithms to solve the proposed stochastic optimization model.In planning railway timetables, planners commonly assume the data inputs (e.g., departure, arrival and travel times of trains) are precisely known and ignore the influence of parameters uncertainty on the optimality and feasibility of the timetable generation. However, in the real-time rail operations, the published timetables are often affected by random unforeseen events (e.g., inclement weather conditions, equipment breakdown and track maintenance etc), and the travel times of trains could significantly deviate from the planned timetable. Therefore, it is conceivable that during day-to-day rail operations the travel times may violate critical constraints (trains related or segment capacity constraints etc.,) which results in poor punctuality of the railway services. These observations call for addressing the issues of modeling travel time uncertainty at the planning stage in order to construct robust timetables. To systematically integrate the medium-term planning and operational planning stages, we propose a two-stage stochastic recourse model that incorporates real-time uncertainty and dispatching policies into the medium-term train timetabling decisions to (1) minimize the total travel times of all trains in the published timetable and (2) reduce the expected schedule delay from its planned travel times under random segment running times. Since, both planning stages (i.e., train timetabling and dispatching) need to solve complex integer optimization problems, we further explore efficient solution algorithms to find out near optimal solutions.Although substantial progress has been made to various aspects of the robust timetabling problem, it is still important to develop a computationally efficient framework to solve complex timetabling models. In this thesis, we propose a heuristic sequential decomposition scheme (that could be applied to decompose the problem to a series of sub-problems for individual trains). With the help of proposed sequential decomposition scheme, we are able to model the delay propagation of a train from one segment to the following segment, and also captured the delay propagation between trains, that is, the primary delay of a train at a segment could further cause secondary delays to the following trains that have been planned/scheduled previously at the same segment.Furthermore, to accurately estimate the propagation of knock-on delays among a cluster of trains, a space-time network representation is proposed to reformulate the optimal slack allocation problem as a stochastic time-dependent shortest path problem. In particular, the sub-problem under consideration seeks to determine a "reference" path that can minimize the total trip time (in the planning timetable) and the expected schedule deviations from the planned timetable among all possible random scenarios. The other advantages of adopting a stochastic shortest path framework is that, we are able to (a) easily propagate delay distributions through arcs, and (b) use stochastic dominance rules to eliminate dominated partial timetables from the early search process.Lastly, to capture segment running time uncertainties in daily railway dispatching, it is well known that the number of possible segment running time scenarios grows exponentially due to unforeseen events. An efficient sample average approximation method is proposed to choose representative samples from the huge number of randomly generated segment running times. In sample approximation approach, the expected objective function of the two-stage stochastic problem is approximated by a sample average estimate derived from a random sample taken from the historical database. The resulting sample average approximation problem is then solved by deterministic optimization technique. This process is repeated with different samples to obtain solutions along with statistical estimates of their optimality gaps.Extensive numerical experiments along with illustrative examples are provided to demonstrate the efficiency and efficacy of the proposed model and solution algorithms using real-world Beijing-Shanghai passenger high-speed rail corridor test data set in China.