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

Diplomarbeit von Martin Luy

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 Aufheben von Konventionen, v.a. bei der Einfahrtsreihenfolge der Schiffe, signifikante Verbesserungen ermöglichen würde.

Wir betrachten also für beide Schleusen das folgende Lock-Scheduling-Problem (LSP): Für eine Menge von Schiffen, deren Abmessungen, Fahrtrichtungen und Ankunftszeiten bei der Schleuse gegeben sind, soll ein nachfrageorientierter Schleusungs-Zeitplan erstellt werden. Solche Zeitpläne bezeichnen wir als Lösungen. Das wichtigste Kriterium dabei ist, dass die Passierzeit jedes Schiffs möglichst nahe an seiner bestmöglichen Passierzeit liegt. Derzeit erfolgt die Planung der Schleusungsvorgänge am NOK manuell, doch mit zunehmendem Verkehrsaufkommen wird es immer schwieriger, gute Lösungen mit geringen Wartezeiten zu finden. Ziel dieser Diplomarbeit ist deshalb die Entwicklung, Implementierung und Evaluation von Algorithmen für das LSP, die bzgl. der vorgegebenen Kriterien zulässige Lösungen mit möglichst hoher Qualität berechnen. Optimale Lösungen können jedoch selbst bei Einsatz von leistungsfähigen Rechnern meist nicht in akzeptabler Zeit gefunden werden, da das Problem NP-schwer ist.

Schiffe müssen nicht nur vor den Schleusen, sondern wegen der beschränkten Kanalbreite oft auch in verschiedenen Weichen innerhalb des Kanals warten, um andere Schiffe passieren zu lassen. Die drei Optimierungsprobleme des Kanals und der beiden Schleusen werden wegen ihrer Interaktionen kollektiv behandelt. Zuerst werden für die Schiffe, die sich zu einem initialen Zeitpunkt bereits im Kanal befinden, zulässige Fahrpläne bis zur Ankunft an einer Schleuse, genannt Routen, berechnet. Danach wird über aufeinanderfolgende überlappende Zeithorizonte in zeitlich aufsteigender Reihenfolge iteriert. Für jeden Zeithorizont wird zuerst die Optimierung der Schleusungsvorgänge durchgeführt. Dabei werden Schiffe, die spätestens zum Ende des Zeithorizonts an einer Schleuse ankommen und den Kanal verlassen wollen, ins Meer geschleust. In der Gegenrichtung kommen jeweils neue Schiffe durch die Schleuse in den Kanal. Die Schleusungen bis zu einem bestimmten Zeitpunkt werden fixiert. Schließlich werden die Routen aller Schiffe, die sich im momentanen Zeithorizont im Kanal befinden, optimiert. Dabei dürfen die Routen der Schiffe von bereits fixierten Schleusungen nur noch soweit verändert werden, dass ihre festgelegten Schleusungszeiten eingehalten werden.

Die meisten aus dem Meer kommenden Schiffe müssen ihre Daten erst etwa eine Stunde vor ihrer Ankunft an einer Schleuse melden, sodass es sich insgesamt um ein Online-Problem handelt. In dieser Diplomarbeit betrachten wir jedoch nur die Optimierung an den Schleusen und nicht die innerhalb des Kanals. Das Schleusungs-Programm, das für eine LSP-Instanz eine zulässige Lösung berechnen soll, wird vom übergeordneten Kanal-Programm für jeden Zeithorizont separat aufgerufen. Deshalb können wir für das LSP davon ausgehen, dass alle Schiffsdaten im Voraus bekannt sind; es liegt also ein Offline-Problem vor. Ein weiterer günstiger Effekt der Zeithorizonte auf das LSP ist, dass eine Probleminstanz nur einen kleinen Teil der Schiffe enthält und damit die Rechenzeit viel niedriger ist.

In Kapitel 1 werden nun die Anforderungen für die Optimierung der Schleusungsvorgänge am NOK detailliert beschrieben, anhand derer das Modell des LSPs entwickelt wurde. Die formale Problemdefinition, weitere Anwendungsmöglichkeiten und eine Komplexitätsanalyse folgen in Kapitel 2. Danach gibt Kapitel 3 eine Übersicht über bisherige Untersuchungen des Problems sowie die Planung der Schleusungsvorgänge auf anderen Wasserwegen und stellt ein verwandtes Optimierungsproblem vor. Obwohl das LSP in der hier behandelten Form bisher kaum untersucht und deshalb auch kaum angewandt wurde, tritt es bei der Ablaufplanung an vielen Schleusen, aber auch in einigen anderen Situationen auf. Entsprechend vielseitig einsetzbar sind die in Kapitel 4 vorgestellten Algorithmen zur Berechnung von Lösungen des LSPs. In Kapitel 5 werden mit Hilfe von unteren Kostenschranken die Qualitätsunterschiede zwischen optimalen und erzeugten Lösungen analysiert. Anhand von Daten des NOKs wird schließlich in Kapitel 6 die Qualität der Lösungen empirisch untersucht.

Inhaltsverzeichnis:

0.	Einleitung	1
1.	Schleusungen am Nord-Ostsee-Kanal (NOK)	5
1.1	Grundlegende Funktionsweise von Schleusen	5
1.2	Vereinfachende Modellannahmen	6
1.3	Schiffspassagen	7
1.4	Zeitlicher Ablauf von Schleusungen	9
1.5	Positionierung von Schiffen in Schleusenkammern	12
1.6	Grafische Darstellung von Lösungen	14
1.7	Bewertung von Lösungen	15
2.	Das Lock-Scheduling-Problem (LSP)	17
2.1	Formales Modell	17
2.1.1	Die gegebenen Daten	18
2.1.2	Die Daten einer Lösung	19
2.1.3	Weitere wichtige Daten	20
2.1.4	Zulässigkeit	21
2.1.5	Die Kostenfunktion	25
2.2	Anwendungen des LSPs	26
2.3	Komplexitätsanalyse	27
3.	Einordnung in die Literatur	31
3.1	Bisherige Untersuchungen des Problems	31
3.2	Management der Schleusungen auf anderen Wasserwegen	33
3.3	Die Verwandtschaft mit dem Truck-Scheduling-Problem	35
4.	Algorithmische Lösungsverfahren	37
4.1	Berechnung der Schleusungen einer Lösung	39
4.1.1	Entscheidung für spät ankommende Schiffe	42
4.1.2	Positionierung der Schiffe	46
4.1.3	Gesamtlaufzeit für die Berechnung der Schleusungen	51
4.1.4	Verhinderung von Kollisionen	52
4.2	Generierung initialer Lösungen	52
4.3	Lokale Suche	57
4.3.1	Nachbarschaften	57
4.3.2	Hill-Climbing	67
4.4	Weitere Optimierungsverfahren	70
4.4.1	Postoptimierung	70
4.4.2	Verschlechterungsschritte	73
4.5	Gesamtablauf	74
5.	Qualität der berechneten Lösungen	75
5.1	Untere Kostenschranken	76
5.1.1	Einfahrt der Schiffe in der Ankunftsreihenfolge	77
5.1.2	Einfahrt der Schiffe in beliebiger Reihenfolge	80
5.1.3	Kombination mehrerer unterer Schranken	84
5.1.4	Anwendung auf einige Probleminstanzen	84
5.2	Untere Schranken an den Approximationsfaktor	88
6.	Empirische Analyse	89
6.1	Vorgehen bei der Durchführung von Testläufen	89
6.1.1	Simulierung der gegebenen Daten	89
6.1.2	Verschiedene Berechnungsweisen	90
6.1.3	Zielvariablen	91
6.1.4	Weitere Variablen	92
6.2	Ergebnisse mit Kanal-Programm	92
6.2.1	Einschränkung der Parameter	93
6.2.2	Explorative Analyse	94
6.2.3	Auswahl der besten Berechnungsweisen	106
6.2.4	Statistische lineare Modelle	107
6.3	Ergebnisse ohne Kanal-Programm	108
6.3.1	Einschränkung der Parameter	108
6.3.2	Explorative Analyse	108
6.3.3	Auswahl der besten Berechnungsweisen	114
6.3.4	Statistische lineare Modelle	115
	Schlusswort	121
	Anhang	123
A.	Bemerkungen zur Programmierung des Schleusungs-Programms	123
B.	Beschreibung von Positions- und Ablaufdiagrammen	124
C.	Abkürzungsverzeichnis	124
	Liste der Algorithmen	127
	Abbildungsverzeichnis	129
	Literaturverzeichnis	131

Textprobe:

Kapitel 1.4, Zeitlicher Ablauf von Schleusungen:

In Kapitel 1.1 wurde der grobe zeitliche Ablauf von Schleusungen bereits dargestellt. Nun wollen wir ihn vertiefen.

Einfahrtsreihenfolge der Schiffe:

Für jede Schleusung wird festgelegt, in welcher Reihenfolge die enthaltenen Schiffe ein- und wieder ausfahren. Prinzipiell gibt es dafür keine Vorgaben, sofern keine Sequenzierungsregel angewandt wird.

Definition 1.2 (‘First-come-first-served’ (FCFS)). Die FCFS-Regel ist eine Sequenzierungsregel, die vorschreibt, dass die Schiffe pro Schleusenkammer und Fahrtrichtung in der Reihenfolge ihrer Ankunft beim Warteraum in die Kammer einfahren müssen.

Vorschriften für den Ablauf von Schleusungen:

Wie in Kapitel 1.2 vereinbart, nehmen wir an, dass die Füllzeit nur von der Schleusenkammer abhängig ist. Gleiches gilt für die Torzeit und damit auch für die Ausführungszeit. Zudem ist für jede Schleusenkammer ein initialer Zustand gegeben, der zwei Daten enthält: eine initiale Richtung, in der die erste Schleusung stattfinden wird, und eine initiale Startzeit, die ihren Beginn festlegt. Falls eine Schleusung keine Schiffe enthält, ist ihr Ende durch das Ende der Toröffnung und andernfalls durch den Ausfahrtszeitpunkt des letzten Schiffs gegeben. Das Ende einer Schleusung bestimmt jeweils den Beginn der nächsten Schleusung bei derselben Kammer. Der Beginn der Torschließung darf nicht vor dem Ende der Einfahrt des letzten Schiffs bzw. bei einer Leerschleusung nicht vor ihrem Beginn liegen.

Schließlich müssen die Schiffe einer Schleusung folgende von der Kammer und der Fahrtrichtung abhängige Sicherheitszeiten A-D einhalten:

A) Eine minimale Zeitspanne zwischen dem Beginn der Schleusung und dem Ende der Einfahrt des ersten Schiffs.

B) Eine minimale Zeitspanne zwischen den Einfahrten zweier aufeinanderfolgender Schiffe.

C) Ein exaktes Zeitintervall zwischen dem Ende der Toröffnung und der Ausfahrt des ersten Schiffs.

D) Schließlich ein exaktes Zeitintervall zwischen den Ausfahrten zweier aufeinanderfolgender Schiffe.

Das Diagramm in Abbildung 1.3 zeigt den genauen Ablauf der Schleusungen bei einer Schleusenkammer. Vorgänge zwischen zwei Ereignissen werden durch rote Transitionen dargestellt. Bei Transitionen in schwarzer Farbe finden die verbundenen Ereignisse gleichzeitig statt. Leerlauf bezeichnet ein beliebig langes nichtnegatives Zeitintervall.

Nun definieren wir rekursiv, wann Schiffe spätestens einfahren müssen. Es ist leicht zu sehen, dass die Einfahrt eines Schiffs bei Einhaltung der obigen Regeln nicht später als seine späteste Einfahrt stattfinden kann.

Definition 1.3 (Späteste Einfahrt). Das Ende der spätesten Einfahrt des letzten Schiffs einer Schleusung wird durch den Beginn der Torschließung definiert. Die spätesten Einfahrten zweier aufeinanderfolgender Schiffe derselben Schleusung unterscheiden sich exakt um die Sicherheitszeit B.

Bemerkung 1.4. Die Passierzeit eines Schiffs würde sich nicht verändern, wenn es selbst und alle nachfolgenden Schiffe seiner Schleusung nach Definition 1.3 so spät wie möglich in die Kammer einfahren.

Zusätzliche Sicherheitszeiten:

Die beschriebenen Sicherheitszeiten verhindern nicht, dass Schiffe verschiedener Schleusungen kollidieren. Daher existieren zusätzliche Sicherheitszeiten, die zwischen den Ein- und Ausfahrten der einzelnen Schleusungen liegen müssen. Dies gilt sowohl für Schleusungen derselben als auch verschiedener Richtung. Um ihre Einhaltung zu gewährleisten, werden die Torschließungen einzelner Schleusungen, die Einfahrten einzelner Schiffe sowie ggf. die nachfolgenden Vorgänge erst etwas später veranlasst. Diese zusätzlichen Sicherheitszeiten werden wir jedoch nicht in das Modell des LSPs aufnehmen.

Bemerkung 1.5. Wenn keine zusätzlichen Sicherheitszeiten berücksichtigt werden müssen, dann werden die Einfahrten der Schiffe und die Torschließung so festgelegt, dass folgende Aussagen erfüllt sind:

• Ein Schiff hat keinen Aufenthalt im Warteraum, oder die Kammer befindet sich vor seiner Einfahrt nicht im Leerlauf.

• Der Beginn einer Leerschleusung bzw. das Ende der Einfahrt des letzten Schiffs einer nichtleeren Schleusung ist gleich dem Beginn der Torschließung, vor der also kein Leerlauf stattfindet. Die reale und die späteste Einfahrt des letzten Schiffs sind gleich.

Bemerkung 1.6. Die Schleusungsvorgänge zweier Kammern sind genau dann voneinander unabhängig, wenn keine zusätzlichen Sicherheitszeiten gegeben sind.

1.5, Positionierung von Schiffen in Schleusenkammern:

Bevor wir auf die Vorschriften für die Positionierung von Schiffen eingehen, beschreiben wir die räumlichen Eigenschaften von Schiffen und Schleusenkammern.

Eigenschaften von Schiffen und Schleusenkammern:

Wir nehmen an, dass die Länge, die Breite und der Tiefgang eines Schiffs seine maximalen Abmessungen bezeichnen, die Länge beispielsweise den Abstand von Bug und Heck. Somit können wir uns Schiffe quaderförmig und direkt unterhalb der Wasseroberfläche vorstellen. Auch die Verkehrsgruppe mit den ganzzahligen Werten 0 bis 6 beschreibt die Größe der Schiffe, wobei 0 für sog. Sportboote und 6 für sehr große Schiffe steht.

Schleusenkammern stellen wir uns ebenfalls quaderförmig vor. Die nutzbare Länge, Breite und Tiefe einer Kammer bestimmen den Raum, der bei Schleusungen mit Schiffen gefüllt werden kann. Natürlich kann ein Schiff nur in solchen Kammern geschleust werden, in die es zumindest ohne andere Schiffe hineinpasst. Das Ausfahrtstor befindet sich jeweils an der Kammerfront.

Vorschriften für die Positionierung:

Schiffe müssen in den Schleusenkammern an einer der beiden Seitenwände positioniert werden. Entsprechend definieren wir die Kammerseiten links und rechts.

Definition 1.7 (Bug- und Heckposition eines Schiffs). Die Bug- bzw. Heckposition eines Schiffs in einer Schleusenkammer sei der Abstand seines Bugs bzw. Hecks zur Kammerfront.

Definition 1.8 (Position eines Schiffs in einer Schleusenkammer). Die Position eines Schiffs in einer Schleusenkammer wird durch seine Kammerseite und seine Bugposition definiert.

Jedes Schiff muss auf der ihm zugewiesenen Kammerseite einfahren und darf seine Position nach der Einfahrt nicht mehr ändern. Zudem müssen zwischen Schiffen stets zwei konstante räumliche Mindestabstände eingehalten werden: Ein Seitenabstand parallel zu den Toren und ein Längsabstand parallel zu den Seitenwänden der Kammern. Dies gilt nicht nur für die Schiffspositionen während der Ausführung einer Schleusung. Denn Schiffe dürfen auch zu keinem Zeitpunkt der Einfahrt die Mindestabstände zu bereits eingefahrenen Schiffen verletzen. In diesem Fall sind sie auch bei der Ausfahrt gewährleistet, da die Schiffe in der Reihenfolge ihrer Einfahrt auch wieder ausfahren.