• nesting problem
• poligoni irregolari
• packing
• ottimizzazione

In questo lavoro di tesi indagheremo i cosiddetti cutting and packing problems (C&P) con pezzi bidimensionali di forma irregolare, in alcuni casi chiamati anche nesting problems. Questi problemi hanno come obiettivo quello di posizionare degli oggetti bidimensionali di forme irregolari all'interno di uno o più contenitori, con lo scopo di ottimizzare un qualche obiettivo, come ad esempio la minimizzazione della lunghezza del posizionamento, la massimizzazione dell'area degli oggetti posizionati nel contenitore o ancora la minimizzazione del numero di contenitori utilizzati.
Lo scopo di questo lavoro non è quello di fornire un racconto cronologico o esaustivo della letteratura, quanto piuttosto tracciare un percorso che attraversi i principali approcci risolutivi e geometrici. Scomporremo, quindi, il problema in due parti principali: la componente geometrica e gli approcci risolutivi. La prima ha come scopo quello di risolvere il problema geometrico sottostante, cioè in una soluzione ammissibile i pezzi devono essere posizionati all'interno dei bordi del contenitore senza intersecarsi gli uni con gli altri. I secondi, invece, consistono nella selezione dei pezzi da posizionare all'interno del contenitore o nello spostamento dei pezzi in posizioni migliori, e nell'ordine con cui vengono posizionati.
Abbiamo suddiviso gli approcci risolutivi in costruttivi, migliorativi, metaeuristiche ed esatti. Gli approcci costruttivi costruiscono una soluzione ammissibile un pezzo alla volta, i migliorativi partono da una soluzione completa ed ammissibile e apportano iterativamente piccole modifiche per ottenere una soluzione "migliore", le metaeuristiche sono strategie generali, indipendenti dal problema specifico a cui vengono applicate, che guidano il processo di ricerca di una buona soluzione, ed infine gli approcci esatti si caratterizzano perché fanno uso al loro interno di modelli matematici. All'interno di uno specifico approccio queste quattro categorie non si escludono mutuamente, anzi spesso convivono in uno stesso algoritmo che può essere scomposto in una o più tra le quattro categorie. Ognuna delle categorie è poi ulteriormente suddivisa in base alle rotazioni consentite sui pezzi, cioè nessuna rotazione, un numero finito o un numero arbitrario di rotazioni.
La combinazione di modelli matematici e tecniche euristiche in un unico algoritmo, talvolta chiamati matheuristic algorithms, non è ancora largamente studiata perciò riteniamo possa essere una delle più interessanti linee di ricerca per il futuro.