The Integrated Optimization of School Starting Times and Public Transport

Die vorliegende Dissertation beschaftigt sich mit der Formulierung und Losung eines mathematischen Modells zur integrierten Optimierung der Schulanfangszeiten und des Nahverkehrsangebots, kurz: IOSANA. Ziel ist es, die Schulanfangszeiten in die Optimierung der Abfahrtszeiten und derUmlaufe von Bussen des offentlichen Personennahverkehrs (OPNV) einzubeziehen, um auf diese Weise Einsparungen bei der Anzahl der eingesetzten Fahrzeuge gegenuber 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. Fur diese neue Problemklasse fuhren 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 Komplexitatstheorie) wie auch praktisch schwer zu losen. Zur Losung entwickeln und vergleichen wir daher verschiedene primale undduale Verfahren. Auf der primalen Seite erweitern wir bekannte Heuristiken (sogenannte Greedy-Verfahren) zunachst um Aspekte der Kopplung von Zeitfenstern. Der nachste 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 fur die Anzahl der eingesetzten Busse zu erhalten. Zur Verbesserung dieser Schranken untersuchen wir Moglichkeiten, die Modellformulierung zu verscharfen. Als besonders wirksam stellt sich die Reformulierung als Set-Partitioning-Problem heraus, wodurch jedoch die Zulassigkeit verloren geht. Wir stellen die Resultate der in dieser Arbeit entwickelten Verfahren anhand verschiedener zufallig generierter und realer Instanzen vor. Reale Datensatze aus funf verschiedenen deutschen Landkreisen wurden von unserem Projektpartner BPI-Consult zur Verfugung gestellt. Unsere Losungen vergleichen wir mit dem Status-Quo in den jeweiligen Landkreisen. Eine Einsparung von 10-30 % der Fahrzeugflotte ist durch den Einsatz der integrierten Optimierung moglich. 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 jahrlich. Rechnet man dieses auf alle 323 Landkreise Deutschlands hoch, so ergeben sich Einsparungen von bis zu 300 Mio. Euro an jahrlichen Zuschussen der Landkreise fur die Schulerbeforderung im OPNV.