Sie sind hier
E-Book

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

AutorMartin Luy
VerlagDiplomica Verlag GmbH
Erscheinungsjahr2011
Seitenanzahl161 Seiten
ISBN9783842811881
FormatPDF/ePUB
Kopierschutzkein Kopierschutz/DRM
GerätePC/MAC/eReader/Tablet
Preis34,99 EUR
Mit zunehmendem Verkehrsaufkommen auf internationalen Wasserwegen ist eine rechnergesteuerte Verkehrsoptimierung an Schiffsschleusen unausweichlich. Das wichtigste Kriterium dabei ist, dass ankommende Schiffe möglichst zügig geschleust werden. Diese Studie präsentiert algorithmische Lösungsverfahren für die Planung der Schleusungsvorgänge auf dem Nord-Ostsee-Kanal (NOK). Auch bei vielen anderen Schleusen ist eine Anwendung unter einigen Voraussetzungen ohne weiteres möglich. Zudem werden interessante Verwandtschaften zum Truck Scheduling und Machine Scheduling, insbesondere im Güterverkehr, bei Container-Terminals und Autofähren aufgezeigt.

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.

Kaufen Sie hier:

Horizontale Tabs

Leseprobe
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.
Blick ins Buch
Inhaltsverzeichnis
Inhaltsverzeichnis3
Kapitel 0 Einleitung7
Kapitel 1 Schleusungen am NOK11
1.1 Grundlegende Funktionsweise von Schleusen11
1.2 Vereinfachende Modellannahmen12
1.3 Schiffspassagen13
1.4 Zeitlicher Ablauf von Schleusungen15
1.5 Positionierung von Schiffen in Schleusenkammern19
1.6 Grafische Darstellung von Lösungen20
1.7 Bewertung von Lösungen22
Kapitel 2 Das Lock-Scheduling-Problem (LSP)25
2.1 Formales Modell25
2.1.1 Die gegebenen Daten26
2.1.2 Die Daten einer Lösung27
2.1.3 Weitere wichtige Daten28
2.1.4 Zulässigkeit29
2.1.5 Die Kostenfunktion34
2.2 Anwendungen des LSPs35
2.3 Komplexitätsanalyse37
Kapitel 3 Einordnung in die Literatur41
3.1 Bisherige Untersuchungen des Problems41
3.2 Management der Schleusungen auf anderen Wasserwegen43
3.3 Die Verwandtschaft mit dem Truck-Scheduling-Problem46
Kapitel 4 Algorithmische Lösungsverfahren49
4.1 Berechnung der Schleusungen einer Lösung51
4.1.1 Entscheidung für spät ankommende Schiffe55
4.1.2 Positionierung der Schiffe58
4.1.3 Gesamtlaufzeit für die Berechnung der Schleusungen64
4.1.4 Verhinderung von Kollisionen65
4.2 Generierung initialer Lösungen66
4.3 Lokale Suche70
4.3.1 Nachbarschaften70
4.3.2 Hill-Climbing81
4.4 Weitere Optimierungsverfahren84
4.4.1 Postoptimierung84
4.4.2 Verschlechterungsschritte87
4.5 Gesamtablauf89
Kapitel 5 Qualität der berechneten Lösungen91
5.1 Untere Kostenschranken92
5.1.1 Einfahrt der Schiffe in der Ankunftsreihenfolge93
5.1.2 Einfahrt der Schiffe in beliebiger Reihenfolge97
5.1.3 Kombination mehrerer unterer Schranken101
5.1.4 Anwendung auf einige Probleminstanzen102
5.2 Untere Schranken an den Approximationsfaktor105
Kapitel 6 Empirische Analyse107
6.1 Vorgehen bei der Durchführung von Testläufen107
6.1.1 Simulierung der gegebenen Daten107
6.1.2 Verschiedene Berechnungsweisen108
6.1.3 Zielvariablen110
6.1.4 Weitere Variablen110
6.2 Ergebnisse mit Kanal-Programm111
6.2.1 Einschränkung der Parameter111
6.2.2 Explorative Analyse113
6.2.3 Auswahl der besten Berechnungsweisen125
6.2.4 Statistische lineare Modelle126
6.3 Ergebnisse ohne Kanal-Programm127
6.3.1 Einschränkung der Parameter127
6.3.2 Explorative Analyse127
6.3.3 Auswahl der besten Berechnungsweisen134
6.3.4 Statistische lineare Modelle135
Schlusswort141
Anhang143
Liste der Algorithmen147
Abbildungsverzeichnis149
Literaturverzeichnis153

Weitere E-Books zum Thema: Statistik - Algorhitmen

Deutscher SCOR-Preis für Aktuarwissenschaften 2009

E-Book Deutscher SCOR-Preis für Aktuarwissenschaften 2009
Zusammenfassungen eingereichter Arbeiten - Schriftenreihe der SCOR DEUTSCHLAND 9 Format: PDF

Der SCOR-Preis für Aktuarwissenschaften wurde 2009 zum 12. Mal verliehen. Die in Kooperation mit der Universität Ulm gestiftete Auszeichnung hat sich im deutschsprachigen Raum zum bedeutendsten Preis…

Deutscher SCOR-Preis für Aktuarwissenschaften 2011

E-Book Deutscher SCOR-Preis für Aktuarwissenschaften 2011
Zusammenfassungen eingereichter Arbeiten - Schriftenreihe der SCOR DEUTSCHLAND 12 Format: PDF

Den SCOR-Preis für Aktuarwissenschaften verleiht die SCOR Rückversicherungs-Gruppe in Zusammenarbeit mit der Universität Ulm seit 1998 jährlich an junge Wissenschaftler, die sich im Rahmen ihrer…

Kreditrisikomessung

E-Book Kreditrisikomessung
Statistische Grundlagen, Methoden und Modellierung Format: PDF

Jeder Kredit birgt für den Kreditgeber ein Risiko, da unsicher ist, ob Kreditnehmer ihren Zahlungsverpflichtungen nachkommen. Kreditrisiken werden mit Hilfe statistischer Methoden und mathematischer…

Statistik für Ökonomen

E-Book Statistik für Ökonomen
Datenanalyse mit R und SPSS Format: PDF

Die Autoren erläutern in einer anschaulichen, anwendungsorientierten und kompakten Darstellung alle elementaren statistischen Verfahren, die in der Ökonomie angewendet werden - ergänzt durch…

Weitere Zeitschriften

Ärzte Zeitung

Ärzte Zeitung

Zielgruppe:  Niedergelassene Allgemeinmediziner, Praktiker und Internisten. Charakteristik:  Die Ärzte Zeitung liefert 3 x pro Woche bundesweit an niedergelassene Mediziner ...

AUTOCAD & Inventor Magazin

AUTOCAD & Inventor Magazin

FÜHREND - Das AUTOCAD & Inventor Magazin berichtet seinen Lesern seit 30 Jahren ausführlich über die Lösungsvielfalt der SoftwareLösungen des Herstellers Autodesk. Die Produkte gehören zu ...

Card Forum International

Card Forum International

Card Forum International, Magazine for Card Technologies and Applications, is a leading source for information in the field of card-based payment systems, related technologies, and required reading ...

Card-Forum

Card-Forum

Card-Forum ist das marktführende Magazin im Themenbereich der kartengestützten Systeme für Zahlung und Identifikation, Telekommunikation und Kundenbindung sowie der damit verwandten und ...

Courier

Courier

The Bayer CropScience Magazine for Modern AgriculturePflanzenschutzmagazin für den Landwirt, landwirtschaftlichen Berater, Händler und generell am Thema Interessierten, mit umfassender ...

Die Großhandelskaufleute

Die Großhandelskaufleute

Prüfungs- und Praxiswissen für Großhandelskaufleute Mehr Erfolg in der Ausbildung, sicher in alle Prüfungen gehen, im Beruf jeden Tag überzeugen: „Die Großhandelskaufleute“ ist die ...

DSD Der Sicherheitsdienst

DSD Der Sicherheitsdienst

Der "DSD – Der Sicherheitsdienst" ist das Magazin der Sicherheitswirtschaft. Es erscheint viermal jährlich und mit einer Auflage von 11.000 Exemplaren. Der DSD informiert über aktuelle Themen ...