AP3: Robust routing in railway systems

Network flow theory forms the backbone of cost- and time efficient design and analysis of routing algorithms in logistic and communication networks. Various elegant and fast combinatorial network flow algorithms exist, e.g. to maximise the amount of traffic (“flow”) that can be sent through a capacitated network—even under the objective to minimise a linear cost function. However, when uncertainties in the capacities come into play, the problem to find a flow that maximises the flow value which actually reaches the sink becomes inherently complex. Already for the simple problem to find a max K-robust flow, i.e., a flow that maximises the guaranteed throughput given that K > 1 arcs may fail, the complexity status is open. (One paper claimed NP-hardness for K=2. The proof, however, only shows that the dual separation is NP-hard.) Complexity results and algorithms for network flow problems under uncertainties are investigated in current research. This doctoral project aims at developing routing algorithms that are robust by minimising the amount of traffic that might be harmed by unforeseen arc failures and/or major disruptions.

Developing routing algorithms that are efficient and robust towards changes in the input data belongs to one of the biggest challenges in the design of railway systems. Route- and time-schedules are computed that prescribe which type of train travels along which link of the railway-network in which time period. Certainly, there are numerous different kinds of constraints that need to be satisfied turning the corresponding optimisation problem which asks for a feasible routing protocol of minimum cost and/or time into a highly complex problem, even in the nominal setting, i.e., where there are no uncertainties on the input data.

The railway network design algorithms generalise uncertainties in terms of an initial delay distribution function for each train type so far. Other uncertainties like the failure of a link or a major disruption are neglected. Additionally they ignore the temporal dimension of the problem to a large extent. Note that the trains need a certain travel time to traverse each single link of the network. As a consequence, the capacities in the network on tracks and stations limit the amount of flow/trains entering a particular link/station per time-unit.

The flow models used so far for route-computations in railway systems work on so-called “static” flow models: the time horizon is split into smaller time periods, and feasible routes are computed using static flow theory for each of those periods separately. Dynamic flows take travel times into account and allow for a more realistic modelling of the underlying routing problem. Dynamic flows were introduced by Ford and Fulkerson. For railway systems, an integral version of dynamic flows, also referred to as packet routing seems to be more appropriate.

The goal of this research project is to improve existing routing algorithms in railway systems by either incorporating the theory of dynamic flows and/or by incorporating the theory of robust optimisation, in particular, robust flows. By combining the theory of robust optimisation and railway engineering, we are optimistic to develop various new techniques, methods, and structural insights for dynamic routing in railway operations research.

(This dissertation project is related to the projects AL1 and AL2.)