Reinforcement learning for the shape nesting problem
Luisa Botta
Reinforcement learning for the shape nesting problem.
Rel. Giulia Bruno, Niccolo' Giovenali. Politecnico di Torino, Master of science program in Engineering And Management, 2024
|
|
PDF (Tesi_di_laurea)
- Thesis
Restricted to: Only staff users fino al 16 April 2026 (data di embargo). Licence: Creative Commons Attribution Non-commercial No Derivatives. Download (5MB) |
Abstract
This thesis addresses the “2D Irregular Packing problem”, a combinatorial optimization challenge with significant applications in industries such as manufacturing, furniture production, textiles and aerospace. The problem focuses on efficiently arranging two-dimensional objects of irregular shapes on a surface with the goal of minimizing unused space and maximizing material utilization. Given the problem’s NP-complete nature, finding an optimal solution is computationally infeasible for most real-world scenarios. As a result, in literature approximate solutions are typically sought using heuristic and metaheuristic algorithms. This thesis first addresses the nesting problem through the algorithms present in the literature. The geometric problem of positioning a polygon into a hole or relative to another polygon is treated with two methods: the Envelope Polygon and the No-Fit Polygon.
These geometric methods are then used by the two main approaches to solve nesting: the first decomposes the problem into a placement algorithm (e.g., the Bottom Left) and a sequencing algorithm like the Genetic Algorithm; the second approach, allowing temporary overlaps of polygons by progressively reducing the area that acts as the container and swapping polygons, finds the optimal sequence for this heuristic approach
Publication type
URI
![]() |
Modify record (reserved for operators) |
