Keywords

Introduction

In recent years, many western European railway operators have altered the traditional planning process by including strategic timetabling. These strategic timetables, which are constructed ten to twenty years in advance, are used as input for further strategic and tactical planning steps, including network design. In this paper, we present a railway network design problem where the demand is derived from a strategic timetable. Even though the first strategic timetable has been constructed in Switzerland in the 1980s, the topic has been picked up by academic research only recently, e.g. in [4] or [7]. More research has been conducted focusing on tactical timetables (refer to Chaps. 5 and 6 of [1, 2]).

Railway network design has also been studied in a few publications, including timetable-independent approaches like [6] or microscopic approaches without an implementation like [5]. The integration of these two steps however leaves room for further research. We try to reduce the gap with this paper. Since the strategic timetable is constructed many years in advance, it is subject to uncertainty. We address this uncertainty by using a robust optimization approach based on timetable families. Robust optimization in railway analysis is common, but it is usually applied to the tactical and operational planning stages like tactical timetabling or crew and vehicle scheduling [3].

The remainder of this short paper is structured as follows: in Section “Methodology”, we describe the modelling of the network and the input timetable, including a focus on the robust modelling in Section “Considering Robustness”. The key properties of the optimization model including the constraints dealing with the robust optimization are presented in Section “Optimization Model”. In Section “Case Study”, we provide details about the implementation and the case study before concluding the paper in Section “Conclusion and Outlook”.

Methodology

Modeling Approach

In our model, we start with a given strategic timetable and use it to calculate a cost-optimal network on which the timetable can be operated. To gain some flexibility for optimization, the timetable is relaxed in several ways:

  • the trains can be routed freely from their origin to their destination nodes, with an option to define via-nodes

  • only time bounds for the departure at the origin node and the arrival at the destination node are considered.

Using these relaxations, we derive an operational concept which includes a list of trains with start and destination nodes and time bounds. It also includes a list of timing-related connections between pairs of trains which model either frequencies or transfers.

The network is defined as a multi-graph G = (N, A) featuring nodes \(i \in N\) and arcs \((i,j,tr) \in A\). Nodes represent stations or junctions and provide the opportunity to change from one arc to another. We also consider node links (i, a, b), which connect two arcs (a, i, tr) and (i, b, tr) with each other, allowing trains to travel from node a to node b through node i. We do not consider limited node capacities at the moment.

The arcs (i, j, tr) are identified by the nodes which they connect (i and j) and the track number tr. One arc represents one track, so multi-track sections are modelled by several parallel arcs. This allows us to model both single-track and multi-track sections. The inclusion of an arc into the solution is controlled by the decision variable \(y_{i,j,tr}\). Similar decision variables \(l_{i,a,b}\) exist for node links. Both are associated with building costs and are part of the objective function. To estimate the capacity used on a section, we use train-type and train-sequence-dependent minimal headway times (MHT), which have to be respected between two trains that use the same track. In case the capacity is insufficient, the model features three options to extend capacity on arcs:

  • including more parallel arcs

  • reducing travel times

  • reducing headway times.

The last two are modelled using reduction variables \(r^{time}\) and \(r^{MHT}\), which are also included in the objective function and come with associated costs \(c^{time}\) and \(c^{MHT}\) for each unit of time reduction.

Considering Robustness

Because of the long planning horizon and the resulting difficulties to estimate demand and political decisions influencing the timetable, strategic timetables are subject to uncertainties. Since the network designed by our model is based on a strategic timetable, it needs to account for possible changes to this input timetable. We model the uncertain timetables by defining timetable families, which comprise several discrete timetable scenarios with individual lists of trains and connections. Besides, the demand within one scenario is variable.

By defining timetable families, we can model slightly different timetable concepts which may vary in the trains or the timing relationships. We can then calculate a network which enables a specified percentage of the timetable family. By observing this scenario coverage share, we can calculate both full robust networks, which cover all given scenarios and light robust networks, which cover only a certain share of the scenarios.

The variable demand within one scenario is modelled with optional trains. They can be considered in different ways:

  • only activate optional trains if they don’t require additional infrastructure

  • add a penalty to the objective function if a train is not activated and create a trade-off between the capacity to run additional trains and the costs for additional infrastructure

  • randomly select a random number of trains from the optional set before the optimization, which then become mandatory.

The optional trains can also be used to evaluate the remaining capacity on the optimized network and to quantify the robustness towards changes in the input timetable.

Optimization Model

We model the timetable-based railway network design problem as a mixed-integer linear program. Our objective function (60.1) minimises infrastructure costs, which contains building costs \(f_{i,j,tr}\) and \(f_{i,a,b}\) for arcs and node links as well as reduction costs \(c^{time}_{i,j}\) and \(c^{MHT}_{i,j}\) for reductions of travel and headway times. It also includes penalty terms which are activated if a scenario or an optional train is not included in the final solution. This is modelled using the decision variables \(o_{s}^{szo}\) for scenarios and \(o_{k}^{train}\) for trains.

$$\begin{aligned} min \sum \limits _{(i,j,tr)\in A} f_{i,j,tr}y_{i,j,tr} + \sum \limits _{(i,a,b)\in L} f_{i,a,b}l_{i,a,b} + \sum \limits _{(i,j)\in A_{l}} c_{i,j}^{time}r_{i,j}^{time} \nonumber \\ \quad + \sum \limits _{(i,j)\in A_{l}} c_{i,j}^{mht}r_{i,j}^{mht} + \sum \limits _{k \in K}pen_{k}(1-o_{k}^{train}) + \sum \limits _{s\in S}pen_{s}(1-o_{s}^{szo}) \end{aligned}$$
(60.1)

Because we integrate network design and strategic timetabling as well as observe railway-specific capacity measures by using minimal headway times, the constraint set is extensive and an explanation of the full model would exceed the scope of this short paper. Therefore, we will describe only the constraints dealing with the robustness consideration and leave a full description for a future paper.

$$\begin{aligned} \sum \limits _{s\in S} \frac{1}{n_{s}}o_{s}^{szo} \ge s_{s} \end{aligned}$$
(60.2)
$$\begin{aligned} o_{s}^{szo} = 1 \quad \forall s \in S_{mand} \end{aligned}$$
(60.3)
$$\begin{aligned} \sum \limits _{(k,p) \in P_{k}} p_{k,p} = o_{k}^{train} \cdot o_{s}^{szo} \quad \forall k \in K \end{aligned}$$
(60.4)
$$\begin{aligned} o_{k}^{train} = o_{s}^{szo} \quad \forall k \in K_{mand,s}, \quad \forall s \in S \end{aligned}$$
(60.5)
$$\begin{aligned} \sum \limits _{k \in K} o_{k}^{train} \ge n_{k,mand,s} + n_{k,opt,demand,s} \quad \forall s \in S \end{aligned}$$
(60.6)

The most important aspect of our robust optimization approach, the scenario coverage share \(s_{s}\), is controlled by (60.2), while (60.3) allows to define certain scenarios as mandatory. To route the trains through the network, we use pre-generated paths for each train. These paths have to include all defined via-nodes for a train and must fulfil the travel time requirements given by the operational concept. Constraint (60.4) makes sure that exactly one path is chosen for each train if both the scenario and the train itself are active. It is important to note that this constraint is linearised in the code. If the correspondent scenario is active, all mandatory trains of this scenario have to be active as well, which is ensured by (60.5). As mentioned in Section “Considering Robustness”, we have an option to request a certain amount of optional trains to be included. This is done by constraint (60.6).

Further constraints cover the standard network design aspects by ensuring that trains travel only on arcs and node links included in the solution networks. The integrated timetabling is done by constraints ensuring that given time bounds, travel times, required frequencies and transfer times and minimal headway times are correctly observed. The frequency and transfer constraints are only active if the correspondent scenario is activated. The correct headway time to be observed depends on the train types and the sequence of two trains following each other.

The results include the cost-optimal network with all the arcs and node links necessary to operate the requested timetable scenarios. They also include the routing of each train and a feasible macroscopic timetable for each scenario. Note, that the timetable is not yet optimized. However, it is possible to optimize the timetable in a later optimization step, e.g. by minimizing the total travel time while fixing the infrastructure.

Case Study

To demonstrate the model, prove its functionality and identify performance issues, the optimization model has been tested on a small case study. Several test cases and scenarios have been derived from drafts for the Deutschlandtakt, the strategic timetable concept for Germany. The optimization model has been implemented in Python 3.8 and solved by Gurobi v9.5.1. using a laptop featuring an Intel Core i7-8565U CPU @1.80 GHZ and 16 GB of RAM. The computational results for a test case with ten scenarios are shown in Table 60.1. The scenarios vary in the number, type and route of trains (between 22 and 48) and the amount of frequency and transfer constraints (between 0 and 56). The resulting network has been calculated for varying coverage percentages.

Table 60.1 Computational results
Full size table

As expected, the infrastructure costs increase with the scenario coverage. It can also be observed, that the demanded coverage share has a significant impact on the model’s performance and that computation times are rather long, given that the shown example covers only about 12 nodes and 20 arcs. Even though the model is associated with strategic planning, the current runtimes do not allow the calculation of realistically sized instances within reasonable time, especially when multiple scenarios are considered. Therefore, a heuristic approach for calculating a network covering all scenarios has been developed. First, cost-optimal networks are calculated for each timetable scenario independently. Using an adapted version of the optimization model, the feasibility of each timetable scenario on each unique infrastructure resulting from the first step is evaluated. In case no network topology covers all scenarios, the infrastructure covering the largest number of timetable scenarios is then iteratively extended to cover the unfulfilled timetable scenarios. This approach has proven to be faster than the complete optimization model, but still leaves room for further improvements.

Conclusion and Outlook

In this short paper, we gave an overview of our research concerning the integration of strategic railway timetabling and railway network design. We motivated the problem at hand and identified a gap in the literature. We propose a mixed-integer linear program which calculates a cost-optimal railway network based on demand given as an operational concept derived from a strategic timetable, featuring a list of trains and important timetabling aspects such as frequencies and transfers. The model incorporates railway-specific details like track-based routing and a realistic capacity estimation using minimal headway times on both single- and double-track lines. During the optimization, a feasible timetable respecting the key properties given in the operational concept is designed. Further research will focus on performance improvements by studying both heuristic approaches and decomposition techniques. Besides that, an evaluation of the remaining capacity of the networks is planned as well as a sensitivity analysis of the network towards changes in the input parameters.