Konzeptionierung und Implementierung einer Metaheuristik für das Train Timetabling Problem

Betreuer: Florian Hauck, Prof. Dr. Natalia Kliewer

Zielgruppe: Masterstudierende

Voraussetzungen: Programmierkenntnisse

Art der Arbeit: konzeptionell; methodisch

Kurzbeschreibung: Die Planung sowie der Betrieb von Bahnsystemen stellt eine komplexe Herausforderung für Bahnbetriebe dar. In mehreren Phasen und auf unterschiedlichen Ebenen finden sich unterschiedliche Problemstellungen des Operations Research wieder – von der Planung des Schienennetzwerkes und der Linien auf der strategischen Ebene bis hin zum Echtzeitmanagement während des Betriebes. Auf der taktischen Ebene beschäftigt man sich unter anderem mit der Erstellung eines möglich „guten“ Fahrplans, wobei dabei unterschiedliche Ziele wie die Minimierung der Gesamtkosten aber auch die Erhöhung der Robustheit gegenüber Verspätungen berücksichtigt werden können. Dabei gilt es verschiedenste Restriktionen des Schienenverkehrs (Mindestzugfolgezeiten, Überholen nur an bestimmten Punkten möglich, Kapazitäten der Bahnhöfe,…) zu berücksichtigen. Dieses Problem wird als Train Timetabling Problem (TTP) bezeichnet.

Ziel dieser Arbeit ist es, eine Metaheuristik für das TTP zu entwickeln. Ausgehend von einem Literaturüberblick, soll eine geeignete Metaheuristik zunächst konzeptioniert und schließlich auch implementiert werden. Es stehen verschiedene reale Instanzen zur Verfügung, die zum Testen des Verfahrens verwendet werden können. Anhand der Testergebnisse soll die Eignung der Heuristik evaluiert und kritisch beurteilt werden.

Literaturhinweise:

  1. Lusby, R. M.; Larsen, J.; Ehrgott, M. & Ryan, D. (2011). Railway track allocation: models and methods OR Spectrum, 33(4), 843-883. Verfügbar unter http://dx.doi.org/10.1007/s00291-009-0189-0
  2. Tormos, P., Lova, A., Barber, F., Ingolotti, L., Abril, M., & Salido, M. A. (2008). A genetic algorithm for railway scheduling problems. In Metaheuristics for Scheduling in Industrial and Manufacturing Applications (S. 255-276). Springer Berlin Heidelberg. Verfügbar unter http://users.dsic.upv.es/grupos/gps/papers/Genetic-Railway.pdf  
  3. Dréo, J., Petrowski, A., Siarry, P. & Taillard, E. (2006). Metaheuristics for hard optimization: Methods and Case Studies. Springer-Verlag Berlin Heidelberg.
  4. Michalewicz, Z., & Fogel, D. B. (2004). How to solve it: modern heuristics. Springer.

 

 

icon3_department_wirtschaftsinformatik
Visit www.or2017.de ...