Die Schiffsstauplanung verständlich erklärt

Beim Beladen eines Schiffs wollen zwei Dinge in entgegengesetzte Richtungen: Was zuerst ausgeladen wird, soll oben liegen, und Schweres soll unten stehen. Beides zugleich scheint unmöglich. Die Seite zeigt, warum zwei einfache Regeln scheitern und warum es bei mäßig strenger Vorgabe doch fast ohne Mehraufwand geht.

Zuletzt aktualisiert: 11. November 2026

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

Zwei Wünsche an jeden Stapel

Stellen Sie sich einen Lieferwagen vor. Er hat Pakete für fünf Kunden geladen, die er nacheinander beliefert. Die Pakete stehen in Stapeln im Laderaum.

Der Fahrer hat zwei Wünsche. Erstens soll beim ersten Kunden nichts im Weg stehen. Liegt dessen Paket unter dem Paket für den dritten Kunden, muss der Fahrer das obere abheben und wieder aufsetzen. Das kostet Zeit. Zweitens soll Schweres unten stehen. Sonst wird der Wagen kopflastig und kippt leichter. Auch links und rechts soll ungefähr gleich viel Gewicht stehen.

Auf einem Containerschiff ist es dasselbe, nur größer. Aus den Paketen werden Container, aus den Kunden die Häfen, die das Schiff nacheinander anläuft. Der Zielhafen eines Containers ist der Hafen, in dem er von Bord geht. Steht ein Container für einen späteren Hafen über einem für einen früheren, muss ihn ein Kran abheben und zurücksetzen. Das heißt Umstauen. Es kostet zwei Kranbewegungen (Fachwort: Kranspiele).

Liegt ein Container über Containern für zwei frühere Häfen, wird er an beiden Häfen umgestaut und zählt für beide mit. Container für denselben Hafen behindern sich gegenseitig nicht.

Wie hier gerechnet wird

Die Zahlen stammen aus einem vereinfachten Rechenbild (Fachwort: Modell). Ein Computer erzeugt zufällige Ladelisten: erfundene Container, jeder mit einem Zielhafen und einer von vier Gewichtsklassen, von leicht bis schwer. Damit füllt er einen Schiffsabschnitt (Fachwort: Bay) mit acht Stapeln und sechs Lagen zu 90 %. Das sind gut vierzig Container. Er probiert vier Verfahren aus und wiederholt jeden Versuch mit vielen Listen. Bei jeder Zahl steht, über wie viele Listen sie gemittelt ist. Die Aussagen beschreiben dieses Rechenbild, nicht die Wirklichkeit.

Für die Stabilität zählt der Schwerpunkt, die Höhe, in der das Gewicht im Durchschnitt liegt. Ein Paket in der obersten Lage zieht ihn weiter nach oben als dasselbe Paket am Boden. Ein schweres Paket zieht stärker als ein leichtes. Eine Grenze legt fest, wie hoch der Schwerpunkt höchstens liegen darf. Beim Lieferwagen hieße 100 %: Der Fahrer lädt nach der Reihenfolge der Kunden und achtet nicht aufs Gewicht. 0 % hieße: Er muss die schwersten Pakete konsequent nach unten legen.

Erste Regel: nach Hafen sortieren

Der erste Wunsch lässt sich einfach erfüllen. Der Container für den am weitesten entfernten Hafen kommt nach unten, der für den nächsten Hafen nach oben. Dann steht in keinem Stapel etwas im Weg, und es gibt keine Umstauung.

Das Gewicht bleibt dabei unbeachtet. Schwere und leichte Container sind zufällig verteilt, also liegt der Schwerpunkt hoch. Sobald die Grenze strenger ist als die lockerste, fällt dieser Plan durch. In allen 20 Ladelisten dieses Versuchs war das so.

Zweite Regel: nach Gewicht sortieren

Die zweite Regel stellt die schwersten Container nach unten. Das ergibt den tiefsten Schwerpunkt, der überhaupt möglich ist, und erfüllt damit jede Grenze für den Schwerpunkt. Die Häfen ignoriert sie. Ein leichter Container für einen späten Hafen steht darum oft über einem schweren für einen frühen.

Im Mittel über 20 Listen gab es gut 26 Umstauungen, bei mehr Häfen noch mehr. Das sind mehr zusätzliche Kranbewegungen, als gut vierzig Container an Bord sind.

Beides zugleich: tauschen oder rechnen

Es geht besser, als der Anfang vermuten lässt. Ein Stapel verlangt nur eine Ordnung zwischen verschiedenen Häfen. Innerhalb eines Hafens darf man frei wählen, und dort lässt sich das Schwere nach unten setzen. Das ist eine Deutung dieser Seite. Gemessen wurde nur das Ergebnis.

Zwei Verfahren nutzen das. Die Tauschregel startet bei der Hafen-Sortierung und tauscht Container, bis der Schwerpunkt unter der Grenze liegt. Sie wählt die Tausche so, dass möglichst wenig Umstauungen entstehen. Ein Rechenverfahren, der exakte Löser, sucht unter allen erlaubten Anordnungen die mit den wenigsten Umstauungen. Es schließt Anordnungen systematisch aus, bis keine bessere übrig sein kann. Darum kann es am Ende beweisen, dass es keine bessere gibt. Reicht die Rechenzeit nicht, nennt es einen Bereich, in dem das Beste liegt.

Je strenger die Grenze, desto mehr schwere Container müssen nach unten. Desto eher stehen sie unter Containern für frühere Häfen. Wie viele Umstauungen beide im Mittel brauchten, zeigt diese Liste, gemittelt über acht Ladelisten:

• Grenze 100 %: Tauschregel keine Umstauung, exakter Löser keine.
• Grenze 30 %: Tauschregel etwa eine, exakter Löser keine.
• Grenze 10 %: Tauschregel knapp vier, exakter Löser keine.
• Grenze 0 %: Tauschregel knapp sechs, exakter Löser knapp drei.

Erst am strengen Ende kommt auch der Löser nicht mehr ohne Umstauungen aus. Dort konnte er nicht immer beweisen, dass es nicht noch besser geht. Seine Zahl ist darum ein Mittel der besten gefundenen Pläne.

Die Tauschregel kann sich festfahren. Sie hört auf, wenn kein einzelner Tausch mehr hilft. In den acht Listen oben hielt sie die Grenze immer ein. In anderen Zufallsfällen verfehlte sie die Grenze selten, je nach Seitenneigung in einer bis elf von hundert Listen.

Häufige Missverständnisse

• „Die tiefste Anordnung ist die sicherste Wahl.“ Sie ist die stabilste, aber die Grenze verlangt nur „stabil genug“. Wer mehr Stabilität einkauft, als verlangt wird, zahlt mit Umstauungen. Die zweite Regel baut immer die tiefste Anordnung. Sie braucht darum gleich viele Umstauungen, egal wie locker die Grenze ist.
• „Je klüger das Verfahren, desto größer der Gewinn.“ Gegenüber der Regel nach Gewicht spart der Löser über zwanzig Umstauungen. Gegenüber der Tauschregel spart er weniger, bei lockerer Grenze nichts, bei strenger Grenze einige. Der Grund: Die Tauschregel startet bei einer Ordnung ohne Umstauung und ändert nur, was die Grenze verlangt.

Woran Sie das im Alltag erkennen

• Sie packen den Kofferraum für eine Reise mit Zwischenstopps. Was Sie am ersten Halt brauchen, liegt unter dem Rest.
• Im Rucksack soll das Schwere unten liegen, sonst zieht er nach hinten. Die Regenjacke soll oben liegen, sonst müssen Sie alles auspacken.

Wie ernst ist das Rechenbild zu nehmen?

Es kennt nur einen Ladehafen und rechnet die Stabilität einfach, ohne Schiffsstatik. Die Zahlen zeigen Größenordnungen, keine Messung an echten Stauplänen.

Was Sie mitnehmen

• Fragen Sie bei jeder Ordnung, welchen zweiten Wunsch sie verletzt.
• Prüfen Sie, wie streng eine Bedingung wirklich ist. Oft kostet sie nichts, bis man ihr äußerstes Ende erreicht.
• Fragen Sie bei einer guten Faustregel, wie weit sie vom Besten entfernt ist, bevor Sie mehr Aufwand treiben.

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, die Demo. Sie erreichen es über den ersten Knopf unten. Zum Verstehen brauchen Sie es nicht. Der zweite Knopf führt zum zweiten Teil für Fachleute.

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. Er beschreibt die Stauplanung eines einzelnen Bays (eines Schiffsabschnitts) auf zufällig erzeugten Ladelisten, nicht auf echten Bay-Plänen.

• Bay und Container: \(C\) Stapel nebeneinander mit je höchstens \(T\) Lagen (Lage 0 ist unten), ein Ladehafen, Zielhäfen \(1,\dots,P\) in der Reihenfolge der Anläufe. Ein Container hat einen Zielhafen und eine von vier Gewichtsklassen \(1,\dots,4\) (leicht bis schwer); alle sind gleich groß und stehen ohne Lücken. Voreinstellung: 8 Stapel, 6 Lagen, 5 Zielhäfen. Wählbar sind 4 bis 12 Stapel, 3 bis 8 Lagen (höchstens 96 Zellen insgesamt) und 2 bis 7 Zielhäfen.
• Ladeliste: Die Zahl der Container ist der Füllgrad mal die Zahl der Zellen, kaufmännisch gerundet (Voreinstellung 90 %, wählbar von 50 bis 100 % in Schritten von 5). Zielhafen und Gewichtsklasse sind je Container gleichverteilt und voneinander unabhängig.
• Umstauungen: Ein Container \(j\) mit Zielhafen \(p_j\) wird am Hafen \(p < p_j\) umgestaut, wenn unter ihm ein Container mit Zielhafen \(p\) steht. Je Container zählt die Zahl der verschiedenen solchen Häfen \(p\) unter ihm. Mehrere Container desselben Hafens darunter zählen also einmal, Container mit gleichem Zielhafen behindern sich nicht. Beim Löschen von \(p\) wird der Container abgehoben und oben wieder aufgesetzt; er bleibt über den tieferen Containern.
• Kranzeit: Kranspiele = Container + 2 × Umstauungen: Jeder Container zählt einmal (Laden und Löschen werden nicht getrennt gezählt), jede Umstauung zweimal, denn sie braucht ein Abheben und ein Zurücksetzen. Das ist eine Modellannahme. Für die Umrechnung in Zeit gelten als Annahme 30 Spiele je Stunde.
• Stabilität: Zwei Bedingungen. Die Schwerpunkt-Summe \(\sum\) Gewichtsklasse mal Lage darf eine Grenze \(L\) nicht überschreiten, und das Seitenmoment darf dem Betrag nach eine Grenze \(B\) nicht überschreiten (links und rechts ähnlich viel Gewicht; in der Demo „Seitenneigung“ genannt). Beide stehen unter „Die Formeln“.
• Zielhafen zuerst: nach Zielhafen sortiert, der fernste unten, Lage für Lage von unten gefüllt, innerhalb eines Hafens die schweren zuerst; innerhalb einer Lage kommt jeder Container (schwere zuerst) auf die freie Position, die das Seitenmoment am nächsten an null hält. Null Umstauungen nach Konstruktion. Die Schwerpunkt-Summe dieses Plans heißt \(K_{\mathrm{pod}}\) („pod“ für englisch port of discharge, Zielhafen); allgemein steht \(K\) für die Schwerpunkt-Summe eines Plans.
• Gewicht zuerst (Referenz aller Vergleiche): die schwersten unten, Lage für Lage gefüllt, bei gleichem Gewicht der fernste Zielhafen unten. Innerhalb einer Lage gilt dieselbe Platzierung nach dem Seitenmoment wie bei Zielhafen zuerst. Die Seitengrenze ist damit nicht garantiert, war aber in allen nachgerechneten Fällen eingehalten (Seitenneigung 2 %, 20 Listen, drei Grenzwerte; Nachrechnung dieser Seite). Das liefert die kleinste erreichbare Schwerpunkt-Summe \(K_{\min}\) (laut Demo gegen eine Aufzählung und eine geschlossene Untergrenze geprüft). Der Plan hängt nicht von der Grenze ab.
• Sortieren + Reparatur: eine Eigenkonstruktion. Start bei Zielhafen zuerst; solange die Schwerpunkt-Summe über \(L\) liegt, wird der Tausch zweier Container gewählt, der sie je zusätzlicher Umstauung am günstigsten senkt und die Seitenneigung einhält. Danach folgen Tausche, die Umstauungen senken, ohne eine Grenze zu verletzen. Sie endet, wenn kein Tausch mehr hilft, und kann die Grenze dann verfehlen.
• Exakt: ein ganzzahliges Modell (CP-SAT aus Google OR-Tools, Formeln unten) mit der Reparatur als Startlösung. Zeitlimit 4 s in der Hauptansicht, 30 s auf Knopfdruck, 2 s je Ladeliste in Stichprobe und Kurve. Das Ergebnis trägt seine Beweislage: optimal (bewiesen), zulässig mit Intervall [untere Schranke, bester Wert], unzulässig (bewiesen) oder unbekannt. Ein Wert 0 ist als Optimum bewiesen; hat die Reparatur 0 Umstauungen, läuft der Löser nicht.
• Auswertung: Die Stichprobe stellt die eingestellten Bay- und Grenzwerte auf 20 fest erzeugte Ladelisten nach (unabhängig vom gewählten Zufallsstart). Die Kurve zeigt die Umstauungen über der Schwerpunkt-Grenze an 7 Grenzwerten (0, 10, 20, 30, 50, 75, 100 %) auf je 8 Ladelisten (große Bays bekommen weniger Punkte und Listen). Alle Vergleiche sind gepaart; in das Urteil gehen nur Listen ein, in denen beide Verfahren beide Grenzen einhalten.

Die Formeln

Index \(j\) steht für einen einzelnen Container, \(k\) für einen Typ (eine Kombination aus Zielhafen und Gewichtsklasse), \(p\) für einen Hafen. Drei Prozentgrößen sind zu unterscheiden: der Füllgrad, die Schwerpunkt-Grenze \(\theta\) (ein Anteil der Spanne zwischen \(K_{\min}\) und \(K_{\mathrm{pod}}\), ohne eigene physikalische Einheit) und die Seitenneigung \(\beta\) (ein Anteil am Moment). Ein Container-Typ \(k\) hat Zielhafen \(p_k \in \{1,\dots,P\}\) und Gewichtsklasse \(w_k \in \{1,\dots,4\}\) und kommt \(n_k\)-mal vor. Die Variable \(x_{c,t,k} \in \{0,1\}\) ist 1, wenn ein Container vom Typ \(k\) in Stapel \(c\) und Lage \(t\) steht; \(c\) läuft von 0 bis \(C-1\). Der Aufbau verlangt höchstens einen Container je Zelle, keine Lücke unten (eine Zelle ist nur besetzt, wenn die darunter besetzt ist) und dass alle Container jedes Typs stehen:

\[\sum_k x_{c,t,k} \le 1, \qquad \sum_k x_{c,t,k} \le \sum_k x_{c,t-1,k}, \qquad \sum_{c,t} x_{c,t,k} = n_k .\]

Mit dem Stapelgewicht \(W_c = \sum_{t,k} w_k x_{c,t,k}\) lauten die beiden Stabilitätsbedingungen: Die Schwerpunkt-Summe liegt höchstens bei \(L\), das Seitenmoment hat höchstens den Betrag \(B\). Der Faktor \(2c - C + 1\) ist der Abstand des Stapels von der Bay-Mitte in halben Stapelbreiten.

\[\sum_{c,t,k} w_k \, t \; x_{c,t,k} \le L, \qquad \Big| \sum_c (2c - C + 1)\, W_c \Big| \le B .\]

Die Grenzen entstehen ganzzahlig. Mit \(\theta \in [0,1]\) (eingestellt als 0 bis 100 %, Voreinstellung 30 %) gilt \(L = K_{\min} + \lfloor \theta\,(K_{\mathrm{pod}} - K_{\min}) \rfloor\). Bei \(\theta = 1\) ist die Zielhafen-Sortierung gerade noch erlaubt, bei \(\theta = 0\) nur Pläne mit der kleinsten Schwerpunkt-Summe, von denen es im Allgemeinen mehrere gibt; unter ihnen suchen Reparatur und Exakt die mit den wenigsten Umstauungen. Das Seitenmoment ist begrenzt durch \(B = \lfloor \beta\,(C-1) \sum_j w_j \rfloor\), einen Anteil \(\beta\) (eingestellt als 1 bis 5 %, Voreinstellung 2 %) der Obergrenze \((C-1)\sum_j w_j\) des Moments; sie würde erreicht, wenn alles Gewicht im Randstapel stünde, was die Höhengrenze \(T\) nicht immer zulässt. Dabei ist \(w_j\) die Gewichtsklasse des Containers \(j\).

Für die Umstauungen sei \(b_{c,t,p} = 1\), wenn unter Lage \(t\) des Stapels \(c\) ein Container mit Zielhafen \(p\) steht, und \(r_{c,t,p} \ge b_{c,t,p} + [\,p_{j(c,t)} > p\,] - 1\) mit dem Container \(j(c,t)\) in Zelle \((c,t)\). Dann ist \(r_{c,t,p} = 1\), wenn dieser Container an Hafen \(p\) umgestaut wird. Linear in \(x\) ist das, weil \([\,p_{j(c,t)} > p\,] = \sum_{q > p} \sum_{k:\,p_k = q} x_{c,t,k}\) die Besetzung der Zelle mit einem späteren Zielhafen zählt, und \(b\) folgt aus \(b_{c,0,p} = 0\), \(b_{c,t,p} \ge b_{c,t-1,p}\) und \(b_{c,t,p} \ge \sum_{k:\,p_k = p} x_{c,t-1,k}\). Da \(r\) minimiert wird, nehmen \(b\) und \(r\) die kleinsten zulässigen Werte an. Das Ziel lautet:

\[\min \sum_{c,t,p} r_{c,t,p} .\]

Ein Wert 0 ist bewiesen optimal, weil die Zielfunktion nicht negativ ist. Beim Vergleich eines Verfahrens \(V\) mit der Referenz \(V_0\) auf den Ladelisten \(\ell = 1,\dots,S\), in denen beide zulässig sind, ist \(\Delta_\ell = R_{V_0}^{(\ell)} - R_V^{(\ell)}\) der Gewinn (Umstauungen der Referenz minus Umstauungen von \(V\)); \(R^{(\ell)}\) ist die Gesamtzahl der Umstauungen auf Liste \(\ell\). Berichtet werden Mittel, Median und die Anteile der Listen mit \(\Delta_\ell > 0\), \(= 0\) und \(< 0\). Ein Unterschied gilt als klar, wenn \(|\bar\Delta| > 2\,\mathrm{SE}(\Delta)\) mit dem Standardfehler (SE) der gepaarten Differenz.

Zwei Rechnungen dieser Seite, keine Messungen der Demo. Erstens: Die Grenze \(L\) wächst mit \(\theta\), und \(B\) bleibt gleich. Jeder Plan, der bei einem \(\theta\) zulässig ist, bleibt es bei einem größeren. Auf derselben Ladeliste kann das Optimum also nicht steigen, wenn die Grenze lockerer wird. Zweitens: Zwei Kranspiele je Umstauung machen aus den 26,3 Umstauungen von Gewicht zuerst (Mittel, siehe Befunde) mehr als fünfzig zusätzliche Spiele. Bei der Voreinstellung stehen dreiundvierzig Container im Bay (Füllgrad mal Zellen, kaufmännisch gerundet); die Umstauungen kosten also mehr Spiele, als es Container gibt.

Befunde

Die Zahlen gelten, wenn nichts anderes steht, für die Voreinstellung (Bay 8 × 6, Füllgrad 90 %, 5 Zielhäfen, Seitenneigung 2 %). Sie stammen aus einer Vorab-Messreihe des Autors und aus Auswertungen der Demo auf zufälligen Ladelisten: 20 Listen für die Stichprobe, 8 für die Kurve. Eigene Nachrechnungen dieser Seite sind als solche gekennzeichnet.

Frage	Befund
Wie viele Umstauungen kostet Gewicht zuerst?	23 bis 27 bei 5 Zielhäfen, bis 30 bei 7 Zielhäfen; unabhängig von der Grenze. Auf welche Größe sich die Spanne bezieht, ist nicht angegeben. Die Nachrechnung dieser Seite bestätigt das Mittel 26,3 über die 20 Ladelisten der Stichprobe (5 Zielhäfen); die Einzelwerte der Listen streuen weiter als die Spanne.
Warum nicht einfach nach Zielhafen sortieren?	Unterhalb von 100 % Grenze ist der Plan in 20 von 20 Ladelisten unzulässig. Die Nachrechnung dieser Seite fand bei 0, 10 und 30 % ebenfalls 20 von 20 unzulässig, bei 100 % keinen.
Lohnt sich der exakte Löser?	Gegen Gewicht zuerst klar: Bei 30 % braucht Exakt im Mittel keine Umstauung, Gewicht zuerst gut 26. Gegen die Reparatur bei 30 % im Mittel über 20 Ladelisten 1,6 gegen 0, klar, aber klein; alle 20 Optima sind bewiesen. Auf den 8 Listen der Kurve unten sind es für die Reparatur 1,1.
Wie weit reicht der Löser?	Größtes wählbares Bay (12 × 8) mit 96 Containern (Füllgrad 100 %) bei 50 % Grenze: Median 1,3 s, alle Optima bewiesen. Das ist eine Angabe des Autors, hier nicht nachgeprüft; Laufzeiten hängen von Rechner und Last ab. In der Voreinstellung bleiben bei 0 % Grenze 13 von 20 Optima im Zeitlimit von 2 s unbewiesen; dort steht ein Intervall.
Ist die Reparatur zuverlässig?	Nein, sie verfehlt die Grenze gelegentlich. Der Test der Demo sichert nur, dass sie die Grenze in höchstens zehn von hundert vergleichbaren Zufallsfällen verfehlt. Die Nachrechnung dieser Seite ergab in diesen Zufalls-Bays (Seitenneigung 3 %) gut zwei von hundert. In der Voreinstellung bei 0 % Grenze fehlte sie bei Seitenneigung 2 % in einer von hundert Listen, bei Seitenneigung 1 % in elf von hundert. Das Verfehlen geschieht laut Test der Demo an einem lokalen Ende (kein einzelner Tausch hilft mehr). In 1 von 186 Fällen, in denen beide Verfahren zulässig sind, ist sie schlechter als Gewicht zuerst.
Wo liegt die Kante?	Die Kante ist der strengste Rand der Grenze, ab dem auch das Optimum Umstauungen kostet: bei 0 %. Bei 10 % war das Optimum in einer zweiten Messung im Mittel über 20 Listen höchstens 0,2 (bei siebzehn von 20 bewiesen, sonst beste gefundene Pläne), in der Kurve unten 0.

Die Kurve zeigt die mittleren Umstauungen über der Schwerpunkt-Grenze (Mittel über 8 Ladelisten, Zeitlimit 2 s je Liste):

Grenze in %	0	10	20	30	50	75	100
Exakt (beste gefundene Pläne)	2,6	0	0,1	0	0	0	0
Reparatur	5,9	3,6	2,4	1,1	0,75	0,25	0

Ab etwa 10 % Grenze ist die Stabilität im Mittel praktisch kostenlos; erst bei 0 % entstehen auch im Optimum Umstauungen. Auf diesen 8 Listen fehlen der Reparatur gegenüber Exakt bis zu 3,6 Umstauungen (bei 10 %, wo Exakt bei 0 liegt); auf 20 Listen sind es bei 10 % etwa 4 (Nachrechnung dieser Seite). Der Wert 0,1 bei 20 % steht über dem Wert 0 bei 10 %, obwohl das Optimum bei lockerer Grenze nicht steigen kann (Rechnung oben; die Kurve nutzt an jedem Grenzwert dieselben Listen). Eine unabhängige Nachrechnung mit einem eigenen ganzzahligen Programm fand bei 10 % und bei 20 % auf allen 8 Listen das Optimum 0. Die 0,1 ist also eine unbewiesene Obergrenze: Im Zeitlimit kam der Löser in einer Liste nicht auf 0. Die Werte der Zeile Exakt sind Mittel der besten gefundenen Pläne, keine Mittel bewiesener Optima.

Was die Messung zeigt und wo ihre Grenzen liegen

Das zeigt die Messung:

• Die Bausteine sind unabhängig geprüft: Die Formel für die Umstauungen stimmt mit einer Simulation des Löschens Hafen für Hafen auf 300 Zufallsstapeln überein, Gewicht zuerst liefert den tiefsten Schwerpunkt (gegen Aufzählung und eine geschlossene Untergrenze), und der Löser stimmt auf 300 Kleinstlisten mit einer vollständigen Aufzählung überein. Eine kleine Zahl weiterer Kleinstlisten prüft ihn zusätzlich gegen eine dynamische Programmierung über die Stapel.
• Der Vergleich ist gepaart. Ein Plan, der eine Grenze verletzt, zählt nicht als Verbesserung. Der Löser nennt einen unbewiesenen Wert nicht als Optimum, sondern als Intervall.
• Die Kurve mittelt über alle 8 Listen. Die Reparatur war dort an jedem Punkt in allen 8 Listen zulässig (Nachrechnung dieser Seite), der Mittelwert ist also nicht durch Ausfiltern verzerrt.

Das zeigt sie nicht:

• Zufallsmodell: Zielhafen und Gewichtsklasse sind gleichverteilt und unabhängig. Echte Ladelisten haben korrelierte Gewichte; das ist nicht modelliert. Alle Zahlen sind Größenordnungen aus einer Simulation, keine Messung an echten Bay-Plänen.
• Ein Bay, ein Ladehafen: Es gibt kein Zu- und Aussteigen unterwegs; weitere fehlende Merkmale stehen im nächsten Abschnitt.
• Vereinfachte Stabilität: Die Schwerpunkt-Summe aus Gewicht mal Lage und ein einfaches Seitenmoment ersetzen keine Stabilitätsrechnung eines Schiffs. Die 30 Kranspiele je Stunde sind eine Annahme; die Kranzeit ist eine Umrechnung, keine Messung.
• Eine Konfiguration, wenige Listen: Die Kurve gilt für Bay 8 × 6, 90 % Füllgrad, 5 Zielhäfen und Seitenneigung 2 % auf 8 Listen je Grenzwert. Andere Einstellungen rechnet die Demo nur live nach.
• Die Reparatur ist eine Eigenkonstruktion: Eine bessere Tauschregel könnte die Lücke zum Optimum schließen. Aussagen über „die“ Heuristik für dieses Problem gibt es nicht.
• Zeitlimit: Die Beweislage schwankt mit der Rechenlast. Bei überlasteter CPU bleiben Optima unbewiesen, die sonst in unter einer Sekunde bewiesen sind. Eine gemeldete 0 ist immer bewiesen; ob der Löser im Limit eine mögliche 0 findet, hängt von der Rechenlast ab (die 0,1 bei 20 % ist so ein Fall).
• Vergleichsbasis: Verglichen wird mit Regeln, die für die Demo gebaut sind; eine Standard-Heuristik aus der Literatur ist nicht dabei. Gewicht zuerst ignoriert die Häfen und ist ein schwacher Gegner. Die Kurve zeigt nur Mittelwerte; Median und Verteilung zeigt die Demo in der Stichprobe.
• Urteil über Stichproben: In das Urteil gehen nur Listen ein, in denen beide Verfahren zulässig sind. Das kann ein Verfahren begünstigen, dessen Fehlschläge ausfallen. Das Kriterium von zwei Standardfehlern ist bei 20 Listen, vielen Gleichständen und schiefen Differenzen nur grob.

Erweiterungen und Verweise

Bewusst nicht gebaut sind mehrere Ladehäfen (Zu- und Aussteigen unterwegs), Kühlcontainer-Steckdosen, 20- und 40-Fuß-Container, Gefahrgut-Trennung, eine Stapelgewichtsgrenze, Lukendeckel, mehrere Bays mit Kranverteilung, korrelierte Gewichte und eine Kalibrierung an echten Bay-Plänen. Nahe Fragen liegen in Nachbar-Demos:

• mehrhafenstau-demo: dieselbe Umstau-Frage aus Reedereisicht, aber ohne Gewicht und Stabilität: wie viele Stapelplätze eine Bucht für null Umstauungen über eine ganze Route mit der nach Zielhafen sortierten Regel braucht.
• uld-beladeplan-demo: ein Schwerpunktfenster in der Luftfracht, bei vollem und leerem Tank, ohne Umstauen; dazu die Seite Der Beladeplan für Luftfracht verständlich erklärt.

Quellen

• Quelltext, Messreihe und Tests der Demo: github.com/sebastian-hanisch/stauplanung-demo.
• Löser: CP-SAT aus Google OR-Tools.
• Zum Umstauproblem (Blocks Relocation Problem): M. Caserta, S. Schwarze, S. Voß (2012), A mathematical formulation and complexity considerations for the blocks relocation problem, European Journal of Operational Research.
• Zur Stauplanung mit Umstauungen als Zielgröße: E. Avriel, M. Penn, N. Shpirer, S. Witteboon (1998), Stowage planning for container ships to reduce the number of shifts, Annals of Operations Research.

Die Demo nennt keine Literatur. Von den beiden Veröffentlichungen sind Titel, Zeitschrift und Jahr per Suche bestätigt; ihr Inhalt ist nicht gelesen. Sie passen nur lose: In diesem Modell wird ein abgehobener Container oben auf denselben Stapel zurückgesetzt, im Blocks Relocation Problem wählt man den Zielstapel. Die Rechnungen dieser Seite sind keine Messungen der Demo.