Die Kaiplatz-Zuteilung verständlich erklärt

Mehrere Schiffe wollen im Hafen anlegen, aber der Platz am Ufer ist begrenzt. Wer darf wann wohin? Wer zuerst kommt, ist fair, wer wichtig ist, soll nicht lange warten. Diese Seite zeigt, was jede Regel kostet und wann die kluge Regel versagt.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Ein langer Parkstreifen

Stellen Sie sich einen langen Parkstreifen am Straßenrand vor. Autos, Transporter und Busse wollen dort parken, jedes für eine bestimmte Zeit. Jedes Fahrzeug braucht ein zusammenhängendes Stück des Streifens. Zwei Fahrzeuge dürfen nie zur selben Zeit am selben Stück stehen. Dazwischen bleibt etwas Abstand, damit niemand beim Rangieren anstößt.

Ein Teil des Streifens liegt unter einer niedrigen Unterführung. Dort passen nur flache Fahrzeuge hin. Hohe Fahrzeuge müssen auf den freien Teil. Außerdem sind manche Fahrzeuge eilig, etwa Lieferwagen mit festen Terminen. Wartet ein Lieferwagen, kostet das mehr, als wenn ein Wohnmobil im Urlaub wartet.

Die Frage lautet: Wer parkt wann und wo? Im Hafen heißt sie Kaiplatz-Zuteilung (englisch: Berth Allocation).

Dasselbe im Hafen

Im Hafen sind die Fahrzeuge Schiffe. Der Parkstreifen ist der Kai, das befestigte Ufer, an dem Schiffe festmachen und beladen werden. Wie tief ein Schiff im Wasser liegt, heißt Tiefgang. Ein Schiff mit großem Tiefgang braucht tiefes Wasser unter dem Rumpf. Darum hat der Kai einen tiefen und einen flachen Abschnitt. In den flachen Abschnitt passen nur Schiffe mit kleinem Tiefgang, wie unter die Unterführung nur flache Fahrzeuge. Der tiefe Abschnitt gleicht dem Teil ohne Unterführung: Dort dürfen alle liegen, auch die tiefen Schiffe.

Wie lange ein Schiff am Kai bleibt, heißt Liegezeit. Die Wartezeit ist die Zeit zwischen der Ankunft im Hafen und dem Anlegen. Sie soll klein sein, aber nicht für alle gleich klein.

Das Beispiel kennt drei Schiffsarten. Ein Mainliner ist ein großes Linienschiff, dessen Container schnell auf andere Schiffe oder Züge weiter müssen. Ein Feeder ist ein kleineres Zubringerschiff. Ein Tramp-Schiff fährt ohne festen Fahrplan und kann am ehesten warten. Eine Wartestunde eines Mainliners zählt so viel wie drei Wartestunden eines Tramp-Schiffs. Ein Feeder liegt dazwischen. Als Maß dient die gewichtete Wartezeit: Man zählt die Wartestunden aller Schiffe zusammen, und jede Stunde zählt mit dem Gewicht ihrer Schiffsart. Je kleiner die Summe, desto besser der Plan.

Die Seite erklärt das an einem vereinfachten Rechenbild (Fachwort: Modell). Darin sind Schiffe, Ankünfte und Liegezeiten erfunden und vorab bekannt. Die Aussagen in diesem Teil beschreiben dieses Rechenbild, nicht die Wirklichkeit.

Wer zuerst kommt oder wer wichtig ist

Nehmen wir einen Beispielhafen an einem vollen Tag. Sieben Schiffe treffen innerhalb von etwa einem Tag ein. Alle liegen so tief im Wasser, dass sie den tiefen Abschnitt brauchen. Der ist so kurz, dass immer nur ein Schiff hineinpasst. Es bildet sich eine Schlange.

Die erste Regel vergibt die Plätze nach Ankunft: Wer zuerst da ist, bekommt zuerst seinen Platz. Das wirkt fair. Die zweite Regel vergibt sie nach Wichtigkeit: Die Mainliner suchen sich zuerst ihren Platz aus, dann die Feeder, dann die Tramp-Schiffe. Ein einmal vergebener Platz wird nicht mehr verschoben.

So lange warten die Schiffe im Beispielhafen im Mittel, auf ganze Stunden gerundet:

• Mainliner: 41 Stunden bei Plätzen nach Ankunft, 8 Stunden bei Plätzen nach Wichtigkeit.
• Feeder: 9 Stunden bei Plätzen nach Ankunft, 54 Stunden bei Plätzen nach Wichtigkeit.
• Tramp: 30 Stunden bei Plätzen nach Ankunft, 75 Stunden bei Plätzen nach Wichtigkeit.

Die Mainliner gewinnen, weil sie in der Schlange nach vorn rücken. Der tiefe Abschnitt wird dadurch nicht größer, also rutschen die anderen nach hinten. Wichtigkeit verteilt die Wartezeit um. Beachten Sie: Der Beispielhafen hat drei Mainliner, drei Tramp-Schiffe und nur einen Feeder, dessen Wert ist ein Einzelfall.

Wenn Wichtigkeit nicht hilft

Nicht immer nützt die Regel nach Wichtigkeit. Nehmen wir einen ruhigen Beispielhafen mit fünf Schiffen, von denen keines ein Mainliner ist. Hier schneidet die Regel nach Wichtigkeit schlechter ab als die nach Ankunft.

Der Grund: Ein Feeder trifft spät ein, sucht sich aber als wichtiger zuerst seinen Platz aus. Er belegt den tiefen Abschnitt. Ein Tramp-Schiff, das fünf Stunden früher angekommen ist, muss deshalb hinter ihn. Hätte das Tramp-Schiff zuerst angelegt, hätte der Feeder nur drei Stunden gewartet. So wartet das Tramp-Schiff mehr als zehn Stunden. Ein einmal vergebener Platz wird nicht verschoben, und das Maß wird insgesamt schlechter.

Ein dritter Weg: tauschen und prüfen

Ein drittes Verfahren startet mit der besseren der beiden Reihenfolgen. Dann vertauscht es zwei Schiffe in der Reihenfolge der Platzvergabe und prüft, ob der Plan besser wird. Nur Verbesserungen bleiben. Das Ergebnis ist darum nie schlechter als der Start. Gemessen an der gewichteten Wartezeit schlägt es im belebten Beispielhafen beide Regeln, im ruhigen bleibt es bei der besseren. Die Zahlen dazu zeigt die Demo.

Ein Bild dazu, eine Deutung und keine Messung: Im Supermarkt stehen Sie hinter einem Kunden mit vollem Wagen. Sie lassen jemanden mit einem Joghurt gern vor. Das kostet den einen wenig und spart dem anderen viel. Ein Schiff mit sehr langer Liegezeit ist wie der volle Wagen, auch wenn es wichtig ist. Das Schiff mit kurzer Liegezeit ist wie der Joghurt. Lässt man es vor, warten alle dahinter weniger lang. Der Tausch findet solche Fälle.

Zum Vergleich gibt es eine Referenzrechnung (Fachwort: exakte Lösung). Sie schließt ganze Gruppen von Möglichkeiten aus, ohne jede einzeln auszuprobieren, und kann beweisen, dass kein besserer Plan existiert. Bei so kleinen Flotten geht das in der Regel schnell. Wird die Rechenzeit knapp, bleibt nur die beste bisher gefundene Lösung, ohne Beweis.

Das Programm zum Ausprobieren

Zu dieser Seite gehört ein Programm zum Ausprobieren, die Demo. Der erste Knopf unten öffnet sie, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie die Demo nicht. Dort stellen Sie Kai, Schiffe und Ankünfte selbst ein und sehen die Pläne nebeneinander.

Häufige Missverständnisse

• „Der beste Plan ist für alle gut.“ Nein. Der beste Plan hat nur die kleinste gewichtete Summe aller Wartezeiten. Wer wenig Gewicht hat, wartet trotzdem lange. Im besten gefundenen Plan des belebten Beispielhafens warten die Tramp-Schiffe am längsten.
• „Mit Tauschen findet man immer den besten Plan.“ Nein. Das Tauschen hört auf, wenn kein einzelner Tausch mehr hilft. Das muss nicht der beste Plan sein. Nur die Referenzrechnung kann das beweisen.

Woran Sie das im Alltag erkennen

• Etwas Begrenztes wird in Zeitstücken vergeben, etwa ein Besprechungsraum. Wer zuerst bucht, behält den Raum, auch wenn später ein wichtigerer Termin kommt.
• Eilige und weniger Eilige teilen sich eine Warteschlange, etwa in einer Arztpraxis. Wer vorgezogen wird, verlängert die Wartezeit der anderen.

Wie ernst ist das Rechenbild zu nehmen?

Die Wartezeiten stammen aus zwei Beispielhäfen und gelten für diese Flotten, nicht für jeden Hafen. Echte Häfen haben Gezeiten und Verspätungen, im Rechenbild fehlen sie.

Was Sie mitnehmen:

• Fragen Sie bei jeder Vorrangregel, wer dafür länger wartet.
• Fragen Sie bei jedem besten Plan, nach welchem Maß er der beste ist.
• Prüfen Sie, ob eine einfache Regel im ruhigen Fall schon reicht, bevor Sie eine kluge einführen.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Das Modell ist ein Planungsproblem auf einem Kai mit vorab bekannten Schiffen (Berth Allocation Problem, in der kontinuierlichen Variante, bei der die Position beliebig entlang des Kais liegt; die Demo bezeichnet es als NP-schwer). Alle Zahlen gelten nur für die genannten Beispielflotten.

• Kai und Zonen: Der Kai hat die Länge \(L\) in Metern und besteht aus zwei aneinandergrenzenden Zonen, erst Tiefwasser, dann Flachwasser. Eine Zone \(z\) reicht von \(z_{\text{lo}}\) bis \(z_{\text{hi}}\) und hat ein Tiefgang-Limit \(D_z\). Das Limit der Flachwasserzone beträgt drei Fünftel des Limits der Tiefwasserzone. Kailänge, Anteil der Tiefwasserzone und Limit \(D_z\) sind einstellbar; die Werte der Beispielflotten stehen unter Befunde.
• Schiffe: Schiff \(i = 0, \dots, n-1\) hat Länge \(\ell_i\), Tiefgang \(d_i\), früheste Anlegezeit \(a_i\), feste Liegezeit \(h_i\) und Klassengewicht \(w_i\): Mainliner 3, Feeder 1,5, Tramp 1. Längen, Ankünfte (Stunden) und Liegezeiten sind ganzzahlig; der Tiefgang dient nur dem Vergleich mit dem Zonenlimit. Eine Zufallsflotte zieht Länge, Tiefgang und Liegezeit normalverteilt um einstellbare Mittel mit einstellbarer Streuung (nach unten beschnitten), die Ankunft gleichverteilt im Ankunftsfenster. Die Klasse ist Mainliner mit einstellbarer Wahrscheinlichkeit, sonst Feeder oder Tramp mit gleicher Wahrscheinlichkeit. Eine Klasse kann deshalb leer oder einelementig sein.
• Entscheidung: Startzeit \(t_i \ge a_i\) und Kaiposition \(p_i\) je Schiff; Verholen nach dem Anlegen gibt es nicht.
• Sicherheitsabstand: Jedes Schiff reserviert die Breite \(\ell_i + m\), also seine Länge plus den Abstand \(m\). Das gilt auch am Ende einer Zone: Das letzte Schiff muss mit seinem Abstand noch hineinpassen. Das ist eine Modellentscheidung und strenger als nötig, wenn der Abstand nur zwischen zwei Schiffen gebraucht wird. Positionen sind ganze Meter. Eine Position ist frei, wenn das Intervall \([p, p + \ell_i + m)\) kein Positionsintervall eines zeitlich überlappenden Schiffs schneidet.
• Zielgröße: die gewichtete Wartezeit \(\sum_i w_i (t_i - a_i)\), mit der Wartezeit \(t_i - a_i\) als Anlegebeginn minus Ankunft. Als zweites Ziel dient die ungewichtete Gesamtwartezeit (siehe Zielfunktion). Berichtet werden außerdem die mittlere Wartezeit je Klasse und die letzte Abfahrt; diese beiden gehen nicht in die Optimierung ein.
• Unlösbare Szenarien: Passt schon ein einzelnes Schiff samt Abstand in keine verträgliche Zone, gibt es keinen Plan. Die Demo prüft das vor jeder Rechnung.

Die Formeln

Zulässige Positionen. Ein Schiff liegt vollständig in einer Zone, deren Limit zu seinem Tiefgang passt, und reserviert neben der Länge den Abstand \(m\):

\[p_i \in \bigcup_{z:\, D_z \ge d_i} [z_{\text{lo}}, \, z_{\text{hi}} - \ell_i - m]\]

Keine Überlappung. Für jedes Schiffspaar \(i \ne j\) mit zeitlicher Überlappung, also \(t_i < t_j + h_j\) und \(t_j < t_i + h_i\), muss räumliche Trennung gelten:

\[p_i + \ell_i + m \le p_j \qquad \text{oder} \qquad p_j + \ell_j + m \le p_i\]

Der Löser (Google OR-Tools CP-SAT) bildet jedes Schiff als Rechteck im Zeit-Position-Raum ab, Zeitintervall \([t_i, t_i + h_i)\) mal Positionsintervall \([p_i, p_i + \ell_i + m)\). Eine einzige eingebaute Nichtüberlappungsbedingung für Rechtecke (AddNoOverlap2D) ersetzt die Fallunterscheidung von Hand.

Zielfunktion. Primär zählt die gewichtete Wartezeit. Als zweites Ziel dient die ungewichtete Gesamtwartezeit, damit der Löser unter gleich guten Plänen keinen mit unnötiger Wartezeit liefert. Das Gewicht \(W\) multipliziert das erste Ziel und ist so groß gewählt, dass eine Verbesserung des zweiten Ziels nie eine Verschlechterung des ersten aufwiegt. Der Löser nimmt \(W = nH + 1\) mit dem Planungshorizont \(H\), der Summe aller Liegezeiten plus der spätesten Ankunft plus einem Tag. Jede Wartezeit ist höchstens \(H\), die ungewichtete Summe also höchstens \(nH\) und kleiner als \(W\), während jede Verbesserung des ersten Ziels mindestens eine ganze Einheit beträgt. Zur Ganzzahligkeit werden die Klassengewichte intern verdoppelt, aus 1,5 wird 3:

\[\min \; \Big(\sum_i w_i (t_i - a_i)\Big) \cdot W \;+\; \sum_i (t_i - a_i)\]

Die Verfahren

Alle drei Heuristiken bauen den Plan durch Einfügen. Sie legen eine Reihenfolge \(\sigma\) der Schiffe fest und fügen die Schiffe nacheinander in den bis dahin gebauten, zulässigen Plan ein:

• Einfügeschritt: Kandidatenzeiten für Schiff \(i\) sind die Ankunft \(a_i\) und alle Abfahrtszeiten \(t_j + h_j\) bereits eingefügter Schiffe \(j\), die mindestens \(a_i\) betragen. Für die kleinste Kandidatenzeit, zu der in irgendeiner verträglichen Zone eine freie Position existiert, wird die kleinste freie Position gewählt. Eingefügte Schiffe werden danach nie verschoben.
• Ankunftsreihenfolge: \(\sigma\) sortiert nach \(a_i\) aufsteigend, bei Gleichstand nach Index.
• Vorrang: \(\sigma\) sortiert nach \(w_i\) absteigend, dann nach \(a_i\).
• Vorrang plus Tauschsuche: Start bei der besseren der beiden Reihenfolgen, gemessen an der gewichteten Wartezeit. Dann werden in jedem Durchlauf alle Paare von Stellen der Reihenfolge in zufälliger Reihenfolge vertauscht, der Plan jeweils neu gebaut und eine echte Verbesserung sofort übernommen (Erstverbesserung, ohne Vergleich aller Tausche). Die Suche endet, wenn ein ganzer Durchlauf nichts verbessert oder die Zahl der Versuche (dreihundert) ausgeschöpft ist.
• Exakt: CP-SAT mit Zeitlimit und der besten Heuristik als Startvorschlag. Der Löser läuft nur auf Anforderung. Ist die Zeit abgelaufen, wird die beste gefundene Lösung ohne Optimalitätsbeweis gemeldet.

Herleitungen Schritt für Schritt

Die folgenden Herleitungen sind Rechnungen dieser Seite, keine Messungen der Demo.

Warum der Einfügeschritt nie scheitert.

• Voraussetzung: Jedes Schiff passt für sich allein irgendwo hin, das Szenario ist also nicht unlösbar.
• Schritt 1: Liegt keine Abfahrtszeit bei oder nach \(a_i\), sind alle eingefügten Schiffe bei \(a_i\) schon fort. Dann ist \(a_i\) selbst ein freier Kandidat.
• Schritt 2: Sonst ist die späteste Abfahrtszeit \(T \ge a_i\) ein Kandidat. Ab \(T\) liegt kein eingefügtes Schiff mehr am Kai, es gibt keinen Zeitkonflikt. In einer Zone, in die das Schiff allein passt, ist also eine Position frei. Die Suche findet daher spätestens bei \(T\) einen Platz.

Warum die Kandidatenzeiten genügen.

• Schritt 1: Bei festem Plan und fester Position sei \(t^*\) der früheste zulässige Anlegebeginn von Schiff \(i\), und es gelte \(t^* > a_i\).
• Schritt 2: Dann ist \(t^* - 1\) mit derselben Position unzulässig. Es gibt ein eingefügtes Schiff \(j\), das dort zeitlich und räumlich kollidiert, bei \(t^*\) aber nicht. Die räumliche Lage ist dieselbe, also hat sich nur die zeitliche Überlappung gelöst.
• Schritt 3: Bei \(t^*\) gilt \(t^* \ge t_j + h_j\) oder \(t_j \ge t^* + h_i\). Der zweite Fall ist ausgeschlossen, denn bei \(t^* - 1\) war \(t_j < t^* - 1 + h_i\). Also gilt \(t^* \ge t_j + h_j\), und wegen der Kollision bei \(t^* - 1\) auch \(t^* - 1 < t_j + h_j\). Mit ganzzahligen Zeiten folgt \(t^* = t_j + h_j\): Der früheste Anlegebeginn ist die Ankunft oder die Abfahrt eines anderen Schiffs.
• Bedingung: Ganzzahlige Zeiten und feste Pläne der schon eingefügten Schiffe.

Warum die Tauschsuche nie schlechter wird als der Start. Die Suche startet bei der Reihenfolge mit der kleineren gewichteten Wartezeit der beiden Konstruktionen und nimmt nur strenge Verbesserungen an. Die Zielgröße fällt also nur und liegt am Ende nicht über dem Minimum beider Konstruktionen. Das sagt nichts darüber, wie weit das Ergebnis vom Optimum entfernt ist.

Wenn alle Schiffe um denselben Abschnitt konkurrieren: ein Liegeplatz.

• Voraussetzung: Alle Schiffe brauchen dieselbe Zone, und für je zwei Schiffe ist die Summe der Breiten \(\ell_i + m\) größer als die Zone. Dann liegt immer nur ein Schiff in der Zone, ein Plan ist eine Reihenfolge auf einem Liegeplatz.
• Schritt 1: Mit der Abfahrt \(C_i = t_i + h_i\) gilt \(\sum_i w_i (t_i - a_i) = \sum_i w_i C_i - \sum_i w_i (h_i + a_i)\). Der zweite Term hängt nicht vom Plan ab, es genügt also, \(\sum_i w_i C_i\) zu minimieren.
• Schritt 2: Liegen zwei Schiffe \(i\) und \(j\) unmittelbar hintereinander und beginnt das erste zur Zeit \(s\), so tragen sie bei \(i\) zuerst \(w_i (s + h_i) + w_j (s + h_i + h_j)\) bei, bei \(j\) zuerst \(w_j (s + h_j) + w_i (s + h_j + h_i)\). Die Differenz (erste Reihenfolge minus zweite) ist \(w_j h_i - w_i h_j\).
• Schritt 3: Schiff \(i\) sollte also vor \(j\) liegen, wenn \(h_i / w_i < h_j / w_j\) gilt. Sind alle Schiffe schon da, also alle \(a_i\) gleich, ordnet das aufsteigende Verhältnis \(h_i / w_i\) die Schiffe optimal an (Regel nach Smith, siehe Quellen). Jede Reihenfolge lässt sich durch solche Nachbartausche ohne Verschlechterung dorthin bringen.
• Schritt 4: Die Vorrang-Reihenfolge ordnet nur nach \(w_i\) und dann nach Ankunft. Sie stimmt mit der aufsteigenden Ordnung von \(h_i / w_i\) überein, wenn alle Liegezeiten gleich sind. Das ist hinreichend, nicht notwendig: Sie stimmt auch dann überein, wenn für jedes Paar mit \(w_i > w_j\) gilt \(h_i / w_i \le h_j / w_j\). Bei ungleichen Liegezeiten kann sie abweichen, wie das Beispiel unten zeigt. Bei ungleichen Ankünften kommen Leerzeiten und Freigabezeiten hinzu, das Problem ist dann allgemein schwer (für die ungewichtete Variante bekannt, siehe Quellen).

Durchgerechnet: zwei Schiffe, ein Liegeplatz. Mainliner A (Gewicht 3, Liegezeit \(h_A\)) und Tramp B (Gewicht 1, Liegezeit 2) kommen zur selben Zeit. Liegt A zuerst, wartet B \(h_A\) Stunden, die Kosten sind \(1 \cdot h_A\). Liegt B zuerst, wartet A 2 Stunden, die Kosten sind \(3 \cdot 2 = 6\). Bei \(h_A = 9\) gilt 9 gegen 6: B zuerst ist besser, obwohl B unwichtiger ist. Bei \(h_A = 5\) gilt 5 gegen 6: A zuerst ist besser. Die Grenze liegt bei \(h_A = 6\), wo beide Reihenfolgen gleich teuer sind. Ein Mainliner mit dreifachem Gewicht soll also nur vor dem Tramp-Schiff liegen, wenn seine Liegezeit höchstens das Dreifache der Liegezeit des Tramp-Schiffs beträgt.

Durchgerechnet: warum Vorrang im ruhigen Fall verliert

Rechnung dieser Seite mit dem Programm der Demo, keine Messung der Demo. Das ruhige Beispielszenario (Parameter unter Befunde) mit fünf Schiffen, mittlerer Länge einhundertvierzig Meter und weit gestreuten Ankünften enthält zwei Feeder, drei Tramp-Schiffe und keinen Mainliner. Vier der fünf Schiffe brauchen die Tiefwasserzone, und dort passt immer nur eines.

• Konfliktpaar: Ein Tramp-Schiff trifft fünf Stunden vor einem Feeder ein. Beide liegen acht Stunden.
• Ankunftsreihenfolge: Das Tramp-Schiff legt sofort an, der Feeder wartet drei Stunden, sein Beitrag ist \(1{,}5 \cdot 3\), also viereinhalb. Ein weiteres Tramp-Schiff (Ankunft sechs Stunden nach dem Feeder, Liegezeit zwölf Stunden) beginnt mit der Abfahrt des Feeders und wartet fünf Stunden. Summe: neuneinhalb.
• Vorrang: Der Feeder wird zuerst eingetragen und legt bei seiner Ankunft an. Das frühere Tramp-Schiff beginnt erst mit der Abfahrt des Feeders und wartet dreizehn Stunden, das weitere beginnt nach ihm und wartet zehn. Summe: dreiundzwanzig, mehr als das Doppelte.
• Tauschsuche: Sie startet bei der Ankunftsreihenfolge, der besseren Konstruktion, und findet keine Verbesserung. Ihr Ergebnis gleicht der Ankunftsreihenfolge.

Befunde

Alle Werte sind Einzelwerte je Szenario und Zufallsflotte, keine Mittel über viele Flotten. Wartezeiten sind Mittelwerte je Klasse in Stunden. Zeilen mit dem Vermerk „Rechnung dieser Seite“ stammen aus dem Nachrechnen mit dem Programm der Demo; die übrigen gibt die Dokumentation der Demo an.

Frage	Befund
Wer gewinnt und wer zahlt, wenn Mainliner Vorrang haben? (Kai 700 m, Tiefwasserzone 40 %, also 280 m, mittlere Schiffslänge 200 m, eine feste Zufallsflotte)	Mittlere Wartezeit je Klasse bei Ankunftsreihenfolge gegen Vorrang: Mainliner 41,0 gegen 8,3, Feeder 9,0 gegen 54,0, Tramp 30,0 gegen 75,0.
Wie sind die beiden Beispielflotten aufgebaut? (Rechnung dieser Seite, aus dem Programm der Demo)	Belebter Fall: 7 Schiffe, Kai 700 m, Tiefwasseranteil 40 % mit Limit sechzehn Meter, mittlere Länge 200 m, mittlerer Tiefgang zwölf Meter, mittlere Liegezeit sechzehn Stunden, Ankunftsfenster vierundzwanzig Stunden, Mainliner-Anteil die Hälfte, Abstand 15 m, Startwert des Zufallsgenerators 1. Ruhiger Fall: 5 Schiffe, Kai fünfhundert Meter, Tiefwasseranteil 40 % mit Limit dreizehn Meter, mittlere Länge einhundertvierzig Meter, mittlerer Tiefgang acht Meter, mittlere Liegezeit 10 Stunden, Ankunftsfenster achtundvierzig Stunden, Mainliner-Anteil ein Zehntel, Abstand zwölf Meter, Startwert 3. Die Streuungen von Länge, Tiefgang und Liegezeit sind einstellbar und waren in beiden Fällen von null verschieden.
Wie belastbar sind diese Klassenmittel? (dieselbe Flotte)	Rechnung dieser Seite: Die Flotte hat sieben Schiffe. Alle brauchen die Tiefwasserzone, und dort liegt in allen drei Plänen immer nur ein Schiff. Die Feeder-Klasse besteht aus einem einzigen Schiff, die Mainliner-Klasse aus dreien, die Tramp-Klasse aus dreien.
Schlägt die Tauschsuche beide Regeln? (dieselbe Flotte)	Rechnung dieser Seite: Die gewichtete Wartezeit ist niedriger als bei Ankunftsreihenfolge und bei Vorrang. Das Mainliner-Mittel liegt unter dem des Vorrangs, das Feeder-Mittel gleicht dem der Ankunftsreihenfolge, das Tramp-Mittel liegt zwischen beiden Regeln.
Hilft Vorrang immer? (ruhiges Szenario mit fünf Schiffen)	Rechnung dieser Seite: Nein. Die gewichtete Wartezeit liegt bei Vorrang mehr als doppelt so hoch wie bei Ankunftsreihenfolge; die Tauschsuche gleicht der Ankunftsreihenfolge.
Wann ist ein Szenario unlösbar?	Wenn ein einzelnes Schiff samt Abstand in keine verträgliche Zone passt. Bei Kai 550 m, Tiefwasseranteil 30 % (165 m) und mittlerer Schiffslänge 220 m braucht ein Schiff mit großem Tiefgang 220 + 15 = 235 m, mehr als die Tiefwasserzone breit ist, und darf nirgends sonst liegen. Mit Kai 700 m, Anteil 40 % (280 m) und 200 m ist das behoben.
Wie schnell löst der exakte Löser?	Die Dokumentation der Demo nennt für die größte mögliche Flotte (10 Schiffe) unter 200 ms mit Optimalitätsbeweis. Eine eigene Zeitmessung gibt es hier nicht.

Was die Messung zeigt und wo die Grenzen liegen

Was sie belegt:

• Die Umverteilung der Wartezeit durch Vorrang ist in der genannten Flotte gemessen: Mainliner warten weniger, Feeder und Tramp mehr. Das zeigt, dass Vorrang Wartezeit verschiebt und dass dies so ausgeprägt vorkommen kann. Es zeigt nicht, wie groß der Effekt in anderen Flotten ist. Die Dokumentation nennt diese Flotte einen besonders klaren Beleg.
• Dass Vorrang auch verlieren kann, stützt sich auf eine zweite Einzelflotte. Es zeigt, dass es vorkommt, nicht wie oft. Der Verlust folgt aus der Vorrang-Reihenfolge zusammen mit der Regel, dass eingefügte Schiffe nie verschoben werden; ein Verfahren, das Schiffe verschiebt oder Lücken füllt, ist hier nicht gemessen, der Befund gilt also nicht für Vorrang als Prinzip.
• Zulässigkeit: In den Prüfungen der Demo geht jeder getestete Plan, ob von einer Heuristik oder vom Löser, durch eine unabhängige Zulässigkeitsprüfung. Im laufenden Programm wird diese Prüfung nicht ausgeführt. Auf kleinen Zufallsfällen stimmt sie mit einer Zellbelegungsprüfung überein, und der Löser trifft bei drei Schiffen das durch Vollaufzählung bestimmte Optimum. Beides gilt für kleine Fälle, nicht für die Größen der Demo.

Was sie nicht belegt:

• Abstand zum Optimum: Wie weit die Tauschsuche vom bewiesenen Optimum des Modells entfernt liegt, ist hier nicht gemessen, weil der Löser nicht gerechnet wurde. Rechnung dieser Seite: In beiden Beispielflotten erreicht die Tauschsuche das Minimum über alle Einfüge-Reihenfolgen (Vollaufzählung). Das ist kein Optimalitätsbeweis, denn das Modell des Lösers erlaubt zusätzlich Leerzeiten und andere Pläne als das Einfügen.
• Kleine Klassen: Klassenmittel über ein bis drei Schiffe schwanken stark von Flotte zu Flotte. Wie stark, ist nicht gemessen.
• Rechenzeit: Die Demo räumt ein, dass bei vielen Schiffen und engem Kai das Zeitlimit greifen kann, während die Dokumentation für die größte Flotte „durchweg“ unter 200 ms angibt. Welche Angabe zutrifft, ist hier nicht nachgemessen und lässt sich ohne Messung nicht auflösen; greift das Zeitlimit, kennzeichnet die Demo das Ergebnis als ohne Optimalitätsbeweis. Rechenzeiten hängen vom Rechner ab.
• Ziel und Gewichte: Die Gewichte 3, 1,5 und 1 sind eine Setzung. Anschlussverkehr, Fristen und Verspätungskosten sind nicht modelliert; der Vorrang der Mainliner wirkt nur über das Gewicht. Gerechtigkeit zwischen den Schiffen ist kein Ziel, und die Wartezeit zählt ab der planmäßigen Ankunft.
• Modellannahmen: Ankünfte, Liegezeiten und Tiefgänge sind vorab bekannt, es gibt keine Verspätungen. Die Liegezeit ist fest und hängt nicht von der Zahl der eingesetzten Containerbrücken ab. Tidenfenster fehlen. Ein Schiff bleibt an seinem Platz, und es gibt nur zwei Zonen.

Erweiterungen und Verweise

Zwei Erweiterungen sind in der Demo bewusst nicht umgesetzt. Tidenfenster würden die Startzeiten jedes Schiffs auf periodische Fenster einschränken. Eine von der Kranzahl abhängige Liegezeit würde das Modell mit der Brückeneinsatzplanung verbinden.

Verwandte Demos dieser Website:

• Unpünktliche Schiffe: Die Robuste Kaiplatzplanung lässt die Schiffe später als geplant ankommen und stellt Reserve im Plan gegen Neuplanung im Betrieb. Instanzen, Einfügeverfahren und Löser stammen aus der hier erklärten Demo.
• Die Ebene darunter: Die Containerbrücken-Einsatzplanung entscheidet, welche Brücke welchen Abschnitt eines bereits liegenden Schiffs bearbeitet.

Quellen

• Cordeau, Laporte, Legato, Moccia (2005): Models and tabu search heuristics for the berth-allocation problem. Transportation Science 39 (von der Demo als Bezug für die kontinuierliche Formulierung genannt; Inhalt und Zuordnung nicht geprüft).
• Smith (1956): Various optimizers for single-stage production. Naval Research Logistics Quarterly 3 (Regel zur Reihenfolge nach Verhältnis von Dauer zu Gewicht).
• Lenstra, Rinnooy Kan, Brucker (1977): Complexity of machine scheduling problems. Annals of Discrete Mathematics 1 (Schwere von Reihenfolgeproblemen mit Freigabezeiten).
• Quelltext, Beschreibung und Prüfungen der Demo: github.com/sebastian-hanisch/berth-allocation-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Angaben stammen aus dem Gedächtnis und sind nicht geprüft. Die Befundtabelle gibt die Dokumentation der Demo wieder, soweit sie nicht als Rechnung dieser Seite gekennzeichnet ist; Herleitungen und gekennzeichnete Werte sind eigene Rechnungen.