Reinforcement learning for the shape nesting problem
Luisa Botta
Reinforcement learning for the shape nesting problem.
Rel. Giulia Bruno, Niccolo' Giovenali. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Gestionale (Engineering And Management), 2024
|
|
PDF (Tesi_di_laurea)
- Tesi
Accesso riservato a: Solo utenti staff fino al 16 Aprile 2026 (data di embargo). Licenza: 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
Tipo di pubblicazione
URI
![]() |
Modifica (riservato agli operatori) |
