1 Introduction

The Train Dispatching Problem (TDP) deals with the determination of a railway timetable by constructing train routes and corresponding arrival and departure times to operate train requests in a given railway network. Due to the complex operation rules, limited capacity, which is only upgradeable with massive financial effort, the infrastructure network builds a natural bottleneck. Thus, it is appreciable to utilize the existing infrastructure in the best way.

The TDP integrates several major requirements like safety system rules, train characteristics, blocking and headway times, timetable requirements, and infrastructure capacities. A detailed problem description and a Mixed Integer Programming formulation to solve this problem is described in detail in [5]. In this paper, we report on a Re-optimization or Re-scheduling approach for the TDP in a real time setting using a state-of-the-art MIP solver.

The authors of [2] introduced a re-optimization approach for rolling stock rotation planning problems. In case of the TDP, we adapted it as follows: At some point in time a railway undertaking has to agree on a timetable, ideally, utilizing an optimization algorithm or by manual planning. Later in time this problem or aspects changes that much, such that the reference solution, in case of the TDP the timetable, becomes infeasible. Thus, a modified problem has to be solved. In contrast to the first process leading to the reference timetable the time limitations are in the second stage rather strict. Since an operator has only minutes or seconds for his decisions, the re-optimization algorithm has to calculate solutions within a real time management system. Another major goal is to change as few as possible in comparison to the original timetable. This should minimize the disturbance of the ongoing timetable because fewer changes are easier to communicate, easier to apply, and hence more reliable. Moreover, it is impossible for an operator to change many routes at the same time, because the running and blocking times highly depend on the routes and interaction between the trains. In case of the timetable construction this is evaluated in detail by microscopic simulation which is not applicable in a real time setting. Therefore, the reference solution highly influences the objective function. There are various causes that can lead to a situation where the implemented timetable becomes unexpectedly infeasible. Predictable and unpredictable construction sites and breakdowns that block a track must be integrated into the timetable as fast as possible. In addition, delayed trains and modifications of speed limits may require an adjustment of the timetable. The paper contributes an adaption of the Mixed Integer Programming approaches presented in [5, 7] to re-optimize timetables. We show how to incorporate re-optimization requirements into the disjunctive graph based formulation, see [1, 3, 4, 6]. An iterative approach is used by [4] to solve real-time instances of the Dutch railway network. They use a branch-and-bound algorithm for sequencing train movements and improving the solution by locally rerouting some trains. The connection between adjacent dispatching areas is studied by [3]. Mascis and Pacciarelli [6] use a disjunctive graph formulation to model and solve a job-shop scheduling problem with blocking constraints. This paper is organized as follows. Section 2 defines the considered problem including an overview of the disjunctive based formulation. In Sect. 3 we present some real world scenarios, consider common re-optimization use cases for the TDP, and presents computational results. This indicates that the model and algorithmic approach produces high quality solutions in a very short time and is able to tackle the real time re-optimization setting.

2 A Re-optimization Model for the TDP

Consider the following problem setting for the TDP. We model the infrastructure network by a directed graph \(G=( V, A)\). The arcs correspond to track segments with fixed running times \(\tau ^{r}_{(v,w)}\) for each train \(r \) that is able to operate on track segment \((v,w) \in A\). For each track segment (v, w) and train pair \(r,{r'} \) exists a headway time \(h^{r,{r'}}_{(v,w)}\) which is defined as the minimal time between two consecutive trains \(r \) and \({r'} \) that use the same track segment (v, w), see details in [9]. The set of scheduled train requests is denoted by \(R \). Each train \(r \in R \) is associated with an initial route \(p ^{*}\in P ^{r}\), where \(P ^{r}\) is the set of possible routes for request \(r\). Additionally, there are essential stops \(S ^r \subset V\) for each train \(r \in R \). Each stop \(s \in S ^r \) of train \(r\) have to be fulfilled during the time period \([\underline{\alpha }_{s}^r, \overline{\alpha }_{s}^r ]\). A time unit of deviance from the scheduled departure of train \(r\), denoted by \(\alpha _{s}^r \), is penalized by \(\underline{c}_{s}^r \) if the actual departure time is before \(\alpha _{s}^r \), and \(\overline{c}_{s}^r \) if the actual departure time is after \(\alpha _{s}^r \). Furthermore, we denote by \(\delta ^{r}_{p}\) the cost that occur from re-routing train \(r \) on route \(p \) instead of its initial route \(p ^{*}\) with cost \(\delta ^{r}_{p ^{*}}=0\). By \(\gamma ^{r}\in \mathbb {R}^{-}\) we denote a (negative) profit value for not routing train \(r \). Usually, this value should ensure that a maximal number of trains is scheduled. If meaningful data is available this could also be used to give the algorithm a priority estimation for each train depending on the demand. The set \(B \subseteq A\) is the set of arcs \((v,w)\) where some kind of disturbance takes place during the period of \([\underline{\beta }_{(v,w)},\overline{\beta }_{(v,w)}]\).

A solution of the TDP has to associate each scheduled train \(r \in R \) at most one route \(p \in P ^{r}\) with departure times for each node \(v\in p \) under consideration of the headway constraints. The task of the model is to select a path for each train and to determine departure times \(t^{r}_{v}\) for each node \(v\) that is visited by train \(r \) on its path. For this, we enforce relations between different departure times w. r. t. the chosen paths and the order in which different trains traverse the same arc. In particular, we will make use of the following three types of decisions:

  1. 1.

    \(r \text { uses } (v, w)\), which is satisfied if and only if the selected path for \(r \) contains arc \((v, w)\),

  2. 2.

    \(r \prec _{(v, w)} {r'} \), which is satisfied if and only if \(r \) traverses \((v, w)\) before \({r'} \),

  3. 3.

    \(r \prec b_{(v,w)}\) and \(r \succ b_{(v,w)}\), which are satisfied if and only if \(r \) uses \((v,w)\) before or after the disruption, respectively.

Depending on these conditions, we can formulate the following constraints for the departure times:

$$\begin{aligned} \textit{running times:}&r \text { uses } (v,w)&\Rightarrow t^{r}_{v} + \tau ^{r}_{(v, w)} \le t^{r}_{w},\end{aligned}$$
(1)
$$\begin{aligned} \textit{headway times:}&r \prec _{(v,w)} {r'}&\Rightarrow t^{r}_{v} + h^{r,{r'}}_{(v, w)} \le t^{{r'}}_{v},\end{aligned}$$
(2)
$$\begin{aligned} \textit{disruption times:}&r \prec b_{(v,w)}&\Rightarrow t^{r}_{w} \le \underline{\beta }_{(v,w)}, \text { and } r \succ b_{(v,w)} \Rightarrow t^{r}_{v} \ge \overline{\beta }_{(v,w)}.\end{aligned}$$
(3)

We using the following binary variables

  1. 1.

    \(z^{r}_{p} = 1 \iff r \text { runs on } p \in P ^{r}\),

  2. 2.

    \(x^{r,{r'}}_{(v,w)}=1 \iff r \text { runs before } {r'} \text { on } (v, w)\),

  3. 3.

    \(b^{r}_{(v, w)} = 1 \iff r \text { runs before disruption on } (v,w)\)

and formulate the disjunctive constraints as linear big-\(M\) constraints.

With this notation the TDP can be stated as a mixed integer program as follows:

$$\begin{aligned} {{\mathrm{minimize}}}\quad&\sum _{v\in S} ( \underline{c}^{r}_{v} \underline{\varDelta }^{r}_{v} + \overline{c}^{r}_{v} \overline{\varDelta }^{r}_{v}) + \sum _{r \in R} \sum _{p \in P ^{r}} \delta ^{r}_{p} z^{r}_{p} + \sum _{r \in R} \gamma ^{r} \sum _{p \in P ^{r}}\, z^{r}_{p} \end{aligned}$$
(4)
$$\begin{aligned} \text {subject to}\quad&(1), (2), (3), \end{aligned}$$
(5)
$$\begin{aligned}&\sum _{p \in P ^{r}} z^{r}_{p} \le 1,&r \in R, \end{aligned}$$
(6)
$$\begin{aligned}&t^{r}_{v} - \overline{\varDelta }^{r}_{v} \le \alpha ^{r}_{v},&r \in R, v\in S^{r}, \end{aligned}$$
(7)
$$\begin{aligned}&t^{r}_{v} + \underline{\varDelta }^{r}_{v} \ge \alpha ^{r}_{v},&r \in R, v\in S^{r}, \end{aligned}$$
(8)
$$\begin{aligned}&t^{r}_{v} \in [\underline{\alpha }^{r}_{v}, \overline{\alpha }^{r}_{v}],&r \in R, v\in S^{r}, \end{aligned}$$
(9)
$$\begin{aligned}&t^{r}_{v}, \underline{\varDelta }^{r}_{v}, \overline{\varDelta }^{r}_{v} \ge 0,&r \in R, v\in S^{r}, \end{aligned}$$
(10)
$$\begin{aligned}&z, x, b\text { binary} \end{aligned}$$
(11)

In addition to the three types of binary variables, the continuous variables \(t^{r}_{w}\) model the departure time of train \(r \) at node w. The continuous cost variables \(\underline{\varDelta }^{r}_{w}\) and \( \overline{\varDelta }^{r}_{w}\) measure the deviation between the departure time of the reference timetable and re-allocated departures times of train \(r \) at node w. The linear objective function (4) minimizes the sum of the total costs for deviance at stops, costs for alternative routes, and costs for unscheduled trains. The constraints for the running times (1), the headway times (2) and the disruption times (3) are formulated as big-M constraints as mentioned above. The inequalities (7) and (8) ensure the correct values for the time deviation cost variables and constraints (6) ensure that at most one route is selected for each train. The departure time windows of the stops are modeled by (9).

If the trains have delays the model aims at pushing the trains back to its actual routing and timing. In some cases this is not desired since the new schedule may lead to a lot of modifications of the current timetable, which is not realizable. In this case the reference departure times could be adjusted to keep the delays at the current level. Of course, by setting the variables cost \(\underline{c}^{r}_{s},\overline{c}^{r}_{s}\) and \(\delta ^{r}_{p}\) to zero for all stops, paths and trains it is possible to calculate a timetable that is completely independent from the reference timetable.

3 Computational Study

We implemented the proposed re-optimization model in a C++-framework. This implementation takes use of MIP solver CPLEX 12.6. All our computations were performed on a desktop computer with an Intel Xeon CPU E3-1245 v3 with 3.40 GHz and 32 GB of RAM. The set of instances are scenarios derived from the INFORMS RAS Problem Solving Competition 2012, see [8].

The RAS instances include a microscopic infrastructure network containing 82 nodes and 184 arcs. There are three different scenarios with increasing complexity, i.e., in terms of larger number of trains and disturbances. Table 1 shows the corresponding sizes.

Table 1 Key numbers of re-optimization scenarios from RAS
Full size table

In all cases we chose \(\gamma ^{r} = -10^3\) for the profit value of routing train \(r \). The parameter \(\delta ^{r}_{p}\) equals the number of deviating tracks between route p and reference route \(p^{*}\). The cost parameters are set in such a way that the optimization goals are weighted in order of importance. First the number of cancelled trains should be minimal, second the number of route changes should be minimal and third the departure times should be as close as possible at the reference timetable. For the MIP solvers we set a time limit of 1800 s.

We limited the set of possible routes for each train since otherwise most of the trains have 192 possible routes which is far too much to handle. In addition, most of those ignored potential routes cannot be part of an optimal solution. An observation is that the model can be solved in a few seconds if the number of alternative routes per train is small. Therefore we sort accordingly to \(\delta ^{r}_{p}\) the alternative routes for each train and select the first 4, 8 and 16 alternative routes for each train, respectively. We use the cost parameters \(\delta ^{r}_{p}\) since there are the only costs that can be calculated in advance.

The computational results are in Table 2. The second column is the number of alternative routes for each train and is followed by the number of trains in the reference time table. Then we have the number of blocked trains and the number of planned, cancelled and rerouted trains in the solution. If the time limit was reached than this is indicated with TL in the running time column.

Table 2 Solutions of the RAS scenarios with 4, 8 and 16 alternative routes for each train
Full size table

From the practical point of view even the restriction to four tours per train is more than a dispatcher can overlook in a couple of minutes or even seconds. We are able to solve the first two scenarios to optimality and solve the third with an optimality gap of at most 5.3%. It turns out that for the RAS instances the first four selected tours are sufficient to provide high quality solutions. Furthermore the optimality gaps after 20 s indicate that we are able to get good solutions fast.

4 Conclusion

We extended a well known MIP formulation for the TDP to be able to tackle re-optimization scenarios. Our computational study demonstrates that our re-optimization approach can be used to produce high quality solutions in reasonable computation time for a real time application.