Fundamenten en algoritmes voor 3D onregelmatige cutting en packing problemen

3D irregular cutting and packing problems concern the challenge of efficiently arranging arbitrarily shaped three-dimensional objects inside bigger containers. Examples of such problems include the packing of products in boxes, the compacting of 3D printing layouts, and the extraction of desirable shapes from raw pieces of material. The goal in these problems is typically to either minimize the volume used or to maximize the value of objects that are arranged. These are particularly difficult optimization problems to solve, given the compounding challenges of (i) working with three-dimensional irregular geometry and (ii)~the~inherent combinatorial complexity of packing problems. This fusion of geometric and combinatorial complexity forms a high barrier to entry for researchers and developers wishing to tackle these problems. This helps explain why despite the practical relevance of such problems in our three-dimensional world, they have received relatively little attention in the scientific literature. The situation is further exacerbated by the lack of open-source implementations for the few methods that do exist, which limits the ability to reproduce and build upon previous work. With this thesis, we aim to address the aforementioned shortcomings that currently affect 3D irregular cutting and packing research. We consider two vastly different problem variants: the strip packing problem and the volume maximization problem. For both problems, we succeed in pushing the boundaries of the previous state-of-the-art solution methods, both in terms of exact and heuristic methods. In doing so, we address the relatively limited attention these problems have received in the scientific literature and the lack of exact methods more specifically. Advancing the capabilities of exact methods is important, even though one can safely assume heuristic approaches will outperform exact solution methods for problems of real-world scale and complexity. The limits of exact methods properly substantiate the need for heuristics, and allow us to better understand and evaluate their performance. To help lower the barrier to entry for future researchers, we introduce an open-source software library: MeshCore. This library provides the core functionality needed to manipulate three-dimensional objects, implement packing algorithms, and visualize solutions. In doing so, MeshCore enables rapid prototyping of 3D irregular cutting and packing algorithms. Throughout this thesis, MeshCore is used as a reusable foundation beneath all the algorithms we introduce. Our experiments prove that MeshCore is a suitable tool for addressing a variety of problems and performant enough to support the development of state-of-the-art heuristics. In addition to making MeshCore open source, we also chose to make the implementation of all our algorithms publicly available. This is to actively counteract our concerns regarding the verifiability and reproducibility of academic research in the area of 3D irregular cutting and packing. In addition to making significant academic contributions through publicly available algorithms, this thesis will also explore the impact our research achieved in an industrial context. In collaboration with a diamond processing company, we developed optimization software for maximizing the value of polished diamonds that can be extracted from a rough stone. This case study highlights how the algorithms we develop can have a significant positive impact on real-world applications. One thing that became clear to us throughout the course of this thesis is that the field of 3D irregular cutting and packing is still in many ways in its infancy. Not only in terms of solution methods, but also in other aspects like reproducibility. While we significantly improve upon the previous state of the art for the two problems we address, most of our contributions should be considered foundational in nature. This is because they tackle basic problem variants, concern novel solution strategies, or are the first adaptation of established techniques from related fields. Therefore, many open challenges and opportunities remain for future research in this area, which we feel confident will benefit from our open source MeshCore library.