Estimation of railway capacity consumption using stochastic differential equations.
The efficient utilization of railway infrastructures is a primary objective in an open-market context like the European one. The capacity consumption, that is the infrastructure occupation augmented with buffers to avoid delays (referred to a time window, e.g. peak hour or day), is a measure of the utilization level of a given timetable. The standard UIC leaflet "Capacity" recommends a procedure to evaluate the infrastructure occupation, without buffers, by compressing the timetable until the blocking time stairways touch each other in the critical section. There is no recommendation about buffer times, except a well known rule of thumb about the running time supplement, which is often set to 5% of the journey time. Buffer times choice is a trade-off between efficient utilization and stability, to avoid secondary delays caused by primary delays. Given the probability distribution of the primary delays, it is possible to estimate the distribution of secondary delays and hence the buffers. In this work the primary delays are modelled following an innovative approach, that is using a family of stochastic processes called Lévy processes. These stochastic processes are defined through a very simple and general assumption: stationary independent increments. A disturbance on which there is few knowledge may reasonably be assumed to satisfy independence and stationarity properties, because independence means the future doesn't depend on the past and stationarity means the process doesn't change its structure over the time (often it is true only on large time windows). Another reasonable assumption is the path continuity, so the Lévy process reduces to a Brownian motion. The train movement is therefore modelled with a differential equation to which a Brownian motion is added, leading to a stochastic differential equation (SDE). Given the numerical approximation of the Brownian motion sample path, which is pseudo-random generated, it is possible to solve the SDE and obtain the sample path of the train. The analysis of the stochastic phenomenon requires the replication (called Monte Carlo) of the pseudo-random generation of the approximated Brownian motion sample path and the solution of a SDE to be computed many times. The result is a collection of simulated sample paths for each train scheduled. This set of collections may be used in two different ways: - estimation of the probabilistic distributions of the blocking times and consideration of the stochastic version of the blocking time stairways; - estimation of the risk, that is the probability of hindrance which corresponds to a given timetable, with the trains running in free mode (no external control, signals ignored) but counting the risky events highlighted by the signalling system. The estimation of the risk is repeated varying the number of trains, so that a relationship is built between the risk and the number of the trains or headways, from which a measure of capacity consumption is obtained given the risk level. The thesis consists of two parts, the first is made of preparation chapters while the second one is devoted to models and applications. The work begins with a chapter on capacity issues, where concepts, definitions and standards are illustrated to establish the research framework; the chapter ends with a literature review where the recent approaches are discussed and the lack of an SDE approach is highlighted. There is one stochastic approach which uses differential equations, but they are deterministic and combined with stochastic boarding time. Then a brief theoretical chapter on the Lévy processes is presented to justify the modelling choice and to introduce the Brownian motion in a reasonably acceptable way; unavoidable definitions of stochastic entities and theorems bring the reader to the presentation of the central result of the Lévy theory, that is the decomposition theorem. The Lévy-Ito decomposition theorem states that a Lévy process always decomposes as the sum of a Brownian motion with drift, a compound Poisson process and a martingale: if the sample paths are continuous, then there is only the Brownian component because the other ones have jumps in their paths. The Brownian motion introduction is followed by a theoretical chapter on the SDEs, where the symbolic meaning of dW is explained, together with two popular formulations of the stochastic integral, Ito and Stratonovich and the choice of Ito's one is justified on modelling basis. The Ito formula, that is the stochastic chain rule of calculus, and the stochastic Ito-Taylor expansion are presented as essential tools for understanding stochastic numerical methods. The chapter ends with the theorem that states the existence and uniqueness of a strong solution, that is the solution of the SDE given the driving Brownian motion Wt. The following chapter is about the numerical methods that are available to solve an SDE; at the beginning a brief review of the concepts and methods of deterministic ordinary differential equations is given. The most known and used schemes - i.e. Euler and Milstein - are presented together with their convergence and stability properties. Other schemes are briefly cited for sake of completeness. The preparation part closes with a chapter devoted to Monte Carlo simulations and the type of possible applications of the resulting collections of train paths to capacity assessment, that is estimation of the probabilistic distributions of the blocking times and estimation of the risk as probability of hindrance. Replications of Monte Carlo simulations with different timetables allow the building of the capacity-risk relationship. In the models and applications part two SDE-based models are presented, together with case studies: the first model is simple but allows some theoretical considerations to validate (in the form of bounds) the simulation results; the second model is a stochastic optimal control model. In both cases the model parameters are estimated using real life data and then the capacity-risk relationship is build through simulations. Another result of the simulation is the set of blocking/clearing time distributions for each section, which is graphically represented by plotting their key points (the mean value and extremes of the almost-sure range estimated by taking three times the standard deviation) at each section for a group of train paths. This second model describes in a more realistic way the train journey, because the mechanical equation is more suitable and the driving machine produces a force following an optimal control rule which considers both the distance from the timetable and the energy consumption. The optimal control law of the exact stochastic optimal control problem may be found by solving the Hamilton Jacobi Bellman equation, which is numerically heavy as well as difficult to solve because of instability and non-linearities. An approximated stochastic optimal control problem is solved for the more relevant part of the train travel, that is the steady state maintenance stage (initial acceleration stage and final stop stage are excluded), where the driver tries to reach the steady state determined from the planned timetable: the mechanical equation is linearized near the steady state speed and the optimal control law expression in terms of state variables is found and therefore substituted in the SDE. A parameter, the driving style, defined as the ratio of the schedule cost and the energy cost, is introduced to describe the different weights the two objectives may be given. Sensitivity analysis has been performed to determine the parameters' ranges for model applicability. The more relevant aspects of this work from a transportation research point of view are: - a new approach of computing free running times by means of stochastic differential equations has been introduced, after deep considerations about the characteristics of the stochastic perturbation; - the collection of free running times, result of a Monte Carlo simulation, can be used to estimate the distribution of primary delays, from which it is possible to derive the distribution of the secondary delays and hence choose the buffers; - the collection of free running trajectories can be used to estimate the distributions of the blocking times of the timetable stairways; - a new approach of capacity assessment based on the estimation of a relationship with the probability of hindrance by performing Monte Carlo simulations in different conditions has been introduced, together with the concept of risk-coupled capacity: capacity (and capacity consumption) depends on the maximum acceptable level of risk; - two SDE models have been introduced, together with their parameters' estimation procedures and applicability rules; - the second model is obtained solving a stochastic optimal control problem which models real life needs such as timetable observation and low energy consumption; once its closed-form expression is found, the optimal control law can also be applied in real life, provided the continuous measures of train state, i.e. its speed and position.
Università degli studi di Trieste