E-Book, Deutsch, 161 Seiten
E-Book, Deutsch, 161 Seiten
ISBN: 978-3-8428-1619-0
Verlag: Diplomica Verlag GmbH
Format: EPUB
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)
Wie viele Probleme der kombinatorischen Optimierung ist das Scheduling von Schleusungsvorgängen NP-schwer, d.h. optimale Lösungen (Fahrpläne) können meist nicht in akzeptabler Rechenzeit gefunden werden. U.a. mit Hilfe von lokaler Suche werden jedoch Fahrpläne berechnet, die für die Anwendung beim NOK sehr zufriedenstellend sind, denn die Schiffe müssen im Durchschnitt nur wenige Minuten warten. Des weiteren wird mit multivariaten statistischen Verfahren und einer großen 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 Schleusungsvorgänge zu gruppieren, sodass die Schiffe einer Schleusung in die entsprechende Kammer passen. Festzulegen sind die Zeitpunkte der Schleusungsvorgänge sowie der Ein- und Ausfahrten der Schiffe.
Die Studie enthält auch eine ausführliche Literaturrecherche über bisherige Untersuchungen des Problems und das Schleusenmanagement bei anderen bekannten Wasserwegen. Die Komplexität des Problems an sich sowie die Laufzeiten der vorgestellten Algorithmen werden jeweils angegeben und bewiesen. Zusätzlich zu den statistischen Analysen werden Abschätzungen für die Qualitätsunterschiede von berechneten und optimalen Lösungen hergeleitet.Martin Luy, geboren 1985 in Augsburg, studierte Diplom-Mathematik mit Nebenfach Informatik an der Universität Augsburg und der TU Berlin. Dabei erwarb er sich vertiefte Fachkenntnisse in kombinatorischer Optimierung und statistischer Datenanalyse. Durch verschiedene Projekte, etwa beim Online-Buchhandel buch7.de, sammelte er zudem mehrjährige Erfahrung bei der Modellierung komplexer Sachverhalte und der Programmierung mit Java und RubyOnRails. Im vorliegenden Buch kombiniert der Autor diese Fachgebiete, indem er ein praxisnahes NP-vollständiges Problem mathematisch formuliert, Approximationsalgorithmen dazu vorstellt und diese u.a. mit statistischen Methoden auswertet.
Autoren/Hrsg.
Fachgebiete
- Technische Wissenschaften Bauingenieurwesen Verkehrsingenieurwesen, Verkehrsplanung
- Technische Wissenschaften Verkehrstechnik | Transportgewerbe Schiffbau, Seeverkehr
- Geowissenschaften Geographie | Raumplanung Regional- & Raumplanung Verkehrsplanung, Verkehrspolitik
- Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Algorithmen & Datenstrukturen
- Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Angewandte Mathematik, Mathematische Modelle
Weitere Infos & Material
1;Inhaltsverzeichnis;3
2;Kapitel 0 Einleitung;7
3;Kapitel 1 Schleusungen am NOK;11
3.1;1.1 Grundlegende Funktionsweise von Schleusen;11
3.2;1.2 Vereinfachende Modellannahmen;12
3.3;1.3 Schiffspassagen;13
3.4;1.4 Zeitlicher Ablauf von Schleusungen;15
3.5;1.5 Positionierung von Schiffen in Schleusenkammern;19
3.6;1.6 Grafische Darstellung von Lösungen;20
3.7;1.7 Bewertung von Lösungen;22
4;Kapitel 2 Das Lock-Scheduling-Problem (LSP);25
4.1;2.1 Formales Modell;25
4.1.1;2.1.1 Die gegebenen Daten;26
4.1.2;2.1.2 Die Daten einer Lösung;27
4.1.3;2.1.3 Weitere wichtige Daten;28
4.1.4;2.1.4 Zulässigkeit;29
4.1.5;2.1.5 Die Kostenfunktion;34
4.2;2.2 Anwendungen des LSPs;35
4.3;2.3 Komplexitätsanalyse;37
5;Kapitel 3 Einordnung in die Literatur;41
5.1;3.1 Bisherige Untersuchungen des Problems;41
5.2;3.2 Management der Schleusungen auf anderen Wasserwegen;43
5.3;3.3 Die Verwandtschaft mit dem Truck-Scheduling-Problem;46
6;Kapitel 4 Algorithmische Lösungsverfahren;49
6.1;4.1 Berechnung der Schleusungen einer Lösung;51
6.1.1;4.1.1 Entscheidung für spät ankommende Schiffe;55
6.1.2;4.1.2 Positionierung der Schiffe;58
6.1.3;4.1.3 Gesamtlaufzeit für die Berechnung der Schleusungen;64
6.1.4;4.1.4 Verhinderung von Kollisionen;65
6.2;4.2 Generierung initialer Lösungen;66
6.3;4.3 Lokale Suche;70
6.3.1;4.3.1 Nachbarschaften;70
6.3.2;4.3.2 Hill-Climbing;81
6.4;4.4 Weitere Optimierungsverfahren;84
6.4.1;4.4.1 Postoptimierung;84
6.4.2;4.4.2 Verschlechterungsschritte;87
6.5;4.5 Gesamtablauf;89
7;Kapitel 5 Qualität der berechneten Lösungen;91
7.1;5.1 Untere Kostenschranken;92
7.1.1;5.1.1 Einfahrt der Schiffe in der Ankunftsreihenfolge;93
7.1.2;5.1.2 Einfahrt der Schiffe in beliebiger Reihenfolge;97
7.1.3;5.1.3 Kombination mehrerer unterer Schranken;101
7.1.4;5.1.4 Anwendung auf einige Probleminstanzen;102
7.2;5.2 Untere Schranken an den Approximationsfaktor;105
8;Kapitel 6 Empirische Analyse;107
8.1;6.1 Vorgehen bei der Durchführung von Testläufen;107
8.1.1;6.1.1 Simulierung der gegebenen Daten;107
8.1.2;6.1.2 Verschiedene Berechnungsweisen;108
8.1.3;6.1.3 Zielvariablen;110
8.1.4;6.1.4 Weitere Variablen;110
8.2;6.2 Ergebnisse mit Kanal-Programm;111
8.2.1;6.2.1 Einschränkung der Parameter;111
8.2.2;6.2.2 Explorative Analyse;113
8.2.3;6.2.3 Auswahl der besten Berechnungsweisen;125
8.2.4;6.2.4 Statistische lineare Modelle;126
8.3;6.3 Ergebnisse ohne Kanal-Programm;127
8.3.1;6.3.1 Einschränkung der Parameter;127
8.3.2;6.3.2 Explorative Analyse;127
8.3.3;6.3.3 Auswahl der besten Berechnungsweisen;134
8.3.4;6.3.4 Statistische lineare Modelle;135
9;Schlusswort;141
10;Anhang;143
11;Liste der Algorithmen;147
12;Abbildungsverzeichnis;149
13;Literaturverzeichnis;153
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.
