Stochastic improvement of cyclic railway timetables
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)
Optimizing scheduled times, allowing for behavioural response
Transportation Research Part B
(1998)Ex ante heuristic measures of schedule reliability
Transportation Research Part B
(1999)- et al.
Predicting on-time performance in scheduled railroad operations: methodology and application to train scheduling
Transportation Research Part A
(1998) - et al.
Running times on railway sections with heterogeneous train traffic
Transportation Research Part B
(2001) Periodic network optimization with different arc frequencies
Discrete Applied Mathematics
(1996)Railroad capacity and traffic analysis using SIMON
- et al.
Introduction to Stochastic Programming
(1997) Advanced railway planning using Max-Plus algebra
- et al.
Modeling the reliability of train arrival times
Journal of Transportation Engineering
(1996) The max-plus algebra approach to railway timetable design
A new Monte Carlo technique: antithetic variables
Proceedings of the Cambridge Philological Society
Modelling train delays in urban networks
Transportation Science
Decision support systems support the search for win-win solutions in railway network design
Interfaces
Probabilistic bounds (via large deviations) for the solutions of stochastic programming problems
Annals of Operations Research
Asymptotic theory for solutions in statistical estimations and Stochastic Programming
Mathematics of Operations Research
The sample average approximation method for stochastic discrete optimization
SIAM Journal on Optimization
Cited by (176)
Integrating stop planning, timetabling and rolling stock planning on high-speed railway lines: A multi-objective optimization approach
2024, Expert Systems with ApplicationsNetwork periodic train timetabling with integrated stop planning and passenger routing: A periodic time–space network construct and ADMM algorithm
2023, Transportation Research Part C: Emerging TechnologiesScheduling shared passenger and freight transport on a fixed infrastructure
2023, European Journal of Operational ResearchDevelopment of new railway timetabling rules for increased robustness
2023, Transport Policy
- 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).