Die Seefracht-Konsolidierung verständlich erklärt

Ein Versandunternehmen sammelt kleine Pakete aus vielen Gegenden und schickt sie in Containern über das Meer. Wer packt was zusammen, und in welchem Hafen geht jeder Container an Land? Die Seite zeigt, warum die naheliegende Ordnung nur manchmal die billigste ist.

Zuletzt aktualisiert: 11. November 2026

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

Viele kleine Pakete, ein Schiff

Ein Versandunternehmen sammelt Pakete von vielen Kunden. Alle sollen über das Meer in ein anderes Land. Die Pakete sind unterschiedlich groß, und die Empfänger wohnen in verschiedenen Gegenden.

Verschifft wird in Containern, das sind große Stahlkisten. Ein Container fasst nur begrenzt viel. Seine Überfahrt kostet einen festen Preis, egal ob er voll oder halb leer ist. Darum teilen sich mehrere Pakete einen Container. Fachleute nennen das Konsolidierung.

Dazu kommt der Hafen. Ein Container kann in mehreren Häfen an Land gehen, und die Überfahrt hat je nach Hafen einen anderen Preis. Vom Hafen bringt ein Lkw jedes Paket zum Empfänger. Das kostet mehr bei großen Paketen und langen Wegen.

Gesucht ist ein Plan: Welche Pakete teilen sich einen Container, und über welchen Hafen fährt jeder Container? Beides hängt zusammen. Welcher Hafen am billigsten ist, hängt davon ab, wohin die Pakete im Container wollen.

Zwei einfache Wege zu einem Plan

Die Seite zeigt das an einem vereinfachten Rechenbild, also einem Zufallsmodell mit erfundenen Zahlen. Karte, Preise und Pakete sind zufällig erzeugt. Der Lkw-Preis wächst mit der Größe des Pakets und der Länge des Wegs. Alles, was hier über Messungen steht, beschreibt dieses Rechenbild und nicht die Wirklichkeit.

Jede Gegend hat einen Hafen, von dem aus der Lkw am billigsten fährt. Er heißt hier Lieblingshafen. Nun zwei Wege, die nahe liegen. Bei beiden bekommt jeder fertig gepackte Container zum Schluss den Hafen, bei dem Überfahrt und Lkw-Wege zusammen am wenigsten kosten. Das muss nicht der Lieblingshafen sein.

• Vollpacken: Man legt die größten Pakete zuerst in den ersten Container mit freiem Platz und achtet nicht auf die Empfänger. Weil nur die Größe zählt, lassen sich die Container dicht füllen. Dafür liegen Pakete für weit entfernte Gegenden zusammen, und der Hafen ist ein Kompromiss.
• Nach Hafen sortieren: Man bildet für jeden Lieblingshafen einen Haufen und packt jeden Haufen für sich. Dann haben alle Pakete in einem Container denselben Lieblingshafen, und die Lkw-Wege sind kurz. Dafür gibt es mehr Container, wie der nächste Abschnitt zeigt.

Wann sich das Sortieren lohnt

Sortieren hat einen Preis. Denken Sie an Wäsche. Wer Weißes und Buntes trennt, schont die Stoffe. Er braucht aber mehr Waschgänge, weil jeder Haufen eine halb volle Trommel übrig lässt.

Bei den Paketen ist es genauso. Jeder Haufen endet in einem Container, der nicht voll wird. In einer kleinen Stichprobe von fünf Zufallsfällen brauchte das Sortieren jedes Mal mehr Container als das Vollpacken. Jeder zusätzliche Container kostet eine ganze Überfahrt.

Ob sich das lohnt, entscheidet der Preis der Überfahrt. Ist er niedrig, spart der kurze Lkw-Weg mehr, als die zusätzlichen Container kosten. Ist er hoch, verliert das Sortieren seinen Vorteil und kippt am Ende ins Gegenteil.

Die Messung bestätigt das. In 10 Zufallsszenarien war das Sortieren beim üblichen Preis von 800 € je Container jedes Mal billiger als das Vollpacken. Beim Dreifachen dieses Preises war es nur noch in einem von 10 billiger. Dazwischen schrumpft sein Vorsprung allmählich. Einen scharfen Umschlag gibt es nicht. Jedes Szenario kippt bei einem anderen Preis, mal früher, mal später.

Beim üblichen Preis sparte das Sortieren in einer Messreihe mit 40 bis 200 Paketen rund 10 % der Kosten des Vollpackens.

Ein Paket darf auch den zweitbesten Hafen nehmen

Ein ausgedachtes Beispiel. Ein Container fasst 100 Einheiten, seine Überfahrt kostet 800 €. Es gibt drei Pakete: zwei für Gegend A mit 60 und 45 Einheiten und eines für Gegend B mit 55 Einheiten. Gegend A liegt nur knapp näher an Hafen eins als an Hafen zwei. Gegend B liegt viel näher an Hafen zwei.

Beim Sortieren warten die beiden Pakete aus A auf Hafen eins. Zusammen sind sie größer als ein Container, also brauchen sie zwei. Das Paket aus B bekommt einen dritten.

Besser ist es, wenn das kleine Paket aus A über Hafen zwei fährt. Dort teilt es sich mit dem Paket aus B einen Container, denn 45 und 55 ergeben genau 100. Der Lkw-Weg wird für dieses Paket um 45 € teurer. Dafür entfällt ein ganzer Container für 800 €. Unter dem Strich spart das 755 €.

Der dritte Weg sucht solche Gelegenheiten. Er startet mit einem fertigen Plan und probiert kleine Änderungen. Ein Paket zieht in einen anderen Container um. Zwei Pakete tauschen den Platz. Oder zwei Container werden ausgeleert und neu gefüllt. Jede Änderung, die Geld spart, bleibt.

Er startet von zwei Plänen aus, dem Vollpacken und einer vorab nachgebesserten Sortierung, denn keiner von beiden ist immer besser. Danach nimmt er das billigere Ergebnis. Weil er nur Änderungen behält, die Geld sparen, wird er nie teurer als diese beiden einfachen Wege. Wie viel er bringt, schwankt: Bei sehr teurer Überfahrt fand er in einem Fall nichts Besseres als das Vollpacken.

Der billigste Plan ist nicht immer der beste

Man kann zwei Alternativen zum billigsten Plan berechnen. Die erste nutzt nur wenige Häfen. Der Gedanke dahinter: Mit weniger Häfen arbeitet man mit weniger Spediteuren zusammen. Dafür werden die Lkw-Wege länger. In einem geprüften Fall kostete ein einziger Hafen 45 % mehr, zwei Häfen 19 % mehr. Ab drei erlaubten Häfen gab es keinen Unterschied.

Die zweite füllt die Container gleichmäßiger, sodass keiner randvoll ist. Dafür darf der Plan bis zu einer festen Grenze teurer werden.

Das Programm zum Ausprobieren

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, 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. Die drei Wege heißen dort „blind gepackt“, „hafen-bewusst gruppiert“ und „Beam Search“.

Häufige Missverständnisse

• „Mehr Container sind immer schlechter.“ Nein. Bei niedrigem Überfahrtspreis war der Plan mit mehr Containern billiger, weil die Lkw-Wege kürzer wurden.
• „Das Programm findet den besten Plan.“ Nein. Es probiert nur kleine Änderungen. Jedes weitere Paket vervielfacht die Zahl der Aufteilungen. Schon bei 40 Paketen sind es zu viele, um alle zu prüfen. Das Ergebnis ist eine gute Näherung.

Woran Sie das im Alltag erkennen

• Sie bestellen mit Nachbarn gemeinsam und lassen alles an einen Abholpunkt liefern. Jede Lieferung kostet Versand, und der Heimweg ist für jeden verschieden lang.
• Sie planen mit mehreren Autos eine Fahrt zu einem Treffpunkt. Jedes Auto kostet Sprit, egal wie voll es ist. Der Weg danach ist für jeden anders.

Wie ernst ist das Rechenbild zu nehmen?

Das Rechenbild kennt nur Größe und Entfernung. Gewicht, Gefahrgut, Abfahrtstermine und Mengenrabatte fehlen. Die Zahlen zeigen Muster und keine echten Preise.

Was Sie mitnehmen:

• Fragen Sie bei jedem Sammelplan zuerst, was ein zusätzlicher Container kostet und was ein kürzerer Weg spart.
• Prüfen Sie, bei welchem Preis ein Verfahren kippt, statt einem Verfahren immer zu trauen.
• Fragen Sie nach Alternativen zum billigsten Plan, etwa mit weniger Beteiligten oder gleichmäßigerer Füllung.

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 eine zufällig erzeugte Instanz mit festen Regeln; alle Messzahlen gelten nur für diese Bauart.

• Gegeben: Packstücke \(i \in I = \{1,\dots,n\}\) mit Größe \(w_i > 0\) und Zielregion \(g_i\); Häfen \(K = \{1,\dots,m\}\); Containerkapazität \(Q\); Straßenkosten \(c^{road}_{r,k} \ge 0\) je Größeneinheit von Region \(r\) über Hafen \(k\); Seefracht \(c^{sea}_k \ge 0\) je genutztem Container über Hafen \(k\).
• Szenario: Häfen und Regionen erhalten zufällige Koordinaten, gleichverteilt in einem Quadrat der Seitenlänge neunzig. Die Straßenkosten je Größeneinheit sind das 0,5-Fache der euklidischen Entfernung zwischen Region und Hafen: Bei Entfernung 40 kostet ein Packstück der Größe 20 also vierhundert Euro Straße, gegen 800 € Seefracht je Container (Rechnung dieser Seite). Die Seefracht des Hafens \(k\) ist die Basis mal \(1 + u_k\), mit \(u_k\) gleichverteilt in \([-s, s]\) (Streuung \(s\)); die Häfen liegen also bis zu \(2s\) der Basis auseinander, bei \(s = 0{,}3\) bis zu 60 %. Packstückgrößen sind gleichverteilt zwischen 5 und 30, die Zielregionen gleichverteilt über die Regionen.
• Voreinstellung und Bereiche: 40 Packstücke (10 bis 100), 6 Regionen (3 bis 8), 3 Häfen (2 bis 5), Kapazität \(Q = 100\) (von 30 bis zum Dreifachen der Voreinstellung), Seefracht-Basis 800 € (200 bis 4.000 €), Streuung \(s = 0{,}3\) (0 bis 0,8).
• Plan und Kosten: Ein Container mit Inhalt \(C \subseteq I\) und \(\sum_{i \in C} w_i \le Q\) fährt über den Hafen, der seine Kosten minimiert (Formel unten). Ein Plan \(\sigma\) ist eine Zerlegung von \(I\) in solche Container; seine Kosten sind die Summe der Containerkosten, leere Container kosten nichts. Gesucht ist ein Plan mit kleinsten Gesamtkosten.
• Binäres Programm: Mit höchstens \(n\) Containern \(j\) und Variablen \(x_{ij}\) (Packstück \(i\) in Container \(j\)), \(y_j\) (Container \(j\) benutzt) und \(z_{jk}\) (Container \(j\) über Hafen \(k\)) lautet das Ziel \(\min \sum_{j,k} z_{jk}\,c^{sea}_k + \sum_{j,k,i} z_{jk}\,x_{ij}\,w_i\,c^{road}_{g_i,k}\). Nebenbedingungen: jedes Packstück in genau einem Container, \(\sum_i x_{ij} w_i \le Q\,y_j\), \(\sum_k z_{jk} = y_j\) (genau ein Hafen je benutztem Container) und \(x_{ij} \le y_j\). Das Produkt \(z_{jk}x_{ij}\) lässt sich durch eine Hilfsvariable mit drei linearen Ungleichungen ersetzen (McCormick, für zwei Binärvariablen exakt). Die Demo stellt dieses Programm nicht auf, sondern rechnet mit Heuristiken.
• Komplexität: Bei einem Hafen (\(m = 1\)) sind die Straßenkosten eine Konstante, und das Ziel ist die Seefracht mal die Containerzahl. Das ist 1D-Bin-Packing und NP-schwer; das allgemeine Problem enthält diesen Fall und ist damit ebenfalls NP-schwer.
• Blind gepackt (kurz „Vollpacken“) und hafen-bewusst gruppiert (kurz „Sortieren“): Beide packen mit First-Fit-Decreasing (FFD): Packstücke absteigend nach Größe, jedes in den ersten Container mit genug Restplatz, sonst in einen neuen. Blind gepackt packt alle Packstücke gemeinsam. Hafen-bewusst gruppiert bildet zuerst Gruppen von Packstücken mit gleichem Lieblingshafen \(k_{\mathrm{pref}}(r) = \arg\min_k c^{road}_{r,k}\) (nur nach Straßenkosten) und packt jede Gruppe für sich. Der Hafen eines Containers folgt bei beiden danach aus der Gesamtkostenformel und kann vom Gruppenhafen abweichen, weil dort die Seefracht mitzählt.
• Verbesserungssuche (in der Demo „Beam Search“ genannt): Sie startet von zwei Plänen, dem blind gepackten und einer alternierenden Neugruppierung der hafen-bewussten Gruppierung. Diese weist abwechselnd jedem Packstück den Hafen seines Containers zu und packt alle Packstücke mit gleichem Hafen neu per FFD, höchstens fünf Zyklen, angenommen nur bei echter Verbesserung. Von jedem Start aus wählt die Suche je Runde den besten Nachbarplan, höchstens drei Runden, Abbruch ohne Verbesserung. Nachbarn sind: ein Packstück in einen anderen Container verschieben, ein Packstück in einen neuen Container abspalten (beides jede Runde) und zwei Packstücke aus zwei Containern tauschen (nur in der ersten Runde, weil die Zahl der Paare quadratisch wächst). Der bessere der beiden Pläne wird mit Large Neighborhood Search (LNS) poliert: fünf Iterationen, in jeder werden zwei zufällig gewählte Container ausgeleert, die freien Packstücke (größte zuerst) dort eingefügt, wo die Zusatzkosten am kleinsten sind, und danach wird mit einer kleinen Verbesserungssuche (Beam-Breite 2, zwei Runden) nachgebessert; die beste je gesehene Lösung bleibt. Der Zufallsgenerator der LNS hat einen festen Startwert. Der Name „Beam Search“ ist historisch: In der Hauptsuche ist die Beam-Breite fest 1, es wird je Runde nur ein Plan verfolgt.
• Alternativen: (a) Wenige Häfen: Bei fester Packung wird für jede Anzahl \(k = 1, \dots, m\) die beste Teilmenge \(S\) von \(k\) Häfen gesucht, \(\min_{|S|=k} \sum_C \min_{h \in S} \big[ c^{sea}_h + \sum_{i \in C} w_i\, c^{road}_{g_i,h} \big]\). Der Aufschlag ist die Mehrkosten gegenüber der freien Hafenwahl (\(k = m\)). (b) Ausgeglichene Container: Durch Tausch von Packstücken zwischen zwei Containern wird die Varianz der Füllgrade \(\sum_{i \in C} w_i / Q\) gesenkt, solange die Gesamtkosten höchstens das \((1 + \tau)\)-Fache des kostenoptimalen Plans betragen, mit \(\tau = 5\,\%\).

Die Formeln

Hafenwahl bei festem Inhalt. Für einen Container mit Inhalt \(C\) ist der günstigste Hafen \(k^*(C) = \arg\min_{k \in K} \big[ c^{sea}_k + \sum_{i \in C} w_i\, c^{road}_{g_i,k} \big]\), und die Kosten des Containers sind

\[\mathrm{cost}(C) = c^{sea}_{k^*(C)} + \sum_{i \in C} w_i\, c^{road}_{g_i,k^*(C)}\]

Die Kosten eines Plans sind \(\mathrm{score}(\sigma) = \sum_{C \in \sigma} \mathrm{cost}(C)\). Die Hafenwahl für einen festen Inhalt ist eine einfache Suche über die \(m\) Häfen.

Hafen-Präferenz einer Region. Die Vorab-Gruppierung beachtet nur die Straßenkosten, nicht die Seefracht:

\[k_{\mathrm{pref}}(r) = \arg\min_{k \,\in\, K} \; c^{road}_{r,k}\]

Kipppunkt. Sei \(\Delta_{road}\) die Straßenkosten des blinden Plans minus die des hafen-bewussten Plans (die Ersparnis durch die Gruppierung) und \(\Delta_{sea}\) die Seefracht-Summe des hafen-bewussten Plans minus die des blinden (der Mehraufwand durch zusätzliche Container). Weil die Gesamtkosten Straßen- plus Seefracht sind, ist der hafen-bewusste Plan genau dann billiger, wenn

\[\Delta_{road} \;>\; \Delta_{sea}\]

gilt. \(\Delta_{sea}\) hängt von der Zahl der zusätzlichen Container und von der Hafenwahl aller Container ab, nicht nur vom Durchschnitt der Seefracht.

Packgüte. Für reines 1D-Bin-Packing ohne Hafenwahl gilt für FFD mit der optimalen Containerzahl \(\mathrm{OPT}(I)\) die Schranke

\[\mathrm{FFD}(I) \;\leq\; \tfrac{11}{9}\,\mathrm{OPT}(I) + \tfrac{6}{9}\]

Die Schranke ist ein Worst-Case-Wert (bis gut ein Fünftel über dem Optimum, plus eine Zugabe) und belegt für sich nicht, dass FFD hier nahe am Optimum liegt. Das zeigt erst die Messung: Andere Packreihenfolgen bringen kaum etwas (siehe Befunde).

Herleitungen und durchgerechnetes Beispiel

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

Wo liegt der Umschlagpunkt? Alle Häfen kosten gleich viel, Streuung \(s = 0\), Preis \(p\) je Container:

• Schritt 1: Beide Pläne hängen nicht von \(p\) ab. Die Packung folgt bei Vollpacken nur der Größe und bei der Gruppierung den Straßenkosten, und die Hafenwahl je Container vergleicht bei gleicher Seefracht nur die Straßenkosten.
• Schritt 2: Dann ist \(\Delta_{road}\) eine Konstante, und \(\Delta_{sea} = (t_a - t_b)\,p\) mit den Containerzahlen \(t_a\) (hafen-bewusst) und \(t_b\) (blind). Die Bedingung \(\Delta_{road} > \Delta_{sea}\) wird für \(t_a > t_b\) zu \(p < \Delta_{road}/(t_a - t_b)\).
• Schritt 3: Für \(t_a > t_b\) und \(\Delta_{road} > 0\) ist der Umschlagpunkt \(p^* = \Delta_{road}/(t_a - t_b)\); bei \(\Delta_{road} \le 0\) gewinnt das Sortieren dann nie. Für \(t_a \le t_b\) gilt \(\Delta_{sea} \le 0\): Mit \(\Delta_{road} > 0\) gewinnt das Sortieren bei jedem Preis. Mit \(\Delta_{road} \le 0\) gewinnt es nur für \(t_a < t_b\), und zwar erst bei hohem Preis, nämlich für \(p > -\Delta_{road}/(t_b - t_a)\); bei \(t_a = t_b\) nie. Fälle mit \(t_a < t_b\) kamen in den geprüften Szenarien nicht vor.
• Schritt 4: \(\Delta_{road}\) und die Containerzahlen hängen vom Szenario ab, also hat jedes Szenario seinen eigenen Umschlagpunkt. Der Anteil der Szenarien, in denen das Sortieren noch gewinnt, fällt über viele Zufallsszenarien deshalb allmählich statt als Stufe, wie die Messung unten zeigt. Für \(s > 0\) gilt das nur näherungsweise, weil die Hafenwahl dann auch von der Seefracht abhängt.
• Nachrechnung: Für die zehn Szenarien der Kipptabelle (30 Packstücke, 5 Regionen, 3 Häfen, Startwerte 1 bis 10) stimmt \(p^*\) bei \(s = 0\) mit dem per Intervallhalbierung gefundenen Umschlagpreis überein. Die Umschlagpreise liegen zwischen gut 800 € und knapp zweitausend Euro je Container, bei \(s = 0{,}3\) zwischen gut 1.000 € und gut zweitausend Euro. In einem Szenario haben beide Wege gleich viele Container, dort kippt es nie.

Warum das Sortieren Container kostet.

• Schritt 1: Hat eine Gruppe \(g\) die Gesamtgröße \(W_g\), braucht jede zulässige Packung mindestens \(\lceil W_g / Q \rceil\) Container für sie, denn ein Container fasst höchstens \(Q\).
• Schritt 2: Das Sortieren braucht also mindestens \(\sum_g \lceil W_g / Q \rceil\) Container, das Vollpacken mindestens \(\lceil \sum_g W_g / Q \rceil\). Die Summe der aufgerundeten Werte ist nie kleiner als der aufgerundete Gesamtwert: Jede Gruppe füllt ihren letzten Container nur zum Teil.
• Grenze: Das sind nur untere Schranken, und FFD ist nicht optimal. Dass das Sortieren nie weniger Container braucht als das Vollpacken, folgt daraus nicht. Es ist ein Befund: fünf geprüfte Fälle der Demo, und eine Nachprüfung dieser Seite an mehreren hundert Zufallsszenarien fand keinen Fall mit weniger Containern.

Durchgerechnetes Beispiel: warum die starre Gruppierung Geld liegen lässt. Konstruierter Fall: zwei Häfen mit Seefracht je 800 €, Kapazität 100. Region A hat Straßenkosten 10 über Hafen 1 und 11 über Hafen 2, Region B 50 bzw. 5. Packstücke: zwei aus A mit Größe 60 und 45, eines aus B mit Größe 55.

• Starre Gruppierung: A bevorzugt Hafen 1, B Hafen 2. Die beiden A-Packstücke passen nicht zusammen (60 + 45 > 100) und brauchen zwei Container, das B-Packstück einen dritten. Das sind drei Seefrachten, die Gesamtkosten betragen 3.725 €.
• Flexible Lösung: Das A-Packstück der Größe 45 fährt über Hafen 2 und füllt mit dem B-Packstück genau einen Container (45 + 55 = 100). Seine Straßenkosten steigen um \(45 \cdot (11 - 10) = 45\) €, die Seefracht sinkt um einen ganzen Container (800 €). Die Gesamtkosten betragen 2.970 €.
• Ergebnis: Die Ersparnis ist 755 €, rund 20 % der starren Lösung. Die Verbesserungssuche liefert für diesen Fall 2.970 €. Hier erreicht aber schon das Vollpacken diesen Wert (ein Container mit 60, ein zweiter mit 55 und 45); nur die starre Gruppierung lässt Geld liegen. Von der Gruppierung aus findet die Suche den Wert durch Verschieben des 45er-Packstücks.

Befunde

Wenn nichts anderes steht, gelten die Zahlen für Szenarien mit Streuung 0,3 und Kapazität 100. „Vollpacken“ steht für blind gepackt, „Sortieren“ für hafen-bewusst gruppiert. „Billiger“ heißt kleinere Gesamtkosten im selben Szenario, Kosten sind in €. Szenarien entstehen aus festen Startwerten des Zufallsgenerators, die je Zeile genannt sind, soweit bekannt. Die Zahlen sind die Messreihen der Demo, soweit nicht als Rechnung dieser Seite gekennzeichnet.

Frage	Befund
Wo kippt der Vorteil des Sortierens? (30 Packstücke, 5 Regionen, 3 Häfen, je 10 Szenarien, Startwerte 1 bis 10)	Seefracht-Basis 800 € (1,0×): Sortieren billiger in 10 von 10 Szenarien; 1,5×: 6 von 10; 2,0×: 3 von 10; 2,5×: 2 von 10; 3,0×: 1 von 10. Der Übergang ist allmählich.
Wie viele Container braucht welcher Weg? (30 Packstücke, 5 Regionen, 3 Häfen, 5 Szenarien, Startwerte 1 bis 5)	Vollpacken 5 bis 6 Container, Sortieren 7.
Wie viel spart das Sortieren bei Basis 800 €? (30 Packstücke, 5 Regionen, 3 Häfen, 8 Szenarien, Startwerte 1 bis 8)	Billiger in 8 von 8 Szenarien, im Schnitt um ca. 750 €.
Hängt der Vorteil von der Größe ab? (6 Regionen, 3 Häfen, je 5 Szenarien, Startwerte 1 bis 5)	Das Sortieren ist gegenüber dem Vollpacken um 6,0 / 10,9 / 9,1 / 11,2 / 10,5 / 11,0 % billiger bei 20 / 40 / 60 / 100 / 150 / 200 Packstücken (Mittel der Kosten über die 5 Szenarien). Nachrechnung dieser Seite mit Startwerten 0 bis 4: von knapp vier Prozent bei 20 Packstücken bis gut zehn Prozent bei 200; fünf Szenarien streuen stark.
Wann ist der Vorsprung besonders groß?	Bei 80 Packstücken, 8 Regionen und 5 Häfen: 26 % in einem Szenario (bezogen auf die Kosten des Vollpackens), über mehrere Szenarien im Schnitt 16 bis 17 %. Zahl der Szenarien und Startwerte nennt die Quelle nicht; eine Nachrechnung dieser Seite ergab je nach Startwerten 16 bis knapp zwanzig Prozent. Mehr Häfen und mehr Packstücke verstärken den Effekt deutlich, mehr Regionen leicht.
Wann gewinnt das Vollpacken klar? (30 Packstücke, 5 Regionen, 3 Häfen, Basis 4.000 €, Startwerte 1 bis 10)	Vollpacken billiger in 9 von 10 Szenarien (mit Startwerten 0 bis 9: 10 von 10); das Sortieren ist im Mittel rund 10 % teurer als das Vollpacken (bezogen auf dessen Kosten). In einem gewählten Szenario sind es 11,6 % (10,4 %, bezogen auf die Kosten des Sortierens); die Verbesserungssuche erreicht dort 27.735 € und damit das Niveau des Vollpackens.
Hilft eine andere Packreihenfolge?	Varianten der Reihenfolge innerhalb der Gruppen (eine frühere Fassung der Suche) brachten gegenüber dem Sortieren nur 0 bis 0,4 % (20 bis 200 Packstücke). Selbst in einem harten Packregime (Größen 40 bis 60, Kapazität 100) und bei Beam-Breiten bis 1.000 blieb es bei etwa 0,5 %. Der Hebel ist die Gruppierung (rund 10 %), nicht die Reihenfolge.
Was bringt die Verbesserungssuche? (14 Szenarien, Basis 800 €)	Für eine frühere Fassung (nur Verschieben und Abspalten, 30 Packstücke) nennt die Messreihe der Demo im Schnitt 1,9 % gegenüber dem Sortieren, in Einzelfällen bis 7,1 % und in mehreren Fällen 0 %. Nachmessung dieser Seite mit der heutigen Fassung (Startwerte 1 bis 14), gegenüber dem Sortieren: bei 30 Packstücken, 5 Regionen und 3 Häfen im Schnitt gut fünf Prozent, in der Voreinstellung (40 Packstücke, 6 Regionen, 3 Häfen) knapp zwei Prozent.
Welche Startpläne braucht die Suche? (40 Fälle, volle Suche mit LNS)	Ohne den blinden Startplan wird das Ergebnis in 14 von 40 Fällen schlechter (zusammen ca. 15.800 €), ohne die alternierende Neugruppierung in 3 von 40 (ca. 478 €). Weitere Startpläne (gesamtkostenbewusste Gruppierung: 2 von 40, ca. 156 €; eine eigenständige Beam-Konstruktion: 0 von 40) brachten nach der LNS-Politur kaum noch etwas und sind entfernt. Auch die einfache Sortierung als Startplan hatte 0 von 40, gemessen vor der LNS-Politur.
Wie nah am Optimum? (kleine Fälle)	Gegen die Vollaufzählung aller Aufteilungen (3 bis 7 Packstücke, 40 Fälle) liegt keiner der drei Wege unter dem Optimum, und die Suche ist nie teurer als Vollpacken und Sortieren. Nachrechnung dieser Seite: Auf diesen Fällen erreichte die Suche in allen das Optimum. Bei 9 Packstücken (4 Regionen, 3 Häfen, 10 Szenarien, Startwerte 1 bis 10, Basis 800 €) war sie in 7 von 10 Szenarien optimal und im schlechtesten Fall knapp 6 % darüber.
Was kosten die Alternativen?	Wenige Häfen (ein Fall; Aufschlag gegenüber freier Hafenwahl bei fester Packung): 1 Hafen +45 %, 2 Häfen +19 %, ab 3 Häfen kein Unterschied. Ausgeglichene Container (40 Fälle): in 65 % der Fälle über 30 % weniger Streuung der Füllgrade, im Schnitt rund 1 % Mehrkosten, höchstens rund 3 %; erlaubt sind bis zu 5 %.

Was die Messung zeigt und wo die Grenzen liegen

Was sie belegt:

• Die Richtung des Kippens: Je teurer die Überfahrt gegenüber der Straße, desto seltener gewinnt das Sortieren. Als Mechanismus (mehr Container) sind die Containerzahlen in den geprüften Fällen belegt; allgemein folgt nur die untere Schranke aus der Herleitung.
• Die Rangfolge der Suche gegenüber den einfachen Wegen: Sie behält nur Änderungen, die die Kosten senken, und nimmt das blinde Ergebnis und die Neugruppierung der hafen-bewussten Gruppierung als Startpläne. Dadurch ist sie nie teurer als beide; geprüft ist das zusätzlich an den kleinen Fällen mit bekanntem Optimum.
• Das Beispiel mit den drei Packstücken ist eine Rechnung, keine Messung.

Was sie nicht belegt:

• Stichprobe: Jede Stufe der Kipptabelle beruht auf 10 Szenarien. Ein Wert wie 6 von 10 gehört zu einem üblichen Konfidenzbereich für den wahren Anteil (Clopper-Pearson, zweiseitig, fünf Prozent Irrtumswahrscheinlichkeit), der etwa von gut einem Viertel bis knapp neun Zehnteln reicht (Rechnung dieser Seite).
• Lage des Kipppunkts: Sie gilt für die Bauart der Tabelle. In der Voreinstellung (40 Packstücke, 6 Regionen, 3 Häfen) gewinnt das Sortieren nach einer Nachrechnung dieser Seite an zehn Szenarien beim Dreifachen der Seefracht noch in sechs und beim Fünffachen in fünf. Die Demo verortet den Umschlag am Regler der Seefracht dagegen grob zwischen dem Eineinhalbfachen und dem Zweieinhalbfachen der Voreinstellung; das trifft nur die Bauart der Tabelle.
• Prozentbasis und Streuung: Die Vorsprünge des Sortierens sind relativ zum Vollpacken gerechnet, die Aussagen zur Suche relativ zum Sortieren, soweit nicht anders angegeben; die Einzelangabe 10,4 % bezieht sich auf die Kosten des Sortierens. Für die Prozentangaben gibt es keine Streuungsmaße. Die Messreihe der Demo fasst den Vorsprung als „rund 9 bis 11 %“ zusammen, doch bei 20 Packstücken liegt der Wert bei 6,0 %. Die Schwankung der Größenreihe (6,0, 10,9, 9,1, 11,2 …) ist bei je fünf Szenarien als Rauschen zu lesen.
• Heuristiken: Kein Optimalitätsbeweis, und ein exakter Löser (gemischt-ganzzahliges Programm) für mittlere Größen fehlt; der Abstand zum Optimum bei 40 Packstücken ist offen. Der Abstand zum Optimum ist nur für kleine Fälle nachgewiesen. Bei 9 Packstücken war er schon nicht mehr in allen Szenarien null (Rechnung dieser Seite).
• Modellgrenzen: Packen ist ein 1D-Volumen (keine Gewichtsgrenzen, kein Gefahrgut, keine räumliche Packung). Die Straßenkosten sind eine Matrix Region mal Hafen, keine Tourenplanung ab Hafen; sie sind linear in Größe und Entfernung. Die Seefracht ist je Container fest, ohne Mengenrabatt und ohne Abhängigkeit vom Inhalt. Es gibt keine Abfahrtstermine, Zeitfenster oder mehrere Zielorte je Packstück.
• Beam-Breite: Sie ist fest auf 1 gesetzt, weil die Breiten 1 bis 6 im Mittel nur rund 13 € brachten und bei 100 Packstücken 653 statt 382 ms kosteten. Dass eine größere Breite nie schadet (Monotonie), gilt für die Suche nicht streng: In etwa 10 % der Fälle war ein Ergebnis bei größerer Breite um weniger als 0,5 % schlechter. Eine Breite über 1 lässt sich in der Demo nicht einstellen.

Erweiterungen und Verweise

Verwandte Demos dieser Website und Anpassungsideen:

• Räumliche Packung im Container: Die 3D-Packungsoptimierung zeigt die räumliche Packung; hier ist ein Container nur ein Volumen.
• Lkw-Strecke ab Hafen: Statt einer Kostenmatrix käme eine echte Tourenplanung als letzte Meile in Frage. Das ist hier nicht umgesetzt; das Routenproblem für sich zeigt die Tourenplanung.
• Weitere Nebenbedingungen: Gewichtsgrenzen, Gefahrgut je Hafen und feste Abfahrtstermine je Hafen sind als Anpassungsideen vorgemerkt, aber nicht gebaut.

Quellen

• Jost, Henke, Hedtke, Bredtmann, Weise, Buchheim, Clausen (2022): Partitioned vs. Integrated Planning of Hinterland Networks for LCL Transportation (TU Dortmund mit DB Schenker). arXiv 2211.10345. Dass eine integrierte Planung Vorteile hat, aber mehr Rechenaufwand braucht, steht im Abstract. Die Spanne von etwa 1 bis 7 % in den Testinstanzen nennt nur die Dokumentation der Demo; sie ist an der Arbeit nicht geprüft.
• Garey, Johnson (1979): Computers and Intractability. W. H. Freeman (NP-Schwere des Bin-Packing).
• Dósa (2007): The tight bound of First Fit Decreasing bin-packing algorithm is FFD(I) ≤ 11/9 OPT(I) + 6/9. In: Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, Springer.
• Quelltext, Messreihen und Prüfungen der Demo: github.com/sebastian-hanisch/freight_demo.

Von Jost et al. wurde nur das Abstract gelesen, die übrigen Arbeiten wurden für diese Seite nicht vollständig nachgeschlagen; die Angaben stammen aus der Dokumentation der Demo und aus dem Gedächtnis. Die Befundtabelle gibt die Messreihen der Demo wieder; Herleitungen, Beispiel und Nachmessungen sind Rechnungen dieser Seite.