3D Packing

Motivation

Dreidimensionale Packungsprobleme treten in vielen verschiedenen industriellen Szenarien auf, in denen Trends zur Miniaturisierung den Bedarf an hohen Packungsdichten und dem Komponenteneinbau in kleine Anordnungsräume erhöhen. Unser Projekt 3D-Packing konzentriert sich auf Packungsprobleme in technischen Anwendungsbereichen, wie beispielsweise dem kompakten Bau von Maschinen, und Unterstützung bei der konzeptionellen Anordnung von Bauteilen in Fahrzeugen (z. B. in der Auto- oder Luft- und Raumfahrtindustrie). Unser Ziel ist es, mit Algorithmentechnologie Packungen zu konstruieren, die die funktionalen Zusammenhänge zwischen den Bauteilen gewährleisten und den Marktanforderungen in den Bereichen Kosten, Sicherheit und Komfort sowie in wirtschaftlichen und umwelttechnischen Aspekten gerecht werden. Die Integration computerunterstützter Packungsfunktionalitäten in moderne CAD-Systeme bietet optimierte Lösungen und reduziert die Zeit bis zur Einführung des Produktes.

Das Fraunhofer-Institut für Algorithmen und Wissenschaftliches Rechnen (SCAI) hat langjährige Erfahrung in der Lösung zweidimensionaler Packungsprobleme. Die Projekte OMSI und ROUTING beschäftigen sich mit dem optimalen Layout von VLSI-Chips. Diese Aufgabe beinhaltet die Platzierung von Gates und das Verlegen von Drähten unter verschiedenen technischen Nebenbedingungen. Zusätzlich haben wir Software-Pakete entwickelt, welche die Menge des verschnittenen Materials bei Schnittbildern in der Leder- und Textilindustrie minimieren. Dieses wurde im NESTING Projekt umgesetzt und bildet die Grundlage unserer dreidimensionalen Packungs-Aktivitäten im Maschinenbau.

Um die Praxisrelevanz unserer Forschungen sicherzustellen pflegen wir intensive Gespräche mit Partnern aus der Industrie. Bei Packungsproblemen im Automobilbau arbeiten wir mit der Personenwagen-Abteilung von Mercedes-Benz und der Forschungsabteilung von Daimler-Benz zusammen.

Abstrakt lässt sich das Problem wie folgt definieren: Gegeben ist eine Menge unregelmäßig geformter dreidimensionaler Objekte, gefunden werden soll eine Anordnung mit minimalem Platzverbrauch, welche die Designziele erreicht und zusätzliche Randbedingungen erfüllt. Ein Beispiel für ein sekundäres Designziel ist die Minimierung der Länge von Komponenten verbindenden Drähten. Zusätzliche Randbedingungen können sich aus Betrachtungen für den Zusammenbau und die Erreichbarkeit der einzelnen Bauteile ergeben.

Automatisierte Packungs-Tools bieten die Möglichkeit, eine Anzahl völlig verschiedener Lösungen zu generieren, die jeweils für unterschiedliche Planungskriterien optimiert sind. Wir betrachten allgemeine Optimierungsmethoden als unverzichtbar in der konzeptionellen Phase, weil spezielle Optimierungstechniken die volle Flexibilität in frühen Planungsabschnitten nicht ausnutzen.

Das endgültige Ziel ist die Integration von Packungs-Funktionalitäten in die Aspekte von Konstruierbarkeit und Wartbarkeit genauso wie der Ergonomie, beispielsweise im Automobilbau.

Routing-Graph

Verdrahtungsfläche

Wir haben einen algorithmischen Zugang zum Packen rechteckiger Objekte (das sind Objekte, deren Seiten parallel zu den Koordinatenachsen sind) im dreidimensionalen Raum entwickelt. Unsere Branch-and-Bound-Prozedur benutzt Methoden, die ihren Ursprung in Verdichtungs-Algorithmen im VLSI-Design haben. Das Verdrahten enthält einem grundlegenden Anteil des industriellen Anordnungs-Problems. Wir integrieren eine Abschätzung der Verdrahtungsfläche basierend auf Relaxations-Techniken ganzzahliger Programmierung in das Packungs-Modul. Unser Algorithmus berechnet eine Anordnung mit minimalem Platzverbrauch und bleibt zu jedem Zeitpunkt innerhalb einer oberen Grenze (die beste bisher gefundene zulässige Anordnung) und einer unteren Grenze (wie viel Platz wird mindestens von einer zulässigen Anordnung belegt). Wenn der Algorithmus preemted treffen sich obere und untere Grenze nicht, aber sie bieten eine Qualitätsaussage für die berechnete Anordnung.

Die Konstruktion passender Routing-Graphen ist grundlegend für eine Abschätzung der Verdrahtungsfläche. Der Graph soll sich so an das Layout anpassen, dass die Knoten in Gebieten mit nicht-einheitlichen Routing-Eigenschaften dichter sind. Beispiele für einen Routing-Graphen und die resultierende Verdrahtungsfläche werden unten abgebildet.

Das im Projekt 3D Packing gewonnene Know-how floss auch in unser Standardprodukt PackAssistant ein.

 

 

Frühere Arbeit an 3D-Packungsproblemen ist in Operations Research und Management Science Literatur zu finden. Der Schwerpunkt liegt hierbei auf Problemstellungen der Container-, Fahrzeug- und Palettenbeladung, welche sich auf die Beladung mit rechteckigen Objekten konzentriert. Ebenenorientierte Prozeduren werden in den meisten Fällen präsentiert, scheinen aber in unserem Fall nicht anwendbar zu sein.

Bisher wurde nur wenig an den Problematiken in den Ingenieurwissenschaften und nicht-orthogonalen Objekten gearbeitet.