A probabilistic (max, +) approach for determining railway infrastructure capacity

Abstract

We consider the problem of determining the capacity of a planned railway infrastructure layout under uncertainties. In order to address the long-term nature of the problem, in which the exact (future) demand of service is unknown, we develop a “timetable”-free approach to avoid the specification of a particular timetable. We consider a generic infra-element that allows a concise representation of many different combinations of infrastructure, safety systems and traffic regimes, such as mixed double and single track lines (e.g., a double track line including a single tunnel tube), and train operations on partly overlapping routes at station yards. We translate the capacity assessment problem for such a generic infra-element into an optimization problem and provide a solution procedure. We illustrate our approach with a capacity assessment for the newly built high-speed railway line in The Netherlands.

Introduction

Capacity assessment for railway infrastructure plays a key role in the design of layouts of infra-elements, such as tunnels, bridges, lines and complex railway yards, such as stations. We define capacity of a railway infra-element (denoted by N_sys) as the maximal number of train movements that can be executed on the particular infra-element in T time units (e.g., T=60 minutes) with probability greater than or equal to p where p is a predefined reliability threshold. The purpose of railway capacity assessments is to decide whether the proposed infrastructure layout can handle the intended traffic load (denoted by N_intended) meeting predefined quality requirements. If capacity assessments yield negative results, that is, if N_sys<N_intended with probability greater than p, alternative track layouts have to be considered. In this way, railway planners can adequately weigh involved construction costs against expected revenues (in terms of quality of service offered). In fact, changes in the European railway market show that this cost awareness argument for performing capacity studies is of growing importance.

The capacity of an infra-element is determined by (a) structural aspects, such as the proposed track layout and the underlying safety system, (b) timing aspects, such as running times and dwelling times of trains as well as the amount of time required for boarding and alighting, and (c) the timetable (precise arrangement of train arrivals and departures in time and space). Structural aspects remain constant for many years ahead, and they are usually known during the planning phase. This is in contrast to the timing aspects as well as the timetable. As for the timing aspects, they are typically unknown during planning stages for two reasons: (1) the future service demand (for example, the expected numbers of passengers traveling by train, and the types of rolling stock to be deployed during operation) is unknown, and (2) external influences (for example, weather conditions and malfunctioning of rolling stock) may cause fluctuations in the (actual) process times. On the other hand, the timetable is usually altered at least once a year, and, hence, it is not practical to use a particular timetable to assess the infrastructure capacity.

The uncertainty about the timing aspects is addressed by letting the corresponding variables be stochastic, and in order to obtain a capacity measurement that is insensitive to a particular timetable, we apply “Wakob’s razor”: (1) we let trains arrive to the infra-element with interarrival time 0, and (2) we assume that initially there are infinitely many trains waiting in reservoirs to enter the infra-element. This saturation type of approach was introduced in [15], while its effectiveness in practice was demonstrated in De Kort et al. [10]. Apart from avoiding the specification of a particular timetable, Wakob’s razor has the benefit that the measured capacity is independent of stochastic perturbations of the “outer” system, that is, the cause of any observed delay has to be the layout of the infra-element.

In order to model the infra-element according to steps (1) and (2) above, we determine N_sys, the maximal number of train movements that can be executed in T time units (e.g., T=60 minutes) with probability p. Hence, we consider the capacity to be sufficient if and only if N_sys⩾N_intended. A mathematical framework most suitable for the analysis of transportation systems, such as train networks, is the (max,+) algebra (to be introduced presently), and we model dynamics of the train system (including the impact of the underlying safety system) by a set of stochastic difference equations that are linear in the (max,+) algebra. Heidergott and De Vries [7] provide a state-of-the-art overview of the applications of (max,+) techniques to the control of train networks.

Predominant in railway capacity planning literature are stochastic models capturing uncertainties with respect to the precise traffic load. Here, random travel times model an unspecified timetable, see e.g. Schwanhäußer [13], Wakob [15], Wendler [16] and Huisman and Boucherie [8]. By contrast, methods dealing with stochastic fluctuations, such as delays, typically assume a specific traffic load or even a fixed timetable; see e.g. Middelkoop and Bouwman [12], Florio and Mussone [5], Barter [3] and Kraft [11].

The approach most closely related to ours is that of Wakob [15]. More specifically, Wakob studies the impact of track layouts on capacity while assuming that trains arrive in a completely random way (no timetable). To this end, particular infra-elements are isolated and analyzed by a queueing theory-based approach. Subsequently, the obtained performances of the isolated infra-elements are aggregated according to an overall scheme to yield the capacity of entire track facilities, such as stations. The adopted performance indicator is based on total waiting times. Unfortunately, these waiting times are abstract entities and are not related to waiting times that may occur in the real system, which makes it difficult to compare outcomes of the method to real-life observations (see [10]). Furthermore, Wakob’s approach does not deal with stochastic fluctuations, such as delays.

The approach we present in the paper combines the main capabilities of all above mentioned methods. That is, our method simultaneously deals with stochastic fluctuations and uncertainties in service demand while revealing the impact of a given track layout on capacity. In addition, the adopted performance indicator is easy to understand because it has a clear and obvious correspondence to daily practice (namely, the proportion of trains arriving in time).

The paper is organized as follows. Section 2 provides a brief introduction to (max,+) algebra. In Section 3, we introduce a generic infra-element and we derive the difference equations that describe the temporal dynamic behavior of this element. In Section 4, we formulate the optimization problem and provide a solution procedure. In Section 5, we apply our approach to a real-life situation: a capacity assessment for the new high-speed railway line in The Netherlands. Section 6 concludes the paper.