Schleusenmanagement

Software zum Scheduling von Schleusungsvorgängen



Download & Kollaboration


Diese Software wird auf Sourceforge.net unter der MIT-Lizenz zur Verfügung gestellt.

http://sourceforge.net/projects/lockscheduling/

Gerne können Sie an der Weiterentwicklung mitwirken. Kontaktieren Sie mich dazu.


Forschungsprojekt


Die Anwendung ist im Rahmen meiner Diplomarbeit entstanden, die Teil einer Studie der TU Berlin für die Wasser- und Schifffahrtsverwaltung des Landes Schleswig-Holstein war. Dabei handelte es sich um Verkehrsoptimierung auf dem Nord-Ostsee-Kanal. Genauere Informationen zu dieser Studie sind auf der Webseite der Forschungsgruppe "Kombinatorische Optimierung und Graphenalgorithmen" der TU Berlin zu finden.


Anwendbarkeit


Die vorliegende Software kann sowohl auf Schleusen-Standorte bei Mündungen als auch bei Binnengewässern angewandt werden. Es sollten folgende Voraussetzungen erfüllt sein:

Schleusenkammern:
  • Die Schleusenkammern sind parallel angeordnet.
  • Sie führen unabhängig voneinander Schleusungen durch.
  • Die Zeiten zum Füllen bzw. Leeren einer Schleusenkammer sowie zum Öffnen und Schließen der Kammertore ist nur von den Gegebenheiten der Kammer und nicht etwa von den Gezeiten abhängig. D.h. bei Schleusen an Mündungen werden die Gezeiten vernachlässigt.
Schiffe:
  • Die Schiffe können eigenständig fahren und werden nicht in mehrere physische Teile aufgeteilt.
  • Die Daten aller Schiffe (v.a. Abmessungen und Ankunft beim Warteraum) sind im Voraus bekannt.
    Ist dies nicht der Fall, so muss ein übergeordneter Algorithmus diese Bedingung sicherstellen. Dies ist z.B. notwendig, wenn Interaktionen der Schleusungsvorgänge zwischen verschiedenen Schleusen-Standorten existieren. Eine Lösungsmöglichkeit wäre, die Schleusungen jeweils für aufeinanderfolgende überlappende Zeithorizonte zu berechnen.
Bevorzugung von Schiffen:
  • Normalerweise ist jedes Schiff gleichberechtigt. Dies hat zur Folge, dass große Schiffe aus Platzgründen oft längere Zeit warten müssen, während zuerst mehrere kleine Schiffe zusammen geschleust werden. Das kann jedoch durch einfache Modifikationen angepasst werden, z.B. indem man in der Kostenfunktion die Wartezeiten großer Schiffe mehrfach zählt oder die Wartezeiten der Schiffe jeweils mit ihrer Grundfläche oder ihrem Volumen multipliziert.
  • Die FCFS-Regel lässt sich an- und ausschalten. Sie besagt, dass Schiffe pro Fahrtrichtung und Schleusenkammer in der Reihenfolge ihrer Ankunft einfahren müssen.
Positionierung der Schiffe in Schleusenkammern:
  • Alle Schiffe müssen direkt an der linken oder rechten Wand der Schleusenkammer liegen.
    Bei anderen Anforderungen an die Positionierung in den Kammern muss im Wesentlichen nur der Teilalgorithmus verändert werden, der dieses Packing behandelt.
  • Die Sicherheitsabstände vor / hinter und neben den Schiffen in den Schleusenkammern sind konstant.
    Andernfalls sind ebenfalls im Wesentlichen nur Änderungen des Packings nötig.
Ein- und Ausfahrten der Schiffe:
  • Die Ein- und Ausfahrtzeiten der Schiffe von den beiden Warteräumen in die Schleusenkammern und umgekehrt sind nur von der Fahrtrichtung und dem Schleusen-Standort abhängig.
  • Die Sicherheitszeiten vor und zwischen den Ein- und Ausfahrten der Schiffe sind nur von der Fahrtrichtung und der Schleusenkammer abhängig.
  • Wenn mehrere Schleusenkammern existieren, können sich Schiffe bei der Ein- und Ausfahrt in / aus Schleusenkammern kreuzen. Das wird momentan nicht berücksichtigt und muss extern abgesichert werden.
  • Die Schiffe fahren in der Reihenfolge ihrer Einfahrt in eine Schleusenkammer auch wieder aus.


Inhalt der Software


Der Hauptbestandteil sind kombinierbare und variierbare Algorithmen zum Scheduling von Schleusungsvorgängen.

Zielfunktion:

Das Ziel ist v.a., die Wartezeiten der Schiffe zu minimieren. Auch manche andere Größen können in der Zielfunktion nach Bedarf gewichtet werden.

Lösungsstrategie:

Es wurde v.a. die mathematische Technik der lokalen Suche verwendet. Initiale Lösungen werden durch iterative und alternierende Anwendung verschiedener Nachbarschafts-Gruppen optimiert.

Eingabe der Problemdaten:

Die Eingabe der Daten der Probleminstanzen erfolgt mit XML-Dateien und ist daher sehr flexibel. Zudem lassen sich eine beträchtliche Anzahl von Parametern, die von den Algorithmen verwenden werden, im Quellcode verändern.

Weitere Features:
  • Grafische Darstellung der berechneten Lösungen (siehe Abbildung 1 unten).
  • Grafische Darstellung der lokalen Suche (siehe Abbildung 2 unten)
  • Randomisierte Generierung von Probleminstanzen (Schiffe, Schleusenkammern sowie deren initialer Status)
  • Ausführliches Framework für die Analyse der Algorithmen und der berechneten Lösungen:
    • Generierung von Testinstanzen
    • Simulation mit mehreren parallelen Rechnern, Speicherung wichtiger Daten über die berechnete Lösung, die Berechnung an sich und die aktuellen Parameter
    • R/JGR-Code für multivariate statistische Analysen, z.B. für die Auswahl der besten Parameterkombinationen
  • Berechnung unterer Schranken für die Kosten der Lösungen
  • Generierung optimaler Lösungen und Vergleich mit der jeweiligen Lösung, die vom Algorithmus berechnet wird
  • Vergleich der Kosten von Lösungen, die für dieselbe Probleminstanz mit unterschiedlichen Parametern berechnet werden

Abbildungen


1. Grafische Darstellung von Lösungen


Grafische Darstellung von Lösungen
Abbildung 1: Grafische Darstellung von Lösungen

Die obere Tabelle zeigt Daten der berechneten Lösung. Die zweite Tabelle enthält die Eingabedaten der Schleusenkammern und Daten der Lösung bezogen auf die einzelnen Schleusenkammern.

Die Grafik veranschaulicht schließlich die Lösung. Die vertikale Achse ist der Zeitverlauf. Die Vorgänge bei den einzelnen Schleusenkammern sind durch senkrechte schwarze Linien getrennt.

Die hellblauen Balken stehen für den Zeitraum, der jeweils für ein Schiff relevant ist, also von der Ankunft beim Warteraum bis zur Ausfahrt aus der Schleusenkammer (waagrechte pinke Linie). Die Zahlen sind die IDs der Schiffe. Die gelben Abschnitte stellen die Einfahrt des Schiffs in die Kammer dar. Eventuell angezeigte rote Abschnitte stehen für den spätesten Zeitraum, zu dem das Schiff einfahren kann, ohne die Ausführung der Schleusung zu verzögern.

In der Mitte der Darstellung für eine Kammer befindet sich ein Balken, der die direkt bei der Kammer stattfindenden Ereignisse zeigt. Hellgraue und dunkelgraue Abschnitte zeigen Schleusungsvorgänge der beiden Fahrtrichtungen. Die enthaltenen Schiffe sind entsprechend links oder rechts vom Balken gezeichnet. Die Einfahrt und Ausfahrt der Schiffe erfolgt in der Reihenfolge von außen nach innen.

Die dunkelblauen Abschnitte stellen die Schleusungs-Ausführungen dar, d.h. das Schließen des Einfahrtstores, das Anpassen des Wasserstandes und das Öffnen des Ausfahrtstores. Diese Zeiträume sind durch zwei weiße Linien getrennt. Die grünen Abschnitte auf den Schleusungs-Balken stehen für Sicherheits-Zeiten, die jeweils vor der Ein- oder Ausfahrt eines Schiff eingehalten werden muss.

Zu den einzelnen Grafikelementen werden Tooltips mit detaillierten Informationen angezeigt, wenn man daraufklickt. Die betrifft z.B. die hellblauen Schiffs-Balken, die Einfahrten der Schiffe und die Schleusungs -Ausführungen. Bei den grauen Schleusungs-Abschnitten werden im Tooltip die Positionen der enthaltenen Schiffe in der Schleusenkammer aus der Vogelperspektive gezeigt.


2. Grafische Darstellung der lokalen Suche


Grafische Darstellung der lokalen Suche
Abbildung 2: Grafische Darstellung der lokalen Suche

Die Grafik veranschaulicht die lokale Suche, die vom Algorithmus für eine bestimmte Probleminstanz durchgeführt wurde. Jeder Knoten steht für eine Lösung. Die vertikale Achse zeigt die Kosten und die horizontale Achse die Anzahl der Suchschritte. Die Knoten von Nachbarlösungen sind jeweils durch eine Kante verbunden.

Beim Anklicken eines Knotens wird für die entsprechende Lösung ein neues Fenster mit Abbildung 1 geöffnet. Fährt man nur mit der Maus über einen Knoten, so werden Informationen über die Lösung in einem Tooltip angezeigt.