ETD system

Electronic theses and dissertations repository

 

Tesi etd-01172018-224127


Thesis type
Tesi di laurea magistrale
Author
SABA, VALENTINO
URN
etd-01172018-224127
Title
Approcci esatti ed euristici per problemi di packing di poligoni irregolari
Struttura
MATEMATICA
Corso di studi
MATEMATICA
Commissione
relatore Prof. Frangioni, Antonio
Parole chiave
  • nesting problem
  • poligoni irregolari
  • packing
  • ottimizzazione
Data inizio appello
09/02/2018;
Consultabilità
completa
Riassunto analitico
In questo lavoro di tesi indagheremo i cosiddetti cutting and packing problems (C&amp;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&#39;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&#39;area degli oggetti posizionati nel contenitore o ancora la minimizzazione del numero di contenitori utilizzati.<br>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&#39;interno dei bordi del contenitore senza intersecarsi gli uni con gli altri. I secondi, invece, consistono nella selezione dei pezzi da posizionare all&#39;interno del contenitore o nello spostamento dei pezzi in posizioni migliori, e nell&#39;ordine con cui vengono posizionati. <br>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 &#34;migliore&#34;, 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&#39;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.<br>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.
File