- Scheduling von Schleusungsvorgängen: Algorithmen zur Verkehrsoptimierung am Beispiel des Nord-Ostsee-Kanals
- Inhaltsverzeichnis
- Kapitel 0: Einleitung
- Kapitel 1: Schleusungen am NOK
- 1.1 Grundlegende Funktionsweise von Schleusen
- 1.2 Vereinfachende Modellannahmen
- 1.3 Schiffspassagen
- 1.4 Zeitlicher Ablauf von Schleusungen
- 1.5 Positionierung von Schiffen in Schleusenkammern
- 1.6 Grafische Darstellung von Lösungen
- 1.7 Bewertung von Lösungen
- Kapitel 2: Das Lock-Scheduling-Problem (LSP)
- 2.1 Formales Modell
- 2.1.1 Die gegebenen Daten
- 2.1.2 Die Daten einer Lösung
- 2.1.3 Weitere wichtige Daten
- 2.1.4 Zulässigkeit
- 2.1.5 Die Kostenfunktion
- 2.2 Anwendungen des LSPs
- 2.3 Komplexitätsanalyse
- Kapitel 3: Einordnung in die Literatur
- 3.1 Bisherige Untersuchungen des Problems
- 3.2 Management der Schleusungen auf anderenWasserwegen
- 3.3 Die Verwandtschaft mit dem Truck-Scheduling-Problem
- Kapitel 4: Algorithmische Lösungsverfahren
- 4.1 Berechnung der Schleusungen einer Lösung
- 4.1.1 Entscheidung für spät ankommende Schiffe
- 4.1.2 Positionierung der Schiffe
- 4.1.3 Gesamtlaufzeit für die Berechnung der Schleusungen
- 4.1.4 Verhinderung von Kollisionen
- 4.2 Generierung initialer Lösungen
- 4.3 Lokale Suche
- 4.3.1 Nachbarschaften
- 4.3.2 Hill-Climbing
- 4.4 Weitere Optimierungsverfahren
- 4.4.1 Postoptimierung
- 4.4.2 Verschlechterungsschritte
- 4.5 Gesamtablauf
- Kapitel 5: Qualität der berechneten Lösungen
- 5.1 Untere Kostenschranken
- 5.1.1 Einfahrt der Schiffe in der Ankunftsreihenfolge
- 5.1.2 Einfahrt der Schiffe in beliebiger Reihenfolge
- 5.1.3 Kombination mehrerer unterer Schranken
- 5.1.4 Anwendung auf einige Probleminstanzen
- 5.2 Untere Schranken an den Approximationsfaktor
- Kapitel 6: Empirische Analyse
- 6.1 Vorgehen bei der Durchführung von Testläufen
- 6.1.1 Simulierung der gegebenen Daten
- 6.1.2 Verschiedene Berechnungsweisen
- 6.1.3 Zielvariablen
- 6.1.4 Weitere Variablen
- 6.2 Ergebnisse mit Kanal-Programm
- 6.2.1 Einschränkung der Parameter
- 6.2.2 Explorative Analyse
- 6.2.3 Auswahl der besten Berechnungsweisen
- 6.2.4 Statistische lineare Modelle
- 6.3 Ergebnisse ohne Kanal-Programm
- 6.3.1 Einschränkung der Parameter
- 6.3.2 Explorative Analyse
- 6.3.3 Auswahl der besten Berechnungsweisen
- 6.3.4 Statistische lineare Modelle
- Schlusswort
- Anhang
- A Legende für Positions- und Ablaufdiagramme
- B Bemerkungen zur Programmierung desSchleusungs-Programms
- C Abkürzungsverzeichnis
- Liste der Algorithmen
- Abbildungsverzeichnis
- Literaturverzeichnis
Textprobe:
Kapitel 2.2, Anwendungen des LSPs:
Das vorliegende Optimierungsproblem tritt nicht nur bei Schleusen auf. Wir geben nun eine Übersicht über mögliche Anwendungen des LSPs. Bei dieser Gelegenheit wiederholen wir noch einmal einige wichtige Voraussetzungen für die Anwendbarkeit auf die Planung von Schleusungsvorgängen.
Schiffsschleusen:
Das LSPs kann nur dann auf die Ablaufplanung von Schleusungen bei einer Schleuse angewandt werden, wenn folgenden Bedingungen erfüllt sind:
- Die Schleusenkammern sind parallel angeordnet.
- Die Schleusenkammern sind parallel angeordnet. ist die Verhinderung von Kollisionen nach Bemerkung 1.6.
- Die Füllzeit ist nur von der Schleusenkammer und nicht etwa von den Gezeiten abhängig.
- Die Schiffe können eigenständig fahren und werden nicht in mehrere physische Teile aufgeteilt.
- Die Daten aller Schiffe sind im Voraus bekannt. Interaktionen der Schleusungsvorgänge an verschiedenen Schleusen-Standorten müssen von einem übergeordneten Algorithmus behandelt werden. Beim NOK geschieht dies, wie in der Einleitung beschrieben, durch aufeinanderfolgende überlappende Zeithorizonte.
Gütertransport z.B. bei Autofähren:
Ein Anwendungsbeispiel, das überraschenderweise ebenfalls mit Schifffahrt zu tun hat, liegt bei Autofähren vor: Voneinander unabhängige Fähren, die den Schleusenkammern entsprechen, transportieren Fahrzeuge verschiedener Größen zwischen zwei Ufern hin und her. Die Fahrzeuge kommen an den Ufern wie die Schiffe an den beiden Seiten einer Schleuse zu zufälligen Zeitpunkten an und sollen jeweils mit möglichst kurzer Wartezeit überführt werden. Ähnliche Anwendungen findet man bei Güterzügen und Lastenaufzügen, sofern sie ebenfalls Güter zwischen zwei Stationen hin- und hertransportieren.
Verladestationen:
Auch auf Verladestationen wäre das Problem anwendbar, wenn z.B. Container von Kränen zwischen zwei Terminals umgeladen werden. Auf die Verwandtschaft des LSPs mit dem Truck-Scheduling-Problem (TrSP), das bei Verladehäfen angewandt wird, werden wir in Kapitel 3.3 näher einge
