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.