Contpack - Maximising the Volume Utilisation of Containers
by Onno Garms, Ralf Heckmann and Stefan Rank
The Fraunhofer Institute for Algorithms and Scientific Computing (SCAI) has developed three-dimensional packing software for optimising the volume utilisation of containers. The software automatically chooses from a given range of containers and quickly generates highly efficient three-dimensional packings of complex objects.
Today's industrial production is often spread over many sites and locations worldwide. Manufacturing of various parts and intermediate or final assembly can all occur in different places, and the integration of these production sites requires efficient transportation of the turnout between them. This transportation of parts or products is often done in containers or boxes. In order to minimise the cost of transport and logistics, it is beneficial to many companies to pack their products as tightly as possible.
 |
| Figure 1: Workers loading containers with parts. Courtesy by the online magazine 'logistics pilot'. |
The optimisation group within Fraunhofer SCAI is currently developing automatic packing algorithms and software that can be used to pack complex three-dimensional parts (each of which may have many hundreds of thousands of facets) into containers as efficiently as possible, thereby maximising their volume utilisation.
Apart from volume utilisation, the results calculated by our packing algorithms are subject to other constraints and demands from industry. Since the loading and unloading of containers is often done by humans, it is important to generate layouts which are easily reproducible by humans. The number of different rotational positions of the components is therefore limited to a small number. These rotations are not provided in advance, but must be found and optimised by the software. Additionally, the containers are filled in tiers, many of which are identical.
In current industrial practice, the generation of packing layouts for containers is done by human beings, who require a sufficient number of physically available components and containers, and complete the task by trial and error. Such a procedure is impossible if the components have not yet been produced. Increasingly however, companies would like to generate container packings for their parts while still in the design stage, in case there exists a way of modifying the outer hull of a part slightly such that it remains equivalent from a technological point of view but can be packed more efficiently.
Finding optimal packing methods with physical objects is a difficult and time-consuming task, because both component geometry and a large variety of possible container dimensions must be considered. Another common method uses CAD systems to generate the layout, but these lack algorithmic support for the task. As things stand, the packing quality of a part into a container improves over time as the insights and suggestions of employees are implemented.
 |
| Figure 2: Computer-generated packing of loudspeakers into a container. |
Our Contpack software chooses a proper container size from a given list of sizes and generates a high-density regular layout for this container. This reduces the overall number of containers needed in the supply chain, including stocking, transportation and handling. In the stage of production planning, the automatic packing generation helps estimate the required number of containers. It can also help in recognising the need to develop containers with new dimensions.
In contrast to existing algorithms, which are often limited to the packing of cuboids using bin-packing strategies, our algorithms can handle components of arbitrary shapes. The software can be used at an early stage in component development, because the algorithms can handle CAD data of different quality. The integration of the Contpack program into existing CAD systems allows both the design of new components and the planning of their transportation to be performed in a single step within a uniform environment.
The user can select a triangulated VRML representation of the component to be packed and a list of container sizes to be tested, and can define the stable positions. The stable positions restrict the degrees of freedom for the components to rotations around the vertical axis and to arbitrary translations. This accounts for the stability of the generated layout.
There are a number of packing options, including lattice packing. The lattice is a two-dimensional grid made up of repeating units such as rectangles, trapezoids or hexagons. The lattice maintains the layout during transportation and thus protects the components. The use of a lattice results in a completely regular packing of the container. For achieving denser layouts there are options without a given lattice structure. The resulting layout can be viewed in three dimensions, allowing the user to browse through the tiers of the filled container.
Packing tasks belong to the class of NP-hard problems, meaning that no algorithm for the optimal, time-efficient solution of the problem is known. The techniques employed include exact and heuristic optimisation methods depending on the complexity of the task or sub-task being performed by the algorithm. For packings into given lattice structures we have implemented very fast optimal methods. For packings without lattice structures, the problem is NP-hard. We also apply strategies for finding regular packings, but we add heuristic methods for finding optimal combinations of regular packings in different areas of the box.
Future work will include relaxing the strict separation of the tiers inside the container by robust intermediate tiers. Also, more than one stable position per tier will be allowed. The user will be able to define taboo areas between the components, and we will fully integrate the software into the user's CAD environment, eg into CATIA.
Fraunhofer SCAI has a strong background in the solution of cutting and packing problems. Experts in the department for optimisation have been working on packing problems for over ten years. The application of the software to three-dimensional container packing started in 2002.
Fraunhofer SCAI is collaborating on this project together with and by the commission of Audi and the BMW Group. Our partner Solve-IT MVI in Munich took over the project management and developed the interface to the container and VRML data, the dialogues, the visualisation in 3D and the generation of the packing instruction reports. While the program is tailor-made for the needs of the automotive industry, it can be used in many areas of the manufacturing industry. Fraunhofer SCAI intends to release a standard product for the container-packing problem in the near future. We also plan to extend the functionality of the software and to make it usable in other fields of application.
Link:
http://www.scai.fraunhofer.de/opt
Please contact:
Stefan Rank, Fraunhofer SCAI
Tel: +49 2241 14 1503
E-mail: Stefan.Rank scai.fraunhofer.de
|
