3D Packing

Motivation

Three-dimensional packing problems occur in various industrial settings in which miniaturisation trends increase the need for high packing density and fitting of components in small design spaces. Our project 3D-Packing focusses on packaging problems in engineering applications like finding compact machine assemblies and supporting the conceptual layout of vehicles (e.g. in automotive and aerospace industries). Our goal is to support with algorithmic techniques the design of package layouts that meet the functional relationships between the parts and match market needs including cost, safety, comfort, as well as economic and environmental aspects. Integrating computer aided packaging functionalities into modern CAD-systems offers optimized solutions while reducing the time to market.

The Institute for Algorithms and Scientific Computing (SCAI) has long-term expertise in solving two-dimensional packing problems. The projects OMSI and ROUTING are concerned with optimal layout generation for VLSI chips. This task includes the placement of gates and routing of wires under various technological constraints. In addition, we developed software packages to minimize the amount of wasted material in cutting images for leather and textile industry. This work is done in the NESTING project and forms the basis for our three-dimensional packing activities in mechanical engineering.

To assure the practical relevance of our research activities, we maintain intensive dialogues with industrial partners. On packaging problems in automobile design, we cooperate with the passenger car division of Mercedes-Benz and the research sector of Daimler-Benz.

On an abstract level we can define the problem as follows: Given a set of irregularly shaped three-dimensional objects, find a layout with minimal space requirements that achieves the design objectives while satisfying additional constraints. An example of a secondary design objective is mimimizing routing lengths for wires that connect components. Additional constraints may also arise from assembly or accessibility considerations.

Automated packaging tools offer the opportunity of generating a number of substantially different solutions, optimized for varying design criteria. We consider global optimization methods to be essential in the conceptual phase because local optimization techniques will not exploit the full flexibility given in early design stages.

The ultimate goal is the integration of packaging functionalities with issues of constructibility and maintainability as well as ergonomics, for instance in automobile design. Knowledge-based approaches and interactive graphics with sophisticated visualisation may be necessary to achieve this.

Routing Graph

Wiring Area

We have developed an algorithmic approach to packing rectagonal objects (objects with sides parallel to the coordinate axes) in three-dimensional space. Our branch & bound procedure uses methods originating from compaction algorithms in VLSI design. The routing of wires comprises an essential part of the industrial layout problem at hand. We integrate into the packaging module a wiring area estimation based on integer programming relaxation techniques. Our algorithm computes a layout with minimal space requirement and maintains an upper bound (the best legal layout found so far) and a lower bound (how much space is occupied at least by a legal layout) at discreet points in time. If the algorithm is preemted, then the upper and lower bounds do not meet but still present a quality certificate for the computed arrangement.

The construction of suitable routing graphs is essential for a good wiring area estimation. The graph should adapt to the layout such that nodes are more dense in regions with non-uniform routing properties. Examples for a routing graph and the resulting wiring area estimation are shown below.

The know-how developed in the project 3D Packing has been incorporated in our standard product PackAssistant.

Previous work on 3D-packing problems can be found in the Operations Research and Management Science literature. The main focus here is on container, vehicle and pallet loading problems that consider loading patterns for box-shaped objects. Layer oriented procedures are presented for most parts which seem not to be applicable in our case.

Only little work has been done on problems in engineering disciplines and on non-orthogonal objects.