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

Inhaltsangabe:Einleitung: Der Nord-Ostsee-Kanal (NOK) führt von Kiel nach Brunsbüttel, wo die Elbe in die Nordsee mündet. Er ist 11m tief und knapp 100km lang. Den Daten der offiziellen Website des Bundesamtes für Seeschifffahrt und Hydrographie (BSH) zufolge beträgt die durch die Gezeiten verursachte Amplitude der Meeresspiegelhöhe, genannt Tidenhub, in Brunsbüttel etwa 3m und in Kiel ca. 30cm. Strömungen würden jedoch das Navigieren der Schiffe im ohnehin engen Kanal erheblich erschweren. Um den Wasserstand konstant zu halten, befindet sich an beiden Kanalenden eine Schleuse mit mehreren Schleusenkammern. Abbildung 0.1 zeigt die Schleuse in Brunsbüttel, wo genauso wie in Kiel zwei kleine und zwei große Kammern mit einer Länge von 125 bzw. 310m existieren. Im langjährigen Mittel passieren täglich etwa 100 Schiffe den NOK, der damit laut www.kiel-canal.org ‘die meistbefahrene künstliche Seeschifffahrtsstraße der Welt’ ist. Einzelne Schiffe sind bis zu 300m lang. Die Übermittlung von Schiffsdaten an die zentrale Kanalüberwachungsstelle erfolgt über ein sog. Automatisches Identifikationssystem (AIS). Gesendet werden u.a. die aktuelle Position, die Fahrtrichtung, die Geschwindigkeit und die Abmessungen der Schiffe. Die vierteljährlichen Informationen auf www.kiel-canal.org, der offiziellen Webseite des NOKs, zu dessen wirtschaftlicher Situation berichten von einem kontinuierlichen Trend zu immer größeren Schiffen. Die Anzahl der befahrenden Schiffe sei im vergangenen Jahrzehnt nur leicht gestiegen und im Jahr 2009 aufgrund der internationalen Wirtschaftskrise deutlich zurückgegangen. Langfristig erwarte man jedoch, dass sich das Wachstum der Schiffszahlen fortsetzt. Sowohl die vom NOK direkt und indirekt profitierende Industrie als auch die Wasser- und Schifffahrtsverwaltung des Bundes (WSV) als Betreiber haben ein Interesse daran, dass möglichst viele Schiffe den Kanal mit geringer Wartezeit passieren können. Dabei spielen die Schleusen eine entscheidende Rolle, denn die einzelnen Kammern benötigen für einen Schleusungsvorgang durchschnittlich etwa 30 Minuten und haben nur begrenzte räumliche Kapazitäten. Bevor allerdings Schleusenkammern vergrößert oder neu gebaut werden müssen, möchte man im Sinne der Wirtschaftlichkeit herausfinden, ob sich die Wartezeiten der Schiffe an den Schleusen unter den momentanen Gegebenheiten noch verringern lassen, sodass die bestehenden Kapazitäten effizienter genutzt werden. Dabei soll auch ermittelt werden, ob das [...]