Packen: Reihenfolge und Platzierungsregel erklärt
Stellen Sie sich vor: In einer Lagerhalle liegen zwölf Pakete verschiedener Größe, und alle sollen in gleich große Container. Wer sie in Lieferreihenfolge jeweils in den ersten Container mit freiem Platz setzt, braucht im ersten Beispiel der Linie 7 Container. Wer die größten Pakete zuerst einsetzt, kommt mit 5 aus. Woran liegt das, und woher weiß man, ob 5 schon das Beste ist?
Das ist ein Packproblem: Teile sollen in möglichst wenige Behälter. Eine Packung entsteht aus zwei Dingen, einer Reihenfolge der Teile und einer Regel, wohin das nächste kommt. Dazu kommt die Schranke: eine Mindestzahl an Containern, die jede Packung braucht. Erreicht eine Packung diese Zahl, ist sie bewiesen die beste. Die Leitfrage dieser Linie lautet: Was entscheidet stärker, die Reihenfolge oder die Regel, und woran erkennt man, wie nah eine einfache Regel am Besten liegt?
Vierzehn Stücke gehen dem nach,. Zuerst eindimensionale Pakete, bei denen nur die Länge zählt: Sie handeln von der Reihenfolge, von immer schärferen Rechnungen, wie wenige Container überhaupt reichen könnten, von gezielt gebauten Paketmengen, an denen die einfache Regel schlecht packt, und von Behältern mit zwei Grenzen, Volumen und Gewicht. Dann Rechtecke auf einer Palette: einmal in waagerechten Reihen, einmal so, dass man die freie Fläche selbst verwaltet. Zuletzt Quader im Container, die nur stehen dürfen, wo genug Fläche unter ihnen liegt, und deren Schwerpunkt im erlaubten Bereich bleiben soll. Drei Stücke sind optional, das letzte stellt die Verfahren nebeneinander. Die Erklärseiten zum Sortieren und Einsetzen, zur Untergrenze und zu Stützfläche und Schwerpunkt erzählen das Lagerproblem zuerst im Alltagsbild. Eine Fall-Demo lässt einen Container oder eine Palette in 3D beladen: Packungsoptimierung.
Was diese Linie ist und was nicht: Es sind Rechenversuche mit gewählten Annahmen. Alle Befunde stammen von erfundenen Paketgrößen und sagen nichts über echte Lagerdaten. Bei Rechtecken und Quadern sagt die Mindestzahl oft wenig darüber, ob eine Packung schon die beste ist. Dort vergleicht die Linie vor allem die Verfahren untereinander.
In short: Covers bin packing as an order of items plus a placement rule: sorting, lower bounds, where first fit decreasing fails, LP bounds, shelf, skyline and extreme point methods, support and balance, and choosing a method.
Hintergrund zum Thema: Packen und Zuschnitt.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
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.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Sortieren und Einsetzen verständlich erklärt
Warum beim Packen in gleich große Container die Reihenfolge der Pakete mehr verändert als der Wechsel zwischen den beiden besseren Regeln, und wo „größte zuerst“ an Grenzen stößt: erst für Einsteiger ohne Formeln, dann für Fachleute mit Schranken und Messwerten.
Die Untergrenze beim Packen verständlich erklärt
Woran man erkennt, dass man mit weniger Containern nicht auskommt: die Untergrenze aus der Gesamtmenge, die schärfere für große Pakete und was ein Verfehlen bedeutet. Erst für Einsteiger ohne Formeln, dann für Fachleute mit Formeln und Messwerten.
Stützfläche und Schwerpunkt verständlich erklärt
Warum Kisten im Container nicht schweben dürfen und die Last nicht einseitig liegen darf, was die Mindest-Stützfläche an Behältern kostet und warum sich die Mitte mit diesem Verfahren nur verbessern, nicht zusagen lässt: erst für Einsteiger ohne Formeln, dann für Fachleute mit Formeln und Messwerten.
Von der Sortierung zur Verfahrenswahl: Reihenfolge, Regel, Schranke
Die Wurzel ist das Sortieren und Einsetzen bei Paketen mit einer Größe: Die Reihenfolge entscheidet stärker als die Regel. Die Schranken zeigen, wann FFD bewiesen optimal ist, und stoßen an Grenzen, die das Stück zu Triplets und der 11/9-Instanz ausleuchtet. Die LP-Schranke beweist mehr, und zwei optionale Stücke gehen darüber hinaus: der Arc-Flow berechnet das Optimum selbst, das Näherungsschema rundet und gruppiert. Das Vektor-Packen zeigt, was passiert, wenn zwei Größen zählen.
Ein zweiter Strang führt in die Fläche und in den Raum: Regale, Skyline und MaxRects für Rechtecke, Extreme Points für Quader, dann Stützfläche und Schwerpunkt als Nebenbedingungen und optional die Entladereihenfolge. Die Reihenfolgesuche macht aus der festen Reihenfolge eine gesuchte. Die Verfahrenswahl führt die Wege zusammen und fragt, welches Verfahren bei welcher Mischung gewinnt.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
- Baustein aus einer anderen Linie
Gestrichelt umrandet sind Demos aus anderen Linien: das Online-Packen aus den Online-Algorithmen und die Column Generation aus der Exakten Suche. Doppelt umrandet ist die Verfahrenswahl, in der mehrere Wege zusammenlaufen. Die Stücke Arc-Flow, Näherungsschema und Entladereihenfolge sind optional.
Verwandt in anderen Linien
- Online-Algorithmen — Das Online-Packen packt Frachtstücke, ohne die späteren zu kennen. Das Sortieren und Einsetzen ist das Offline-Gegenstück: Wer alle Pakete vorab kennt, darf sie vor dem Einsetzen ordnen, und das ändert im Beispiel mit zwölf Paketen die Zahl der Container bei First Fit von 7 auf 5.
- Exakte Suche — Die Column Generation löst das Zuschnittproblem mit einem Muster-LP und erzeugt die Muster erst bei Bedarf. Die LP-Schranke dieser Linie nutzt dasselbe Muster-LP nur als Messlatte: Sie fragt, ob der aufgerundete LP-Wert beweist, dass FFD optimal ist, und erklärt das Erzeugen der Spalten nicht.
- Klassische Scheduling-Theorie — Die LPT-Demo ordnet Aufträge nach Länge, bevor sie auf Maschinen verteilt werden. Sortieren und Einsetzen ist die verwandte Idee beim Packen: erst absteigend ordnen, dann jedes Teil in den ersten Behälter setzen, in den es passt.
Packen: Erst sortieren, dann einsetzen
Sehen Sie, wie zwölf Pakete in gleich große Container gesetzt werden und was die Containerzahl stärker verändert: der Wechsel zwischen First Fit und Best Fit oder die Reihenfolge der Pakete. Ein Vergleich zeigt live alle neun Kombinationen; im ersten Beispiel braucht First Fit wie geliefert 7 Container, größte Pakete zuerst nur 5. Der Haken: Gemessen wird nur an gleichverteilten Größen, Praxisdaten fehlen.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Schranken: Wann ist FFD bewiesen optimal?
Verfolgen Sie, wie sich entscheidet, ob die Packung von FFD (First Fit, größte Pakete zuerst) beweisbar die wenigsten Container braucht: Das gilt, wenn sie eine untere Schranke erreicht, eine Mindestzahl für jede Packung. Vier Handbeispiele zeigen je einen Ausgang, ein Raster misst, woran ein offener Fall liegt. Der Haken: Bei 12 Paketen und 100 Instanzen je Zelle sind die Anteile nicht stabil, ein zweiter Satz verschiebt sie.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Wo FFD versagt: Triplets und die 11/9-Instanz
Sehen Sie, wie Paketmengen gebaut werden, deren Optimum feststeht: Je drei Pakete (ein Triplet) füllen zusammen einen Container, und trotzdem packt FFD, das die größten Pakete zuerst setzt, sie schlecht. Ein Regler wählt die Zahl der Triplets. Bei 100 Triplets braucht FFD im Mittel 12,88 Container mehr als nötig. Der Haken: Die Instanzen sind gezielt gegen FFD gebaut und sagen nichts über Praxisdaten.
Demo starten →LP-Schranke: Was Brüche beweisen
Sehen Sie, wie eine stärkere Mindestzahl für die Container entsteht, wenn eine Gruppe von Paketen, die in einen Container passt (ein Muster), auch zum Bruchteil benutzt werden darf. Von 129 Rasterinstanzen, die die einfachen Schranken offen lassen, beweist der aufgerundete Wert bei 66, dass FFD optimal ist. Der Haken: In den gesuchten Zufallsinstanzen verfehlte er das Optimum nicht, doch aus der Literatur sind Gegenbeispiele bekannt.
Demo starten →Arc-Flow: der Graph statt der Muster
Optional: Verfolgen Sie, wie die kleinste Containerzahl als Strom durch ein Netz aus Füllständen entsteht, in dem jeder Pfeil ein Paket ist, statt aus einer Liste aller Beladungen. Die Demo zeichnet Netz und Strom: Bei 12 großen Paketen und Kapazität 1000 behält die kleinste Stufe im Mittel 2 % der Bögen des vollen Graphen. Der Haken: Das gilt nur für drei Größenverteilungen und höchstens 30 Pakete.
Demo starten →Runden und Gruppieren: ein Näherungsschema
Optional: Verfolgen Sie, wie ein Näherungsschema große Pakete gruppiert und auf die Größe des größten Mitglieds aufrundet, sodass wenige Größen bleiben, die sich optimal lösen lassen; kleine Pakete füllen zuletzt auf. Gegen das einfache Verfahren FFD ist es im Mittel über je 50 Instanzen nur in 3 von 108 Kombinationen aus Zelle und Einstellung besser. Der Haken: Die Rechnung für die versprochene Güte wird ab eps etwa 0,05 absurd groß.
Demo starten →Zwei Grenzen: Volumen und Gewicht
Sehen Sie, wonach man sortiert, wenn ein Behälter zwei Grenzen hat, Volumen und Gewicht: Ein größtes Teil gibt es dann nicht, man bildet aus beiden Zahlen eine Sortierzahl. Im Handbeispiel braucht First Fit (jedes Teil in den ersten Behälter, in dem es passt) nach dem Volumen sortiert 6 Behälter, in Lieferreihenfolge nur 4. Der Haken: Bei gegenläufigen Maßen ist die Untergrenze locker, dort zählt nur die Rangfolge der Schlüssel.
Demo starten →Von Zeilen zu Regalen: NFDH gegen FFDH
Sehen Sie, wie Rechtecke ohne Überlappung in waagerechten Regalen landen: Eine Regel wählt das Regal, ein Sortierschlüssel die Reihenfolge. Ein Vergleich zeigt live, dass zwölf Rechtecke je nach Reihenfolge und Regel 6 oder 3 Behälter brauchen und dass die Höhe in allen 16 Messzellen der beste Schlüssel ist. Der Haken: Ab 40 Rechtecken fehlt das Optimum als Maßstab; belastbar ist dort nur der Vergleich der Kombinationen.
Demo starten →Freiflächen verwalten: Skyline und MaxRects
Sehen Sie, wie statt fester Regale der freie Platz selbst verwaltet wird: Skyline merkt sich die Oberkante der gesetzten Rechtecke, MaxRects die größten freien Rechtecke. Ein Vergleich zeigt live, dass MaxRects nach Fläche sortiert gegen das nach Höhe sortierte Regal in 307 von 1600 Instanzen weniger Behälter braucht. Der Haken: Sortiert man alle nach Höhe, ist das Regal bei mittleren Rechtecken ab 20 Stück besser.
Demo starten →Die dritte Dimension: Extreme Points
Verfolgen Sie, wie Quader in Behälter gepackt werden, wenn eine Liste freier Eckpunkte verwaltet wird, an denen der nächste Quader ansetzen darf. Ein Vergleich von 15 Kombinationen zeigt live, dass im ersten Beispiel mit zwölf Quadern nur ein Verfahren alle in einen Behälter bringt. Der Haken: Ohne Stützbedingung liegen in der besten Variante bei 80 flachen Quadern 42,3 % auf weniger als 80 % ihrer Grundfläche auf.
Demo starten →Nebenbedingungen: Stützfläche und Schwerpunkt
Sehen Sie, wie eine Mindest-Stützfläche das Packen verändert: Ein Quader darf nur stehen, wo ein Mindestanteil seiner Grundfläche aufliegt. Ein Regler zeigt, dass bei einem Handbeispiel mit zwölf Quadern das Volumen als Sortierschlüssel mit 80 % Stützfläche zwei Behälter braucht statt einem. Der Haken: Einen harten Schwerpunkt liefert das Verfahren nicht; auch mit Schwerpunktregel und Verschieben der Ladung liegen bei 80 flachen Quadern nur 44 % der Behälter im Schwerpunktfenster.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Entladereihenfolge: Stopps und Stapelbarkeit
Optional: Sehen Sie, wie zwei Bedingungen aus der Auslieferung das Packen verteuern: Was über einem anderen Quader liegt, darf nicht später entladen werden, und über nicht stapelbaren Quadern liegt nichts. Ein Vergleich von fünf Sortierschlüsseln zeigt live die Behälterzahl. Der Haken: Nach dem Stopp zu sortieren lohnt meist nicht, die Grundfläche ist bei 3 Stopps und 40 % nicht stapelbaren Quadern in allen 12 Zellen der beste Schlüssel.
Demo starten →Reihenfolge suchen: Zufall und Tausch
Verfolgen Sie, wie eine Suche die Reihenfolge verbessert, in der Rechtecke gepackt werden: Sie vertauscht zwei Teile der besten Reihenfolge und behält die neue, wenn sie nicht schlechter ist. Bei gleicher Behälterzahl zählt auch, wie leer der leerste Behälter ist. Im ersten Beispiel finden damit nach 1000 Versuchen 17 von 20 Startzahlen des Zufallsgenerators die zwei Behälter statt der drei nach Fläche. Der Haken: Eine einzelne Suche bleibt ein Zufallsergebnis.
Demo starten →Verfahrenswahl: welches Packverfahren wann?
Sehen Sie, welches Packverfahren sich wann lohnt: Eine Karte stellt für Pakete, Rechtecke und Quader je vier Mischungen von Teilegrößen nebeneinander und zeigt, welches Verfahren im Mittel am wenigsten Behälter braucht. Überraschend: Innerhalb eines Bereichs wechselt in dieser Karte der Gewinner nicht, nur die Plätze dahinter drehen sich. Der Haken: Die Mindestzahl an Behältern ist in 2D und 3D locker, belastbar sind nur Unterschiede zwischen den Verfahren.
Demo starten →Welches Stück passt zu meiner Frage?
Ein Entscheidungsbaum über alle vierzehn Stücke: Er fragt danach, was gepackt wird und was man von der Packung wissen will, nicht nach dem Verfahren.
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Der Baum ordnet nach der Frage, nicht nach Güte. Wo mehrere Stücke passen, hilft die Verfahrenswahl; ihre Aussagen gelten für die erfundenen Familien von Größen und die Python-Fassungen der Verfahren.
Weitere Linien in diesem Bereich
Exakte Suche
Bewiesen beste statt nur guter Lösungen: zwei Linien, Rucksack und Cutting Stock, von Branch & Bound bis Column Generation und Branch & Price.
Lineare Programmierung
Was steckt in einem LP-Löser? Elf Stücke vom Tableau-Simplex über Schattenpreise und Innere Punkte bis zum Crossover, alle von Grund auf geschrieben und gemessen.
Nichtlineare Optimierung
Wie findet man ein Minimum, wenn nichts linear ist? Acht Stücke vom ersten Schritt bergab über Krümmung und Nebenbedingungen bis zur Brücke ins Deep Learning, jedes mit gemessenem statt behauptetem Befund.
Konvexe und konische Optimierung
Wann ist ein Ergebnis beweisbar optimal, wie rechnet ein Löser mit Kegeln, und welcher Löser passt zu welcher Aufgabe? Sechzehn Stücke von der Lücke als Beweis bis zur Verfahrenswahl.
Anordnen: relaxieren und runden
Wie weit unter dem Besten liegt die beste Zahl, die man beweisen kann, und wie rundet man eine Lockerung zurück auf eine Anordnung? Fünfzehn Stücke von der Mini-Halle bis zur Verfahrenswahl.
Populations-Metaheuristiken
Wie durchsucht eine ganze Population den Lösungsraum? Elf Verfahren von der Kreuzung über Kovarianzmatrizen bis zu Pheromonspuren, jedes mit seiner gemessenen Grenze.
Trajektorien-Metaheuristiken
Wie kommt eine einzelne Lösung über ihr erstes lokales Optimum hinaus? Zwölf Verfahren von Verschlechterungen akzeptieren bis Destroy-and-Repair, jedes mit seiner gemessenen Grenze.
Heuristische Baumsuche
Was bleibt von der Suche, wenn man das Optimum nicht abwarten kann? Acht Verfahren von der gierigen Suche bis Monte Carlo Tree Search, jedes mit seiner gemessenen Grenze.
Novelty Search und Quality-Diversity
Ein Hof-Roboter im täuschenden Labyrinth, zwölf Stücke: von der Sackgasse der Fitness über Novelty Search und MAP-Elites bis zu Go-Explore, Routing und POET.
Standortplanung
Welche Standorte eröffnen, wenn jeder Kunde zum nächsten offenen geht? Sechs Stücke von der einfachen Fixkosten-Entscheidung über Kapazität, Maximum statt Summe und Lagerbestand bis zum Wettbewerb zweier Spieler und zum Hub mit Rabatt.
Klassische Scheduling-Theorie
Ein wachsendes Beispiel von einer Maschine bis zum allgemeinen Ressourcenmodell: elf Stücke, jedes hebt genau eine Annahme des vorigen auf.
Optimierung unter Unsicherheit
Eine Kapazität, die vor der unbekannten Nachfrage gewählt wird, sechs Stücke: vom Wert der Information über Stichprobe, CVaR, Robustheit und Garantie bis zur rollierenden Planung.
Bayessche Optimierung und Gauß-Prozesse
Eine teure Simulation, sieben Stücke: vom Gauß-Prozess und der erwarteten Verbesserung über Rauschen und Nebenbedingungen bis zu hohen Dimensionen, parallelen Läufen und mehreren Genauigkeiten.
Online-Algorithmen
Wie man entscheidet, bevor die Zukunft bekannt ist, und was die Garantie für den schlimmsten Fall im Betrieb kostet: sieben Stücke von Mieten oder Kaufen bis zu Vorhersagen.
Zielfunktionsdesign
Was ändert sich, wenn nur das Ziel wechselt? Vierzehn Stücke von der Wahl zwischen Summe und Maximum über Fairness und Ersatzziele bis zur Frage, wie man ein Ziel vor dem Einsatz testet.
Bestandspolitiken
Wie viel bestellen, wenn jede Periode zählt? Sieben Demos mit demselben Artikel: von der Rückwärtsrechnung über Fixkosten, Lieferzeit, Verderb und zwei Lager bis zur Frage, welche einfache Regel reicht.
Komplexitätsklassen
Was sagt es aus, wenn ein Problem als NP-schwer gilt, und welcher Ausweg passt zu welchem Grund der Härte? Zehn Stücke über Reduktionen, typische Instanzen, große Zahlen, Garantien, Parameter, Zufall, Zählen, Spiele und lokale Optima.
SAT und Constraint Programming
Wie merkt sich ein Löser, warum eine Sackgasse eine war? Sechzehn Stücke vom Konfliktlernen über Beweise, Zähler und Symmetrie bis zu Mengen- und Maschinenschlüssen, lokaler Suche und der Wahl der Modellwelt.
Umstauen: Untergrenze und Suche
Wie viele Container müssen mindestens umgestapelt werden, und wann lohnt sich die Suche nach dem Besten? Fünfzehn Stücke von der einfachen Regel bis zur Verfahrenswahl.
Tourenbildung: eine Reihenfolge, optimal zerlegt
Wie bildet man Touren aus einer einzigen Reihenfolge aller Kunden, und wann schlagen Savings, Sweep oder Suche sie? Fünfzehn Demos von der Aufzählung bis zur Verfahrenswahl.
Ressourcenwege und Spaltenerzeugung
Wie findet man unter unüberschaubar vielen möglichen Touren die mit dem größten Nutzen, wenn jede Zeit- und Lastgrenzen einhalten muss? Dreizehn Demos vom Weg mit Grenze bis zur Wahl des Verfahrens.
Takt und Periodizität
Ein Fahrplan, der sich jede Stunde wiederholt: vier Stücke von den Zeitabständen über die Wartezeit der Umsteiger und die Kreisgleichungen bis zum Betriebstag.