Approcci esatti ed euristici per problemi di packing di poligoni irregolari

Università di Pisa

Facoltà di Scienze Matematiche, Fisiche e Naturali

Corso di Laurea in Matematica

Approcci esatti ed euristici per problemi

di packing di poligoni irregolari

09 febbraio 2018

Tesi di Laurea Magistrale

Candidato

Valentino Saba

Relatore

Prof. Antonio Frangioni

Introduzione

Il presente lavoro di tesi nasce dall'esigenza di indagare i cosiddetti cutting and packing problems (C&P) con pezzi bidimensionali di forma irregolare, in alcuni casi chiamati anche nesting problems. In breve, questi problemi hanno come obiettivo quello di posizionare degli oggetti bidimensionali di forme irrego-lari all'interno di uno o più contenitori, con lo scopo di ottimizzare un qualche obiettivo. Quest'ultimo può essere ad esempio quello di minimizzare la lunghezza del posizionamento oppure massimizzare l'area degli oggetti posizionati nel contenitore, o ancora minimizzare il numero di contenitori utilizzati. La questione che ha dato origine alla nostra ricerca è quella che riguarda il posizionamento del maggior numero di oggetti bidimensionali di forma irregolare all'interno di un contenitore rettangolare. Tutta-via, in letteratura questo problema non è arontato con frequenza, perciò noi allargheremo il nostro studio ad altri due tipi di problemi maggiormente studiati ed i cui approcci risolutivi possono essere adattati al problema di nostro interesse.

Lo scopo di questo lavoro non è quello di fornire un racconto cronologico o esaustivo della letteratura, piuttosto tracciare un percorso che attraversi i principali approcci risolutivi e geometrici. Scompor-remo, 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 posizio-nati.

Nel capitolo 1 partiremo da una descrizione generale della categoria dei problemi di C&P, concentran-doci via via sul sottoinsieme di problemi oggetto di questa tesi. Daremo inoltre una descrizione delle istanze di test usate dagli approcci in letteratura a cui faremo riferimento durante il terzo capitolo. Nel capitolo 2 descriveremo il problema geometrico che sta alla base dei problemi di C&P, con partico-lare riferimento al nesting problem. Mostreremo rapidamente le principali tecniche di rappresentazione dei pezzi e successivamente esploreremo le soluzioni presenti in letteratura.

Inne nel capitolo 3 descriveremo gli approcci risolutivi al problema di nesting, suddividendo lo studio tra approcci costruttivi, migliorativi, metaeuristiche ed esatti. All'interno di uno specico 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 ulterior-mente suddivisa in base alle rotazioni consentite sui pezzi, cioè nessuna rotazione, un numero nito o un numero arbitrario di rotazioni. Durante il percorso, facendo riferimento alle istanze denite nel primo capitolo, mostreremo i risultati dei test eettuati dagli autori sui principali approcci.

Un ringraziamento particolare va al prof. Antonio Frangioni, la sua guida, la sua pazienza ed i suoi appunti1 _{sono stati di grande aiuto per la stesura di questa tesi.}

1_{http://www.di.unipi.it/optimize/Courses/ROM/1617/Appunti1617.pdf}

Introduzione 1

1 I problemi di Cutting and Packing (C&P) 4

1.1 Il focus della tesi . . . 5

1.2 Le istanze di test . . . 6

2 La componente geometrica 10 2.1 Metodi di rappresentazione a griglia . . . 10

2.2 Metodi di rappresentazione poligonali . . . 11

2.2.1 La D function . . . 12

2.2.2 Il not polygon . . . 13

2.2.2.1 Il calcolo del NFP . . . 14

2.2.3 La phi function . . . 16

2.3 La rappresentazione con cerchi . . . 17

2.4 La letteratura . . . 18

2.4.1 I metodi a griglia . . . 18

2.4.2 I metodi poligonali . . . 19

2.4.3 I metodi con cerchi . . . 21

3 Gli approcci risolutivi 23 3.1 Approcci costruttivi . . . 23 3.1.1 Nessuna rotazione . . . 24 3.1.2 Rotazioni nite . . . 25 3.1.3 Rotazioni continue . . . 28 3.2 Approcci migliorativi . . . 29 3.2.1 Nessuna rotazione . . . 31 3.2.2 Rotazioni nite . . . 32 3.2.3 Rotazioni continue . . . 35 3.3 Metaeuristiche . . . 37 3.3.1 Nessuna rotazione . . . 37 3.3.2 Rotazioni nite . . . 38 3.3.3 Rotazioni continue . . . 39 3.4 Approcci esatti . . . 40 3.4.1 Nessuna rotazione . . . 40 3.4.2 Rotazioni continue . . . 46 Appendices 57 A Un algoritmo di posizionamento basato su una strategia bottom left 58 B Fast neighboorhood search 61 B.0.1 Una formula speciale per l'area dell'intersezione . . . 61

B.0.2 Algoritmi di trasformazione . . . 64

B.0.3 Traslazione di poligoni . . . 67 2

INDICE 3 B.0.4 Rotazione di poligoni. . . 70

I problemi di Cutting and Packing (C&P)

I problemi di cutting and packing (C&P) riguardano, genericamente, la possibilità di ritagliare oggetti piccoli da un oggetto più grande, oppure la possibilità di posizionare oggetti più piccoli all'interno di oggetti più grandi.

Questi problemi hanno radici in diversi contesti industriali, ad esempio nel campo degli indumenti, dei mobili o della lavorazione dei metalli, dove oggetti piccoli devono essere ritagliati da, oppure impac-chettati in, oggetti più grandi.

Partendo dall'insieme generale dei problemi di cutting and packing cercheremo di delineare ed inqua-drare quello preso in considerazione in questo lavoro, in modo da tracciare le linee guida per interpretare i capitoli successivi.

Come descritto inWäscher et al. (2007), la struttura basilare di ogni problema di C&P è la seguente: in presenza di due insiemi di elementi, che per comodità chiameremo A e B, dove A individua l'insieme che comprende gli oggetti grandi (ad es. dei contenitori) e B quello degli oggetti piccoli (da posizionare all'interno dei suddetti contenitori), possiamo scegliere tutti o alcuni elementi di B, da raggruppare in uno o più sottoinsiemi per assegnarli a ciascuno degli elementi di A, in modo tale che gli oggetti piccoli selezionati siano interamente contenuti all'interno di ogni contenitore, e questi non si sovrappongano tra loro, ottimizzando nel contempo una data funzione obiettivo.

Dalla denizione di questi problemi è evidente che risolverli signica trovare la soluzione ad alcuni sottoproblemi: la selezione di oggetti grandi, la selezione ed il raggruppamento degli oggetti piccoli, come assegnare i sottoinsiemi di oggetti piccoli agli oggetti grandi, ottenere un layout con posizioni ammissibili per gli oggetti piccoli.

Wäscher et al. (2007) hanno proposto una classicazione dei problemi di cutting and packing, ri-visitando la classicazione di Dyckho (1990), secondo la quale i problemi di cutting and packing vengono partizionati per:

• dimensionalità: una, due o tre dimensioni,

• obiettivo del problema: minimizzazione dello "spreco" o massimizzazione del "protto",

• oggetti grandi: un singolo contenitore, contenitori multipli ed identici o contenitori multipli e dierenti,

• oggetti piccoli: omogeneità dei pezzi, e forma.

Inoltre,Wäscher et al.(2007) categorizzano la letteratura dal 1995 al 2004, e nella loro ricerca, restrin-gendo il campo al caso bidimensionale con oggetti piccoli di forma irregolare, gli autori si focalizzano su tre tipi di problemi:

• Open Dimension Problem in cui si ha un contenitore rettangolare con larghezza ssa e lunghezza da minimizzare. Questo tipo di problemi viene anche chiamato Strip packing.

1.1 Il focus della tesi 5 • Single Bin-Size Bin Packing Problem in cui, a dierenza del tipo precedente, si hanno più

conteni-tori rettangolari di dimensioni entrambe ssate e l'obiettivo è minimizzare il numero di conteniconteni-tori usati. Questo tipo di problemi viene chiamato anche Bin packing.

• Single Knapsack Problem in cui l'obiettivo è la massimizzazione del valore degli oggetti impac-chettati, dove supponiamo il valore di un pezzo proporzionale alla sua area. Questo tipo di problemi viene chiamato anche Knapsack packing.

In letteratura è molto comune il termine Nesting problem per identicare un problema di C&P bidi-mensionale con oggetti di forma irregolare, in cui c'è un unico contenitore e l'obiettivo è minimizzare la lunghezza del posizionamento. Troveremo diversi nomi con cui i ricercatori lo identicano, alcuni dei termini più comuni sono irregular shape stock cutting, irregular strip packing, nesting, polygon pla-cement, marker making, non-convex cutting stock, 2D packing problems o una qualche combinazione di questi termini.

Bennell and Oliveira (2009) ne danno una denizione ancora più generale:

Un nesting problem è un problema bidimensionale in cui un insieme di pezzi contenenti almeno un pezzo di forma irregolare devono essere posizionati all'interno di un'area senza sovrapposi-zioni, in modo da ottimizzare un obiettivo.

Dalla denizione si evince che l'area di posizionamento può essere costituita da uno o più contenitori, i contenitori possono essere aree chiuse oppure variabili (es: rettangolo con una dimensione libera). Quando i pezzi hanno archi di curva nei lati, nella maggior parte dei casi questi vengono approssimati con un poligono di contenimento nel quale i lati sono formati da tangenti alla curva.

Durante la discussione faremo riferimento ai problemi di nesting principalmente come a problemi bidimensionali con oggetti irregolari del tipo strip packing.

1.1 Il focus della tesi

In questo lavoro esploreremo la letteratura sui problemi di C&P nel caso bidimensionale con oggetti di forma irregolare, alla ricerca di approcci principalmente rivolti alla risoluzione dei tre tipi di problemi enunciati sopra: Strip Packing (SP), Bin Packing (BP) e Knapsack Packing (KP).

Il problema bidimensionale che in origine si vuole studiare riguarda la possibilità di posizionare il maggior numero di oggetti di forma irregolare all'interno di un contenitore rettangolare, in modo da minimizzare lo spazio inutilizzato nel contenitore. Utilizzando la classicazione di Wäscher et al. (2007), questo è un problema Single Knapsack, bidimensionale, con oggetti di forma irregolare. Tra i tre tipi di problemi esiste un legame che consente di sfruttare alcuni degli approcci risolutivi ai problemi di strip packing e bin packing, per risolvere un problema di knapsack packing.

Legame tra SP e KP: supponiamo di risolvere all'ottimo (in modo eciente) il nesting problem con un contenitore rettangolare di lunghezza nita (ovvero un problema KP), e sia L un estremo su-periore delle lunghezze dei posizionamenti, ad esempio L può essere la somma delle lunghezze dei rettangoli di contenimento dei pezzi. Deniamo una funzione f : [0, L] → {true, false} tale che f (l) =true ⇔ esiste un posizionamento ammissibile di lunghezza l. Osserviamo che vale la proprietà seguente: f(l) = true ⇒ f(l0_{) = true ∀l}0 _{> l. Questa proprietà ci consente, dato un errore , di}

applicare la ricerca binaria per trovare la minima lunghezza l per cui f(l) = true (il cui corrispondente posizionamento dei pezzi è la soluzione dello SP), in al più log(L

) passi, avendo la garanzia che la

corrispondente soluzione sia -ottima, ovvero tale che f(l − ) = false. L'algoritmo di ricerca binaria trova una tale soluzione con precisione  in O(log(1

))chiamate a f(l), quindi esso è polinomiale in 1 

a meno di un errore.

Legame tra BP e KP: può essere visto in due fasi; in una prima fase si assegnano gli oggetti a k > 1 bins (contenitori), in una seconda fase verico che l'assegnamento sia ammissibile (ossia risolvo k problemi di KP). Questo non implica che il KP "risolva" il BP, perché gli assegnamenti possibili

sono "tanti", tuttavia date queste premesse è chiaro che esiste un legame tra i due tipi di problemi. Così come è chiaro che, come per il legame tra SP e KP, ogni singolo approccio algoritmico di BP va analizzato per capire se può essere esteso al KP in modo naturale oppure no.

Per quanto riguarda le forme degli oggetti bidimensionali da posizionare nei contenitori, in lette-ratura troveremo principalmente due categorie: regolare ed irregolare. Un oggetto di forma regolare è un poligono regolare, nella maggioranza dei casi un rettangolo, mentre un oggetto è detto irregolare se richiede almeno tre parametri per essere identicato, ad esempio, un cerchio ha bisogno di un unico parametro, il raggio; un rettangolo ha bisogno di due parametri, larghezza ed altezza.

In letteratura troveremo principalmente quattro tipi di oggetti irregolari, in ordine dal più semplice al più complesso: poligoni convessi, poligoni nonconvessi, poligoni nonconvessi senza buchi, poligoni nonconvessi con buchi. Solo in rari casi discuteremo di approcci con poligoni nonconvessi con buchi, ma nella maggioranza dei casi ci concentreremo su approcci con poligoni nonconvessi senza buchi. Infatti, questo tipo di approcci può essere usato nel caso dei poligoni nonconvessi con buchi, prima riempiendo i buchi al meglio e poi ignorandoli.

Per quanto riguarda la forma dei contenitori, come in parte abbiamo già detto sopra, ci concentreremo nella quasi totalità dei casi su approcci con contenitori di forma rettangolare.

1.2 Le istanze di test

Descriviamo in questa sezione le principali istanze di test usate dai paper e citate nel capitolo3. Nelle tabelle 1.1, 1.2 e 1.3 ci sono le istanze di test di EURO Special Interest Group on Cutting and Packing noto come ESICUP, reperibili nel sito web1_.

La tabella1.1riporta le istanze più usate dagli approcci di strip packing in letteratura, con le informa-zioni più importanti. Le istanze maggiormente utilizzate dagli approcci euristici sono: Albano, Dagli, Dighe1, Dighe2, Fu, Jakobs1, Jakobs2, Mao, Marques, Shapes0, Shapes1, Shapes2, Shirts, Swim e Trou-sers. Poichè queste istanze sono sviluppate principalmente per testare gli algoritmi di strip packing, Del Valle et al.(2012) le adattano al loro algoritmo che risolve il problema di knapsack, utilizzando co-me dico-mensione libera da ssare la migliore in letteratura coco-me descritto inGomes and Oliveira(2006). Tra gli approcci esatti, Alvarez-Valdes et al. (2013) testano il loro algoritmo utilizzando alcune delle istanze con meno pezzi usate dagli approcci euristici, come: Dighe2, Fu, Jakobs1, Jakobs2, Poly1a, Three, ThreeP2, ThreeP2W9, ThreeP3, ThreeP3W9, predendo però sottoinsiemi di poligoni di queste istanze. In questo modo ottengono circa 50 istanze di test per il loro algoritmo esatto. Peralta et al. (2017), il cui approccio esatto è descritto nella sezione 3.4.2, testano il loro algoritmo sulle istanze: Albano, Blaz1, Dagli, Jakobs1, Jakobs2, Marques, Poly1a, Poly2a, Poly3a, Poly4a, Poly5a, Poly10a, Poly20a, Shirts, Swim, Trousers.

Le tabelle 1.2 e 1.3 riportano due raggruppamenti di istanze di test utilizzati principalmente negli approcci di bin packing da Lopez-Camacho et al. (2013a,b) ed utilizzati anche da Abeysooriya et al. (2018), in cui ciascuna riga delle due tabelle rappresenta un gruppo di 30 istanze. La prima tabella contiene 540 istanze bidimensionali con pezzi convessi (divisi in 18 gruppi con 30 problemi per ciascuno, ogni problema con un numero dierente di pezzi), mentre la seconda contiene 480 istanze bidimensio-nali in cui alcuni pezzi hanno concavità (divisi in 16 gruppi di 30 problemi ciascuno). La rettangolarità media rappresenta la proporzione tra l'area di ogni pezzo e l'area di un rettangolo orizzontale che lo contiene, e varia nelle istanze tra 0.35 ed 1.0.

Per maggiori informazioni sulle istanze di queste tabelle si veda la pagina web corrispondente del sito ESICUP2_.

La tabella 1.4 contiene quattro delle istanze create da Martins and Tsuzuki (2010), quelle in cui il contenitore è rettangolare. Queste istanze vengono testate successivamente daDel Valle et al.(2012), i quali comparano i risultati con gli autori. Poichè l'approccio risolutivo diMartins and Tsuzuki(2010)

1_{https://paginas.fe.up.pt/~esicup/}

1.2 Le istanze di test 7 ammette rotazioni arbitrarie dei pezzi, gli angoli di rotazione consentiti si riferiscono all'approccio di Adamowicz and Albano(1976).

La tabella 1.5 contiene 8 istanze di test prese dall'industria dell'abbigliamento. Le istanze vengo-no utilizzate nell'approccio di strip packing daWong et al. (2009) nel loro algoritmo genetico in cui i pezzi vengono rappresentati e posizionati per mezzo di una matrice (o griglia).

Inne la tabella 1.6 descrive (con poche informazioni) le istanze broken glass create da Fischetti and Luzzi (2009) nel loro approccio esatto, ed utilizzate anche daAlvarez-Valdes et al. (2013). Le istanze broken glass vengono create simulando la rottura in modo casuale in n pezzi poligonali di un blocco rettangolare di vetro. Questo tipo di istanze è importante perchè si conosce dall'inizio il valore della soluzione ottima, che sarebbe la lunghezza del blocco. Inoltre, i modelli di programmazione intera MIP risultanti sono molto dicili da risolvere.

Tabella 1.1: Istanze di test ESICUP. Problemi di strip packing bidimensionali con pezzi irregolari.

Nome Num. poligonidierenti Num. totalepoligoni Num. mediovertici consentite (Rotazioni◦_{) contenitore}Larghezza

Albano 8 24 7.25 0, 180 4900 Blaz2 4 20 7.50 0, 180 15 Dagli 10 30 6.30 0, 180 60 Dighe1 16 16 3.87 0 100 Dighe2 10 10 4.70 0 100 Fu 12 12 3.58 0, 90, 180, 270a ₃₈ Han 20 23 7.35 0 58 Jakobs1 25 25 5.60 0, 90, 180, 270a ₄₀ Jakobs2 25 25 5.36 0, 90, 180, 270a ₇₀ Mao 9 20 9.22 0, 90, 180, 270a ₂₅₅₀ Marques 8 24 7.37 0, 180b ₁₀₄ Poly1ac _{15 15 4.60 0 40} Poly2a 15 30 4.60 90, 180, 270, 360 40 Poly3a 15 45 4.60 90, 180, 270, 360 40 Poly4a 15 60 4.60 90, 180, 270, 360 40 Poly5a 15 75 4.60 90, 180, 270, 360 40 Poly2b 30 30 4.94 0 40 Poly3b 45 45 4.94 0 40 Poly4b 60 60 4.94 0 40 Poly5b 75 75 4.84 0 40 Shapes0 4 43 8.75 0 40 Shapes1 4 43 8.75 0, 180 40 Shapes2 / Blaz1 7 28 6.29 0, 180 15 Shirts 8 99 6.63 0, 180 40 Swim 10 48 21.90 0, 180 5752 Three 3 3 3.67 0 7 ThreeP2 3 6 3.67 0 7 ThreeP2W9 3 6 3.67 0 9 ThreeP3 3 9 3.67 0 7 ThreeP3W9 3 9 3.67 0 9 Trousers 17 64 5.06 0, 180 79

a_{InGomes and Oliveira(2006) eDel Valle et al.(2012) l'angolo 270}◦_{non viene testato.}

b _{InImamichi et al.(2009) eLeung et al.(2012) vengono testati anche gli angoli 90}◦_{e 270}◦_{, mentre inDel Valle et al.(2012)}

in più l'angolo 90◦

c _{Come si evince dalla descrizione delle istanze nel sito web dell'ESICUP, le Poly1n per n > 1 sono copie multiple della}

Poly1a. Noi riportiamo i nomi per n = 1, . . . , 5, ma in letteratura ne incontreremo altre, come ad esempio Poly10a e Poly20a inPeralta et al.(2017).

Tabella 1.2: Gruppo di istanze di test ESICUP: Terashima1. Problemi di bin packing bidimensionali con pezzi irregolari.

Nome Num. istanze Num. totalepoligoni Rettangolarità media

ConvA 30 30 0.70 ConvB 30 30 0.87 ConvC 30 36 0.68 ConvD 30 60 0.57 ConvE 30 60 0.41 ConvF 30 30 0.59 ConvG 30 36 0.87 ConvH 30 36 0.86 ConvI 30 60 1 ConvJ 30 60 0.83 ConvK 30 54 0.63 ConvL 30 30 0.51 ConvM 30 40 0.55 ConvN 30 60 0.62 ConvO 30 28 0.57 ConvP 30 56 0.49 ConvQ 30 60 0.89 ConvR 30 54 0.63

Tabella 1.3: Gruppo di istanze di test ESICUP: Terashima2. Problemi di bin packing bidimensionali con pezzi irregolari.

Nome Num. istanze Num. totalepoligoni Rettangolarità media

NconvA 30 35-50 0.60 NconvB 30 40-52 0.69 NconvC 30 42-60 0.59 NconvF 30 35-45 0.53 NconvH 30 42-60 0.73 NconvL 30 35-45 0.47 NconvM 30 45-58 0.50 NconvO 30 33-43 0.51 NconvS 30 17-20 0.45 NconvT 30 30-40 0.60 NconvU 30 20-33 0.55 NconvV 30 15-18 0.62 NconvW 30 24-28 0.78 NconvX 30 25-39 0.66 NconvY 30 40-50 0.61 NconvZ 30 60 0.54

1.2 Le istanze di test 9

Tabella 1.4: Istanze di test create daMartins and Tsuzuki(2010) per problemi di knapsack.

Nome Num. totalepoligoni contenitoreLarghezza contenitoreLunghezza Rotazioni

a

consentite (◦₎

Larger First Fails Puzzle 5 400 400 0, 45, 90, 135, 180, 225, 270, 315

Bottom Left Fails Puzzle 5 280 280 0, 45, 90, 135, 180, 225, 270, 315

Small Puzzle 4 100 100 0, 45, 90, 135, 180, 225, 270, 315

Tangram 7 800 800 0, 45, 90, 135, 180, 225, 270, 315

a_{Gli angoli di rotazione si riferiscono ai test eettuati daDel Valle et al.(2012).}

Tabella 1.5: Istanze di test provenienti dall'industria dell'abbigliamento. Problemi di strip packing bidimensionali con pezzi irregolari.

Nome Num. totalepoligoni contenitoreLarghezza

Shirt1 16 48 Shirt2 32 48 Shirt3 48 48 Shirt4 64 48 Swim1 12 60 Swim1 48 60 Swim1 78 60 Swim1 100 60

Tabella 1.6: Istanze di test broken glass create daFischetti and Luzzi (2009). Nome Num. totalepoligoni

Glass1 5

Glass2 7

La componente geometrica

Il primo ostacolo che si incontra arontando il nesting problem è la sua componente geometrica. In una soluzione ammissibile, ogni pezzo deve essere posizionato all'interno del contenitore in modo da non intersecarsi con gli altri pezzi, gli algoritmi devono perciò poter controllare le intersezioni tra i pezzi e che ogni pezzo stia all'interno del contenitore, e questo è un compito complicato per un programma di computer.

Per trovare posizioni ammissibili ogni pezzo deve essere posizionato, eventualmente ruotato o tra-slato e va' controllata l'intersezione con gli altri pezzi già posizionati.

In questo capitolo esporremo i metodi geometrici per rappresentare i pezzi e gestirne le intersezio-ni. Daremo inne una descrizione di come vengono usati basandoci sui principali approcci presenti in letteratura.

2.1 Metodi di rappresentazione a griglia

I metodi di rappresentazione a griglia, di cui possiamo vedere due esempi nelle gure2.1e2.2, dividono il contenitore in zone quadrate di uguale dimensione ed utilizzano una matrice per codicare quali zone sono occupate.

Questa rappresentazione riduce le informazioni geometriche da memorizzare per posizionare ogni pez-zo, ammettendo solo posizioni discrete.

Un vantaggio dei metodi a griglia è che calcolare la distanza di cui un pezzo deve slittare per

ri-(a) Un contenitore (b) Un pezzo (c) Un pezzo posizionato nel conteni-tore

Figura 2.1: Rappresentazioni a griglia diBabu and Babu(2001) tratte daBennel and Oliveira(2008). 10

2.2 Metodi di rappresentazione poligonali 11

Figura 2.2: Rappresentazione di un pezzo diWong et al.(2009)

muovere l'inammissibilità, o anche dove posizionare due pezzi nel contenitore in modo tale che siano in contatto uno con l'altro, è semplice e si riduce a contare un certo numero di celle nella direzione corretta.

Inoltre le rappresentazioni a griglia sono semplici da codicare, possono rappresentare pezzi complessi, con buchi e non convessi come semplici poligoni e sono ragionevolmente veloci quando devono control-lare l'amissibilità del layout.

Uno svantaggio di questi metodi è che non riescono a rappresentare accuratamente i pezzi con angoli non ortogonali ed utilizzano molta memoria rispetto ad altri metodi: infatti per aumentare l'accura-tezza bisogna inttire le griglie e quindi aumentare la dimensione delle matrici e questo comporta un incremento all'uso della memoria durante i calcoli di ammissibilità.

Inoltre, le rappresentazioni a griglia si adattano male alle rotazioni dei pezzi: il modo usuale di ruotare i pezzi rappresentati da matrici (o griglie) è quello di ruotare i pezzi dell'angolo desiderato e riportare nelle matrici questo cambiamento (che è simile a ricalcolare da zero le matrici per un pezzo comple-tamente nuovo). In alternativa è possibile ruotare le matrici stesse, questo si fa facilmente per angoli multipli dell'angolo retto, mentre per angoli dierenti può causare ulteriori problemi, perciò non viene utilizzato.

2.2 Metodi di rappresentazione poligonali

Un'alternativa alle rappresentazioni a griglia è quella di utilizzare i poligoni per rappresentare i pezzi. A dierenza dei metodi a griglia, con una rappresentazione polinomiale la grandezza di un pezzo non inuenza la quantità informazioni necessarie a rappresentarlo, infatti la quantità di informazioni da memorizzare è proporzionale al numero di vertici del poligono e non dipende della grandezza asso-luta dei pezzi o del contenitore.

Inoltre utilizzando la rappresentazione poligonale non è dicile implementare le rotazioni: per ruotare un poligono tutti i suoi vertici devono essere ruotati attorno ad un punto selezionato ed il numero di pezzi con cui bisogna controllare le possibili intersezioni cresce al crescere dei vertici del poligono stesso. La rappresentazione poligonale può essere esatta soltanto se il bordo del pezzo è formato da seg-menti di retta, gli archi di curva vengono approssimati da segseg-menti di retta.

Per gestire l'ammissibilità di un posizionamento o la qualità di un layout, a dierenza dei metodi a griglia, la geometria della rappresentazione non è suciente e perciò bisogna sviluppare altri metodi, come ad esempio la D-function, il not polygon e la phi function, che vedremo in questa sezione.

2.2.1 La D function

La D function è uno strumento ecace per caratterizzare la relazione tra un punto del piano ed un segmento. Questa relazione può essere interpretata in modo da valutare la sovrapposizione tra due poligoni, ovvero: dati due vertici di un poligono che rappresentano un segmento, l'espressione mate-matica della D-function può vericare la posizione relativa di ogni altro vertice rispetto alla retta di supporto del segmento.

Supponendo che l'origine delle coordinate (0, 0) sia nell'angolo in basso a sinistra del contenitore e che i pezzi abbiano i lati orientati in senso orario, la D-function distinguerà tra l'interno e l'esterno del poligono sapendo che l'interno è alla destra e l'esterno alla sinistra del lato orientato.

La D function si denisce come segue:

DABP = (xA− xB)(yA− yP) − (yA− yB)(xA− xP) (2.1)

essa rappresenta la posizione di un punto P con coordinate (xP, xP)rispetto ad un segmento orientato

AB con A = (xA, yA) e B = (xB, yB).

Confrontando la posizione relativa di un segmento orientato (o meglio, della sua retta di supporto) con un punto usando la D function, possono essere dedotte le seguenti conclusioni:

• se il risultato è maggiore di zero, allora il punto è alla sinistra della retta di supporto; • se il risultato è uguale a zero, allora il punto è sulla retta di supporto;

• se il risultato è minore di zero, il punto è alla destra della retta di supporto.

Un esempio è la gura2.3. Per una descrizione approfondita su come calcolare la posizione relativa di due lati orientati utilizzando la D function si può vedere Mahadevan(1984).

Figura 2.3: Interpretazione della D function, presa da Bennel and Oliveira(2008).

Le D function hanno il vantaggio di poter utilizzare le coordinate esatte di rappresentazione dei poli-goni, questo signica che si può utilizzare la rappresentazione oating-point: come eetto collaterale però abbiamo che aumenta il costo computazionale rispetto agli approcci che utilizzano prevalentemen-te numeri inprevalentemen-teri, come ad esempio la rappresentazione a griglia. Inoltre ogni volta che una posizione viene cambiata bisogna rieettuare tutti i calcoli e i controlli di ammissibilità: questo rende dicile l'applicazione a metodi iterativi di ricerca poichè aumenta considerevolmente il tempo di calcolo. Se invece si adottano algoritmi costruttivi per la ricerca di una soluzione, si possono usare le D-function in modo eciente per risolvere i problemi geometrici del nesting problem.

Se ne può vedere un'applicazione nell'algoritmo esatto di Peralta et al. (2017), in cui le linee rette che separano due poligoni vengono chiamate separation lines.

Una descrizione maggiormente dettagliata della D function si può trovare in Bennel and Oliveira (2008).

2.2 Metodi di rappresentazione poligonali 13 2.2.2 Il not polygon

Il not polygon, anche detto NFP, è stato introdotto per primo da Art (1966) ed è diventato un'op-zione sempre più popolare nella risoluun'op-zione dei problemi geometrici del nesting problem, poichè è più eciente della D function e lavorando direttamente con i lati del poligono condivide con questo metodo l'accuratezza dei calcoli. Esso viene prevalentemente usato negli approcci risolutivi al nesting problem che non permettono le sovrapposizioni dei poligoni nelle fasi intermedie dell'algoritmo.

Formalmente possiamo denire il not polygon tra due poligoni P e Q in questo modo: Denizione 2.1 (not polygon):

Siano P e Q due poligoni e sia v il punto di riferimento di Q. Il bordo del not polygon è la traccia di v, quando Q viene fatto scorrere adiacente a P senza rotazioni nè sovrapposizioni.

Esso si indica con NFPP Q.

Si può vederne un esempio nella gura2.4a. Se il pezzo P viene posizionato nel punto u ed il pezzo

(a) Il not polygon tra due pezzi Pie Pj ottenuto

con uno schema orbitante (b) L'innert polygon tra un pezzo Pcontenitore j ed un

Figura 2.4: Il not polygon e l'innert polygon in due immagini prese daSato et al. (2012) Q viene posizionato nel punto v (u e v sono quindi i punti di riferimento rispettivamente di P e Q), il problema di determinare se P e Q si intersecano si riduce ad un test di inclusione di un punto in un poligono, cioè bisogna determinare se il punto denito da v − u sta all'interno di NFPP,Q oppure

no: se v − u si trova all'interno di NFPP,Q allora i due poligoni si intersecano; se invece v − u si trova

nel bordo di NFPP,Q i due poligoni sono adiacenti; inne se v − u si trova all'esterno del NFPP,Q i

due poligoni sono disgiunti. Se, come spesso accadrà più avanti durante la descrizione degli approcci, il NFPP,Q si calcola prendendo come punto di riferimento il punto di riferimento u di P , allora per

determinare se P e Q si intersecano bisogna solo determinare se il punto di riferimento v di Q è dentro o fuori dal NFPP,Q, perchè in questo caso u = 0, cioè u coincide con l'origine degli assi nelle coordinate

del not polygon.

Si può vedere un altro esempio di not polygon nella gura 2.5.

Se P e Q hanno rispettivamente s e t lati, il numero di lati nel loro NFP sarebbe dell'ordine di O(s2_t2_).

Un'altra proprietà del not polygon tra due pezzi P e Q, NFPP,Q è che, se si scambia l'ordine dei

due poligoni, scegliendo quindi P come il poligono che scorre adiacente a Q, NFPQ,P è equivalente a

NFPP,Q ruotato di 180◦.

Lo svantaggio più importante del NFP è che deve essere calcolato per ogni coppia di poligoni. Se i po-ligoni non devono ruotare, allora questo non è un grave problema poichè il calcolo dei NFP può essere eettuato in una fase di preprocessing in un tempo ragionevole (se il loro numero non è troppo alto): se n è il numero dei poligoni bisogna calcolare n2 _{NFP. Se invece ci sono un numero nito di angoli}

di rotazione permessi per ogni poligono, allora bisogna calcolare molti più NFP: ad esempio, 4 angoli richiedono il calcolo di (4 · 2 · n)2 _{NFP. Se inne fosse permessa la rotazione arbitraria dei poligoni,}

Figura 2.5: Il not polygon in un'immagine di Dowsland et al.(2002).

allora bisognerebbe scegliere un numero abbastanza grande di angoli permessi, così da calcolare gli NFP per quegli angoli ed ottenere perciò una soluzione approssimata.

Nonostante questi svantaggi il NFP è un potente strumento per la risoluzione del problema delle intersezioni del nesting problem.

Un concetto legato al NFPP,Q è l'innert polygon (indicato con IFPP,Q), generato usando un

ap-proccio simile.

Esso rappresenta l'insieme delle posizioni ammissibili di un poligono Q all'interno di un altro poligono P. Come con il NFPP,Q, la traccia del punto di riferimento di Q mentre scorre rimanendo dentro P

denisce il IFPP,Q. Si può vedere un esempio di innert polygon nella gura2.4b.

Se il punto di riferimento di Q sta dentro o nel bordo del IFPP,Q il poligono Q è dentro P . Se è fuori

dal IFPP,Q il poligono Q non è interamente contenuto in P .

Alcuni approcci risolutivi utilizzano l'innert polyogn come strumento per determinare il posiziona-mento di un poligono relativamente ad una soluzione parziale già posizionata all'interno del contenitore. Quando il poligono più grande P è un rettangolo, l'innert polygon tra un poligono P e Q viene chiamato anche innert rectangle e si indica con IFRP,Q.

2.2.2.1 Il calcolo del NFP

Il not polygon (NFP) è l'approccio principalmente utilizzato in letteratura per controllare se due poligoni irregolari (ricordiamo che consideriamo solo poligoni semplici, cioè poligoni i cui lati non si intersecano tra loro) si intersecano o no, poiché è riconosciuto essere il metodo più eciente per gestire i problemi geometrici associati. Ci sono diversi modi di denire e calcolare il NFP tra due poligoni, ma i principali possono essere divisi in tre categorie, come specicato ad esempio daBennel and Oli-veira (2008) ma anche daBennell and Song (2008): il metodo orbitante, le somme di Minkowski e la decomposizione.

cal-2.2 Metodi di rappresentazione poligonali 15 colare. Cuninghame-Green(1989) crea un semplice algoritmo per calcolare il NFP per poligoni pura-mente convessi: la tecnica si basa sull'ordinare i lati dei due poligoni insieme in base alla pendenza e ricostruire il NFP attraverso questo insieme ordinato di lati. Un'idea chiave sviluppata in quel lavoro è che i dierenti ruoli dei due poligoni danno orientazioni opposte per i loro lati. Una seconda idea importante è che il NFP di poligoni convessi è convesso ed è una replica dei lati dei due poligoni con orientazioni opposte, ordinati per pendenza. Se invece uno o entrambi i poligoni sono non convessi il calcolo del NFP si complica.

Diamo una breve descrizione dei tre metodi per il calcolo del NFP.

Il metodo orbitante. In questo metodo si descrive il NFP come il movimento di un poligono che scorre lungo il bordo dell'altro poligono. L'approccio orbitante tenta di simulare questo scorrimento: se entrambi i poligoni sono convessi questo è equivalente ad ordinare i lati per pendenza e costruire il poligono. Se però uno dei due poligoni ha delle concavità un poligono potrebbe non riuscire a scorrere nel bordo dell'altro senza sovrapporsi. Mahadevan (1984) sviluppa un algoritmo per superare questa dicoltà basato sull'ordinamento dei lati e vertici corrispondenti. Il difetto principale di questo al-goritmo è che identica solamente il bordo esterno del NFP, eventuali buchi all'interno non vengono considerati.

Burke et al. (2007) modicano l'approccio migliorando l'ecienza computazionale e permettendo l'i-denticazione dei buchi.

Le somme di Minkowski. E' la tecnica maggiormente utilizzata in letteratura per il calcolo del NFP. Diamo la denizione di somma di Minkowski in Rn _{per iniziare:}

Denizione 2.2:

Siano A e B due sottoinsiemi di Rn_{. La somma di Minkowski di A e B è denita come:}

S = A ⊕ B = {a + b|a ∈ A, b ∈ B}. Se Ab denota l'insieme A traslato del vettore b allora vale che

S = A ⊕ B = [

b∈B

Ab.

Se A e B sono due poligoni, diversi autori (ad esempio Stoyan and Ponomarenko (1977) e Mi-lenkovic et al. (1992)) attraverso calcoli di algebra vettoriale fanno vedere che A ⊕ −B è equivalente al NFPAB. Poichè seguiamo la convenzione che i poligoni hanno i lati orientati in senso antiorario,

−B = {−b | b ∈ B}è semplicemente B con i lati orientati in senso orario.

Poichè il NFP e le somme di Minkowski sono equivalenti, ogni meteodo per calcolare queste somme può essere utilizzato per calcolare i NFP. Un approccio che sfrutta le somme di Minkowski viene utilizzato daGhosh (1991) il quale osserva che la somma di Minkowski di due poligoni può essere ottenuta come funzione dei lati che compongono i loro bordi; nel lavoro dell'autore vengono poi enunciati diversi teoremi Boundary Addition per gestire i casi di poligoni convessi e non.

Approcci più recenti che migliorano l'ecienza del calcolo del NFP si trovano in Bennel et al.(2001), Bennell and Song(2008) eBehar and Lien (2011).

La decomposizione. In questo metodo si tenta di decomporre i due poligoni in parti più sem-plici e calcolare il NFP attraverso queste parti. Ci sono principalmente due modi per decomporre i poligoni: decomposizione convessa e decomposizione "star-shaped".

Watson and Tobias (1999) e più recentemente Agarwal et al. (2002) decompongono poligoni sem-plici in sotto-poligoni convessi: il principio di questo approccio è quello di calcolare i NFP di coppie di sotto-poligoni convessi ciascuno appartenente ad un poligono distinto (come descritto da Cuninghame-Green(1989) il calcolo del NFP di due poligoni convessi è facile ed è un poligono convesso).

ci sono un numero dispari di vertici concavi, allora l'ultimo taglio viene eettuato tra il vertice con-cavo ed un vertice convesso. I NFP tra le coppie di sotto-poligoni convessi così ottenuti si calcolano facilmente con la tecnica dell'ordinamento dei lati di Cuninghame-Green(1989), inne ricombinano i NFP ottenuti per ottenere il NFP dei due poligoni iniziali. Sebbene la decomposizione faciliti i calcoli degli NFP tra poligoni convessi essa genera anche dei problemi: bisogna trovare una decomposizione eciente ed una procedura robusta per ricombinare i NFP ottenuti: Agarwal et al.(2002) investigano questi problemi nel caso della decomposizione convessa.

Li and Milenkovic (1995) decompongono i poligoni in sotto-poligoni shaped: un poligono star-shaped è un poligono che contiene almeno un punto, chiamato "kernel", tale che un segmento di retta tracciato tra questo punto ed un qualsiasi punto del bordo sia interamente contenuto nel poligono. Essi mostrano anche che la somma di Minkowski di due poligoni star-shaped è star-shaped.

2.2.3 La phi function

Le Phi-function sono espressioni matematiche concepite e sviluppate da Stoyan et al. (2001), Stoyan et al.(2004) e successivamente utilizzate anche daChernova et al. (2010) eStoyan et al.(2016), il cui scopo è quello di rappresentare le mutue posizioni di due oggetti (poligoni in questo contesto). Il NFP e la Phi-function sono concetti legati: il NFP corrisponde alla Phi-function di livello zero.

In questa sezione illustreremo semplicemente il concetto e qualche sua applicazione.

Figura 2.6: Una rappresentazione dei punti di contatto tra due cerchi, in un'immagine presa daBennel and Oliveira(2008).

Il valore della Phi-function è maggiore di zero se gli oggetti sono separati, uguale a zero se i loro bordi si toccano e minore di zero se si sovrappongano. Quando la funzione è normalizzata il suo valore è la distanza euclidea tra i due oggetti, altrimenti è una stima della distanza.

Gli autori hanno derivato la Phi-function per gli oggetti basici, ovvero cerchi, rettangoli, poligoni re-golari, poligoni convessi. Tutti questi oggetti hanno rette e cerchi come forme primitive. Le forme che non sono oggetti basici possono essere rappresentate come unione, intersezione o complementare di questi oggetti basici. Osserviamo che è permessa la sovrapposizione degli oggetti basici quando sono usati per costruire oggetti più complessi.

Alla base delle Phi-function c'è la geometria analitica. Al loro livello base, le Phi-function usano le forme primitive per calcoli geometrici come la distanza tra un punto ed una retta o tra un punto ed un cerchio. Inoltre insiemi di queste forme primitive vengono aggregati per denire gli oggetti basici. Le combinazioni di oggetti basici (e primari) sono utilizzate per formare gli oggetti composti, che ci aiutano a rappresentare i pezzi. Per confrontare le posizioni relative di oggetti composti si devono confrontare le posizioni relative per ognuno degli oggetti basici che compongono ciascuno degli oggetti composti: si richiede che tutte le coppie di oggetti basici di diversi oggetti composti non si sovrappon-gano. Questo signica che, per assicurare la non intersezione si devono confrontare gli oggetti primari

2.3 La rappresentazione con cerchi 17 che compongono i basici di pezzi diversi, e questi confronti devono dare esito positivo.

Facciamo un esempio di applicazione delle Phi-function con oggetti basici: consideriamo il caso di due cerchi. Per fare in modo che i due cerchi non si intersechino, la distanza tra i centri dei due cerchi deve essere maggiore o uguale alla somma dei loro raggi. Si può vederne una rappresentazione nella gura2.6.

Supponiamo quindi di avere due cerchi nel piano: il cerchio 1 di raggio r1 ed il cerchio 2 di

rag-gio r2. Supponiamo che il cerchio 1 sia ssato con coordinate del centro (0, 0), allora l'equazione

p

x2_{+ y}2 _{= r}

1+ r2 descrive tutte le mutue posizioni (x, y) del cerchio 2 (cioè del suo centro) tale che

i due cerchi si tocchino ma non si sovrappongano. Se i cerchi fossero separati avremmo px2_{+ y}2 _{> r}

1+ r2, e la dierenza sarebbe la distanza euclidea

tra i due cerchi.

La Phi-function in questo caso può essere denita come: φ(x, y) = px2_{+ y}2_{− (r}

1+ r2).

Se rimuoviamo la condizione che il cerchio 1 è ssato nel punto (0, 0) e poniamo che invece abbia coordinate (x1, y1) ed analogamente poniamo le coordinate del cerchio 2 come (x2, y2), allora

dobbia-mo traslare entrambi i cerchi di (−x1, −y1) per far sì che il cerchio 1 sia posizionato nell'origine ed il

cerchio 2 abbia la stessa precedente posizione relativa.

Possiamo quindi denire la Phi-function per due cerchi in posizioni arbitrarie come: φ(x1, y1; x2, y2) =

p

(x2− x1)2+ (y2− y1)2− (r1+ r2).

Quando φ(x, y) = 0, dove x = x2− x1, y = y2− y1, abbiamo la Phi-function di livello zero, che coincide

con il NFP.

Uno dei problemi principali (se non il principale) del metodo delle Phi-function è che aumenta il numero di oggetti usati, poichè un oggetto composto contiene diversi oggetti basici e ciascuno di questi contiene diverse forme primitive.

In conclusione, questo strumento sembra avere un grande potenziale nel contribuire alla risoluzione del nesting problem, tuttavia richiede ancora ricerche volte a migliorarne i difetti, e poichè il processo di ottenimento delle phi function ha funto da barriera non viene ancora largamente adottato.

2.3 La rappresentazione con cerchi

Una rappresentazione dei poligoni alternativa che supporta posizionamenti e rotazioni continue è la rappresentazione con cerchi, nella quale ogni pezzo viene rappresentato con un insieme di cerchi. Gli algoritmi che utilizzano questo tipo di rappresentazione risolvono modelli matematici in cui l'interse-zione tra pezzi diventa in intersel'interse-zione tra cerchi che rappresentano pezzi distinti.

Un tipo di rappresentazione richiede il calcolo della copertura con cerchi del poligono, visibile in un esempio nella gura2.7. I problemi di copertura sono problemi di minimizzazione in cui l'obiettivo è quello di ricoprire una regione con uno o più oggetti.

Quando si usa la copertura con cerchi per ottenere una rappresentazione che può essere utilizzata durante il problema di nesting, devono essere soddisfatte alcune caratteristiche, questo richiede che si raggiunga un compromesso tra la copertura totale della regione con un certo grado di approssimazione dei suoi contorni e la minimizzazione del numero di cerchi utilizzati.

Attraverso questa rappresentazione è semplice gestire le rotazioni, infatti per ruotare un pezzo è su-ciente ruotare i centri dei cerchi che lo ricoprono. Il calcolo delle intersezioni è semplice poichè bisogna confrontare le distanze tra cerchi di pezzi dierenti e i loro raggi. Normalmente i cerchi dello stesso

(a) Copertura con cerchi tratta da Rocha

et al.(2015). (b) Coperture con cerchi tratta da(2014). Jones

Figura 2.7: Coperture con cerchi.

insieme (cioè quelli che ricoprono lo stesso pezzo) sono liberi di sovrapporsi tra loro, mentre non è consentita la sovrapposizione tra cerchi di insiemi dierenti.

Sfortunatamente il maggior svantaggio di questa rappresentazione è che per ottenere una buona qualità del layout bisogna aumentare il numero di cerchi utilizzati per ricoprire ogni poligono, e questo fa si che cresca il costo computazionale degli algoritmi che la utilizzano.

2.4 La letteratura

Descriviamo qua gli approcci geometrici più rilevanti in letteratura suddivisi per tipo di rappresenta-zione ed evidenziamo gli elementi più importanti di ogni approccio raggruppandoli dove possibile per caratteristiche comuni.

2.4.1 I metodi a griglia

Dierenti autori hanno dierenti schemi con i quali codicare le informazioni in una matrice, nella maggior parte dei casi guidati dall'algoritmo di posizionamento che utilizza queste informazioni geo-metriche.

Lo schema di codica della matrice utilizzato da Babu and Babu (2001), di cui si può vedere un esempio nella gura 2.1, varia a seconda che sia il contenitore o un pezzo. Il contenitore, che può avere una forma qualsiasi e contenere buchi, viene ricoperto con una griglia immaginaria di forma rettangolare. Questa viene poi suddivisa in quadrati di eguali dimensioni chiamati pixel. Il valore di un pixel è 0 se il contenitore è interamente all'interno del quadrato. Altrimenti il valore del quadrato è un intero positivo assegnato in questo modo: si parte da 1 nel quadrato più a destra che sia diverso da zero, e andando verso sinistra iterativamente si aggiunge 1.

Dato un pezzo di forma irregolare da posizionare, questo viene ricoperto da una matrice rettangolare per avere un punto di riferimento: il pezzo risulterà quindi interamente contenuto nella griglia. Il valore di un pixel è 0 se il pixel è interamente o parzialmente contenuto all'interno del pezzo. Altrimenti, il valore del pixel è un numero intero positivo che parte da 1 nel pixel che intersecano il pezzo più a destra della matrice, e viene incrementato di uno man mano che si procede verso sinistra nella matrice. Un benecio di questo approccio si ha utilizzando la regola di posizionamento bottom left 3.1, infatti se si vuole posizionare il pezzo all'interno del contenitore senza sovrapposizioni con altri pezzi già po-sizionati è possibile saltare più celle in un'unica iterazione, il valore del pixel indica infatti di quante celle bisogna spostarsi verso destra.

Di contro, rispetto ad altri approcci di rappresentazione a griglia, è più complesso tenere aggiornata la matrice.

2.4 La letteratura 19

Dierente è la codica adottata da Wong et al. (2009), dove un pixel vale 1 se è occupato, 0 al-trimenti (si veda la gura 2.2). Per aumentare la qualità del layout senza compromettere il costo computazionale, gli autori propongono un approccio a due fasi per posizionare i pezzi descritto nella sezione 3.1.1: in una prima fase si posiziona più in basso a sinistra possibile il pezzo, mentre in una seconda fase si compatta la matrice del pezzo con l'eventuale sottomatrice dei pezzi già posizionati. 2.4.2 I metodi poligonali

Elkeran (2013), Leung et al. (2012), Imamichi et al. (2009) e Egeblad et al. (2007) risolvono il pro-blema della minimizzazione della sovrapposizione (overlap minimization problem). Per il calcolo della penalizzazione da assegnare alla sovrapposizioneEgeblad et al.(2007) utilizzano l'area dell'intersezione tra coppie di poligoni come penalità. Essi sviluppano un algoritmo per ridurre la sovrapposizione, che ha complessità temporale polinomale e che determina la traslazione di un poligono che ne minimizza l'intersezione. L'algoritmo si chiama Fast neighboorhood search ed è stato sviluppato inizialmente da Nielsen and Odgaard (2003). Egeblad et al. (2007) successivamente ne propongono una variante. Le due versioni si possono trovare nelle appendici BeC.

Figura 2.8: La relazione tra il not polygon NFPPi,Pj e la penetration depth δ(Pi ⊕ xi, Pj ⊕ xj), in

un'immagine presa da Imamichi et al.(2009).

Elkeran (2013), Leung et al. (2012) e Imamichi et al. (2009) utilizzano una formulazione dierente del problema della minimizzazione della sovrapposizione, permettono infatti anche la protrusione dei pezzi dal bordo del contenitore. Questi autori utilizzano la profondità dell'intersezione (penetration depth) come penalità da assegnare alla sovrapposizione. La profondità dell'intersezione δ(Pi, Pj)

(an-che detta penetration depth o intersection depth) di una coppia di poligoni Pi, Pj è la minima distanza

di traslazione da applicare per separarli. Formalmente è denita così:

δ(Pi, Pj) = min{kzk | Pi∩ (Pj⊕ z) = ∅, z ∈ R2}, (2.2)

dove k · k denota la norma euclidea, e la funzione di traslazione ⊕ è denita così: dato un poligono P ed un vettore di traslazione v = (vx, vy) allora P ⊕ v := {(px+ vx, py+ vy) | p0 ∈ P }.

δ(Pi, Pj)può essere calcolato utilizzando il not polygon: se il punto di riferimento Oj di Pj è

all'inter-no di NFPPi,Pj, allora δ(Pi, Pj) è uguale alla distanza minima tra Oj e NFPPi,Pj, altrimenti è uguale

a 0.

La variabile z nella denizione 2.2 è detto vettore di intersezione (intersection vector o penetration vector), e può essere ottenuto nel processo di calcolo di δPi,Pj. Quando la profondità dell'intersezione

è zero il vettore di penetrazione è (0, 0); altrimenti, potrebbe non essere unico, ed in questo caso pos-siamo scegliere uno qualsiasi dei z tale che kzk sia minimo come vettore di penetrazione.

La relazione tra il not polygon e la penetration depth si può osservare nella gura2.8: due poligoni Pie Pj possono essere separati traslando il punto di riferimento di Pj in un punto x0 nel bordo del not

polygon. Le frecce solide e tratteggiate sono esempi di traslazioni di Pj verso il bordo del not polygon,

mentre i poligoni con i bordi tratteggiati rappresentano i movimenti di Pj quando viene traslato dalle

frecce. La freccia solida x00_{− (x}

j − xi) corrisponde alla minima distanza di traslazione, e ci da la

penetration depth δ(Pi⊕ xi, Pj⊕ xj). Per approfondimenti vedereImamichi et al.(2009) eLeung et al.

(2012).

Elkeran (2013) utilizza la metaeuristica guided cuckoo search per muovere un poligono con orien-tazione ssa verso una posizione di minore sovrapposizione.

Imamichi et al. (2009) e Leung et al. (2012) utilizzano entrambi lo stesso algoritmo di separazione esatto (quello creato daImamichi et al.(2009)), che fa uso di un modello nonlineare non vincolato de-scritto nella sezione3.4.1. In questi algoritmi gli autori, per ottenere la funzione obiettivo del problema di minimizzazione della sovrapposizione, calcolano la penetration depth ed il suo gradiente usando il not polygon.

Negli algoritmi migliorativi diGomes and Oliveira(2002),Dowsland et al.(2002),Gomes and Oliveira (2006), Sato et al. (2012) e Abeysooriya et al. (2018) descritti nelle sezioni 3.2.2 e 3.2.3 gli autori utilizzano il not polygon e innert rectangle, visibili entrambi in un esempio nella gura 2.4, per posizionare i pezzi nel layout senza sovrapposizioni, individuando per ogni pezzo un insieme di punti nel layout che costituiscono l'insieme di punti che generano posizionamenti ammissibili per il pezzo. Gomes and Oliveira (2002) e Sato et al. (2012) usano lo stesso insieme nito di punti, ma i primi ne considerano solamente il vertice bottom left, mentre i secondi eettuano la ricerca del punto di posizionamento tra elementi degeneri dell'insieme, che rappresentano posizioni in cui il pezzo da posi-zionare è incastrato in una o entrambe le direzioni agli altri pezzi. Questi elementi si dividono in lati e vertici degeneri. Se il posizionamento avviene in un lato degenere, il pezzo si potrà muovere nel layout solo in una direzione; se invece avviene in un vertice degenere, che rappresenta un posizionamento sso, non è possibile nessun movimento.

L'euristica di posizionamento di Dowsland et al. (2002), descritta nell'appendice A, combina il NFP con la regola bottom-left. Essa simile a quella di Gomes and Oliveira (2002) ed è sviluppata in modo indipendente dagli autori.

Abeysooriya et al. (2018) considerano la soluzione parziale mj all'iterazione j come un unico pezzo.

L'insieme delle posizioni ammissibili all'interno del contenitore C all'iterazione j consiste nell'interse-zione tra il bordo di NFPC,mj e IFPC,Pj, che rappresenta tutte le posizioni ammissibili in cui Pj tocca

mj.

Gomes and Oliveira (2006) invece, come nel gruppo di approcci che arontano l'overlap minimization problem, consentono la sovrapposizione tra i pezzi. In particolare utilizzano due modelli lineari di compattamento e separazione (compaction and separation approach): uno che compatta un layout ed in cui non è ammessa la sovrapposizione tra pezzi, ed un altro che consente la sovrapposizione e cerca di rimuoverla. Questi modelli rappresentano i pezzi con le coordinate nel piano dei punti di riferimento, e gestiscono la sovrapposizione attraverso vincoli che ne misurano l'entità utilizzando il not polygon. Del Valle et al. (2012) cercano di posizionare ogni poligono nel bordo della soluzione parziale già posizionata, in modo tale da minimizzare l'area della chiusura rettangolare e della chiusura convessa della nuova soluzione. Essi utilizzano il calcolo del not polygon con il metodo orbitante descritto in 2.2.2.1 per calcolare i posizionamenti ammissibili di ogni pezzo, e la procedura di ricerca estesa di Adamowicz and Albano (1976) per il calcolo del punto migliore: per ogni vertice del not polygon calcolano il punto nel lato uscente dal vertice che minimizza la chiusura rettangolare dei due poligoni. Tra tutti i punti trovati, l'estensione dell'algoritmo di Del Valle et al. (2012) calcola il punto che mi-nimizza l'area della chiusura convessa.

2.4 La letteratura 21

Nell'algoritmo migliorativo di Burke et al. (2006), descritto nella sezione 3.2.2 la rappresentazione dei pezzi include gli archi circolari e i buchi. Gli autori propongono un nuovo algoritmo di posiziona-mento di tipo bottom left ll. La tecnica di rimozione dell'intersezione risolve la sovrapposizione tra due pezzi cercando una nuova posizione nella direzione verticale continua. Se questa ricerca non ha esito positivo, si scorre di un passo ssati nella direzione orizzontale e si cerca di posizionare il pezzo senza sovrapposizioni nella successiva colonna.

Oliveira et al. (2000) e Bennell and Song (2010) utilizzano il not polygon insieme ad una tecnica dierente dalla bottom left per posizionare iterativamente ciascun pezzo nel contenitore. Essi costrui-scono la soluzione parziale e la considerano come un unico poligono. Ciascun pezzo viene posizionato nella migliore posizione (a seconda dei criteri scelti) nel bordo della soluzione parziale, tuttavia l'in-terno bordo della soluzione parziale è disponibile a patto che la dimensione della soluzione non ecceda le dimensioni nel contenitore. In Oliveira et al.(2000) il not polygon tra il pezzo da posizionare e la soluzione parziale viene calcolato utilizzando la tecnica di sliding descritta in2.2.2.1. Sebbene questa tecnica sia semplice, essa non raggiunge grandi qualità di nesting per la coppia di pezzi. Inoltre gli autori non riempiono i buchi che si formano nel layout. Bennell and Song(2010) apportano diversi mi-glioramenti a questo algoritmo, tra cui la possibilità di riempire i buchi presenti nel layout utilizzando l'innett polygon. Essi calcolano inoltre il not polygon in maniera più precisa utilizzando la tecnica delle somme di Minkowski descritta in2.2.2.1.

Anche Hi and M'Hallah (2003) e Liu and He (2006) utilizzano strategie di posizionamento die-renti dalla bottom left. Hi and M'Hallah(2003) utilizzano tecniche geometriche basate su proiezioni dei lati dei poligoni da posizionare nei lati dei poligoni già posizionati, per determinare la sovrapposi-zione o meno di poligoni nel contenitore. Ogni poligono già posizionato dà origine a cinque candidati punti di posizionamento per il pezzo, dai quali si sceglie quello ammissibile che riduce maggiormente la lunghezza del layout. Liu and He(2006) calcolano invece l'innert polygon tra il pezzo ed il contenitore mentre questo scorre senza uscirne lungo il bordo, usando come punto di riferimento il baricentro del pezzo. Cambiando angolo di rotazione chiaramente cambia anche l'innert polygon: gli autori scelgono l'angolo rotazione che produce il centro di gravità più basso. Dopo ogni posizionamento l'area del pez-zo da posizionare viene sottratta dall'area del contenitore e l'algoritmo continua con il pezpez-zo successivo. Dierente è il discorso di come gli approcci risolutivi basati su modelli di programmazione lineare utilizzano il not polygon. Gli approcci descritti nella sezione 3.4.1 di Li and Milenkovic (1995), Bennel and Dowsland(2001),Gomes and Oliveira(2006),Fischetti and Luzzi(2009) eAlvarez-Valdes et al.(2013) utilizzano tecniche geometriche allo scopo di caratterizzare la regione esterna ad ogni not polygon per trovare il miglior posizionamento di due pezzi senza intersecarsi. Per approfondimenti si veda la sezione3.4.1.

Inne, il modello nonlineare presentato da Peralta et al.(2017) descritto nella sezione degli approcci esatti con rotazioni continue 3.4.2, a dierenza di tutti gli altri approcci descritti, utilizza le linee di separazione (o separation lines: sono analoghe alle D function2.2.1) per evitare la sovrapposizione tra due poligoni. Come descritto nella sezione3.4.2, l'equazione di una linea di separazione che passa per un lato di un poligono, cioè che passa attraverso due vertici (xk, yk) e (xk+1, yk+1), è la seguente:

(y − yk)(xk+1− xk) − (yk+1− yk)(x − xk) = 0.

Gli autori utilizzano un modello nonlineare basato su queste linee di separazione per gestire l'interse-zione tra poligoni con rotazioni continue.

2.4.3 I metodi con cerchi

Rocha (2014) e Rocha et al. (2013) deniscono tre diversi tipi di coperture di cerchi per i pezzi, la copertura parziale (PC), la copertura interna (IC) e la copertura completa (CC). La (CC) viene usata

poi nell'approccio risolutivo diRocha et al.(2015) descritto nella sezione3.4.2, ed è visibile in un esem-pio nella gura2.7a. Più le coperture sono "ni", ovvero più è alto il numero di cerchi che rappresenta ogni pezzo, maggiore è il costo computazionale richiesto dall'algoritmo risolutivo. Per applicare con successo queste rappresentazioni al problema di nesting è necessario quindi raggiungere un compro-messo tra qualità di rappresentazione e errore di approssimazione dei pezzi.

Jones (2014) usa un'euristica iterativa greedy per posizionare i cerchi all'interno di ogni poligono, se ne può vedere un esempio nella gura2.7b. L'euristica greedy fa si che il numero di cerchi aumenti nelle zone del poligono che richiedono maggiore qualità durante l'esecuzione dell'algoritmo risolutivo.

Capitolo 3

Gli approcci risolutivi

In letteratura esistono numerosi metodi risolutivi al problema di nesting e quella che segue è una breve discussione su alcuni tra i più interessanti di essi. Pertanto distingueremo quattro categorie di approc-ci: costruttivi, migliorativi, metaeuristiche, esatti. Si noti come all'interno di uno specico approccio risolutivo 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.

Nel corso di questo studio analizzeremo i paper in letteratura che trattano lo strip packing, il bin packing ed il knapsack packing. Il procedimento generale degli approcci di strip e bin packing può essere adattato al caso del knapsack packing, cercheremo perciò di essere il più generali possibile in modo da poter astrarre la strategia dal particolare problema che risolve.

Gli articoli sono categorizzati tenendo conto delle rotazioni consentite sui pezzi, che possono essere di tre tipi: nessuna rotazione consentita, un numero nito di rotazioni consentite, qualsiasi rotazione consentita. Ciascuno dei quattro tipi di approcci risolutivi sarà perciò suddiviso in queste tre ulteriori categorie.

3.1 Approcci costruttivi

Questi metodi costruiscono una soluzione un pezzo alla volta e l'ammissibilità della soluzione è sottesa nell'euristica poichè ogni pezzo viene posto in una posizione ammissibile nel contenitore.

Due caratteristiche fondamentali di questo tipo di euristiche sono la regola e l'ordine di posiziona-mento dei pezzi.

La regola di posizionamento dei pezzi, come è facile immaginare, è l'algoritmo usato per posi-zionare un pezzo scelto all'interno del contenitore, dove può essere già presente un gruppo di pezzi già posizionati.

In letteratura il posizionamento di un pezzo nel contenitore viene gestito in diversi modi, ma la regola più conosciuta e utilizzata è la Bottom-Left (BL), studiata ed applicata al problema di nesting per primo daArt(1966) e successivamente utilizzata da diversi autori come ad esempio daDowsland et al. (2002) eGomes and Oliveira (2002). Diamone una denizione:

Denizione 3.1 (Bottom-Left):

Dato un contenitore P ed un insieme di pezzi Pi, i = 1, . . . , m, già posizionati con coordinate (xi, yi),

il pezzo successivo Pk viene posizionato seguendo la strategia bottom-left, cioè, al punto (xk, yk) con

la x più piccola e, se le coordinate x coincidono, con la più piccola y, in modo tale che Pk stia dentro

il contenitore e non si sovrapponga a nessun pezzo Pi già posizionato.

Questa regola muove quindi iterativamente ogni pezzo orizzontalmente (verso sinistra) nché pos-sibile (cioè nché non incontra un altro pezzo oppure il lato del contenitore) e poi verticalmente (verso

(a) Senza hole lling (b) Con hole lling

Figura 3.1: Due esempi della regola di posizionamento bottom left, presi daDowsland et al.(2002). il basso) nché possibile (nché non incontra un altro pezzo oppure nché non incontra il lato del contenitore). La regola può essere applicata anche utilizzando altre direzioni. Utilizzando la regola BL il pezzo posizionato è costretto a stare all'interno del contenitore e a non sovrapporsi a nessuno degli altri pezzi già presenti. Le strategie basate sulla regola bottom-left hanno come vantaggi la velocità e la semplicità di esecuzione. In letteratura gli approcci che la utilizzano si divdono in due gruppi in base a come la implementano: quelli che la utilizzano in congiunzione con un algoritmo hole-lling che tenta di riempire i buchi nella soluzione parziale, e quelli che invece non ammettono che il pezzo possa posizionarsi nelle parti interne della soluzione parziale. Una rappresentazione è visibile nella gura3.1. L'ordinamento dei pezzi è invece l'ordine con cui i pezzi sono dati in input (uno per volta) alla regola di posizionamento.

Nella stragrande maggioranza degli approcci costruttivi l'ordinamento è dinamico e varia durante l'e-secuzione dell'algoritmo. In questo caso si utilizzano algoritmi di ricerca locale o metaeuristiche da applicare all'insieme dei pezzi rimanenti che ne deniscono l'ordine di posizionamento.

3.1.1 Nessuna rotazione

I maggiori vantaggi della rappresentazione dei pezzi (e del contenitore) con una griglia (o matrice) sono: semplicare notevolmente i calcoli per ogni pezzo e capire facilmente quando due pezzi si intersecano. Wong et al. (2009) utilizzano una rappresentazione a griglia per i pezzi e per il contenitore. Essi rappresentano i rettangoli di contenimento di ciascun pezzo da posizionare con una matrice B = (bij)

in cui bij = 1 se il pixel (pi, pj) è occupato, 0 altrimenti. Applicano poi un approccio costruttivo a

due fasi posizionamento-compattamento come regola di posizionamento, considerando le matrici dei pezzi una per volta, e di volta in volta compattando il pezzo inserito con i pezzi già posizionati nella matrice che rappresenta il contenitore, unendo la sottomatrice del pezzo appena posizionato con la sottomatrice della soluzione parziale. Questa regola di posizionamento è utilizzata all'interno di un algoritmo migliorativo descritto in 3.2.1 e non compromette il costo computazionale dell'algoritmo. La regola bottom left insieme alla rappresentazione a griglia viene applicata anche nel lavoro diBabu and Babu(2001). Come descritto nella sezione 2.1, gli autori impongono una matrice di numeri interi maggiori uguali a zero al contenitore e ad ogni pezzo da posizionare. Queste due matrici vengono codicate in modo dierente per fare in modo di rendere ecace un posizionamento bottom left. Per ogni pezzo da posizionare con una rotazione ssata, la posizione iniziale è quella in cui il rettangolo di contenimento (cioè la matrice) del pezzo e del contenitore hanno l'angolo in basso a sinistra coincidente. A partire da questa posizione il pezzo viene fatto scorrere in modo incrementale nelle due direzioni x e ynchè non si trova una posizione ammissibile. La codica delle matrici del contenitore risulta ecace

3.1 Approcci costruttivi 25 in questo caso, in quanto il numero presente in ogni casella indica di quante caselle ogni pezzo deve spostarsi verso destra per trovare una posizione ammissibile. La sequenza dei pezzi da posizionare e l'o-rientazione di ciascun pezzo vengono determinati da un algoritmo genetico descritto nella sezione3.3.2. Utilizzando invece la rappresentazione poligonale dei pezzi, Hi and M'Hallah (2003) implementano una regola di posizionamento dierente: il primo pezzo viene posizionato nella posizione bottom-left, per il pezzo successivo si valutano i posizionamenti in cinque punti: (x, 0), (0, y), (x, y), (x, y), (x, y), dove x, x, y, y sono le coordinate x e y massime e minime del pezzo già posizionato. Si prosegue così per i pezzi successivi. Ad ogni iterazione si escludono le posizioni che danno luogo a un posizionamen-to inammissibile (ad esempio quelle che creano intersezione con i pezzi già posizionati). Tra tutte le candidate posizioni, si sceglie quella che posiziona il pezzo il più a sinistra e in basso possibile. Un algoritmo costruttivo basato sulla regola bottom-left viene presentato nel lavoro diDowsland et al. (2002). Gli autori presentano una regola di posizionamento veloce ed ecace che consente di arontare problemi con diverse centinaia di pezzi irregolari. L'algoritmo proposto produce un layout ottimo dal punto di vista della regola bottom-left, nel senso che le posizioni considerate contengono la posizione bottom-left tra l'insieme innito delle possibilità.

Gli autori risolvono la variante strip packing del problema di nesting e non consentono ai pezzi di poter ruotare. Essi utilizzano il NFP come strumento geometrico per gestire il posizionamento senza intersezioni, in combinazione con la regola di posizionamento bottom-left. Per maggiori dettagli vedere l'appendiceA.

Gli autori testano il loro algoritmo costruttivo utilizzando i quattro data set diDowsland et al.(1998) e considerano tre dierenti larghezze per il contenitore, un numero di pezzi variabile da 20 a 120 e nove dierenti ordinamenti dei pezzi.

3.1.2 Rotazioni nite

La regola bottom-left è largamente utilizzata negli algoritmi di cutting and packing con diverse varianti di implementazione. Come sappiamo, l'idea è quella di posizionare iterativamente ciascun pezzo nella posizione ammissibile più in basso e a sinistra possibile indipendentemente dal pezzo.

L'algoritmo usato da Elkeran (2013) è la regola di posizionamento bottom left di Gomes and Oli-veira (2002), a cui si aggiunge un algoritmo denominato pairwise clustering che si applica in una fase di preprocessing. L'algoritmo combina coppie pezzi che si incastrano bene tra loro riducendo così il numero totale di pezzi da posizionare. Questo algoritmo di pairwise clustering viene applicato anche da Abeysooriya et al.(2018) nel loro algoritmo Jostle esposto nella sezione 3.2.3.

Una regola di posizionamento dierente dalla regola bottom left (in realtà, è un tipo di regola bottom-left non hole-lling) è quella sviluppata daOliveira et al.(2000) nel loro algoritmo chiamato per brevità TOPOS: supponiamo di aver già scelto un pezzo da posizionare e la sua rotazione, quello che rimane da fare è trovare la miglior posizione del pezzo nel contenitore. Gli autori considerano a questo punto due poligoni: il poligono scelto tra quelli rimasti da posizionare e l'insieme dei pezzi già posizionati che formano la soluzione parziale no a quel momento, descritto dal suo contorno ed è anch'esso un poligono.

Per trovare la migliore posizione possibile tra questi due poligoni vengono analizzati tre diversi criteri: • minimizzazione dell'area del rettangolo di contenimento dei due poligoni (gura3.2a),

• minimizzazione della lunghezza del rettangolo di contenimento dei due poligoni (gura 3.2b), • massimizzazione della sovrapposizione tra i rettangoli di contenimento dei due poligoni, senza

permettere la sovrapposizione tra i poligoni (gura 3.2c).

Dopo aver denito la regola di posizionamento scegliendo uno tra i tre criteri esposti, gli autori danno sette possibili criteri ciascuno dei quali denisce un dierente ordinamento dei pezzi.

(a) Area rettangolo di

conte-nimento. (b) Lunghezza rettangolo dicontenimento. (c) Area sovrapposizione tra irettangoli.

Figura 3.2: Tre caratteristiche considerate da Oliveira et al.(2000) per il miglior posizionamento tra due poligoni.

come spazio sprecato e questi una volta che si presentano non verranno più riempiti; inoltre poichè la soluzione parziale cambia ad ogni iterazione, bisogna ricalcolare il NFP ogni volta tra il nuovo pezzo e la soluzione corrente la quale ha un contorno con un numero sempre maggiore di lati (poichè vi si aggiunge un pezzo per volta) e questo fa si che il tempo di calcolo del NFP cresca ad ogni iterazione. TOPOS viene testato in tutte le sue 126 varianti su 5 data set descritti nella tabella1.1all'interno della sezione 1.2: Shapes0, Shapes1, Shapes2, Shirts, Trousers. I risultati vengono confrontati con quelli ottenuti daAlbano and Sapuppo(1980) e migliorati di una percentuale che va dal 3% al 5%. Successi-vamente gli autori confrontano TOPOS anche con i migliori risultati per ogni istanza di test, ottenuti da: Blazewicz et al.(1993),Dowsland et al.(1998) eOliveira and Ferreira(1993b). Rispetto a questi ul-timi casi le performance di TOPOS variano da un miglioramento del 6.2% ad un peggioramento del 4%. Un tentativo di miglioramento dell'algoritmo TOPOS viene fatto da Bennell and Song (2010): ol-tre ad aggiungere la capacità di riempire i buchi all'algoritmo implementano alcune migliorie ai calcoli dei NFP, utilizzando per costruire quest'ultimo la tecnica delle somme di Minkowski di Mahadevan (1984) (vedi sezione2.2.2.1nella Componente geometrica). Nella gura3.3si vedono le caratteristiche che gli autori migliorano: in (a) c'è la soluzione parziale con le dimensioni del rettangolo Lold e Wold; in (b) il layout dopo l'aggiunta del nuovo pezzo ed il corrispondente rettangolo di contenimento, con le nuove dimensioni Lnew e Wnew; inne, in (c) l'area di sovrapposizione dei rettangoli di contenimento. Gli autori implementano anche un algoritmo di beam search che ingloba l'algoritmo TOPOS migliorato come parte integrante del suo procedimento.

La beam search è un'euristica che utilizza una struttura di ricerca ad albero con nodi simile alla tecnica di branch-and-bound. L'albero rappresenta la costruzione di una soluzione parziale dove ogni nodo aggiunge un nuovo elemento alla sequenza. Gli autori utilizzano la beam search e l'albero di ricerca viene esplorato con una strategia "breadth rst", facendo pruning dei rami ad ogni livello a seconda di una funzione di valutazione.

Gli autori testano l'algoritmo TOPOS migliorato su 6 istanze descritte nella tabella 1.1: Shapes0, Shapes1, Shapes2, Shirt, Trousers e Swim. Le prime 5 sono state usate anche nell'algoritmo oroginale TOPOS e gli autori usano i risultati per fare un confronto tra i due algoritmi, e ne risulta che il loro algoritmo performa meglio dell'originale raggiungendo un layout più compatto su tutte le istanze meno che Shapes2. Gli esperimenti eettuati servono anche a valutare l'uso di un'orgine ottante per la soluzione parziale oppure della costruzione a partire dall'angolo bottom left. L'algoritmo di beam search, invece, viene confrontato con i migliori algoritmi presenti in letteratura diEgeblad et al. (2007),Rocha et al. (2015) e in una istanza Burke et al. (2006). Le istanze usate sono le seguenti 16, tutte descritte nella tabella1.1: Albano, Dagli, Dighe1, Dighe2, Fu, Jakobs1, Jakobs2, Mao, Marques, Poly5b, Shapes0, Shapes1, Shapes2, Shirts, Swim, Trousers. I risultati mostrano che l'algoritmo di beam search performa come o meglio dei migliori risultati in 7 casi su 16, con un costo computazionale