1 Introduction

Timetabling and, intimately related, track allocation are two of the most challenging planning problems for every railway infrastructure provider. Due to the ongoing deregulation of the transportation market in Europe, new railway undertakings are entering the market. This leads to an increase in train path requests and thus to a higher number of scheduling conflicts among them. The goal of timetabling and track allocation is to resolve these conflicts as much as possible by producing a feasible, i.e., conflict free, timetable that achieves a maximal utilization of the railway infrastructure.

From a mathematical point of view, the optimal track allocation problem can in principle be easily stated as a multi-commodity flow problem in an extremely large space-time network with certain additional constraints, see, e.g., Borndörfer and Schlechte (2007). The problem is well investigated in the literature, but it is only a very recent development that problems of sizes that are, say, somewhat relevant in practice started to become tractable. The literature is therefore currently divided into two branches. One branch is devoted to the study of simplified macroscopic models, considering mainly corridor scenarios, see Cai and Goh (1994), Brännlund et al. (1998), Caprara et al. (2002), Borndörfer et al. (2006), Cacchiani (2007), Borndörfer and Schlechte (2007), Cacchiani et al. (2008), Fischer et al. (2008). The other branch investigates routing problems through individual stations on a more detailed level, see Zwaneveld et al. (1996), Caimi et al. (2004), Lusby et al. (2006), Caprara et al. (2007). There are only a few works on the interplay between both modeling approaches. In Kettner et al. (2003) a concept for an integration of microscopic and macroscopic models is presented and implemented in a system called NEMO, which is actually used by the Austrian Railways. In contrast to our approach, however, the NEMO transformation is based solely on the network topology (it does not depend on train routes), which limits the aggregation potential. Caimi (2009) develops in his thesis a top-down planning and decomposition strategy that is based on empirical knowledge of experienced planners in Switzerland. The above mentioned literature focuses mainly on the strategic or tactical planning level. For operational variants of this problem, namely rescheduling and real time management, we refer to Jespersen-Groth et al. (2009) and Corman et al. (2010).

We demonstrate in this paper the application of a new bottom-up planning approach that is based on an automatic simplification of complex microscopic railway infrastructure data. This is done at the example of the Simplon railway corridor. The term “microscopic” means that the starting data describes the infrastructure and the train driving dynamics on a very detailed level that is suitable to simulate the railway traffic accurately, i.e., with exact track and platform assignments and with a precise treatment of switches, signals, and vehicle dynamics. This data is condensed into much fewer constituents, namely, only those that are relevant for planning by means of a “macrotization” that makes the problem amenable to exact integer programming optimization. The timetable that is constructed at this level is finally retransformed to the microscopic level in such a way that it remains operationally feasible. It is, of course, crucial to retain as many degrees of freedom as possible in the construction of the macroscopic network. The micro-macro network aggregation algorithm is implemented in a tool called netcast, see Schlechte et al. (2011), the optimization algorithm in a tool called TS-OPT, see Borndörfer et al. (2009).

The transition between microscopic and macroscopic planning in our approach may seem complicated and difficult at first sight, but it is well justified. In fact, testing the operational feasibility of timetables and train paths allocations is one of the prime motivations behind the development of railway simulation systems. In the last 20 years several sophisticated programs of this type were developed, see Wendler (1999), Gröger (2002), Hürlimann (2001), Siefer and Radtke (2005). Almost all railway companies use them to support their operations and their planning processes by experimentally evaluating the interactions between large numbers of trains in a timetable, the stability of a timetable with respect to delays, and the effects of changes in the infrastructure or the rolling stock pool. Industrial simulation tools are therefore widely accepted for their accurate reproduction of the operation of a railway system. If a timetable or train path allocation “works” in one of them, it can be considered to be operable. We take this point of view in this study, and use the synchronous simulation system OpenTrack, that was developed at the ETH Zurich, see Hürlimann (2001), as the basis of our approach; see also Hansen and Pachl (2008) for a wide comparison of synchronous and asynchronous railway simulation methods. Our microscopic network consists of exported OpenTrack data, and OpenTrack was also used to verify the feasibility of our timetables and track allocations.

An exact timetable optimization at the microscopic level is completely out of reach as the resulting models become simply too large. However, it would also not be appropriate for many planning purposes. Microscopic data does not have to be considered on a strategic or on a tactical level. Information about train acceleration and braking, or the operation of signals can be compressed into running and minimal headway time information, segments of tracks can often be amalgamated, etc. In similar areas, e.g., in line planning, see Borndörfer et al. (2007), or in periodic timetabling, see Liebchen (2006), simplified models of the railway infrastructure and approximations of event times, mostly in minutes, are commonly used with success. We also use a macroscopic model of the railway system in a standardized format, for which documentation and test instances mapping a part of the German long distance network are freely available in the TTPlib library, see Erol et al. (2008). This aggregation brings the network size to a manageable level that allows for a simultaneous optimization of many train paths; it must of course be done in a conservative way, such that any timetable that works on the macroscopic level can be translated back to the microscopic setting. This can be done by working with appropriate buffers and is described in detail in a companion paper, see Schlechte et al. (2011).

The contribution of this paper is to demonstrate the viability of a bottom-up micro-macro transformation approach on a real-world example, the Simplon corridor between Switzerland and Italy. In addition, we study the effects of variations in important parameters such as time discretization. The paper is structured as follows. The problem setting is described in Sect. 2. Section 3 provides a capacity analysis of the Simplon tunnel using state-of-the-art optimization techniques.

2 The Simplon corridor

There are only two north-south railway connections through the Alps in Switzerland, namely, the Gotthard corridor and the Lötschberg-Simplon corridor. The Simplon connects Switzerland and Italy and is therefore of strategic importance in particular for the international railway freight traffic. It has a length of approximately 45 km and 12 stations. This sounds like a rather small network at first glance, but the routing possibilities at the terminals Brig and Domodossola, the routing possibilities in the intermediate stations Iselle and Varzo, and a rather unusual slalom routing for certain types of cargo trains lead to very complex planning situations. Thus, this network is perfectly qualified to provide a proof of concept for our integrated aggregation and optimization approach. An OpenTrack network data export for the part from Brig (BR) in Switzerland to Domodossola (DO) in Italy was provided by the Schweizerische Bundesbahnen (SBB). The microscopic network consists of 1154 nodes and 1831 arcs including 223 signals, see Fig. 1.

Fig. 1
figure 1

Microscopic representation of the Simplon corridor with zoom on station Iselle as given by the railway simulator OpenTrack

Full size image

This data was macrotized in two steps. The first step is resort to standardized train driving dynamics that induce the definition of a handful of train types; these are used to compute standardized driving and headway times. This allows to amalgamate larger parts of the microscopic infrastructure network to a macroscopic network in the second step. The following subsections describe this process for the Simplon application.

2.1 Train types

The decision which train types to consider is a crucial point, because a more detailed consideration of driving dynamics allows the construction of tighter schedules. For a capacity analysis, however, a modeling strategy is appropriate that captures the main characteristics, but abstracts from minor special characteristics of individual trains. We use six different train types, two for passenger trains and four for freight trains.

The different, but invariable stopping patterns of regional trains (R) and intercity trains (EC) and their very different driving dynamics (due to the different engines used) result in considerable differences in running and headway times for such trains. They are therefore considered as two train types. We do, however, ignore different train compositions, i.e., in length and in the number of wagons. Hence, R and EC are the two types of passenger trains that we consider.

There is a large number of different types of freight trains that traverse the Simplon. In order to determine the theoretical capacity of the corridor, SBB pointed out four prototypes which were considered to represent the operating freight trains well enough on a strategic or tactical planning level. In fact, due to conservative assumptions on the weight of the trains the considered microscopic running times are often overestimated, i.e., using simplified freight train types underestimates the corridor capacity.

GV Auto are special train services that transport passengers and their automobiles from Brig (BR) to the next station after the Simplon tunnel, which is Iselle (IS). There these trains cross all other tracks to reach an isolated ramp. Because of these unique routing requirements at Iselle, we consider them as belonging to an individual freight train type on their own.

GV RoLa and GV SIM are train types that transport freight vehicles (GV RoLa) and containers (GV SIM). They have a larger height and width than standard freight trains, and they can use only one of the tracks in the tunnel between Iselle and Preglia. This results in a so-called “slalom route” that these trains have to take from Brig. In Iselle they have to change to the right trackFootnote 1 until Preglia, i.e., it is possible to change again to the standard side in the intermediate station Varzo to let other trains pass. Furthermore, the running times of these trains types, especially for the direction from Brig to Domodossola, differ significantly, namely, a GV RoLa needs about 7 minutes more than a GV SIM. They also use different routes in the area of Domodossola. Thus separate train types GV RoLa and GV SIM are introduced. Finally, GV MTO are standard freight trains which use the standard tracks in the Iselle-Preglia tunnel.

SBB was interested in running additional freight trains through the Simplon such that we concentrated on freight traffic. We assume, in particular, that the passenger trains are given and cannot be changed. Hence the train paths for passenger trains R and EC from Brig to Domodossola and vice versa are fixed. In addition, the GV Auto trains, which are not operated all day, are also fixed. All these trains must, however, be considered with respect to their influence on the remaining traffic, i.e., with respect to their headways and with respect to station capacities. Figure 2 visualizes the distribution of passenger and GV Auto trains, which shows an unequal utilization by those trains during the day.

Fig. 2
figure 2

Given distribution of passenger and GV Auto trains in the Simplon corridor for both directions

Full size image

2.2 Network aggregation

The train types introduced in Sect. 2.1 can run on 28 different routes. The routes differ in their stopping pattern and in various ways to pass through Varzo. These routes are the basis of the aggregation of the microscopic network. They partition the network into segments, on which driving and headway times can be computed individually. In other words, if a train route runs on a track segment and no other routes cross, one can compute the parameters that are relevant for a track allocation on this segment beforehand, and compress the segment. This is the key idea of our micro-macro transformation approach.

Clearly, the routes meet at the stations, such that the macroscopic network must necessarily contain a node for each of the twelve stations. Some more macroscopic pseudo nodes are needed to model all train route interactions correctly, i.e., divergences, convergences, and crossings. Applying the micro-macro transformation algorithm of netcast described in Schlechte et al. (2011) compresses the original microscopic network with 1154 nodes and 1831 arcs to a macroscopic network with only 55 nodes and 87 tracks. 32 of these nodes are pseudo stations. Most of them are located directly in the front area of stations. The other 23 nodes are possible start, end, or waiting nodes along the corridor.

This automatically constructed network was further aggregated in a second step by applying some reductions that are not yet implemented in netcast. We kept only those pseudo stations that handle crossing conflicts, namely, for GV Auto on the route from Brig to Iselle and those for a detailed modeling of the station Varzo. The reason for this detailed treatment of Varzo is that the routing through this station is a crucial factor for the capacity of the whole corridor. In Varzo the over-width freight trains can pass each other, such that a locking of the entire area between Iselle and Preglia can be avoided for GV SIM and GV RoLa trains from the other direction, when one of them runs through the tunnel. All other potential pseudo nodes were aggregated to the closest station node in a conservative manner, i.e., the headway times for the incident tracks had to be slightly overestimated. This is particularly the case for the large freight hubs at Brig and Domodossola, where more than sufficient tracks are available.

In addition, some nodes that represent different platforms at the same station were aggregated. After these modifications the network consists of 18 stations and 40 tracks. For comparison, we also consider a “traditional” macroscopic network that is solely based on station nodes; clearly, a conservative model based on such an aggregation will employ oversized buffers and therefore waste capacity. Let us list the macroscopic networks, that we constructed using netcast on the basis of microscopic OpenTrack data:

  • network with station area aggregation (18 stations and 40 tracks),

    simplon_big,

  • network with full station aggregation (12 stations and 28 tracks),

    simplon_small.

After some experiments with these networks, the expertise of SBB about the operational conditions in the Simplon corridor led to the introduction of additional technical blocking times for combinations of GV RoLa trains with any other trains in the front area of Domodossola. The headway times of cargo trains were set to a fixed value of some minutes instead of the simulation values in order to guarantee certain departure and arrival distances in the marshaling yard of Brig. We further improved the macroscopic model by adding buffer times for standard headways and headways for the opposite direction. In this way, two more macroscopic networks were generated:

  • network with station area aggregation (18 stations and 40 tracks) and technical times, simplon_tech,

  • network with station area aggregation (18 stations and 40 tracks) and technical and buffer times simplon_buf.

These macroscopic models are tractable by state-of-the-art track allocation methods. We use in this study the optimizer TS-OPT, see Borndörfer et al. (2009) for more information.

2.3 Time discretization

An important point is the impact of different time discretizations on our macroscopic model. Clearly, a coarser treatment of times simplifies the scenario, but must be compensated by large buffer times, which reduces the corridor capacity. We illustrate this trade-off now by means of an example.

Disregarding realistic traffic assumptions, the “most efficient” utilization of a railway infrastructure is to use the fastest train type as much as possible. For the Simplon corridor, this is an EC train. The EC driving times for both directions are listed in Table 1. Let δ be the discretization of all event times of the microscopic model. In our setting, OpenTrack provides these values in seconds. We denote by Δ the fixed parameter to measure all macroscopic time information, e.g., units of 60 seconds. Here, we denote by “running” the time needed by an EC train with respect to the time discretization Δ and by “headway” the technically minimal headway time in δ and Δ, respectively.

Table 1 Running and headway times for EC trains with respect to different time discretizations Δ
Full size table

It can be seen that assuming a coarse discretization Δ in units of 5 minutes, only 12 (\(= \frac{3600}{300}\)) trains can be run in each direction per hour. Choosing Δ smaller than or equal to 12 seconds, the maximum capacity of trains per direction and per hour is theoretically 13 or even 14 (\(= \lfloor{ \frac {3600}{251} } \rfloor\)) in case of Δ=1. The choice of the time discretization has therefore a major influence on the capacity of a macroscopic railway network, as we learned from this very simple example with only two stations, two tracks, and one train type.

2.4 Demand

The capacity of the Simplon corridor is estimated by saturating it with freight trains, that are selected from fictional request sets. To this purpose, we have constructed 16 train request sets listed in Table 2. The first eight request sets cover a four hour time horizon (prefix “4h” in the request set name) either from 8 am to 12 am (suffix “d” for day) or from 0 am to 4 am (suffix “n” for night). The other request sets are used to calculate a timetable for an entire day (24h).Footnote 2

Table 2 Statistics of scenarios for the Simplon case study w.r.t. demand
Full size table

Three of the 4h request sets are called “testplan” (tp), which means that they are used to evaluate the correctness of the micro-macro transformation on the basis of a microscopically feasible timetable that has been generated manually by the authors. The same applies to the three “testplan” request sets that cover the whole day. Some of the test request sets, e.g., 24h-tp-as, have the disadvantage that the requests are not symmetrically distributed with respect to both directions. We therefore distinguish between asymmetric (as) and symmetric (s) request sets, which do not have this drawback.

We also remark that almost all “tp” request sets do not match the train type distribution that is desired by SBB. Namely, traffic demand in practice takes the form that every second request is a GV SIM, while the others are GV RoLa and GV MTO in equal parts. To approximate this characteristic, we generated some more requests using a uniform distribution according to the desired train demand pattern. The resulting request sets are named with the infix “fx”, where x denotes the period time of the freight trains. We remark that we are aware of the fact that in practice traffic demand is not uniformly distributed. However, for the purpose of demonstrating the principal viability of our approach, we deem this data good enough.

3 Capacity analysis

We provide in this section a capacity analysis of the Simplon corridor using our micro-macro aggregation approach. The goal of this study is to saturate the residual capacity of the corridor by running a maximum number of fictitious freight trains (GV MTO, GV SIM, GV RoLa) between the passenger trains (remember the passenger trains are given as fixed).

We remark that there are many side-constraints for such additional trains that we do not consider. Requirements such as desired arrival or departure time windows at certain stations, dwell time requirements, the balance of train traffic in opposite directions, and other constraints are ignored, partly because of lack of data, partly because there is no point for such constraints in an analysis of a theoretical capacity maximum. These considerations are also the reason for using the following simple objective function:

  • a basis value for each scheduled train depending on type and direction,

  • a penalty for deviations from optimal arrival and departure times,

  • and very small penalties for travel time increases or avoidable stops.

We constructed the macroscopic scenarios associated with all request sets and with all four macroscopic networks, namely simplon_small, simplon_big, simplon_tech, and simplon_buf. Furthermore, we varied the time discretization of the model using step sizes of 6, 10, 30, and 60 seconds. The resulting macroscopic track allocation problems were solved using the integer programming based track allocation optimizer TS-OPT, see Borndörfer and Schlechte (2007), the solutions were disaggregated using netcast and verified by OpenTrack. For each run of TS-OPT, a time limit of one day (86400 s) was used. All computations were done on machines with a 3 GHz Intel Quad Core Processor and 8 GB of RAM running Suse-Linux 11.2.

Table 3 lists exemplary solution statistics for all request scenarios and network simplon_big using a discretization of 10 s. The tables gives:

  • number of trains,

  • number of columns of the integer programming formulation,

  • number of rows of the integer programming formulation,

  • optimal value of the linear relaxation (v(lp)),

  • (best) proven upper bound (bbound),

  • (best) objective function value of integral solution (v(ip)),

  • optimality gap in percent,

  • time needed to solve the linear relaxation,

  • the total running time of TS-OPT.

A first important result is that TS-OPT is indeed able to compute a feasible, i.e., microscopic conflict free, train path allocation for all instances within one day. We verified the feasibility of the track allocations by a 24 hour simulation with the microscopic simulation tool OpenTrack. Figure 3 shows an example of a resulting train diagram in OpenTrack with a valid block occupation for request set 24h-tp-as, network simplon_buf, and a discretization of 30 s.

Fig. 3
figure 3

OpenTrack traffic diagram with block occupations for request set 24h-tp-as

Full size image
Table 3 Solutions for network simplon_big using a time discretization of 10 s and a computation time limit of one day
Full size table

The instances are computational tractable because of the significant contraction by the network aggregation algorithm of netcast, see Schlechte et al. (2011), which produces reasonably sized macroscopic models that give rise to reasonably sized track allocation problems.

There is no instance where TS-OPT needs more than 600 MB of main memory, and TS-OPT can therefore compute feasible solutions for almost all problems. This gives evidence that our micro-macro aggregation approach works.

Not every instance could be solved to proven optimality for each network and time setting. But the 4h-requests never took more than three and a half hours to be solved to optimality, and even for the really complex uniformly distributed daily scenarios feasible solutions with small optimality gaps could be computed. Moreover, the instance with the maximum number of train requests (24h-tp-as with 390 train requests) could be solved to optimality for each network and all time discretizations of 30 seconds and more. Table 3 shows that such an instance produces a timetable with 203 trains, which means that 140 freight train paths out of the requested potential 327 train paths are routed in the optimal schedule. This establishes a theoretical capacity of the Simplon corridor of more than 200 trains per day. Adding technical and buffer times in network simplon_buf, it is still possible to schedule 170 trains. This number is almost identical to the saturation in the timetable that is currently in operation and can be taken as an indication of both the accuracy of the model as well as the quality of the current timetable. We can also observe that not every request set produces a saturated timetable that runs between 160 and 200 trains per day. This highlights the fact that the demand, i.e., the number of requested trains of different types and the degrees of freedom in routing them have a crucial effect on the capacity of a corridor.

We also analyzed the effects of different time discretizations. Table 4 gives an overview on the sizes of the resulting track allocation problems for two test instances. We distinguish two different discretization parameters, namely, we denote by dep_steps the step size for train departure events and by wait_steps the step size for train dwell activities, respectively. As expected, problem sizes normallyFootnote 3 decrease with coarser time discretizations, and the same holds for the running times. Anyway, TS-OPT can solve even instances with more than 500.000 variables.

Table 4 Solution statistics for two instances of network simplon_small with different time discretization Δ
Full size table

An exception to the rule—coarser time discretization implies a decrease in problem size—can be observed by comparing the first 30 s and the 60 s instances. This irregularity originates from a different parameter setting with respect to possible departure and waiting times, see Table 4. In the first 30 s discretization scenario a train can only depart at times that are multiples of 150 s, see definition of dep_steps, and the waiting times must be a multiple of five minutes, see definition of wait_steps. That is a rather rough model with limited degrees of freedom. We therefore changed the parameters for the 60 s runs, such that the time steps are narrower and more similar to the 6 s case. We also did 30 s runs with departure and waiting times similar to the 6 s cases, such that the influence of those two parameters could be analyzed. It turns out that there is not only a connection between time discretization and the number of scheduled trains, but there is also an often even stronger connection between departure and waiting time steps and the number of scheduled trains. We therefore also must pay attention to these parameters. We finally remark that the combinatorial complexity and/or the computational tractability of a particular track allocation instance can not be reliably predicted or estimated by looking at simple scenario statistics.

Another important point is the influence of network aggregation on the number of scheduled trains. As shown in Fig. 4, a more detailed network model leads to a major increase in the number of scheduled trains. But by introducing specific headway times, we again loose about 8 % of the trains and an additional 6 % by also considering buffer times.

Fig. 4
figure 4

Comparing the number of scheduled trains for different networks (simplon_) for request set 24h-tp-as using a 60 s time discretization

Full size image

Up to now we only considered the total number of scheduled trains as a measure for the corridor capacity. But it is also important to keep the structure of the computed timetable in mind. Figure 5 shows the train type distribution of the three freight train types for two request sets. This little example is representative for the general observation that the train type distribution associated with uniformly distributed requests is much closer to the desired distribution, see Fig. 5, than that of the requests based on the testplan timetable. The latter timetables feature a higher fraction of GV MTO requests than desired; in fact, these trains do not run on a slalom route in the corridor and are therefore easier to schedule. The higher percentage of GV SIM and GV RoLa trains in the uniformly distributed request sets often leads to bigger problems than that resulting from the testplan request sets, see Table 4.

Fig. 5
figure 5

Distribution of scheduled freight trains for the request sets 24h-tp-as and 24h-f15-s using network simplon_big and a time discretization of 10 s

Full size image

We observed that the majority of timetables contains more trains from Domodossola to Brig than vice versa. This is not surprising as the models do not contain any symmetry constraints. We did, however, try to achieve some balance by manipulating the objective function. Introducing global constraints in order to control the proportion could be an interesting aspect of future work.