Tesi Erick Baldi

ALMA MATER STUDIORUM UNIVERSITA' DEGLI STUDI DI BOLOGNA Seconda Facoltà di Ingegneria sede di Cesena Corso di laurea in Ingegneria Informatica Tesi di Laurea in Ricerca Operativa L-A

Modelli e algoritmi per l'ottimizzazione di layout fieristici Tesi di laurea di: Erick Baldi Relatore: Chiar.mo Prof. Ing. Silvano Martello Correlatori: Prof. Ing. Daniele Vigo Dott. Ing. Manuel Iori

Università di Bologna

Prima sessione

AA. 2007/2008

Indi e Introduzione

i

1 Problemi di pa king e utting nei layout

1

1.1

Layout eristi i . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2

Cutting and Pa king problems . . . . . . . . . . . . . . . . . .

4

1.2.1

Knapsa k problem

. . . . . . . . . . . . . . . . . . . .

6

1.2.2

Bin Pa king Problem . . . . . . . . . . . . . . . . . . .

13

1.2.3

Two Dimensional Bin-pa king Problem . . . . . . . . .

18

1.2.4

Two Dimensional Strip-pa king Problem

. . . . . . . .

34

1.2.5

Two Dimensional Knapsa k Problem

. . . . . . . . . .

40

Fa ility layout problem . . . . . . . . . . . . . . . . . . . . . .

44

1.3.1

Modelli per il fa ility layout problem

. . . . . . . . . .

45

1.3.2

Metodologie di risoluzione

. . . . . . . . . . . . . . . .

48

1.3

2 Ottimizzazione dei layout eristi i 2.1

Spe i he e ontesti per il progetto 2.1.1

2.2

55 . . . . . . . . . . . . . . .

56

Modelli matemati i . . . . . . . . . . . . . . . . . . . .

61

Studio e analisi di asi reali

. . . . . . . . . . . . . . . . . . .

65

2.2.1

Caso 1: Fortaleza hand raft fair . . . . . . . . . . . . .

66

2.2.2

Caso 2: Regional fair in Romont . . . . . . . . . . . . .

70

2.2.3

Considerazioni nali

80

. . . . . . . . . . . . . . . . . . .

3 Casi di studio e spe i he di progetto 3.1

Presentazione dei asi di studio

83

. . . . . . . . . . . . . . . . .

84

3.1.1

Fiera del Levante . . . . . . . . . . . . . . . . . . . . .

85

3.1.2

Fiera di Bolzano

88

. . . . . . . . . . . . . . . . . . . . . 1

INDICE

INDICE 3.1.3

3.2

Expo Ferroviaria 2008

. . . . . . . . . . . . . . . . . .

91

Criterio per la denizione e la s rittura delle matri i . . . . . .

92

4 Implementazione degli algoritmi e risultati omputazionali 97 4.1

Fiera del Levante: soluzione

. . . . . . . . . . . . . . . . . . .

98

4.2

Fiera di Bolzano: soluzione . . . . . . . . . . . . . . . . . . . . 102

4.3

Expo Ferroviaria 2008: soluzione

4.4

Considerazioni nali

. . . . . . . . . . . . . . . . 103

. . . . . . . . . . . . . . . . . . . . . . . 104

5 Con lusioni

109

Bibliograa

111

Ringraziamenti

Ringrazio sentitamente il mio relatore, Prof.Ing.Silvano Martello, e i miei orrelatori, Prof.Ing.Daniele Vigo e Ing.Manuel Iori, per la disponibilità e l'aiuto nello sviluppo del progetto di tesi e nella onseguente stesura. Ringrazio soprattutto la mia Famiglia per il prezioso sostegno, la fidu ia, l'aiuto ostante e i numerosi sa rifi i; ringrazio inoltre tutti gli Ami i e le persone he in questi anni mi sono stati vi ini. Grazie a tutti.

La stupidità deriva dall'avere una risposta per ogni osa La saggezza deriva dall'avere una domanda per ogni osa (Milan Kundera)

Introduzione Questa tesi ha ome obiettivo quello di determinare algoritmi e metodi per ottimizzare il layout di esposizioni eristi he, on parti olare riferimento e appli azione a tre ontesti eristi i eterogenei, manifestazioni di grande importanza (sia su s ala nazionale he internazionale) he hanno luogo in varie ittà italiane. In parti olare si er herà di implementare gli algoritmi studiati e illustrati nei primi due apitoli ai tre asi sopra itati, in modo da raggiungere l'obiettivo dell'appli abilità di tali metodologie ai asi più generali possibile. Lo s opo del lavoro onsiste quindi nel massimizzare il numero di stand espositivi he possono essere ontenuti negli spazi adibiti alla era, fo alizzando il on etto in base ai problemi di spazio, allo azione e adeguamento. Nel orso della trattazione, dopo una esauriente presentazione dei modelli matemati i, verranno studiati asi reali già dis ussi e ultimati, in maniera da ri ondurre i problemi a realtà simili, he fungono da punti di partenza. In parti olare verranno studiati ontesti quali la era di Fortaleza (Brasile) e di Romont (Svizzera) poi hè rappresentano due esempi esaustivi e ompleti per pro edere nel progetto. La struttura della tesi è organizzata in 5 apitoli osì suddivisi:

• Capitolo 1 :

introduzione e analisi dei problemi di layout e pa king, e

dei relativi modelli matemati i utili per l'ottimizzazione. Verranno illustrate le metodologie alle quali è possibile ri ondurre un problema di organizzazione di spazi espositivi, in ui si presentano numerosi osta oli quali l'area irregolare di esposizione, la dimensione degli stand, gli spazi ne essari al passaggio delle persone e all'eventuale gestione da parte degli organizzatori, l'ambiente in ui i si trova a lavorare. Il tuti

ii

INDICE to improntato sull'obiettivo della programmazione matemati a e degli algoritmi della Ri er a Operativa.

• Capitolo 2 :

presentazione di asi di studio già analizzati e on lusi. Le

manifestazioni eristi he di Fortaleza e di Romont sono esempi molto

alzanti di appli azione delle te ni he dell'ottimizzazione eristi a a queste tipologie di problemi. Partendo dallo studio di entrambi i asi e adattandone le aratteristi he al ontesto in oggetto, si sono potuti ri avare algoritmi e modelli utili, da appli are in maniera più spe i a ai asi presi in onsiderazione nella tesi.

• Capitolo 3 :

asi di studio oggetto della tesi. Appli azione degli algo-

ritmi di ottimizzazione di layout eristi i on parti olare riferimento a tre ontesti diversi: la Fiera del Levante di Bari, la Fiera di Bolzano Messe Bozen e la Expo Ferroviaria 2008 presso il Lingotto di Torino. Questo apitolo onsiste in una panorami a dei tre ontesti analizzati, des rivendone le soprattutto le spe i he te ni he per la progettazione, pur senza tralas iare notizie stori he e aratteristi he di ias una manifestazione.

• Capitolo 4 :

soluzioni e possibili ulteriori obiettivi. I metodi della ri er-

a operativa e della ottimizzazione ombinatoria vengono qui messi in prati a grazie all'implementazione software degli algoritmi visti e studiati nei pre edenti apitoli. Con riferimento alle alternative studiate nel terzo apitolo, verranno qui implementate le metodologie per l'appli azione degli algoritmi a tre proposte piuttosto dierenti tra loro, in maniera tale da arontare il

fair layout problem in maniera più generi a

possibile.

• Capitolo 5 :

on lusioni e obiettivi raggiunti. Breve sintesi della strada

per orsa nel progetto di tesi, on uno sguardo ai modelli e agli algoritmi implementati e alla loro appli azione ai asi presi in esame.

Capitolo 1 Problemi di pa king e utting nei layout Il punto di partenza per l'analisi delle problemati he legate ai layout eristi i è rappresentato dalla progettazione in ambito industriale. Prima di proseguire è ne essario fornire al une denizioni. Si denis e

layout ome

una organizzazione della produzione he ha ome oggetto la progettazione, la messa in opera, la manutenzione e il miglioramento di sistemi integrati di uomini, ma

hine e materiali; fa endo uso di metodi e te ni he tratti dalle s ienze matemati he, si he e so iali, oltre he dai riteri dell'analisi e onomi a, essa deve denire gli obiettivi di tali sistemi integrati, valutare preventivamente e ontrollare i risultati ottenuti. Quindi, in maniera più sempli e e sinteti a, il layout non è altro he un modo di organizzare la gestione di beni materiali adandosi a metodi razionali, matemati i e ingegneristi i. Si tratta di trovare il giusto ompromesso tra uomo e produzione, in termini di gestione ottimale di quest'ultima. Se si pensa he uno dei fattori ru iali he maggiormente inuenzano i osti di un'azienda ( ir a dal 30% al 75%) è proprio legato alle politi he di layout e di movimentazione di materiale, è bene er are delle soluzioni ottimizzate per ovviare al problema e ridurre di onseguenza i osti he ne derivano. 1

2

1. Problemi di pa king e utting nei layout Il layout ottimale è quello he onsente di soddisfare il maggior numero possibile di soggetti interessati ad un erto aspetto di produzione o di organizzazione ( ome ad esempio i vari settori oinvolti nell'allestimento di una era),

er ando di venire in ontro alle esigenze di tutti gli interessati. Questo non è aatto un ompito sempli e: er are di soddisfare adeguatamente ogni gruppo di persone addette ai numerosi settori di organizzazione, signi a reare un layout he soddis i requisiti di tutti i settori oinvolti. Ovviamente ogni gruppo oinvolto ha le proprie esigenze, in base al proprio lavoro e o

upazione svolti. Per questo nel progettare un layout ottimo o

orre tenere onto di diversi fattori:

•

omplessità e tipologia del pro esso di produzione

•

volumi e quantità di produzione

•

ussi e trasporti interni di materiale

•

massima utilizzazione degli impianti e delle attrezzature

•

utilizzo e a e di spazi e ambienti disponibili

•

ondizioni ambientali e lo ali favorevoli

•

previsioni future (possibili estensioni, dierenziazioni, e

.)

Tutti questi fattori dipendono in maniera più o meno forte tra di loro, ed è quindi fondamentale o

uparsene, oltre he singolarmente, an he nel loro omplesso; i prin ipali ris ontri dovuti a un'adeguata organizzazione del lavoro si avranno sulla planimetria delle aree adibite all'esposizione. In parti olare si otterranno vantaggi in ambito logisti o, ad esempio nell'ottimizzazione dei ussi, nelle distanze da oprire, nelle informazioni e dei dati da s ambiare, nelle attività da svolgere e portare a termine.

1.1 Layout eristi i In un ontesto eristi o il layout assume un ruolo fondamentale, oltre he per l'organizzazione interna, an he per il servizio oerto a lienti e visitatori;

1.1 Layout eristi i

3

ri opre inoltre una funzione spe iale per determinare l'e ienza, l'esteti a e le funzionalità della era. In aggiunta alle aratteristi he viste per un layout prettamente industriale, in ambito eristi o (derivante appunto da quello industriale) si hanno altre importanti pe uliarità quali:

•

e a e utilizzo degli spazi e dell'ambiente

•

ottimizazione dei per orsi per lienti e per organizzatori

•

progettazione di spazi e luoghi oerentemente on una previsione adeguata del numero di visitatori

•

oretto sfruttamento delle risorse ambientali disponibili

In prati a, iò he dierenzia prin ipalmente i layout industriale e eristi o risiede nel fatto he mentre nel primo aso ha molta importanza la buona gestione del usso di materiale, nel se ondo prevalgono esigenze di tipo esteti o e a

attivante, in modo da attrarre l'attenzione e sus itare l'interesse nel maggior numero possibile di persone. Considerando un po' brutalmente l'ambito eristi o ome un'industria, si può asso iare il prodotto industriale al liente della era: il liente he entra in una era è la materia prima da lavorare, il liente he es e dalla era è il prodotto ultimato.

L'obiettivo

onsiste quindi nel produrre il maggior numero di beni materiali ossia, nel

aso eristi o, nel soddisfare il maggior numero possibile di lienti. Sebbene in letteratura non esistano studi spe i i in ambito eristi o, ma solo industriale, è bene adattare questi studi in maniera da estrapolare una metodologia di progetto valida an he nel aso di ere ed esposizioni; la progettazione deve avvenire in modo pre iso e metodi o prendendo in onsiderazione tutti i possibili aspetti e gli elementi oinvolti. Naturalmente l'appro

io on ui progettare un layout dipenderà molto dalla tipologia in ui si inseris e il ontesto eristi o: una era dedi ata al mer ato automobilisti o sarà ben diversa di una dedi ata alle spe ialità gastronomi he!

Tra gli elementi fondamentali he ostituis ono un layout, massima

importanza ha la

planimetria, tramite la quale

sizione di stand, passaggi, ussi e per orsi.

è possibile studiare la dispo-

La progettazione planimetri a

dovrà an he tenere onto delle apa ità, ovvero del ``funzionamento a pieno

4

1. Problemi di pa king e utting nei layout 1

e a vuoto . Analogamente ai metodi usati per progettare layout industriali, si pro ederà appli ando questo appro

io a quello eristi o.

Nello s hema

di gura 1.1 è mostrato un possibile insieme di passi. Grazie all'aiuto della Ri er a Operativa

2

è possibile appli are delle metodologie di progetto ade-

guate al aso di layout eristi i. Nei prossimi paragra verranno introdotti al uni importanti algoritmi per risolvere problemi legati al

utting

e

pa king

di oggetti e più in generale per determibare il layout ottimo.

1.2 Cutting and Pa king problems L'ottimizzazione ombinatoria è una bran hia della Ri er a Operativa ui fanno riferimento i problemi di utting e pa king, i quali onsistono nel trovare una soluzione massimizzata o minimizzata per mettere insieme un dato insieme di oggetti in uno o più ontenitori. Questa metodologia è molto utilizzata dalle industrie manifatturiere (legno, arta, vetro, a

iaio, pelle, e

.)

osì ome nelle tipograe per la stampa di giornali e quotidiani, ma an he in molti altri settori della produzione industriale. Per molti anni si sono er ate soluzioni he minimizzassero il

throughput 3

4

e i tempi di latenza

dei prodotti

da ultimare, ma he nel ontempo massimizzassero le quantità e i volumi di produzione delle aziende. Settori ingegneristi i della Ri er a Operativa, della

Computer S ien e o dell'industria manifatturiera si sono a lungo o

upati di problemi di utting and pa king (C & P). Basandosi su diversi riteri, uno su tutti legato alla dimensione del problema, si possono suddividere gli appro

i progettuali in tre dimensioni. Trattandosi di layout eristi i, il nostro interesse si soermerà solamente su due dimensioni, relativamente all'area espositiva della era.

1 si

intende nei asi di massime e minime presenze di visitatori, ma an he di ussi di materiale, personale ed eventuali mezzi oinvolti nell'organizzazione. 2 settore della matemati a he si o

upa prevalentemente di problemi di ottimizzazione di risorse, on largo uso di supporti matemati i e informati i per la determinazione e l'appli azione di algoritmi di ottimizzazione 3 numero di unità ompletate in un erto lasso di tempo. 4 tempo impiegato per la produzione di un bene materiale o di un servizio oerto.

1.2 Cutting and Pa king problems

Figura 1.1: Sempli azione on ettuale di un generi o knapsa k problem

5

6

1. Problemi di pa king e utting nei layout •

C & P problems ad una dimensione 1. Knapsa k algorithm

01

(KP)

2. Bin pa king problem (BPP)

•

C & P problems a due dimensioni

1. Two-dimensional Bin Pa king Problem (2BPP) 2. Two-dimensional Strip Pa king Problem (2SPP) 3. Two-dimensional Knapsa k Problem (2KP)

utting and pa king si può onsiderare valido e attuabile nel aso in ui le dimensioni degli oggetti interessati (items ) possano essere ontenuti dagli oggetti ontenitori ( ontainers ) e he entrambi items

E' ne essario sottolineare he il

e ontainers non si sovrappongano tra loro.

1.2.1 Knapsa k problem Supponendo, tra varie alternative, il aso in ui si debbano s egliere degli oggetti ompatibilmente on erti riteri prestabiliti, onsideriamo nella fattispe ie il aso in ui, per restare in tema, si debbano s egliere tra gli stands quelli adatti alle nostre spe i he di layout. Se numeriamo gli stand ``idonei da

1 a n e reiamo un

vettore di variabili binarie

xj (j = 1, ..., n) in modo he

valga

xj = Se inoltre indi hiamo on

aso), on il suo

wj

(

pj

1 0

se l'oggetto j è s elto altrimenti

il protto dato dall'oggetto

la sua dimensione e on

c la dimensione del suo ontainer

osto ), allora l'obiettivo Knapsa k

i vettori binari

x

wj xj ≤ c

j=1

e he massimizzano la funzione obiettivo

n X j=1

(ossia

sarà quello di selezionare, tra tutti,

he soddisfano il vin olo

n X

j (lo stand nel nostro

pj xj .

1.2 Cutting and Pa king problems

7

Per generalizzare il problema hiamiamo gli oggetti

n;

pari ad

items, on

una quantità

j − esimo sono hiamati pj e vj (j = (1, ..., n)). Na-

il valore e la dimensione dell'oggetto

rispettivamente

protto

e

peso

e indi ati on

turalmente il dis orso appena fatto riguarda un aso knapsa k generi o, il

ui s opo onsiste nel determinare uno o più sottoinsiemi per ui la somma dei pesi non superi (o eguagli) una erta quantità limite (detta

bound )

e la

somma dei valori sia massimizzata. Questa tipologia di problema, ri ondu i-

algoritmo Knapsa k,

bile all'

ha ris ontrato enorme interesse da entrambi

i punti di vista teori o e prati o, adattandosi a varie forme di progettazione

he ri hiedono l'ottimizzazione. Di seguito si analizzeranno più in dettaglio le varie tipologie di

and Pa king problems

Cutting

in base alle denizioni pre edentemente fornite per

problemi a una e due dimensioni.

KNAPSACK 0-1 (BINARY) Il

Knapsa k problem 0-1

è il più importante dei problemi di ottimizzazione

ombinatoria. Esiste un esempio di problema asso iato allo knapsa k he ne espli a in maniera piuttosto esauriente la funzione. ``dello zaino''

5

Tale problema, detto

è posto nel modo seguente:

sia dato uno zaino he possa supportare un determinato peso e siano dati inoltre N oggetti, ognuno dei quali aratterizzato da un peso e un'utilità (ovvero un guadagno). Il problema si propone di s egliere quali di questi oggetti mettere nello zaino per ottenere la maggiore utilità senza e

edere nel peso sostenibile dallo zaino stesso, il quale non è altro he un problema analogo al aso visto in pre edenza. Detto iò si può proseguire elen ando tre motivi fondamentali per ui l'algoritmo ha assunto tale importanza:

•

può essere trattato ome un sempli e problema di Programmazione Intera Lineare (ILP)

5 in

inglese knapsa k indi a proprio la parola zaino

8

1. Problemi di pa king e utting nei layout

Figura 1.2: sempli azione on ettuale di un generi o knapsa k problem •

appare ome sottoproblema di problemi più omplessi

•

può essere utile in molte soluzioni prati he

Le variabili d'interesse per lo sviluppo di questo algoritmo sono tutte binarie (da qui il nome ``Knapsa k 0-1'') e il su

o del dis orso può essere riassunto qui di seguito: date le seguenti variabili

pj = protto wj = peso c = apa ita

dell'oggetto j

dell'oggetto j del ontenitore

è opportuno s egliere un sottoinsieme di

massimizzare

items

tale da:

−→ max(z) =

n X

pj xj

(1.1)

j=1

soddisfa endo

−→

n X j=1

wj xj ≤ c

(1.2)

1.2 Cutting and Pa king problems dove

9

−→ xj ∈ {0, 1} , j ∈ N = {1, ..., n}

(1.3)

analogamente alle denizioni date in pre edenza. Se ora ipotizziamo he

pj , w j e c

sono interi positivi,

n X

(1.4)

wj ≤ c,

(1.5)

j=1

wj < c, on j ∈ N,

(1.6)

e se onsideriamo violata la prima ipotesi, allora si ottengono delle frazioni

he possono essere moltipli ate per un opportuno fattore, mentre gli eventuali valori negativi verranno trattati ome

0

o ome

1

in base alle seguenti

relazioni:

• ∀j ∈ N 0 = {j ∈ N : pj ≤ 0, wj ≥ 0} =⇒ xj = 0 • ∀j ∈ N 1 = {j ∈ N : pj ≥ 0, wj ≤ 0} =⇒ xj = 1 N − ome N − = {j ∈ N : pj < 0, wj > 0}, N + = N \ (N 0 ∪ N 1 ∪ N − ).

Deniamo inoltre il valore sarà:

mentre per

N+

Inne deniamo:

(

yj = 1 − xj , p¯j = −pj , w ¯j = −wj yj = xj , p¯j = pj , w ¯ j = wj

per per

j ∈ N− j ∈ N+

Ora he tutte le variabili e i asi sono stati deniti, enun iamo il problema. Si vuole risolvere il problema he ha ome obiettivo quello di massimizzare la funzione

z=

X

p¯j yj +

j∈N − ∪N + mentre ome

onstraint

X

pj

j∈N 1 ∪N −

del problema la funzione

X

j∈N − ∪N +

w¯j yj ≤ c −

X

wj .

j∈N 1 ∪N −

Se i dati in input violano l'espressione (1.2) ipotizzata pre edentemente allora

xj = 0, ∀j ∈ N ,

mentre se violano l'assunzione (1.3) allora si avrà

xj =

10

1. Problemi di pa king e utting nei layout 0, ∀j ∈ N : wj > c

.

Se non spe i ato in altro modo, si supporranno sempre gli

items

in ordine

de res ente se ondo l'ordine del protto per unità di peso:

p1 p2 pn ≥ ≥ ... ≥ w1 w2 wn Data ad ogni problema una ottima on

z(I)

istanza I , si indi herà il valore di ogni soluzione

o più sempli emente on

z.

Considerando il problema nella

versione minimizzata anzi hè massimizzata, gli obiettivi si invertono se ondo lo s hema seguente:

minimizzare

−→ min(z) =

n X

pj y j

j=1

soddisfa endo

−→

n X

wj y j ≤ q

j=1

dove

−→ yj ∈ {0, 1} , j ∈ N = {1, ..., n}

dal quale si evin e he il pro edimento per tornare da una forma (minimizzata) all'altra (massimizzata) onsiste nel porre Pn (1.1), la (1.2) e la (1.3) on c = j=1 wj − q . Inoltre, ponendo ome

yj = 1 − xj

e risolvendo la

zmax

il valore della soluzione massimizzata di ogni Pn problema, la sua versione minimizzata sarà zmin = j=1 pj − zmax .

Rilassamento lineare Togliendo il vin olo dell'integrità sulle variabili

xj , nelle proprietà (1.1), (1.2)

e (1.3), si ottiene la prima variante del problema knapsa k 0-1 ovvero il osiddetto

rilassamento lineare o ontinuous Knapsa k problem C(KP). In pra-

ti a un rilassamento è una qualunque te ni a he ha lo s opo di migliorare (ottimizzare) la funzione obiettivo in tutti i punti della regione ammissibile

6

originale : massimizzare

−→ max(z) =

n X

pj xj

j=1

6 metodo

improntato sull'ampliamento della regione ammissibile e/o sull'innalzamento della funzione obiettivo in orrispondenza della regione ammissibile originale

1.2 Cutting and Pa king problems

11

−→

soddisfa endo

n X

wj xj ≤ c

j=1

dove

−→ 0 ≤ xj ≤ 1, j = 1, ..., n

Supponiamo inoltre he gli oggetti, ordinati ome illustrato sopra, siano inseriti onse utivamente nel ontenitore, n hé non si trova un oggetto non può più essere inserito. Questo è un problema di

s=

(

j:

j X

wj > c

i=1

s

he

riti al item :

)

da ui si può notare, ri ordando le (1.4), (1.5) e (1.6), he si ha

1 < s ≤ n.

Tale metodo è stato risolto nel 1957 mediante un algoritmo s operto da Dantzig.

Rilassamento lagrangiano Un'alternativa al aso appena visto, di tipo lineare, è il rilassamento lagrangiano. In questo modo i si pone lo s opo di eliminare un insieme di vin oli, tenendone però onto nella funzione obiettivo. Dato un fattore non negativo

on (L(KP,

λ))

λ,

il

rilassamento lagrangiano

del KP, indi ato

è:

massimizzare

−→ max(z) =

n X

pj xj + λ(c −

j=1

dove

n X

wj xj )

j=1

−→ xj ∈ {0, 1} , j = 1, ..., n.

La funzione obiettivo può essere espressa ome

z(L(KP, λ)) =

n X

p˜j xj + λc

(1.7)

j=1

dove

p˜j = pj + λwj

per

j = 1, ..., n.

fa ilmente determinabile in un tempo

x˜j =

(

1 0

La soluzione ottima di

O(n) se se

L(KP, λ)

è

ome:

p˜j > 0 p˜j < 0

(1.8)

12

1. Problemi di pa king e utting nei layout (quando

p˜j = 0

Quindi, denendo sarà:

xj è irrilevante).   p˜j > λ , il J(λ) = j : wj

il valore di

X

z(L(KP, λ)) =

valore della soluzione

L(KP, λ)

p˜j + λc.

j∈J(λ) Per ogni

λ≥0

'è un upper bound in

z(KP )

he, omunque, non potrà mai

essere migliore della soluzione fornita da Dantzig; l'equazione (1.8) i fornis e la soluzione del rilassamento ontinuo (o lagrangiano) di

L(KP, λ) nel

modo

seguente:

z(L(KP, λ)) = z(C(L(KP, λ))) ≥ z(C(KP )) z(L(KP, λ)) è λ∗ = wpss . Con questo valore, in realtà, abbiamo he p ˜j ≥ 0 per j = 1, ..., s − 1 mentre p˜j ≤ 0 ∗ per j = s, ..., n. In questo modo J(λ ) ⊆ {1, ..., s − 1}. Da qui x ˜j = x¯j , per j ∈ N \ {s} (dove x¯j è denita nel teorema seguente) e Il valore di

λ

he produ e il valore minimo di

grazie alle (1.7) e (1.8), si evin e he

∗

z(L(KP, λ )) =

s−1 X

(pj − λ∗ wj ) + λ∗ c = z(C(KP ))

j=1

Inne si può notare he, per

|p∗j |

λ = λ∗ , p˜j

è il de remento he si ottiene in

diventa

ps ; il modulo ws x˜j = 1 − xj e da

p∗j = pj − wj

z(L(KP, λ∗ ))

ponendo

qui un lower bound sul orrispondente de remento della soluzione ontinua (da quando l'ottimo

λ

ambia imponendo le ondizioni sopra elen ate). Al-

tri rilassamenti lagrangiani del problema KP sono stati studiati da Ma ulan (1983) e da Fisher (1981).

Teorema La soluzione ottima

x¯

del problema C(KP) è:

x¯j = 1

per

j = 1, ..., s − 1

x¯j = 0

per

j = s + 1, ..., n

x¯s =

c¯ , ws

1.2 Cutting and Pa king problems dove:

c¯ = c −

s−1 X

13

wj .

j=1

Figura 1.3: s operte e appli azioni più importanti legate ai modelli knapsa k problem in

ordine ronologi o

1.2.2 Bin Pa king Problem Il bin-pa king problem (BPP) è un altro tipo di problema di natura ombinatoria e onsiste nel raggruppare oggetti di volumi diversi in un numero nito di ompartimenti di apa ità

V,

in maniera tale da minimizzare il nu-

mero di tali ompartimenti da utilizzare. Ovviamente, ome per tutti i problemi di questo tipo, an he il BPP ha un

ampo di appli azione molto vasto, dall'industria ai trasporti, dalla logisti a all'organizzazione aziendale, dall'informati a alle tele omuni azioni. Usando la terminologia e la formalizzazione tipi he dei problemi

on

n

il numero di oggetti/items e di ontenitori (

knapsa k, indi hiamo

bins ) mentre

indi heremo

14

1. Problemi di pa king e utting nei layout

Figura 1.4: Bin Pa king Problem

on

wj

item

il peso dell'

j-esimo e on

c

la apa ità di ogni

bin.

Lo s opo del problema è di assegnare ogni item ad un bin in modo he il peso totale degli oggetti in ogni ontenitore non e

eda la apa ità

c

del onteni-

tore stesso, e he il numero dei bins impiegati sia minimo. Dal punto di vista matemati o, il problema si pone nel modo seguente:

minimizzare

−→ min(z) =

n X

yi

i=1

soddisfa endo

−→

n X

wj xij ≤ cyi , i ∈ N = {1, ..., n} ,

j=1

n X

xij = 1, j ∈ N,

i=1

yj ∈ {0, 1} , i ∈ N,

xij ∈ {0, 1} , i, j ∈ N Si denis ono qui di seguito i valori delle variabili:

yi

xij

(

1 0

(

1 0

se il bin i è usato altrimenti

se l'item j è assegnato al ontenitore i altrimenti

(1.9)

(1.10)

1.2 Cutting and Pa king problems c

15

è un intero positivo

wj ≥ c

per

j∈N

Se l'assunzione (1.11) risulta violata e i sostituito on

⌊c⌋

wj

(1.11)

sono tutti interi,

; se un item viola l'assunzione (

??)

c

può essere

l'istanza risulta ina -

ettabile. Tuttavia non esiste un modo sempli e per trasformare una istanza in modo da poter trattare pesi negativi. Per sempli ità assumiamo he, per ogni soluzione ammissibile, vengano usati i pio

yi ≤ yi+1

per

bins

di indi e più basso (ad esem-

i = 1, ..., n − 1).

L'appro

io mediante algoritmi BPP viene trattato in letteratura basandosi sulla approssimazione degli algoritmi stessi e sulle loro performan e.

In

questo ampo rivestono parti olare importanza gli studi di Coman, Garey e Johnson (1984).

Algoritmi approssimati Il più sempli e appro

io approssimativo al mo

Next-Fit

2, ..., n sono

bin-pa king problem

è l'algorit-

(NF): il primo oggetto/item è assegnato al bin 1. Gli items

poi onsideati al res ere dell'indi e, ossia ogni item è assegnato

al bin orrente se adatto, altrimenti è assegnato a un nuovo bin he diventa

O(n)7 . E' fa ile soluzione NF (I) fornita

quello orrente. Si dedu e he la omplessità dell'algoritmo è infatti provare he, per ogni isanza

I

del BPP, la

dall'algoritmo soddisfa il bound

NF (I) ≤ 2z(I) dove

z(I)

rapporto

indi a la soluzione ottima.

NF (I) z(I)

Esistono, inoltre, istanze per ui il

tra le due soluzioni è arbitrariamente fermato a 2: ioè la

peggior performan e he si possa avere nel rapporto di NF è he

r(NF = 2).

Si nota he, per un problema di minimo, il peggior aso di un rapporto tra un generi o algoritmo A approssimato è denito ome il più pi

olo numero 7 in

ambito omputazionale, in relazione a una teoria della omplessità, la notazione detta big O è usata per des rivere quanto la dimensione, il peso dell'input inuis e sulle risorse impiegate nell'elaborazione di un algoritmo (di solito sui tempi di throughput o dell'o

upazione di memoria)

16

1. Problemi di pa king e utting nei layout r(A) ∈ R

tale he

A(I) ≤ r(A) z(I)

per tutte le istanze di I,

dove A(I) indi a la soluzione ottenuta dall'algoritmo A.

Un algoritmo migliore, il

First-Fit

(FF), onsidera gli items all'in remen-

tare degli indi i e assegna ogni item al più basso indi e di bin inizializzato nel quale entra; solo quando l'oggetto orrente non viene assegnato a qual he bin inizializzato, viene introdotto un nuovo ontenitore.

Un altro algoritmo,

Best-Fit

(BF), è ottenuto dal FF assegnando il or-

rente item al bin a

ettabile (se 'è) he ha la più pi

ola apa ità residua (rompendo il vin olo del bin on indi e più basso).

Si assuma ora he gli oggetti siano sistemati in modo he siano

... ≤ wn , e he

w1 ≤ w2 ≤

in seguito siano appli ati gli algoritmi NF, oppure FF, oppure

Next-Fit DeBest-Fit De reasing

BF. Gli algoritmi risultanti sono hiamati rispettivamente

reasing

(NFD),

First-Fit De reasing

(FFD) e

(BFD).

La omplessità di questi algoritmi e i asi peggiori di performan e he si possono raggiungere sono stati studiati da Johnson, Demers, Ullman, Garey e Graham (1974).

Nella tabella riassuntiva di g. dei vari algoritmi, in ui

r

∞

1.5 sono illustrati i riteri di valutazione

asymptoti worst ase performan e ratio 8 ;

è l'

per un generi o algoritmo approssimato A, esso è denito ome il minor numero reale

r ∞ (A)

A(I) ≤ r ∞ (A) z(I)

tale he, per un qual he valore intero positivo K, sia

per ogni istanza I he soddis

z(I) ≥ K :

8 stima asintoti a della prestazione nel aso peggiore;

il simbolo di innito sta ad indi are il numero impre isato di volte per ui viene ripetuta la stima

1.2 Cutting and Pa king problems

17

Figura 1.5: onfronto tra i vari algoritmi e loro performan e Rilassamento lineare Enun iamo qui di seguito la versione del

ontinuous problem

riferita al rilas-

samento lineare nel aso del bin pa king. Per il modello in esame il C(BPP) è il seguente: minimizzare

−→ min(z) =

n X

yi

i=1

soddisfa endo

−→

n X

wj xij ≤ cyi , i ∈ N = {1, ..., n} ,

j=1

n X

xij = 1, j ∈ N,

i=1

0 ≤ yi ≤ 1, i ∈ N, 0 ≤ xij ≤ 1, i, j ∈ N Tale rilassamento può essere fa ilmente risolto ponendo

(j 6= j)

e ponendo

yi =

wi , ∀i c

∈ N.

Da qui otteniamo

z(C(BP P )) =

n X wi i=1

c

xij = 1, xij = 0

on

18

1. Problemi di pa king e utting nei layout

1.2.3 Two Dimensional Bin-pa king Problem Finora si sono lassi ati i problemi di pa king a se onda del numero di dimensioni.

In problemi BPP l'attenzione era fo alizzata sull'obiettivo di

trovare un modo per raggruppare insieme un erto numero di oggetti, impiegando il minor numero di ontenitori possibile. I problemi a due dimensioni possono an he essere lassi ati in base alla forma degli oggetti da impa

are; nelle appli azioni industriali è parti olarmente presente il

two-dimensional re tangle pa king problem

per ui è ri hiesto di

ollo are un insieme di oggetti rettangolari in un numero minimo di unità rettangolari più grandi, minimizzando quindi an he lo spazio inutilizzato. Inoltre nelle industrie del legno e del vetro, pezzi di forma rettangolare devono essere tagliati a partire da grandi lamine di materiale. Nel ontesto dei magazzini, i prodotti devono essere messi sugli s aali. Nell'impaginazione dei giornali, gli arti oli devono essere ben posizionati nelle pagine. In tutte queste appli azioni industriali, il problema del pa king si presenta spesso on vin oli lievemente dierenti; molte varianti del problema sono state onsiderate in letteratura. Contestualmente, quando si ha a he fare on problemi multi-dimensionali, si tende a raggrupparli nel osiddetto insieme di problemi NP-hard

9

ossia una

parti olare lasse di problemi non risolvibili mediante algoritmi polinomiali. Ovviamente, più aumentano la omplessità delle spe i he e più aumentano i vin oli da soddisfare:

• Orientamento Si assume di solito he ogni rettangolo abbia una erta rotazione ssa, oppure he possa essere ruotato di

90◦ .

La rotazione dei rettangoli non

è ammessa per esempio nell'impaginazione dei giornali, quando gli item da tagliare sono de orati o non isomor (legno, lamiera).

• Tagli a ghigliottina Eettuare un taglio a ghigliottina signi a he gli items sono stati ottenuti attraverso una sequenza di tagli lato-a-lato paralleli ai lati del

di Non-deterministi Polynomial time ; sono problemi de isionali la ui soluzione non può essere determinata mediante l'utilizzo di software e omputazioni usuali, ma mediante appro

i euristi i 9 abbreviazione

1.2 Cutting and Pa king problems

19

ontenitore. Ciò è spesso imposto da limitazioni te ni he di ma

hine da taglio automati he ( ad esempio seghe verti ali o ir olari) o di al uni materiali. in gura 1.6 sono illustrati due esempi di piazzamenti di items on o senza il vin olo dei tagli a ghigliottina.

• Impa

amento a livelli Il piazzamento degli items è ottenuto posizionandoli da sinistra a destra in righe formanti diversi livelli. Il primo livello è il fondo del ontenitore, e ogni livello seguente è la linea orizzontale oin idente on il lato superiore dell'item più alto impa

ato a livello inferiore. In gura 1.7 se ne presenta un dettaglio illustrativo.

• Che kerboard pattern I he kerboard patterns, onos iuti an he ome

1-group patterns

(Gil-

more e Gomory, 1965) fanno parte della lasse spe iale dei tagli a ghigliottina a due fasi (

two-stage guillotine patterns ) he

non ne essitano

di essere ritagliati. Essi possono infatti essere prodotti ruotando la sega di

90◦ ,

dopo i tagli fatti in una prima fase. Le stris e ottenute nella

prima fase sono tutte tagliate nella se onda fase produ endo gli items desiderati (illustrazione in gura 1.8). Tagli di questo tipo ri hiedono meno tempo per le ma

hine, e sono parti olarmente interessanti nei settori on alta domanda quando le ma

hine rappresentano il ollo di bottiglia della produzione.

• Pa king Problem Un onstrained, Constrained o Doubly on-

strained

Indi ando on

xi

minimo e massimo numero di oggetti di ha he

Pi tipo i

i pezzi da impa

are e on

0 ≤ Pi ≤ xi ≤ Qi

e

Qi

rispettivamente il

da poter impa

are, si

e he in a

ordo on tali assunzioni si possono

distinguere tre tipi di problemi: 1.

2.

3.

L∗W ⌋ li ∗ wi L∗W ⌋ Constrained : ∀i, Pi = 0, Qi < ⌊ li ∗ wi

Un onstrained : ∀i, Pi = 0, Qi = ⌊

Doubly Constrained : ∃i : Pi > 0, ∃j : Qj = ⌊

L∗W ⌋ lj ∗ wj

20

1. Problemi di pa king e utting nei layout

Figura 1.6: taglio a ghigliottina: nel aso a sinistra il taglio, in quello a destra la disposizione originale

Figura 1.7: level pa king Per sempli ità, si deniranno i problemi su

essivi assumendo he ogni item abbia una orientazione ssa e he il vin olo del taglio a ghigliottina non sia imposto se non diversamente spe i ato. Inoltre i si on entrerà sugli algoritmi osiddetti o-line, ovvero algoritmi nei quali si ha ompleta onos enza di tutti i dati in input. Gli algoritmi on-line

10

sono inve e algoritmi

nei quali si impa

ano gli items in ordine dell'arrivo in input (senza onos ere l'item su

essivo). La des rizione del problema in modo più formale è la seguente: si ha un insieme di

j ∈ J = {1, ..., n},

n

oggetti rettangolari (re tangular items)

ognuno dei quali denito da una larghezza

wj

e da un'al-

algoritmi on-line i si riferis a a: J.Csirik, G.Woeginger, On-line pa king and

overing problems, in: Online algorithms, Springer Le ture Notes in Computer S ien e, 10 Sugli

vol. 1442, 1996, pp. 147-177

1.2 Cutting and Pa king problems

Figura 1.8: he kerboard pattern

Figura 1.9: esempio di tagli a s a

hi; prima e se onda fase

21

22

1. Problemi di pa king e utting nei layout

Figura 1.10: esempio di un sto k di rettangoli di misura 10x10 in ui ollo are i pezzi sopranumerati da 1 a 10. La gura mostra le soluzioni ottime per i problemi un onstrained (b), onstrained ( ) e doubly onstrained (d)

1.2 Cutting and Pa king problems tezza

hj ,

23

e unnumero illimitato di ontenitori rettangolari (

uguale larghezza

W

e altezza

bins ) aventi tutti

H.

L'obiettivo, ome sempre, è quello di impa

are tutti gli oggetti minimizzando il numero di ontenitori. E' ri hiesto di sistemare gli oggetti ortogonalmente senza sovrapposizioni (il lato lato

W

wj

dell'item

j

deve essere parallelo al

del ontainer). Si assumerà inoltre, senza perdita di generalità, he i

dati di input siano interi positivi, e he

wj ≤ W , hj ≤ H ,

Questo problema non è altro he una estensione del BPP

on

j = (1, ..., n).

one dimensional,

in quanto quest'ultimo è un aso spe iale del BPP a due dimensioni, he

ompare quando

hj = H , ∀j ∈ N .

Il primo tentativo di ostruire un modello del pa king problem a due dimensioni è stato fatto da Gilmore e Gomery (1965), attraverso un' estensione del loro appro

io al pa king a una dimesione. Essi proposero un appro

io a generazione di olonne basato sull'enumerazione di tutti i sottoinsiemi di items (patterns) he possono essere impa

ati all'interno di un singolo ontenitore. Sia

Aj

n elementi aij = (i = 1, ..., n) al j − esimo pattern e valore 0

una olonna di vettori binari di

he assumono valore 1 se l'item

i

appartiene

altrimenti. L'insieme di tutti i pattern a

ettabili viene rappresentato attraverso la matri e A, omposta da tutte le possibili olonne e il orrispondente modello matemati o, di tipo

minimizzare

−→ min(z) =

Aj , J = (1, ..., M)

set partitioning, è: M X

xj

j=1

soddisfa endo

−→

M X

aij xj = 1 , i = (1, ..., n)

j=1

x ∈ {0, 1} dove

xj

assume valore 1 se il pattern

,

j

j = (1, ..., M) appartiene alla soluzione, 0 altrimenti.

Si osservi he il modello mostrato è un valido modello an he per il

pa king

a una dimensione, on l'uni a dierenza he le olonne Aj soddisfano tutte Pn il vin olo i=1 aij hj ≤ H . A ausa dell'immenso numero di olonne he possono apparire in

A,

l'uni o modo di arontare il modello è quello di ge-

nerare dinami amente olonne quando e n'è bisogno. Ma mentre per il 1BP Gilmore e Gomory sono rius iti ad avere un appro

io di programmazione

24

1. Problemi di pa king e utting nei layout dinami a alla generazione di olonne, grazie all'asso iazione del problema a un K01, per il 2BPP essi hanno avuto di oltà nell'asso iarlo al orrispondente problema a due dimensioni. Così essi hanno trattato il problema nel

aso in ui gli oggetti devono essere impa

ati in righe he formano livelli.

LEVEL PACKING Molti degli algoritmi approssimati per il 2BPP suppongono di impa

are gli oggetti

a livelli, in ui il primo livello è ostituito dal fondo del ontenitore

e gli oggetti sono via via impa

ati appoggiando la loro base su di esso. Il livello superiore è determinato da una linea orizzontale ``disegnata sull'estremità superiore dell'oggetto più alto del livello sottostante (gura 1.7). Tre lassi he strategie per l'impa

amento a livelli sono state rilevate da al uni famosi algoritmi e in ognuno dei asi gli items sono inizialmente numerati in ordine de res ente di altezza e impa

ati nella orrispondente sequenza. Se si indi a on

j

l'item orrente e on

s l'ultimo livello reato, le tre strategie

possono essere illustrate ome segue:

• Next-Fit De reasing Height (NFDH) strategy: l'item j è impa

ato giusti ato a sinistra al livello s, se i sta. Altrimenti è reato un nuovo livello (s := s + 1), e j viene impa

ato giusti ato a sinistra in esso

• First-Fit De reasing Height (FFDH) strategy:

l'item

j

è impa -

ato giusti ato a sinistra al primo livello in ui ries e a stare, se 'è. Se nessun livello può ontenere

j , è reato un nuovo

livello inizializzato

ome in NFDH

• Best-Fit De reasing Height (BFDH) strategy:

l'item

j

è impa -

ato giusti ato a sinistra in quel livello, tra quelli dove ries e a stare, per il quale lo spazio in orizzontale inutilizzato è minimo. Se nessun livello può ontenere

j,

è reato un nuovo livello inizializzato ome in

NFDH

Nella gura 1.11 è possibile vedere le tre strategie.

1.2 Cutting and Pa king problems

25

Figura 1.11: problemi e strategie di level pa king: da sinistra a destra, NFDH, FFDH e BFDH

TWO DIMENSIONAL LEVEL BIN PACKING PROBLEM Indi hiamo on 2LBP il problema a due dimensioni ristretto al tipo di impa

amento a livelli, supponendo, senza perdere in generalità, he: 1. in ogni livello, l'oggetto a sinistra sia il più alto 2. in ogni ontenitore, il livello più basso abbia maggiore altezza degli altri 3. gli oggetti siano disposti e rinumerati per valori de res enti di tezza dell'item

hj

(al-

j − esimo)

Si dirà he l'oggetto più a sinistra di un livello e il livello più in basso di un ontenitore inizializzano il livello o il ontenitore. Si può e ientemente

n potenziali livelli (l'i−esimo livello è asso iato all'item i he lo inizializza), e n potenziali

ontenitori (il k −esimo ontenitore è asso iato al potenziale k −esimo livello

he lo inizializza). Sia quindi yi , i ∈ J una variabile binaria he assume valore 1 se l'item i inizializza il livello i, e valore 0 vi eversa. Allo stesso modo sia qk , k ∈ J una variabile binaria he assume valore 1 se il livello k inizializza il ontenitore k , e valore 0 vi eversa. Il modello del problema può essere il

ostruire il modello del problema 2LBP assumendo he i siano

seguente: min

n X k=1

qk

(1.12)

26

1. Problemi di pa king e utting nei layout

Figura 1.12: Level pa king normalizzato se ondo il 2LBP

suje t to

j−1 X

xij + yj = 1, j = (1, ..., n)

(1.13)

i=1

n X

wj xij ≤ (W − wi )yi , i = (1, ..., n − 1)

(1.14)

j=i+1 i−1 X

zki + qi = yi, i = (1, ..., n)

(1.15)

k=1

n X

hi zki ≤ (H − hk )qk , k = (1, ..., n − 1)

(1.16)

i=k+1

yi , xij , qk , zki ∈ {0, 1} ∀i, j, k

j > i (rispettivamente zki , k ∈ J \ (n) e i > k ) assume valore 1 se l'item j viene impa

ato a livello i (rispettivamente il livello i viene allo ato al ontenitore k ), e valore 0 altrimenti. Inoltre: dove

xij , i ∈ J \ (n)

(1.17)

e

•

le restrizioni

•

le equazioni (1.13) e (1.15) impongono, rispettivamente, he ogni item

j>i

e

i>k

seguono dalle assunzioni 1 e 3

sia impa

ato esattamente una volta, e he ogni livello usato sia assegnato a un uni o ontenitore

1.2 Cutting and Pa king problems •

27

le equazioni (1.14) e (1.16) impongono, rispettivamente il vin olo di larghezza di ogni livello usato e il vin olo di altezza di ogni ontenitore usato

Esperimenti omputazionali hanno mostrato he il modello è abbastanza utile nella prati a. Il loro uso diretto su un risolutore ommer iale di ILP produ e risultati molto buoni (e, in molti asi, la soluzione ottima) per istanze realisti he on tempi di CPU brevi. Inoltre al une varianti del problema 2LBP possono fa ilmente essere eettuate modi ando al uni vin oli, o aggiungendo altri vin oli lineari al modello. Il modello matemati o può an he essere usato per produrre lower bounds, rilassando i requisiti di integralità delle variabili.

NON-LEVEL ALGORITHMS Oltre all'impa

amento a livelli, nella Ri er a Operativa i sono stati altri appro

i al problema di pa king a due dimensioni. La prin ipale strategia ``non a livelli è onos iuta ome

Bottom-left

(BF), e onsiste nell'impa -

are l'item orrente nella posizione più bassa possibile, giusti ata a sinistra. Essa è stata analizzata da Baker (1980) et al., Ja kobs (1996) e Liu e Teng (1999).

Di questi ultimi l'algoritmo he ha onseguito risultati migliori è

stato quello di Baker. An he Barkey e Wang (1987) hanno proposto il loro appro

io BL per il aso in ui 'è un nito numero di ontenitori. Il loro algoritmo

Finite Bottom-Left (FBL) sistema gli items in ordine de res ente

di larghezza. L'item orrente viene poi impa

ato nella posizione più bassa di ogni ontenitore inizializzato, giusti ato a sinistra; se nessun ontenitore può ollo are l'item, ne viene inizializzato uno nuovo.

alternate dire tions (AD),

hanno proposto l'

Lodi et al.

(1999)

algoritmo he onsiste nell'i-

nizializzare L ontenitori (L è il lower bound) impa

ando sul loro fondo un sottoinsieme di items, seguendo una politi a de rementale best-t. Gli items rimanenti sono impa

ati, in un ontenitore alla volta, a stris e, alternativamente da sinistra a destra e da destra a sinistra. Non appena nessun item può essere impa

ato in nessuna delle due direzioni, un nuovo bin inizializzato o un nuovo bin già parzialmente riempito diventa quello orrente. L'algoritmo ha omplessità

O(n3 ).

Il metodo è illustrato nella gura 1.13.

28

1. Problemi di pa king e utting nei layout

Figura 1.13: Algoritmo AD, Alternate Dire tions Beasley (1985) ha onsiderato il

two dimensional utting problem

nel quale

ad ogni oggetto è asso iato un protto, on l'obiettivo di impa

are il sottoinsieme di oggetti aventi protto massimo in un uni o ontenitore (

sto k problem ).

Esso ha una formulazione ILP

11

utting

basata sulla rappresenta-

zione dis reta dello spazio geometri o e l'uso delle oordinate nelle quali gli oggetti possono essere ollo ati, vale a dire:

xipq =

(

1 0

se l'oggetto i è posizionato on il suo angolo sinistro in (p,q) altrimenti

Il dis orso vale per

i = 1, ..., n, p = 0, ..., W − wi

Un modello simile, nel quale le oordinate

p

e

e

q = 0, ..., H − hi .

q

sono arontate attraver-

so varibili di de isione distinte, è stato introdotto da Hadji onstantinou e Christodes (1995). Entrambi i modelli sono usati per fornire upper bounds attraverso rilassamenti Lagrangiani e l'ottimizzazione di subgradienti.

Un appro

io ompletamente diverso, inve e, è stato re entemente proposto da Fekete e S hepers (1997), attraverso una aratterizzazione grafo-teoreti a dell'impa

amento di un insieme di oggetti in un uni o ontenitore. Se pren-

Gw = (V, Ew ) (rispettivamente Gh = (V, Eh )) ome grafo intervallato avente un verti e vi asso iato a ogni item i nel pa king e un lato tra due verti i (vi , vj ) se e solo se le proiezioni degli items i e j sull'asse orizzontale (rispettivamente sul verti ale) si sovrappongono. E'

diamo in onsiderazione

11 Integer

Linear Progamming, programmazione lineare intera: sono tutti quei problemi lineari he presentano al loro interno solo variabili intere, ioè variabili he possono assumere solo i valori ontenuti all'interno del loro dominio di esistenza

1.2 Cutting and Pa king problems

29

stato dimostrato appunto da Fekete e S hepers he se il pa king è a

ettabile allora:

•

per ogni insieme

Evi ∈S wi ≤ W • Ew

T

S

Gw (rispettivamente Evi ∈S hi ≤ H )

di solidi di

(rispettivamente

di

Gh )

si ha he

Eh = {}

Figura 1.14: Algoritmo di Fekete e S hepers

ALGORITMI METAEURISTICI L'

euristi a12

è un metodo di appro

io alla soluzione dei problemi he

non segue un hiaro per orso, ma si ada all'intuito e allo stato temporaneo delle ir ostanze, al ne di generare nuova onos enza. È opposto al pro edimento algoritmi o e quindi, in ambito informati o, si denis e euristi o il lavoro di un software he non opera me

ani amente, ma utilizza inve e una te ni a virtualmente reativa, ioè non si limita ad analizzare i dati se ondo

onfronto di dati noti, ma prova a simularne il omportamento 12 di

13

.

derivazione gre a, rappresenta una parte dell'epistemologia e del metodo s ienti o i più diusi software di questo tipo, troviamo gli antivirus e le appli azioni ontro il phishing per ui è fondamentale adarsi a te ni he non onsuete, ome inve e lo è l'analisi per onfronto 13 tra

30

1. Problemi di pa king e utting nei layout Nel settore della Ri er a Operativa, quindi più in generale dove si fondono informati a e matemati a, si utilizzano algoritmi euristi i ome parti olari tipi di pro edimenti le ui soluzioni non rispe

hiano la soluzione ottima per quel dato problema. L'euristi a è un appro

io di risoluzione dei problemi molto diuso nella

simulazione

per vari possibili motivi:

•

la risoluzione del problema ottimo può essere impossibile

•

la risoluzione del problema ottimo può essere troppo ostoso in termini di tempo o di apa ità di elaborazione

Le te ni he metauristi he sono oggi un frequente strumento usato per trovare la soluzione approssimata dei problemi di ottimizzazione ombinatoria. Dowsland (1993) presentò uno dei primi appro

i metauristi i al 2BPP. Il suo algoritmo

simulated annealing 14

esplora sia le soluzioni a

ettabili he le so-

luzioni nelle quali gli items si sovrappongono. Durante la ri er a, la funzione obiettivo onsiste per iò nell'eliminazione totale delle aree sovrapposte, e il vi inato ontiene tutte le soluzioni orrispondenti allo spostamento verti ale o orizzontale degli items.

Appena una nuova soluzione migliore di quella

orrente viene trovata, l'upper bound è ssato alla sua altezza.

Un'estensione dell'appro

io di Dowsland al 2BP è stato proposto da Faero et al. (1999). Essi usano un simile vi inato e una simile strategia di ri er a all'interno di un appro

io

guided lo al sear h.

Dato un lower bound e

un upper bound sul valore della soluzione ottima, se questi non oin idono, l'algoritmo assegna asualmente gli items impa

ati nel ontenitore di indi e più alto ad altri ontenitori. La nuova soluzione è di solito non ammissibile, osì la nuova funzione obiettivo risulta essere la totale eliminazione delle aree sovrapposte, più un termine he penalizza, durante la ri er a, i modelli inammissibili. Il vi inato è esplorato attraverso gli spostamenti degli items. Minimizzare la nuova funzione obiettivo orrisponde a trovare una soluzione 14 pro esso

he mira a trovare un minimo globale quando si è in presenza di più minimi lo ali. deriva dalla s ienza dei metalli, dov'è usato per des rivere il pro esso di eliminazione di difetti reti olari dai ristalli tramite una pro edura di ris aldamento seguita da un lento rareddamento (molto usato in Mi roelettroni a). Nel nostro aso un difetto reti olare

orrisponde ad una ombinazione errata di due oggetti.

1.2 Cutting and Pa king problems

31

ammissibile he oinvolge un ontenitore in meno. Il pro esso è iterato no a quando l'upper bound non eguaglia il lower bound, oppure no a quando non si raggiunge un limite di tempo pressato. Spe iali te ni he per ridurre la omplessità omputazionale per l'esplorazione di questo grande vi inato sono state implementate.

Lodi et al. (1999) hanno sviluppato un algoritmo

tabu sear h

per il 2BPP.

La aratteristi a prin ipale di quest'ultimo è l'adozione di uno s hema di ri er a e un vi inato he sono indipendenti dallo spe i o pa king problem da risolvere. La struttura può an he essere usata per ogni variante del 2BPP ed è stata fa ilmente estesa an he al problema a tre dimensioni. Partendo da una soluzione a

ettabile, le mosse la modi ano, attraverso un euristi o ostruttivo, ambiando l'impa

amento di un sottoinsieme momento impa

ati in

k

S

di items al

diversi ontenitori, e er ando di riempire uno spe-

i ato target bin (un ontenitore he può essere fa ilmente riempito). Sia

Si

l'insieme degli items momentaneamente impa

ati nel ontenitore i: il target bin

t

è quello he minimizza, tra tutti i bins

ϕ(Si ) = α

P

i,

la funzione:

wj hj |Si | − WH n

j∈Si

(α rappresenta un peso positivo pre-stabilito). Tale formula fornis e appunto la misura della fa ilità on ui un ontenitore può essere riempito. Una volta selezionato il target bin, il sottoinsieme un item

j,

S

è denito in modo da in ludere

nel target bin e gli oggetti ontenuti attualmente dagli altri

bins. Il nuovo pa king per euristi o A su

S.

S

Il valore di

k

è ottenuto eseguendo un appropriato algoritmo

k,

he denis e la dimensione e la struttura del

vi inato orrente, è automati amente aggiornato durante la ri er a in modo da evadere dall'ottimo lo ale. Se la mossa impa

a gli items

ontenitori, ioè l'item

j

in

k

(o meno)

è stato rimosso dal target bin, un nuovo item è stato

selezionato, un nuovo insieme

S

è denito, e una nuova mossa è stata esegui-

k bins, o un diverso item j dal target bin (se tutte le possibili ongurazioni di k bins sono state provate per il orrente item j ). Se l'algoritmo si blo

a, ioè il target bin non è riempito, il vi inato si allarga aumentando il valore di k no a un

ta. Altrimenti

S

S

è ambiato selezionando un diverso insieme di

limite superiore pressato. C'è una

tabu list

e un

tabu tenure

per ogni valore

32

1. Problemi di pa king e utting nei layout di

k.

Un alto valore di

k

impli a una potente ri ombinazione, ma an he l'e-

vidente in onveniente di un elevato tempo omputazionale per l'esplorazione del vi inato. L'uni a parte he dipende dallo spe i o problema è l'euristi o

ostruttivo, usato per ottenere la prima soluzione e per ri ombinare gli items ad ogni mossa.

ALGORITMI ESATTI Martello e Vigo (1998) hanno proposto un algoritmo esatto per il 2BPP. Gli items sono inizialmente sistemati in ordine de res ente rispetto alla loro area, e una pro edura di riduzione prova a determinare il pa king ottimale di al uni ontenitori, ridu endo quindi la dimensione dell'istanza. La prima soluzione in ari a, di valore si basa su uno s hema

z∗,

è poi ottenuta euristi amente. L'algoritmo

two-level bran hing :

• outer bran h-de ision tree :

a ogni nodo de isionale, un item è assegnato

a un ontenitore senza spe i are la sua posizione attuale

• inner bra h-de ision tree :

è determinato un pa king a

ettabile (se

esiste) per gli items assegnati momentaneamente a un ontenitore euristi amente o attraverso un algoritmo he enumera tutti i possibili modelli L'outer bran h-de ision tree è ri er ato in un modo detto

depth-rst,

fa en-

do uso di lower bound. Quando è possibile stabilire he ulteriori items non an ora assegnati possono essere messi in un dato ontenitore inizializzato, questo bin viene hiuso: un bin inizializzato e non hiuso è hiamato Al livello

k (k = 1, ..., n),

a tive.

l'item k è assegnato, a turno, a tutti i ontenitori

inizializzati e, possibilmente, ad un nuovo bin (se il numero di bins ri hiesto dalla soluzione parziale orrente è minore di gnamento di un item

k

z ∗ − 1).

a un ontenitore già ontenente un insieme

è ontrollata euristi amente. Un lower bound

I

L'a

ettabilità dell'asse-

L(I)

ba ktra king.

Altrimenti, sono appli ati a

di items

è al olato per l'istanza

denita dagli items orrentemente assegnati al ontenitore: se

segue un

I

I

L(I) > 1

algoritmi euristi i: se

un single-bin pa king a

ettabile viene trovato, si riprende l'enumerazione. Se non lo si trova, lo s hema

inner bran hing

elen a tutti i possibili modi di

1.2 Cutting and Pa king problems impa

are gli items

ward :

I

33

in un uni o bin attraverso il prin ipio

left-most down-

ad ogni livello, l'item su

essivo viene posizionato, a turno, in tutte le

posizioni dove esso ha il lato sinistro adia ente al lato destro di un altro item o al lato sinistro del ontenitore, e il lato inferiore adia ente al lato superiore di un altro item o al lato inferiore del ontenitore. Non appena si trova un pa king a

ettabile per tutti gli items tale pa king non esiste, si esegue un

I,

si riprende l'enumerazione. Se un

outer ba ktra king.

ULTIME VERSIONI E APPLICAZIONI I pa king problems a due dimensioni ontinuano a essere studiati. Ultimamente riveste parti olare importanza l'arti olo riguardante il

two-dimensional

orthogonal pa king probelm, redatto da Clautiaux, Carlier e Moukrim (2006). Essi propongono pro edure di riduzione e un nuovo metodo esatto soprannominato TSBP (

two-step bin pa king ).

Il metodo ridu e sostanzialmente il

numero di nodi visitati del metodo di Martello e Vigo (1998). Questo può essere spiegato per il fatto he per molte istanze non ammissibili, il problema rilassato non ha soluzioni. Inoltre essi propongono metodi per risolvere parte delle ridondanze he ri orrono nel metodo

bran h & bound

e nuovi lower

bounds he possono essere usati on risultati positivi.

Sempre Clautiaux, Carlier e Moukrim, riferendosi al bin pa king problem

on aggiunta di varianti hanno presentato un nuovo arti olo ( he ompare su Operations Resear h Letters) in ui propongono un nuovo metodo esatto per il problema. Esso si basa su una de omposizione iterativa dell'insieme di items all'interno di due disgiunti sottoinsiemi. L'algoritmo, onfrontato on al uni ben hmar ks della letteratura onferma l'e ienza del metodo.

un onstrained two-

Interessante an he l'arti olo di Cui e Zhang (2006) sull'

dimensional utting problem of re tangular pie es. algoritmo two-stage, ovvero ome tagliare generi i

Esso des rive un nuovo blo

hi in due fasi, on

altre due o più fasi ri hieste per tagliare i blo

hi in pezzi:

in un primo

momento tagli verti ali dividono il foglio di materiale in segmenti, poi tagli orizzontali dividono i segmenti in blo

hi. Un generi o blo

o ontiene

34

1. Problemi di pa king e utting nei layout generi he stris ie, e ogni taglio su un blo

o produ e una di queste stris ie. L'algoritmo presentato ri orre a una programmazione dinami a per determinare il layout delle stris ie per ogni blo

o, risolve un problema di tipo knapsa k per ottenere il layout dei blo

hi su ogni segmento e il layout del segmento su ogni foglio di materiale. I risultati omputazionali indi ano he l'algoritmo è molto e iente e ha tempi di ese uzione ragionabili.

Solo un anno fa inoltre al uni ri er atori dell'università della Danimar a (Pisinger, Sigurd, 2005) hanno pubbli ato un arti olo sul pa king a due dimensioni onsiderando due nuove variabili: il osiddetto

sized bin pa king problem

two-dimensional variable

(2DVSBPP) è il problema di impa

are un insieme

di items in un insieme di bins rettangolari aventi diverse misure e diversi

osti, e l'obiettivo è quello di minimizzare il osto dei ontenitori usati per impa

are gli oggetti. Nello s ritto us ito lo s orso anno su Dis rete Optimization gli autori presentano una formulazione intera lineare del problema e introdu ono diversi lower bound. In esso è inoltre sviluppato un algoritmo esatto basato sul

bran h-and-pri e.

1.2.4 Two Dimensional Strip-pa king Problem Questo tipo di problema ha ome s opo quello di allo are ortogonalmente tutti gli item su di una stris ia (assolutamente senza al una sovrapposizione) minimizzando l'altezza totale o

upata dal pa king. Il problema in questione è di tipo NP-hard e quindi la ri er a ha improntato gran parte delle soluzioni basandosi su algoritmi approssimati, i quali si avvi inano molto alla soluzione ottima, ma non garantis ono l'ottimizzazione ompleta su tutti gli insiemi di

two dimensional strip-pa king problem (2SPP) può essere visto ome la trasformazione del problema di bin pa king a una dimensione,

dati proposti. Il

dove quest'ultimo ha soluzione ``fa ile''. Partendo infatti da una qualsivoglia istanza del 1BPP si ottiene fa ilmente un'istanza del 2SPP aggiungendo al problema una variabile

hj = 1

per

j ∈ J:

il valore della soluzione ottima di

tale istanza è ottima an he per l'istanza del 1BPP. Tale problema ompare in diversi ontesti reali, ome nel taglio di rulli di

arta o di tessuto, nel taglio di legno, metallo o vetro da pezzi si sto ks

1.2 Cutting and Pa king problems

35

standardizzati, nell'allo azione di memoria nei omputer, per elen are solo al uni degli usi più omuni.

Figura 1.15: al une soluzioni al 2SPP basate sull'euristi a two dimensional variable sized bin pa king problem (2DVSBPP)

ALGORITMI ESATTI Il miglior algoritmo esatto del problema è stato presentato da Martello, Mona i e Vigo (2003). In esso si assume he gli items abbiano un'orientazione ssa, ovvero he non possano essere ruotati. Si suppone inoltre he tutti i dati in input siano positivi interi, e he

wj ≤ W (j = 1, ..., n).

Per determi-

nare la soluzione esatta del 2SPP, sono stati inseriti parti olari lower bounds (ottenuti al uni da sempli i onsiderazioni geometri he, altri da un nuovo rilassamento del problema) in un ``adattamento dell'algoritmo bran h-andbound proposto da S heithauer (1997) e Martello et al. (2003) per riempire un uni o ontenitore bidimensionale. L'albero de isionale funziona in questo modo: ad ogni nodo de isionale, la potenziale soluzione orrente, he impa

a gli items di un sottoinsieme

I ⊂ J,

è in rementato selezionando a turno

36

1. Problemi di pa king e utting nei layout ogni item

j ∈ J \ I,

e generando nodi dis endenti allo ando

j

in tutte le sue

posizioni ammissibili. È stato provato in Martello et al. (2000) he gli items di I denis ono un ``involu ro he separa le due regioni dove gli items

J \I

possono o no essere posizionati, e iò è su iente per generare nodi orrispondenti al piazzamento dell'angolo inferiore sinistro di

j

nei punti dove la

pendenza dell'involu ro ambia da verti ale a orizzontale. Questi sono hiamati

orner points

e possono essere determinati in un tempo

O(|I| log |I|):

Lo s hema bran h-and-bound è stato poi migliorato in due modi: attraver-

Figura 1.16: involu ro asso iato agli items di I = {1, 2, 3, 4, 5} dove i orner points sono

indi ati on un puntino nero.

so una te ni a per evitare la generazione multipla di nodi de isionali he produ ono lo stesso modello, e attraverso l'aggiunta di e a i algoritmi di approssimazione. Si onsiderino, ad un dato livello due punti d'angolo

a, b

e due items

j1 , j2 ∈ J \ I :

k

dell'albero de isionale,

la regola di base potrebbe

generare quattro nodi, orrispondenti a quattro oppie di tipo ( orner point, item): (a, j1 ), (a, j2 ), (b, j1 ), (b, j2 ), dove la oppia indi a il nodo. Tra i gli di (a, j1 ) si può poi generare un nodo orrispondente alla oppia (b, j2 ), e,

k + 1, si può generare, tra i gli di (b, j2 ), un identi o nodo a (a, j1 ). Per evitare situazioni di questo genere, he non si

allo stesso livello

orrispondente

presentano solo tra i gli, ma an he, più generalmente, tra dis endenti di nodi fratelli, Martello et al. hanno adottato la seguente te ni a. Per ogni

1.2 Cutting and Pa king problems

37

potenziale nodo, orrispondente al piazzamento di un item

j

in un angolo

a,

essi determinano gli involu ri he si dovrebbero generare dall'insieme di item

{j} ∪ (I \ {i}), ∀i ∈ I . Se esiste un item i ∈ I , orrentemente piazzato, in un

orner point b, per il quale l'involu ro orrispondente a {j} ∪ (I \ {i}) in lude b tra i suoi punti d'angolo, sappiamo he il orrente nodo potenziale potrebbe produrre un modello identi o a quello prodotto ambiando l'ordine nel quale

i

e

j

sono onsiderati nel pro esso di bran hing. E

o per hé il nodo è gene-

rato solo se

j > i.

Per trovare una buona soluzione iniziale ammissibile per il

nodo padre, o per migliorare la solizione orrente per i nodi dis endenti, sono implementati al uni lassi i algoritmi euristi i della letteratura (Coman et al. (1980); Baker et al. (1980)...).

Figura 1.17: illustrazione s hemati a e molto sommaria del pro esso strip-pa king

ALGORITMI METAEURISTICI Un appro

io metauristi o interessante è quello presentato da Iori, Martello e Mona i (2003). Il 2SPP viene risolto attraverso una ombinazione tra un algoritmo 15 metodo

tabu sear h

15

e un algoritmo di tipo geneti o

. L'algoritmo di

euristi o di ri er a ed ottimizzazione, ispirato al prin ipio della selezione naturale di Charles Darwin he regola l'evoluzione biologi a. Gli algoritmi geneti i sono appli abili alla risoluzione di un'ampia varietà di problemi d'ottimizzazione non indi ati

38

1. Problemi di pa king e utting nei layout tipo tabu sear h di riferimento è l'algoritmo 2BP-TS proposto da Lodi, Martello e Vigo (1999) eseguito indi ando on

z∗

il valore della soluzione orrente

16

del 2SPP, inizialmente al olata attraverso algoritmi BUILD

e

T P2SP 17 ,

e

appli ando parti olari pro edure di post-ottimizzazione des ritte dagli autori. L'algoritmo geneti o è inve e un algoritmo sviluppato dagli stessi e indi ato

on 2SP-GA. Esso si basa sulla permutazione della struttura dei dati he rappresenta l'ordine nel quale gli items sono impa

ati nella stris ia.

La

dimensione della popolazione è ostante ma vengono prodotti nuovi individui attraverso riteri di riproduzione. È inoltre ottenuta una diversi azione attraverso l'immigrazione e la mutazione. La ri er a è inoltre intensi ata attraverso ri er a lo ale.

Inne nell'algoritmo, viene onsiderata la storia

dell'evoluzione, in modo da intensi are la ri er a in aree promettenti, e da evitarla nei minimi lo ali. Sui due algoritmi metauristi i sono stati eettuati vari esperimenti omputazionali sia su istanze prese dalla letteratura sia su istanze reate asualmente: sia il 2SP-TS he il 2SP-GA hanno mostrato un buon omportamento empiri o. In parti olare si è potuto notare ome l'appro

io geneti o abbia migliori prestazioni nel aso di istanze di pi

ole dimensioni e on pi

oli valori della misura

W

della stris ia da riempire, mentre l'opposto a

ade per l'altro algo-

ritmo. Tuttavia le performan e migliori sono state ottenute sperimentando

hybrid algorithm, ovvero

l'

la ombinazione dei due algoritmi sopra itati.

Oltre al metodo sopra menzionato, nella tabella 1.1 (al termine del apitolo) è riportato un elen o di al uni di altri re enti sviluppi metauristi i per il 2SPP. In parti olare in essa sono stati distinti:

•

quattro sottotipi di

strip pa king problem :

per gli algoritmi lassi i, ompresi quelli in ui la funzione obiettivo è dis ontinua, non derivabile, sto asti a, o fortemente non lineare. 16 algoritmo he parte dalla soluzione del rilassamento del 1CBP e ostruis e una soluzione ammissibile per il 2SPP ongiungendo i tagli per ri ostruire l'item di origine. Si veda a proposito: Martello, Mona i e Vigo: An exa t approa h to the Strip-Pa king problem 17 inizializza la stris ia ad una lunghezza L, e onsidera gli items a se onda dell'ordine in

ui vengono dati. Per poi impa

arli se ondo un pre iso metodo. A riguardo si proprone:

Iori, Martello, Mona i: Metaheuristi Algorithms for the Strip Pa king Problem

1.2 Cutting and Pa king problems 

RF

→

i pezzi possono essere ruotati di

39 90◦

ma non sono ri hiesti

90◦

e sono ri hiesti tagli a

tagli a ghigliottina



RG

→

i pezzi possono essere ruotati di

ghigliottina



OF

→

l'orientamento dei pezzi è sso ma non sono ri hiesti tagli

a ghigliottina



OG

→

l'orientamento dei pezzi è sso e sono ri hiesti tagli a

ghigliottina

•

tre gruppi di appro

io alla soluzione dei metauristi i (Hopper e Turton, 2000/2001):

1. Il metodo del primo gruppo usa una odi a delle soluzioni. Di solito, una soluzione genera una sequenza di piazzamenti per i pezzi. La ri er a viene svolta dal relativo euristi o nello spazio delle soluzioni e tipi amente usa operatori indipendenti dal problema 2. Gli appro

i per le soluzioni del se ondo gruppo sono in una posizione intermedia. Mentre, da un lato, soluzioni odi ate, ontengono già informazioni geometri he o di layout, è ri hiesto un pro edimento addizionale di piazzamento per il posizionamento nale. Tipi i di questo gruppo è una odi a spe i a al problema di riferimento, spesso basata su gra 3. L'appro

io del gruppo

3

non usa la odi a. La ri er a avviene

direttamente nello spazio dei layout ompletamente deniti, he sono poi manipolati ome detto da spe i i operatori

•

tre tipi di algoritmi metaeuristi i:



GA



SA

→

simulated annealing



TS

→

tabu sear h

→

genethi algorithms

40

1. Problemi di pa king e utting nei layout LEVEL PACKING An he per il

two dimensional strip pa king problem

ome per il BPP

esiste un pa king a livelli, proposto da Lodi, Martello e Mona i (2002). Tale alternativa onsiste nel modi are la funzione obiettivo eliminando tutti i vin oli e le varibili relativi al bin pa king problem visto pre edentemente, in modo da ottenere il modello seguente:

minimizzare

−→ min

n X

hi yi

i=1

soddisfa endo

−→

j−1 X

xij + yj = 1, j = {1, ..., n} ,

i=1

n X

wj xij ≤ (W − wj )yi , i ∈ N = {1, ..., n − 1}

j=i+1

yi , xij ∈ {0, 1} ∀i, j

1.2.5 Two Dimensional Knapsa k Problem 18

Consideriamo innanzitutto un problema knapsa k di tipo rettangolare ossia un problema a due dimensioni avente ome

items

,

degli oggetti rettan-

golari.

N = (1, ..., n) pi

oli rettangoli (gli items), in ui ognuno ha una larghezza wj , un'altezza hj e un protto pj on j ∈ N e un ontenitore di larghezza W e altezza H . L'obiettivo onsiste, analogamente agli Sono dati: un insieme di

altri asi pre edenti, nell'inserire nel ontainer (knapsa k) un sottoinsieme di items he massimizzi il protto; il vin olo è he gli oggetti non si sovrappongano e he ognuno di essi abbia il lato

hj

parallelo al lato

Si noti he 2KP è una generalizzazione del già itato

H

19

del ontenitore

.

1-dimensional Knapsa k

problem, visto ome aso parti olare avente hj = H ∀j ∈ N . An he il two-dimensional Knapsa k Problem (2KP) è un problema NP-hard e in letteratura sono stati studiati molti metodi per risolverlo, a partire dal

in poi hiameremo tale problema un re tangle pa king problem denis e on questi vin oli un tipo di problema denominto orthogonal pa king

18 d'ora 19 si

problem without rotation

1.2 Cutting and Pa king problems

41

fondamentale studio di Gilmore e Gomory (1965). Tuttavia, sembra non es-

worst- ase

sere onos iuto nessun algoritmo approssimato he garantis a una

performan e ; iò è sorprendente dato he al uni risultati di questo genere sono inve e noti per il onnesso problema di impa

amento a due dimensioni. Pro ediamo illustrando un naturale rilassamento del 2KP:

max

X

pj xj

j∈N

X

(wj hj )xj ≤ W H

j∈N

x ∈ {0, 1} , (j ∈ N) j, (j ∈ N)

wj hj , uguale all'area del rettangolo j nel 2KP, e apa ità del ontenitore W H , uguale all'area del

ontenitore nel 2KP. Per una istanza I del 2KP, sia OP T (I) la soluzione ottima e UKP (I) l'upper bound su OP T (I) orrispondente alla soluzione otnel quale ogni item

ha un protto

pj

e peso

tima della formulazione sopra des ritta. Il rapporto di performan e peggiore è denito ome:

. inf r(UKP ) = I Il worst- ase ratio trovato nora è



OP T (I) UKP (I)

r(UKP ) =



1 . Tale rilassamento, approfon3

dito da Caprara e Mona i (2003) ostituis e una buona base di partenza per quattro nuovi algoritmi per risolvere il 2KP: essi rappresentano l'appro

io esatto al problema più re ente. Oltre a Caprara e Mona i (2003), altri studi sono stati ondotti a riguardo:

Beasley Basley (2003) ha presentato un algoritmo euristi o di tipo geneti o per la risoluzione del problema; è basato su una nuova e non lineare formulazione del problema ed è rappresentato da una popolazione euristi a (

Population

heuristi s, PH) dove la popolazione delle soluzioni al problema si evolve progressivamente. La nuova PH proposta si dis osta dalle ``sempli i popolazioni euristi he pre edenti e può essere sintetizzata nel seguente modo: 1. si genera una popolazione iniziale

42

1. Problemi di pa king e utting nei layout 2. si valuta il tness e l'untness degli individui (repeat) 3. si selezionano due individui genitori della popolazione (random) 4. si ri ombinano i genitori produ endo un solo glio, attraverso il rossover 5. si muta il glio; uno ogni die i gli viene mutato 6. si valuta il tness e l'untness del glio e miglioralo usando uno s hema euristi o di miglioramento 7. si sostituis e un membro della popolazione on il glio usando uno s hema di rimpiazzamento, a meno he il glio non sia un dupli ato di un membro della popolazione, in tale aso lo si s arta 8. i si ferma dopo aver riportato la miglior soluzione in ontrata

Hadji onstantinou and Christodes Hadji onstantinou e Christodes (1995) hanno presentato una pro edura esatta

tree-sear h 20

per risolvere il kanpsa k a due dimensioni.

Essi han-

no onsiderato il aso in ui 'è un numero massimo di volte in ui un pezzo può essere usato. L'algoritmo limita la dimensione del

tree

usando un bound

derivante da un rilassamento lagrangiano della formulazione binaria del problema. Un'ottimizzazione del subgradiente viene poi usata per ottimizzare il bound. Le performan e omputazionali dell'algoritmo indi ano he la pre edente è una pro edura veramente apa e di risolvere ottimamente il problema nel aso di medie dimensioni.

R.Alvarez-Valdes, F.Parrenho, J.M.Tamarit Tali ri er atori presentano nel 2006 un algoritmo tabu sear h ompleto di mosse basate sulla riduzione e l'inserzione di pezzi, di pro edure di intensi azione e diversi azione basate su una memoria a lungo termine. parti olare l'e ienza delle mosse è basata su una strategia

In

merge and ll.

I risultati omputazionali mostrano he tutte queste idee funzionano bene in 20 ri er a

ad albero

1.2 Cutting and Pa king problems

43

Figura 1.18: strategia Merge and Fill parti olare per i problemi

onstrained

e

doubly onstrained.

Hadji onstantinou, Iori Presentano un nuovo appro

io euristi o per risolvere il problema, sempli e ma molto e iente:

nella fase preliminare, vengono al olati sempli i up-

per bounds e soluzioni iniziali sono ottenute attraverso

greedy algorithms.

In seguito è eseguita una ri er a geneti a, he usa la selezione dei genitori, la teoria etilista, l'immigrazione, e diversi operatori rossover. L'appro

io geneti o diviene ibrido dopo aver usato un euristi o on-line. Risultati omputazionali mostrano he l'algoritmo trova la miglior soluzione in un tempo

omputazionale molto velo e e he in molti asi migliora gli altri metauristi i presenti in letteratura.

44

1. Problemi di pa king e utting nei layout

1.3 Fa ility layout problem Il

fa ility21 layout problem

(FLP) si riferis e all'allo azione di un erto

spazio disponibile a una varietà di attività he hanno diverse relazioni tra di loro. Si tratta di un problema di ottimizzazione ombinatoria he si presenta in una moltitudine di problemi ome ad esempio nella progettazione dei layout di ospedali, s uole e aeroporti; nei problemi di progettazione di impianti elettri i; nei magazzini; nella progettazione di turbine elettri he; et . Tuttavia la maggior parte delle volte il fa ility layout problem è denito ome la determinazione dell'organizzazione si a di un sistema di produzione. Dove posizionare gli impianti e le attrezzature e una loro e iente progettazione sono problemi strategi i e fondamentali he ogni industria di produzione si trova a dover arontare. Lo s opo prin ipale di un algoritmo he risolva le ``funzionalità onsiste nell' ``arrangiare in maniera ottima gli elementi oinvolti nella progettazione del layout (elementi he naturalmente variano in base al ontesto) per trovare la via più e iente di disposizione degli oggetti. La ragione prin ipale, ome già detto pre edentemente, risiede nel fatto he i osti di

material handling

oprono una buona per entuale dei osti totali di un'impresa, ed è quindi

22

onveniente limitarne lo sviluppo e l'aumento

. Un layout dei ma

hinari

e iente può arrivare a ridurre questi osti dal 10% al 30% l'anno. Un layout ine iente può infatti portare a un a

umulo di gia enze di work-in-progress, un sovra

ari o dei sistemi di movimentazione dei materiali, tempi di setup ine ienti. Inoltre, il fa ility layout problem rappresenta un investimento ostoso e a lungo termine. An he le modi he ri hiedono grandi spese per hé non possono essere eettuate fa ilmente: il re-layout delle strutture non è solo un onsumo di tempo, ma interrompe le attività dei lavoratori e il usso dei materiali. È per questo he l'impatto strategi o della progettazione del layout non dovrebbe essere ignorato. Negli ultimi anni, molte ri er he hanno proposto una varietà di pro edure 21 i

si riferis e alla funzionalità nel layout di un erto ambito progettuale ri er he hanno stimato he l'8% del prodotto lordo nazionale degli USA è stato speso e ontinua ad esserlo attualmente per nuovi impianti e attrezzature, e per la manutenzione e la modi a di quelli già esistenti. Altri studi dimostrano inve e he i osti relativi agli spostamenti dei materiali oprono il 20-30% dei osti di un'impresa 22 al une

1.3 Fa ility layout problem

45

per risolvere il problema. In parti olare si è operato er ando di sviluppare una soluzione ottima per l'allo azione di attrezzature dalle forme rettangolari, usando l'adia enza ome riterio di interesse nel selezionare le attrezzature

he devono ondividere i onni. Molte delle pro edure re enti inoltre ri hiedono interazioni on il progettista degli impianti e ne essitano di un buon progetto ome s heletro iniziale. Data una matri e di usso tra diversi impianti e l'area allo ata a ias uno di essi, la ri er a del layout ottimo è stata messa a fuo o sviluppando diverse te ni he. La maggior parte delle pro edure sono state lassi ate o-

single-row quando gli impianti sono sistemati linearmente su di una la, oppure multi-row fa ilities quando gli impianti sono sistemati linearmente me

in due o più le.

Due lassi di modelli e algoritmi sono inoltre stati usati

per risolvere sia i problemi di layout single-row he quelli di tipo multi-row: pro edure ottimali e euristi i. Di seguito saranno elen ate le prin ipali.

1.3.1 Modelli per il fa ility layout problem MODELLO QAP Il

quadrati assignment problem

(QAP) è oggigiorno la formulazione più

utilizzata nelle risoluzioni fo alizzate sulle funzionalità, pertanto su questo modello verrà posta maggore attenzione. Tale formulazione usa il bari entro della lo azione ome punto di riferimento per valutare la distanza tra due attrezzature. Inoltre molto spesso, le formulazioni diverse dal QAP sono basate su varianti del QAP o usano il QAP ome struttura di riferimento. Koopmans e Be kman (1957) sono stati i primi a formulare il fa ility layout problem ome QAP. Il nome ``quadrati assignment problem è stato s elto per hé la funzione obiettivo è una funzione polinomiale di se ondo grado rispetto alle variabili, e i vin oli sono uguali ai vin oli del problema dell'assegnamento. L'obiettivo del QAP è quello di trovare l'assegnamento ottimo di

n

fa ilities (impianti, dipartimenti o stazioni ma

hina) in

n

siti in modo

da minimizzare il osto della movimentazione dei materiali espresso ome il prodotto del usso di lavoro per la distanza. Il QAP può essere formulato

46

1. Problemi di pa king e utting nei layout

ome segue: min

n X n X n X n X

Aijst xij xst

(1.18)

i=1 j=1 s=1 t=1

ondizione1

n X

xij = 1 , ∀j

(1.19)

xij = 1 , ∀i

(1.20)

i=1

ondizione2

n X i=1

variabili dove

→ xij ∈ {0, 1}

,

∀i, j

(1.21)

   wis djt se i 6= s oppure j 6= t Aijst Fij se i = s oppure j = t   ∞ se i = s oppure j 6= t

(1.22)

wis è il usso tra gli impianti i e s, wii = 0 , djt la distanza tra le posizioni j e t, djj = 0 , Fij il osto sso per lo are l'impianto i nella posizione j , e ( 1 se l'impianto i è allo ato alla posizione j xij (1.23) 0 altrimenti Il vin olo (1.19) è la restrizione he solo un impianto può essere piazzato in una determinata posizione, mentre il vin olo (1.20) assi ura he ogni posizione può essere assegnata a un solo impianto. minimizzare il usso totale tra gli impianti

L'obiettivo è quello di

i(i = 1, ..., n) e s(s = 1, ..., n).

La

funzione obiettivo può an he essere ompletata on un fattore he onsidera il osto sostenuto se l'impianto

i

è piazzato nella posizione

s;

la funzione

diviene pertanto:

min

n X n X n X n X i=1 j=1 s=1 t=1

Aijst xij xst +

n X n X

cis xis

(1.24)

i=1 s=1

Il QAP è un problema NP-hard (Sahni e Gonzalez, 1976): nora l'istanza più grande per la quale è stata trovata una soluzione ottima ha una dimensione di

n ≈ 30.

Per questa ragione sono stati molti gli euristi i proposti

per risolvere il problema.

In parti olare Lawler (1963) ha presentato una

formulazione generale del QAP, del quale sostiene he la formulazione di

1.3 Fa ility layout problem

47

Koopmans-Be kmann sia un aso parti olare, e ha proposto un metodo per

al olare la soluzione ottima seguendo una logi a di partizione. Egli ha inoltre dimostrato l'equivalenza del problema QAP on un problema di assegnamento lineare avente erti vin oli addizionali: un QAP on essere reso lineare denendo

n4

variabili

yijpq

n2

variabili

può

, dove

yijpq = xij xpq Christodes et al.

xij

(1.25)

(1980) hanno proposto una te ni a di bound fortemen-

te non lineare. L'algoritmo di tipo tabu sear h di riferimento è l'algoritmo 2BP-TS proposto da Lodi, Martello e Vigo (1999) eseguito indi ando on

z ∗ il

valore della soluzione orrente del 2SPP, inizialmente al olata attraverso algoritmi ng basata sull'estrazione dalla formulazione del problema QAP, di un ampio problema di assegnamento lineare ( he può essere risolto all'ottimo), las iando il rimanente problema QAP di dimensioni più ridotte possibili. La soluzione del residuo QAP può poi essere risolto on una pro edura separata. Questo

metodo 2-step

produ e bounds migliori rispetto a quelli prodotti

all'appli azione diretta di algoritmi di bounding al QAP originale. Per ulteriori dettagli rimandiamo al survey re ente di Burkard, Dell'Ami o e Martello [6℄.

MODELLO GRAPH THEORY Nell'appro

io dei gra ogni dipartimento o ma

hinario (ignorando l'area e la forma del dipartimento all'inizio) è denito ome un nodo all'interno di una rete di un grafo. Questi dipendono dall'adia enza predenita e opportuna di ogni oppia di ma

hinari. In altre parole, si può dire he nell'appro

io dei gra, si assume he si onos a l'opportuna vi inanza della lo azione di ogni oppia di attrezzature.

Come a

ade per il QAP, an he

in questo aso problemi di aree diverse, perno di pi

ole dimensioni, non possono essere risolti all'ottimo. Sono state pubbli ate numerose relazioni su questo argomento, in ui sono stati analizzati diversi modelli e algoritmi.

MODELLO MIP An he metodi basati sul

Mixed Integer Programming

sono stati presi in

onsiderazione per risolvere il FLP. Sin dalla prima formulazione, he ha un

48

1. Problemi di pa king e utting nei layout obiettivo basato sulla distanza ed è usato nella rappresentazione di un layout he è una estensione del dis reto QAP, su

essivamente altri studi hanno sviluppato un aso spe iale di questo MIP e hanno proposto un algoritmo two-step per risolvere il FLP assumendo variabile l'area he può risolvere il

dynami fa ility layout

e rendere rettangolare l'area di tutti i dipartimenti.

Inoltre si è poi esteso il modello proposto per trattare aree disuguali e osti di ridisposizione. Tuttavia, il modello può essere risolto all'ottimo solo nel

aso di problemi di pi

ole dimensioni. Altri studi hanno onsiderato il problema di allo are i punti di input e output (I/O) di ogni dipartimento per un dato blo

o di layout he l'obiettivo di minimizzare la distanza totale di trasporto. È stato proposto un nuovo algoritmo bran h-and-bound he sembra migliorare l'e ienza an he per problemi di grandi dimensioni. An he se, la soluzione simultanea del problema del layout e dei punti di I/O non è an ora stato risolto i sono già alternative he propongono un appro

io di programmazione matemati a per il problema del layout generalizzato. Un MIP dettagliato, sebbene il suo appro

io riservi molte promesse, fornis e al momento soluzioni risolvibili solo per FLP di dimensione sei o minori. L'obiettivo è basato sulla distanza rettilinea di usso e di tempo tra il bari entro e i dipartimenti.

1.3.2 Metodologie di risoluzione Varie metodologie di risoluzione sono disponibili per risolvere il fa ility layout problem. Qui di seguito ne sono presentate al une

23

(una breve pano-

rami a), tra ui le metodologie ad appro

io esatto, euristi o e metaeuristi o,

on uno sguardo alle proposte future.

METODI ESATTI Sono stati usati metodi bran h-and-bound per trovare una soluzione ottima del FLP formulato ome assegnamento quadrati o poi hé il QAP oinvolge solo variabili binarie. In letteratura sono però riportate soluzioni ottime per problemi di dimensione no a 30. Per 23 sono

n > 30

diventa impossibile per il

state tralas iate altre metodologie di risoluzione per il FLP, tra ui menzioniamo gli appro

i a rete neurale e a fuzzy logi

1.3 Fa ility layout problem

49

omputer risolvere il problema e, di onseguenza, an he un omputer molto potente non può arontare un'istanza di grandi dimensioni.

ALGORITMI EURISTICI Gli algoritmi euristi i possono essere lassi ati ome algoritmi di tipo

ostruttivo poi hé una soluzione viene ostruita da uno s hizzo, ma an he di tipo migliorativo poi hé la soluzione iniziale viene migliorata. I metodi ostruttivi sono onsiderati gli appro

i più sempli i e tradizionali per risolvere il QAP da un punto di vista on ettuale e di implementazione, ma la qualità delle soluzioni prodotte non è di solito soddisfa ente.

I metodi basati sul

miglioramento partono da una soluzione ammissibile e provano a migliorarla attraverso inters ambi tra singoli assegnamenti. Questi due tipi di appro

i ( ostruttivi e migliorativi) possono fa ilmente essere ombinati tra loro. Ad esempio CRAFT è un algoritmo migliorativo molto usato he usa doppi inters ambi. Una lista degli euristi i più onos iuti usati per risolvere il FLP è quella riportata nella tabella a ne apitolo. Questi euristi i sono lassi ati

ome algoritmi basati sull'adia enza o sulla distanza. La dierenza tra questi due tipi di algoritmi si trova nella funzione obiettivo. La funzione obiettivo per gli algoritmi di adia enza è data ome:

max

XX i

dove

xij

vale 1 se il dipartimenti

i

(rij )xij

j

è adia ente al dipartimanto

j,

vi eversa

vale 0. Il prin ipio di base he sta dietro a questa funzione obiettivo è he il osto di movimentazione dei materiali è ridotto signi ativamente se i due dipartimenti hanno i onni adia enti. La funzione obiettivo degli algoritmi basati sulla distanza è inve e data ome:

n n n n 1 X X XX Cik Djl Xij Xkl min(TC) = 2 i=1,i6=k j=1,j6=l k=1 l=1 dove

Xij

è 1 se l'impianto

i

è assegnato alla posizione

j,

0 altrimenti

50

1. Problemi di pa king e utting nei layout Cik

è il osto per posizionare l'impianto

Djl

è la distanza tra la posizione

j

i

nella posizione

e la posizione

k

l

La losoa da sottolineare dietro a questa funzione obiettivo è he la distanza aumenta il osto totale dei viaggi. Visto he tutti gli indi i sono sommati da 1 a n, ogni assegnamento è ontato due volte; da qui la ne essità di moltipli are per

1 . 2

Cik

può essere sostituito on

Fik

( = usso tra gli impianti

i

e

k

) a se onda

dell'obiettivo.

ALGORITMI METAEURISTICI Al une alternative on appro

io metaeuristi o, ome ad esempio SA e

24

GA

, sono attualmente usati per approssimare la soluzione di FLP di grandi

dimensioni. La te ni a SA deriva dalla teoria della me

ani a statisti a ed è basata sull'analogia tra la fusione dei solidi e la risoluzione di problemi di ottimizzazione. Studi piuttosto re enti hanno studiato un algoritmo SA per il QAP. Una ra

olta molto re ente degli arti oli basati sugli algoritmi SA è riportata nella tabella di gura 1.19.

Figura 1.19: ra

olta di arti oli sugli algoritmi SA per la risoluzione dei FLP 24 Simulated

Annealing e Geneti Algorithms

1.3 Fa ility layout problem

51

Durante l'ultimo de ennio an he l'algoritmo geneti o ha guadagnato molta attenzione; esso utilizza una odi a binaria di individui ome stringhe di lunghezza ssa. GA er a iterativamente l'ottimo globale, senza esaurire lo spazio delle soluzioni, in un pro esso parallelo he inizia da un pi

olo insieme di soluzioni ammissibili (popolazione) e he genera nuove soluzioni in un qual he modo aleatorio. La performan e del GA dipende dal problema per hé la sistemazione dei parametri e lo s hema di rappresentazione dipendono dalla natura del problema.

Tavakkoli-Moghaddam e Shayan (1998)

hanno analizzato l'adeguatezza degli algoritmi geneti i per risolvere il FLP. La tabella di gura 1.20 fornis e re enti arti oli sui FLP basati sui GA. Gli algoritmi Tabu-Sear h (TS) sono altre pro edure iterative progettate per risolvere problemi di ottimizzazione. Helm e Hadley (2000) hanno appli ato algoritmi TS per la risoluzione del FLP. Il metodo è an ora molto studiato, ed è in ontinua evoluzione e miglioramento. Re entemente, al uni arti oli sono apparsi dove un algoritmo

ant olony

è stato usato per risolvere FLP di

grandi dimensioni. Talbi et al. (2001) hanno usato un algoritmo ant olony per risolvere il QAP.

Figura 1.20: ra

olta di arti oli sugli algoritmi GA per la risoluzione dei FLP

52

1. Problemi di pa king e utting nei layout OBIETTIVI FUTURI E NUOVI SCENARI D'AZIONE Dall'analisi delle moltepli i alternative riportate in questo paragrafo, si evin e he la ri er a sul FLP non è onvergente, ma in qual he modo divergente. Al momenti, l'appro

io AI

25

può essere usato per sviluppare euristi i

he risolvano FLP di grandi dimensioni; inoltre è ne essaria più ri er a nelle funzioni multi-obiettivo per raggiungere riteri di layout più rilevanti. Ogni due anni il

Material Handling Institute of Ameri a, insieme ad altre industri

sponsorizzatri i e alle agenzie di governo, organizza un onsorzio sulla ri er a riguardo le novità sui sistemi di trasporto materiali dove i ri er atori possono presentare le proprie ri er he. È stato s operto he 'è una man anza di appli azione della

on urrent engineering

nel FLP in a

ordo on la s elta del

sistema di movimentazione materiali he mostra ome la progettazione del layout dei ma

hinari sia indipendente dalla s elta del sistema di movimentazione. È stato al olato he lo stesso layout non è appropriato per tutti i periodi, poi hé la domanda non rimane la stessa. Da qui, la ri er a dovrebbe indirizzarsi verso un layout delle attrezzature dinami o e non stati o. Per la risoluzione del FLP sta emergendo soprattutto la ri er a nell'appli azione di meta-euristi i ome gli algoritmi SA, GA e TS. Tuttavia, il risultato nale dipende an he dalla soluzione iniziale presa (popolazione). Quindi, la ri er a deve an he sviluppare validi euristi i he generino buone soluzioni iniziali.

25 Arti ial

Intelligen e

1.3 Fa ility layout problem

Authors, sour e Ja obs (1996) Dagli and Poshyanonda (1996, 2004) Liu and Teng (1999) Hopper and Turton (2000) Hopper and Turton (2000) Hopper and Turton (2000) Mumford, Valenzuela et al. (2003) Kro¨ger (1993, 1995) S hne ker (1996) Ratanapan and Dagli (1997, 1998) Iori et al. (2002) and Mona i (2001)

53

SPP subtype Approa hes

Methaeuristi s

RF

1

GA

RF

1

GA

RF

1

GA

RF

1

GA

RF

1

SA

RF

1

NE⋆

RG

1

GA

RG

2

Parallel GA

RG

2

Parallel GA

RF

3

GA

OF

Hybrid

Hybrid GA+TS

Tabella 1.1: Algoritmi metaeuristi i per il 2SPP on pezzi rettangolari; indi a NaiveEvolution, ovvero un GA on mutazione ma senza rossover

⋆

54

1. Problemi di pa king e utting nei layout

Capitolo 2 Ottimizzazione dei layout eristi i Prendendo spunto dalle numerose fonti disponibili sul web o dai do umenti a riguardo, si può riassumere brevemente lo s opo primario di una buona progettazione del layout, sia dal punto di vista aziendale he organizzativo (per eventi, ere, manifestazioni, e

.).

L'organizzazione vera e propria dello spazio di vendita (layout) prevede il disegno dei per orsi e della ir olazione, in ui la sequenza delle aggregazioni mer eologi he deve risultare naturale e di fa ile lettura per la propria lientela-obiettivo. Generalmente si rea un per orso prin ipale, he stimoli il liente a seguirlo, e spazi di viabilità se ondaria, all'interno delle diverse are del punto vendita. Nel fare iò i si deve assi urare he i per orsi siano su ientemente ampi da garantire il passaggio agevole della lientela e dei ommessi, eliminandone i punti morti. La presenza di un'illuminazione studiata e di una segnaleti a e a e ma non invasiva deve, inoltre, guidare l'attenzione dei lienti verso i punti di maggiore attrattiva del lo ale. In parti olare, nel orso del presente apitolo, verrà fo alizzata l'attenzione sull'analisi di asi di studio noti, quali le ere di Fortaleza in Brasile e di Romont in Svizzera. Tali informazioni e dati sono infatti molto utili ome modello per lo sviluppo e l'appli azione degli algoritmi visti nel primo

apitolo all'ambito eristi o. 55

56

2. Ottimizzazione dei layout eristi i

2.1 Spe i he e ontesti per il progetto L'obiettivo prin ipale del progetto di un layout eristi o onsiste nel posizionare il massimo numero di stand nell'area adibita all'esposizione, soddisfa endo un erto numero di requisiti operazionali ( super ie numero

n

S

onstraints ).

Data una

adibita all'esposizione, di forma irregolare e non onvessa, e un

di stand uguali e rettangolari, si vuole massimizzare il numero di

stand ontenuti in

S

er ando allo stesso tempo di ottenere un layout he

possa rispondere alle esigenze di un ontesto eristi o. ``fattibile se soddisfa un erto numero di

onstraints

Un layout si di e

di base (tipi i di un

ontesto eristi o) più altri requisiti spe i i forniti dall'organizzazione nel

aso spe i o. Si possono riassumere le ondizioni di ``fattibilità del layout nei seguenti punti omuni ad ogni organizzazione eristi a:

•

gli stands non possono sovrapporsi

•

gli stands devono essere ompletamente ontenuti nella super ie

•

i visitatori (ma an he gli organizzatori) devono poter fa ilmente a

e-

S

dere agli stands Oltre a tali requisiti generi i, ogni organizzazione ha an he altre ne essità proprie, per le quali è opportuno onsiderare altri onstraints da inserire nel progetto. Un problema simile già ampiamente studiato è quello on ernente l'ottimizzazione dei layout industriali; si usa il termine ``simile e non il termine ``uguale per hé nell'ambito delle ere non bisogna tenere onto del usso: tra uno stand e uno altro non vi è nessun usso di materiale ome inve e a

ade tra un ma

hinario ed un altro in un'impresa manifatturiera. Il problema del layout eristi i sembra piu vi ino a quello del parti olare il

two dimensional pa king problem

1

.

pa king,

in

Tuttavia si tratta di un

task di grande interesse nel ampo dell'ottimizzazione ombinatoria, essendo un ampo di appli azione piuttosto nuovo; ome ulteriore ompli azione, rispetto ai asi generali di pa king NP-hard, per un ontesto eristi o nas e 1 appunto

per hé si ha a he fare on un problema di pa king, allora si inseris e tale prolema nell'insieme degli NP-hard ( onsiderando il aso più generale in ui ogni stand può essere ruotato in ogni direzione possibile)

2.1 Spe i he e ontesti per il progetto

57

il problema legato alla irregolarità della super ie espositiva. Un esempio di super ie irregolare è quello di gura 2.1:

Figura 2.1: tipi o esempio di super ie irregolare su ui progettare il layout A

anto a questo importante e determinante

onstraint

le spe i he, piutto-

sto omuni nella maggioranza dei asi, impongono an he di onsiderare gli stands orientati tutti nello stesso modo e allineati tutti nella stessa direzione lungo stris ie verti ali; ovviamente sarà opportuno riservare uno spazio minimo tra tali stris ie per permettere un a

esso fa ile alla lientela. Nel progettare un layout siatto è bene tenere in onsiderazione tre obiettivi fondamentali, asso iati ad altrettante funzioni obiettivo:

•

l'utilizzo ottimo dello spazio a disposizione

•

lo s opo di attirare la maggiore lientela possibile

•

la onvenienza dal lato liente

Ovviamente, ome già detto in pre edenza, si tratta di un tipi o problema di 2BPP e di FLP, analizzati nel apitolo pre edente. In parti olare è opportuno onsiderare un impa

amento di questo tipo è hiamato in letteratura

two-dimensional two-staged pa king ; si supponga he si voglia tagliare l'area per l'esposizione per produrre una serie di aree più pi

ole rappresentanti gli stand, iò può essere fatto grazie a una prima fase di tagli a ghigliottina paralleli al lato rappresentante l'altezza e a una se onda fase in ui si eseguono tagli, sempre a ghigliottina, paralleli al lato rappresentante la larghezza. Nella se onda fase è ne essario eettuare un taglio per ogni stris ia ottenuta

58

2. Ottimizzazione dei layout eristi i nella prima fase.

Riassumendo i prin ipali puti salienti del problema, possiamo des rivere ome operare seguendo una serie di a

orgimenti e metodi risolutivi he indi hiamo

ome

Fair Layout Optimization Problem

(FLOP). Si onsiderino le seguenti

assunzioni:

assunzione 1

2

: l'area su ui progettare è una super ie

nuta in un rettangolo di altezza

H

e larghezza

W

irregolare, onte-

he la in apsula in

modo pre iso (vedere le linee tratteggiate di gura 2.1);

assunzione 2 larghezza

assunzione 3

: gli stands sono rettangoli tutti identi i e hanno altezza

h

e

w :

non sono ammesse rotazioni degli stands (tutti devono

essere orientati allo stesso modo)

assunzione 4 : l'allo azione deve essere fatta ortogonalmente su stris ie (strips ) verti ali parallele ai lati verti ali del rettangolo, garantendo l'a

esso da uno dei lati liberi per ias uno stand A questo proposito si pro ederà se ondo una dupli e variante del FLOP

er ando di impa

are il massimo numero di stand nella super ie a disposizione in modo da non violare tutte le onsiderazioni fatte in pre edenza e soddisfa endo le assunzioni appena fatte.

•

FLOP 1: viene ri hiesto he ogni stand (ogni strip) possa essere a

eduto da ambo i lati (stris ie singole)

•

FLOP 2: è possibile disporre gli stand in stris ie a

oppiate senza spazi tra di esse, in modo he l'a

esso agli stand avvenga dal solo lato libero

In gura 2.2 sono illustrate le due varianti FLOP1 e FLOP2 rispettivamente. Senza perdere di generalità, assumeremo he la super ie sia a

essibile da tutte le parti. Se si onsidera l'area espositiva ome una matri e binaria

on

H

righe e

W

M

olonne, orrispondente al rettangolo sopra itato, numeran-

do righe e olonne dall'angolo in basso a sinistra della matri e (si onsiderino 2 da

qui deriva il fatto he si progetta su due dimensioni

2.1 Spe i he e ontesti per il progetto

59

Figura 2.2: varianti del progetto: a) = FLOP1 (a sinistra) e b) = FLOP2 (a destra) le due dimensioni della super ie ome su di un piano artesiano), si denis e la matri e ome:

Mi,j =

(

1 0

se lo spazio

δ×δ

alle oordinate (i,j) viene allo ato per lo stand

altrimenti

dove, per sempli ità si onsiderano tutte le variabili (altezze, larghezze, distanze, e

.) ome valori interi, espressi se ondo una unità minima di lunghezza he indi hiamo on

δ,

mentre

i = 1, ..., H

e

j = 1, ..., W .

Pertanto

Figura 2.3: matri e M asso iata all'area di esposizione eristi a di gura 2.1 si seleziona una olonna (

strip )

j

per il layout nel aso in ui una stris ia di stands

sia posizionata sulla olonna stessa ol lato sinistro: ad esempio in

gura 2.1 e 2.2 la prima olonna viene selezionata ome prima strip (dove

w = 3, h = 2).

Supponiamo he ias una olonna

j

e ias un intervallo

60

2. Ottimizzazione dei layout eristi i massimo di righe

[ia , ib ]

di

M

formino una sottomatri e avente tutti

1

ome

suoi elementi: tali elementi della sottomatrie ottenuta saranno rettangoli di

w e altezza (ib − ia + 1) ol proprio verti e in basso a sinistra alla

oordinata (ia , j). Di onsegienza, il massimo numero di stands he possono ib − ia ⌋. In gura 2.3 ad essere piazzati all'interno di tale sottomatri e è ⌊ h esempio, si ontano per j = W − 3, due intervalli massimi di righe di larlarghezza

ghezza 3: uno alto 2 e l'altro alto 5; la stris ia orrispondente può quindi disporre di tre stands in totale.

j ≤ W − w + 1, il massimo numero di stands vj he possono posizionati ol loro lato sinistro nella olonna j è ottenuto in maniera

Per ogni olonna essere

iterativa, determinando le su

essive olonne he soddisno le ondizioni spe i ate. Una s hietta implementazione di questo metodo ri hiederebbe, per

O(H) O(W Hw).

ogni olonna, un numero di iterazioni pari a pari a

O(w);

quindi in totale un tempo

Una pro edura più velo e he ri hiede un tempo

di omplessità temporale

O(W H)

pari a quello im-

piegato per `` ari are la matri e M sarà illustrata di seguito; tale pro edura

al ola le stesse informazioni

vi (j = 1, ..., W − w + 1).

2.1 Spe i he e ontesti per il progetto

61

i he sia Mi,j = 1, un puntatore p(i) all'ultima olonna ˆ j in modo he sia Mi,j = Mi,j+1 = ... = Mi,ˆj = 1. Se inve e Mi,j = 0 per la olonna orrente j , allora p(i) avrà un qualsivoglia valore minore di j ; in questo modo tutti gli intervalli massimi di riga possono essere determinati esaminando ogni elemento di M un numero sso e ostante di volte. La variabile ontatore k memorizza, per la olonna orrente j e Si analizzi l'algoritmo: deniamo, per ogni riga

per l'attuale intervallo di riga, il numero di righe he soddisfano le spe i he e he quindi deniamo ``idonee. Il nostro problema di ottimizzazione ombinatoria si fo alizza per iò nella determinazione delle olonne delle

strips

j

he possono essere inserite nell'impa

amento

di stands.

2.1.1 Modelli matemati i Nel presente paragrafo si analizzeranno i due modelli matemati i orrispondenti alle due varianti di pre edenza.

fair layout optimization problem

introdotte in

La prima parte, dedi ata al FLOP1, non prevede al una ri-

hiesta riguardante la distanza tra due

strips

diverse di stands; inoltre si

fa riferimento alle assunzioni 1-4 viste pre edentemente. Consideriamo una variabile binaria

xj =

(

1 0

se una strip singola di stands ha il proprio lato sinistro sulla olonna j altrimenti (2.1)

∀j = 1, ..., W − w + 1. Il primo problema

FLOP1 può quindi essere

WX −w+1

vj xj

(2.2)

xj ≤ 1 , (k = w + a, ..., W − w + 1)

(2.3)

(FLOP1)

max

modellato ome segue:

j=1

subje t to

k X

j=k−a−w+1

xj ∈ {0, 1} dove

a

,

(j = 1, ..., W − w + 1)

(2.4)

3

rappresenta la larghezza minima del passaggio pedonale tra strips .

Dalla espressione (2.3) si nota he i vin oli impongono he gli stands non si 3 he

in inglese si indi a on aisle=navata ome si può vedere in gura 2.5

62

2. Ottimizzazione dei layout eristi i sovrappongano tra loro e he i sia spazio su iente per le lonna

aisles :

se una o-

k viene selezionata allora le olonne (k−a−w+1, ..., k−1) non possono

essere selezionate a loro volta, ome è possibile onstatare dalla gura 2.4. È

= 1, ..., w + a − 1) (k = w + a).

inoltre possibile notare he le onstraints (2.3) per (k sono imposte, bensì derivano dal primo vin olo

non

Figura 2.4: onstraints per il FLOP1 (sinistra) e per il FLOP2 (destra) Il se ondo problema FLOP2 può essere modellato analogamente all'algoritmo pre edente, introdu endo un se ondo tipo di variabile binaria per ogni

olonna

ξj =

(

j: 1 0

se una strip doppia di stands ha il proprio lato sinistro sulla olonna j altrimenti (2.5)

∀j = 1, ..., W − 2w + 1. Osserviamo he il massimo numero di stands idonei ad essere ompresi nella

double-strip

è

vj + vj+w .

Ne deriva quindi il modello

FLOP2 seguente:

(FLOP2)

max

W −2w+1 X

(vj + vj+w )ξj

(2.6)

j=1

subje t to

k X

j=k−a−w+1

min(W −2w+1,k)

xj +

X

ξj ≤ 1 , (k = w + a, ..., W −w + 1)

j=max(1,k−a−2w+1) (2.7)

2.1 Spe i he e ontesti per il progetto xj ∈ {0, 1} ξj ∈ {0, 1}

, ,

63

(j = 1, ..., W − w + 1)

(2.8)

(j = 1, ..., W − 2w + 1)

(2.9)

Analogamente al aso del FLOP1, qui i vin oli (2.7) impongono he le stris ie (singole e doppie) di stands non si sovrappongano e he i sia, ome al solito,

k viene selezionata (sia se singola sia se doppia), allora le olonne k−a−w+1, ..., k−1 spazio su iente per onsentire il usso dei lienti: se una olonna

non possono esserlo altrettanto (nel aso di una lonne una

k − a − 2w + 1, ..., k − 1

double-strip ).

single-strip ),

mentre le o-

non possono esserlo altrettanto (nel aso di

max e min nella se onda soml'indi e j poi hè è fuori dal range.

Si può notare he gli indi i

matoria della equazione (2.7) es ludono

Nella parte destra di gura 2.4 si può osservare l'insieme di onstraint utilizzate per il FLOP2, mentre nelle gure 2.5 e 2.6 è possibile vedere un esempio di layout he tiene onto di entrambe le varianti FLOP1 e FLOP2.

Figura 2.5: esempio di layout he tiene onto delle distanze tra le aisles per i pedoni e tra strips (aδ ). Gli spazi olorati indi ano zone in ui non risulta possibile posizionare stand.

Inne, analizzando le due alternative presentate, si dedu e una fondamentale proprietà: le matri i dei vin oli di tutte e due le varianti sono totalmente

unimodulari ; dove per ``matri e unimodulare'' si intende una matri e seguenti requisiti:

A

he soddis i

64

2. Ottimizzazione dei layout eristi i

Figura 2.6: dierenze tra FLOP1 e FLOP2: nel primo aso ogni stand ha due a

essi e vi sono strip singole; nel se ondo aso ogni dtand ha un solo lato di a

esso libero ed è disposto su stris ie doppie. • aij ∈ {−1, 0, 1} •

ias una olonna non deve avere più di due elementi non nulli

•

esiste una partizione (A1 , A2 ) delle righe tale he per ogni olonna on due elementi non nulli, questi appartengono uno a

A1 ,

e l'altro ad

A2

se e solo se sono on ordi in segno Se hiamiamo statare he

A

A

la matri e asso iata al vin olo (2.3) si può fa ilmente on-

è proprio

unimodulare :

i oe ienti di ogni riga

i

(sempre

riferendosi ai onstraint (2.3)) sono tutti zero tranne un insieme di valori unitari onse utivi he partono proprio da

i.

w+a

Questo insieme di ele-

wδ , ossia di larghezza w e unità di ′ misura δ ≈ 20cm (in generale). Ora sia ai il vettore asso iato alla riga i ′ ′ ′ di A, per i = 1, ..., W − w + 1, e si modi hi A ponga ai = ai − ai+1 , per i = 1, ..., W −w +1. In questo modo, partendo da A si ottiene la matri e A˜ di Figura 2.7. E' fa ile notare he la matri e A soddisfa le ondizioni su ienti

menti unitari è un gruppo di elementi

per essere una matri e totalmente unimodulare.

In parti olare la olonna

avente più di due elementi non nulli può essere divisa in

A1 = A

e

A2 = ⊘.

Da iò segue he entrambi i problemi FLOP1 e FLOP2 possono essere risolti in un 4 si

polynomial time 4

sostituendo i vin oli (2.5) ( orrispondenti ai vi oli

fa riferimento a un problema risolvibile in tempi omputazionali, mediante l'asso iazione della omplessità del problema a una funzione polinomiale

2.2 Studio e analisi di asi reali

Figura 2.7: a sinistra, la matri e A asso iata ai vin oli imposti dalla equazione (2.3); a destra, la matri e A˜ ottenuta mediante al une operazioni lineari sulle righe di A.

(2.8)) e i vin oli (2.9) on i loro rispettivi rilassamenti lineari:

0 ≤ xj ≤ 1 , (j = 1, ..., W − w + 1) 0 ≤ ξj ≤ 1 , (j = 1, ..., W − 2w + 1) e risolvendo il risultante problema di programmazione lineare dato dalle (2.2),(2.3), (rispettivamente (2.8) e (2.9)) insieme alle ultime due relazioni appena ri avate.

2.2 Studio e analisi di asi reali Nei prossimi due sottoparagra verranno presentate due metodologie di appli azione degli algoritmi per il layout eristi o. In parti olare verranno analizzati i ontesti della era dell'artigianato di Fortaleza (Brasile) sul lungomare di Beira Mar, e la era regionale di Romont (Svizzera), he ospita

ir a 100 espositori e 50 mila visitatori l'anno. Tali ontesti rappresentano un'analisi ompleta sotto i vari punti di vista, poi hé oprono nel omplesso tutte le possibilità e le eventualità he si possono presentare in ambito eristi o. Se nel primo aso, infatti, si tratta di una era permanente, on sede su una super ie irregolare e suggestiva ome la spiaggia del lungomare a

anto a hotel, ristoranti e luoghi di turismo molto aollati, nel se ondo

aso si ha a he fare on una era regionale he ha luogo ogni due anni nella lo alità di Romont, nel tipi o paesaggio montuoso della Svizzera. Due tipologie di studio piuttosto diverse, ma he oprono gran parte delle

65

66

2. Ottimizzazione dei layout eristi i

aratteristi he tipi he del ontesto, in modo da poter far fronte ad un largo insieme di spe i he, requisiti e vin oli, al ne di reare un progetto ompleto e adeguato ad ogni evenienza.

2.2.1 Caso 1: Fortaleza hand raft fair Ogni giorno ir a sei ento artigiani si re ano all'altezza della spiaggia di Meireles e assemblano e smontano i loro stand per dare vita a una famosa era di artigianato he da anni è presente sul lungomare di Fortaleza (Brasile). L'area he ir onda la era è una delle zone più attive della ittà ed è piena di noti hotel e ristoranti. E' stata l'importanza di questa era, data dal grande numero di persone he vi lavorano e dall'enorme auenza di visitatori, e la omplessità dell'ambiente entro ui essa è ollo ata, he hanno spinto l'Università di Ceará a trasformare la disposizione degli stand dei osiddetti

Juarez

in un vero e proprio problema di ottimizzazione. Questo grande am-

montare di stand ha infatti bisogno di una disposizione meno aoti a e più razionale he renda possibile l'inserimento di più artigiani possibile. Lo s opo della ri er a onsiste quindi nel massimizzare il numero di stand

he possono essere ontenuti nella super ie adibita alla era, er ando di ottenere un layout a

ettabile, ovvero un layout he onsideri an he tutti gli spazi ne essari per il passaggio delle persone e per il montaggio/smontaggio degli stand. Tutto iò tenendo ben presente he la super ie disponibile per l'esposizione è di forma irregolare e non onvessa (all'interno e attorno alla super ie sono infatti presenti numerosi osta oli: palme, s ulture, pan hine..) e he gli stand sono tutti uguali e rettangolari. Proprio queste ultime

onsiderazioni, rendono il problema generalizzabile ad ogni altro ontesto eristi o e quindi parti olarmente interessante. In gura 2.8 è disponibile una piantina he ritrae la super ie di esposizione della era di Fortaleza. L'algoritmo orrispondente al problema di programmazione lineare della era è stato implementato utilizzando un software free dotato di interfa

ia gra a sempli e e intuitiva he potesse permettere di fa ilitare le operazioni

2.2 Studio e analisi di asi reali

67

Figura 2.8: vista dall'alto della zona dedi ata all'esposizione eristi a (indi ata in grigio) in lo alità Beira Mar, a Fortaleza 5

di disegno del layout . Le dimensioni dell'area he ospita il layout sono ir a di 200 metri di larghezza ( he indi hiamo, oerentemente on quanto visto nelle sezioni pre edenti

on

W)

e 50 metri di altezza ( he indi hiamo on quindi on

H ).

L'anali-

si, risalente al 2006, onta 617 stands, posizionati in 26 stris ie doppie, on arrangiamento piuttosto simile a quello pensato per il FLOP2, mentre per quanto riguarda l'altezza e la larghezza degli stand, vale per tutti

w = 2 metri.

h=2

e

E' importante sottolineare he he l'area è di tipo non onvesso,

ossia 'è la presenza di alberi, pi

oli negozietti, lampioni, monumenti, per

ui al une aree non sono disponibili per l'installazione di stands. Nel aso in questione, denendo

H = 1084;

δ = 5cm

si ottengono

w = h = 40, W = 4090

e

il valore indi ativo fornito per determinare la larghezza del pas-

saggio pedonale (

aisle ) è di 3.5m,

ovvero

a = 70.

I passi eettuati per testare l'e ienza degli algoritmi FLOP1 e FLOP2 onsistono in operazioni piuttosto ompli ate e laboriose, soprattutto nel passare dalla mappatura reale a quella virtuale (per lo s opo sono stati utilizzati

6

strumenti di CAD) e per onvertire il tutto in formato SHP

ontenente le

``georeferenze e le oordinate della super ie espositiva. A sua volta il le SHP è stato onvertito in una matri e bineria 5 tutte

M

di dimensione

1084 × 4090

le simulazioni e i test sono stati eseguiti su ma

hine on pro essore Pentium 4 a 1.8GHz dotate di 2GB di RAM. 6 shapele, formato vettoriale per sistemi informativi geogra i he tradu e le informazioni gra he in dati geometri i ri

hi di attributi di orredo alle forme poligonali he determinano le elaborazioni

68

2. Ottimizzazione dei layout eristi i ( omune ai due modelli), mediante un programma hiamato Delphi Obje t

7

Pas al ; questa onversione ha ri hiesto un tempo omputazionale molto lungo, ir a 1000 se ondi di elaborazione da parte della CPU.

Figura 2.9: output relativo alla soluzione mediante algoritmo FLOP1.

Figura 2.10: output relativo alla soluzione mediante algoritmo FLOP2. Il modello FLOP1, la ui soluzione è rappresentata il gura 2.9, è stato elaborato e risolto in 24 se ondi e la soluzione ottimizzata ha fornito ome output un totale di 505 stands disposti su 36 le singole (le

strips )

on meno del

20% di de remento rispetto al aso di partenza (a stris ie doppie). Il modello FLOP2, inve e, è stato risolto dal software in 62 se ondi e la soluzione, in gura 2.10, ha al olato 742 stands arrangiati in 26

double strips, in remen-

tando del 20% la soluzione di partenza. Stando ad esigenze ulteriormente stringenti, al uni organizzatori hanno ri hiesto an he di sfruttare la zona in alto a destra (di forma grosso modo triangolare) e si sono ottenute altre soluzioni, impiegando 759 stands sempre 7 della

software house ``Borland''

2.2 Studio e analisi di asi reali

69

su 26 stris ie doppie (quindi sempre riferendosi al FLOP2). Nessuna delle soluzioni proposte dal FLOP2 ha avuto modo di ombinarsi on quelle proposte dal FLOP1 e ioé non vi è modo di ombinare stris ie singole e doppie, probabimente a ausa del fatto he le

aisles pedonali sono relativamente piut-

tosto larghe, e non onviene us ire dalle alternative trovate. Una ulteriore possibilità per ottimizzare an ora di più le prestazioni ompu-

di spazio, ma di tempo. Ad esempio per

δ , he non ottimizzano le questioni δ = 10cm l'algoritmo ha bisogno di

M,

di 4 se ondi per risolvere il FLOP1

tazionali onsiste nel ambiare i valori di

246 se ondi per ostruire la matri e

e di 10 se ondi per quanto riguarda il FLOP2.

Inoltre, nel primo aso si

ontano 503 stands inve e he 505, mentre per il FLOP2 si hanno gli stessi 742 stands he in pre edenza. Per

δ = 20cm si hanno 64 se ondi per ostruire

la matri e, e 2 se ondi per FLOP1 e 1 se ondo per FLOP2 on un ulteriore de remento degli stands, rispettivamente a 499 e 737. Per valori sempre più pi

oli di

δ,

no a

δ = 5cm,

si sono ottenuti tempi di al olo empre più

elevati, senza però al un bene io in ottimizzazione.

Il ampo he interessa i layout eristi i ha assunto notevole importanza soprattutto negli ultimi anni, ed è diventato di fondamentale importanza in materie ome la Ri er a Operativa e in appli azioni matemati he e informati he. Tuttavia è un problema in piena evoluzione e in ontinua fase di studio per l'ottimizzazione ombinatoria, per iò ome tale ri hiede ontinui adattamenti e revisioni in modo da poter soddisfare un numero sempre più ampio di requisiti e oprire in larga s ala tutte le eventualità.

A titolo di

esempio si onsideri propio il aso di Fortaleza, in ui gli organizzatori hanno proposto nuove alternative e introdotto nuove

onstraints

al problema:

nel aso appena analizzato, una delle spe i he onsisteva nell'arrangiare le strips in modo perpendi olare alla spiaggia (la base della piantina); ma è possibile `` omporre gli stands in altro modo, produ endo soluzioni migliori o adatte alle varie esigenze he ambiano di volta in volta. Considerando un appro

io tipi o dei layout generi i, non sarebbe insensato disporre gli stands a gruppi di 4, ome rappresentato in gura 2.11.

70

2. Ottimizzazione dei layout eristi i

Figura 2.11: bozza alternativa alle varianti previste per la soluzione; si dispongono gli stands a gruppetti di quattro.

2.2.2 Caso 2: Regional fair in Romont La era regionale di Romont ha luogo ogni due anni in un paese di 4 mila abitanti ir a, a metà strada tra Ginevra e Berna, nella Svizzera fran ofona.

La zona adibita alle esposizioni è di ir a 5200 mq (le dimensioni

pre ise sono di

W = 100

metri di lunghezza e

H = 52

metri di larghezza

del rettangolo) e al suo interno si presentano mer i e servizi di almeno un

entinaio di espositori.

Nel 1998 si sono registrati ir a 50 mila visitatori

durante gli 8 giorni dedi ati alla manifestazione. Sotto quest'otti a gli organizzatori hanno ne essitato di provvedimenti per ottimizzare il layout e far fronte ad eventuali aumenti dei visitatori.

Di solito, l'appro

io utilizzato

dall'organizzazione onsiste nel partire da una lista degli espositori e delle loro ri hieste in termini di spazi, per poi adeguare il layout soddisfa endo un

liente alla volta; un appro

io alternativo, inve e, prevede di partire da un layout predenito e di assegnare a ias un espositore una super ie he ne soddis le esigenze. Si può suddividere il pro esso di sviluppo delle soluzioni in due bran hie: allo are in primis lo spazio per gli stands, in maniera tale da non sovrapporre gli spazi espositivi; in se ondo luogo allo are gli spazi per il usso dei visitatori ( iò he di solito indi hiamo on

aisles ).

Vediamo in dettaglio questi

due punti.

•

Poi hé una delle aratteristi he portanti della era di Romont è he non si mantiene tale e quale alle edizioni pre edenti, i progettisti del layout devono ogni volta adattarsi alle nuove disposizioni ed esigenze

2.2 Studio e analisi di asi reali

71

Figura 2.12: disposizione degli stands nell'edizione del 1998 della era. e quindi riproporre ogni anno soluzioni diverse: il tutto si tradu e in una ra

olta di requisiti he omprende la prima parte del progetto. In parti olare si ra

olgono informazioni su:



8

la forma e le dimensioni degli stands (se rettangolari o ad angolo ,

on le relative misure)

 •

i lati di a

esso agli stands

Il usso di persone he può transitare all'interno degli spazi adibiti può essere elevato ed è quindi ne essaria un'e a e auenza nel per orso riservato alla lientela.

La pe uliarità he si ris ontra nella era di

Romont sta nel fatto he il liente deve seguire un per orso guidato e

9

obbligato tra i vari stand, in modo da poterli visitare tutti . Nel aso in esame lo spazio dei orridoi va da un minimo di 2 metri ad un massimo di 3 In aggiunta a queste aratteristi he vanno aggiunti altri vin oli he sono rappresentati da osta oli all'interno dello spazio, ossia presenza di bagni e toilettes, di muri, olonne e barriere ar hitettoni he, di us ite d'emergenza, e

., seppur omunque il ari o di lavoro da arontare si basa su tre fattori determinanti: 8 he

possono essere piazzati in un angolo dell'area espositiva strategia è tipi a an he in altri ambiti, quali ad esempio nei dis ount o in supermer ati (vedi IKEA), ma è un aso piuttosto singolare quando si tratta di ere regionali 9 questa

72

2. Ottimizzazione dei layout eristi i utilizzo degli spazi

: è l'aspetto più importante, dal quale derivano gli altri

due. Si tratta dell'ottimizzazione di tutti gli spazi possibili, nel senso

he ogni spazio inutilizzato (

dead spa e ),

va omunque ``reso utile'' e

adibito agli stands

valore attrattivo

: rappresenta la `` apa ità della era di attirare il mag-

gior numero possibile di lienti e visitatori. Non dipende solamente da fattori quali marketing o promozioni, ma an he, e soprattutto, da un progetto a

orto. Cias uno stand deve avere una propria lo azione il più attraente possibile: il aso ideale sarebbe di disporli in modo he

open side

l'

di ias uno di essi si aa

i sul per orso dei visitatori

agevolazioni ai visitatori

: naturalmente una qualsivoglia manifestazio-

ne, mostra o esposizione eristi a deve essere omoda da visitare e pia evole da vedere. Deve prevedere a

orgimenti mirati alla omodità del liente in modo da invogliarne e stimolarne la uriosità; bisogna quindi tenere onto dei per orsi (magari intervallando on aree di sosta e minimizzando i ambiamenti di direzione, per non aati are la visita), degli spazi e del ontesto in ui i si trova

È ovvio he risulta impossibile soddisfare appieno tutte e tre le spe i he, per iò o

ore er are un trade-o tra di esse in modo da adeguare il progetto alle esigenze di organizzatori, espositori e visitatori. Generalmente tale ompromesso dipende dall'abilità e dall'esperienza del progettista.

Figura 2.13: des rizione degli items utilizzati nel progetto e legenda. adja en y model, he

Il modello ui i si è attenuti nel progettare il layout è l'

2.2 Studio e analisi di asi reali

73

permette una rappresentazione basata sull'adia enza del per orso dei visitatori ai lati aperti degli stand espositivi; viene usata una dis retizzazione degli elementi oinvolti nel pro esso di layout e questo signi a he la super ie e gli spazi ri hiesti sono espressi ome valori interi e multipli dell'unità base dell'area, mentre la super ie espositiva è asso iata ad un rettangolo suddiviso in al une unità di misura di base, ome si può vedere dalle gure seguenti. In parti olare la lunghezza del rettangolo è di

L unità, mentre

la altezza è

B

unità. Ogni punto all'interno del rettangolo può essere identi ato mediante le oordinate sugli assi artesiani ome illustrato in gura 2.14.

Figura 2.14: fairground relativo allo spazio espositivo, asso iato ad un rettangolo su un piano artesiano.

Per quanto riguarda gli stands, essi sono rappresentati ome aree rettangolari o angolari (ad angolo) e le diverse tipologie di stand sono illustrate in gura 2.15; tali spazi espositivi possono essere posizionati verti almente o

Figura 2.15: tipologie di stands/moduli impiegati nella era. orizzontalmente, a se onda delle esigenze, avendo per iò no a 4 possibili

10

orientamenti dello stand

. In gura 2.16 è possibile vedere ome viene posi-

zionato uno stand ad angolo all'interno della super ie, assieme ad una lista di valori he esprimono dimensioni e oordinate per il posizionamento. Si ha inve e, per quanto on erne il per orso riservato ai visitatori, he il path 10 supponiamo

he le rotazioni possano avvenire ogni 90◦

74

2. Ottimizzazione dei layout eristi i

Figura 2.16: posizionamento di uno stand angolare i sul fairground. non presenta al un tratto urvilineo ed è quindi omposto da tratti orizzontali e verti ali (solo rettilinei) he devono essere paralleli agli assi artesiani del rettangolo. Come si può vedere dalla gura 2.17, il quadrato nero indi a un ambio di direzione del per orso, uno snodo he si può fa ilmente referenziare nell'algoritmo, per hé orrisponde esattamente ad una unità base di misura.

Figura 2.17: per orso per i visitatori e relative oordinate. L'

adja en y model

impli a la formulazione di tre riteri quantitativi per mi-

surare la qualità di un layout progettato bene; tali riteri derivano dai tre fattori visti in pre edenza:

utilizzo degli spazi

: deniamo il oe iente

r

he esprime il rapporto tra

la super ie rettangolare (il fairground) e la somma delle aree o

upate

2.2 Studio e analisi di asi reali

75

dai padiglioni,

r= dove

N

PN

i=1 ((ki

× li ) − [(ki − wki ) × (li − wli )]) , L×B

rappresenta il numero di stands, mentre

LeB

sono rispettiva-

mente la lunghezza e la larghezza del fairground. Notiamo he per padiglioni di forma rettangolare si ha

ki = wki

per

ui il se ondo addendo della sottrazione si annulla e quindi per questo

aso la super ie viene al olata solo tramite

valore attrattivo

ki × li

: tale requisito si misura grazie al al olo dell'adia enza

bi , dove il numeratore rappresenta la lunghezza del padiglione qi

ai = i − esimo

riferito al per orso della lientela e il denominatore indi a la

lunghezza dell'open spa e dello stand

i-esimo.

Due esempi autoespli-

ativi del al olo delle adia enze sono illustrati in gura 2.18. Indipendentemente dal fatto he la forma dell'item sia rettangolare o angolare, l'adia enza viene al olata onsiderando valori tra

0 e 1, he indi ano la

per entuale on ui la lunghezza dell'open side omba ia ol per orso. Se l'indi e di adia enza

ai

è alto, il valore attrattivo diventa importan-

te, questo per hé si alzano le probabilità he i visitatori si interessino al padiglione i-esimo

agevolazioni ai visitatori

: questo fattore è piuttosto di ile da quanti-

are, per iò è stato adottato un riterio he onsiste nel onsiderare due stands he si aa

iano sullo stesso tratto di per orso. Introdu iamo un

oe iente

f

tale he

f= dove

g

PN

i=1 bi

2×g

,

indi a la lunghezza del path dei visitatori.

Per varie ragioni il valore del oe iente

f

si preferis e he sia alto per

quanto riguarda i visitatori Appli ando queste soluzioni ad un aso reale (l'edizione della era del 2000) si sono ris ontrati risultati soddisfa enti e il layout ottenuto è stato al olato in base a questi tre riteri di progetto. In parti olare si evidenziano i fattori

f = 80%

e

a¯i = 84%

dove quest'ultimo rappresenta l'indi e di adia enza

76

2. Ottimizzazione dei layout eristi i

Figura 2.18: al olo delle adia enze: nel primo aso sono al olate quattro ombinazioni

in base all'entità degli stand e del path, mentre nel se ondo ne sono al olate tre, on un solo tipo di stand ma on tre tipologie di per orso. medio ris ontrato. Come è illustrato in gura 2.19, gli stands più hiari (la maggioranza) orrispondono ad un zone più s ure vanno da

0.5

a

adja en y index

tra

0

e

0.5,

mentre le

1.

Figura 2.19: risultato nale dell'adja en y model appli ato all'esposizione del 2000. Basandosi per iò sull'adja en y model possiamo ostruire un modello di layout partendo da una ongurazione iniziale he onsiste nel posizionare uno spazio di seguito all'altro a

anto al per orso prestabilito per i visitatori, dove quest'ultimo viene già fornito all'inizio assieme ad al uni stand he sono

2.2 Studio e analisi di asi reali

77

già disposti per motivi moltepli i. A questo proposito sono stati sviluppati tre algoritmi per pro edere al piazzamento degli spazi espositivi della era di Romont. I dati di input degli algoritmi sono ostituiti da dati on ernenti le dimensioni degli stands e il layout iniziale. In parti olare intendiamo per layout iniziale la ongurazione he in lude le dimensioni le oordinate

(xi , yi)

L×B

del fairground,

dei nodi del per orso e i dati sul posizionamento degli

stand rettangolari e angolari

(oi , xi , yi ).

In gura 2.20 è ragurato un layout iniziale della era di Romont, in ui sono dati il path e gli stand pre-posizionati e in ui vanno installati tutti i rimanenti spazi espositivi, raggruppati nella parte sinistra dell'immagine. Come dati iniziali vengono quindi forniti

g = 508 e M = 35, ovvero la lunghezza del

path in unità di area e il numero di nodi, rispettivamente. L'algoritmo non fa altro he s egliere gli items rettangolari, oerentemente oi riteri adottati, e piazzarli nel fairground n hè non si raggiunge un layout nale. L'output dell'algoritmo sarà ostitutito per iò dai dati relativi agli stands posizionati, quindi

(oi , xi , yi),

e dal numero di stands he non è stato possibile in ludere.

Figura 2.20: layout di partenza della era di Romont dove si vedono il path e al uni

stand preposizionati, mentre a sinistra sono raggruppati gli altri stand da in ludere nel progetto. Diamo adesso al une denizioni he i permettono di proseguire on l'analisi:

•

deniamo

path se tion

una porzione di per orso delimitata da due nodi

78

2. Ottimizzazione dei layout eristi i e quindi in maniera più sempli e un segmento di per orso; se onsideriamo segmenti orizzontali si hanno due direzioni he sono est e ovest, mentre per quelli verti ali si parlerà di nord e sud; un ambio di direzione del per orso si ha quando si è all'inizio o alla ne di ias un segmento, e in questo aso si può girare a destra (dj (d j

•

= R)

o a sinistra

= L)

deniamo

orridoi laterali

quegli spazi, ortogonali al per orso, ne essari

a garantire he uno stand sia a

essibile attraverso entrate alternative,

he non si aa

iano ne essariamente al path

•

i

andidate points

sono le oordinate di ogni verti e di uno stand he

può essere piazzato interamente nel layout grazie al fatto he tutte le

oordinate soninterne all'area selezionata per il posizionamento. Inoltre sono

andidate points

an he quei punti in ui un nodo del per orso non

inuis e sullo stand, ad esempio andando a tagliare internamente lo stand

A questo punto proseguiamo on l'illustrare il primo algoritmo, il quale ha

ome s opo quello di testare la possibilità di piazzamento di uno spazio nel fairground, denendo tra i vari

onstraints an he la larghezza minima dei or-

ridoi laterali e l'adia enza dello stand al per orso. In parti olare l'algoritmo determina se uno stand è idoneo o meno ad entrare nel rettangolo riservato all'esposizione: in aso positivo signi a he lo stand non si sovrappone a nessun altro stand già presente, he non invade lo spazio riservato al path o ad altri elementi, he risiede interamente all'interno del rettangolo e he, inne, fornis e una larghezza minima del orridoio laterale idonea a quanto previsto. Utilizzando però questa soluzione si ottiene un layout he es lude al uni spazi espositivi e dunque è ne essaria una riformulazione dell'algoritmo he onsideri non più una ottimizzazione riferita ad un solo lato del segmento del path adia ente allo stand, bensì tutti i lati a ontatto on esso. Tale aggiornamento sarà identi ato ome se ondo algoritmo: questo appro

io rivela

he al une aree del per orso dei visitatori non sono usate appieno e he le aree disponibili he si in ontrano all'inizio del per orso sono più o

upate

2.2 Studio e analisi di asi reali

79

rispetto a quelle he si trovano verso la ne. Questo a

ade per hé l'algoritmo2 valuta le posizioni partendo proprio dal nodo iniziale del path. Un'ulteriore te ni a per ``ranare la pro edura onsiste nel distribuire in maniera più uniforme gli stands lungo il per orso usufuendo al massimo degli spazi inutilizzati. L'algoritmo3 ombina per iò le qualità positive delle due versioni pre edenti e rappresenta una versione denitiva e ultimata del layout, per hé permette di realizzare un progetto ottimo he soddisfa i requisiti e le spe i he e he ries e ad in ludere tutti gli stands nel fairground. In gura 2.21 sono rappresentate le tre versioni dell'algoritmo usato nell'edizione della era di Romont del 2000; si ri ondu e a ne apitolo per quanto riguarda la formuazione degli algoritmi se ondo uno pseudo-linguaggio.

Figura 2.21: tre versioni dell'algoritmo impiegato per il layout ottimo dell'esposizione del 2000.

I risultati ottenuti appli ando l'algoritmo nella sua versione nale mostrano

he la pro edura di ostruzione genera risultati promettenti, basandosi sul modello dell'adia enza. Inoltre i tre riteri pre edentemente analizzati (utilizzo degli spazi, valore attrattivo e agevolazioni ai lienti visitatori) sono

onnati in intervalli di a

ettabilità e i valori dei oe ienti

f

di quelli ris ontrati usando un layout ``manuale. Il oe iente

sono più alti

r = 0.64

he

80

2. Ottimizzazione dei layout eristi i misura il buono sfruttamento dello spazio è il migliore ris ontrato. Tutti i al oli e le elaborazioni sono stati eettuati su una ma

hina on pro essore Pentium a 200MHz on gli algoritmi implementati mediante il linguaggio Visual Basi 6.0, per un tempo impiegato dal al olatore he va da un minimo di

9.78

e

15.42

se ondi. L'algoritmo 3 impiega normalmente

un se ondo in più rispetto all'algoritmo 2, he prevede minor omplessità.

2.2.3 Considerazioni nali La disposizione degli stand in ambito eristi o non è an ora parti olarmente soggetta a studi s ienti i, tuttavia lo studio pre edentemente eseguito ha qual he parallelismo on il al olo del layout aziendale; di solito un layout eristi o tiene onto di più riteri, inve e in un layout aziendale il riterio fondamentale è quello di minimizzare i osti.

Per quanto riguarda la era

di Romont si sono utilizzati diversi riteri per avvi inarsi ad una soluzione a

ettabile. La pro edura su ui si basavano i tre algoritmi visti pre edentemente era improntata sulla ollo azione degli stand dato un erto per orso pressato e dati dei layout iniziali; proprio questi ultimi tendono ad inuenzare maggiormente il raggiungimento di un possibile layout nale, il quale dipende da:

•

dimensioni

della

super ie

•

espositiva

•

lunghezza del per orso (path)

•

numero di ambi di direzione nel per orso (nodi)

posizione (in oordinate artesiane) degli angoli degli per orso

•

posizione obbligatoria e irremovibile di al uni stands

Negli algoritmi pre edentemente studiati gli stand venivano ollo ati uno alla volta; si potrebbe inve e velo izzare il pro edimento usando un algoritmo di pa king in grado di ollo are diversi stand nello stesso momento. La

reazione del per orso iniziale può essere onsiderata ome un importante problema an he se è solo l'inizializzazione del layout; l'individuazione di un per orso ideale fa iliterebbe il raggiungimento di una soluzione a

ettabile

2.2 Studio e analisi di asi reali nale.

Per iò he riguarda la era di Fortaleza, inve e, si può on ludere aermando he l'implementazione dei due tipi di FLOP i ha portati all'ottenimento del nostro traguardo, potendo appunto aermare he il numero di stand he si possono ollo are all'interno dell'area espositiva di Fortaleza è maggiore di quello del layout pre edente.

Figura 2.22: Algoritmo 1.

81

82

2. Ottimizzazione dei layout eristi i

Figura 2.23: Algoritmo 2.

Figura 2.24: Algoritmo 3.

Capitolo 3 Casi di studio e spe i he di progetto Il presente apitolo è dedi ato all'analisi e all'appli azione degli algoritmi esaminati nel primo apitolo, aan ati dal riferimento alle soluzioni viste nel se ondo apitolo, in maniera tale da adattare tali onos enze ai asi di studio presentati qui di seguito. In parti olare, tra i dati di interesse fondamentale per l'appli azione dei modelli, si on entrerà l'attenzione sulle dimensioni degli stand (moduli) e sulle distanze tra di essi, sulla largheza dei orridoi e dei passaggi ( il modello di

Fair Layout Optimization Problem

aisles ) se ondo

già analizzato, e illustrato

nelle gure seguenti:

Figura 3.1: Flop1, aratteristi he e spe i he di pa kaging. 83

84

3. Casi di studio e spe i he di progetto

Figura 3.2: Flop2, aratteristi he e spe i he di pa kaging.

3.1 Presentazione dei asi di studio I layout eristi i presi in onsiderazione nel progetto di tesi sono tre:

•

la

Fiera del Levante di Bari, importantissima e elebre era ampio-

naria internazionale he si svolge annualmente nel apoluogo pugliese dal 13 al 21 settembre 2008

•

era mondiale dei vei oli alimentati a gas metano e ad idrogeno , he si avrà luogo dal 9 al la Fiera di Bolzano in o

asione della

1

12 Giugno 2008 ontemporaneamente al Congresso ENGVA

•

Expo Ferroviaria 2008 , era dedi ata all'industria e alla te nologia

l'

ferroviarie, dal 20 al 22 Maggio 2008 presso il Lingotto Fiere di Torino I modelli studiati nelle sezioni pre edenti sono generalizzabili a vari ontesti, per ui il fatto he si analizzino tre dierenti ontesti non è altro he una sempli e e diretta onferma al on etto di adattare le soluzioni alle varie tipologie di layout he si presentano. 1 European

Natural Gas Vehi le Asso iation, asso iazione europea dei vei oli a gas naturali, ome ad esempio metano e idrogeno

3.1 Presentazione dei asi di studio

3.1.1 Fiera del Levante La prima edizione della Fiera del Levante - Campionaria Internazionale - si è svolta nel 1930, mentre nel 1929 l'Ente Autonomo Fiera del Levante nas eva per iniziativa del Comune di Bari, dell'Amministrazione provin iale e della Camera di Commer io di Bari. La rassegna ha ontinuato a svolgersi puntualmente a settembre di ogni anno, on la sola interruzione durante gli anni della Se onda Guerra Mondiale, dal 1940 al 1946. Il quartiere eristi o si espande su di una super ie omplessiva di ir a 300 mila metri quadrati,

he ospitano nel orso dell'anno una trentina di manifestazioni al une delle quali hanno il ri onos imento di internazionalità.

Figura 3.3: vista panorami a dell'ingresso prin ipale (Ingresso Monumentale) alla Fiera del Levante di Bari. Complessivamente, gli espositori he parte ipano annualmente alle manifestazioni in alendario sono oltre 5.000, nazionali ed esteri. A ir a due milioni ammontano inve e i visitatori. La manifestazione maggiore resta an ora la Campionaria internazionale di settembre, he può ontare su oltre 2.000 espositori e più di 700.000 visitatori. La Fiera del Levante opera prin ipalmente al servizio del grande mer ato entromeridionale, pur allargando il suo ampo operativo al sud est europeo ed all'area mediterranea.

85

86

3. Casi di studio e spe i he di progetto Dal punto di vista dei dati te ni i la super ie espositiva, la ui planimetria è disponibile in gura 3.4, presenta:

•

44 padiglioni generali

•

una super ie espositiva omplessiva di 300.000 mq

•

33 padiglioni isolati

•

una super ie espositiva operta di 120.000 mq

•

7 porte di a

esso (ingressi alla era)

•

una

super ie

espositiva

s o-

perta di 40.000 mq

Figura 3.4: planimetria della Fiera del Levante di Bari. I padiglioni onsiderati per l'appli azione degli algoritmi sono stati s elti in modo da avere un appro

io il più eterogeneo possibile, al ne di oprire le più dierenti asisti he: nella fattispe ie sono stati presi in esame i padiglioni 11, 116 e 129. Mentre il primo presenta una super ie e una forma regolari, il se ondo e il terzo sono molto più irregolari e presentano dis ontinuità nei

ontorni. La s elta di questi spazi espositivi è appunto giusti ata dalle sostanziali dierenze tra i tre padiglioni, sia per quanto riguarda la dimensione degli stand, sia per il loro arrangiamento negli spazi previsti. Dal punto di

3.1 Presentazione dei asi di studio

87

vista delle dimensioni di interesse per l'appli azione degli algoritmi, di seguito sono elen ate le prin ipali aratteristi he di progetto ( on riferimento a entrambi i op e quindi alle gg. 3.1 e 3.2):

Dim. stand [h × w℄

Largh. orridoi [a℄

Dist. tra stand

Padiglione 11 4×4 m

3 m (vert.); 4 m (orizz.)

nessuna

4×3 m

6.02 m (orizz.)

nessuna

4×3.50 m

nessuna

Padiglione 116 4×4 m

5 m (vert.); 4 m (orizz.)

nessuna

6×6 m

nessuna

6×4 m

nessuna

Padiglione 129 4×4 m

5 m (vert.); 4 m (orizz.)

nessuna

6×6 m

nessuna

6×4 m

nessuna

Tabella 3.1: Caratteristi he e dimensionamenti dei parametri di progetto

Ogni riga rappresenta i diversi dimensionamenti he si trovano all'interno di

ias un padiglione. In parti olare non vi è una sola dimensione degli stand, né un'uni a alternativa per quanto riguarda la larghezza dei orridoi. Questo è dovuto, oltre he ad esigenze di spazio, alla forma del padiglione (irregolare o meno he sia) e agli osta oli strutturali ( onstraints) he si trovano all'interno degli spazi espositivi. Nell'implementare gli algoritmi per questo ontesto si terrà onto di una sola tipologia di dimensioni dei moduli ([h×w]) e dei orridoi ([a]), fornendo varie un'uni a alternativa progettuale in base ai dati di input standard, imposti dall'organizzazione. Nelle gura 3.5 sono mostrate le varie planimetrie dei padiglioni onsiderati, on un arrangiamento degli stands già predisposto per l'edizione 2007.

88

3. Casi di studio e spe i he di progetto

Figura 3.5: padiglioni della Fiera del Levante onsiderati nel progetto.

3.1.2 Fiera di Bolzano Da sempre la ittà di Bolzano, nodo fondamentale tra nord e sud Europa, è stata sede di ere e riunioni ommer iali e mer antili. Tuttavia la prima era ampionaria moderna risale al 1948, passando per gli anni '70 in ui si registrò un notevole sviluppo del quartiere eristi o, e giungendo ai giorni nostri in ui la Fiera di Bolzano è diventata una So ietà per Azioni, e ospita nel suo alendario più di 12 manifestazioni annuali di vario genere; si registrano omplessivamente ir a 171.000 visitatori l'anno. ``Fiera Bolzano si trova al entro della Zona Produttiva Bolzano Sud, solo 2,5 km la separano dal entro ittà, per ui il omplesso eristi o è fa ilmente raggiungibile grazie alla posizione alla periferia. Misura 40.000 mq tra super ie espositiva e annesso entro servizi; se poi si onsidera an he la struttura polifunzionale adia ente, il ``Palaonda, si hanno altri 5000 mq di spazio. Pro edendo on l'analisi dei dati salienti, il quartiere eristi o è osituito da 4 padiglioni espositivi, un padiglione polifunzionale (il Palaonda appunto), un Centro Servizi e un Centro Congressi e inne da un Hotel all'interno della

3.1 Presentazione dei asi di studio

89

Figura 3.6: organizzazione del quartiere ersisti o Fiera di Bolzano - Messe Bozen. era; il tutto aan ato da ampi e omodi par heggi sia interrati he super iali e rialzati. L'omogeneità delle super i degli stand onsente a tutti gli espositori una presentazione e a e dei propri prodotti e servizi. In parti olare, ome si può onfrontare an he in gura 3.6, la planimetria del quartiere è organizzata nel modo seguente:

•

padiglione A - espositivo

•

2500 mq

7600 mq

• •

•

padiglione C - espositivo 6060 mq

padiglione E - polifunzionale 5000 mq

padiglione B - espositivo 4700 mq

padiglione D - espositivo

•

padiglione S - entro servizi

•

padiglione K - entro ongressi

•

padiglione H - Hotel Fiera

Dal 9 al 12 giugno Fiera Bolzano S.p.A. ospiterà la era mondiale dei vei oli alimentati a gas metano e ad idrogeno. Contemporaneamente si terrà l'undi esimo Congresso europeo di ENGVA, asso iazione europea dei vei oli a metano e idrogeno. La era viene organizzata dalla rivista spe ializzata the Gas Vehi les Report on il sostegno della Provin ia Autonoma di Bolzano. Al proprio interno il quartiere eristi o possiede un'ampia area stradale riservata agli espositori, ma direttamente onnante on l'intera ostruzione

90

3. Casi di studio e spe i he di progetto

Figura 3.7: immagine a 360 gradi (espansa) del quartiere ersisti o Fiera di Bolzano Messe Bozen.

di mostra; i test drive all'interno di tale struttura ostituis ono una prova ulteriore per gli

exhibitors

di mostrare i loro prodotti in una zona he non

ri hiede agli ospiti di las iare il entro di mostra. La manifestazione ENGVA ha luogo all'interno del padiglione D, la ui struttura è rappresentata in gura 3.9; tale struttura presenta vin oli e

ts

onstrain-

tipi he, quali aree dedite ai servizi di ristorazione, us ite di emergenza,

ingressi e us ite prin ipali, strutture di sostegno (pilastri, e

.). Nella implementazione dei layout andrà tenuto onto di tutte queste aratteristi he. Con ludendo, si ha quindi he il padiglione D, di dimensioni pari a 7600mq, ospiterà stand di dimensioni standard (

basi stand )

pari a

5×5

metri (g.

3.8), mentre per i orridoi sarà prevista una larghezza minima di 4 metri. Inoltre saranno distinti due asi, nel primo dei quali la distanza minima tra stand è nulla, mentre nel se ondo è di 2 metri (sia orizzontale he verti ale).

Dim. stand [h

5×5 5×5

× w℄

Largh. orridoi [a℄

Dist. tra stand

m

4 m

nessuna

m

4 m

2 m

3.1 Presentazione dei asi di studio

91

Figura 3.8: dimensioni standard di uno stand basi della Fiera di Bolzano - Messe Bozen.

3.1.3 Expo Ferroviaria 2008 La manifestazione torinese è il punto di in ontro per l'industria ferroviaria internazionale, on espositori provenienti da 18 Paesi e spe ializzati nei più svariati ampi dell'industria e della te nologia he hanno a he vedere

ol mondo delle ferrovie. L'uni a era ferroviaria he ha luogo regolarmente in Italia si svolge a Torino presso il Lingotto Fiere dal 20 al 22 maggio 2008. Strutturalmente l'Expo ospitata al Lingotto Fiere si suddivide in due padiglioni, i quali hanno le seguenti dimensioni: Padiglione2

Padiglione1 dimensioni: 141

×

54 metri

dimensioni: 187

×

96 metri

totale: 7620 mq;

totale: 17960 mq;

altezza max: 10,5 metri;

altezza max: 14,2 metri;

Per quanto riguarda i dati inerenti gli spazi espositivi, onsiderando lo stand di gura 3.10, le dimensioni standard sono di

[h × w] = 4 × 4 metri; per

iò he on erne le larghezze dei orridoi, inve e, le dimensioni del parametro

[a]

sono di 3 metri; si è s elto, per evitare ompli azioni al modello e per hé

non indispensabili, di non onsiderare rilevanti (e quidi nulle) le distanze tra i singoli moduli. In gura 3.13 è riportata la planimetria della manifestazione di Torino.

92

3. Casi di studio e spe i he di progetto

Figura 3.9: Padiglione D della Fiera di Bolzano - Messe Bozen. Dim. stand [h

4×4

m

× w℄

Largh. orridoi [a℄

Dist. tra stand

3 m

nessuna

3.2 Criterio per la denizione e la s rittura delle matri i Riprendiamo un argomento già trattato, ma omunque di fondamentale rilievo per l'implementazione degli algoritmi e dei modelli appena visti. Si rei una matri e

Φ,

omposta da quadrati di dimensione

totalmente il rettangolo di dimensioni

[H × W ]

[δ × δ]

he opra

ontenente la super ie di

esposizione. Usando un appro

io granulare, si esprimeranno tutte le dimensioni (quelle esterne e degli stand) ome multipli di questi (pi

oli) valori. In parti olare è denita la seguente dimensione:

Xδ =

⌊Wδ × Hδ ⌋. Un elemento della matri e assume valore 1 se il orrispondente quadratino [δ ×δ]

dove

X = {H, W, h, w}.

X δ

Tale matri e ha per iò dimensioni

3.2 Criterio per la denizione e la s rittura delle matri i

Figura 3.10: dimensioni dello stand standard onsiderato per l'Expo Ferroviaria 2008. può essere usato ompletamente per l'impa

amento degli stand:

Φi,j =

(

1 0

se il quadrato

(i, j)

può essere interamente usato per il pa kage

altrimenti

∀j = 1, ..., Wδ e ∀i = 1, ..., Hδ . noti he per δ << W , o an ora meglio

questo Si

per

δ << w ,

l'approssimazione

risulta molto bassa. Ora si numerino le olonne da 1 a

Wδ

. Si dirà he una olonna è s elta per

l'impa

amento, se una stris ia di stand è piazzata on l'angolo sinistro dello stand all'inizio della olonna.

A ausa del riterio utilizzato e per evitare

di dover ostruire matri i in input di notevoli dimensioni è stata usata l'approssimazione al metro (ogni quadratino orrisponde ad un mq). Di questa approssimazione ne risentono ad esempio le dimensioni delle porte he a volte possono raggiungere la larghezza di 2 metri. Si ri ordi he, dato un modello, la soluzione del orrispondente rilassamento lineare è sempre intera se tutta la parte destra del modello è intera e se la matri e dei vin oli è totalmente

2

unimodulare 2 una

(TUM).

matri e totalmente unimodulare è una matri e (non ne essariamente quadrata) per la quale an he ogni minore non singolare è unimodulare. Ne onsegue he ogni suo elemento vale 0, +1 o −1. Un programma intero nel quale la matri e dei vin oli è totalmente unimodulare può essere risolto e ientemente, in quanto il suo rilassamento LP porta a soluzioni intere.

93

94

3. Casi di studio e spe i he di progetto

Figura 3.11:

Ferroviaria 2008.

panorami a del quartiere Lingotto Fiere di Torino sede dell'Expo

3.2 Criterio per la denizione e la s rittura delle matri i

Figura 3.12: planimetria del quartiere Lingotto Fiere di Torino. sottolineati i padiglioni sede dell'Expo Ferroviaria 2008.

In rosso sono

95

96

3. Casi di studio e spe i he di progetto

Figura 3.13: padiglioni della Expo Ferroviaria 2008. I due padiglioni sono separati dai

muri portanti (in nero). Nella parte alta del se ondo padiglione è stata tagliata la zona di ristorazione, omunque inutile al layout. La gura omprende solamente le zone idonee al

ontenimento degli stand.

Capitolo 4 Implementazione degli algoritmi e risultati omputazionali Questo apitolo è dedi ato all'appli azione spe i a degli algoritmi presentati nel apitolo 1 ai asi di studio presentati nel apitolo pre edente. Partendo dalle planimetrie delle ere di Bari, Bolzano e Torino, sono stati implementati gli algoritmi tramite un software sviluppato su piattaforma Java dall'Ing.Muritiba, presso il DEIS

1

di Bologna.

Tale appli ativo è in grado di fornire soluzioni per l'impa

amento del maggior numero possibile di stand. Il software lavora ostruendo le piantine dei padiglioni attraverso delle oordinate he vengono fornite ome input; il on etto base è quello di reare un poligono esterno on la forma del padiglione e su

essivamente reare dei pi

oli poligoni interni he evidenzino le aree in

ui non è possibile impa

are gli stand (a ausa di porte, bar, servizi, e

.). Per reare questi poligoni è ne essario fornire le oordinate

X−Y

di ogni

angolo partendo da un punto, ed elen are su

essivamente tutti i restanti punti in senso orario o in senso antiorario. I poligoni sono divisi in due tipi:

•

polygon unlo k - è il poligono he rappresenta la forma del padiglione o di iò he voglio rappresentare; può essere uno solo

•

polygon lo k - rappresenta ogni singola area in ui non è possibile im-

1 Dipartimento

di Elettroni a, Informati a e Sistemisti a 97

98

4. Implementazione degli algoritmi e risultati omputazionali pa

are al uno stand ed è evidente he all'interno di un'area espositiva ne troveremo di diversi tipi Come si vedrà poi meglio nello studio dei singoli asi reali, la forma degli spazi espositivi e dei orridoi è rappresentata in bian o mentre tutti i vin oli (polygon lo k) sono rappresentati da spazi grigi. Una volta introdotti questi

2

dati in input si è poi provveduto alle implementazioni di due diversi FLOP

per al olare quanti stand poter inserire all'interno dei nostri padiglioni. Per ogni planimetria sono stati eseguiti entrambi i FLOP, le ui aratteristi he sono ri hiamate brevemente di seguito:

Flop1

: si tratta di singoli strip di stand di forma quadrata dove vengono

h (lato dello stand), s (pi

oli orridoi di separazione tra gli stand) ed a (distanza tra gli strip di stand). Spe i hiamo però he s è sempre stato onsiderato nullo in entrambi i FLOP

forniti in input i valori di

per ias una soluzione

Flop2

: si tratta di doppi strip di stand dove vengono forniti in input gli

stessi dati del FLOP1; in più ompare un dato

d

he però negli studi

presentati di seguito sarà sempre onsiderato nullo Con riferimento ai asi di studio proposti, verranno presentate di seguito le varie soluzioni relative all'implementazione degli algoritmi e dei

op

ai vari

padiglioni. Si sottolinea he la pro edura di implementazione degli algoritmi, per ias una soluzione, è stata eettuata su ma

hine ostituite da pro essore Intel Core 2 Duo on 1GB di memoria RAM e sistema operativo Linux Ubuntu su ui è installata la Java Virtual Ma hine.

4.1 Fiera del Levante: soluzione Con riferimento al padiglione 11 e alle dimensioni rappresentate nella tabella 3.1, presentiamo le soluzioni relative, prima impiegando il FLOP1 e quindi il FLOP2: 2 a ronimo

per indi are il Fair Layout Optimization Problem

4.1 Fiera del Levante: soluzione

99

CPU-time FLOP1

CPU-time FLOP2

Stands FLOP1

Stands FLOP2

215 ms

680 ms

89

114

Ri ordiamo he nelle ipotesi abbiamo onsiderato i moduli di dimensione standard

4×4

metri e i orridoi di larghezza 4 metri in linea orizzontale

e 3 metri in verti ale, tralas iando gli altri asi poi hé la soluzione attuale rappresenta il miglior ompromesso tra spazi o

upati e numero di stand ottimo. In gura 4.1 sono rappresentate le soluzioni relative al Padiglione 11.

Figura 4.1: soluzioni proposte per il padiglione 11 on FLOP1 e FLOP2. Per quanto riguarda il padiglione 116, sempre on riferimento alla tabella 3.1, si riportano entrambe le soluzioni adottate: CPU-time FLOP1

CPU-time FLOP2

Stands FLOP1

Stands FLOP2

158 ms

351 ms

27

31

In gura 4.2 sono riportate le rispettive gra he dei FLOP. In questo padiglione le dimensioni relative alla dimensione dei moduli sono

100

4. Implementazione degli algoritmi e risultati omputazionali

Figura 4.2: soluzioni proposte per il padiglione 116 on FLOP1 e FLOP2. In questo

aso gli stand sono rappresentati in nero e i vin oli sempre in grigio. sempre di

4×4

metri, mentre i orridoi hanno dimensione di 5 (verti ale)

×

4 (orizzontale) metri. Prendiamo inne in onsiderazione inne il Padiglione 129, di forma piuttosto irregolare analogamente al aso pre edente, e riportiamo le soluzioni nella tabella seguente e nella gura 4.3: CPU-time FLOP1

CPU-time FLOP2

Stands FLOP1

Stands FLOP2

106 ms

272 ms

24

31

dove, ome per i pre edenti padiglioni, la dimensione degli stand è di metri e per i orridoi è di 5 (verti ale)

×

4×4

4 (orizzontale) metri.

Nel listato seguente sono elen ati i le di input da fornire al software Java per

ostruire il layout di ias un padiglione (rispettivamente, i padiglioni 11, 116 e 129), tenendo in onsiderazione i vin oli e gli osta oli imposti dal ontesto:

polygon; unlo k; 0 0; 0 80; 70 80; 70 0 lo k1; lo k; 0 0; 0 8; 4 8; 4 0 lo k2; lo k; 0 18.5; 0 22.5; 4 22.5; 4 18.5

4.1 Fiera del Levante: soluzione

101

Figura 4.3: soluzioni proposte per il padiglione 129 on FLOP1 e FLOP2. In questo

aso gli stand sono rappresentati in nero e i vin oli sempre in grigio. lo k3; lo k; 0 33; 0 37; 4 37; 4 33 lo k4; lo k; 0 47.5; 0 52; 4 52; 4 47.5 lo k5; lo k; 0 64; 0 78; 4 78; 4 64 lo k6; lo k; 66 0; 66 12; 70 12; 70 0 lo k7; lo k; 66 20; 66 24; 70 24; 70 20 lo k8; lo k; 66 34.5; 66 42.5; 70 42.5; 66 34.5 lo k10; lo k; 66 53; 66 63; 70 63; 70 53 lo k11; lo k; 12 80; 12 75; 16 75; 16 80 polygon; unlo k; 0 0; 0 84; 16 100; 48 100; 48 81; 22 81; 18 78; 18 0 lo k1; lo k; 0 0; 0 84; 16 100; 24 100; 24 92; 18 92; 14 90; 6 84; 4 76; 4 0

102

4. Implementazione degli algoritmi e risultati omputazionali

lo k2; lo k; 48 81; 32 81; 32 87; 48 87 lo k3; lo k; 18 26; 14 26; 14 38; 18 38 lo k4; lo k; 18 92; 22 92; 22 90; 18 90 polygon; unlo k; 0 0; 0 31,2; 22 53.2; 46 30; 33.6 18; 33.6 0 lo k1; lo k; 0 6.4; 0 12; 3 12; 3 6.4 lo k2; lo k; 0 20.8; 0 26.4; 3 26.4; 3 20.8 lo k3; lo k; 8 38; 22 53.2; 24 51.2; 10 36; 8 36; lo k4; lo k; 46 30; 43.2 27.2; 36 34; 38 37.2

4.2 Fiera di Bolzano: soluzione Avendo pre edentemente onsiderato la forma degli stand di

5 × 5 metri e

la larghezza di tutti i orridoi di 4 metri (sia in orizzontale he in verti ale), la soluzione presentata per il padiglione D della Fiera di Bolzano è riassunta nella tabella he segue:

CPU-time FLOP1

CPU-time FLOP2

Stands FLOP1

Stands FLOP2

aso1

230 ms

710 ms

112

126

aso2

275 ms

800 ms

94

100

In questa rappresentazione sono stati prese in onsiderazione due varianti: nel primo aso ( aso 1) la distanza imposta tra gli stands è nulla, mentre nel se ondo ( aso 2) è di 2 metri sia in orizzontale he in verti ale. Per il resto tutti i parametri rimangono invariati. Analogamente a quanto fatto per il ontesto pre edente, viene qui di seguito presentato il listato relativo al ontesto di Bolzano oi rispettivi rappresentano i vin oli e gli osta oli all'interno del padiglione:

polygon; unlo k; 0 0; 0 80; 85 lo k1; lo k; 0 0; 0 30; 13 30; lo k2; lo k; 14 0; 14 5; 19 5; lo k3; lo k; 33 0; 33 5; 38 5; lo k4; lo k; 52 0; 52 5; 57 5;

80; 85 0 13 0 19 0 38 0 57 0

lo k

he

4.3 Expo Ferroviaria 2008: soluzione

103

lo k5; lo k; 71 0; 71 5; 76 5; 76 0 lo k6; lo k; 0 30; 0 35; 5 35; 5 30 lo k7; lo k; 0 44; 0 49; 5 49; 5 44 lo k8; lo k; 0 63; 0 68; 5 68; 5 63 lo k9; lo k; 13 80; 20 80; 20 74; 13 74 lo k10; lo k; 51 80; 58 80; 58 74; 51 74 lo k11; lo k; 23 5; 23 7.5; 25.5 7.5; 25.5 5 lo k12; lo k; 41.5 5; 41.5 7.5; 44 7.5; 44 5 lo k13; lo k; 60 5; 60 7.5; 62.5 7.5; 62.5 5 lo k14; lo k 78.5 5; 78.5 7.5; 80 7.5; 80 5 lo k15; lo k; 78.5 24; 78.5 26.5; 80 26.5; 80 24 lo k16; lo k; 78.5 41.5; 78.5 44; 80 44; 80 41.5 lo k17; lo k; 78.5 59; 78.5 61.5; 80 61.5; 80 59

4.3 Expo Ferroviaria 2008: soluzione Il al olo degli elementi e degli spazi per i padiglioni dell'Expo Ferroviaria 2008 hanno portato ad una soluzione ottimizzata he viene riassunta nella tabella seguente: CPU-time FLOP1

CPU-time FLOP2

Stands FLOP1

Stands FLOP2

174 ms

478 ms

264

374

371 ms

1046 ms

578

781

Tabella 4.1: Risultati dei al oli per i padiglioni dell'Expo Ferroviaria 2008. In alto i dati riguardanti il pad.1 e in basso quelli per il pad.2.

mentre per quanto riguarda le immagini relative ad entrambi i padiglioni, esse sono rappresentate nelle gure 4.4 e 4.5

Ri ordiamo he, per entrambi

i padiglioni, le dimensioni dei moduli sono di

4×4

metri, mentre i orridoi

hanno una larghezza di 3 metri. Presentiamo inne i le di input he permettono la mappatura dei due padiglioni dell'Expo Ferroviaria:

polygon; unlo k; 0 0; 0 153; 54 153; 54 0

104

4. Implementazione degli algoritmi e risultati omputazionali

lo k1; lo k; 0 0; 0 12.5; 54 12.5; 54 0 lo k2; lo k; 0 12; 0 16; 31 16; 31 12 lo k3; lo k; 0 20; 0 27.92; 4 27.92; 4 20 lo k4; lo k; 0 35.84; 0 38.34; 2.5 38.34; 2.5 35.84 lo k5; lo k; 0 45.34; 0 53.26; 4 53.26; 4 45.34 lo k6; lo k; 0 60.26; 0 62.76; 2.5 62.26; 2.5 60.26 lo k7; lo k; 0 69.26; 0 77.18; 54 77.18; 54 69.26 lo k8; lo k; 0 83.68; 0 86.18; 2.5 86.18; 2.5 83.68 lo k9; lo k; 0 93.18; 0 101.1; 4 101.1; 4 93.18 lo k10; lo k; 0 107.6; 0 110.1; 2.5 110.1; 2.5 107.6 lo k11; lo k; 0 116.6; 0 124.52; 54 124.52; 54 116.6 lo k12; lo k; 0 128.52; 0 153; 24.48 153; 24.48 128.52 lo k13; lo k; 51.5 153; 54 153; 54 150.5; 51.5 150.5 lo k14; lo k; 51.5 133.52; 54 133.52; 54 131.02; 51.5 131.02 lo k15; lo k; 51.5 110.1; 54 110.1; 54 107.6; 51.5 107.6 lo k16; lo k; 51.5 86.18; 54 86.18; 54 83.68; 51.5 83.6 lo k17; lo k; 51.5 62.76; 54 62.76; 54 60.26; 51.5 60.26 lo k18; lo k; 51.5 38.34; 54 38.34; 54 35.84; 51.5 35.84 polygon; unlo k; 0 0; 0 199; 96 199; 96 0 lo k1; lo k; 0 0; 0 12.5; 96 12.5; 96 0 lo k2; lo k; 0 199; 96 199; 96 124.52; 60 124.52; 60 174.52; 0 174.52 lo k3; lo k; 0 116.6; 0 124.52; 96 124.52; 96 116.6 lo k4; lo k; 0 69.26; 0 77.18; 96 77.18; 96 69.26

4.4 Considerazioni nali Rispetto all'arrangiamento degli spazi eettuato dagli organizzatori, i risultati ottenuti mediante al oli e modelli matemati i hanno portato ad un miglioramento e ad un'ottimizzazione in termini di stand impiegati e di vin oli rispettati, il tutto in a

ordo on le spe i he mostrate nel terzo apitolo. In parti olare, per quanto riguarda le tre alternative e i tre layout analizzati, si sono ris ontrati i risultati omplessivi s hematizzati in tabella 4.2

4.4 Considerazioni nali

105

Stands originali Stands FLOP1 Stands FLOP2 Padiglione 11 Fiera del Levante

154

89

114

45

27

31

16

24

31

90

112

126

90

94

100

114

274

374

219

578

781

Padiglione 116 Fiera del Levante Padiglione 129 Fiera del Levante Padiglione D.1 Fiera di Bolzano Padiglione D.2 Fiera di Bolzano Padiglione 1 Expo Ferroviaria Padiglione 2 Expo Ferroviaria

Tabella 4.2: Numero di stands per ogni layout analizzato, in relazione agli stand disposti dagli organizzatori nella ongurazione originale di ias un padiglione. Si noti he il padiglione D del ontesto di Bolzano è stato suddiviso in due parti a se onda dei asi enun iati nel paragrafo 4.2

Oltre ai dati relativi al numero di stands ``impa

hettati e alle elaborazioni

omputazionali, ri opre fondamentale importanza e rilevanza il dato relativo alla dimensione delle matri i asso iate ai vari FLOP. In parti olare, rimandando il lettore al paragrafo 3.2, le matri i reate onseguentemente alle elaborazioni sono, per ias una delle manifestazioni eristi he onsiderate, le seguenti: Matrix Pad. 11

Matrix Pad. 116

Matrix Pad. 129

[799 x 699℄

[999 x 479℄

[531 x 459℄

Tabella 4.3: Dimensione delle matri i per la Fiera del Levante

106

4. Implementazione degli algoritmi e risultati omputazionali

Matrix Pad. D.1

Matrix Pad. D.2

[749 x 639℄

[819 x 669℄

Tabella 4.4: Dimensione delle matri i per la Fiera di Bolzano - Messe Bozen

on le due soluzioni in base alla distanza tra i moduli

Matrix Pad. 1

Matrix Pad. 2

[1529 x 539℄

[1989 x 959℄

Tabella 4.5: Dimensione delle matri i per l'Expo Ferroviaria 2008

4.4 Considerazioni nali

107

Figura 4.4: soluzioni proposte per il padiglione 1 dell'Expo Ferroviaria on FLOP1 e FLOP2 rispettivamente a sinista e a destra.

108

4. Implementazione degli algoritmi e risultati omputazionali

Figura 4.5: soluzioni proposte per il padiglione 2 dell'Expo Ferroviaria on FLOP1 e FLOP2 rispettivamente a sinista e a destra.

Capitolo 5 Con lusioni Prima di parlare degli obiettivi raggiunti, è bene riper orrere velo emente tutta la strada fatta. Dopo aver individuato nel FLOP (Fair Layout Optimization Problem) il uore della tesi, si è intrapreso un per orso di ri er a nella letteratura, dapprima in ambito logisti o e poi nell'area della ri er a operativa, allo s opo di trovare qual he supporto bibliogra o signi ativo. In ambito logisti o sono stati trovati solo testi inerenti al layout industriale, ma po hissimi testi fo alizzato sul layout eristi o. An he per quanto riguarda l'ambito della ri er a operativa, non sono state trovate pubbli azioni indirizzate al FLOP, ma sono omunque stati trovati problemi simili. Il problema del posizionamento di stand può essere infatti visto ome aso parti olare dei problemi di impa

amento rivolti ad altri oggetti ( ui possiamo ri ondurre gli stands); un ampio apitolo della tesi è infatti in entrato sui problemi di Knapsa k, di Cutting e di Pa king. La ri er a bibliogra a ha portato alla s operta di un altro problema già ampiamente dis usso in letteratura e he si avvi ina a quello della tesi; si tratta del Fa ility Layout Problem (FLP). In parti olare una tipologia parti olare di quest'ultimo, ovvero il Quadrati Assignement Problem (QAP), presenta aratteri molto simili agli ultimi modelli presentati nel apitolo 3. Se da un lato gli algoritmi studiati per il FLP possono essere prese ome riferimento e ome spunto per al uni sviluppi futuri del FLOP, non potranno mai essere presi in toto, poi hé nei primi vi è il usso tra una posizione e l'altra ome

driver

prin ipale, mentre nel se ondo

non vi è al un problema di movimentazione di materiali. 109

110

5. Con lusioni

Una volta nita la parte di ri er a bibliogra a sono stati arontati i modelli per la risoluzione del FLOP; questi ultimi sono stati prima analizzati nel apitolo 3 e poi inseriti nei ontesti presentati nel apitolo 4. Inne, nel quinto apitolo sono stati des ritti i risultati delle implementazioni sul software, tenendo ovviamente onto di vin oli e spe i he tipi i di un layout di tipo eristi o. Proprio l'implementazione ha dimostrato la validità di tutti i modelli presentati nei apitoli addietro; sono stati tutti orrettamente ompilati ed eseguiti dal software di ottimizzazione. In parti olare si è dimostrato he:

•

le matri i asso iate alle variabili dei primi quattro modelli sono totalmente unimodulari, e proprio per questo i vin oli di interezza delle variabili possono essere sostituiti dai vin oli di minore o uguale

•

tutti i modelli produ ono l'output istantaneamente o in breve tempo (al massimo viene ri hiesto qual he minuto per i modelli più laboriosi)

•

tutti i modelli funzionano orrettamente e restituis ono un output orretto e in linea on le ri hieste

A parte tutte queste onsiderazioni, iò he fa di questa tesi uno s ritto interessante onsiste nella generalizzabilità del lavoro svolto. I modelli esposti possono infatti essere utili in qualsiasi ontesto eristi o, in aree espositive di qualsiasi forma (sia regolare he irregolare): gli algoritmi matemati i des ritti sono infatti estremamente versatili e bastano pi

oli ambiamenti per poterli adattare a qualsiasi esigenza. La onferma di tutto questo è data dal fatto

he i modelli siano stati orrettamente usati in ontesti diversi tra loro, on spazi espositivi e forme regolari e irregolari, on più o meno

onstraints

da

aggirare, e in spazi aperti o hiusi. In sintesi, i punti di forza della tesi risiedono nell'innovazione dal punto di vista dello studio matemati o ol quale è arontato l'argomento dei layout eristi i (è un argomento piuttosto nuovo e tuttora in pieno sviluppo) e la generalizzabilità dei modelli e degli algoritmi presentati.

Bibliograa [1℄ A.E. Fernandes Muritiba, Manuel Iori, Silvano Martello, M.J. Negreiros Gomes.

Models and algorithms for fair layout optimization problems.

Operations Resear h Letters, 2008 (in orso di pubbli azione)

Layout modeling and onstru tion pro edure for the arrangement of exhibition spa es in a fair. Bla kwell, 2003

[2℄ P. S hneuwly, M. Widmer.

[3℄ S. Martello, P. Toth.

implementations. John [4℄ A. Caprara,

Knapsa k Problems. Algorithms and omputer Wiley & Sons

M. Mona i.

On the 2-dimensional knapsa k problems.

Operational Resear h Letters, 2003

An upper bound for the zero-one knapsa k problem and a bran h and bound algorithm. European Journal of Operational

[5℄ S. Martello, P. Toth.

Resear h, 1977

[6℄ R. Burkard, M. Dell'Ami o, S. Martello.

Assignment Problems.

SIAM

Monographs on Dis rete Mathemati s and Appli ations

[7℄ G. Christodes, A. Mingozzi, P. Toth.

Contributions to the quadrati

assignment problem. European Journal of Operational Resear h, [8℄ P. C. Gilmore, R. E. Gomory.

Multistage utting problems of two and

more dimensions. Operations Resear h, [9℄ E. L. Lawler.

1980

1965

The Quadrati Assignment Problem. Management S ien e,

1963 111

112

BIBLIOGRAFIA Approximation algorithms for the oriented two-dimensional bin pa king problem. European Journal of Operational

[10℄ A.Lodi, S.Martello, D.Vigo.

Resear h, 1999 [11℄ M.Iori, S.Martello, M.Mona i.

king Problem.

Metaheuristi Algorithms for Strip Pa -

Optimization and Industry:

New Frontieres, Kluwer

A ademi Publisher (Pardalos P. e Korotki h V. eds.), 2003

An hybrid geneti algorithm for the twodimensional single large obje t pla ement problem. European Journal of

[12℄ E.Hadji onstantinou, M.Iori.

Operational Resear h, 2006 [13℄ J.E.Beasley.

An exa t two-dimensional non-guillotine utting tree sear h

pro edure. Operational Resear h,

1985

A tabu sear h algorithm for a two-dimensional non-guillotine utting problem. European Journal of

[14℄ R.Alvarez-Valdes, F.Parrenho, J.M.Tamarit.

Operational Resear h, 2006 [15℄ D. Vigo.

Lezioni di Ri er a Operativa L-A.

Slides presentate a lezione,

AA. 2007-2008 [16℄ Lisa Bian hini.

Tesi di Laurea sui layout eristi i. Università degli Studi

di Modena e Reggio Emilia [17℄ Lu a Rusti helli.

Tesi di Laurea sui layout eristi i.

Università degli

Studi di Modena e Reggio Emilia [18℄ Mar Baudoin.

Impara LATEX! (...e mettilo da parte).

É ole Nationale

Supérieure de Te hniques Avan ées, Paris [19℄

Wikipedia, www.wikipedia.org

[20℄

DEIS, Università di Bologna, www.deis.unibo.it

[21℄

Operational

Resear h

at

DEIS,

Università

di

Bologna,

S ien e,

University

of

Liverpool,

www.or.deis.unibo.it [22℄

Department

of

www. s .liv.a .uk

Computer

BIBLIOGRAFIA [23℄

Institute of Ele tri al and Ele troni al Engineers, www.ieee.org

[24℄

Google, www.google.it

[25℄

Fiera di Bolzano, www.erabolzano.it

[26℄

Fiera del Levante, www.eradellevante.it

[27℄

Expo Ferroviaria 2008, www.expoferroviaria. om

[28℄

S ien e Dire t, www.s ien edire t. om

[29℄

Asso iazione Italiana di Ri er a Operativa, www.airo.org

113