Behälterpacken mit unregelmäßigen Formen

• Antragsteller: Professor Dr. Stefan Irnich
• Fachliche Zuordnung: Operations Management und BWL-spezifische Wirtschaftsinformatik
• Förderung: Förderung seit 2025
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 561644927

Zuschnitt- und Packprobleme sind zwei Typen wohlbekannter kombinatorischer Optimierungsprobleme. Beim Zuschnitt müssen Rohmaterialien in kleinere Teile zerteilt werden, um eine gegebene Nachfrage zu befriedigen. Bei Packproblemen müssen gegebene Gegenstände in eine minimale Anzahl von Behältern (Bins) gepackt werden. Die beiden Problemtypen sind eng miteinander verwandt und haben viele praktische Anwendungen, z.B. in der Bekleidungs-, Schuh- und Möbelherstellung, in der Automobil-, Schiffbau- und metallverarbeitenden Industrie oder in Transport und Logistik. Angesichts der steigenden Rohstoffkosten fokussieren Unternehmen auf den sparsamen Umgang mit Ressourcen und die Reduzierung von Abfällen, wovon auch die Umwelt profitiert. Ein klassischer Vertreter der Zuschnitt- und Packprobleme ist das eindimensionale Bin-Packing-Problem (BPP). Beim BPP besteht die Aufgabe darin, eine gegebene Menge von Gegenständen mit unterschiedlichem Gewicht in die kleinstmögliche Zahl von Behältern mit bekannter Kapazität zu packen. Obwohl sich die meisten Arbeiten mit dem eindimensionalen Fall befassen, ist er für viele praktische Anwendungen unzureichend. In der Bekleidungs- und Möbelherstellung beispielsweise sind Länge und Breite eines Teils wichtig. Bei der Container- und Palettenbeladung sind Gegenstände und Behälter dreidimensionale Objekte. Ein weiteres charakterisierendes Merkmal ist die Form der Gegenstände und Behälter, d. h., ob sie regelmäßig oder unregelmäßig sind. Im zweidimensionalen Fall wird ein Gegenstand als regelmäßig bezeichnet, wenn es durch höchstens zwei Parameter vollständig beschrieben werden kann, z. B. ein Rechteck mit seiner Länge und Breite. Wenn die Beschreibung mehr als zwei Parameter erfordert, wird er als unregelmäßig bezeichnet. So wird ein allgemeines Polygon als unregelmäßig angesehen, weil es nicht vollständig durch seine Breite und Länge beschrieben werden kann. Wir befassen uns mit dem zweidimensionalen Bin-Packing-Problem mit unregelmäßigen Formen und nennen dieses Problem das Irregular Shape Bin Packing Problem (ISBPP). Das Ziel des ISBPP ist es, alle Gegenstände in einer gegebenen Menge von Behältern überschneidungsfrei zu platzieren, so dass jeder Artikel vollständig in einen Behälter passt und die Anzahl der potenziell unterschiedlichen Behälter minimiert wird. Der Platzierungsaspekt wird normalerweise durch eine Reihe von Regeln modelliert, die angeben, wie jede Art von Gegenstand platziert werden kann, bspw. ob und in welchem Winkel Artikel gedreht werden können. Wir schlagen vor, ISBPPs mit Optimierungsmethoden der ganzzahligen Programmierung zu lösen, genauer mit einem Branch-Price-and-Cut-Algorithmus, bei dem Teilprobleme mit einem kombinatorischen Benders-Algorithmus gelöst werden. Diese Art von Ansatz ist neuartig und generisch, da er die Möglichkeit bietet, verschiedene Repräsentationen der Gegenstände- und Behälter und damit verbundene anwendungsspezifische Platzierungsalgorithmen (Nesting) zu verwenden.

• DFG-Verfahren: Sachbeihilfen