Algorithmen zum Scheduling von Schleusungsvorgängen: Verkehrsoptimierung am Beispiel des Nord-Ostsee-Kanals

Mit zunehmendem Verkehrsaufkommen auf internationalen Wasserwegen ist eine rechnergesteuerte Verkehrsoptimierung an Schiffsschleusen unausweichlich. Das wichtigste Kriterium dabei ist, dass ankommende Schiffe möglichst zügig geschleust werden. Diese Studie präsentiert algorithmische Lösungsverfahren für die Planung der Schleusungsvorgänge auf dem Nord-Ostsee-Kanal (NOK). Auch bei vielen anderen Schleusen ist eine Anwendung unter einigen Voraussetzungen ohne weiteres möglich. Zudem werden interessante Verwandtschaften zum Truck Scheduling und Machine Scheduling, insbesondere im Güterverkehr, bei Container-Terminals und Autofähren aufgezeigt.

Wie viele Probleme der kombinatorischen Optimierung ist das Scheduling von Schleusungsvorgängen NP-schwer, d. h. optimale Lösungen (Fahrpläne) können meist nicht in akzeptabler Rechenzeit gefunden werden. U. a. mit Hilfe von lokaler Suche werden jedoch Fahrpläne berechnet, die für die Anwendung beim NOK sehr zufriedenstellend sind, denn die Schiffe müssen im Durchschnitt nur wenige Minuten warten. Des weiteren wird mit multivariaten statistischen Verfahren und einer großen Menge von Daten des NOKs ermittelt, bei welchen Parameterkombinationen die besten Ergebnisse erzielt werden.

Das Problem wird am Beispiel des NOKs in allen Details anschaulich beschrieben und auf dieser Grundlage mathematisch modelliert. Es handelt sich um eine Kombination aus Packing und Scheduling: Schiffe beider Fahrtrichtungen sind Schleusenkammern zuzuordnen und in Schleusungsvorgänge zu gruppieren, sodass die Schiffe einer Schleusung in die entsprechende Kammer passen. Festzulegen sind die Zeitpunkte der Schleusungsvorgänge sowie der Ein- und Ausfahrten der Schiffe.

Die Studie enthält auch eine ausführliche Literaturrecherche über bisherige Untersuchungen des Problems und das Schleusenmanagement bei anderen bekannten Wasserwegen. Die Komplexität des Problems an sich sowie die Laufzeiten der vorgestellten Algorithmen werden jeweils angegeben und bewiesen. Zusätzlich zu den statistischen Analysen werden Abschätzungen für die Qualitätsunterschiede von berechneten und optimalen Lösungen hergeleitet.

1;Inhaltsverzeichnis;3 2;Kapitel 0 Einleitung;7 3;Kapitel 1 Schleusungen am NOK;11 3.1;1.1 Grundlegende Funktionsweise von Schleusen;11 3.2;1.2 Vereinfachende Modellannahmen;12 3.3;1.3 Schiffspassagen;13 3.4;1.4 Zeitlicher Ablauf von Schleusungen;15 3.5;1.5 Positionierung von Schiffen in Schleusenkammern;19 3.6;1.6 Grafische Darstellung von Lösungen;20 3.7;1.7 Bewertung von Lösungen;22 4;Kapitel 2 Das Lock-Scheduling-Problem (LSP);25 4.1;2.1 Formales Modell;25 4.1.1;2.1.1 Die gegebenen Daten;26 4.1.2;2.1.2 Die Daten einer Lösung;27 4.1.3;2.1.3 Weitere wichtige Daten;28 4.1.4;2.1.4 Zulässigkeit;29 4.1.5;2.1.5 Die Kostenfunktion;34 4.2;2.2 Anwendungen des LSPs;35 4.3;2.3 Komplexitätsanalyse;37 5;Kapitel 3 Einordnung in die Literatur;41 5.1;3.1 Bisherige Untersuchungen des Problems;41 5.2;3.2 Management der Schleusungen auf anderen Wasserwegen;43 5.3;3.3 Die Verwandtschaft mit dem Truck-Scheduling-Problem;46 6;Kapitel 4 Algorithmische Lösungsverfahren;49 6.1;4.1 Berechnung der Schleusungen einer Lösung;51 6.1.1;4.1.1 Entscheidung für spät ankommende Schiffe;55 6.1.2;4.1.2 Positionierung der Schiffe;58 6.1.3;4.1.3 Gesamtlaufzeit für die Berechnung der Schleusungen;64 6.1.4;4.1.4 Verhinderung von Kollisionen;65 6.2;4.2 Generierung initialer Lösungen;66 6.3;4.3 Lokale Suche;70 6.3.1;4.3.1 Nachbarschaften;70 6.3.2;4.3.2 Hill-Climbing;81 6.4;4.4 Weitere Optimierungsverfahren;84 6.4.1;4.4.1 Postoptimierung;84 6.4.2;4.4.2 Verschlechterungsschritte;87 6.5;4.5 Gesamtablauf;89 7;Kapitel 5 Qualität der berechneten Lösungen;91 7.1;5.1 Untere Kostenschranken;92 7.1.1;5.1.1 Einfahrt der Schiffe in der Ankunftsreihenfolge;93 7.1.2;5.1.2 Einfahrt der Schiffe in beliebiger Reihenfolge;97 7.1.3;5.1.3 Kombination mehrerer unterer Schranken;101 7.1.4;5.1.4 Anwendung auf einige Probleminstanzen;102 7.2;5.2 Untere Schranken an den Approximationsfaktor;105 8;Kapitel 6 Empirische Analyse;107 8.1;6.1 Vorgehen bei der Durchführung von Testläufen;107 8.1.1;6.1.1 Simulierung der gegebenen Daten;1
07 8.1.2;6.1.2 Verschiedene Berechnungsweisen;108 8.1.3;6.1.3 Zielvariablen;110 8.1.4;6.1.4 Weitere Variablen;110 8.2;6.2 Ergebnisse mit Kanal-Programm;111 8.2.1;6.2.1 Einschränkung der Parameter;111 8.2.2;6.2.2 Explorative Analyse;113 8.2.3;6.2.3 Auswahl der besten Berechnungsweisen;125 8.2.4;6.2.4 Statistische lineare Modelle;126 8.3;6.3 Ergebnisse ohne Kanal-Programm;127 8.3.1;6.3.1 Einschränkung der Parameter;127 8.3.2;6.3.2 Explorative Analyse;127 8.3.3;6.3.3 Auswahl der besten Berechnungsweisen;134 8.3.4;6.3.4 Statistische lineare Modelle;135 9;Schlusswort;141 10;Anhang;143 11;Liste der Algorithmen;147 12;Abbildungsverzeichnis;149 13;Literaturverzeichnis;153