An iterative optimization framework for delay management and train scheduling

Abstract

Delay management determines which connections should be maintained in case of a delayed feeder train. Recent delay management models incorporate the limited capacity of the railway infrastructure. These models introduce headway constraints to make sure that safety regulations are satisfied. Unfortunately, these headway constraints cannot capture the full details of the railway infrastructure, especially within the stations. We therefore propose an optimization approach that iteratively solves a macroscopic delay management model on the one hand, and a microscopic train scheduling model on the other hand. The macroscopic model determines which connections to maintain and proposes a disposition timetable. This disposition timetable is then validated microscopically for a bottleneck station of the network, proposing a feasible schedule of railway operations. We evaluate our iterative optimization framework using real-world instances around Utrecht in the Netherlands.

1 Introduction

Most regular train passengers recognize the frustration of missing a connecting train when their feeder train arrives at the transfer station with a small delay. In low-frequency railway systems, missing a connection can have a severe impact on the travel time of the passengers, even if the delay of the incoming train is only small. In such cases, an alternative would be to delay the departure of the connecting train, so that passengers from the delayed train can transfer to the connecting one. If a train waits for passengers from a delayed feeder train, the punctuality will be reduced; if it does not wait, passengers need to wait for the next service connecting to their destination. Determining whether a train should wait for a delayed feeder train or should depart on time is the subject of delay management (DM). Netherlands Railways, the largest passenger operator in the Netherlands, endorses the importance of a reliable railway system and has recently introduced the passenger punctuality as a new performance indicator. The passenger punctuality measures the ratio of passengers who arrive at their destination with a delay smaller than a certain threshold value.

Unfortunately, DM models have not been used in practice so far. An important concern of practitioners is that not all details of the railway infrastructure are taken into account in the models. One way to deal with this legitimate concern is to incorporate details of the infrastructure in the DM models (see e.g. Schachtebeck and Schöbel 2010; Dollevoet et al. 2011). However, another possible direction is followed in this paper. We propose to evaluate the wait–depart decisions determined by the DM model in a microscopic model, where a detailed train schedule is calculated taking into account all details of the infrastructure such as signals and safety system. This latter problem is known as the train scheduling (TS) problem.

Furthermore, we present an iterative approach, where the solutions are adjusted by incorporating information from the TS problem in the DM problem. In this way, we can exploit the optimization models reducing total passenger delays at network level, and have feasible train paths in stations and bottleneck areas.

A similar combination of a macroscopic and microscopic model has been applied successfully to several railway planning problems and for a variety of tasks, as briefly reviewed in what follows. We also provide some background on the DM and TS model individually.

Kettner et al. (2003) propose an iterative micro–macro approach developed for the German railways, for the offline infrastructure planning problem. The approach is based on a combination of two simulation tools (none of which is based on optimization routines): the macroscopic NEMO and the microscopic RailSys. The authors report interesting benefits in terms of data storage, administration and acquisition.

The approach developed in the Netherlands for timetabling purposes is based on a top–down decomposition in which tentative macroscopic timetables are first produced at the higher level and then checked for feasibility on the basis of microscopic models. A well-known example of this approach is given by the Dutch system DONS (see Hooghiemstra et al. 1999), in which CADANS (see Schrijver and Steenbeek 1994) produces cyclic timetables at nation-wide level based on aggregate models of the infrastructure and, successively, STATIONS (see Zwaneveld et al. 2001) optimizes the assignment of platforms and routes to trains by modeling the train routing problem in station areas as a node packing problem.

In Switzerland, Caimi et al. (2009) propose a top–down timetabling approach. Train service intentions are first generated at the higher level and then a detailed network-wide timetable is built at the lower level by decomposing the network in condensation and compensation zones. Condensation zones are dense station areas, in which the TS problem is modeled via a conflict graph (see Caimi 2009), while compensation zones are open tracks between stations, in which the authors focus more on speed optimization aspects. Detailed timetables are produced in each zone almost independently from each other and coordinated by means of time portals.

Delorme et al. (2009) develop a model based on an incompatibility graph of the train route assignment in order to evaluate the macroscopic timetable on a detailed station layout. The objective is to evaluate the timetable stability defined as the ability to absorb secondary delays when dealing with the initial delay of any single train. Even if the authors deal with delays, the variability of train dynamics is not taken into account in their model. The test case is a French railway junction with passenger and freight trains.

Schlechte et al. (2011) introduce an automatic procedure for the computation of macroscopic schedules starting from microscopic schedules. The macroscopic model generated from the detailed level is used to compute optimal train path allocations by linear and integer programming methods such that a sum of utilities is maximized and the minimum headway time between pairs of consecutive trains is respected. The feasibility of the resulting macroscopic schedule is then checked on a detailed level so that there are no conflicting train paths at the level of block signals. The micro–macro transformation is applied to a busy corridor between Italy and Switzerland.

Inspired by the positive results in different but related fields, we dedicated our efforts to couple a macroscopic DM model and a microscopic TS model. In order to provide some background on real-time railway scheduling, we now review the main contributions on the DM and TS problem.

Earlier integer programming formulations of the DM problem were introduced in Suhl et al. (2001) and Schöbel (2001). Further formulations have been recently developed in De Giovanni et al. (2008) and Schöbel (2007). In all of these models, it is assumed that passengers will wait for one cycle time whenever they miss a connection. Dollevoet et al. (2012) relax this assumption and assume that passengers take the fastest route to their destination. They present an integer programming formulation that allows for passenger rerouting and show that the delay is reduced significantly with respect to earlier models. Dollevoet and Huisman (2013) develop several heuristics to solve the DM problem with passenger rerouting.

Other extensions of the classical DM model incorporate the limited infrastructure capacity. Schöbel (2009) proposes to apply headway constraints to model the limited capacity on the tracks. An integer programming formulation that includes these headway constraints and several computational tests are given in Schachtebeck and Schöbel (2010). In Dollevoet et al. (2011), a first attempt to take the limited number of platforms in a station into account is presented.

A related stream of research considers online DM, that investigates incomplete or uncertain information available about the future, that will become fully available at a later stage. Gatto et al. (2007) and Krumke et al. (2011) present a competitive analysis for DM on a single train line. Berger et al. (2011) present an optimization tool that models passengers as a multi-commodity flow and is able to update passenger flows and delay propagation in real time. In the last paper, the stochastic nature of the DM problem is also taken into account.

Simulation is used to evaluate the online performance of several DM strategies by Kliewer and Suhl (2011). In such a simulation, the delays appear dynamically. Every time a new delay appears, wait–depart decisions have to be updated, based only on the delays that have occurred in the past. For problem instances with many trains delayed in this fashion, the authors show that rule-based strategies outperform the repeated application of an offline optimization model. Bauer and Schöbel (2011) study online delay management with less delayed trains and show that the reoptimization approach gives better results than simple dispatching rules for those instances. The amount of delayed trains in Bauer and Schöbel (2011) is comparable to the amount in the instances that we consider in this paper. This justifies the application of offline models in many practical instances and the development of more realistic models for the offline delay management problem. In this paper, we improve an existing offline model for delay management by complementing it with a microscopic TS model.

The DM models described so far are all macroscopic. The detailed characteristics of the railway infrastructure are abstracted to make sure that large parts of the network can be considered at once. Such a global scope is necessary for DM, as the passengers travel through large parts of the network; in fact no DM is known that is able to consider passenger flows at network scale, and a detail greater than macroscopic. However, as a consequence, some of the complications arising from the infrastructure layout cannot be taken directly into account.

On the contrary, the TS problem is to compute precisely the effects of delay propagation and the adjustments of train speed profiles at a microscopic level, by considering the capacity of the infrastructure and the behavior of the signaling system. This requires the definition of a microscopic scheduling problem, in which detailed information about the tracks and the switches is taken into account. This way, all characteristics of the infrastructure can be modeled.

Simulation models (see e.g. Hansen and Pachl 2008 for an overview) proved to be a suitable tool to represent the dynamics of train operations, but they are still limited especially when large stations and heavy traffic are considered, and are based on myopic rules that might result in large delays.

Concerning the optimization models for the TS problem, Törnquist (2012) resorts on heuristic procedures for computing schedules in a short time, compatible with operations. To this end, microscopic detail is considered for the most complex stations. Studies on a test case in Sweden report that for a time horizon of traffic prediction of 90 min, a feasible schedule can be computed within 30 s, even for instances where commercial optimization suites fail in finding a solution.

A fully microscopic model is used in Corman et al. (2011) to model train traffic over a complex and dense area of the Dutch railway network, with up to 100s of trains. A truncated branch and bound procedure (D’Ariano et al. 2007) is used that achieves very often optimal solutions, substantially reducing delay propagation, compared to practice or simple dispatching rules. Building on that result, a bi-level programming is introduced in Corman et al. (2012) that allows control over very large instances, divided into many local areas. A coordination level is in charge of defining constraints at the border of the local areas to ensure a feasible global solution. The bi-level formulation allows to check feasibility and optimality at local and global network levels, leading to a branch and bound procedure that achieves quickly a good solution for up to 1 h of traffic prediction.

Only recently, the DM problem has attracted some attention in the train scheduling literature. D’Ariano et al. (2008) were among the first to take into account effects of passenger connections in microscopic TS models. In Corman et al. (2010), a bi-objective TS model is developed that minimizes the delay of the trains on the one hand and the number of missed connections on the other hand. However, as only the connections and trains within a station area are considered, the global behavior of the passenger flows cannot be fully captured.

For the existing TS approaches, the size of instances solvable within a real-time computation horizon is still smaller (in time horizon or geographical extent) compared to the macroscopic DM models. Moreover, typical objectives of TS models regard the reduction of (possibly weighted) delays and delay propagation, and generally exclude passenger flows. Inclusion of continuous passenger flows would increase further the complexity by taking into account multiple objectives.

This paper presents an iterative optimization framework based on DM and TS models. It closes the gap between the theory on DM on the one hand, and on TS on the other hand. In doing so, the global scope of DM is combined with the high level of detail from TS. In this way, we can exactly evaluate train paths in a TS model using the wait–depart decisions obtained by a DM model. A solution is provided that is microscopically accurate and ready for implementation within common DM models. In this way, we can establish a bridge between optimization of passenger flows at a network level and detailed scheduling of train paths on microscopic infrastructure locally at the stations. To the best of our knowledge, this is the first attempt to consider both levels in an integrated approach. In the framework we propose, the impact of train delay propagation on a macroscopic model is quantified with microscopic detail.

In a macroscopic DM model, we first determine which connections to maintain and derive the departure and arrival times of trains at the stations. Given the connections that should be maintained, these departure and arrival times are then validated using a microscopic TS model. Doing so, we find solutions to the DM problem that respect the limited capacity of the station infrastructure, even for some of the most complicated and densely occupied stations in The Netherlands, and optimize connection plans for minimization of passenger delays. We also discuss how DM models could even result in further decrease of passenger delays, at the expenses of greater detail of representation of train movements.

The remainder of this paper is organized as follows. First, Sect. 2 describes the macroscopic DM model and Sect. 3 the microscopic TS model. Section 4 gives an illustrative example for both models. Then, Sect. 5 shows how these models are coupled in our iterative optimization framework. Section 6 reports the experimental setup to evaluate the framework. Section 7 concludes the paper with remarks on the framework and on the computational results. Further research directions are also outlined for practical applications of the proposed methodology.

2 Delay management model

The central question of the DM models is which connections to maintain in case the railway system faces delays. It is assumed that the original timetable and the passenger demand are known. The passenger data is represented as a set of origin–destination pairs (OD-pairs) $\mathcal{P}.$ Each OD-pair $p\in \mathcal{P}$ represents a group of n _p passengers who want to travel from a common origin station to a destination station at a specified time. Given a set of initial delays, the aim is to determine for each connection whether it should be maintained or not. Besides, a so-called disposition timetable is determined that prescribes the expected departure and arrival times of the trains at each station. Finally, in order to determine the delay exactly, we determine a passenger route that connects the origin and destination for each OD-pair, possibly including transfers at intermediate stations.

The DM problem is commonly modeled with an event–activity network. In this directed graph, the nodes correspond to the events that have to be scheduled and are denoted by $\mathcal{E}.$ We distinguish between departure events $\mathcal{E}_{{\rm dep}}$ and arrival events $\mathcal{E}_{{\rm arr}},$ that correspond to the departure from and the arrival at a station, respectively. For each event $e\in \mathcal{E}$, we denote the time when the event is planned to take place by π _e . The variables π thus denote the timetable as it was planned to be operated. For each event $e\in \mathcal{E}$, the initial delay is denoted by d _e .

The arcs in the graph, denoted by $\mathcal{A}$, represent precedence constraints (or activities) between these events and ensure that a minimal time between the events is respected. We distinguish between driving arcs, waiting arcs and changing arcs. Driving arcs in $\mathcal{A}_{{\rm drive}}$ connect a train’s departure from one station to its arrival at the next station. Waiting arcs connect the arrival of a train at a station to its departure from that same station and make sure that time is available for the passengers to get off and on the train. We denote the set of waiting arcs by $\mathcal{A}_{{\rm wait}}$. Finally, changing arcs, contained in $\mathcal{A}_{{\rm change}}$, allow passengers to transfer from one train to another. Driving and waiting (dwelling) arcs correspond to operational constraints that cannot be neglected. On the contrary, transfer arcs model possible transfers for the passengers. In case of delays, the railway operator can decide to not maintain a transfer. For each activity $a \in \mathcal{A}_{{\rm drive}}\cup \mathcal{A}_{{\rm wait}}\cup \mathcal{A}_{{\rm change}}$, we denote the minimal time required for that activity by L _a .

In order to compute the delay for the passengers correctly, Dollevoet et al. (2012) propose to determine a passenger route for each OD-pair explicitly. In order to do so, the event–activity network is extended with auxiliary events and activities. For each OD-pair in $\mathcal{P}$, a passenger route then corresponds to a unit flow in the event–activity network. For more details on modeling the passenger flows, we refer to Dollevoet et al. (2012).

We are now ready to present part of the integer programming formulation for DM with passenger rerouting. We focus only on the constraints that determine the timetable, as these will be used to couple the DM model to the TS model in Sect. 5. The main decision is which connections to maintain. We therefore introduce a binary decision variable

$$ z_a = \left\{\begin{array}{ll} 1 & \hbox{if connection } a \hbox{ is maintained},\\ 0 & {\rm otherwise}. \end{array}\right. $$

For each event $e\in\mathcal{E},$ we determine the actual time x _e that is in general equal to the planned time π _e plus a delay; the set x _e thus defines the disposition timetable.

For each OD-pair $p \in \mathcal{P}$, we introduce an auxiliary variable T _p that represents the arrival time for passengers in OD-pair p. In order to determine the arrival time for each OD-pair, we determine a unit flow from the origin to the destination through the event–activity network.

The relevant constraints in the integer program then read as follows. (We refer to Dollevoet et al. (2012) for more details on the integer program including the constraints for the passenger flows.)

$$ \min \sum\limits_{p \in {\mathcal{P}}} n_p T_p $$

(1)

such that

$$ x_e \geq \pi_e + d_e,\quad \forall e \in {\mathcal{E}}, $$

(2)

$$ x_e \geq x_{e^{\prime}} + L_a,\quad \forall a=(e^{\prime},e)\in {\mathcal{A}}_{\rm wait} \cup {\mathcal{A}}_{\rm drive}, $$

(3)

$$ M(1-z_a) + x_e \geq x_{e^{\prime}} + L_a,\quad \forall a=(e^{\prime},e)\in {\mathcal{A}}_{\rm change}, $$

(4)

$$ x_e \in {\mathbb{N}},\quad \forall e\in {\mathcal{E}}, $$

(5)

$$ z_a \in \{0,1\},\quad \forall a \in {\mathcal{A}}_{\rm change}. $$

(6)

The objective function (1) is to minimize the weighted sum of the passengers’ arrival times. Here, n _p denotes the weight for OD-pair $p\in \mathcal{P}$ and usually equals the number of passengers in p. The planned arrival times are fixed, so this is equivalent to minimizing the average or total passenger delay. The arrival times are determined by a unit flow through the event–activity network. We have omitted these constraints for brevity. Constraints (2) incorporate the initial delays and make sure that no train departs earlier than planned. Constraints (3) propagate the delay along driving and waiting activities. For maintained connections, constraints (4) propagate the delay from the arriving to the departing train. In these constraints, the parameter M is a sufficiently large number.

3 Train scheduling model

Given the actual train delays, the train scheduling problem is to compute a new feasible schedule compatible with the status of the network, with the signaling system, and the dynamics of trains. Potential conflicts between train paths are detected by a conflict detection procedure for a given period of traffic prediction. In case of fixed block signaling, tracks are divided into block sections; each block section cannot host two trains at the same time. A potential conflict occurs whenever two or more trains require the same block section and a decision on the train order has to be taken. The train that will traverse the block section as second will be held outside the block section by the signaling system. In fact, while this train approaches the occupied block section, first a yellow signal will be shown, prescribing to slow down to an approaching speed (e.g. 40 km/h); and finally the signal just before the block section will show a red signal that prescribes a complete stop before the block section, as long as the preceding train has not exited the block section and a minimum setup time has elapsed. A set of ordering decisions might furthermore result in a deadlock. A deadlock is the situation in which a set of trains is mutually waiting for a train in the set to move, and no movement for the trains in the set is possible.

To model those situations, a microscopic model is required, that has a precision of seconds in modeling the travel times and considers train movements at the level of block sections. This is the level of detail required to model properly the triggers of the safety system and to represent the signal aspects of the signaling system. The final outcome is a detailed schedule of train movements, without deadlock situations, where all potential conflicts have been solved. In this way, precise times can be predicted and delays are estimated accurately.

We use a job shop scheduling model of the TS problem that can be represented as an event–activity network with additional constraints. Mascis and Pacciarelli (2002) show that this so-called alternative graph is a suitable model for the job shop scheduling problem with additional constraints, such as blocking, also occurring in the railway context. The main value of this formulation is the detailed representation of the train traffic, the network topology and the signaling system.

This formulation requires that a sequence of successive block sections is defined for each train. The time required by each train to traverse each block section can be computed in advance, except for a possible additional waiting time between operations in order to solve train conflicts. In the alternative graph model, this results in a chain of operations (passage of a train on a block section, modeled by nodes $n \in N$) and associated precedence constraints (modeled by fixed arcs in Fix), similarly to the event–activity network of the DM problem.

For every potential conflict, a passing order must be defined between the trains, which is modeled in the graph by introducing a suitable pair of alternative arcs (in the set Alt) for each pair of trains traversing a block section, that defines each of the two possible orders between the trains. Those arcs result in minimum headways between different trains, according to the signaling system.

A deadlock-free and conflict-free schedule is finally obtained by selecting one alternative arc from each pair, and updating the speed profile of the trains to the actual aspects of the signaling system (Corman et al. 2011). Formally, the TS problem corresponds to a particular disjunctive program, i.e., a linear program with logical conditions involving operation “or” (∨, disjunction), as follows.

$$ \min t_n - t_0 $$

(7)

such that

$$ t_j - t_i \geq w_{ij},\quad (i,j)\in Fix, $$

(8)

$$ (t_j - t_{\sigma(i)} \geq w_{\sigma(i)j}) \vee (t_i - t_{\sigma(j)} \geq w_{\sigma(j)i}), \quad ((\sigma(i),j),(\sigma(j),i))\in Alt. $$

(9)

In Problem (7)–(9), a variable t _i , for $i=1, \ldots, n-1$, is the start time of operation i and corresponds to the entrance time of a train in the associated block section, similarly to x _e in the DM model. We use σ(i) to refer to the successor of operation i on the route followed by a particular train, i.e., the operation on the block section after i. Moreover, operation 0 is a dummy operation that precedes all the other operations, to give a common temporal reference; and operation n is a dummy operation that follows all the other operations, and is used to keep track of delays, as explained later. In the scheduling model, all t _i are expressed in seconds, while the precision of x _e in the DM model is in minutes.

Fixed constraints in Fix are a general family of constraints associated to characteristic processes of railway operations, as follows.

• Running constraints naturally define a chain of driving operations between operation i of a train, and its successor σ(i) on the path followed by the train. For such driving process, we consider precedence relations of the form t _σ(i) ≥ t _i  + w _{i σ(i)}, where w _{i σ(i)} > 0 is the time required to traverse the block section associated to that operation, at its actual speed profile.

• Dwell constraints at a station model the boarding and alighting of passengers, where w _{i σ(i)} is the minimal time required between the arrival operation and the departure operation of the same train.

• Release constraints of the form t _i  − t ₀ ≥ w _0i relate to operation 0 and represent moreover minimal start time for operation i, i.e., model the entrance time of a train into the area. This is analogous to the π _e in the DM model.

• Due date constraints of the form t _n  − t _i  ≥ w _in relate to operation n and represent a due date for operation i. Such constraints are used to compute the delay associated to train traffic.

• Connection constraints, as defined in the DM problem, fix the departure time of a connected train to be larger than the arrival of a feeder train, plus a given minimum connecting time. These constraints are the changing constraints specified by the DM problem (the variables z _a ). Such connections are normally associated to an arrival event of a train at a station platform, and a successive departure of another train at another platform of the same station.

Differently, the set Alt is disjunctive, i.e., is composed by pairs of alternative constraints, each of them representing an ordering decision between trains. For each pair i and j of operations associated with the entrance of two trains in the same block section, we introduce the disjunction (t _j  − t _σ(i) ≥ w _σ(i)j ) ∨ (t _i  − t _σ(j) ≥ w _σ(j)i ), where w _σ(i)j  > 0 and w _σ(j)i  > 0 are the minimum headway times. Those headway times are a function of a variety of factors, such as the length of the block section, the speed profile of the train, the driver behavior, the length of the train, as specified by the blocking time theory (see e.g. Hansen and Pachl 2008). Finally, running and headway times are a function of the speed profiles of trains, that again depend on the ordering decisions taken. The solutions computed are fully compliant with the operational rules, the dynamics of trains, and the actual signal aspects shown.

A TS solution corresponds to fixing the start time of each operation. The schedule is feasible if it satisfies all conjunctions in Fix and exactly one constraint for each disjunctive pair in Alt, and does not result in positive length cycles. Due to the structure of the arcs (i, n), the (positive) train delay can be computed at a set of relevant points (scheduled stops and the exit of the network). It is interesting to consider the consecutive delay only, i.e., the delay introduced when solving conflicts in the dispatching area, caused by the propagation of the initial delays of late trains to the other trains in the railway area.

A typical objective function of the TS problem is the minimization of the maximum consecutive delay, that can be easily translated to the minimization of the length of the longest path between the dummy nodes 0 and n, i.e., t _n  − t ₀. By providing suitable extra information to the TS problem, the length of the longest path between the dummy nodes 0 and n can also be adapted to a different objective function, of particular interest in this iterative setup. Basically, the DM model provides target event times based on approximate macroscopic event times; in an iterative setting, it is important to minimize the maximum deviation between what DM expects and what TS computes. In principle, this results to minimizing delays that are identified as consecutive by the DM. On the one hand, this consecutive delay is computed based on an imprecise representation of train activities and therefore only approximates the real consecutive delay; on the other hand, such a setup gives interesting directions to limit the deviation between the DM and the TS model, intuitively leading to a faster convergence of the iterative setup, at the expense of a more approximate delay reduction.

4 Illustrative example

Figure 1 gives an illustrative example of the two models of Sects. 2 and 3. In the top part of Fig. 1, two trains V and T are running on a line connecting station P with station Q. Train T stops at both stations, while train V stops only at station Q; thus, at this latter station there is a possibility to enforce a connection between the two trains. The dotted line defines the station area, i.e., a region in which switches connect different tracks, that merge and cross each other. In fact, train T follows the lower path in the network, while train V follows the upper path in the network; both are using the block section b just before station Q. To ensure minimum train separation and safe movements over the network, the fixed-block signaling system is used.

Fig. 1

(top) Network of the illustrative example, (center) macroscopic model used in the DM problem, (bottom) microscopic model used for the area of station Q, in the microscopic model for the TS problem

The middle part of Fig. 1 refers to the macroscopic model used for the DM problem. Events are represented as nodes, and activities in the set $\mathcal{A}$ as arcs connecting them; train V is represented as the upper chain of events (including arrival event A3 and departure event D3), and train T as the lower chain (including A1, D1, A2, D2). More in detail, the graph shows a Wait activity at station P for train T (reported as Wait1), a Drive activity between station P and station Q for train T, and waiting activities at station Q for both trains (reported as Wait3 and Wait2). A connection activity in $\mathcal{A}_{\rm change}$ is also considered, resulting in the arc labeled $Connection\;3 \rightarrow 2.$

The bottom part of Fig. 1 considers instead the microscopic model as used for the TS problem, only for the area around station Q. The trains considered in the example define two chain of nodes and arcs (again, the upper chain for train V and the lower one for train T), plus the two dummy nodes 0 and n. Successive nodes of each train are connected by arcs representing Run activities, plus the two Dwell activities at station Q. The ordering decision on the block section b is modeled by a pair of alternative, dotted arcs, representing the two possible orders between trains. The same connection constraint ($Connection\;3 \rightarrow 2$) as in the DM model is included, constraining train T not to leave station Q before train V has arrived and a minimal time has passed. There are four release arcs, that connect dummy node 0 to the first node of each train, representing the entrance time of each train in the area considered, and to the departure from the stations, modeling the published departure time. Finally, two due date arcs connect the exit of each train from the area considered to dummy node n.

5 DM and TS optimization approach

The previous sections presented the DM and TS models individually. We now introduce the optimization framework that iterates between solving a macroscopic DM problem on the one hand and a microscopic TS problem on the other. We will first give a general overview of the combined system and then an example is presented.

A schematic outline of our optimization framework is presented in Fig. 2. The original timetable and the passenger demands are used as input for the algorithm. The passenger demand is given as a set of OD-pairs $p\in \mathcal{P}$, each of them representing n _p passengers who want to travel from an origin to a destination at a specified time. The timetable prescribes for each arrival and departure at a station at what time and at which platform it should take place. Furthermore, a set of initial delays is given. We assume that only the arrival events in the network have an initial delay. Equivalently, we assume that the initial delays are zero for all departure events.

Fig. 2

Schematic representation of the optimization framework

The upper (macroscopic) part solves a DM problem to determine the connections to be maintained and computes a macroscopic disposition timetable. The DM solution minimizes the total delay for the passengers. In order to compute the passenger delays realistically in our model, we determine a path through the event–activity network for all passengers. In doing so, we can determine the passenger delays more accurately and obtain wait–depart decisions that give less passenger delays in total (see Dollevoet et al. 2012 for more details). Our DM model thus allows passengers to change their routes through the railway network.

The DM solution results in a set of passenger connections that should be maintained (i.e., a set of variables z _a ) and an expected macroscopic timetable (corresponding to a set of event times x _e for all events e). Those variables are used to define a TS problem. To this end, we focus on those stations in the network where the infrastructure capacity is a bottleneck, and the possibility of facing conflicts for the scarcely available infrastructure is the highest.

Each TS problem considers part of the railway network around a station, in order to represent most of the potential train conflicts. The release time for an arriving train $e\in \mathcal{E}_{\rm arr}$ into the area is computed based on the expected arrival time x _e of that train in the DM solution, minus a fixed time τ _e that corresponds to the minimal running time between the entrance of the microscopic network and the arrival at the station platform. Similarly, we associate due dates to departing trains $e\in \mathcal{E}_{\rm dep}$, based on x _e , the expected departure time computed by the DM solution, plus a time τ _e equal to the minimal running time from the platform until the exit of the microscopic network. The set of connections to be maintained, i.e., those for which z _a  = 1, is also used in the TS problem. These transfer activities are added as fixed arcs to the set Fix.

The solution to the TS problem is a set of starting times, one for each operation, that are feasible with regard to the signaling system and the dynamics of trains. In particular, the solution contains starting times for the arrival and departure events $e\in \mathcal{E}$, that are considered in the DM problem. We will denote these starting times by t _e for all $e\in\mathcal{E}$.

This updated plan of operations will in general have conflicts in the station area and propagate some of the delays. The actual arrival and departure times t are going to be different from those original times x considered in the DM model. We thus find a set of deviations $\bar{d}_e=t_e-\pi_e$ for each event $e\in \mathcal{E}$ that is considered in the DM problem of the next iteration. To take these delays into account, we use them in the right hand side of (2): We replace this constraint by

$$ x_e \geq \pi_e + \bar{d}_e = t_e \quad \forall e \in {\mathcal{E}} $$

in the integer program. Recall that x _e defines a lower bound on t _e in the TS problem. Similarly, t _e now defines a lower bound on x _e in the next iteration. The delays of the trains will therefore be monotonically increasing along the iterations, and converge to a solution that matches microscopic feasibility with the macroscopic optimization model.

We next illustrate the steps graphically, referring to Fig. 3. We start from the top–left of Fig. 3, which shows a solution to the DM problem, corresponding to a decision to maintain connection $3 \rightarrow 2$, and a proposed disposition timetable computed at macroscopic level, that corresponds to expected arrival and departure times (respectively, x _A3, x _D3, x _A2, and x _D2) for the two trains of the example reported in Fig. 1.

Fig. 3

Iterative solution approach for the combined DM (left column) and TS (right column) problems. Iterations increase clockwise

We use this solution to define a TS problem, in which only some station area is considered. This is reported in the top-right of Fig. 3. The two trains enter the network at their release times (Release 3 for the upper path corresponding to train V, and Release 2 similarly for the lower path and train T), that are computed based on the expected arrival time (x _A3 and x _A2 respectively) and the fixed times τ _A3 and τ _A2 related to running between the entrance of the microscopic network and the arrival at the station platform. We compute these running times assuming that the trains run at the maximum speed allowed by the plan and the speed limits enforced by the signaling system. Similarly, due dates are computed based on the expected departure time (x _D3 and x _D2) and fixed times τ _D3 and τ _D2 related to running time from the platform to the exit of the microscopic network.

The TS problem is to compute the times of each operation, and orders between trains on shared infrastructure elements, that are represented by alternative arcs. The connections defined by the DM solution are included in the TS problem as fixed arcs. A solution to the TS problem is shown in the bottom-right figure, showing the order $V\rightarrow T$ chosen (i.e., train V precedes train T on block section b). This defines a microscopically feasible arrival time of the trains at the platform (respectively t _A3 and t _A2), and similarly feasible departure times from the platform (t _D3 and t _D2, respectively).

We then use the microscopically feasible times of the TS solution to define a new instance of the DM problem in the bottom-left of Fig. 3. In general there will be a difference between the actual times t and the expected times x that were considered at the previous iteration, as trains might face yellow or red signals to avoid potential conflicts. Those differences result in propagated delays $\bar{d}$, that define new process times for driving and changing activities. Based on these updated data, the DM solution might keep the same set of connections as in the iteration before, or choose for new ones. The resulting solution would be the one shown on the top-left of Fig. 3, leading to another iteration. Convergence is achieved when the macroscopic timetable is microscopically feasible, i.e., when there is full correspondence between the DM and TS plans.

6 Computational experiments

We assess the performance of our optimization framework using real-world instances from the Netherlands. Railway activities in the Netherlands are split between an infrastructure manager (ProRail) on the one hand and several railway operators on the other hand. We obtained detailed information on the infrastructure from ProRail and the timetable and passenger information from Netherlands Railways. Netherlands Railways is the largest passenger operator in the Netherlands and transports over a million passengers per day.

We now first describe the instances that we used to evaluate our optimization framework. Then we present the computational results. In all our experiments, our main objective is minimizing the total passenger delay.

6.1 Instances

The instances consider the railway network that is depicted in Fig. 4. This picture shows a dense part of the railway network including Utrecht Central Station, which due to its central position is the major transportation hub of the Netherlands. The dots in the picture represent larger stations, where passengers have the possibility to transfer from one train to another. Two stations are connected by a line if there is a direct train between them. On most lines, both long distance trains and regional trains are operated with a frequency of 2–4 trains/h. The long distance trains stop at the stations in the picture only. On the contrary, regional trains stop on smaller stations along the line, too. We evaluated our method with a timetable that is purely cyclic. In total, we consider 46 stations. Because there are both long distance trains and regional trains in many directions, the station infrastructure in major stations is utilized heavily, especially in Utrecht Central Station.

Fig. 4

A large and busy part of the Dutch railway network

In order to assess the performance of the optimization framework, we generate a set of delay scenarios and solve the corresponding delay management problem with the proposed optimization framework. We generate two samples: one sample with small initial delays and one with large initial delays. Both samples contain 10 scenarios. We have generated the delay scenarios as follows. In all scenarios, each arrival of a train at a station has a probability of 10 % to be delayed. If an arrival is delayed, the initial delay is uniformly distributed between 1 and 5 min in the sample with small initial delays. Similarly, in the sample with large initial delays, the initial delay is uniformly distributed between 1 and 15 min.

Table 1 Some characteristics of the delay management model

In Table 1, we first present some characteristics of the resulting delay management problem. In total, 377 trains are considered. Together, these correspond to 1,221 departure events, 1,221 arrival events and 1,221 driving arcs. Besides, there are 844 dwell arcs, leading to 2,065 operational activities. Furthermore, the network contains 9,643 possible connections. We consider 7,086 OD-pairs, of which 1,732 have a direct train from their origin to their destination. This shows that 76 % of the OD-pairs should transfer at least once. It turns out that OD-pairs with a direct trip attract much more passengers: Only 20 % of the passengers in the railway network have to transfer.

Fig. 5

Microscopic detail in the area around Utrecht Central Station, and the minor stations at the border of the area

Considering the microscopic validation of the solution of the DM model, we focus on the bottleneck of Utrecht Central Station, that is the station in which the infrastructure is used most heavily. In fact, five main lines arrive and depart from the 14 platforms of Utrecht Central Station, passing through two large interlocking areas at the sides of the station with a total of about a hundred switches. The TS model refers to a railway network that includes the station area of Utrecht Central Station, and about 10 kilometers of the railway lines, as in Fig. 5. The network considered results in train scheduling problems with the characteristics reported in Table 2. The area considered is centered around the main station of Utrecht, and delimited by 5 more minor stations along the lines; trains have a planned stop only in Utrecht Central Station. Compared to the DM problem, for the same time horizon, only the trains passing through the area are considered; anyway, the microscopic level of detail leads to more individual operations considered compared to the macroscopic level, with about 20 operations considered for each train, on average. The amount of ordering decisions increases polynomially with the amount of trains running on the block sections, resulting in 69,400 variables defining the order of trains.

Table 2 Some characteristics of the train scheduling model

6.2 Integration of DM and TS

We evaluate the quality of the wait–depart decisions that are obtained using a DM model that neglects the limited infrastructure capacity. When these wait–depart decisions are implemented in practice, there will be additional delays that the DM model did not take into account. Practitioners are concerned that these delays might deteriorate the quality of the solution. In this section we show that this is not the case: The wait–depart decisions found by the global DM model are of good quality.

To give a general reference of the quality of the wait–depart decisions, we compare the solutions of an optimal DM model to those found with a no-wait policy and those found with a simple dispatching rule (see Dollevoet and Huisman 2013). In a no-wait policy, all trains depart as early as possible. This means that the buffers in the driving and waiting times are consumed to reduce the train delays and that connections are only maintained if the connecting train does not have to wait for the feeder train.

The dispatching rule applies a maximal waiting time t _max. When a feeder train is delayed, one first determines the time required for the connecting train to wait in order to maintain the connection. If this time is smaller than or equal to the maximal waiting time t _max, then the connecting train waits. Otherwise, it departs as early as possible. We selected the value for t _max that minimizes the total passenger delay in the DM model. We found t _max = 2 for the instances with small delays, and t _max = 1 for instances with large delays. This is in line with the values for t _max that are reported in Dollevoet and Huisman (2013).

For all solutions for the DM problem, we apply the TS model to find a timetable that is microscopically feasible. The TS model enforces the connections found in the DM model to be maintained. Given this TS solution, we propagate the delays through the network in order to find a solution that is both macroscopically and microscopically feasible. Doing so, we can compute the exact delays of the trains and of the passengers. The results of this comparison are given in Table 3. In this table, we present the total passenger delay in minutes that is obtained by all three solution methods for DM. The total passenger delay is computed as the average over either 10 small or 10 large instances. The upper three rows report the results in absolute terms, while the lowest three report the results after normalizing by the no-wait solution.

Table 3 Evaluation of the wait–depart decisions for a DM solution with and without capacity considerations, in absolute and relative terms

Considering a standard DM model that neglects infrastructure capacity (Columns 2 and 5), the reduction in passengers delays with respect to a no-wait policy reaches as high as 22.8 and 7.3 % for instances with small and large delays, respectively. This reduction seems promising, but practitioners are concerned that most of this reduction will vanish when the wait–depart decisions are implemented in practice. They argue that the DM model does not determine the delay reduction reliably, as it does not incorporate all details of the infrastructure.

The other columns quantify the delay reduction when the wait–depart decisions are implemented in practice, in a bottleneck of limited infrastructure capacity. Recall that we defined two different setups of the iterative framework, concerning the objective function of the TS problem, in Sect. 3 The first objective minimizes the maximal consecutive delay (TS–Cons). The second one minimizes the deviation of the TS solution with respect to the DM solution (TS–Dev). For both setups, we report the average passenger delay after application of the TS model for the three solution methods for DM. We see in the table that most of the trend in delay reduction is retained even when considering microscopical detail scheduling. For TS–Cons, the delay reduction with respect to no-wait is 19.4 and 5.5 %, respectively. With the other objective TS–Dev, the reduction is 21.7 and 8.3 %. Comparing optimal DM to the dispatching rule, we find similar results. In both cases, we see that most of the delay reduction found in the DM model can still be obtained in practice when the DM model is combined with the TS model.

When we compare the different objectives for the TS model, we see that TS–Cons generally leads to solutions that have less passenger delay (in just one case, slightly bigger). This is a consequence of the precise determination of consecutive delays by the TS–Cons approach, that leads to higher quality in the microscopic schedules and, in turn, in better passenger plans. The gap (TS–Cons vs. TS–Dev) is larger for the no-wait policy, where the impact of train scheduling is not mediated by an iterative framework. In general the large delays result in smaller gaps when compared to the small delays, as there is much delay that is just unavoidable by rescheduling trains or updating connection plans.

Further details on the solution procedure are reported in Table 4. These characteristics are very similar for TS–Cons and –Dev, so we have listed the average over both objectives in the table. For instances with small initial delays, the average computation time for DM and TS equals 2 and 4 min, respectively. When we consider instances with large delays, DM requires much more computation time. In our experiments, we set the maximal running time to 20 min. After that time, the maximal optimality gap was below 0.5 %. Computation times of 20 min are too large for practical applications. We note that DM finds a good solution within minutes, and uses the remaining time only to improve it slightly or prove its optimality. In practical applications, one can thus truncate the solution process for example after 5 min. The TS routines, on the other hand, require as much as 5 min for solving the complex instances with large delays. In order to quantify the delays that DM neglects, we also present the average train delay in Utrecht for the DM and for the TS model. For instances with small initial delays, TS increases the average train delay by 35 %. The relative increase for instances with larger delays equals 17 %. This is among the first measures quantifying microscopically train delay propagation phenomena as a consequence of macroscopic plans.

Table 4 Some characteristics of the solution procedure

6.3 Analysis of the iterative process

In order to improve the solutions presented in the previous section, we proposed an iterative framework in Sect. 5. In this section, we describe our experiments to evaluate this iterative approach.

We begin by analyzing the solutions throughout the iterations: a typical behavior for the iterative approach is depicted in Fig. 6. Similar behavior is observed for 15 out of 20 instances. In this figure, there are four lines. Two of the lines (named DM–Cons and DM–Dev) connect the objective values that are found by the DM module in each iteration. Note that these values correspond to macroscopic solutions, that are not feasible microscopically. The other lines connect the total passenger delay that is found after validating the macroscopic timetable with the TS model (respectively, DM + TS–Cons, and DM + TS–Dev). The two pairs of lines correspond to the two different objectives in the TS model.

Fig. 6

The progress of the iterative approach for an instance where the solution quality decreases

We observe in Fig. 6 that the iterative approach converges after 3 iterations for this instance, for both TS objectives. When we consider the objective values corresponding to solutions that are both macroscopically and microscopically feasible (both DM + TS setups), the passenger delay increases gradually at each iteration, until it converges to a value that is about 0.5 % worse than the solution found at iteration 1. We explain in greater detail this behavior by help of the plots in Fig. 7. The plots give a sequence of schematic time–space diagrams for a particular train that drives towards Utrecht Central Station. From the top, the first plot describes the planned trip of the train, and introduces the y axis, distance, increasing upward; and the x axis, time, increasing rightward. During the actual operations, an external event delays the train by 4 min before it enters the station area around Utrecht. In the first DM solution, the time–space path of the train is therefore extended by 4 min and arrives at the border of the station area in Utrecht with a delay of 4 min. In the first TS iteration, the entrance time at the border corresponds to a reference time as explained in Sect. 5, basically it is just the expected arrival time, minus the minimal running time τ. The arrival time of the train at Utrecht is scheduled as closely as possible to the arrival time in the DM solution. However, as a consequence of its late entrance in the station area, the train faces some red or yellow lights in the interlocking area of Utrecht, in the TS solution. The train can thus not drive at its planned speed in the station area, due to conflicts with other trains, resulting in additional delay, that is then reported back to the DM module for iteration DM2. As the DM module cannot model the precise train dynamics within the station area, it extends the delay on the open track between Amsterdam Bijlmer and Utrecht to make sure that the train arrives in Utrecht at the time specified by the TS module in the previous iteration, according to the update rules specified in Sect. 5. Recall that the DM module assumes that the train runs at its planned speed within the station area. In the next round, TS obtains the entrance time in the station area from DM, and tries to find a path for the train within the station area that minimizes the arrival delay of the train. Again, there is no conflict-free plan for the train, so the train is delayed slightly more in the second TS iteration. As a consequence, DM again schedules the arrival at the border of the station area slightly later in the third iteration. However, in the third iteration, TS is able to compute a conflict free path for the train, which is thus equal to that found by the DM module. Now, the models agree on the time–space path for the train, and the process has converged to a solution that is microscopically feasible, and completely described in terms of macroscopic constraints.

Fig. 7

The time-space diagram of a trip from Amsterdam Bijlmer (Asb) to Utrecht (Ut) found by both models in three iterations. TS1 is the solution obtained by applying the DM and TS model sequentially. Final is the solution obtained by the iterative approach

The example illustrates how the iterative process might increase the arrival time of trains at stations (from TS1 to TS3) and the related passengers delay for some instances, while better solutions, such as TS1, have already been obtained.

This potential for achieving better delay management plans can be exploited if the macroscopic models would be able to model individually the run through interlocking areas, at the expenses of larger instances and increased complexity. We refer to this problem as a promising direction to be investigated in future DM models, as pointed out in Sect. 7. On the other hand, the final solution that is found by the iterative approach has also additional advantages deriving from the fact that trains face no conflicts with other trains and thus run at their planned speed in the station area. In fact, such a solution is much easier to implement in practice, as there are no additional measures required by the dispatchers, apart from communicating departure times (see Caimi 2009) and trains do not need to brake and re-accelerate for unplanned stops, which would increase the energy consumption of the trains (see Corman et al. 2009).

Considering the two setups TS–Cons and –Dev, the progress of the iterative approach is very similar. However, for the instance depicted in Fig. 6, we find with TS–Dev a solution that is about 1 % better in each iteration. For 15 out of 20 instances, the behavior of the iterative approach is comparable to that in Fig. 6. Among these 15 instances, the final solution has less passenger delay for 6 instances when TS minimizes the maximal consecutive delay. For 8 instances, the final solution is better when the maximal deviation is minimized. Finally, for 1 instance, the solution is equal for both objectives.

For 3 out of 20 instances, the objective value is actually improved by the iterative approach. The progress of the iterative approach for one of these instances is depicted in Fig. 8. For both objectives in the TS model, a solution to the DM problem is found that decreases the delay significantly in the second iteration. By validating this new solution microscopically by the TS routines, the procedure converges to a solution with a total passenger delay that is lower than it was in the first iteration. In this case, the total passenger delay is reduced by 0.5 %. For the other two instances, the improvement is about 2.0 %.

Fig. 8

The progress of the iterative approach for an instance where the solution is improved

For the remaining instances, we see a combination of both phenomena: For one choice of TS objective function, the total passenger delay increases along the iterations, while it decreases along the iterations for the other choice.

The results on passenger delay minimization are summarized in Table 5. This table presents both for TS–Cons and for TS–Dev the average passenger delay of the solutions in each iteration and that of the best solution found so far. The upper five rows present the results for the TS objective TS–Cons; the lower five rows give the results for TS–Dev. It can be observed that the average objective values increase in most of the iterations. However, if the best solution found during the process is considered, the average objective value decreases in the second iteration. The iterative optimization framework thus improves the solution of the first iteration. We observe that the iterative method finds the best solution with respect to passenger delay either in the first or in the second iteration.

Table 5 The average results over 10 instances for the iterative optimization framework

For most of the instances, the iterative approach converges within three or four iterations. The average number of iterations that are needed to reach convergence equals 3.55 for TS–Cons and 3.6 for TS–Dev. We conclude that the objective that considers the deviation from the macroscopic timetable does not lead to faster convergence than the objective that minimizes the maximal consecutive delay.

7 Conclusions

In this paper, we combined a model for delay management with a model for train scheduling. This overcomes a weak point of the literature on delay management, namely that wait–depart decisions obtained by such DM models are not evaluated taking into account all details of the underlying railway infrastructure. By incorporating the computed wait–depart decisions, we calculated the exact delays of the trains and thereby the passengers with the TS model. In addition, we developed an iterative optimization framework where we propose a mechanism to incorporate consecutive delays from the train scheduling solution in the delay management problem.

We have evaluated our optimization framework on real-world examples from the Netherlands. We have shown that the DM model gives a good estimate of the reduction in total passenger delay, by evaluating the wait–depart decisions with a TS model. The wait–depart decisions obtained by the DM model can be very well used in practice if this approach is combined with an advanced train scheduling routine. From a scientific point of view, macroscopic DM models provide good solution although they lack all kind of details of the infrastructure.

The iterative optimization framework converges within three or four iterations to a solution that is easier to implement by dispatchers and reduces energy consumption. Furthermore, for some instances, the passenger delay can be reduced by up to 2.5 % by using our iterative framework. However, for most instances, the solution from the first iteration could not be improved in terms of passenger delay. Note that the iterative framework also impacts train delays.

Several directions for further research are available. First, the interaction between the models should be investigated in more detail for scenarios with large delays. Considering a more general feedback mechanism could potentially lead to better solutions. For example, one could define weights on the connections in the train scheduling model or penalize changes in the wait–depart decisions in the delay management model. Second, the iterative framework could be tested on a railway network with more bottlenecks. For each station where the infrastructure is scarce, a local scheduler could be applied to compute a feasible train schedule. As the updates from different stations can generate new delays to adjacent station bottlenecks, more iterations might be needed for convergence; moreover, the local view of each TS (controlling a bottleneck) might lead to (globally) suboptimal scheduling decisions, as discussed in Corman et al. (2012) for the TS problem only. The quantitative study of the impact of interdependence between multiple bottlenecks on convergence speed and quality of solutions is a promising research direction.