Stochastic improvement of cyclic railway timetables

https://doi.org/10.1016/j.trb.2007.11.002Get rights and content

Abstract

Real-time railway operations are subject to stochastic disturbances. Thus a timetable should be designed in such a way that it can cope with these disturbances as well as possible. For that purpose, a timetable usually contains time supplements in several process times and buffer times between pairs of consecutive trains. This paper describes a Stochastic Optimization Model that can be used to allocate the time supplements and the buffer times in a given timetable in such a way that the timetable becomes maximally robust against stochastic disturbances. The Stochastic Optimization Model was tested on several instances of NS Reizigers, the main operator of passenger trains in the Netherlands. Moreover, a timetable that was computed by the model was operated in practice in a timetable experiment on the so-called “Zaanlijn”. The results show that the average delays of trains can often be reduced significantly by applying relatively small modifications to a given timetable.

Introduction

Punctuality of a railway system is a highly important issue, since punctuality is often considered as one of the key performance indicators of a railway system. This is particularly true for passenger trains. In the Netherlands, punctuality of passenger trains is defined as the percentage of trains that arrive at one of the larger railway stations with a delay of less than 3 min. Several other countries use a 5 min margin, or they measure the delays only at the final destinations of the trains.

However, measuring punctuality in these ways is not completely satisfactory: a delay of 6 min is as bad as a delay of 10 min. Moreover, it suggests that there is no problem as long as a delay is less than 3 (or 5) min. However, a delay of 2 min at a station reduces the probability of an on-time arrival at the next station. Moreover, punctuality defined as above is rather hard to analyze mathematically, since it is non-linear. Therefore we use the average delays of the trains in this paper to measure the on-time performance of the trains instead of the punctuality.

Delays of trains occur since real-time railway operations are subject to external stochastic disturbances. The latter are also called primary disturbances. However, the timetable is a fixed and deterministic plan. In order to cope with disturbances, a timetable therefore usually contains time supplements in the planned process times of the trains and buffer times between consecutive train movements on the same part of the infrastructure. By the time supplements, part of the primary disturbances can be absorbed without giving rise to delays. Moreover, if delays do occur, then the time supplements also enable their partial absorption. Buffer times between trains reduce the knock-on effects of delays from one train to another. The latter are also called secondary delays.

In general, allocating more time supplement to a certain process increases the probability that the process can be carried out within the planned time. Therefore, time supplements in the timetable may add to the predictability of the realized travel times of the passengers. On the other hand, as Carey (1998) observes, if more time is allocated to a certain process, then a consequence may be that the process tends to use more time in the realizations, just because more time is available.

Moreover, time supplements may have a negative effect on the realized travel times. Indeed, each minute of running time supplement in the timetable brings the possibility that it is not needed in the operations, since there are no disturbances. Additionally, more time supplements may require more personnel and rolling stock, hence they are negative for the efficiency of the railway system. As a consequence, the time supplements should be chosen by a careful trade-off between these elements.

Anyway, in order to improve the average delays of the trains in a railway system, it is relevant to look for an optimal allocation of the time supplements and the buffer times in the timetable. Not only the total amount of time supplements and buffer times, but also their distribution among the processes in the timetable is relevant. The allocation of running time supplements was described recently by UIC (2000). This subject was also studied by Rudolph, 2004, Vromans, 2005, Kroon et al., 2007.

Note that the re-allocation of time supplements and buffer times may improve the robustness of a timetable against relatively small disturbances only. In case of large disturbances, traffic control measures are required and in such cases time supplements and buffer times are hardly effective. Therefore, most robustness related research focuses on insensitivity of the railway system against small disturbances.

The analysis and the improvement of the punctuality of railway services have been studied by several researchers and various models have been developed. Main examples of such models are (i) simulation models, (ii) models based on Max-Plus algebra and (iii) analytical models.

Simulation models of railway processes are described by, e.g. Bergmark, 1996, Wahlborg, 1996, Middelkoop and Bouwman, 2000, Hürlimann, 2001, König, 2001. Models based on Max-Plus algebra are described by, e.g. Goverde, 1998, Goverde, 2005, de Kort, 2000, Soto y Koelemeijer et al., 2000. Finally, analytical models are described by Schwanhäußer, 1974, Weigand, 1981, Petersen and Taylor, 1982, Wakob, 1985, Hallowell and Harker, 1998, Higgins and Kozan, 1998, Carey, 1999, Huisman and Boucherie, 2001, Yuan, 2006.

A drawback of these existing models is that they are mainly evaluation models and that, based on these models, optimization of the robustness of a timetable can only be achieved by trial-and-error. That is, the evaluation models do not provide explicit suggestions on how to modify the timetable in order to improve the robustness. The timetable has to be modified by re-allocating the time supplements and the buffer times, e.g. based on observed bottle-necks in the evaluation and then the evaluation model is used again to evaluate the effect of the modification. These steps are repeated until an acceptable result has been achieved.

In contrast with the existing models, this paper describes a Stochastic Optimization Model (see, e.g. Birge and Louveaux, 1997). This model improves the robustness of a given cyclic timetable. At the same time that this optimization takes place, the model simulates the timetable under construction by operating a number of realizations of the trains in the timetable. These trains are operated as much as possible according to the modified timetable, but subject to stochastic disturbances. The optimization of the timetable is achieved by re-allocating the planned time supplements and buffer times in the timetable. The main objective in the optimization is minimization of the average delays of the trains.

Conversely, one may consider the model as a simulation model that captures the above described iterative optimization process of modifying the timetable and evaluating the modified timetable by carrying out an evaluation in a single optimization run. The optimization of the timetable is driven by the simulation results. The timetable is modified in such a way that the simulation results are as good as possible. That is, the average delays of the trains in the simulation are minimal.

The Stochastic Optimization Model is an improved version of the model described by Vromans, 2005, Kroon et al., 2007. The latter model is based on the same idea and has the same objective, but it uses a linear time axis per train. This feature makes the inclusion of passenger connections in a network of train lines and rolling stock circulations rather cumbersome. The model described in the current paper is based on a cyclic time axis, which better facilitates the inclusion of such aspects. This advantage is explained in more detail in Section 2.7.

The model has been applied to several practical cases. The additional evaluation of the obtained results by the simulation software SIMONE (see Middelkoop and Bouwman, 2000) and experiments in practice have shown that the application of the model may lead to a substantial reduction of the average delays of the trains. Indeed, one of the main contributions of this paper is that it shows that the application of Stochastic Optimization really works in practice.

The structure of this paper is as follows. In Section 2, we describe the Stochastic Optimization Model in more detail. Section 3 presents results on the existence of an optimal solution and on convergence of the solutions of the Stochastic Optimization Model to the optimal solution if the number of realizations increases. Section 4 presents computational results based on instances of NS Reizigers, the main operator of passenger trains in the Netherlands. Section 5 describes the results of a practical experiment with an improved timetable on the so-called “Zaanlijn” in the Netherlands. The paper is concluded in Section 6.

Section snippets

Stochastic Optimization Model

In this section, we describe the Stochastic Optimization Model that can be used to improve a given cyclic timetable for a number of trains on a common part of the railway infrastructure with respect to the average delays of the trains. The latter is achieved by re-allocating the time supplements and the buffer times in the timetable.

We assume that all details of the given timetable are known, e.g. not only the departure and arrival times of the trains, but also the platform assignments and the

Existence and convergence of the solutions

As was mentioned earlier, the Stochastic Optimization Model is a two-stage recourse model for which approximate solutions are generated by a Sample Average Approximation Method.

In this section, we describe this method in a more formal way. To that end, let x be the vector of decision variables. This vector includes all planned departure and arrival times of the trains on a single day, thereby taking into account the fact that all hours of a cyclic timetable are identical. Then the timetabling

Computational results

In this section we present computational results that were obtained by applying the Stochastic Optimization Model to a case based on the 2007 timetable for the northern part of North-Holland in the Netherlands (the so-called “Kop van Noord-Holland”, see Fig. 3).

The computational results were obtained by implementing the model in the modeling system OPL Studio 3.7 running on Windows XP. The model was solved by CPLEX 9.0. The hardware was an Intel Pentium 4 processor with a clock speed of 3.0 GHz

Case description

During the weeks 22–29 of 2006 (May 28 until July 23), a timetable generated by the Stochastic Optimization Model was tested in practice on the so-called “Zaanlijn”. The “Zaanlijn” is part of the “Kop van Noord-Holland”: it is the north–south connection between Den Helder (Hdr) and Amsterdam (Asd), see Fig. 3. Note that a modified timetable was also operated on the “Zaanlijn” during weeks 30 and 31 of 2006, but this period was not representative due to other changes in the timetable.

The

Conclusions and further research

In this paper we described a Stochastic Optimization Model for improving the robustness of a given cyclic railway timetable. The Stochastic Optimization Model is a symbiosis of a simulation model and an optimization model. The model is an improved version of the model described by Vromans, 2005, Kroon et al., 2007. An improvement of the current model is that it is based on a cyclic time axis, which better facilitates the inclusion of passenger connections in a network of train lines as well as

Acknowledgements

The authors want to thank Maarten van der Vlerk (University of Groningen) and Leen Stougie (CWI in Amsterdam and Technical University of Eindhoven) for several stimulating discussions, which were quite helpful in the preparation of Section 3 of this paper.

References (39)

  • Goverde, R.M.P., 2005. Punctuality of railway operations and timetable stability analysis. Ph.D. Thesis, Technical...
  • Goverde, R.M.P., Hooghiemstra, G., Lopuhaa, H.P., 2001. Statistical analysis of train traffic: the Eindhoven Case....
  • J.M. Hammersley et al.

    A new Monte Carlo technique: antithetic variables

    Proceedings of the Cambridge Philological Society

    (1956)
  • A. Higgins et al.

    Modelling train delays in urban networks

    Transportation Science

    (1998)
  • J.S. Hooghiemstra et al.

    Decision support systems support the search for win-win solutions in railway network design

    Interfaces

    (1999)
  • Hürlimann, D., 2001. Objektorientierte Modellierung von Infrastrukturelementen und Betriebsvorgängen im Eisenbahnwesen....
  • Y.M. Kaniovski et al.

    Probabilistic bounds (via large deviations) for the solutions of stochastic programming problems

    Annals of Operations Research

    (1995)
  • A.J. King et al.

    Asymptotic theory for solutions in statistical estimations and Stochastic Programming

    Mathematics of Operations Research

    (1993)
  • A.J. Kleywegt et al.

    The sample average approximation method for stochastic discrete optimization

    SIAM Journal on Optimization

    (2001)
  • Cited by (176)

    View all citing articles on Scopus
    1

    This author was sponsored by the Future and Emerging Technologies Unit of EC (IST priority 6th FP), under Contract No. FP6-021235-2 (ARRIVAL).

    View full text