Paketgrößenproblemen

Paketgrößenprobleme, oft als Bin-Packing-Probleme bezeichnet, gehören zu den zentralen Fragestellungen der kombinatorischen Optimierung. Ausgangspunkt ist eine Menge von Gegenständen mit bekannten Größen, die in möglichst wenige Behälter (Pakete, Kisten) mit fest vorgegebener Kapazität eingeteilt werden sollen, so dass in jedem Behälter die Summe der Größen die Kapazität nicht überschreitet. Typische Zielsetzungen sind die Minimierung der Zahl der verwendeten Behälter oder die Maximierung der Ausnutzung der Kapazität.

Es gibt verschiedene Varianten. Die klassische ein-dimensionale Form betrachtet nur eine Größenachse (z. B. Länge oder Volumen) und wird oft als Bin-Packing bezeichnet. Weiterhin existieren zweidimensionale oder mehrdimensionale Versionen, bei denen neben der Breite auch Höhe oder andere Abmessungen berücksichtigt werden. Weitere Variationen umfassen Bin-Capacities, bei denen unterschiedliche Behältergrößen möglich sind, Online-Versionen, bei denen Items sequentiell erscheinen und der platzsparende Einsatz ohne zukünftige Informationen erfolgen muss, sowie Offline-Versionen, bei denen alle Größen bekannt sind.

Paketgrößenprobleme gelten als NPschwer, selbst in der einfachsten Form. Das moderne Lösungsarsenal kombiniert exakte Verfahren (z. B. ganzzahlige Optimierungsmodelle, Branch-and-Bound, Cut-Generation) mit heuristischen und hybriden Ansätzen. Zu den gebräuchlichen Heuristiken gehören First-Fit- und Best-Fit-Verfahren; es existieren auch fortgeschrittene Approximationen und spezialisierte Algorithmen mit nachweisbaren Gütegarantien. Praktische Anwendungen finden sich in der Logistik, Lagerhaltung, der Montage- und Verpackungsplanung, der Schnittstock-Planung sowie in der Ressourcen- und Speichernutzung in Computersystemen.

Paketgrößenprobleme stehen zudem in Verbindung mit verwandten Problemen wie dem Cutting-Stock-Problem und dem Knapsack-Problem, teilen aber den Schwerpunkt auf effiziente Füllung und Ressourcenallokation unter Kapazitätsbeschränkungen.