Combinatorial Optimization Techniques for Three-Dimensional Arrangement Problems

This paper presents two approaches for the automated layout of threedimensional objects in space. The goal is to achieve high packing densities and fitting of objects in predefined design spaces while satisfying technological side constraints. The focus is on small-sized problem instances (up to 20 objects) with complex, possibly non-convex shapes. Linear programming methods form the common ground of our approaches. The first approach is a global optimization algorithm based on the branch-and- bound paradigm. We introduce a discretization of the configuration space of all possible arrangements which facilitates a complete enumeration of solutions. The bounding procedure then allows for a drastic reduction of the search space. We use a limited number of discrete object orientations within this method. The second approach is a local optimization scheme which starts out from a given initial arrangement and is capable to perform continuous object rotations. It is based on a linearization of orthonormal rotation matrices. We also present a perspective for combining global optimization and continuous object rotations. Examples in this paper are taken from the automobile industry but applications are not limited to this area. Various objective functions may be optimized, including the volume and the location of the center of gravity. We also show how to integrate a wiring area estimation into the global optimization procedure.