A meta-heuristic technique for the packing of three-dimensional irregular pieces Seminar

Event details

The 3D irregular open dimension problem consists in placing a set of irregular pieces in a container of a fixed base, with the objective of minimising its height. This problem, not very often studied in the literature, has a wide range of applications in 3D printing, packaging or component layout, among others. To tackle this problem, we choose a discrete representation of the geometry that uses voxels, the three- dimensional equivalent of pixels. In this discretised space, we define the no-fit voxel. This is an extension of the two-dimensional no-fit polygon, a very popular tool used in two-dimensional packing. The no-fit voxel can be pre-calculated and allows us to very quickly evaluate intersections of pieces during the algorithms and provides a complete description of the valid relative positions between two pieces. Using this tool, we propose a meta-heuristic algorithm that allows overlap of pieces in its intermediate steps. It consists of two components, a search phase and strategic oscillation. In the search phase we perform a number of piece movements and swaps with the aim of resolving the overlap and finding feasible solutions. In the strategic oscillation, we increase or reduce the height of the container depending on the status of the layout. We test this technique across a range of different instances. We adapted some instances from the existing literature, both two and three-dimensional. To deal with more complicated shapes, we also propose two other sets of instances. The first one consists in shapes randomly generated by ourselves by adapting 2D image generation algorithms. The second set consists in collections of parts of realistic objects taken from 3D printing websites. Our results show that this is a robust technique that can be successfully applied to find dense packings across pieces with very different features, regardless of their geometric attributes.