Abstract
Every train schedule entails a certain risk of delay. When adding a new train to an existing timetable, planners have to take the expected risk of delay of the trains into account. Typically, this can be a very laborious task involving detailed simulations. We propose to predict the risk of a planned train using a series of linear regression models on the basis of extensive real world delay data of trains. We show how to integrate these models into a combinatorial shortest path model to compute a set of Pareto optimal train schedules with respect to risk and travel time. We discuss the consequences of different model choices and notions of risk with respect to the algorithmic complexity of the resulting combinatorial problems. Finally, we demonstrate the quality of our models on real world data of Swiss Federal Railways.
This work was partially supported by the Future and Emerging Technologies Unit of EC (IST priority - 6th FP), under contract no. FP6-021235-2 (project ARRIVAL).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. Prentice Hall, Englewood Cliffs (1993)
Akaike, H.: A new look at statistical model identification. IEEE Transactions on Automatic Control 19, 716–723 (1974)
Borndörfer, R., Schlechte, T.: Models for railway track allocation. In: Liebchen, C., Ahuja, R.K., Mesa, J.A. (eds.) ATMOS 2007 – 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, Dagstuhl, Germany (2007)
Cacchiani, V., Caprara, A., Toth, P.: A column generation approach to train timetabling on a corridor. 4OR 6(2), 125–142 (2008)
Dagan, I., Golumbic, M.C., Pinter, R.Y.: Trapezoid graphs and their coloring. Discrete Apllied Mathematics 21, 35–46 (1988)
Felsner, S., Müller, R., Wernisch, L.: Trapezoid graphs and generalizations, geometry and algorithms. In: Schmidt, E.M., Skyum, S. (eds.) SWAT 1994. LNCS, vol. 824, pp. 143–154. Springer, Heidelberg (1994)
Fischer, F., Helmberg, C., Janßen, J., Krostitz, B.: Towards solving very large scale train timetabling problems by lagrangian relaxation. In: Fischetti, M., Widmayer, P. (eds.) ATMOS 2008 – 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, Dagstuhl, Germany (2008)
Flier, H., Graffagnino, T., Nunkesser, M.: Planning additional trains on corridors. Technical Report 164, ARRIVAL Project (2008), http://arrival.cti.gr/
Fox, J.: Applied Regression Analysis and Generalized Linear Models, 2nd edn. SAGE, Thousand Oaks (2008)
Liebchen, C., Lübbecke, M., Möhring, R.H., Stiller, S.: Deliverable 1.2: New theoretical notion of the prices of robustness and recoverability. ARRIVAL Project (2007), http://arrival.cti.gr/
R Development Core Team. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria (2008), http://www.R-project.org/
SBB. Rail 2000 - a public transport network for the third millenium (2000), http://www.sbb.ch/rail2000/
Venables, W.N., Ripley, B.D.: Modern Applied Statistics with S. Statistics and Computing Series. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Flier, H., Graffagnino, T., Nunkesser, M. (2009). Scheduling Additional Trains on Dense Corridors . In: Vahrenhold, J. (eds) Experimental Algorithms. SEA 2009. Lecture Notes in Computer Science, vol 5526. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02011-7_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-02011-7_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02010-0
Online ISBN: 978-3-642-02011-7
eBook Packages: Computer ScienceComputer Science (R0)