Combinatorial Optimization Techniques for Three-Dimensional Arrangement Problems

Thomas Lengauer and Mike Schäfer
Additional contact information
Thomas Lengauer: University of Bonn, Department of Computer Science
Mike Schäfer: University of Bonn, Department of Computer Science

A chapter in Mathematics — Key Technology for the Future, 2003, pp 63-73 from Springer

Abstract: Abstract 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.

Keywords: Arrangement Problem; Linear Separation; Cooperation Partner; Convex Object; Linear Programming Method (search for similar items in EconPapers)
Date: 2003
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-55753-8_6

Ordering information: This item can be ordered from
http://www.springer.com/9783642557538

DOI: 10.1007/978-3-642-55753-8_6

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().