Modelli e algoritmi per l'ottimizzazione di layout fieristici

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 progettazio-
ne, 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 stu-
diati nei pre
edenti 
apitoli. Con riferimento alle alternative studiate
nel terzo 
apitolo, verranno qui implementate le metodologie per l'ap-
pli
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 miglio-
ramento 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 mo-
do 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 pos-
sibile di soggetti interessati ad un 
erto aspetto di produzione o di organizza-
zione (
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 grup-
po 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

upa-
zione 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 lo-
ro 
omplesso; i prin
ipali ris
ontri dovuti a un'adeguata organizzazione del
lavoro si avranno sulla planimetria delle aree adibite all'esposizione. In par-
ti
olare si otterranno vantaggi in ambito logisti
o, ad esempio nell'ottimiz-
zazione 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 ade-
guata 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 este-
ti
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 pro-
gettazione deve avvenire in modo pre
iso e metodi
o prendendo in 
onside-
razione 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 è possibile studiare la dispo-
sizione di stand, passaggi, ussi e per
orsi. 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
e a vuoto1. 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 Operativa2 è 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 tro-
vare una soluzione massimizzata o minimizzata per mettere insieme un dato
insieme di oggetti in uno o più 
ontenitori. Questa metodologia è molto uti-
lizzata 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 throughput3 e i tempi di latenza4 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 proble-
ma, si possono suddividere gli appro

i progettuali in tre dimensioni. Trat-
tandosi di layout eristi
i, il nostro interesse si soermerà solamente su due
dimensioni, relativamente all'area espositiva della era.
1si intende nei 
asi di massime e minime presenze di visitatori, ma an
he di ussi di
materiale, personale ed eventuali mezzi 
oinvolti nell'organizzazione.
2settore 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
3numero di unità 
ompletate in un 
erto lasso di tempo.
4tempo impiegato per la produzione di un bene materiale o di un servizio oerto.
1.2 Cutting and Pa
king problems 5
Figura 1.1: Sempli
azione 
on
ettuale di un generi
o knapsa
k problem
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)
E' ne
essario sottolineare 
he il 
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 
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 fat-
tispe
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 =
{
1 se l'oggetto j è s
elto
0 altrimenti
Se inoltre indi
hiamo 
on pj il protto dato dall'oggetto j (lo stand nel nostro

aso), 
on wj la sua dimensione e 
on c la dimensione del suo 
ontainer (ossia
il suo 
osto), allora l'obiettivo Knapsa
k sarà quello di selezionare, tra tutti,
i vettori binari x 
he soddisfano il vin
olo
n∑
j=1
wjxj ≤ c
e 
he massimizzano la funzione obiettivo
n∑
j=1
pjxj .
1.2 Cutting and Pa
king problems 7
Per generalizzare il problema 
hiamiamo gli oggetti items, 
on una quantità
pari ad n; il valore e la dimensione dell'oggetto j − esimo sono 
hiamati
rispettivamente protto e peso e indi
ati 
on pj e vj (j = (1, ..., n)). Na-
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-
bile all'algoritmo Knapsa
k, 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 Cutting
and Pa
king problems in base alle denizioni pre
edentemente fornite per
problemi a una e due dimensioni.
KNAPSACK 0-1 (BINARY)
IlKnapsa
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. Tale problema, detto
``dello zaino''5 è 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'algo-
ritmo 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 dell'oggetto j
wj = peso dell'oggetto j
c = 
apa
ita del 
ontenitore
è opportuno s
egliere un sottoinsieme di items tale da:
massimizzare −→ max(z) =
n∑
j=1
pjxj (1.1)
soddisfa
endo −→
n∑
j=1
wjxj ≤ c (1.2)
1.2 Cutting and Pa
king problems 9
dove −→ xj ∈ {0, 1} , j ∈ N = {1, ..., n} (1.3)
analogamente alle denizioni date in pre
edenza.
Se ora ipotizziamo 
he
pj , wje c sono interi positivi, (1.4)
n∑
j=1
wj ≤ c, (1.5)
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 even-
tuali valori negativi verranno trattati 
ome 0 o 
ome 1 in base alle seguenti
relazioni:
• ∀j ∈ N0 = {j ∈ N : pj ≤ 0, wj ≥ 0} =⇒ xj = 0
• ∀j ∈ N1 = {j ∈ N : pj ≥ 0, wj ≤ 0} =⇒ xj = 1
Deniamo inoltre N− 
ome N− = {j ∈ N : pj < 0, wj > 0}, mentre per N+
il valore sarà: N+ = N \ (N0 ∪N1 ∪N−).
Inne deniamo:
{
yj = 1− xj , p¯j = −pj , w¯j = −wj per j ∈ N−
yj = xj , p¯j = pj , w¯j = wj per 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 =
∑
j∈N−∪N+
p¯jyj +
∑
j∈N1∪N−
pj
mentre 
ome 
onstraint del problema la funzione
∑
j∈N−∪N+
w¯jyj ≤ c−
∑
j∈N1∪N−
wj.
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
w1
≥ p2w2
≥ ... ≥ pnwn
Data ad ogni problema una istanza I, si indi
herà il valore di ogni soluzione
ottima 
on z(I) 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∑
j=1
pjyj
soddisfa
endo −→
n∑
j=1
wjyj ≤ q
dove −→ yj ∈ {0, 1} , j ∈ N = {1, ..., n}
dal quale si evin
e 
he il pro
edimento per tornare da una forma (minimiz-
zata) all'altra (massimizzata) 
onsiste nel porre yj = 1 − xj e risolvendo la
(1.1), la (1.2) e la (1.3) 
on c =∑n
j=1 wj − q.
Inoltre, ponendo 
ome zmax il valore della soluzione massimizzata di ogni
problema, la sua versione minimizzata sarà zmin =
∑n
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 
o-
siddetto 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
originale6:
massimizzare −→ max(z) =
n∑
j=1
pjxj
6metodo improntato sull'ampliamento della regione ammissibile e/o sull'innalzamento
della funzione obiettivo in 
orrispondenza della regione ammissibile originale