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.
