Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The DB Netz AG is the most important railway infrastructure company in Germany and operates a railway network with a total length of about 34,000 km and more than 5,000 stations. This is the greatest and most complex network in Europe. 48,000 employees make about 30,000 train runs daily possible. The DB Netz AG has three mayor tasks to solve. At the one hand there is the signaling and control of the trains. This is managed locally in signal towers or centrally in operations centers. At the other hand the huge network has to be maintained and repaired permanently and the network has to be developed. The third task is to generate timetables to sell train-paths to the customers, both long-term and short-term.

Forecasts say that there will be a big growth in freight traffic by over 60 % during the next twenty years. To handle the predicted traffic volume in future it is necessary to develop and expand the network and to optimize the use of the existing infrastructure (see [3]). An optimized use of the infrastructure can be achieved if for example the train’s velocity is harmonized or if the demand can be guided to less loaded routes and time.

The capacity management at DB Netz contains the forecast, capacity-analysis and capacity-design and is a continuous process for the development of the infrastructure. The main challenge results from the extensive need of time from planning till commissioning of the infrastructure on the one hand and the dynamically changing infrastructure requirements.

A central element of the capacity-management is a long-term railroad schedule. Based on the forecasts and concepts, for example the long-distance, local rail systems and freight-trains, a real timetable is generated and could be valid for example in six years. This special timetable will not be used in reality then but is an assumption for a possible schedule in future and is used as a base for the capacity-analysis. Although it is planned long-term, all important and relevant conditions are considered, e.g. cadences or connections. In summary the long-term schedule and its restrictions lead to the necessary infrastructure.

The long-term railroad schedule ensures more customer focused train-paths in passenger and freight transport and allows a growth in traffic because the need to develop infrastructure is early identified. So the network capacity and the efficiency will be increased as well as quality of the train-paths is considered and improved.

The creation of a timetable for the biggest European railway-network is naturally complex and time-consuming so there are efforts to aid the personnel by data processing or automate this process in essential parts. In the next section a program-system will be introduced which was designed to help in this topic.

2 Program-System TAKT

The software-system TAKT is a development of the professorship “Verkehrsstroemungslehre” at the TU Dresden [1]. It has been upgraded an enhanced during the last years in many research projects in cooperation with the DB Netz AG. TAKT automatically generates and improves timetables for complex railway networks on the base of periodic event scheduling problems (PESPFootnote 1) by using specialized algorithms. After providing the input data a timetable is calculated automatically and can be evaluated in detail afterwards by the user.

TAKT consist of several modules, which are connected by interfaces as shown in Fig. 1 and will be described next.

Fig. 1
figure 1

Modules of the program-system TAKT

Full size image

The ROUTER prepares the input data for the generation of timetables. On the one hand an infrastructure database is necessary and on the other hand modeltrains for the timetable have to be defined. A modeltrain corresponds for example to a line of a long-distance train. The ROUTER consists of an innovative routing-algorithm and a calculator for the travel time and produces the modeltrains. The routing-algorithm finds a well-suited train-path in the network automatically.

All modeltrains with their characteristics and further conditions like connections for the passengers are called plan of operation. This is the base for the PESP-Solver, which schedules a feasible strictly periodic timetable. To get an enormous speed-up, the PESP is converted to a satisfiability-problem (SAT). After the solution with an up to date SAT-Solver, the result is retransformed and gives the train’s feasible arrival and departure times. This transfomation provides practically useful solutions in appropriate runtimes which former solvers could not achieve.

The Optimizer reduces the waiting time for the passengers in the network. On the one hand there are passengers in the trains who don’t want to wait too long at stations because of connections. On the other hand there are passengers at the stations who want to change trains and therefore a correspondence time is needed. All waiting minutes are weighted and only important connections will be arranged to reduce the total amount of waiting time in the railway network.

The FlowMaster generates as much as possible freight train-paths to an existing periodic timetable. This is done by connecting parts of a train-path until whole train paths between origin and destination are finished and no more capacity is left. Origins and destinations can be for instance great harbours or freight-stations.

In summary the program-system TAKT can strongly aid the employees at DB Netz to create a long-term timetable for the capacity management. The next section intoduces and explains the base model PESP.

3 Periodic Event Scheduling Problem

The automatic timetabling in the program-system TAKT is based on a periodic event network (see [2] for more details). Before introducing the PESP it is necessary to characterize the periodic event network and to differentiate it from a non-periodic event network. In the periodic event network important events are represented by a node, for example the train’s arrival or departure at a station. The nodes in the network are connected with edges which represent a time span. There are for example edges for the travelling time or distance spacing. The periodic event network distances from the infrastructure and deals only with the modeltrain’s relations in time. With the network’s nodes and edges all processes and conditions in railway operation can be described. Figure 2 shows two events in a non-periodic network which are connected by an edge.

Fig. 2
figure 2

Two events in a non-periodic network

Full size image

A solution is feasible if the points in time \(T_{i}\) and \(T_{j}\) are between the time span \([t_{min}; t_{max}]\). Every point in time takes place exactly once. Thus the two events’ order is fixed, \(T_{j}\) always follows \(T_{i}\). For the periodic case we have to define a new variable to the event network, the modulo parameter \(z\). It has to be an integer value. In Fig. 3 two periodic events with one restriction are displayed.

Fig. 3
figure 3

Two events in a periodic network

Full size image

In the periodic case every event k is repeated indefinitely often at the points in time \(T_{k} + z \cdot t_{T}\), so the condition must also be fulfilled in every period. So a feasible solution has to fulfill the advanced inequality in Fig. 3.

\(z_{ij}\) is the modulo operator of condition between event i and j. The events’ order is no longer fixed and will be determined by the modulo operator. In the periodic event scheduling problem has to be decided if there is a feasible schedule \(\mathbf {T}\) which assigns a point in time to every event so that all restrictions are met. Failing this the system is infeasible. Degrees of freedom in this model are the time spans on the conditions and the events’ order.

On the base of the periodic network the PESP-Solver calculates a periodic timetable or finds infeasibility. However, this means not that there is no possible schedule for the plan of operation. The PESP-Solver diagnoses which events and restrictions cannot be fulfilled automatically. There is the opportunity to extend some conditions, for instance the stop time of particular modeltrains, to achieve a feasible timetable. Increasing a stop time in a station can be used to change the order of trains for example. The process of widening some conditions is repeated iteratively until a feasible solution is found or no expandable condition is in the set of restrictions which cannot be fulfilled. Then there would be no feasible schedule possible.

Due to the internal transformation from PESP to a satisfiability problem an enormous advantages in the solver’s run time were possible. The program-system TAKT provides practically useful solutions in appropriate runtimes as can be seen in the next section.

4 Example

In this section some results of a typical long-term railroad schedule are presented. The investigated area covers two of the 7 regional districts of DB Netz and is shown in Fig. 4.

Fig. 4
figure 4

The investigated area

Full size image

All together are in this area more than 4,000 stations and stops, 43,000 tracks and the total length of the infrastructure is about 18,000 km. Within this network 204 lines run (12 long distance, 176 regional and 16 local). The resulting periodic network contains 2,811 nodes and about 14,000 edges. To solve the PESP and get a feasible strictly periodic schedule the PESP-Solver needs 176 iterations to widen conditions and a total run time of only 3 hours. For comparison: If an average employee of DB Netz manually constructed a comparable timetable manually, this would last several weeks!

Figure 5 shows the train graph of a train running from Stralsund via Berlin and Halle/Saale to Erfurt.

Fig. 5
figure 5

Example timetable

Full size image

5 Summary

The long-term railroad schedule is an effective instrument for capacity management at DB Netz and ensures more customer focused train-paths in passenger and freight transport. It identifies the need to develop infrastructure early and allows to adapt the infrastructure to a growing traffic.

The program-system TAKT is a great support for the creation of a long-term schedule because it saves a lot of time due to helpful automations with innovative components. It provides practically useful solutions in appropriate runtimes and improves the long-term schedule’s quality substancially. Due to an easy variation of parameters and the automatic solvers it is initially possible for DB Netz to create and optimize more than one variant of a timetable for great areas.