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.

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. d 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.