Glossar · approach
Bin Packing
Das Problem, Objekte verschiedener Größe so in Behälter fester Kapazität zu packen, dass die Anzahl der Behälter minimal wird.
Bin Packing ProblemBPPBehälterpackungsproblem
Bin Packing ist ein klassisches OR-Problem: gegeben eine Menge Objekte (verschiedene Größe, Gewicht, Volumen), platziere sie in Behälter (bins) fester Kapazität so, dass die Gesamtzahl der Behälter minimiert wird (Standardziel). Die eindimensionale Variante (1D-BPP) — nur Gewicht oder Länge — wird seit Johnson (1974) intensiv untersucht. Die zweidimensionale (2D-BPP) tritt bei Zuschnitt und Etikettenplatzierung auf. Die dreidimensionale (3D-BPP) bei Paletten-, Container- und LKW-Beladung. Da NP-hart, basieren praktische Lösungen auf Heuristiken (first-fit decreasing, best-fit, wall-building) und Meta-Heuristiken (GRASP, Tabusuche, Simulated Annealing). Die mit praktischen Nebenbedingungen erweiterte Version heißt Container Loading Problem (CLP).
Örnek
Ein E-Commerce-Lager soll 500 unterschiedlich große Pakete in 40-Fuß-Container packen. Ein 3D-BPP-Solver reduziert die Containerzahl gegenüber manuell um 15-25%.