Algorithmen zum Scheduling von Schleusungsvorgangen: 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 moglichst zugig geschleust werden. Diese Studie prasentiert algorithmische Losungsverfahren fur die Planung der Schleusungsvorgange auf dem Nord-Ostsee-Kanal (NOK). Auch bei vielen anderen Schleusen ist eine Anwendung unter einigen Voraussetzungen ohne weiteres moglich. Zudem werden interessante Verwandtschaften zum Truck Scheduling und Machine Scheduling, insbesondere im Guterverkehr, bei Container-Terminals und Autofahren 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. Zustzlich zu den statistischen Analysen werden Abschtzungen fr die Qualittsunterschiede von berechneten und optimalen Lsungen hergeleitet.