Die Containerstauung verständlich erklärt

Ein Umzugswagen ist voll, und vor der Tür stehen noch Kisten. Wie man packt, entscheidet, wie viele mitkommen. Die Seite vergleicht drei Packregeln, zeigt, wo klügeres Packen viel bringt und wo wenig, und nennt einen Fehler, der schöne Zahlen vortäuscht.

Zuletzt aktualisiert: 11. November 2026

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

Kisten in einen Laderaum bekommen

Stellen Sie sich einen Umzug vor. Vor dem Transporter stehen Kisten in vielen Größen. Ist viel Platz übrig, gelingt das Packen leicht. Wird es eng, entscheidet die Packweise, wie viele Kisten mitkommen.

Im Großen ist es genauso. Ein Container oder eine Palette soll möglichst voll werden, denn jeder zusätzliche Container kostet Geld. Fachleute nennen das Beladen Stauung, nicht zu verwechseln mit einem Verkehrsstau. Uns interessiert, welchen Anteil des Laderaums die Kisten füllen. Das heißt Raumnutzung.

Dafür schreibt man eine feste Vorgehensweise auf, eine Packregel (Fachwort: Heuristik). Sie liefert schnell einen brauchbaren Plan. Ob er der bestmögliche ist, sagt sie nicht.

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. Alles hier beschreibt ein vereinfachtes Rechenbild, also eine Nachbildung am Computer: zufällig erzeugte Quader als Kisten, ein einziger Laderaum, kein Gewicht.

Drei Packregeln im Vergleich

Die Demo vergleicht drei Regeln. Alle packen eine Kiste nach der anderen. Jede Kiste kommt an die niedrigste Stelle, die noch frei ist, also auf den Boden oder auf andere Kisten. Gibt es mehrere gleich niedrige Stellen, nimmt sie die weiter hinten im Laderaum. Bleibt auch dann ein Gleichstand, gilt die weiter links. Die Regeln unterscheiden sich in der Reihenfolge, im Drehen der Kisten und in der Zahl der Pläne, die sie verfolgen. Ein Plan ist ein teilweise gepackter Laderaum auf dem Papier.

• Schichtenregel: Die höchsten Kisten kommen zuerst. Keine Kiste wird gedreht. Es gibt einen Plan.
• Eckenregel: Die Kisten mit dem größten Rauminhalt kommen zuerst. Sie merkt sich die freien Ecken zwischen den schon stehenden Kisten und probiert jede davon. Jede Kiste darf in jeder der sechs Lagen stehen, auch auf der Seite oder auf dem Kopf. Es gibt einen Plan.
• Mehrplanregel: Reihenfolge und Lagen wie bei der Eckenregel. Sie führt mehrere Pläne nebeneinander, alle mit denselben Kisten, aber mit unterschiedlichen Entscheidungen. Am Ende nimmt sie den Plan mit dem größten Rauminhalt. Voreingestellt sind sechs Pläne.

In der Demo heißen die zweite und die dritte Regel Extreme-Point und Beam Search. Warum kommen die sperrigen Kisten zuerst? Es ist die übliche Faustregel, wie beim Kofferpacken: Große Stücke lassen sich später schwer unterbringen, und kleine füllen am Ende die Lücken. Die Schichtenregel richtet sich dabei nach der Höhe, die Eckenregel nach dem Rauminhalt. Die Demo hat nicht gemessen, ob eine andere Reihenfolge besser wäre.

Was die Messung zeigt

Die Demo hat vier Beispielfälle zum Anklicken, jeweils mit zufällig erzeugten Kisten. Die Zahlen in diesem Teil gelten nur für diese Fälle. Die Raumnutzung steht als Prozentzahl da. Ein Prozentpunkt ist ein Schritt auf dieser Skala, etwa von 50 auf 51.

So weit lagen Eckenregel und Mehrplanregel in den vier Fällen auseinander:

• Ähnlich große Kartons: kein Unterschied.
• Gemischte Ladung: weniger als ein Prozentpunkt.
• Viele kleine Pakete: weniger als ein Prozentpunkt.
• Enges Puzzle: knapp fünf Prozentpunkte zugunsten der Mehrplanregel.

Im vierten Fall passt nur ein Teil der Kisten hinein, und die Größen sind sehr gemischt. Der Autor der Demo hat ihn gezielt ausgesucht: Er prüfte rund 300 Zufallsfälle und nahm einen, in dem die Mehrplanregel gut abschneidet. Nur in einem kleinen Teil davon lag sie mehr als einen Prozentpunkt vorn. Der vierte Fall ist also ein besonders günstiger, kein typischer. Verfolgte die Mehrplanregel dort sechzehn statt sechs Pläne, lag sie gut zehn Prozentpunkte vor der Eckenregel.

Warum bringen mehr Pläne meist wenig? Der Autor der Demo erklärt es so: Meist gibt es für die nächste Kiste eine klar beste Stelle. Dann folgen alle Pläne derselben Idee, und es ändert sich nichts. Mehr Pläne helfen nur, wenn eine Kiste mehrere gleich gute Möglichkeiten hat, etwa dieselbe Stelle in verschiedenen Lagen. Die Eckenregel nimmt die zuerst gefundene. Die Mehrplanregel probiert mehrere aus und behält am Ende die beste.

Eine Garantie gibt es, wenn die Kistenreihenfolge gleich bleibt. Verfolgt die Mehrplanregel mehr Pläne, wird ihr Ergebnis nie schlechter. Mit einem einzigen Plan ist sie die Eckenregel. Also bleibt sie nie hinter der Eckenregel zurück. Dafür rechnet sie länger.

Das war nicht selbstverständlich: Eine frühere Fassung wurde bei 11 von 14 Testfällen schlechter, wenn man mehr Pläne erlaubte.

Die Schichtenregel füllte in sieben getesteten Beispielen weniger Laderaum als die beiden anderen. Die Beispiele hatten je 25 Kisten mit Kantenlängen von 15 bis 55 Zentimetern. Der Abstand lag zwischen 10 und 28 Prozentpunkten. Bei kürzeren Kisten war er größer, er hängt also vom Beispiel ab. Warum, hat die Demo nicht einzeln geprüft. Drei Unterschiede kommen infrage: Sie dreht nicht, sie ordnet nach Höhe statt nach Rauminhalt, und sie probiert weniger Stellen.

Die Falle: Kisten, die in der Luft schweben

Ein Packplan kann gut aussehen und trotzdem unmöglich sein. Die erste Fassung der Demo prüfte nur, ob sich Kisten überlappen und ob sie im Laderaum liegen. Ob etwas darunter steht, prüfte sie nicht.

So konnte eine große Kiste auf einer kleinen liegen und mit einem Teil in der Luft hängen. In einem Testfall mit 25 Kisten standen bei der Eckenregel sechs von 15 eingeräumten Kisten nicht vollständig auf einer Unterlage. Eine hatte gar keinen Halt.

Nach dem Einbau der Prüfung schwebte keine Kiste mehr. Dafür sank die Raumnutzung: In einem früheren Beispielfall fiel sie bei der Eckenregel um gut acht Prozentpunkte. Die schönen Zahlen davor kamen also zum Teil von unmöglichen Packungen.

Häufige Missverständnisse

• „Hohe Raumnutzung heißt: gut gepackt.“ Nicht, wenn alle Kisten hineinpassen. Dann zeigt die Zahl nur, wie viel Kistenvolumen es gab. In einem früheren Beispielfall mit sehr kleinen Kisten passten alle hinein, und alle drei Regeln zeigten dieselbe Raumnutzung. Erst wenn Kisten übrig bleiben, sagt die Zahl etwas über das Packen.
• „Mehr Kisten im Laderaum heißt mehr gefüllter Raum.“ Viele kleine und wenige große Kisten können gleich viel Raum füllen. Die Demo zählt deshalb den Rauminhalt, nicht die Kistenzahl.
• „Wenn eine Kiste nicht mehr passt, ist der Laderaum voll.“ Nicht unbedingt. Eine schon stehende Kiste kann den Platz so verbauen, dass die übrige Lücke zu schmal wirkt. In einem Beispielfall brachte das Umsetzen einer eingeräumten Kiste eine weitere Kiste unter. Die Raumnutzung stieg um knapp zwei Prozentpunkte.

Woran Sie das im Alltag erkennen

• In der Spülmaschine passt eine Schale erst, wenn Sie sie drehen.
• Ein Stapel steht schief, weil eine breite Kiste nur auf einem Rand einer schmalen liegt.

Wie ernst ist das Rechenbild zu nehmen?

Es zeigt, wie sich drei Regeln auf zufälligen Kisten zueinander verhalten. Es kennt weder Gewicht noch Stapelgrenzen noch die Angabe „diese Seite nach oben“. Wie viel ein echter Laderaum bringt, sagt es nicht.

Was Sie mitnehmen

• Prüfen Sie, ob ein Plan überhaupt stehen kann, bevor Sie seiner Zahl trauen.
• Fragen Sie bei einem aufwendigen Verfahren, was es gegenüber dem einfachen bringt.
• Bleibt eine Kiste übrig, fragen Sie, ob ein Umsetzen noch hilft.

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. Betrachtet wird die Beladung eines einzelnen quaderförmigen Containers (oder einer Palette mit Aufbau) mit quaderförmigen Kisten, deren Kanten parallel zu den Containerkanten liegen. Gesucht sind eine Teilmenge der Kisten sowie Lage und Ort jeder gewählten Kiste, sodass das untergebrachte Volumen maximal wird. Gewicht, Stapelgrenzen und Ausrichtungsvorgaben fehlen. Ein zweiter Container wird nicht befüllt.

• Container: Länge \(L\), Breite \(W\), Höhe \(H\) in cm; Voreinstellung 120 × 80 × 100, angelehnt an eine Euro-Palette mit Aufbau.
• Kisten: \(i = 1, \dots, n\) mit Kantenlängen \((l_i, w_i, h_i)\), Die Demo erzeugt sie zufällig: jede Kante gleichverteilt zwischen einer unteren und einer oberen Grenze, auf eine Nachkommastelle gerundet, bei festem Zufallsstart (Seed) reproduzierbar; der Regler erlaubt höchstens 60 Kisten, in der Kistentabelle lassen sich Kisten von Hand hinzufügen und ändern.
• Zulässig ist eine Stelle, wenn die Kiste ganz im Container liegt, keine platzierte Kiste überlappt und die Kiste gestützt ist: Entweder steht sie auf dem Boden, oder ihre gesamte Grundfläche liegt lückenlos auf den Oberseiten platzierter Kisten, die genau auf Höhe ihrer Unterseite enden. Mehrere Kisten dürfen gemeinsam stützen. Die Prüfung rechnet exakt über Koordinatenkompression, nicht über ein Stichprobenraster.
• Lagen: \(R(i)\) ist die Menge der zulässigen Lagen der Kiste \(i\). Die Schichtenregel dreht nicht (\(|R(i)| = 1\)). Eckenregel und Mehrplanregel probieren alle bis zu sechs achsparallelen Lagen (Vertauschungen der Kantenlängen, doppelte bei gleichen Kanten entfernt).
• Raumnutzung: \(u = 100 \cdot \sum_{i \in S} l_i w_i h_i \,/\, (L\,W\,H)\) in Prozent, mit der Menge \(S\) der untergebrachten Kisten. Das Volumen einer Kiste ändert sich beim Drehen nicht.
• Zusatzcontainer: Das Volumen \(V_{\mathrm{rest}}\) der nicht untergebrachten Kisten wird durch das Containervolumen \(V\) geteilt und aufgerundet: \(\lceil V_{\mathrm{rest}} / V \rceil\), bei übrig gebliebenen Kisten mindestens 1. Multipliziert mit einem einstellbaren Kostensatz je Zusatzcontainer ergibt das die Kostenschätzung. Sie geht von einer lückenlosen Füllung aus und ist daher eine untere Schätzung nach Volumen, die bei Raumnutzungen weit unter 100 % zu niedrig liegen kann. Sie stellt keinen Packplan für die Zusatzcontainer auf.

Die drei Packregeln

Alle drei Regeln sind gierige Konstruktionsverfahren ohne Rückwärtssuche: Sie legen Kiste für Kiste fest. Gemeinsam ist die Stellenwahl. Unter den zulässigen Stellen gewinnt die mit kleinstem \(z\), bei Gleichstand mit kleinstem \(y\), dann mit kleinstem \(x\) (lexikografisch, „tief, hinten, links“).

• Schichtenregel: Reihenfolge nach Höhe absteigend, keine Drehung. Kandidatenstellen sind alle Paare aus den \(x\)-Werten und \(y\)-Werten, die als Anfangs- oder Endkante platzierter Kisten vorkommen (anfangs nur 0; nach einer Kiste kommen \(x + l\) und \(y + w\) hinzu). Zu jedem Paar wird die Kiste auf die höchste Oberseite unter ihrem Grundriss gesetzt; die Stelle gilt nur im Container und bei lückenloser Stützung. Passt keine Stelle, bleibt die Kiste draußen, und der Zustand ändert sich nicht. Der Name erinnert an eine frühere Fassung mit festen Schichthöhen; die heutige Fassung kennt keine festen Schichten.
• Eckenregel (Extreme-Point): Reihenfolge nach Volumen absteigend. Es gibt eine Punktmenge, anfangs nur den Ursprung. Je Kiste werden alle Punkte und alle Lagen durchprobiert; gewählt wird die zulässige Stelle mit kleinstem \((z, y, x)\), bei Gleichstand die zuerst gefundene (Punkte außen, Lagen innen). Der belegte Punkt \((x, y, z)\) entfällt, und es kommen drei neue Punkte hinzu, jeweils um eine Kantenlänge der Kiste versetzt: \((x + l, y, z)\), \((x, y + w, z)\) und \((x, y, z + h)\), wobei \((l, w, h)\) die Kantenlängen in der gewählten Lage sind. Die Demo beruft sich auf Crainic, Perboli und Tadei (2008). Ob die Punktregel der Demo mit der der Originalarbeit übereinstimmt, hat diese Seite nicht geprüft.
• Mehrplanregel (Beam Search, monobeam): Reihenfolge wie bei der Eckenregel. Die Breite \(B\) (Voreinstellung 6) ist die Zahl der Plätze, die je Ebene gefüllt werden; eine Ebene entspricht einer Kiste. Die Plätze werden nacheinander bedient: Platz \(c\) erzeugt alle zulässigen Fortsetzungen des Plans, der in der vorherigen Ebene auf Platz \(c\) steht, legt sie in einen gemeinsamen Pool und erhält sofort die beste Fortsetzung des Pools, bevor Platz \(c + 1\) drankommt. Bewertet wird nur die zuletzt gewählte Stelle wie bei der Eckenregel mit \((z, y, x)\), bei Gleichstand gewinnt die zuerst erzeugte Fortsetzung; die Güte des ganzen Plans geht nicht ein. Das ist Absicht: So stimmt die Breite 1 mit der Eckenregel überein. Passt eine Kiste in keine Fortsetzung eines Plans, wird sie in diesem Plan als nicht untergebracht geführt und mit der schlechtesten Bewertung in den Pool gelegt. Erst am Ende gewinnt der Plan mit dem größten untergebrachten Volumen, bei Gleichstand der mit der kleinsten Gesamthöhe (höchste Oberkante aller Kisten des Plans). Das Verfahren folgt Lemons, Linares López, Holte und Ruml (2022).

Die Formeln

Es sei \(S\) die Menge der untergebrachten Kisten, \(r_i\) die gewählte Lage der Kiste \(i\) (eine Vertauschung ihrer Kantenlängen; bei der Schichtenregel nur die gegebene Lage), \(l_i^{r_i}, w_i^{r_i}, h_i^{r_i}\) die Kantenlängen in dieser Lage und \((x_i, y_i, z_i) \ge 0\) die Ecke der Kiste mit den kleinsten Koordinaten. Das Problem lautet:

\[\max_{S,\,r,\,x,y,z} \; \sum_{i \in S} l_i^{r_i}\, w_i^{r_i}\, h_i^{r_i}\]

unter den Bedingungen: jede Kiste liegt ganz im Container, keine zwei Kisten überlappen, und jede Kiste steht auf dem Boden (\(z_i = 0\)) oder liegt mit ihrer ganzen Grundfläche auf Oberseiten, die auf Höhe \(z_i\) enden. Weil das Volumen unter Drehung gleich bleibt, hängt der Zielwert nur von \(S\) ab.

Als gemischt-ganzzahliges Programm schreibt man es nach Chen, Lee und Shen mit Auswahlvariablen \(s_i \in \{0, 1\}\), Lagevariablen \(\rho_{ik} \in \{0, 1\}\) für die Lagen \(k \in R(i)\) und sechs Trennvariablen \(\sigma_{ij}\) je Kistenpaar \(i < j\) (eine je Richtung \(\pm x, \pm y, \pm z\)). Zielfunktion \(\max \sum_i s_i\, l_i w_i h_i\) unter \(\sum_{k \in R(i)} \rho_{ik} = s_i\) und \(\sum \sigma_{ij} \ge s_i + s_j - 1\); jede Trennrichtung erzwingt über eine große Konstante \(M\) etwa \(x_i + \sum_k \rho_{ik}\, l_i^k \le x_j + M\,(1 - \sigma_{ij}^{+x})\). Die Stützungsbedingung ist darin nicht enthalten; das Programm beschreibt also das klassische Problem ohne Stützung, nicht ganz das Problem der Regeln oben. Die Demo löst es nicht; es dient nur der Einordnung.

Schwierigkeit: Mit Kisten der Kantenlängen \((l_i, 1, 1)\) und einem Container \((L, 1, 1)\) bleibt die Wahl einer Teilmenge mit \(\sum_{i \in S} l_i \le L\) und größtmöglicher Summe \(\sum_{i \in S} l_i\). Das ist das Teilsummenproblem, ein Spezialfall des 0/1-Rucksackproblems (Karp; Garey und Johnson). Es ist schwach NP-schwer und bei ganzzahligen Längen per Dynamischer Programmierung in \(O(nL)\) lösbar. Da der Spezialfall bereits NP-schwer ist, ist es auch die allgemeine Packung mit Drehung und Stützung (Argument der Demo). Die Reduktion zeigt nur schwache NP-Schwere; ob die Packung stark NP-schwer ist, wird hier nicht behauptet. Die Demo nennt für die drei Regeln keine Gütegarantie gegen das Optimum; ob es für diese Varianten eine gibt, hat diese Seite nicht geprüft.

Warum die Mehrplanregel nie schlechter wird

Dieser Abschnitt ist eine Rechnung dieser Seite aus dem Aufbau der Mehrplanregel, keine Messung der Demo. Es seien \(b_1 \le b_2\) zwei Breiten.

• Schritt 1: Auf jeder Ebene wird Platz \(c\) aus dem Pool bedient, in den bis dahin nur die Fortsetzungen der Plätze \(1, \dots, c\) der vorherigen Ebene geflossen sind. Platz \(c\) hängt also nur von diesen Plätzen ab, nicht von der Breite.
• Schritt 2: Durch Induktion über die Ebenen stimmen die ersten \(b_1\) Plätze des Laufs mit Breite \(b_2\) auf jeder Ebene mit dem Lauf der Breite \(b_1\) überein.
• Schritt 3: Die Endauswahl nimmt das größte untergebrachte Volumen über alle Plätze, beim breiteren Lauf also über eine Obermenge. Daraus folgt:

\[\mathrm{vol}\big(\mathrm{monobeam}(b_1)\big) \;\leq\; \mathrm{vol}\big(\mathrm{monobeam}(b_2)\big)\]

Voraussetzungen sind die gleiche Kistenreihenfolge und eine Bewertung der Fortsetzungen, die nicht von der Breite abhängt. Die Aussage gilt für das untergebrachte Volumen der Konstruktion, nicht für die Kistenzahl und nicht für das Ergebnis nach der Umsetzsuche (unten), die je Regel getrennt ansetzt. Bei \(b_1 = 1\) wählt das Verfahren mit derselben Bewertung und derselben Gleichstandsregel wie die Eckenregel; die Prüfungen der Demo fanden dabei in den untersuchten Fällen identische Packungen. Also erreicht die Mehrplanregel bei jeder Breite mindestens das Volumen der Eckenregel, solange Bewertung und Gleichstandsregel beider übereinstimmen; ändert man eine davon, entfällt diese Folgerung, die Monotonie in der Breite bleibt. Eine Gütegarantie gegen das Optimum folgt daraus nicht. Für das Ergebnis nach der Umsetzsuche ist „nie schlechter“ nicht gezeigt.

Befunde

Alle Werte sind Raumnutzung in Prozent des Containervolumens, vor der Umsetzsuche, und Einzelwerte je eines Zufallsfalls, wo nichts anderes steht. Stichproben-Angaben, die nur in der Dokumentation der Demo stehen, sind mit „laut Dokumentation“ markiert und nicht nachgerechnet.

Frage	Befund
Wie weit liegen Eckenregel und Mehrplanregel (Breite 6) in vier Beispielfällen auseinander? (Container 120 × 80 × 100 cm, im dritten Fall 70 × 60 × 50 cm)	Je Fall Eckenregel / Mehrplanregel. (1) 20 Kisten, Kantenlängen 25 bis 35 cm, Zufallsstart 1: 50,3 % / 50,3 %. (2) 30 Kisten, 10 bis 60 cm, Start 7: 81,4 % / 81,6 %. (3) 60 Kisten, 8 bis 25 cm, Start 1, Kistenvolumen zusammen 131 % des Containers: 70,9 % / 71,1 %. (4) 30 Kisten, 8 bis 70 cm, Start 10: 71,6 % / 76,2 %.
Wie kam der vierte Fall zustande?	Er wurde gezielt gesucht. Laut Dokumentation fand eine Suche über rund 300 Konfigurationen (Kistenzahl, Größenbereich, Zufallsstart) in 41 davon mehr als einen Prozentpunkt Vorsprung der Mehrplanregel. Fall (4) ist ein ausgewählter Fall, kein Mittel.
Wie wirkt die Breite im vierten Fall?	Breite 1: 71,6 % (gleich der Eckenregel), Breite 6: 76,2 %, Breite 16: 81,7 %.
Wie weit liegt die Schichtenregel zurück?	Laut Dokumentation erreicht sie in sieben getesteten Fällen mit je 25 Kisten 44 bis 62 %, das sind 10 bis 27 Prozentpunkte unter Eckenregel und Mehrplanregel. Eine Nachrechnung dieser Seite mit Kantenlängen von 15 bis 55 cm und den Zufallsstarts 1 bis 7 bestätigt das (größter Abstand knapp 28). Mit Kantenlängen von 10 bis 50 cm liegen dieselben Zufallsstarts nach der Nachrechnung weiter zurück, bis knapp 30 Prozentpunkte. Der Rückstand hängt also vom Kantenbereich ab.
Ist die Mehrplanregel nie schlechter als die Eckenregel?	Laut Dokumentation in 30 Testfällen (Aufbau der Stichprobe nicht beschrieben): 5 besser, 0 schlechter, 25 gleich. Die Prüfungen der Demo verlangen es außerdem für zehn Zufallsstarts mit je 25 Kisten (8 bis 60 cm) und die Breiten 2, 4 und 8. Breite 1 stimmt in fünf Zufallsstarts (25 Kisten, 10 bis 60 cm) und in 20 kleinen Zufallsinstanzen Platz für Platz mit der Eckenregel überein. Eine Nachrechnung dieser Seite mit 30 Zufallsstarts (15 bis 40 Kisten, 8 bis 70 cm) ergibt 8 besser, keinen schlechter, die übrigen gleich.
Wird mehr Breite nie schlechter?	Laut Dokumentation wurde eine frühere Fassung in 11 von 14 Testfällen mit wachsender Breite (1, 2, 4, 6, 8, 12, 16) schlechter. Die heutige Fassung zeigte laut Dokumentation in 0 von 30 Fällen eine Verletzung; die Prüfungen der Demo verlangen die Monotonie für 14 Zufallsstarts und diese Breiten.
Schweben Kisten?	Vor der Stützungsprüfung waren in einem Fall (25 Kisten, Container 120 × 80 × 100 cm) bei der Eckenregel 6 von 15 eingeräumten Kisten (40 %) nicht vollständig gestützt, eine davon ohne jede Stützung; die anderen Regeln zeigten dasselbe Bild. Mit der Prüfung: 0 schwebende Kisten bei allen drei Regeln in den vier Beispielfällen. Folge: In einem früheren Beispiel (25 Kisten, 8 bis 70 cm, Start 11) sank die Raumnutzung der Eckenregel von 80,1 % auf 71,8 %.
Was bringt die Umsetzsuche?	Sie probiert für jede nicht untergebrachte Kiste, eine eingeräumte Kiste probeweise zu entfernen, und übernimmt den Tausch, wenn beide Kisten danach stehen (erster Erfolg zählt). Im Fall (3) stellt sie eine weitere Kiste unter, die Raumnutzung der Eckenregel steigt von 70,9 % auf 72,7 %. Im Fall (4) findet sie keine. Bei 60 Kisten dauert ein Lauf laut Dokumentation etwa 3,6 s (Container und Rechner nicht genannt).
Was kostet die Mehrplanregel an Rechenzeit?	Laut Dokumentation bei 60 Kisten in einem Container 300 × 300 × 300 cm etwa 1,45 s, rund das 11-Fache der Eckenregel (Rechner nicht genannt).
Schlägt eine andere Bewertung die Stellenwahl „tief, hinten, links“?	Die Kontaktfläche einer Kiste ist die Fläche, mit der sie an Boden, Rückwand, linker Wand oder anderen Kisten anliegt. Vier Bewertungen damit (allein, als Zweitkriterium, als Erstkriterium, gewichtet mit der Höhe) schlugen die Standardwahl laut Dokumentation nicht belastbar, bei 28 bis 135 Testfällen. Allein: 15 gegen 11 Siege für die Standardwahl. Die gewichtete Kombination zeigte auf 56 Fällen +0,51 Prozentpunkte (Variante minus Standardwahl), auf 135 Fällen dagegen minus 0,2 bis minus 0,3; der Vorteil verschwand also bei größerer Stichprobe.
Sind die Packungen zulässig?	Ein unabhängiger Prüfer (Belegungsraster in Zehntel-Zentimetern) und eine Vollaufzählung auf Mini-Instanzen (Container 3 × 3 × 3 oder 4 × 3 × 3, höchstens vier Kisten mit ganzzahligen Kanten, Stützung im Endzustand) bestätigten: Alle drei Regeln liefern zulässige Packungen und nie mehr Volumen als das Optimum der Aufzählung. Dabei fanden sich zwei Fehler, beide behoben: Die Umsetzsuche konnte Kisten in der Luft zurücklassen, und die Zusatzcontainer-Schätzung rundete ein exakt ganzzahliges Verhältnis wegen Gleitkommarauschen auf.

Was die Messung zeigt und wo ihre Grenzen liegen

Das zeigt die Messung:

• Die Eckenregel liegt in den geprüften Fällen vor der Schichtenregel (Abstand siehe Tabelle); die Prüfungen verlangen für sieben Zufallsstarts mit je 25 Kisten mindestens Gleichstand.
• Dass die Mehrplanregel bei gleicher Kistenreihenfolge nicht hinter die Eckenregel fällt, folgt aus dem Aufbau (siehe oben) und wurde an Stichproben bestätigt.
• Die Packungen sind zulässig: Überlappung, Containergrenzen und Stützung stimmen mit einem unabhängigen Rechenweg überein, und die Regeln liegen auf den geprüften Mini-Instanzen nie über dem Optimum der Aufzählung.

Das zeigt sie nicht:

• Einzelfälle: Die Tabelle nennt Einzelwerte je eines Zufallsfalls, ohne Mittel und Streuung; mehrere Fälle belegen nur die Aussagen zur Schichtenregel, zur Monotonie und zur Zulässigkeit. Mittel über viele Instanzen mit festen Generatorgrenzen und der Vergleich mit einem Standardverfahren fehlen. Die Werte der Beispielfälle (1) bis (4) hat diese Seite mit dem Quelltext der Demo nachgerechnet; sie stimmen mit der Tabelle überein.
• Ausgewählter Fall: Der Vorsprung im vierten Fall ist ein Suchergebnis. In drei der vier Beispielfälle liegt der Vorsprung unter einem Prozentpunkt, und in den Testfällen war die Mehrplanregel nur teilweise überhaupt besser.
• Kein Abstand zum Optimum: Ein exakter Löser oder eine Schranke fehlt. Wie weit die Regeln bei realistischer Größe vom besten Plan entfernt sind, wurde nicht gemessen.
• Volumen, nicht Kistenzahl: Die Mehrplanregel kann weniger Kisten unterbringen, wenn sie mehr Volumen unterbringt. In einer Nachrechnung dieser Seite stellt sie im vierten Fall eine Kiste weniger ein als die Eckenregel und erreicht trotzdem mehr Volumen.
• Ursache des Rückstands offen: Warum die Schichtenregel zurückliegt, ist nicht einzeln gemessen. Nicht gedreht, nach Höhe statt Volumen sortiert und weniger Kandidatenstellen sind drei gleichzeitige Unterschiede.
• Rechenzeit: Die Zeiten hängen vom Rechner ab. Eine Nachrechnung dieser Seite fand ein kleineres Verhältnis zwischen Mehrplanregel und Eckenregel als das 11-Fache, aber ebenfalls ein Vielfaches.
• Nicht abgebildet: Gewichtsgrenzen, Stapelbarkeit, „diese Seite oben“ (beliebige Drehung bei zwei der drei Regeln), mehrere Container gleichzeitig. Die Kostenschätzung ist volumenbasiert und eine Größenordnung, kein Plan.

Naheliegende Erweiterungen, nicht gebaut: Gewichtsbedingungen (schwere Kisten unten, Tragfähigkeit), eingeschränkte Drehung, mehrere Container oder Paletten gleichzeitig, ein exakter Löser als Vergleich.

Quellen

• Crainic, Perboli, Tadei (2008): Extreme Point-Based Heuristics for Three-Dimensional Bin Packing. INFORMS Journal on Computing.
• Lemons, Linares López, Holte, Ruml (2022): Beam Search: Faster and Monotonic. ICAPS 2022.
• Chen, Lee, Shen: An analytical model for the container loading problem. European Journal of Operational Research.
• Karp sowie Garey, Johnson zur NP-Schwere des Rucksackproblems.
• Quelltext, Messreihen und Prüfungen der Demo: github.com/sebastian-hanisch/pack_demo.

Titel, Jahre und Autoren stehen in der Dokumentation der Demo. Die Namen der Zeitschriften sind aus dem Gedächtnis ergänzt und nicht nachgeschlagen; Jahre und Stichprobengrößen stammen nur aus der Dokumentation der Demo. Die Rechnungen dieser Seite sind keine Messungen der Demo.