Packing and Layout Optimization

Optimization of Circular Layouts

One of our algorithms generates dense arrangements of circular parts inside a circular container.
This can be applied to find dense packings of many leads inside a larger compound cable. A high packing density minimizes the amount of sheathing material needed for enclosing all leads. One further advantage is the fully automated layouting process which eliminates the need to manually arrange all parts. Manual layouting can often be time-consuming since many constraints have to be met at the same time and the amount of possible arrangements increases exponentially with the number of parts. A software solution makes also possible to try different scenarios and to quickly change production layouts if requirements change.

	The image shows some examples of asymmetric and symmetric dense arrangements of circular items inside a circular container. Click to enlarge.

Advantages and State of Reasearch

• Pairwise distances of items can be constrained (minimum and maximum distances) globally or for individual items.
• The minimum or maximum distance of individual items to the sheathing or to the centerline can be specified.
• It is possible to generate symmetric arrangements to ease manufacturing or to distribute masses evenly.
  Already implemented is the generation of reflectional symmetry about one axis or two axes and of manifold rotational symmetry.
  A special feature is the possibility to loosen the symmetry constraints if needed. This allows to arrange multiple groups of items symmetrically in spite of having item quantities that would otherwise be incompatible with a common symmetry. If needed filler items can be inserted to force a desired symmetry.
• The position of items can be fixed.
• If needed a large amount of alternative arrangements can be generated that have similarly high packing densities. This allows to find layouts that meet other external requirements (for example manufaturing or safety constraints).
• Our algorithms are robust even for a large number of items and always end up with valid solutions.
• The algorithms are very efficient despite of the enormous complexity of the underlying optimization problems. For layouts of 50 items it takes approximately 30 seconds on modern computers to get a first, good result; highly optimized layouts can be obtaind within a few minutes.
• The algorithms are extensible by adding further constraints.

Cutting layout planning for industrial production

Industrial production aims to minimize cutting waste when blanking out shapes from metal plates or cutting out pattern pieces from fabric. For this purpose we developed algorithms to find dense arrangements of arbitrary shapes (non-convex polygons).

	The video shows some examples of 2 dimensional layout problems.
	The video shows some examples of 2 dimensional layout problems.

Other Research Fields

We have also developed algorithms for packing boxes, rectangles and arbitrary 3d objects (represented by triangle meshes).