Optimierung integrierter Planungsprozesse im öffentlichen Personenverkehr

Projektbeteiligte

Prof. Dr. Uwe Suhl
Freie Universität Berlin
Fachbereich Wirtschaftswissenschaften

Prof. Dr. Leena Suhl
Universität Paderborn
Lehrstuhl für Wirtschaftsinformatik 4

PD Dr. Taieb Mellouli
Universität Paderborn
Fakultät für Wirtschaftswissenschaften
und Hapag-Lloyd Flug GmbH

Zusammenfassung

Der öffentliche Personenverkehr (ÖPV), sei es mit Flugzeug, Bahn oder Bus, basiert in der Regel auf festen Fahr- oder Flugplänen, die für eine gegebene Periode veröffentlicht und in einem oft sehr komplexen Verkehrsnetz ausgeführt werden.
Die Produktionsplanung und -steuerung im ÖPV wird aufgrund ihrer mathematischen Komplexität in verschiedene, hierarchisierte Planungsstufen unterteilt: Basierend auf der Nachfrageprognose sowie der Netzwerk- und Kapazitätsplanung werden in der Produktplanung die Transportangebote und deren Kapazitäten festgelegt. In der Phase Produktionsplanung und -scheduling werden die Abfahrts- und Ankunftszeiten, beteiligte Flotten und deren Umläufe bestimmt. Zur operativen Planungsphase gehören Zuordnung der physischen Fahrzeuge, Besatzungseinsatzplanung sowie Scheduling der stationären Operationen.
Weil die Schritte jedoch nicht unabhängig voneinander sind, könnte die Ressourcennutzung durch eine starke Rückkopplung, oder - weitaus besser - durch eine parallele Durchführung aller Planungsschritte i. d. R. signifikant verbessert werden.
Darum besteht die primäre Zielsetzung dieses Forschungsprojektes darin, die Potenziale integrierter Planungssysteme zu untersuchen. Dabei sollen Problemstellungen, die mehrere Planungsschritte integrieren, betrachtet und deren Lösbarkeit durch neue Modellierungs- und Lösungstechniken verbessert werden, bspw. durch parallele oder iterative Lösungsmethoden zwischen Planungsphasen, aber insbesondere auch durch effizientere Lösung integrierter Modellformulierungen. Dabei soll ein besonderer Schwerpunkt auf exakt optimale Lösungsmethoden, insbesondere die gemischt-ganzzahlige mathematische Programmierung, gelegt werden. Durch Einbringung von die Problemstruktur ausnutzenden mathematischen Lösungstechniken direkt in die numerischen Routinen des State-of-the-Art-Optimierers MOPS versprechen sich die Autoren große Fortschritte in der Anwendbarkeit der Methodik.

Das Forschungsprojekt wird gemeinsam von folgenden Forschergruppen durchgeführt:
· Prof. Dr. Leena Suhl, Universität Paderborn
· Prof. Dr. Uwe Suhl, Freie Universität Berlin
· PD Dr. Taïeb Mellouli, Universität Paderborn und Hapag-Lloyd Flug, Hannover

Gesamtziel und Abgrenzung

Die auf aggregierte Time-Space-Flussnetzwerke basierende MIP-Modellierungstechnik brachte in vorangegangenen Forschungsprojekten am Lehrstuhl von Leena Suhl, Universität Paderborn, sehr gute Ergebnisse bei der Lösung von integrierten Planungsproblemen sowohl für das Crew Scheduling, die Busumlauf- und Dienstplanung des ÖPNV als auch für die Umlauf- und Wartungsplanung für Lokomotiven im Bahnverkehr. Mehrfach konnten insbesondere durch die zweistufige Aggregationsmethode größere als die bisher in der Literatur dokumentierten Probleme optimal gelöst werden.
Die bisherigen Erfahrungen sind sehr positiv, jedoch können heute bei Weitem nicht alle praxisrelevanten Planungsprobleme optimal gelöst werden. Das Forschungsprojekt setzt sich zum Ziel, die Technologie der gemischt-ganzzahligen Programmierung für aggregierte Time-Space-Flussnetzwerke des ÖPV weiter zu entwickeln und mit anderen Modellierungsmethoden zu vergleichen. Hauptsächlich soll die schrittweise Integration von zwei nacheinander liegenden Schritten betrachtet werden.
Der Stand der Technik soll so erweitert werden, dass
- größere integrierte Modelle als bisher optimal gelöst werden können, sowie
- Modelle praxisrelevanter Größe in akzeptabler Zeit gelöst werden können.
Diese Zielsetzung ist vor allem durch die Expertise und langjährige Erfahrung im Bereich der gemischt-ganzzahligen Programmierung begründet. Heuristische Verfahren werden zur Ergänzung und Steuerung der exakten Such- und Lösungsmethoden entwickelt; im Projekt soll jedoch nicht explizit auf Metaheuristiken oder spezielle Heuristiken als Lösungsalgorithmen eingegangen werden.
Als Anwendungsgebiet wird zunächst Airline Crew Scheduling betrachtet. Die Eignung der entwickelten Techniken wird aber auch für integrierte Busumlauf- und Diensteinsatzplanungsprobleme getestet.
Unsere bisherigen ersten Untersuchungen deuten darauf hin, dass die beabsichtigte Laufzeitreduzierung durch folgende Maßnahmen erreicht werden kann:
  • Ausnutzung der speziellen Eigenschaften von Time-Space-Netzwerkmodellen, um schneller gute ganzzahlige Lösungen zu finden (intelligente Branching-Strategien; "Fix-and-branch")
  • Einfügen von Schnittebenen, die ebenfalls spezielle Eigenschaften von Time-Space-Netzwerken ausnutzen (intelligente Cut-Strategien; "Branch-and-cut")
  • Verbesserung der Behandlung von Degeneriertheit im primalen und dualen Simplex-Verfahren
  • Problembasierte Auswahlkriterien der LP-Optimierungsmethode: primaler/dualer Simplex mit einer geeigneten Pricing-Srategie vs. Barrier-Methode

Förderung

Das Projekt wird gefördert von der Deutschen Forschungsgemeinschaft (DFG)