Diplomarbeit


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


TU Berlin, Oktober 2010, Note 1,3


Beim sozialen Buchhandel buch7.de:

Coverbild

Hier die Seite beim Diplomica Verlag.

Die vorgestellten Algorithmen wurden in Java implementiert. Informationen zur Applikation und zum Download finden Sie hier.


Inhalt


Einleitung
  1. Schleusungen auf dem Nord-Ostsee-Kanal (NOK)
    1. Grundlegende Funktionsweise von Schleusen
    2. Vereinfachende Modellannahmen
    3. Schiffspassagen
    4. Zeitlicher Ablauf von Schleusungen
    5. Positionierung von Schiffen in Schleusenkammern
    6. Grafische Darstellung von Lösungen
    7. Bewertung von Lösungen
  2. Das Lock-Scheduling-Problem (LSP)
    1. Formales Modell
    2. Anwendungen des LSPs
    3. Komplexitätsanalyse
  3. Einordnung in die Literatur
    1. Bisherige Untersuchungen des Problems
    2. Management der Schleusungen auf anderen Wasserwegen
    3. Die Verwandschaft mit dem Truck-Scheduling-Problem
  4. Algorithmische Lösungsverfahren
    1. Berechnung der Schleusungen einer Lösung
    2. Generierung initialer Lösungen
    3. Lokale Suche
    4. Weitere Optimierungsverfahren
    5. Gesamtablauf
  5. Qualität der berechneten Lösungen
    1. Untere Kostenschranken
    2. Untere Schranken an den Approximationsfaktor
  6. Empirische Analyse
    1. Vorgehen bei der Durchführung von Testläufen
    2. Ergebnisse mit Kanal-Programm
    3. Ergebnisse ohne Kanal-Programm
Schlusswort
Anhang
Liste der Algorithmen
Abbildungsverzeichnis
Literaturverzeichnis


Katalogtext


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.