Martin Luy
Algorithmen zum Scheduling von Schleusungsvorgängen am Beispiel des Nord-Ostsee-
Kanals
ISBN: 978-3-8428-1014-3
Herstellung: Diplomica® Verlag GmbH, Hamburg, 2011
Zugl. Technische Universität Berlin, Berlin, Deutschland, Diplomarbeit, 2010
Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte,
insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von
Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der
Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen,
bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung
dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen
der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik
Deutschland in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich
vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des
Urheberrechtes.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in
diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,
dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei
zu betrachten wären und daher von jedermann benutzt werden dürften.
Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können
Fehler nicht vollständig ausgeschlossen werden und der Verlag, die Autoren oder
Übersetzer übernehmen keine juristische Verantwortung oder irgendeine Haftung für evtl.
verbliebene fehlerhafte Angaben und deren Folgen.
© Diplomica Verlag GmbH
http://www.diplomica.de, Hamburg 2011
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
i
ii
I
NHALTSVERZEICHNIS
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
I
NHALTSVERZEICHNIS
iii
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
iv
I
NHALTSVERZEICHNIS
Kapitel 0
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 aus [
3
] zufolge
beträgt die durch die Gezeiten verursachte Amplitude der Meeresspiegelhöhe, ge-
nannt 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 ei-
ner Länge von 125 bzw. 310m existieren. Im langjährigen Mittel passieren täglich
etwa 100 Schiffe
1
den
NOK
, der damit laut [
39
] ,,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.
2
Die vierteljährlichen Informationen auf [
39
], der offiziellen Webseite des
NOK
s, zu dessen wirtschaftlicher Situation berichten von einem kontinuierlichen
Trend zu immer größeren Schiffen. Die Anzahl der befahrenden Schiffe sei im ver-
gangenen Jahrzehnt nur leicht gestiegen und im Jahr 2009 aufgrund der internatio-
nalen 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 Schifffahrtsverwal-
tung 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 Mi-
1
ohne Sport- und Kleinfahrzeuge
2
Die Informationen über den
NOK
stammen aus [
24
,
38
,
39
].
1
2
K
APITEL
0
. E
INLEITUNG
Abbildung 0.1: Die Schleuse am westlichen Kanalende in Brunsbüttel aus der Vo-
gelperspektive. Quelle: [
37
]
nuten und haben nur begrenzte räumliche Kapazitäten. Bevor allerdings Schleu-
senkammern 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, Fahrtrich-
tungen und Ankunftszeiten bei der Schleuse gegeben sind, soll ein nachfrage-
orientierter 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 Ver-
kehrsaufkommen wird es immer schwieriger, gute Lösungen mit geringen Warte-
zeiten zu finden. Ziel dieser Diplomarbeit ist deshalb die Entwicklung, Implemen-
tierung 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
K
APITEL
0
. E
INLEITUNG
3
der beiden Schleusen werden wegen ihrer Interaktionen kollektiv behandelt. Zuerst
werden für die Schiffe, die sich zu einem initialen Zeitpunkt bereits im Kanal be-
finden, 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 Ka-
nal verlassen wollen, ins Meer geschleust. In der Gegenrichtung kommen jeweils
neue Schiffe durch die Schleuse in den Kanal. Die Schleusungen bis zu einem be-
stimmten 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 Schiffs-
daten 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 Schleu-
sungsvorgänge am
NOK
detailliert beschrieben, anhand derer das Modell des
LSP
s
entwickelt wurde. Die formale Problemdefinition, weitere Anwendungsmöglich-
keiten 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 Op-
timierungsproblem 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 Berech-
nung von Lösungen des
LSP
s. In Kapitel
5
werden mit Hilfe von unteren Kosten-
schranken die Qualitätsunterschiede zwischen optimalen und erzeugten Lösungen
analysiert. Anhand von Daten des
NOK
s wird schließlich in Kapitel
6
die Qualität
der Lösungen empirisch untersucht.
4
K
APITEL
0
. E
INLEITUNG
Kapitel 1
Schleusungen am
NOK
Im Rahmen der Studie, zu der diese Diplomarbeit beiträgt, gehen wir in diesem
Kapitel auf die Vorgaben für die Planung der Schleusungsvorgänge auf dem Nord-
Ostsee-Kanal (
NOK
) ein. An diesen Vorgaben wird sich das in der Einleitung be-
reits erwähnte Lock-Scheduling-Problem (
LSP
)
orientieren.
Die Schleusen befinden sich im Falle des
NOK
s an seinen beiden Mündungen.
Die Anzahl dieser Standorte ist unerheblich, da wir das Optimierungsproblem je-
weils separat behandeln. Zudem ist die Anwendbarkeit nicht notwendigerweise auf
Flussmündungen beschränkt, sondern prinzipiell z.B. auch bei Schleusen an Stau-
dämmen denkbar. Voraussetzung für jeden Standort ist, dass der Flusslauf von einer
Schleuse unterbrochen wird, deren parallel liegende Schleusenkammern die bei-
den Seiten verbinden. Das Beispiel des
NOK
s veranlasst uns, die Bezeichnungen
Kanal-
und Meerseite zu verwenden.
1.1
Grundlegende Funktionsweise von Schleusen
Damit ein Schiff eine Schleuse passieren kann, muss es in einer ihrer Kammern ge-
schleust
werden. Jede Kammer führt abwechselnd Schleusungen Richtung Kanal
und Richtung Meer durch, in denen jeweils mehrere Schiffe der entsprechenden
Fahrtrichtung
transportiert werden können. Leerschleusungen bezeichnen Schleu-
sungen, die keine Schiffe enthalten. Auf beiden Seiten einer Schleuse befindet sich
ein Warteraum, in dem Schiffe auf ihre Einfahrt in eine Schleusenkammer warten
und andere Schiffe passieren lassen können. Für jeden Warteraum ist eine Warte-
linie
definiert, die Schiffe vor ihrer Einfahrt nicht überqueren dürfen.
Die Kammern haben auf Kanal- und auf Meerseite je ein Tor, welches das Was-
ser innerhalb und außerhalb der Kammer trennt, sodass verschiedene Wasserstände
möglich sind. Bei Schleusungen Richtung Meer ist das Einfahrtstor auf Kanalseite
und das Ausfahrtstor auf Meerseite, bei Schleusungen Richtung Kanal umgekehrt.
5
6
K
APITEL
1
. S
CHLEUSUNGEN AM
NOK
Zu Beginn einer Schleusung ist das Einfahrtstor geöffnet und das Ausfahrts-
tor geschlossen. Wir sagen in diesem Fall, dass sich die Schleusenkammer auf der
Seite des Einfahrtstores befindet, da diese beiden Wasserstände gleich sind. Das
Einfahrtstor kann schließen, sobald die zugeordneten Schiffe nacheinander einge-
fahren sind. Nachdem der Wasserstand der anderen Seite angepasst wurde, befin-
det sich die Kammer auf der Seite des Ausfahrtstors, das sodann geöffnet wird.
Schließlich fahren die Schiffe in der gleichen Reihenfolge wie bei der Einfahrt
wieder aus. Danach steht die Kammer für die Einfahrt von entgegenkommenden
Schiffen bereit. Denn die nächste Schleusung bei dieser Kammer wird in entge-
gengesetzter Richtung stattfinden.
Folgende aufeinanderfolgende Vorgänge, die zusammen als Ausführung einer
Schleusung bezeichnet werden, betreffen alle enthaltenen Schiffe:
1. Das Schließen des Einfahrtstores, genannt Torschließung,
2. das Anpassen des Wasserstandes
3. und das Öffnen des Ausfahrtstores, die Toröffnung.
Die Füllzeit einer Schleusung sei die Zeit zum Anpassen des Wasserstandes. Die
Dauer einer Toröffnung oder Torschließung nennen wir Torzeit. Die Summe der
Zeitdauern aller drei Vorgänge ergibt die Ausführungszeit.
1.2
Vereinfachende Modellannahmen
Damit berechnete Lösungen des
LSP
s als ,,Fahrplan" für die Schiffe einer gege-
benen Probleminstanz dienen können, muss die Realität ausreichend genau model-
liert werden. Einige auftretende Effekte, auf die wir im Folgenden kurz eingehen,
würden diese Arbeit zu sehr auszuweiten, sodass wir sie nicht weiter berücksichti-
gen. Es bleibt zu überprüfen, inwieweit das Modell des
LSP
s trotz der getroffenen
Vereinfachungen für die Simulation der Schleusungsvorgänge auf dem
NOK
ver-
wendet werden kann.
Gezeiten
Die Gezeiten haben starken Einfluss auf die Füllzeit. In Brunsbüttel, wo die
Meeresspiegelschwankungen sehr viel stärker als in Kiel sind, liegt der Wasser-
stand des
NOK
s laut [
38
] etwa in der Mitte zwischen dem mittlerem Hoch- und
Niedrigwasser
.
1
Das Anpassen des Wasserstandes in einer Kammer sollte bei
1
Bei Schleusungen derselben Richtung muss deshalb manchmal Wasser in die Kammer hinein-
und manchmal abgelassen werden.
1.3
. S
CHIFFSPASSAGEN
7
Schleusungen Richtung Kanal möglichst nicht dann begonnen und bei Schleu-
sungen Richtung Meer nicht dann beendet werden, wenn gerade Ebbe oder Flut
ist. Erschwerend kommt hinzu, dass sich die Gezeitenkurve jeden Tag etwas ver-
schiebt; ihre Periodenlänge beträgt laut [
13
] ca. 12h 25min. Zudem zeigt die
Wasserstandsvorhersage von [
3
], dass die einzelnen Hoch- und Niedrigwasser oft
unterschiedlich ausfallen. Der Einfachheit halber lassen wir die Meeresspiegel-
schwankungen außer Acht und nehmen an, dass die Füllzeit nur von den Eigen-
schaften der jeweiligen Schleusenkammer abhängig ist.
Mitteltore
Die großen Schleusenkammern in Kiel und in Brünsbüttel besitzen jeweils ein drit-
tes Tor, das zwischen den beiden anderen liegt und somit schnellere Schleusungen
ermöglicht. Diese sog. Mitteltore werden wir nicht berücksichtigen.
Kammer-Paare
Die Kammern sind an beiden Standorten paarweise angeordnet, wobei ein Paar
aus zwei identischen Kammern besteht. Für ein Kammer-Paar kann ein gemeinsa-
mer Wasserkreislauf verwendet werden, was z.B. Vorteile beim Energieverbrauch
haben könnte. Solche Interaktionen zwischen den Kammern machen das Problem
jedoch erheblich komplizierter und sind für die aktuelle Studie nicht relevant.
1.3
Schiffspassagen
Die Fahrt eines Schiffs durch eine Schleuse lässt sich in mehrere Zeitabschnitte
gliedern:
1. Die Anfahrt,
2. den Aufenthalt im Warteraum,
3. die Einfahrt in eine Schleusenkammer,
4. den Aufenthalt in der Kammer
5. und die Weiterfahrt.
Die Geschwindigkeiten während der Anfahrt, der Einfahrt und der Weiterfahrt sind
vorgeschrieben. Der Aufenthalt in der Schleusenkammer teilt sich wiederum auf in
1. das Warten auf die Ausführung, während weitere Schiffe einfahren können,
8
K
APITEL
1
. S
CHLEUSUNGEN AM
NOK
2. die Ausführung der Schleusung, wie schon in Kapitel
1.1
beschrieben,
3. und das Warten auf die Ausfahrt, während andere Schiffe derselben Schleu-
sung ausfahren.
Die fünf zuerst genannten Zeitabschnitte werden durch vier aufeinanderfolgende
Zeitpunkte getrennt, die zusammen eine Schiffspassage definieren:
1. Die Ankunft
2
bei der Wartelinie des entsprechenden Warteraums,
2. der Beginn der Einfahrt in eine Schleusenkammer, dem Zeitpunkt des Über-
querens der Wartelinie,
3. das Ende der Einfahrt, zu dem das Schiff in der Kammer ankommt,
4. und seine Ausfahrt, definiert durch das Passieren des Ausfahrtstores.
Die einzelnen Zeitpunkte beziehen sich darauf, wann das Heck des Schiffs den
jeweiligen Ort, also die Wartelinie oder eines der Schleusentore, erreicht bzw. ver-
lässt. Abbildung
1.1
zeigt eine Schiffspassage als Ablaufdiagramm und Abbildung
1.2
als Positionsdiagramm.
3
In beiden Diagrammen stehen blaue Transitionen für
Fahrten und schwarze im Wesentlichen für Aufenthalte des betroffenen Schiffs,
wobei die Fahrt innerhalb der Schleusenkammer, also zwischen Ein- und Aus-
fahrtstor, nicht modelliert wird.
Abbildung 1.1: Ablaufdiagramm für eine Schiffspassage.
Nur die Ankunft beim Warteraum und der Beginn der Einfahrt können gleich
sein, sodass das Schiff keinen Aufenthalt im Warteraum hat. Die Einfahrtzeit hängt
nicht nur vom Standort und der Fahrtrichtung, sondern auch von der Entfernung
der Schleusenkammer von der jeweiligen Wartelinie ab. Auf letztere Abhängigkeit
gehen wir nicht näher ein; sie wird jedoch bei den Testläufen in Kapitel
6
berück-
sichtigt.
2
Hier wird nicht beachtet, dass das Schiff durch andere Schiffe daran gehindert werden könnte,
bis zur Wartelinie vorzufahren.
3
Eine Beschreibung von Ablauf- und Positionsdiagrammen findet sich in Anhang
B
.
1.4
. Z
EITLICHER
A
BLAUF VON
S
CHLEUSUNGEN
9
Abbildung 1.2: Positionsdiagramm für eine Schiffspassage.
Definition 1.1 (Passierzeit). Die (reale) Passierzeit eines Schiffs in einer Lösung
sei die Zeitspanne zwischen der Ankunft beim Warteraum und der Ausfahrt aus der
Schleusenkammer.
1.4
Zeitlicher Ablauf von Schleusungen
In Kapitel
1.1
wurde der grobe zeitliche Ablauf von Schleusungen bereits darge-
stellt. Nun wollen wir ihn vertiefen.
Einfahrtsreihenfolge der Schiffe
Für jede Schleusung wird festgelegt, in welcher Reihenfolge die enthaltenen Schif-
fe 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 Se-
quenzierungsregel, 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 Schleu-
senkammer abhängig ist. Gleiches gilt für die Torzeit und damit auch für die Aus-
führungszeit. Zudem ist für jede Schleusenkammer ein initialer Zustand gegeben,
der zwei Daten enthält: eine initiale Richtung, in der die erste Schleusung stattfin-
den wird, und eine initiale Startzeit, die ihren Beginn festlegt. Falls eine Schleusung
10
K
APITEL
1
. S
CHLEUSUNGEN AM
NOK
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 Schleu-
sung 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 aufeinanderfol-
gender Schiffe,
C) ein exaktes Zeitintervall zwischen dem Ende der Toröffnung und der Aus-
fahrt des ersten Schiffs,
D) und schließlich ein exaktes Zeitintervall zwischen den Ausfahrten zweier
aufeinanderfolgender Schiffe.
Das Diagramm in Abbildung
1.3
zeigt den genauen Ablauf der Schleusun-
gen bei einer Schleusenkammer.
4
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 zwi-
schen den Ein- und Ausfahrten der einzelnen Schleusungen liegen müssen. Dies
4
Eine Beschreibung von Ablaufdiagrammen findet sich in Anhang
B
.
1.4
. Z
EITLICHER
A
BLAUF VON
S
CHLEUSUNGEN
11
Abbildung 1.3: Ablaufdiagramm für Schleusungen.
12
K
APITEL
1
. S
CHLEUSUNGEN AM
NOK
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
LSP
s 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 festge-
legt, 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 Ein-
fahrt 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, be-
schreiben 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 Schleusun-
gen 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.
1.5
. P
OSITIONIERUNG VON
S
CHIFFEN IN
S
CHLEUSENKAMMERN
13
Vorschriften für die Positionierung
Schiffe müssen in den Schleusenkammern an einer der beiden Seitenwände posi-
tioniert
werden. Entsprechend definieren wir die Kammerseiten links und rechts.
5
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 Sei-
tenwä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 Rei-
henfolge ihrer Einfahrt auch wieder ausfahren.
Abbildung
1.4
zeigt eine mögliche Positionierung von Schiffen in einer Schleu-
senkammer von links, aus der Vogelperspektive und von rechts betrachtet. Die
Kammerfront ist oben. Die hellen Rechtecke stellen die Schiffe dar, die dunklen
Flächen links und oberhalb der Schiffe stehen für die Mindestabstände. Wie man
sieht, werden die Schiffe jeweils möglichst weit vorne, d.h. nahe an der Kammer-
front, positioniert.
Abbildung 1.4: Beispiel für die Positionierung von Schiffen in einer Kammer.
5
Die Kammerseiten sind nicht mit der Kanal- und der Meerseite von Schleusen zu verwechseln.
14
K
APITEL
1
. S
CHLEUSUNGEN AM
NOK
1.6
Grafische Darstellung von Lösungen
Übersicht
In Abbildung
1.5
wird ein Schleusungs-Zeitplan, den eine Lösung des
LSP
s sym-
bolisiert, grafisch veranschaulicht. Die vertikale Achse zeigt den Zeitverlauf. Die
kleinen hellblauen Balken mit farbigen Unterbrechungen stehen für die Schiffspas-
sagen der gegebenen Schiffe.
Abbildung 1.5: Grafische Darstellung einer Lösung.
Die Darstellungen für die einzelnen Schleusenkammern sind durch dicke
schwarze Linien getrennt. In der Mitte zweier solcher Linien befindet sich jeweils
ein durchgehender Balken, der die direkt bei der Kammer stattfindenden Vorgänge
zeigt. Hellgraue Abschnitte stehen für Schleusungen in Richtung Meer, dunkel-
graue für Schleusungen in Richtung Kanal. Bei ersteren werden die Passagen der
enthaltenen Schiffe auf der linken Seite, bei letzteren auf der rechten Seite ange-
zeigt. Die blauen Rechtecke stellen die Ausführungen der Schleusungen dar, wobei
die beiden waagrechten weißen Linien das Ende der Torschließung und den Beginn
der Toröffnung verdeutlichen.
Einzelne Schleusungen
Abbildung
1.6
zeigt nun Schleusungen im Detail. Jedes Schiff besitzt eine eindeuti-
ge Identifikationsnummer, die hier angezeigt wird. Die Schiffe sind von außen nach
innen in der Reihenfolge angeordnet wie sie in die Kammer ein- und ausfahren.
Der gelbe Balken eines Schiffs, der den hellblauen Balken der Schiffspassage
überdeckt, steht für die Einfahrt. Das Ende der Einfahrt und die Ausfahrt sind als
1.7
. B
EWERTUNG VON
L
ÖSUNGEN
15
Abbildung 1.6: Grafische Darstellung von Schleusungen.
waagrechte gelbe bzw. pinke Linien gezeichnet, die bis zum Schleusungs-Balken
reichen. Die späteste Einfahrt ist jeweils in roter Farbe zu sehen. Die grünen Berei-
che auf den Schleusungs-Balken stellen die Sicherheitszeiten A-D dar, die vor den
Enden der Einfahrten und vor den Ausfahrten der einzelnen Schiffe eingehalten
werden müssen.
1.7
Bewertung von Lösungen
Es gibt mehrere Kriterien, nach denen Lösungen bewertet werden sollen. In Kapitel
2.1.5
werden wir festlegen, wie wir sie in einer Kostenfunktion kombinieren.
Extrazeiten
Definition 1.9 (Minimale Passierzeit). Nehmen wir an, dass ein Schiff sofort in
die zugewiesene Schleusenkammer einfahren kann und keine weiteren Schiffe in
seiner Schleusung enthalten sind. Die
minimale Passierzeit eines Schiffs sei das
Minimum der so entstehenden Passierzeiten über alle ausreichend großen Schleu-
senkammern.
Definition 1.10 (Extrazeit). Die Differenz der realen und der minimalen Passier-
zeit definiert die
Extrazeit eines Schiffs in einer Lösung.
Die Extrazeit steht sozusagen für die Zeit, die ein Schiff länger als unbedingt
nötig braucht, um die Schleuse zu passieren. Die Summe der Extrazeiten wollen
wir minimieren. Aber auch wenn diese Summe klein ist, müssen einzelne Schif-
fe möglicherweise übermäßig lange warten. Um dies zu verhindern, könnte man
zusätzlich die Standardabweichung der Extrazeiten minimieren.
16
K
APITEL
1
. S
CHLEUSUNGEN AM
NOK
Aufenthaltszeiten in den kanalseitigen Warteräumen
Unsere Lösungen lassen zu, dass sich sehr viele Schiffe gleichzeitig in einem
Warteraum aufhalten. Die beiden Warteräume innerhalb des Kanals haben jedoch
begrenzte Kapazität, sodass Schiffe dort möglichst kurz warten sollten. Wir wol-
len also auch die Summe der Aufenthaltszeiten im Warteraum aller Schiffe, die
Richtung Meer fahren, minimieren. Möglicherweise wäre es hier sinnvoll, nur die
Aufenthaltszeiten derjenigen Schiffe zu berücksichtigen, die vermutlich nicht mehr
in den Warteraum passen.
Abstände langer Schiffe zur Kammerfront
Aus betriebstechnischen Gründen sollen Schiffe ab einer Länge von 140 Metern
sehr nahe an der Kammerfront positioniert werden. Die Summe der Bugpositionen
aller langen Schiffe soll möglichst klein sein.
Große Schiffe in kleinen Schleusenkammern
Die kleinen Schleusenkammern in Kiel und Brunsbüttel sollen möglichst selten
große Schiffe der Verkehrsgruppen 5 und 6 aufnehmen.
Kapitel 2
Das Lock-Scheduling-Problem
(
LSP
)
In diesem Kapitel betrachten wir das abstrakte Modell des Lock-Scheduling-
Problems (
LSP
)
, das sich an den in Kapitel
1
beschriebenen Vorgaben für Schleu-
sungen am
NOK
orientiert. Nach der formalen Problemdefinition zeigen wir
verschiedene Anwendungsmöglichkeiten, die nicht nur bei Schleusen auftreten.
Schließlich analysieren wir die Komplexität des Problems, um herauszufinden,
welche Herangehensweise für algorithmische Lösungsverfahren angebracht ist.
2.1
Formales Modell
Wir beschreiben nun die gegebenen Daten einer
LSP
-Instanz, definieren die Daten
und die Zulässigkeit von Lösungen des
LSP
s und geben eine Kostenfunktion an.
Für eine gegebene Probleminstanz suchen wir eine zulässige Lösung mit mini-
malen Kosten.
Alle Längenangaben und Zeitintervalle sind ganzzahlig und nicht negativ und
haben jeweils die gleiche Einheit. Zeitpunkte werden als Zeitraum seit einem fest-
gelegten Referenzzeitpunkt
1
angegeben. Konstant sind die beiden Fahrtrichtungen
T SEA
(Richtung Meer) und TCANAL (Richtung Kanal) sowie die beiden Kam-
merseiten LEFT und RIGHT . Für eine Richtung dir bezeichnet dir.oppDir die
Gegenrichtung. Entsprechend ist side.oppSide die der Kammerseite side gegen-
überliegende Seite.
1
Hier bietet sich das Minimum der frühesten Ankunft eines Schiffs beim Warteraum und der
frühesten initialen Startzeit einer Schleusenkammer an.
17
18
K
APITEL
2
. D
AS
L
OCK
-S
CHEDULING
-P
ROBLEM
2.1.1
Die gegebenen Daten
Beim
LSP
sind eine Menge Ships = {s
1
, . . . , s
n
} von Schiffen, eine Menge
Chambers
= {c
1
, . . . , c
m
} von Schleusenkammern und einige Parameter gegeben.
Die Daten eines Schiff s sind:
· Die Länge s.length,
· die Breite s.width,
· der Tiefgang s.depth,
· die Verkehrsgruppe s.category,
· die Fahrtrichtung s.dir
· und die Ankunft s.arrival beim Warteraum.
Eine Schleusenkammer c hat
· eine nutzbare Länge c.length,
· eine nutzbare Breite c.width,
· eine nutzbare Tiefe c.depth,
· eine Füllzeit c. f illingTime,
· eine Torzeit c.gateTime,
· einen initialen Status, bestehend aus
einer initialen Richtung c.initDir
und einer initialen Startzeit c.initStart,
· und für jede Richtung dir
eine Einfahrtzeit c.entranceTime
dir
und Sicherheitszeiten A-D:
c.sa f etyTimeA
dir
,
c.sa f etyTimeB
dir
,
c.sa f etyTimeC
dir
,
c.sa f etyTimeD
dir
.
Zudem muss für jede Schleusenkammer bestimmt werden, ob sie eine sog. kleine
Kammer ist. Schließlich sind folgende Parameter gegeben:
2.1
. F
ORMALES
M
ODELL
19
· Die räumlichen Mindestabstände zwischen Schiffen, der Längsabstand
minLengthDistance
und der Seitenabstand minWidthDistance,
· die minimale Länge longShipMinLength, ab der Schiffe als lang bezeichnet
werden,
· f c f sActive, die Angabe ob die in Kapitel
1.4
beschriebene
FCFS
-Regel an-
gewandt werden soll,
· und Koeffizienten für die Kostenfunktion:
2
costWeight
extraTimes
,
costWeight
waitingsInCanal
,
costWeight
bowPositions
und costWeight
tc
56SmallC
.
2.1.2
Die Daten einer Lösung
Eine Lösung beinhaltet für jede Schleusenkammer c eine Liste von Schleusungen
c
.lockages. Für jede Schleusung l müssen eine Richtung l.dir und folgende Zeit-
punkte festgelegt werden:
· Ihr Beginn l.start,
· der Beginn und das Ende der Torschließung l.closingStart und l.closingEnd,
· der Beginn und das Ende der Toröffnung l.openingStart und l.openingEnd
· und das Ende l.end.
Jede Schleusung l enthält eine nach der Einfahrt geordnete Liste von Schiffen
l
.ships. Jedes Schiff s benötigt Informationen über seine Position in der Schleu-
senkammer,
· die Kammerseite s.side
· und die Bugposition s.bowPosition,
sowie seine Schiffspassage,
· den Beginn und das Ende der Einfahrt s.entranceStart und s.entranceEnd
· und die Ausfahrt s.leaving.
Die Ankunft beim Warteraum war gegeben. Dafür sollten aber der Beginn und das
Ende der spätesten Einfahrt s.latestEntranceStart und s.latestEntranceEnd in die
Schiffspassage aufgenommen werden. Zudem soll für ein Schiff auch angegeben
werden, ob seine Schleusenkammer klein ist.
2
siehe Kapitel
2.1.5
20
K
APITEL
2
. D
AS
L
OCK
-S
CHEDULING
-P
ROBLEM
2.1.3
Weitere wichtige Daten
Die Ausführungszeit von Schleusungen bei einer Schleusenkammer c sei
c
.executionTime. Wir nehmen an, dass sie positiv ist. Nach Definition gilt
c
.executionTime = 2 · c.gateTime + c. f illingTime.
(2.1)
Für ein Schiff s bezeichne s.passageTime die Passierzeit, s.minPassageTime die
minimale Passierzeit und s.extraTime die Extrazeit. Es gelten die folgenden Be-
ziehungen:
s
.passageTime = s.leaving - s.arrival
(2.2)
s
.minPassageTime =
min
c
Chambers,
s passt in c
c
.entranceTime
s
.dir
+c.executionTime
+c.sa f etyTimeC
s
.dir
(2.3)
s
.extraTime = s.passageTime - s.minPassageTime
(2.4)
Für die Heckposition s.tailPosition eines Schiffs s gilt
s
.tailPosition = s.bowPosition + s.length.
(2.5)
Die beiden räumlichen Mindestabstände können wir vernachlässigen, wenn wir
den Längsabstand zur Länge und und den Seitenabstand zur Breite jedes Schiffs
addieren. Die virtuelle Länge und Breite eines Schiffs s seien also folgendermaßen
definiert:
s
.virtualLength := s.length + minLengthDistance
(2.6)
s
.virtualWidth := s.width + minWidthDistance
(2.7)
Da die Schiffe direkt an den Rändern der Schleusenkammern positioniert werden,
müssen wir auch deren Abmessungen modifizieren. Wir definieren also die virtu-
elle Länge
und Breite einer Schleusenkammer c analog:
c
.virtualLength := c.length + minLengthDistance
(2.8)
c
.virtualWidth := c.width + minWidthDistance
(2.9)
Wir stellen uns vor, dass wie in Abbildung
1.4
der Längsabstand am Bug und
der Seitenabstand auf der linken Seite der Schiffe hinzugefügt wird. Entsprechend
werden sie bei Schleusenkammern an der Kammerfront und an der linken Kam-
merseite angebracht. Dadurch bekommen wir den virtuellen Bug eines Schiffs und
die virtuelle Kammerfront einer Schleusenkammer.
2.1
. F
ORMALES
M
ODELL
21
Definition 2.1 (Virtuelle Bug- und Heckposition eines Schiffs). Die virtuelle Bug-
bzw.
Heckposition eines Schiffs in einer Schleusenkammer sei der Abstand seines
virtuellen Bugs bzw. seines Hecks zur virtuellen Kammerfront.
Die Bugposition ist gleich der virtuellen Bugposition. Für die virtuelle Heck-
position s.virtualTailPosition eines Schiffs s gilt
s
.virtualTailPosition = s.tailPosition + minLengthDistance.
(2.10)
2.1.4
Zulässigkeit
Eine Lösung des
LSP
s ist zulässig, wenn die Zulässigkeitsbedingungen
2.11
-
2.39
erfüllt und alle numerischen Variablen ganzzahlig und nichtnegativ sind.
Für die verwendeten Listen von Schiffen und Schleusungen verwenden wir
folgende Syntax: size(list) bezeichnet die Anzahl der Elemente einer Liste list.
list
[i] mit i N
0
, i < size(list) steht für das (i + 1)-te Element. last(list) sei das
letzte Element der Liste, also list[size(list) - 1].
Anzahl der Schleusungen und doppelte Leerschleusungen
Vor allem für den Beweis des Satzes
2.4
der Komplexitätsanalyse müssen wir for-
dern, dass die Laufzeit von Iterationen über die Schleusungen einer Lösung poly-
nomiell ist. Es gibt maximal n nichtleere Schleusungen; im Extremfall wird jedes
Schiff einzeln geschleust. Doch die Anzahl der Leerschleusungen ist unbeschränkt.
Verständlicherweise sind Leerschleusungen, die bei einer Kammer aufeinanderfol-
gen, unnötig. Sie verbrauchen Kapazitäten, haben aber keinen Nutzen. Unter der
Annahme, dass sog. doppelte Leerschleusungen nicht vorkommen und die letzte
betrachtete Schleusung jeder Kammer nicht leer ist, finden in einer Lösung höch-
stens 2n Schleusungen statt. Denn zwischen zwei aufeinanderfolgenden nichtlee-
ren Schleusungen sowie vor der ersten nichtleeren Schleusung einer Kammer kann
maximal eine Leerschleusung erfolgen.
Es würde genügen, diese lineare Schranke für die Anzahl der Schleusungen
zu setzen. Wir wollen aber doppelte Leerschleusungen sowie Leerschleusungen an
den Enden der Schleusungslisten ohnehin verbieten.
c
Chambers
size
(c.lockages) 2n
(2.11)
c Chambers i N, i < size(c.lockages) :
c
.lockages[i - 1].ships oder c.lockages[i].ships nicht leer
(2.12)
c Chambers :
c
.lockages nicht leer last(c.lockages).ships nicht leer
(2.13)
22
K
APITEL
2
. D
AS
L
OCK
-S
CHEDULING
-P
ROBLEM
Bedingungen für die Liste der Schleusungen einer Kammer
Der initiale Zustand einer Schleusenkammer c bestimmt die Richtung und den Be-
ginn ihrer ersten Schleusung:
Wenn c.lockages nicht leer ist:
c
.initDir = c.lockages[0].dir,
(2.14)
c
.initStart = c.lockages[0].start
(2.15)
Zwei Schleusungen, die bei derselben Schleusenkammer c aufeinanderfolgen,
haben verschiedene Richtungen und schließen direkt aneinander an:
i N, i < size(c.lockages) :
c
.lockages[i - 1].dir = c.lockages[i].dir,
(2.16)
c
.lockages[i - 1].end = c.lockages[i].start
(2.17)
Bedingungen für Schiffslisten
Die Schiffslisten der Schleusungen enthalten jeweils keine Duplikate:
c Chambers l c.lockages 0 i < j < size(l.ships) :
l
.ships[i] = l.ships[ j]
(2.18)
Und sie bilden eine Partition
3
der Menge aller Schiffe:
Ships
=
·
c
Chambers
·
l
c.lockages
l
.ships
(2.19)
Eine Schleusung l enthält nur Schiffe der entsprechenden Fahrtrichtung:
s l.ships : s.dir = l.dir
(2.20)
Reihenfolge der Schiffe bei
FCFS
Falls die
FCFS
-Regel angewandt wird, müssen für ihre Einhaltung zwei Bedingun-
gen erfüllt sein:
3
Eine duplikatfreie Liste kann man als Menge ansehen, wenn man die Sortierung der Elemente
nicht beachtet.
2.1
. F
ORMALES
M
ODELL
23
· Die Schiffsliste einer Schleusung l ist nach der Ankunft beim Warteraum
geordnet:
i N, i < size(l.ships) :
l
.ships[i - 1].arrival l.ships[i].arrival
(2.21)
· Das letzte Schiff einer nichtleeren Schleusung l kommt nicht später beim
Warteraum an als das erste Schiff einer nichtleeren Schleusung ~l, die bei
derselben Kammer c und in derselben Richtung später als l stattfindet:
l
= c.lockages[i], ~l = c.lockages[ j], 0 i < j < size(c.lockages),
l
.dir = ~l.dir, l.ships nicht leer, ~l.ships nicht leer
last (l.ships) .arrival ~l.ships[0].arrival (2.22)
Bedingungen für den zeitlichen Ablauf von Schleusungen
Sei l eine beliebige Schleusung, die bei einer Schleusenkammer c stattfindet. Die
Einfahrt eines Schiffs s in die Kammer beginnt nicht vor seiner Ankunft beim
Warteraum, und die Einfahrtzeit ist korrekt:
s
.arrival s.entranceStart,
(2.23)
s
.entranceStart + c.entranceTime
s
.dir
= s.entranceEnd
(2.24)
Die Füllzeit und die Torzeit sind exakt eingehalten:
l
.closingStart + c.gateTime = l.closingEnd
(2.25)
l
.closingEnd + c. f illTime = l.openingStart
(2.26)
l
.openingStart + c.gateTime = l.openingEnd
(2.27)
Die Sicherheitszeiten A-D sind eingehalten:
Wenn l.ships nicht leer ist:
l
.start + c.sa f etyTimeA
l
.dir
l.ships[0].entranceEnd
(2.28)
l
.openingEnd + c.sa f etyTimeC
l
.dir
= l.ships[0].leaving
(2.29)
i N, i < size(l.ships) :
l
.ships[i-1].entranceEnd
+ c.sa f etyTimeB
l
.dir
l.ships[i].entranceEnd
(2.30)
l
.ships[i-1].leaving
+ c.sa f etyTimeD
l
.dir
= l.ships[i].leaving
(2.31)
24
K
APITEL
2
. D
AS
L
OCK
-S
CHEDULING
-P
ROBLEM
Der Beginn der Torschließung und das Ende der Schleusung sind korrekt gesetzt:
l
.closingStart
l
.start,
wenn l.ships leer
last
(l.ships) .entranceEnd,
sonst
(2.32)
l
.end =
l
.openingEnd,
wenn l.ships leer
last
(l.ships) .leaving,
sonst
(2.33)
Bedingungen für die Positionierung von Schiffen
Schließlich müssen für jedes Schiff s Ships einige Bedingungen überprüft wer-
den, die seine Position in der Schleusenkammer betreffen. Sei c die Schleusen-
kammer, bei der die Schleusung des Schiffs stattfindet.
· Das Schiff passt alleine in die Kammer:
s
.virtualLength c.virtualLength
(2.34)
s
.virtualWidth c.virtualWidth
(2.35)
s
.depth c.depth
(2.36)
· Die Bedingungen
2.37
und
2.38
stellen sicher, dass die räumlichen Min-
destabstände sowohl während der Ausführung der Schleusung als auch zu je-
dem Zeitpunkt der Einfahrt von s eingehalten werden. Sei previousShips
side
die nach der Einfahrt sortierte Liste von Schiffen derselben Schleusung, die
vor s auf einer Kammerseite side eingefahren sind.
Falls auf der Seite von s schon ein Schiff eingefahren ist, überlappen
sich die beiden Schiffe nicht, und der Längsabstand ist eingehalten:
previousShips
s
.side
nicht leer
last
(previousShips
s
.side
) .virtualTailPosition
s.bowPosition (2.37)
Der Seitenabstand wird zu allen bereits eingefahrenen Schiffen, an
denen s vorbeifährt, eingehalten. Für jedes Schiff, das auf der gegen-
überliegenden Kammerseite positioniert wurde und dessen virtuelle
Heckposition größer als die Bugposition von s ist, muss überprüft wer-
den, ob es neben s in die Kammer passt:
~s previousShips
s
.side.oppSide
:
( ~
s
.virtualTailPosition > s.bowPosition
~s.virtualWidth + s.virtualWidth c.virtualWidth) (2.38)
Ende der Leseprobe aus 141 Seiten
- nach oben
Details
- Arbeit zitieren
- , 2010, Algorithmen zum Scheduling von Schleusungsvorgängen am Beispiel des Nord-Ostsee-Kanals, Hamburg, Bedey Media GmbH, https://www.diplom.de/document/228321
Ähnliche Arbeiten
Deutschlands größter Sharing Community
Jetzt Zusammenfassungen, Skripte und Klausuren kostenlos downloaden!
Uniturm.de
Ihre Vorteile als Autor
Geld verdienen Für jedes verkaufte Exemplar erhalten Sie Autorenhonorar - bis zu 40%.Kostenlose Buchveröffentlichung
Als eBook-Studie im Original und / oder auf Wunsch zusätzlich als hochwertiges Fachbuch in unserem renommierten Buchverlag.
Renommee als Fachbuchautor
Präsentieren Sie sich als Fachfrau oder Fachmann in Ihrem Fachgebiet und machen Sie sich bekannt.
Persönliche Betreuung
Unser Lektorat wird Sie persönlich betreuen und ist auch telefonisch unter 040-655992-14 erreichbar.
Weltweit im Buchhandel
Ihr Buch ist weltweit im Buchhandel und Online-Buchhandel wie z.B. amazon erhältlich.
Jetzt Autor werden!
Kommentare