Algorithmen zum Scheduling von Schleusungsvorgngen

Mit zunehmendem Verkehrsaufkommen auf internationalen Wasserwegen ist eine rechnergesteuerte Verkehrsoptimierung an Schiffsschleusen unausweichlich. Das wichtigste Kriterium dabei ist, dass ankommende Schiffe mglichst zgig geschleust werden. Diese Studie prsentiert algorithmische Lsungsverfahren fr die Planung der Schleusungsvorgnge auf dem Nord-Ostsee-Kanal (NOK). Auch bei vielen anderen Schleusen ist eine Anwendung unter einigen Voraussetzungen ohne weiteres mglich. Zudem werden interessante Verwandtschaften zum Truck Scheduling und Machine Scheduling, insbesondere im Gterverkehr, bei Container-Terminals und Autofhren aufgezeigt.

Wie viele Probleme der kombinatorischen Optimierung ist das Scheduling von Schleusungsvorgngen NP-schwer, d.h. optimale Lsungen (Fahrplne) knnen meist nicht in akzeptabler Rechenzeit gefunden werden. U.a. mit Hilfe von lokaler Suche werden jedoch Fahrplne berechnet, die fr die Anwendung beim NOK sehr zufriedenstellend sind, denn die Schiffe mssen im Durchschnitt nur wenige Minuten warten. Des weiteren wird mit multivariaten statistischen Verfahren und einer groen 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 Schleusungsvorgnge zu gruppieren, sodass die Schiffe einer Schleusung in die entsprechende Kammer passen. Festzulegen sind die Zeitpunkte der Schleusungsvorgnge sowie der Ein- und Ausfahrten der Schiffe.

Die Studie enthlt auch eine ausfhrliche Literaturrecherche ber bisherige Untersuchungen des Problems und das Schleusenmanagement bei anderen bekannten Wasserwegen. Die Komplexitt des Problems an sich sowie die Laufzeiten der vorgestellten Algorithmen werden jeweils angegeben und bewiesen.