Document Open Access Logo

Timing of Train Disposition: Towards Early Passenger Rerouting in Case of Delays

Authors Martin Lemnian, Ralf Rückert, Steffen Rechner, Christoph Blendinger, Matthias Müller-Hannemann

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2014.122.pdf
  • Filesize: 0.52 MB
  • 16 pages

Document Identifiers

Author Details

Martin Lemnian
Ralf Rückert
Steffen Rechner
Christoph Blendinger
Matthias Müller-Hannemann

Cite As Get BibTex

Martin Lemnian, Ralf Rückert, Steffen Rechner, Christoph Blendinger, and Matthias Müller-Hannemann. Timing of Train Disposition: Towards Early Passenger Rerouting in Case of Delays. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 122-137, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/OASIcs.ATMOS.2014.122

Abstract

Passenger-friendly train disposition is a challenging, highly complex online optimization problem with uncertain and incomplete information about future delays. In this paper we focus on the timing within the disposition process. We introduce three different classification schemes to predict as early as possible the status of a transfer: whether it will almost surely break, is so critically delayed that it requires manual disposition, or can be regarded as only slightly uncertain or as being safe. The three approaches use lower bounds on travel times, historical distributions of delay data, and fuzzy logic, respectively. In experiments with real delay data we achieve an excellent classification rate. Furthermore, using realistic passenger flows we observe that there is a significant potential to reduce the passenger delay if an early rerouting strategy is applied.

Subject Classification

Keywords
  • train delays
  • event-activity model
  • timing of decisions
  • passenger flows
  • passenger rerouting

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. L. Anderegg, P. Penna, and P. Widmayer. Online train disposition: to wait or not to wait? ATMOS'02, ICALP 2002 Satellite Workshop on Algorithmic Methods and Models for Optimization of Railways, Electronic Notes in Theoretical Computer Science, 66(6), 2002. Google Scholar
  2. R. Bauer and A. Schöbel. Rules of thumb - practical online strategies for delay management. Technical report, NAM Report, Göttingen, 2012. Google Scholar
  3. M. Bender, S. Büttner, and S.O. Krumke. Online delay management on a single train line: beyond competitive analysis. Public Transport, 5:243-266, 2013. Google Scholar
  4. A. Berger, C. Blaar, A. Gebhardt, M. Müller-Hannemann, and M. Schnee. Passenger flow-oriented train disposition. In C. Demetrescu and M. M. Halldórsson, editors, Proceedings of the 19th Annual European Symposium on Algorithms (ESA), volume 6942 of Lecture Notes in Computer Science, pages 227-238. Springer, 2011. Google Scholar
  5. A. Berger, A. Gebhardt, M. Müller-Hannemann, and M. Ostrowski. Stochastic delay prediction in large train networks. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS), volume 20 of OpenAccess Series in Informatics (OASIcs), pages 100-111. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2011. Google Scholar
  6. A. Berger, R. Hoffmann, U. Lorenz, and S. Stiller. Online railway delay management: Hardness, simulation and computation. Simulation, 87(7):616-629, 2011. Google Scholar
  7. C. Biederbick. Computergestützte Disposition im schienengebundenen Personentransport: ein kundenorientierter Ansatz. PhD thesis, Universität Paderborn, 2006. Google Scholar
  8. C. Biederbick and L. Suhl. Decision support tools for customer-oriented dispatching. In F. Geraets, L.G. Kroon, A. Schoebel, D. Wagner, and C. Zaroliagis, editors, Algorithmic Methods for Railway Optimization, volume 4359 of Lecture Notes in Computer Science, pages 171-183. Springer, 2007. Google Scholar
  9. S. Cicerone, G. Di Stefano, M. Schachtebeck, and A. Schöbel. Multi-stage recovery robustness for optimization problems: A new concept for planning under disturbances. Information Sciences, 190:107-126, 2012. Google Scholar
  10. A. D'Ariano. Improving Real-Time Train Dispatching: Models, Algorithms and Applications. PhD thesis, Technische Universiteit Delft, 2008. Google Scholar
  11. A. D'Ariano, F. Corman, D. Pacciarelli, and M. Pranzo. Reordering and local rerouting strategies to manage train traffic in real time. Transportation Science, 42(4):405-419, 2008. Google Scholar
  12. T. Dollevoet and D. Huisman. Fast heuristics for delay management with passenger rerouting. Public Transport, 2013. URL: http://link.springer.com/article/10.1007%2Fs12469-013-0076-6#page-1.
  13. T. Dollevoet, D. Huisman, M. Schmidt, and A. Schöbel. Delay management with re-routing of passengers. In J. Clausen and G. Di Stefano, editors, 9th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS), OpenAccess Series in Informatics (OASIcs). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2009. Google Scholar
  14. M. Gatto, B. Glaus, R. Jacob, L. Peeters, and P. Widmayer. Railway delay management: Exploring its algorithmic complexity. In T. Hagerup and J. Katajainen, editors, Proceedings of 9th Scandinavian Workshop on Algorithm Theory (SWAT), volume 3111 of Lecture Notes in Computer Science, pages 199-211. Springer, 2004. Google Scholar
  15. M. Gatto, R. Jacob, L. Peeters, and A. Schöbel. The computational complexity of delay management. In D. Kratsch, editor, Graph-Theoretic Concepts in Computer Science: 31st International Workshop (WG 2005), volume 3787 of Lecture Notes in Computer Science. Springer, 2005. Google Scholar
  16. M. Gatto, R. Jacob, L. Peeters, and P. Widmayer. On-line delay management on a single train line. In F. Geraets, L.G. Kroon, A. Schoebel, D. Wagner, and C. Zaroliagis, editors, Algorithmic Methods for Railway Optimization, volume 4359 of Lecture Notes in Computer Science, pages 306-320. Springer, 2007. Google Scholar
  17. J. Jespersen-Groth, D. Potthoff, J. Clausen, D. Huisman, L.G. Kroon, G. Maróti, and M.N. Nielsen. Disruption management in passenger railway transportation. In R. Ahuja, R.-H. Möhring, and C. Zaroliagis, editors, Robust and Online Large-Scale Optimization, volume 5868 of Lecture Notes in Computer Science, pages 399-421. Springer, Heidelberg, 2009. Google Scholar
  18. P. Kecman, F. Corman, A. D'Ariano, and R. Goverde. Rescheduling models for railway traffic management in large-scale networks. Public Transport, 5:95-123, 2013. Google Scholar
  19. P. Kecman and R. M. P. Goverde. Adaptive, data-driven, online prediction of train event times. In 16th IEEE Annual Conference on Intelligent Transportation Systems (ITCS 2013), 2013. Google Scholar
  20. N. Kliewer and L. Suhl. A note on the online nature of the railway delay management problem. Networks, 57:28-37, 2011. Google Scholar
  21. S.O. Krumke, C. Thielen, and C. Zeck. Extensions to online delay management on a single train line: new bounds for delay minimization and profit maximization. Mathematical Methods of Operations Research, 74(1):53-75, 2011. Google Scholar
  22. S. Kurby. Makroskopisches Echtzeitdispositionsmodell zur Lösung von Anschlusskonflikten im Eisenbahnbetrieb. PhD thesis, Fakultät Verkehrswissenschaften "Friedrich List", Technische Universität Dresden, 2012. Google Scholar
  23. M. Müller-Hannemann and M. Schnee. Finding all attractive train connections by multi-criteria Pareto search. In F. Geraets, L. Kroon, A. Schoebel, D. Wagner, and C. Zaroliagis, editors, Proceedings of the 4th Dagstuhl conference on algorithmic approaches for transportation modelling, optimization, and systems (ATMOS), volume 4359 of Lecture Notes in Computer Science, pages 246-263. Springer Verlag, 2007. Google Scholar
  24. M. Müller-Hannemann and M. Schnee. Efficient timetable information in the presence of delays. In R. Ahuja, R.-H. Möhring, and C. Zaroliagis, editors, Robust and Online Large-Scale Optimization, volume 5868 of Lecture Notes in Computer Science, pages 249-272. Springer, 2009. Google Scholar
  25. M. Schachtebeck and A. Schöbel. To wait or not to wait and who goes first? Delay management with priority decisions. Transportation Science, 44(3):307-321, 2010. Google Scholar
  26. T. Schaer, J. Jacobs, S. Scholl, S. Kurby, A. Schöbel, S. Güttler, and N. Bissantz. DisKon - Laborversion eines flexiblen, modularen und automatischen Dispositionsassistenzsystems. Eisenbahntechnische Rundschau (ETR), 45:809-821, 2005. Google Scholar
  27. M. Schmidt. Simultaneous optimization of delay management decisions and passenger routes. Public Transport, 5:125-147, 2013. Google Scholar
  28. A. Schöbel. A model for the delay management problem based on mixed-integer programming. Electronic Notes in Theoretical Computer Science, 50(1), 2001. Google Scholar
  29. A. Schöbel. Customer-oriented optimization in public transportation. Springer, Berlin, 2006. Google Scholar
  30. A. Schöbel. Integer programming approaches for solving the delay management problem. In F. Geraets, L. Kroon, A. Schoebel, D. Wagner, and C. Zaroliagis, editors, Algorithmic Methods for Railway Optimization, volume 4359 of Lecture Notes in Computer Science, pages 145-170. Springer, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact