The Integrated Optimization of School Starting Times and Public Transport

Die vorliegende Dissertation beschäftigt sich mit der Formulierung und Lösung eines mathematischen Modells zur integrierten Optimierung der Schulanfangszeiten und des Nahverkehrsangebots, kurz: IOSANA. Ziel ist es, die Schulanfangszeiten in die Optimierung der Abfahrtszeiten und der
Umläufe von Bussen des öffentlichen Personennahverkehrs (ÖPNV) einzubeziehen, um auf diese Weise Einsparungen bei der Anzahl der eingesetzten Fahrzeuge gegenüber dem Status-Quo zu erzielen.

Das zu Grunde liegende mathematische Modell ist eine Erweiterung des bekannten Tourenplanungsproblems mit Zeitfenstern. Der neue Aspekt sind Kopplungsbedingungen innerhalb der Zeitfenster. Für diese neue Problemklasse führen wir die Bezeichnung Tourenplanungsproblem mit gekoppelten Zeitfenstern ein. IOSANA ist damit zugleich ein erster Anwendungsfall eines derartigen Modells mit gekoppelten Zeitfenstern. Instanzen dieses Problems sind theoretisch (im Sinne der Komplexitätstheorie) wie auch praktisch schwer zu lösen. Zur Lösung entwickeln und vergleichen wir daher verschiedene primale und
duale Verfahren.

Auf der primalen Seite erweitern wir bekannte Heuristiken (sogenannte Greedy-Verfahren) zunächst um Aspekte der Kopplung von Zeitfenstern. Der nächste naheliegende Schritt ist die Parametrisierung der Auswahlfunktion, welche die Suchrichtung der Heuristik steuert. Zur Bestimmung "guter" Parameterwerte verwenden wir unter anderem Improving Hit-and-Run, ein zufallsbasiertes Verfahren der Globalen Optimierung.

Da es sich bei IOSANA um ein ganzzahliges lineares Programm handelt, lassen sich Branch-and-Cut Verfahren einsetzen, um untere Schranken für die Anzahl der eingesetzten Busse zu erhalten. Zur Verbesserung dieser Schranken untersuchen wir Möglichkeiten, die Modellformulierung zu verschärfen. Als besonders wirksam stellt sich die Reformulierung als Set-Partitioning-Problem heraus, wodurch jedoch die Zulässigkeit verloren geht.

Wir stellen die Resultate der in dieser Arbeit entwickelten Verfahren anhand verschiedener zufällig generierter und realer Instanzen vor. Reale Datensätze aus fünf verschiedenen deutschen Landkreisen wurden von unserem Projektpartner BPI-Consult zur Verfügung gestellt. Unsere Lösungen vergleichen wir mit dem Status-Quo in den jeweiligen Landkreisen.

Eine Einsparung von 10-30 % der Fahrzeugflotte ist durch den Einsatz der integrierten Optimierung möglich. Jeder eingesparte Bus ist in etwa 30.000 Euro pro Jahr wert. Pro Landkreis errechnen sich so Einsparungen von bis zu 1,4 Mio. Euro jährlich. Rechnet man dieses auf alle 323 Landkreise Deutschlands hoch, so ergeben sich Einsparungen von bis zu 300 Mio. Euro an jährlichen Zuschüssen der Landkreise für die Schülerbeförderung im ÖPNV.