tesi

Problemi di ottimizzazione nel Facility Design

Pierpaolo Caricato

6 dicembre 2002

Indice

1 I problemi di Facility Design 6

1.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2 Struttura del lavoro di tesi . . . . . . . . . . . . . . . . . . . . 7

2 Problemi di Facility Layout 9

2.1 Systematic Layout Planning . . . . . . . . . . . . . . . . . . . 10

2.1.1 Misurazione dei flussi (Diagrammi From-To) . . . . . . 11

2.1.2 Analisi Attivita/Relazioni (Diagrammi REL) . . . . . . 14

2.1.3 Progettazione del layout fisico . . . . . . . . . . . . . . 15

2.2 Modelli matematici per i problemi di FL . . . . . . . . . . . . 20

2.2.1 QAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.2.2 ABSMODEL . . . . . . . . . . . . . . . . . . . . . . . 21

3 Problemi di Material Handling 27

3.1 Topologie per il Material Handling . . . . . . . . . . . . . . . 28

3.2 Stato dell’arte nelle configurazioni basate su loop . . . . . . . 28

3.2.1 Sequenziamento dei punti di P/D . . . . . . . . . . . . 29

3.2.2 Localizzazione delle celle . . . . . . . . . . . . . . . . . 29

3.2.3 Progettazione di layout a loop singolo . . . . . . . . . . 29

3.2.4 Progettazione di configurazioni tandem . . . . . . . . . 29

4 Single Loop Design Problem (SLDP) 30

4.1 Introduzione e analisi della letteratura . . . . . . . . . . . . . 30

4.2 Formulazione MILP . . . . . . . . . . . . . . . . . . . . . . . . 34

4.3 Branch and cut . . . . . . . . . . . . . . . . . . . . . . . . . . 37

1

INDICE 2

4.3.1 Tagli aggiuntivi di tipo 1 . . . . . . . . . . . . . . . . . 38




4.3.5 Algoritmo Branch & Cut . . . . . . . . . . . . . . . . . 41

4.4 Tabu Search per lo SLDP . . . . . . . . . . . . . . . . . . . . 42

4.4.1 Le meta-euristiche Tabu Search . . . . . . . . . . . . . 42

4.4.2 Implementazione del TS nello SLDP . . . . . . . . . . 55

4.5 Risultati computazionali . . . . . . . . . . . . . . . . . . . . . 62

4.5.1 Gli esperimenti . . . . . . . . . . . . . . . . . . . . . . 62

4.5.2 Taratura del Tabu Search . . . . . . . . . . . . . . . . 63

4.5.3 Risultati . . . . . . . . . . . . . . . . . . . . . . . . . . 66

Bibliografia 68

A Layout utilizzati 71

Elenco delle figure

2.1 Matrici From-To . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2 Confronto tra matrici from-to . . . . . . . . . . . . . . . . . . 14

2.3 Diagramma REL . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.4 Layout e diagramma REL . . . . . . . . . . . . . . . . . . . . 17

2.5 Grafo planare . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.6 Grafi non-planari . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.7 Facce di un grafo planare . . . . . . . . . . . . . . . . . . . . . 18

2.8 Duale di un grafo planare . . . . . . . . . . . . . . . . . . . . 19

2.9 Diverse rappresentazioni planari . . . . . . . . . . . . . . . . . 20

2.10 Layout su singola linea . . . . . . . . . . . . . . . . . . . . . . 22

2.11 Facility ben approssimabili . . . . . . . . . . . . . . . . . . . . 22

2.12 Facility poco approssimabili . . . . . . . . . . . . . . . . . . . 23

2.13 Parametri e variabili decisionali nel FL su singola linea . . . . 23

2.14 Esempio di layout a linea singola . . . . . . . . . . . . . . . . 24

2.15 Parametri e variabili decisionali negli ABSMODEL 2 . . . . . 25

3.1 Configurazioni per la movimentazione dei materiali . . . . . . 28

4.1 Flussi tra celle disgiunte . . . . . . . . . . . . . . . . . . . . . 38

4.2 Flussi tra celle confinanti . . . . . . . . . . . . . . . . . . . . . 39

4.3 Flussi tra vertici di frontiera . . . . . . . . . . . . . . . . . . . 41

4.4 Andamento della f.o. in un TS . . . . . . . . . . . . . . . . . . 44

4.5 Esempio d XOR su celle . . . . . . . . . . . . . . . . . . . . . 57

4.6 Layout non servibile con un unico loop . . . . . . . . . . . . . 57

3

ELENCO DELLE FIGURE 4

A.1 Layout 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

A.2 Layout 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

Elenco delle tabelle

2.1 ABSMODEL 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.2 ABSMODEL 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.1 Formulazione MILP . . . . . . . . . . . . . . . . . . . . . . . . 35

4.3 Riepilogo esperimenti . . . . . . . . . . . . . . . . . . . . . . . 64

4.4 Risultati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

5

Capitolo 1

I problemi di Facility Design

1.1 Introduzione

Per ”Facility” si puo generalmente intendere un edificio in cui persone, ma-

teriali e macchinari sono ospitati per un determinato scopo - tipicamente la

realizzazione di un prodotto o la fornitura di un servizio ([12]). Nel settore

manifatturiero, ad esempio, facility possono essere macchinari, workstation,

postazioni di lavaggio, zone di riposo, postazioni per le misurazioni e cosı

via; nella fornitura di servizi, invece, esempi di facility possono essere uffici,

corridoi, zone di riposo etc.

Una gestione efficiente delle facility puo permettere di perseguire diversi

obiettivi, quali:

• realizzare un prodotto o fornire un servizio ad un costo piu basso;

• migliorare la qualita del prodotto o del servizio;

• impiegare una minor quantita di materie prime.

Spesso gli obiettivi da raggiungere sono contrastanti ed e fondamentale capire

a fondo le complesse problematiche che vi sottostanno per compiere scelte

efficaci.

Un aspetto fondamentale nella gestione delle facility e il posizionamento

fisico degli stessi. Per posizionamento fisico si intende l’assegnamento di ogni

6

CAPITOLO 1. I PROBLEMI DI FACILITY DESIGN 7

facility ad una determinata area. Una disposizione fisica che riduca il movi-

mento di personale e materiali, ad esempio, puo permettere un miglioramento

delle prestazioni del sistema dovuto alla riduzione dei costi sostenuti per la

movimentazione dei materiali. I problemi correlati al posizionamento fisico

delle facility sono inquadrati in letteratura sotto il nome di Facility Layout

Problems.

Una tipologia specifica di facility merita un’attenzione particolare a causa

dell’elevata influenza che ha sui costi complessivi di gestione: e la classe dei

sistemi per la movimentazione dei materiali (Material Handling Systems -

MHS ). Studi sui sistemi manifatturieri hanno mostrato come una percentuale

variabile tra il 30 e il 75% del costo di un prodotto sia da attribuire a spese

per la movimentazione dei materiali ([21]). I problemi relativi alla movi-

mentazione dei materiali sono noti in letteratura come Material Handling

Problems.

1.2 Struttura del lavoro di tesi

Il lavoro di tesi affronta le complesse problematiche relative al FD fornendo

un approfondito studio dello stato dell’arte; viene quindi proposto un con-

tributo originale e migliorativo dello stato dell’arte in un particolare ambito

applicativo. La tesi si articola quindi in due parti:

• analisi delle diverse problematiche inerenti al FD, con approfondita

rassegna dello stato dell’arte;

• analisi di uno specifico problema e realizzazione di un contributo inno-

vativo sia teorico che applicativo.

Primo obiettivo del presente lavoro e, dunque, fornire una rassegna dettagli-

ata ed aggiornata delle diverse problematiche inerenti al FD reperibili in

letteratura. Tali problematiche sono tradizionalmente classificate in:

• problemi di Facility Layout - FL

• problemi di Material Handling - MH

CAPITOLO 1. I PROBLEMI DI FACILITY DESIGN 8

Il capitolo 2 presenta una vasta e approfondita panoramica sui problemi di

FL, mentre il capitolo 3 illustra lo stato dell’arte nell’ambito del MH.

La seconda parte della tesi tratta un particolare problema nell’ambito del

MH: la progettazione di un sistema di movimentazione dei materiali basato

su veicoli a controllo automatico (Automatic Guided Vehicles - AGV ) dis-

posti su di un circuito unidirezionale (Single Loop Design Problem - SLDP).

Questa particolare configurazione presenta numerosi vantaggi sia in termini

di gestione e controllo che in termini economici. Essa e stata tradizional-

mente trattata in letteratura esclusivamente con metodi euristici ovvero con

metodi esatti ma in varianti semplificate. Un recente lavoro ha iniziato ad

affrontare la problematica nella sua interezza, considerando come obiettivo

l’ottimizzazione dei costi complessivi legati alla movimentazione dei mate-

riali, riuscendo pero a fornire strumenti validi solo per la progettazione di

impianti di piccola dimensione.

Il lavoro di tesi si propone di migliorare lo stato dell’arte proponendo

una trattazione del caso in termini di problema di programmazione lineare

mista (Mixed Integer Linear Programming - MILP) con una formulazione

alternativa a quella recentemente introdotta. Viene quindi proposto un ap-

proccio risolutivo esatto di tipo Branch and Cut che, sfruttando la nuova

formulazione, consente la risoluzione di istanze del problema di medie di-

mensioni. Viene, quindi, proposto un metodo risolutivo euristico basato sul

Tabu Search che permette la risoluzione di istanze del problema di grandi di-

mensioni. La validita dell’euristica prodotta viene provata tramite confronto

con i risultati ottenuti utilizzando l’algoritmo esatto nei casi di piccola e me-

dia dimensione. Infine, l’euristica realizzata viene impiegata per determinare

una buona soluzione iniziale in un algoritmo branch and cut, che permette

di ridurre ulteriormente i tempi computazionali nella risoluzione ottima del

problema.

Capitolo 2

Problemi di Facility Layout

I problemi collegati alla progettazione degli impianti manifatturieri non si

incontrano esclusivamente in fase di realizzazione di un nuovo impianto pro-

duttivo, ma anche quando si ha la necessita di espandere o reingegnerizzare

strutture gia esistenti. Anche ditte che operano in un determinato settore

da anni hanno bisogno di rinnovare periodicamente i loro impianti ([18]). La

frequenza con cui si sono avuti cambiamenti nei layout aziendali e aumentata

nelle ultime decadi a causa dei cambiamenti nei product mix che sono ac-

caduti molto piu frequentemente negli ultimi anni rispetto al passato. Questo

trend e stato favorito anche da una maggiore attitudine dei clienti a cambiare

le richieste in termini sia di prodotti che di funzionalita degli stessi.

I problemi di FL in ambito manifatturiero coinvolgono il posizionamento

di macchinari, postazioni di lavoro ed altre facility con lo scopo di perseguire

i seguenti obiettivi:

• minimizzare i costi per il trasporto di materie prime, parti, utensili,

pezzi semilavorati e prodotti finiti tra le facility;

• agevolare il traffico interno;

• minimizzare i rischi di danni a persone e/o ad ogetti

Una distinzione che spesso viene fatta nell’ambito dei problemi di FL e quella

tra problemi di Layout Design e problemi di Facility Location, caratterizzan-

9

CAPITOLO 2. PROBLEMI DI FACILITY LAYOUT 10

do i primi come problemi di progettazione, mentre i secondi come proble-

mi di ottimizzazione: questo comporterebbe l’impossibilita di ottenere una

soluzione ottima nel primo caso. In realta, entrambi i tipi di problemi con-

tengono sia elementi progettuali che di ottimizzazione; conseguentemente,

nessuna delle due tipologie di problemi puo essere interamente classificata in

una o nell’altra categoria. Un approccio risolutivo tipico, infatti, comprende

due fasi successive:

• la determinazione di un certo numero di soluzioni ottime, ognuna sec-

ondo una determinata serie di parametri;

• la selezione di una delle soluzioni sulla base di criteri qualitativi, non

esprimibili in termini matematici.

In letteratura esistono numerosi lavori nel settore del FL. I diversi approc-

ci possono essere distinti in due gruppi: quelli che privilegiano l’aspetto

progettuale e quelli che mettono in risalto, al contrario, l’aspetto modellistico.

2.1 Systematic Layout Planning

Il Systematic Layout Planning - SLP e una delle piu diffuse metodologie per

la progettazione di impianti. La sua introduzione risale agli anni 70 ([17]),

ma e tuttora alla base di numerosi pacchetti software commerciali per il FL.

Uno dei motivi del successo di questa tecnica e il suo semplice approccio

graduale al problema. Il SLP si articola, infatti, in una sequenza di passi.

1. Determinazione delle aree entro cui vanno posizionate le facility. E’

la fase piu semplice e consiste nell’individuazione delle diverse opzioni

possibili per il posizionamento di ciascuna facility.

2. Schema generale del layout. Questa fase consiste nell’individuazione

dei flussi di materiali tra le diverse facility, nella determinazione di

eventuali vincoli di adiacenza e nel calcolo dello spazio richiesto da

ogni facility.


3. Schema di dettaglio del layout. Mentre la fase 2 considera soltan-

to le facility principali (tipicamente i reparti), e compito di questa

fase la definizione dei dettagli riguardanti le facility di supporto, quali

macchinari specifici, strumentazione di supporto, zone di riposo etc.

4. Verifica del layout prodotto. Il layout di dettaglio realizzato nella fase

3 deve passare la verifica di tutte le figure professionali coinvolte nel’u-

tilizzo dello stesso: impiegati, personale di servizio, dirigenti. Viene

quindi realizzato e installato il layout definitivo.

Le fasi 1 e 4 sono di immediata realizzazione e non richiedono particolari

considerazioni teoriche o tecniche. Le fasi 2 e 3 richiedono, invece, una trat-

tazione approfondita per poter ottenere una formalizzazione di due aspetti

particolarmente importanti nella progettazione del layout:

• la quantificazione dei flussi tra le diverse facility;

• l’individuazione delle relazioni che esistono tra le facility.

2.1.1 Misurazione dei flussi (Diagrammi From-To)

Per prima cosa e necessario determinare la quantita di materiali che tran-

sitano tra i diversi reparti. I dati necessari per questa fase possono essere

ricavati da documenti relativi ai processi aziendali quali:

• fatture relative ai materiali acquistati;

• cicli di lavorazione;

• diagramma di produzione/assemblaggio;

• diagrammi delle precedenze.

Dati sui volumi di produzione possono essere ricavati in base alle previsioni

di vendita/produzione. Combinando i dati relativi ai processi aziendali con

quelli relativi ai volumi di produzione previsti e possibile determinare il flusso

complessivo di materiali tra le diverse facility.


Per rappresentare i flussi previsti tra i reparti si impiega una matrice

from-to o matrice dei flussi. La matrice from-to e una matrice quadrata

con numero di righe (e colonne) pari al numero di facility del problema.

L’elemento (i, j) della matrice rappresenta la quantita di materiali previsti

dalla facility i alla facility j. In questa fase, non vengono esaminati i flussi di

materiali all’interno di una facility, quindi la diagonale della matrice from-to

contiene tutti elementi nulli.

Per assicurare una corretta normalizzazione dei flussi di materiali vengono

utilizzati flussi volume-equivalenti di materiali. Si supponga, ad esempio, che

dalla facility 1 alla facility 2 debbano essere movimentati 1000 pezzi di tipo

X, mentre dalla facility 3 alla facility 4 ne vadano movimentati 100 di tipo

Y ; se i pezzi di tipo Y sono 100 volte piu pesanti di quelli di tipo X, allora i

corrispondenti elementi nella matrice from-to saranno (1, 2) = 1 e (3, 4) = 10.

Per calcolare i flussi volume-equivalenti si puo considerare il peso, come nell’e-

sempio, ovvero l’unita di trasporto del materiale, che puo essere, ad esempio,

un pallet, uno scatolo, un barile, etc. Nel caso in cui la movimentazione di

determinati materiali sia pericolosa o necesi attenzioni particolari, il flusso

volume-equivalente ad essi relativo puo essere opportunamente maggiorato

in base a questi fattori.

Il flusso totale tra due facility viene calcolato come la somma dei flussi

volume-equivalenti di tutti i materiali tra le due facility. In base ai dati sui

processi aziendali, ogni parte da produrre viene esaminata per determinare

attraverso quali facility deve transitare. Una stima della quantita di parti

da realizzare viene invece effettuata sulla base delle previsioni. Si procede

quindi alla costruzione della matrice from-to dopo il calcolo dei flussi volumi-

equivalenti tra ogni coppia di facility.

La matrice from-to per un impianto organizzato come singola linea di

produzione, ad esempio, avra tutti elementi nulli tranne quelli al di sopra

della diagonale (Figura 2.1a). Questa struttura (nota come matrice di Hes-

senberg nella terminologia dell’algebra lineare) si puo presentare soltanto se

le facility sono ordinate secondo il ciclo di lavorazione. Se non si ha una lin-

ea di produzione singola, solitamente si individua per ogni facility un flusso

predominante e si ordinano le facility in base a valori decrescenti dei flussi


1 2 3 41 0 X 0 02 0 0 X 03 0 0 0 X4 0 0 0 0

1 2 3 41 0 X X X2 0 0 X X3 0 0 0 X4 0 0 0 0

a b

1 2 3 41 0 0 X 02 0 0 0 X3 0 X 0 04 0 0 0 0

1 2 3 41 0 X X X2 0 0 0 X3 X 0 0 X4 0 0 X 0

c d

Figura 2.1: Matrici From-To

dominanti individuati. I flussi al di sopra della diagonale principale sono

flussi ordinati, mentre quelli al di sotto sono flussi di ritorno. La presenza

di flussi di ritorno normalmente rende piu complicata la progettazione del

layout. La figura 2.1b e un esempio di matrice con soli flussi ordinati, mentre

le figure 2.1c e 2.1d sono esempi di matrici from-to generiche.

Per determinare quale tra due ordinamenti delle facility da una matrice

from-to piu appetibile, e possibile calcolare il momento µ della matrice:

µ =∑(i,j)

dijfij

in cui:

• dij e la distanza dell’elemento (i, j) dalla diagonale;

• fij e il valore dell’elemento (i, j) nella matrice.

Ad esempio, si considerino le due versioni della stessa matrice from-to, cor-

rispondenti a diversi ordinamenti delle facility, riportate in figura 2.2. I

momenti relativi sono dati da:

µa = 2 · 1 + 5 · 2 + 1 · 2 + 4 · 1 + 2 · 1 = 20

µb = 5 · 1 + 2 · 3 + 4 · 1 + 2 · 2 + 1 · 1 = 18


1 2 3 41 0 2 5 02 0 0 0 13 0 2 0 44 0 0 0 0

1 2 3 41 0 5 0 22 0 0 4 23 0 0 0 04 0 0 1 0

a b

Figura 2.2: Confronto tra matrici from-to

Pertanto, la matrice in figura 2.2b e da preferire a quella in figura 2.2a. Il

momento di una matrice viene spesso modificato per tener conto dell’impor-

tanza dei flussi di ritorno. A questo scopo, spesso, nel calcolo del momento,

si da un peso maggiore ai flussi di ritorno. Nell’esempio considerato, se si

moltiplicano i flussi di ritorno per un fattore 10, si ottengono rispettivamente

i valori 38 e 27 (confermando la maggiore appetibilita della matrice b).

2.1.2 Analisi Attivita/Relazioni (Diagrammi REL)

Le matrici dei flussi caratterizzano una parte essenziale del problema di lay-

out; esistono, tuttavia, altri aspetti che possono essere altrettanto importanti

ma che non sono quantificabili. Esempi tipici di questi fattori possono essere

considerazioni sull’estetica e sulla sicurezza, preferenze personali, necessita di

supervisione e controllo. Queste informazioni qualitative vanno integrate con

quelle quantitative fornite dalla matrice dei flussi al fine di dare un giudizio

sulla possibilita/necessita di avere determinate facility vicine tra loro. Uno

strumento che si utilizza per questo tipo di analisi sono i diagrammi REL

(RELationship charts).

Il diagramma REL rappresenta l’importanza che due facility siano adia-

centi sulla base di una scala a sei valori:

A assolutamente necessario;

E di importanza speciale;

I importante;


Figura 2.3: Diagramma REL

O di importanza ordinaria;

U ininfluente;

X non desiderabile.

E’ compito dell’analista classificare ogni coppia di facility in base a questa

scala di valori. Il diagramma REL viene rappresentato solitamente attraverso

una tabella come quella riportata in figura 2.3. Ogni rombo rappresenta la

relazione esistente tra due facility: la meta superiore indica la classificazione

in base alla scala introdotta, mentre la parte inferiore e usata per fornire la

motivazione della classificazione fatta. Viene anche fornita una legenda delle

motivazioni.

2.1.3 Progettazione del layout fisico

I diagrammi REL possono essere impiegati nella progettazione del layout

per determinare le adiacenze tra le diverse facility. Se la movimentazione dei

materiali o se le necessita di controllo e supervisione sono ritenute strategiche,

allora una classificazione elevata di due facility nel diagramma REL porta ad

una localizzazione adiacente nel layout fisico delle due facility. La forma e

le dimensioni delle facility limitano, ovviamente, il numero di facility che


possono essere adiacenti. Uno dei primi passi nella progettazione effettiva

del layout consiste proprio nella determinazione delle adiacenze tra le diverse

facility.

L’approccio tradizionalmente utilizzato consiste nell’approssimare le facil-

ity mediante quadrati. Questi vengono fatti muovere su una griglia e vengono

collegati tramite linee il cui spessore rappresenta la classificazione relativa

all’adiacenza tra le due facility connesse. I quadrati vengono spostati man-

ualmente sulla griglia fino a raggiungere un layout ritenuto soddisfacente dal

punto di vista delle adiacenze. Ovviamente questo metodo presenta numerosi

svantaggi:

• e molto legato all’abilita del progettista;

• e completamente soggettivo;

• diventa ingestibile se le facility presenti sono numerose.

Un approccio piu flessibile e quantitativo impiega i diagrammi REL e la

teoria dei grafi. Ogni facility e rappresentata in un grafo come un vertice. Se

due facility sono adiacenti, allora i vertici corrispondenti sono collegati da un

arco. Nell’esempio in figura 2.4, il layout e costituito dalle facility A, B, C,

D ed E e da una facility esterna F. Associando ad ogni facility un vertice e

ad ogni coppia di celle adiacenti l’arco tra i corrispondenti vertici, si ottiene

il diagramma REL associato al layout.

Si noti che il diagramma REL in figura 2.4 e disegnato in modo che nessun

arco del grafo si intersechi. Questa e una proprieta importante del grafo di

REL: comunque sia dato un layout, il grafo di REL corrispondente gode di

questa proprieta. I grafi in cui gli archi possono essere disegnati in modo da

non avere intersezioni prendono il nome di grafi planari. Nella progettazione

del layout, dunque, si e interssati soltanto ai grafi planari, in quanto sono gli

unici a cui e possibile asre un layout.

Ogni grafo planare puo essere ridisegnato in modo da non avere archi che

si intersecano. In figura 2.5 e riportato un esempio di grafo planare disegnato

con archi che si intersecano e riportato in forma planare.


Figura 2.4: Layout e diagramma REL

Figura 2.5: Grafo planare


Figura 2.6: Grafi non-planari

Figura 2.7: Facce di un grafo planare

Se un grafo non puo essere ridisegnato in forma planare, allora viene

definito grafo non-planare. Due esempi di grafi non-planari sono riportati in

figura 2.6. I due esempi riportati sono grafi particolari, denominati rispetti-

vamente K5 e K3,3; si puo dimostrare che un grafo e non-planare se e solo se

una versione di uno di questi due grafi vi e contenuta (teorema di Kurtowski).

Un grafo planare suddivide il piano in un insieme di regioni chiamate facce.

Una e solo una di queste facce non e limitata e viene detta faccia esteriore.

Tutte le altre facce sono delimitate dagli archi del grafo planare. In figura

2.7 e riportato il grafo planare della figura 2.4 con l’aggiunta dell’indicazione

delle facce da a ad h. Si noti che h e la faccia esterna.


Figura 2.8: Duale di un grafo planare

Dato un grafo planare G, si denoti con G∗ il suo duale. Il duale di un

grafo planare viene definito creando un vertice per ciascuna faccia del grafo

di origine; due vertici di G∗ sono collegati da un arco se le corrispondenti

facce in G sono separate da un arco. In figura 2.8 e riportato il grafo planare

della figura 2.4 insieme al suo duale.

Il grafo duale G∗ di un grafo planare G e a sua volta un grafo planare.

E’ facilmente verificabile che il duale di G∗ e G. Si noti anche che il numero

di facce di G∗ e pari al numero di vertici di G. Poiche ogni vertice di G

rappresenta una facility, ogni faccia di G∗ rappresenta una facility: si puo

quindi usare ogni faccia per rappresentare una facility nel layout.

E’ importante notare che un grafo planare puo essere disegnato in maniera

planare in diversi modi. A seconda della rappresentazione utiliz, il duale

corrispondente puo essere anche molto diverso. In figura 2.9 e riportato

un esempio di due diverse rappresentazioni planari di uno stesso grafo, a cui

corrispondono grafi duali molto differenti. Si noti, in particolare, che il vertice

che rappresenta la faccia esterna ha, nel primo duale, 5 archi incidenti (vertice

di grado 5 secondo la terminologia della teoria dei grafi); nel secondo duale,

al contrario, nessun vertice ha grado 5. Non e, quindi, possibile ottenere

un duale dall’altro semplicemente ridisegnando il grafo. Questa peculiarita

permette di ottenere layout alternativi a partire da un medesimo diagramma


Figura 2.9: Diverse rappresentazioni planari

REL.

L’utilizzo dei diagrammi REL per progettare il layout e uno strumento

molto potente. Tuttavia, creare un buon grafo a partire dal diagramma REL

e un problema di non semplice soluzione. Tra le diverse tecniche euristiche

esistenti in letteratura per la soluzione di questo problema, una delle piu

utilizzate in ambito industriale e la tecnica del Deltaedro, descritta in [6].

2.2 Modelli matematici per i problemi di FL

Nella progettazione di un layout e necessario tener conto di numerosi aspet-

ti; l’obiettivo principale, comunque, consiste nella minimizzazione dei costi

relativi al trasporto di pezzi semi-lavorati, prodotti finiti, materie prime

e utensili. Per poter perseguire questo obiettivo e necessario fornire una

formulazione matematica del problema, per la cui soluzione e poi richiesta

l’implementazione di un algoritmo risolutivo opportuno.


Dal punto di vista della modellazione matematica, il problema di FL puo

essere classificato in due distinte tipologie:

• problema di layout su singola linea;

• problema di layout multi-linea.

Nel problema a singola linea, le facility sono disposte lungo un asse, men-

tre nei problemi multi-linea sono disposti su di una superficie bidimensionale

(non necesariamente su piu linee). Un semplice esempio di problema su sin-

gola linea puo consistere nell’assegnamento degli aerei in arrivo ai diversi gate

in un aereoporto. Tipicamente, un aereo che arriva in aereoporto trasporta

sia passeggeri per i quali l’aereoporto considerato e la destinazione finale, sia

passeggeri in transito verso altre destinazioni. Nell’arco di poche ore, molti

aerei possono atterrare nell’aereoporto. E’ necessario, quindi, minimizzare la

distanza complessiva che i passeggeri devono coprire, a piedi, nell’aereoporto

(al fine, ad esempio, di ridurre i disagi per i passeggeri stessi), cercando di

assegnare a gate adiacenti voli con forte interazione.

2.2.1 QAP

sddas

2.2.2 ABSMODEL

ABSMODEL 1

Il modello ABSMODEL 1 sono una formalizzazione del problema di FL

su singola-linea tramite un modello non lineare, ma linearizzabile medi-

ante l’introduzione di variabili ausiliarie intere. Vengono fatte le seguenti

assunzioni:

1. le facility sono quadrate o rettangolari e la loro forma e nota a priori ;

2. le facility devono essere posizionate lungo una linea retta, come illus-

trato in figura 2.10;


Figura 2.10: Layout su singola linea

Figura 2.11: Facility ben approssimabili

3. l’orientamento delle facility e fissato a priori ;

4. non ci sono limitazioni sulla forma e sulle dimensioni dell’edificio che

deve contenere le facility.

L’ipotesi 1 puo sembrare particolarmente restrittiva. Occorre, tuttavia,

osservare che qualsiasi forma abbia una facility, questa puo essere approssima-

ta tramite il piu piccolo rettangolo che la contiene. Questa approssimazione

puo incidere sulla qualita della soluzione ottenuta in maniera trascurabile,

nei casi come quelli in figura 2.11, o in maniera rilevante, nei casi come quelli

riportati in figura 2.12. Fortunatamente, i casi reali in cui le facility assumono

forme come quelle in figura 2.12 sono piuttosto rari.


Figura 2.12: Facility poco approssimabili

Figura 2.13: Parametri e variabili decisionali nel FL su singola linea

L’ipotesi 2 e alla base di qualsiasi problema di FL su singola linea.

L’orientamento di una facility rettangolare indica se e il lato lungo oppure

il lato corto a dover essere lungo la linea del layout. In molti sistemi mani-

fatturieri, i macchinari devono essre posizionati in modo tale che i punti di

carico/scarico si trovino tutti lungo la linea del layout. Poiche questi punti

di carico/scarico sono fissi per ciascun macchinario, l’ipotesi 3 e facilmente

rispettata.

L’applicabilita dell’ipotesi 4 dipende, chiaramente, dal singolo problema

in esame.

I parametri che caratterizzano un ABSMODEL 1 sono i seguenti:

n numero di facility da posizionare;

cij costo per la movimentazione di una unita volume-equivalente di

materiale di una unita di distanza tra la facility i e la facility j;

fij numero di viaggi tra i e j;

li lunghezza del lato della facility i da posizionare sulla linea del

layout;

dij distanza minima tra le facility i e j lungo la linea;

H dimensione orizzontale complessiva del layout.

Le variabili decisionali sono le seguenti:

xi distanza tra il centro della facility i e la linea di riferimento

verticale (VRL - Vertical Reference Line)

Un riepilogo visivo dei parametri e delle variabili decisionali che caratteriz-

zano il problema e presentato nella figura 2.13.


minn−1∑i=1

n∑j=i+1

cij · fij · |xi − xj| (2.1)

s.v.

|xi − xj| ≥1

2(li + lj) + dij i = 1, 2, . . . , n− 1 j = i + 1, . . . , n (2.2)

Tabella 2.1: ABSMODEL 1

Figura 2.14: Esempio di layout a linea singola

Il modello ABSMODEL 1 e riportato in tabella 2.1. La funzione obiettivo

??, da minimizzare, rappresenta il costo complessivo dovuto alle movimen-

tazioni tra le facility. Il set di vincoli ?? assicura la non sovrapposizione delle

facility.

La non negativita delle variabili non e indispensabile, ma si puo ag-

giungere come vincolo andando ad influenzare solamente la posizione del

riferimento VRL.

In accordo con l’ipotesi fatta sul non porre limitazioni sull’area comp-

lessivamente occupata dalle facility, non e presente alcun vincolo che sfrutti

il parametro H. Essendo, infatti, posto a minimizzare il costo complessivo

dovuto alle movimentazioni, le facility risulteranno il piu vicino possibile.

Se si vuole, viceversa, imporre comunque un limite, cio puo essere ottenuto

tramite il set di vincoli aggiuntivi ??:

H − 1

2li ≥ xi ≥

1

2li i = 1, 2, . . . , n (2.3)

Poiche xi si riferisce alla distanza tra il centroide della facility i e il rifer-

imento VRL, il vincolo ?? sara soddisfatto anche se la facility si trova al-

l’estrema destra o all’estrema sinistra del layout. Si esamini la figura 2.14. Si

noti che il vincolo ?? assicura che il riferimento VRL coincida col lato sinistro

della facility all’estrema sinistra del layout.

La formulazione degli ABSMODEL 1 non e lineare a causa della presen-

za dei valori assoluti. I problemi di FL su singola linea non sono, quindi,

risolvibili con gli algoritmi classici della programmazione lineare. Esistono,


Figura 2.15: Parametri e variabili decisionali negli ABSMODEL 2

minn−1∑i=1

n∑j=i+1

cij · fij · (|xi − xj|+ |yi − yj|) (2.4)

s.v.

|xi − xj|+ |yi − yj| ≥ 1 i = 1, 2, . . . , n− 1 j = i + 1, . . . , n (2.5)

xi, yi ∈ N i = 1, 2, . . . , n (2.6)

Tabella 2.2: ABSMODEL 2

tuttavia, diverse euristiche, implementate anche in software commerciali, che

permettono una soluzione sub-ottima ma efficiente di questo tipo di problemi.

ABSMODEL 2

Le ipotesi alla base dei modelli ABSMODEL 1 obbligano a trattare layout su

singola linea. Nel caso in cui il layout da progettare sia del tipo multilinea,

con celle quadrate e di uguale dimensione, in alternativa all’approccio QAP

introdotto in ??, possono essere impiegati i modelli ABSMODEL 2. Questi

modelli estendono la trattazione fatta per gli ABSMODEL 1 considerando le

seguenti variabili decisionali:

xi distanza orizzontale tra il centro della facility i ed il riferimento

verticale (Vertical Reference Line - VRL);

yi distanza verticale tra il centro della facility i ed il riferimento

oriztale (Horizontal Reference Line - HRL).

Il riepilogo dei parametri e delle variabili decisionali coinvolti nel problema e

riportato in figura 2.15. Il modello matematico e invece riportato in tabella

2.2.

Si suppone che non vi sia spazio vuoto (clearance) tra le facility e che ogni

facility abbia area unitaria, e quindi che i lati di ciascuna facility abbiano

lunghezza unitaria. Poiche si suppone che le facility siano tutte quadrate e


con medesime dimensioni, quest’ultima ipotesi non lede la generalita della

trattazione.

I vincoli ?? e ?? assicurano che le facility non si sovrapngano. Il vincolo

di integrita ?? non e imposto per garantire l’integrita delle variabili, bensı

per evitare la sovrapposizione delle facility. Si consideri, ad esempio, una

soluzione ammissibile rilasciando il set di vincoli ?? che abbia i seguenti

valori: xi = 0, 5, xj = 0, yi = 0.5 ed yj = 0. Questa soluzione soddisfa i

vincoli ??, ma provoca la sovrapposizione delle celle i e j. Imponendo anche

i vincoli di interezza, tali situazioni di sovrapposizione vengono evitate.

Anche nel caso degli ABSMODEL 2, come negli ABSMODEL 1, con-

siderando H e V rispettivamente come la dimensione orizzontale e verticale

massime del layout, e possibile introdurre ulteriori vincoli sull’area comp-

lessivamente utilizzabile dal layout:

H ≥ xi ≥ 1 i = 1, 2, . . . , n

V ≥ yi ≥ 1 i = 1, 2, . . . , n

ABSMODEL 3

Gli ABSMODEL 3 costituiscono la generalizzazione degli ABSMODEL 2 al

caso in cui le facility non siano necessariamente quadrate e di uguale dimen-

sione. Negli ABSMODEL 3 si assume che le facility siano di forma rettango-

lare, aree in generale diverse, orientamento noto a priori. Per le ipotesi fatte

su forma e orientamento delle facility, valgono le stesse considerazioni fatte

nella sezione sugli ABSMODEL 1.

Capitolo 3

Problemi di Material Handling

La progettazione dei sistemi di movimentazione dei materiali e una delle

attivita principali nell’ambito piu ampio della progettazione di layout per

impianti industriali. In [2] viene messo in evidenza quanto sia fondamentale

affrontare le problematiche relative ai sistemi di movimentazione gia nella

progettazione del layout. In [24] si stima che, in ambito manifatturiero,

una quantita variabile tra il 20% ed il 50% dei costi di produzione siano da

attribuire alla progettazione del layout e dei sistemi di movimentazione. E’,

dunque, estremamente importante riuscire ad effettuare efficacemente queste

attivita al fine di contenere i costi complessivi di produzione.

Le problematiche relative al material handling sono state esaminate ampia-

mente in letteratura: in particolare, si puo fare riferimento ai testi [7] per

una panoramica d’insieme sui problemi di MH e a [8] per lo stato dell’arte

nell’ambito dei sistemi di movimentazione basati su veicoli a guida automat-

ica. Un particolare rilievo e dato, sia in letteratura che nell’utilizzo aziendale

(come riportato in [1]), ai sistemi di movimentazione su loop: quei sistemi,

cioe, in cui i veicoli addetti alla movimentazione dei materiali si muovono

lungo una o piu traiettorie che formano un anello chiuso sul layout.

27

CAPITOLO 3. PROBLEMI DI MATERIAL HANDLING 28

Figura 3.1: Configurazioni per la movimentazione dei materiali

3.1 Topologie per il Material Handling

Esistono diverse configurazioni trattate in letteratura per la movimentazione

dei materiali. Le quattro diverse topologie base sono le seguenti:

• rete convenzionale unidirezionale (figura 3.1a): introdotta da [16], con-

siste in una rete unidirezionale che copre tutti gli spigoli del layout;

• loop unidirezionale (figura 3.1b): esaminata in [22], permette una ges-

tione semplificata delle collisioni tra i veicoli, che puo risultare co-

munque complicata se il numero di veicoli richiesti e elevato;

• configurazione tandem (figura 3.1c): introdotta in [5], consiste nella

scomposizione della rete di flussi di materiali in piu sottoreti, ciascuna

servita da un unico veicolo che circola su di un loop, collegate tramite

punti di trasbordo;

• loop segmentato (figura 3.1a): esaminato in [20], consiste in una config-

urazione loop“spezzato” su diverse tratte, ognuna servita da un singolo

veicolo.

3.2 Stato dell’arte nelle configurazioni basate

su loop

Tra le diverse configurazioni esistenti, quelle basate su loop sono quelle mag-

giormente trattate in letteratura, sia a causa del loro ampio utilizzo in ambito

industriale sia per la loro difficolta di trattazione in fase di progettazione. Le

reti convenzionali, infatti, comportano uno sforzo quasi nullo in fase di pro-

gettazione, mentre richiedono un’attenzione maggiore in fase di gestione, a

causa delle difficolta legate alle collisioni e quindi allo scheduling dei viag.

Le problematiche relative alla progettazione dei sistemi di movimentazione

basati su loop sono esaminate e riassunte nelle sezioni che seguono.

CAPITOLO 3. PROBLEMI DI MATERIAL HANDLING 29

3.2.1 Sequenziamento dei punti di P/D

Un problema importante nella progettazione di sistemi di movimentazione

dei materiali basati su loop e la localizzazione relativa delle stazioni combi-

nate di carico/scarico (o punti di P/D - Pickup/Delivery), assegnati i flussi

previsti tra le facility (le matrici from-to esaminate nella sezione 2.1.1). In

particolare, in questo tipo di problemi, si assume che tutti i carichi di ma-

teriali in ingresso al sistema entrino tramite una stazione specializzata (la

stazione 0). L’obiettivo e la minimizzazione del numero di volte che ciascun

carico transita attraverso la stazione 0 prima di uscire dal sistema.

In questo tipo di problemi, la forma, l’orientamento e la dimensione delle

celle non viene preso in considerazione. Ogni facility e rappresentata sem-

plicemente da un nodo. Il problema cosı posto, noto in letteratura come SSP

- Station Sequencing Problem, e stato introdotto in [1] ed e stato dimostrato

essere NP-hard in [15]. E’ stata anche data una formulazione dell’SSP come

caso particolare del problema di assegnamento quadratico (QAP) in [14],

mentre in [23] e stata proposta una procedura euristica di post-ottimizzazione

basata sugli scambi.

3.2.2 Localizzazione delle celle

3.2.3 Progettazione di layout a loop singolo

3.2.4 Progettazione di configurazioni tandem

Capitolo 4

Single Loop Design Problem

(SLDP)

4.1 Introduzione e analisi della letteratura

Il problema relativo alla progettazione di un sistema di movimentazione dei

materiali basato su veicoli a guida automatica (AGV) che compiano una

traiettoria ad anello unidirezionale e noto in letteratura come Single Loop

Design Problem (SLDP).

La progettazione dei percorsi guida per gli AGV puo essere affrontata

in diversi modi a seconda delle ipotesi che vengono fatte. In particolare, le

principali differenze si hanno in base a:

1. Cosa si intende progettare:

(a) progettazione del layout dell’impianto, dei percorsi guida per gli

AGV e posizionamento dei punti di pickup-delivery;

(b) progettazione dei percorsi guida per gli AGV e posizionamento dei

punti di pickup-delivery dato il layout dell’impianto;

(c) progettazione dei percorsi guida per gli AGV dato il layout del-

l’impianto e data la posizione dei punti di pickup-delivery.

2. L’obiettivo da perseguire:

30

CAPITOLO 4. SINGLE LOOP DESIGN PROBLEM (SLDP) 31

(a) la minimizzazione del flusso di materiali nel sistema sulla base dei

flussi tra i diversi reparti;

(b) la minimizzazione dei tempi o delle distanze richiesti dagli AGV

per eseguire le consegne.

In [9] si suppone che il layout dell’impianto e la posizione dei punti di pickup-

delivery (P/D) siano noti. La determinazione del percorso guida per gli AGV

viene quindi formulato come un problema di programmazione lineare binaria.

In [25] si suppone assegnato il layout dell’impianto e viene proposta una

procedura per posizionare i punti di P/D. Tale procedura si articola in due

fasi: nella prima, viene impiegato il modello sviluppato in [9] per determinare

la direzione dei flussi; nella seconda, viene proposto un metodo euristico

per migliorare le prestazioni del sistema cambiando il posizionamento dei

punti di P/D. La procedura proposta e molto onerosa computazionalmente

col crescere del numero di reparti e, comunque, non fornisce la soluzione

ottima. Per poter ottenere l’ottimalita, infatti, e necessario considerare

contemporaneamente la progettazione dei percorsi guida per gli AGV e il

posizionamento dei punti di P/D.

In [13], vengono considerati assegnati il layout dell’impianto e la posizione

dei punti di P/D e viene proposta una formulazione del problema dell’individ-

uazione del percorso guida ottimo in termini di problema di programmazione

lineare binaria. La soluzione viene quindi determinata con un metodo di tipo

branch and bound.

La trattazione contemporanea della progettazione del percorso guida e

del posizionamento dei punti di P/D una volta noto il layout dell’impianto

viene affrontata per la prima volta in [22]. Viene proposta una procedura in

cinque fasi:

1. viene risolto un problema di programmazione lineare intera per deter-

minare un loop iniziale ammissibile (che comprenda, quindi, almeno

uno spigolo di ciascun reparto)

2. enumerazione completa dei loop ammissibili a partire dal loop iniziale


3. l’applicazione di tre regole permette di ridurre il numero dei loop am-

missibili da considerare nelle fasi successive

4. viene risolto un problema di programmazione lineare intera mista per

il posizionamento dei punti di P/D su un determinato loop

5. permette di determinare un lower bound sul valore di funzione obiettivo

di un determinato loop

Tecniche risolutive piu efficienti per la risoluzione dei modelli matematici

presenti nelle fasi 1 e 4 vengono introdotte in [19].

In [4] viene affrontata la progettazione dei percorsi guida per gli AGV

dato il layout dell’impianto con obiettivo la minimizzazione delle distanze

richieste dagli AGV per eseguire le consegne, non tenendo conto del flusso

effettivo dei materiali. Il problema consiste, quindi, nell’individuazione del

loop di lunghezza minima. Viene data una formulazione come problema di

programmazione lineare intera con un numero di vincoli inizialmente molto

elevato; vengono quindi proposti dei metodi per la riduzione dei vincoli effet-

tivamente richiesti e vengono forniti risultati computazionali che confermano

l’efficienza dell’approccio proposto.

Un’ipotesi di base nella trattazione del problema del SLDP e la coinciden-

za dei punti di P/D per ciascuna cella. Tale ipotesi discende da motivazioni

di tipo tecnico-pratiche. Questa ipotesi viene, tuttavia, rimossa nel recente

lavoro [3]. Viene fornita una formulazione del problema di tipo ILP che

determini contemporaneamente il percorso guida per gli AGV, comprensi-

vo di orientamento, e il posizionamento dei punti di P/D. L’obiettivo e la

minimizzazione del flusso di materiali nel sistema sulla base dei flussi tra i

diversi reparti. Il modello viene risolto impiegando l’algoritmo di branch and

bound implementato in un risolutore matematico standard, opportunamente

calibrato nelle strategie di branching e di selezione dei nodi da esplorare sfrut-

tando le caratteristiche del problema. Gli esperimenti condotti riguardano

layout con 11 e 20 celle e matrici di flusso sparse, caratterizzate da un numero

di flussi inferiore a 40, con risultati ottimi ottenuti sempre in meno di 1000

secondi.


Nel lavoro di tesi e stato affrontato il problema della progettazione dei

percorsi guida per gli AGV e del contemporaneo posizionamento dei punti di

pickup-delivery dato il layout dell’impianto. Obiettivo e la minimizzazione

del flusso di materiali nel sistema sulla base dei flussi tra i diversi reparti.

Le ipotesi fatte sono quelle riscontrate nella letteratura esaminata. In

particolare:

• il percorso guida e un loop unidirezionale che comprenda almeno uno

spigolo di ciascuna cella/reparto

• ogni reparto ha un unico punto di P/D, posizionato in uno dei vertici

della cella

Nessuna ipotesi viene fatta sulla forma e sulla dimensione di ogni cella, purche

sia possibile individuare, anche solo convenzionalmente, almeno un vertice

che possa ospitare il punto di P/D.

Viene proposta una formulazione come problema di programmazione lin-

eare intera mista. Il modello proposto permette di risolvere con l’algoritmo

branch and bound di un risolutore matematico standard, problemi di piccola

dimensione con matrice dei flussi tra i reparti densa e problemi di piccola e

media dimensione nei casi con matrice dei flussi sparsa. Viene quindi propos-

to un algoritmo di tipo branch and cut che permette di ridurre notevolmente

i tempi di elaborazione, permettendo di risolvere anche problemi di media

dimensione con matrice dei flussi densa. Per la risoluzione di problemi di

grandi dimensione, e stat implementata un’euristica di tipo Tabu Search. La

qualita dell’algoritmo proposto e stata verificata nella risoluzione dei proble-

mi di piccola e media dimensione risolti in maniera ottimale. Infine, e stato

realizzato un algoritmo esatto ”ibrido”, che utilizza l’euristica TS nell’ambito

dell’approccio branch and cut. Il metodo ibrido proposto permette di ridurre

ulteriormente i tempi computazionali richiesti per la risoluzione ottimale dei

problemi trattati.


4.2 Formulazione MILP

Il problema della progettazione dei percorsi guida per gli AGV e del con-

temporaneo posizionamento dei punti di pickup-delivery dato il layout del-

l’impianto puo essere efficacemente formulato come problema di program-

mazione lineare intera mista. Obiettivo e la minimizzazione del flusso di

materiali nel sistema sulla base dei flussi tra i diversi reparti. Parametri del

problema sono:

• il layout dell’impianto: il numero di celle, gli spigoli e i vertici di

ciascuna cella, la lunghezza degli spigoli

• la matrice dei flussi tra i reparti: i flussi previsti tra ciascuna coppia di

celle

Il problema e caratterizzato dalle seguenti informazioni:

C insieme dei reparti

E insieme degli spigoli del layout

V insieme dei vertici del layout

Φ insieme delle coppie di celle tra cui e previsto un flusso

Vc insieme dei vertici della cella c

EIi insieme degli spigoli entranti nel vertice i

EOi insieme degli spigoli uscenti dal vertice i

lij lunghezze degli spigoli

fcd flusso previsto di materiali dalla cella c verso la cella d, con (c, d) ∈ ΦUtilizzando la notazione introdotta, il problema puo essere formulato

come riportato in tabella 4.1.

Le variabili decisionali utilizzate sono raggruppabili in quattro insiemi:

• variabili reali che rappresentano la frazione di flusso diretto dalla cella

c verso la cella d che passa lungo lo spigolo (i, j);

• variabili binarie che indicano se lo spigolo (i, j) fa parte del loop;

• variabili binarie che indicano se il vertice i fa parte del loop;


min∑

(i,j)∈E

∑(c,d)∈Φ

lij · fcd · xijcd (4.1)

s.v.

yij + yji ≤ 1 ∀(i, j) ∈ E (4.2)∑(i,j)∈Ec

yij ≥ 1 ∀c ∈ C (4.3)

∑i∈Vc

zci = 1 ∀c ∈ C (4.4)

zci ≤ zi ∀c ∈ C, ∀i ∈ Vc (4.5)∑(i,j)∈EO

i

yij +∑

(j,i)∈EIi

yji ≥ zci ∀c ∈ C, ∀i ∈ Vc (4.6)

∑(j,i)∈EI

i

yji ≤ 1 ∀i ∈ V (4.7)

∑(i,j)∈EO

i

yij ≤ 1 ∀i ∈ V (4.8)

∑(j,i)∈EI

i

yji ≥ zi ∀i ∈ V (4.9)

∑(i,j)∈EO

i

yij ≥ zi ∀i ∈ V (4.10)

zi + zj ≥ 2 · yij ∀(i, j) ∈ E (4.11)∑(i,j)∈EO

i

xijcd −∑

(j,i)∈EIi

xjicd = zci − zdi ∀(c, d) ∈ Φ, ∀i ∈ V (4.12)

∑(c,d)∈Φ

xijcd ≤ |Φ| · yij ∀(i, j) ∈ E (4.13)

xijcd ∈ [0, 1] ∀(i, j) ∈ E, ∀(c, d) ∈ Φ (4.14)

yij ∈ 0, 1 ∀(i, j) ∈ E (4.15)

zci ∈ 0, 1 ∀c ∈ C, ∀i ∈ Vc (4.16)

zi ∈ 0, 1 ∀i ∈ V (4.17)

Tabella 4.1: Formulazione MILP


• variabili binarie che indicano se il vertice i fa da punto di P/D per la

cella c.

La funzione obiettivo 4.1, da minimizzare, rappresenta il flusso complessivo

di materiali nell’impianto.

La sussistenza delle ipotesi di base del problema SLDP sono assicurate

dai set di vincoli 4.2, 4.3 e 4.4. Poiche il loop deve essere unidirezionale, ogni

spigolo puo essere presente sullo stesso in una soltanto delle due possibili

direzioni. Questo e assicurato dal set di vincoli 4.2. Inoltre, ogni cella deve

essere toccata dal loop in almeno uno spigolo: da qui il set di vincoli 4.3. Ogni

cella, infine, deve avere uno ed un solo punto di P/D: questo e garantito dal

set di vincoli 4.4.

Un vertice di una cella puo fungere da punto di P/D solo se fa parte del

loop, altrimenti la cella considerata risulterebbe isolata (set di vincoli 4.5).

Se un vertice funge da punto di P/D per una cella, allora almeno uno

spigolo della cella che comprenda il vertice considerato deve essere presente

sul loop (set di vincoli 4.6).

Ciascun vertice puo avere al massimo uno spigolo entrante sul loop (set

di vincoli 4.7) e al piu uno uscente (set di vincoli 4.8). D’altro canto, se

un vertice e sul loop, allora almeno uno spigolo in esso entrante ed uno da

esso uscente devono essere sul loop (set di vincoli 4.9 e 4.10). Infine, se uno

spigolo si trova sul loop, allora i due vertici che lo identificano devono trovarsi

anch’essi sul loop (set di vincoli 4.11).

Il set di vincoli 4.4 esprime il vincolo di conservazione dei flussi. Con-

siderando una coppia di celle tra cui sia previsto un flusso e un generico

vertice i, possono verificarsi le seguenti ipotesi:

• il vertice i non funge da punto di P/D per nessuna delle due celle: il

flusso netto uscente da i relativo alla coppia (c, d) e nullo;

• il vertice i funge da punto di P/D per una delle due celle: in questo

caso, il flusso netto uscente da i sara pari a 1 o a -1 a seconda di quale

cella utilizza i come punto di P/D;


• il vertice i funge da punto di P/D per entrambe le celle: in questo caso,

il flusso netto uscente da i deve essere nuovamente nullo.

Per non appesantire la notazione non si e rappresentato esplicitamente, nel set

di vincoli 4.4, il caso in cui il vertice i considerato non faccia parte dei vertici

di una o di entrambe le celle considerate. In questo caso, la variabile e/o

corrispondente non e definita e viene sostituita dal valore nullo, conservando

la validita del vincolo.

Considerato un generico spigolo sul loop, la quantita di flussi che vi puo

transitare e pari, al piu, al numero totale di flussi previsti nell’intero layout.

Questo limite e espresso dal set di vincoli 4.13.

4.3 Branch and cut

Il modello matematico presentato nella sezione precedente permette di risol-

vere il problema dello SLDP adoperando l’algoritmo di branch and bound

implementato in un risolutore matematico standard (ad esempio CPLEX).

E’ possibile, tuttavia, migliorare le prestazioni del modello, e abbreviare

quindi i tempi di calcolo, adoperando un approccio di tipo branch and cut.

Il modello matematico introdotto, infatti, puo essere ampliato con numerosi

vincoli aggiuntivi non derivanti da combinazione lineare di quelli gia presenti,

ma che derivano dalla particolare struttura del problema in esame.

Sia definito l’insieme D delle coppie di celle disgiunte come l’insieme delle

coppie di celle che non hanno alcun vertice in comune. Corrispondentemente

sara anche definito l’insieme delle celle contigue N . Possono essere fatte

diverse considerazioni sulle peculiarita del problema per le coppie di celle che

fanno parte dell’uno o dell’altro insieme, che permettono di ottenere ulteriori

vincoli validi per il problema e non esprimibili come combinazione lineare dei

vincoli gia introdotti.

E utile introdurre anche l’insieme Φ′ ⊆ Φ delle celle tra cui sia pre-

visto un flusso bidirezionale, definito come l’insieme delle coppie (c, d) ∈Φ t.c. (d, c) ∈ Φ.


Figura 4.1: Flussi tra celle disgiunte

4.3.1 Tagli aggiuntivi di tipo 1

Considerando una coppia di celle disgiunte tra cui sia previsto un flusso bidi-

rezionale di materiali, lungo un generico spigolo del layout che sia inserito nel

loop deve necessariamente transitare uno dei due flussi previsti. Consideran-

do la situazione in Figura 4.1, ad esempio, sullo spigolo orientato evidenziato

deve passare necessariamente uno ed uno solo dei flussi previsti tra la cella

1 e la cella 8. Un possibile loop ammissibile e riportato, invece, accanto: in

questo caso, lungo lo spigolo considerato deve transitare il flusso diretto dalla

cella 8 verso la cella 1.

La considerazione fatta porta alla formulazione del seguente set di vincoli

aggiuntivi:

xijcd + xijdc = yij ∀(c, d) ∈ D ∩ Φ′,∀(i, j) ∈ E (4.18)


Considerando una coppia di celle confinanti tra cui sia previsto un flusso

bidirezionale di materiali e un generico spigolo orientato del layout, non e

possibile ripetere le considerazioni fatte nel caso dei tagli di tipo 1. Infatti,

in questo caso, il flusso previsto tra le due celle potrebbe anche non circolare

nel layout, qualora per le celle fosse selezionato come punto di P/D un medes-

imo punto, appartenente evidentemente ad entrambe le celle. Un esempio e


Figura 4.2: Flussi tra celle confinanti

riportato in figura 4.2. Lungo lo spigolo orientato evidenziato, infatti, anche

se questo dovesse far parte del loop ottimo, potrebbe non transitare alcun

flusso relativo alla coppia di celle selezionate 4 e 7. Viene riportato, ad es-

empio, quello che potrebbe essere il loop ottimale per il problema in esame.

Se il punto evidenziato viene scelto come punto di P/D per le celle 4 e 7,

allora nessun flusso di materiali relativo a questa coppia di celle circolera nel

loop e, quindi, neanche lungo l’arco indicato. Tuttavia, se lo spigolo orien-

tato non si trova sul loop, allora lungo lo stesso non transitera alcun flusso,

indipendentemente dalla coppia di celle selezionata.

In generale, quindi, considerata una coppia di celle confinanti tra cui sia

previsto un flusso bidirezionale e un generico spigolo orientato, lungo di esso

puo transitare al piu uno dei due flussi previsti tra le celle. Questa proprieta

permette di formulare il seguente set di tagli aggiuntivi:

xijcd + xijdc ≤ yij ∀(c, d) ∈ N ∩ Φ′, ∀(i, j) ∈ E (4.19)


Si consideri una coppia (c, d) di celle confinanti tra cui sia previsto un flusso

bidirezionale e un generico spigolo (i, j) orientato sul layout. Per ciascuno


dei vertici k comuni alle due celle e possibile introdurre un vincolo del tipo:

xijcd +xijdc ≤ 2−zck−zdk ∀(c, d) ∈ N ∩Φ′, ∀(i, j) ∈ E, ∀k ∈ Vc∩Vd (4.20)

Infatti, i flussi tra le due celle che devono transitare nel loop si annullano

nel caso in cui un vertice comune alle due celle viene scelto come punto di

P/D per entrambe le celle.

La disuguaglianza 4.20 puo essere rafforzata considerando un qualsiasi

vertice i del layout e tutti gli spigoli orientati da esso uscenti. Da ciascun

vertice, infatti, i flussi uscenti relativi alla coppia di celle considerata dovran-

no essere nulli nell’ipotesi che k sia punto di P/D per entrambe le celle.

Analogo discorso puo essere fatto nel caso degli archi uscenti da un vertice

del layout.

Il set di vincoli 4.20 puo quindi essere sostituito con i seguenti set di

vincoli:

∑(i,j)∈EO

i

xijcd + xijdc ≤ 2− zck − zdk ∀(c, d) ∈ N ∩ Φ′, ∀i ∈ V, ∀k ∈ Vc ∩ Vd

(4.21)

∑(j,i)∈EI

i

xjicd+xjidc ≤ 2−zck−zdk ∀(c, d) ∈ N∩Φ′, ∀i ∈ V, ∀k ∈ Vc∩Vd (4.22)


Considerando una coppia (c, d) di celle confinanti tra cui sia previsto un flusso

bidirezionale ed uno spigolo (i, j) che abbia un vertice su una delle due celle

e uno sull’altra, si puo introdurre un taglio del tipo:

xijcd ≥ yij + zci + zdi − 2 ∀(c, d) ∈ N ∩ Φ′, ∀i ∈ Vc, ∀(i, j) ∈ E t.c. j ∈ VD

(4.23)


Figura 4.3: Flussi tra vertici di frontiera

La relazione 4.23 e irrilevante se almeno uno tra i termini al secondo

membro e nullo; vincola, invece, il primo membro ad assumere valore unitario

se si verificano contemporaneamente le seguenti ipotesi:

• lo spigolo orientato considerato fa parte del loop

• il vertice scelto fa da punto di P/D per entrambe le celle

Nel caso in figura 4.3, ad esempio, se l’arco evidenziato fa parte del loop e i

vertici indicati fanno rispettivamente da punto di P/D per la cella 2 e per la

cella 5, allora lungo lo spigolo deve necessariamente transitare tutto il flusso

di materiale previsto dalla cella 5 verso la cella 2.

4.3.5 Algoritmo Branch & Cut

L’introduzione di tutti i vincoli introdotti nelle sezioni precedenti al mod-

ello matematico presentato nella sezione 4.1 porterebbe ad un appesanti-

mento notevole dello stesso, tanto da rallentare il tempo richiesto per la

sua risoluzione col metodo di branch and bound implementato nei risolutori

matematici standard. Il tempo extra richiesto per risolvere i rilassamenti

continui dei singoli nodi dell’albero di branch and bound supera, nei test

effettuati, il tempo che si risparmia grazie alla riduzione del numero di nodi

dovuta alla migliore qualita dei lower bound prodotti.

Un modo migliore per sfruttare le relazioni introdotte consiste nel loro

impiego in un algoritmo di tipo branch and cut. L’approccio branch and


cut per la risoluzione di problemi di ottimizzazione intera e diventato molto

popolare negli ultimi anni. La differenza principale con l’approccio branch

and bound classico consiste nell’utilizzo dei rilassamenti lineari e nell’impiego

di piani di taglio in ogni nodo dell’albero di elaborazione.

Nell’approccio adoperato, i vincoli aggiuntivi vengono presi in esame ad

ogni nodo dell’albero di elaborazione, a partire dal nodo radice. I vincoli che

risultano violati vengono introdotti in modo permanente nella risoluzione

dei successivi nodi. L’impiego dei tagli aggiuntivi permette di migliorare

notevolmente la qualita dei lower bound sui singoli nodi, e in particolare

al nodo radice, con conseguente riduzione del numero di nodi complessivi;

la generazione dinamica dei tagli, al tempo stesso, consente di pervenire a

questi risultati introducendo solo una piccola parte di tutti i possibili tagli

disponibili.

4.4 Tabu Search per lo SLDP

4.4.1 Le meta-euristiche Tabu Search

La Tabu Search (TS), presentato da Glover in [10], e una procedura meta-

euristica utilizzabile per risolvere un’ampia classe di problemi di ottimiz-

zazione. La caratteristica principale della TS e di consentire al processo riso-

lutivo di uscire da situazioni di stallo, costituite dal raggiungimento di punti

di ottimo locale. Questo obiettivo viene conseguito grazie alle tecniche di

autoapprendimento che contraddistinguono la TS. Le direzioni lungo cui ef-

fettuare la ricerca dei punti di ottimo vengono, infatti, stabilite ed influenzate

dalla storia della ricerca stessa.

Sono soprattutto tre gli aspetti della TS che vanno evidenziati:

1. l’utilizzo di strutture di memoria flessibili basate su attributi ;

2. un meccanismo di controllo che utilizza tali strutture per guidare il

processo di ricerca;

3. strategie che agiscono sulle strutture di memoria allo scopo di intensi-

ficare e diversificare la ricerca.


Prima di analizzare in dettaglio la TS introduciamo un problema di ottimiz-

zazione in senso lato:

min c(x)

s.v.

x ∈ X

doveX e l’insieme finito delle soluzioni ammissibili;

x e una generica soluzione ammissibile;

c(x) : X → R esprime la funzione obiettivo.

Descrizione

La caratteristica principale della TS consiste nel prendere decisioni in base

alla ”storia”della ricerca. Si supponga che l’algoritmo risolutivo sia giunto ad

una soluzione xnow. E’ possibile identificare tutta una regione di X, N(xnow),

definita come l’insieme di tutte le soluzioni di X raggiungibili direttamente

da xnow con un’operazione detta mossa. In tale regione andra selezionata la

soluzione successiva xnext. Muovendosi sistematicamente in questo modo, si

corre il rischio di effettuare mosse che portano a soluzioni con caratteristiche

poco attraenti, gia esaminate nel processo di ricerca. Di conseguenza, la TS

va a considerare non tutto N(xnow), ma un suo sottoinsieme N(H, xnow),

dove H esprime la storia della ricerca fino all’iterazione attuale. La selezione

di N(H, xnow) all’interno di N(xnow) viene effettuata inibendo, in funzione di

H, la scelta di elementi di N(xnow) che vengono considerati tabu. Anche la

scelta di xnext ∈ N(H, xnow) dipende dinamicamente dal processo risolutivo,

verra selezionata infatti la xnext che rende minimo il costo c(H, x).

Il processo risolutivo puo essere, allora, sintetizzato come esposto nell’al-

goritmo 1.

Va sottolineata la necessita di imporre la convergenza dell’algoritmo, ar-

restando la ricerca dopo un assegnato numero di iterazioni, in quanto essa si

basa su un principio euristico sulla cui convergenza non e possibile fare al-

cuna ipotesi. In figura 4.4, e riportato l’andamento di una generica funzione

obiettivo al variare delle soluzioni ammissibili.

Si supponga di voler effettuare la ricerca del punto di minimo eseguendo


STEP 1 (inizializzazione)Si sceglie una soluzione del problema. Si pone:xnow = prima soluzionebest cost = c(xnow)Si azzera la struttura H.STEP 2Si sceglie xnext ∈ N(H, xnow) che minimizzi la c(H, x).STEP 3Si pone xnow = xnext.Se c(xnext) <best cost, si aggiorna best cost. Si aggiorna la struttura H.Si torna allo STEP 2 o si esce se il numero di iterazioni supera il numeromassimo prefissato.

Algoritmo 1: Tabu Search

Figura 4.4: Andamento della f.o. in un TS

gli STEP individuati in precedenza. Si ipotizzi che la ricerca parta dalla

soluzione x2 e che l’insieme N(xnow) contenga le soluzioni adiacenti ad xnow

nell’ordine di rappresentazione.

Alla prima iterazione il processo risolutivo seleziona xnext = x3 che, tra

le soluzioni di N(x2) = {x1, x3}, e quella di costo minore. Alla seconda

iterazione il processo di ricerca si porta in x4 (N(x3) = {x2, x4}), che cos-

tituisce un punto di minimo locale. Alla terza iterazione l’algoritmo non

riesce a trovare soluzioni migliorative (N(x4) = {x3, x5}), e sceglie quindi la

soluzione meno peggiorativa (x5). A questo punto, essendo N(x5) = {x4, x6},la soluzione successiva dovrebbe essere x4. Tale scelta determina l’entrata in

loop dell’algoritmo. Se pero all’iterazione 3 si etichetta la mossa che porta

nella soluzione x4 come non effettuabile, viene data al processo di ricerca la

possibilita di allontanarsi dall’ottimo locale e di esplorare nuove soluzioni.

Attributi di mossa e restrizioni tabu

Il passaggio da N(xnow) a N(H, xnow) viene realizzato introducendo nuovi

vincoli al problema, detti restrizioni tabu. Tali vincoli esplicano il loro ef-

fetto rendendo temporaneamente vietati alcuni attributi che identificano un


determinato insieme di mosse. In questo modo si impedisce al processo riso-

lutivo di ripetere o invertire mosse gia effettuate, fornendo cosı la possibilita

di uscire dai punti di stallo, costituiti dai minimi locali.

Si consideri un problema in cui la generica soluzione e descritta da una

sequenza di elementi ed il costo associato e individuato univocamente dal

loro ordine. Un esempio di tale problema e il TSP (Traveling Salesman

Problem), dove la generica soluzione e una sequenza di tutti i nodi della

rete, ed il suo costo, e la somma di quelli associati agli archi. Si consideri

la mossa xnow → xnext, consistente nello spostamento dell’elemento j dalla

posizione p a quella q. In letteratura, sono stati proposti i seguenti attributi

per individuare tale mossa :

(A1) la posizione iniziale p;

(A2) la posizione finale q;

(A3) la coppia (A1) e (A2);

(A4) la differenza ∆ = g(xnow) − g(xnext), dove g(x) e una funzione

scelta opportunamente.

La scelta dell’attributo, o degli attributi, dipende da molti fattori e, in gen-

erale, viene presa in relazione ad esperienze su problemi analoghi a quello in

analisi. Ne consegue che, in relazione agli attributi considerati, vengono inib-

ite mosse diverse durante il processo di ricerca. Ad esempio, con riferimento

agli attributi descritti in precedenza, risultano tabu le seguenti mosse:

Attributo Mossa tabu

(A1) (R1): mossa che sposta j dalla posizione p;

(A2) (R2): mossa che porta j nella posizione q;

(A3) (R3): (R1) o (R2);

(A4) (R4): (R1) e (R2);

(A5) (R5): mossa che produca una variazione ∆.


La scelta tra una o piu di queste restrizioni e legata alle caratteristiche di

aggressivita che si vogliono conferire alla ricerca. A tal proposito si osservi

come il vincolo (R3) sia piu restrittivo di (R4), cio rende vietate un numero

maggiore di mosse. In questo caso la ricerca e spinta ad esplorare nuove zone.

Un metodo per poter gestire i vincoli tabu consiste nel definire due array,

tabu start(e) e tabu end(e); dato l’attributo e, tabu start(e) rappresenta l’it-

erazione in cui l’attributo e e divenuto tabu, mentre tabu end(e) l’iterazione

in cui cessera tale stato.

All’iterazione i, quindi, se e esprime un attributo della mossa effettuata, si

aggiorna tabu end( not(e)) con il valore i+T , dove not(e) esprime l’attributo

della mossa inversa, e T esprime il numero di iterazioni, durante le quali, tutte

le mosse che cercano di ripristinare l’attributo not(e) sono considerate tabu.

Il parametro T esprime quindi la lunghezza della lista tabu.

Il valore da assegnare a T dipende dal problema, ma possono essere date

delle regole di massima per fissare tale valore:

1. regole statiche: T e posto pari a valori varianti tra 5, 2 e 20 (7 o 12 in

particolare) o a√

N , se N e la dimensione del problema

2. regole dinamiche:

(a) vengono fissati a priori Tmax e Tmin e si sceglie T variabile in tale

intervallo;

(b) si lasciano variabili anche Tmax e Tmin i cui valori sono assunti come

funzioni dell’attrattivita e dell’influenza dei singoli attributi.

Criteri di aspirazione

In qualche caso, risulta favorevole, ai fini della ricerca, eseguire particolari

mosse contenute nella lista tabu. Il criterio di aspirazione consiste in un

test che, se soddisfatto, permette l’effettuazione di una mossa tabu. Ogni

attributo puo avere uno o piu criteri di aspirazione che, come le restrizioni

tabu, sono dipendenti dal tempo. Il criterio d’aspirazione puo essere applicato

ad un attributo nel periodo in cui esso e tabu, per consentire l’esecuzione di

una mossa tabu che porti ad una soluzione migliore di quelle precedenti.


E’ possibile individuare i seguenti criteri d’aspirazione:

1. Criterio di aspirazione per obiettivo:

(a) Forma Globale: una mossa tabu viene eseguita se c(xnext) <

best cost, cioe se e migliorativa in assoluto

(b) Forma Regionale: l’ insieme X viene suddiviso in regioni Xi def-

inite come {x ∈ X : g(x) = r con r ∈ R}. La mossa viene aspi-

rata se migliora il costo minimo della propria regione (c(x) <

best cost(Xi))

2. Criterio di aspirazione per influenza

(a) Si supponga di essere in grado di misurare in qualche modo l’in-

fluenza che un attributo ha sul processo di ricerca. Sara possibile

aspirare gli attributi a bassa influenza, che erano divenuti tabu

prima che fosse eseguita una mossa con attributi di forte influenza.

Il criterio 2 e di facile comprensione, se si pensa che una mossa ad alta influen-

za porta la ricerca verso nuove zone di X, spazio delle soluzioni ammissibili,

per cui non si corre il rischio di ritornare indietro effettuando le mosse tabu

a bassa influenza.

Un criterio d’aspirazione, che si discosta da quelli esaminati in preceden-

za, prevede la classificazione di un attributo tabu, che soddisfa un criterio

d’aspirazione, come tabu pendente [11]. Una mossa che coinvolga un at-

tributo tabu pendente potra essere effettuata solo se non esistono soluzioni

ammissibili migliorative.

Si definisce inoltre una mossa fortemente ammissibile se e verificata al-

meno una delle seguenti due condizioni:

1. e ammissibile in senso stretto (cioe non coinvolge nessun attributo

tabu attivo o pendente);

2. soddisfa il criterio di aspirazione per obiettivo in forma globale (cioe

c(x) < best cost).


Il criterio di aspirazione puo essere, quindi, enunciato nel seguente modo: pos-

to last nonimprovement pari al valore dell’ultima iterazione non migliorativa

e last strongly admissible pari al valore dell’ultima iterazione nella quale e

stata effettuata una mossa fortemente ammissibile, se last nonimprovement <

last strongly admissible allora tutte le mosse migliorative classificate tabu

vengono considerate tabu pendenti e vengono effettuate solo se non esistono

altre mosse migliorative.

La scelta di uno o piu criteri d’aspirazione, dipende dal tipo di proble-

ma, dalla sua dimensione e dalle altre caratteristiche della TS implementata.

Un criterio d’aspirazione, per esempio, puo risultare piu o meno efficace, in

relazione alla scelta degli attributi di mossa o dal tipo di mossa stessa. La

selezione va quindi operata sulla base di dati sperimentali.

Strategia basata sulla frequenza delle mosse e delle soluzioni

Le informazioni che provengono dall’evoluzione dell’algoritmo di ricerca, pos-

sono essere utilizzate fondamentalmente in due modi: uno e quello legato agli

attributi e alle mosse di recente effettuazione (Recency Based Memory) ed e

la strada seguita dal controllo basato sulle restrizioni tabu.

Esiste pero anche un altro possibile controllo della ricerca. Tale tipo

di controllo utilizza le informazioni che riguardano la frequenza con la quale,

durante la ricerca, vengono coinvolti gli attributi delle mosse e le mosse stesse

(Frequency Based Memory).

Sia x(1), x(2), · · · , x(iter corrente) la sequenza di tutte le soluzioni gener-

ate durante il processo di ricerca fino all’iterazione corrente, e sia S una sua

sottosequenza. Si definiscono:

S(attrib sol) = insieme delle soluzioni di S che contengono

l’attributo attrib sol

#S(attrib sol) = la cardinalita di S(attrib sol)

S(attrib mossa) = insieme delle soluzioni di S ottenute con una

mossa individuata da attrib mossa

S(attrib mossa) = la cardinalita di S(attrib mossa)

Se, ad esempio, un attrib sol e rappresentato dalla posizione ′′xj = p′′,


S(′′xj = p′′) indica tutte le soluzioni di S che hanno l’elemento j in posizione

p. Se invece attrib mossa e, per esempio, dato da ′′da xj = p a xj = q′′,

S(′′da xj = p a xj = q′′) identifica tutte le mosse che spostano l’elemento j da

p a q.

Dunque #S(attrib sol) costituisce una misura di residenza dell’attrib-

uto attrib sol nelle soluzioni che si sono succedute in S. Il rapporto tra

#S(attrib sol) e il numero delle occorrenze di tutti gli attributi di soluzione,

ci fornisce una misura della frequenza di residenza di attrib sol nella sequenza

di soluzioni.

Analogamente, e possibile definire una misura di transizione ed una fre-

quenza di transizione, a partire dagli attributi di mossa. La conoscenza di tali

dati permette di controllare la direzione lungo la quale proseguire il processo

di ricerca del punto di ottimo.

Se la frequenza di residenza di un dato attributo e alta, per esempio, puo

essere desunto che tale attributo e fortemente attrattivo, nel caso in cui la

sequenza di soluzioni e di alta qualita, o fortemente repulsivo, se la sequenza

e di bassa qualita.

Intensificazione e diversificazione

I parametri di residenza e di transizione, forniscono informazioni sulle mosse

e sulle soluzioni che storicamente si sono succedute. Tali parametri sono

quindi gli strumenti ideali per monitorare il processo di ricerca e modificare

le direzioni del processo stesso.

L’intensificazione e una strategia che dirige il processo di ricerca nell’in-

torno di soluzioni identificate da un attributo che compare frequentemente

in soluzioni buone.

La diversificazione, invece, ha come effetto quello di spostare la ricerca

verso nuove regioni, non ancora esplorate durante il processo di ricerca. Tale

operazione si rende necessaria poiche, in molti casi, le strategie a breve ter-

mine, quelle cioe legate alle sole restrizioni tabu, non sono in grado di uscire

dalla regione d’attrattivita di un minimo locale. Nasce quindi la necessita di

forzare il passaggio in una zona lontana dalla precedente. Tale osservazione


evidenzia la necessita di introdurre strategie di diversificazione, a prescindere

dal fatto che l’analisi basata sui parametri di frequenza, venga effettuata o

meno.

Si sono prese in considerazione alcune strategie di controllo presenti in

letteratura.

Penalita e incentivi. Un approccio che puo essere seguito per intensifi-

care e diversificare la ricerca, e quello basato sull’introduzione di penalita ed

incentivi nella selezione delle mosse da effettuare. In questo caso la selezione

della prossima soluzione, si basa sul valore assunto dalla funzione obietti-

vo, alla quale viene sommato un costo aggiuntivo, funzione dei parametri di

frequenza. Se si penalizzano le mosse relative agli attributi piu frequenti,

si otterra un effetto di diversificazione. Se, invece, si incentivano le mosse

contenenti gli attributi piu frequenti, si otterra un effetto di intensificazione.

Sequenze di diversificazione. Per diversificare il processo di ricerca, in

modo efficiente, e necessario generare tutta una sequenza di mosse di diver-

sificazione, ognuna delle quali deve essere selezionata in modo opportuno.

Glover e Laguna [11] hanno suggerito dei criteri per caratterizzare tali se-

quenze. Sia Z(k) = (z(1), z(2), . . . , z(k)) una sequenza di k soluzioni. Tale

sequenza viene definita sequenza di diversificazione se, definita una metri-

ca nello spazio delle soluzioni, Z(k) e costituita da sottosequenze Z(h), con

h ≤ k, tali che z = z(h + 1) soddisfi le tre seguenti condizioni:

1. z massimizza la minima distanza d(z, z(i)) per i ≤ h;

2. z massimizza la minima distanza d(z, z(i)) per 1 ≤ i ≤ h, poi per

2 ≤ i ≤ h, etc;

3. z massimizza la minima distanza d(z, z(i)) per i = h, poi per i = h−1,

etc.

Tali condizioni impongono che le soluzioni z(i) siano i vertici di un ipercubo

nello spazio delle soluzioni, la cui posizione e legata, in particolare, a z(1),

che costituisce il seme della sequenza.

Rinforzo delle restrizioni tabu. Se un attributo e molto frequente in se-

quenze di soluzioni d’alta qualita, si puo pensare di intensificare la ricerca in


tale regione, rinforzando quelle restrizioni tabu che impediscono la rimozione

di tale attributo. Questa strategia presenta le stesse caratteristiche di quella

legata all’introduzione di penalita e incentivi, con due vantaggi supplemen-

tari: riducendo il numero di mosse ammissibili, rende piu veloce la loro se-

lezione; in secondo luogo, rinforzando le restrizioni tabu, esalta la possibilita

di far uscire la ricerca da eventuali situazioni di stallo, situazioni per le quali

le restrizioni tabu sono state introdotte.

Costruzione di un sentiero. Si scelgono x′ e x′′ da una collezione di

soluzioni, selezionate tra quelle effettuate fino all’iterazione attuale. Viene

poi generato un sentiero che porta da x′ a x′′, individuando r soluzioni in-

termedie (x′(1), x′(2), . . . , x′(r)), scelte in modo tale che x′(i) minimizzi il

numero di mosse che mancano per raggiungere x′′. Una volta costruito il

sentiero, si seleziona una o piu x′(i) come nuovo punto di partenza della

ricerca. L’effetto di intensificazione si ottiene se x′ e x′′ contengono attributi

fortemente attrattivi, mentre l’effetto di diversificazione si ottiene se x′ e x′′

sono molto distanti tra loro.

Valutazione delle soluzioni non visitate. Un’altra strategia di controllo

si basa sulle informazioni relative alle caratteristiche delle soluzioni analiz-

zate ma non selezionate durante la ricerca. Questo approccio e basato sulla

memorizzazione di parametri di frequenza, relativi ad attributi di soluzioni

non effettuate e quindi non presenti nella memoria del processo di ricerca.

La struttura di alcune di queste soluzioni, per esempio quelle appartenen-

ti ad una data banda di attrattivita espressa in termini di funzione obi-

ettivo, puo risultare utili per contribuire a pilotare un processo di ricerca

d’intensificazione e diversificazione.

Metodo delle oscillazioni. Tale approccio permette di ottenere una strate-

gia di ricerca che si pone a meta strada tra la diversificazione e l’intensifi-

cazione. Questo metodo fornisce gli strumenti per oltrepassare i confini del-

l’insieme N(xnow). La sequenza di diversificazione o di intensificazione, e

costituita da mosse che attraversano tali confini lungo ogni direzione possi-

bile, individuata da un processo oscillatorio. Il controllo di tale oscillazione

si basa sulla variazione dei criteri con i quali vengono selezionate le mosse

ed e influenzato dalla regione che attualmente e interessata dal processo di


ricerca.

Target Analysis

Procedure che inglobano elementi di diversificazione e intensificazione pos-

sono essere ottenute stabilendo degli standard storici per differenziare la

qualita di mosse alternative.

L’efficacia di uno stimatore, come quello basato sulle variazioni della fun-

zione obiettivo, puo variare notevolmente in funzione della soluzione corrente.

Il target analysis, e un approccio basato sull’esperienza, che permette lo

sviluppo di stimatori opportuni per intensificare e diversificare la ricerca. Al-

la base di tale approccio c’e la volonta di investire un intenso sforzo prelim-

inare per determinare soluzioni ottime o sub-ottime (soluzioni target), per

problemi rappresentativi di una data classe. Successivamente si risolvono

nuovamente tali problemi utilizzando le soluzioni target per valutare l’effi-

cacia degli stimatori: uno stimatore sara ritenuto efficace se e in grado di

dirigere la soluzione verso soluzioni target. Sulla base di questo criterio, e

possibile valutare uno stimatore, in funzione della vicinanza o meno delle

soluzioni generate rispetto a quelle target.

Mediante tali valutazioni, si puo scoprire se, e in quali regioni, gli sti-

matori sono attendibili, e quindi memorizzare gli attributi delle mosse dalle

valutazioni piu alte. Si possono costruire, inoltre, funzioni parametriche dalle

informazioni cosı ottenute, che integrino gli stimatori standard nelle regioni

dove questi fallissero nella ricerca di buone soluzioni e, in conclusione, si

possono scegliere opportunamente tali parametri, utilizzando tali funzioni al

posto degli stimatori standard.

Diversificazione basata sulla distanza

Una strategia di diversificazione risulta particolarmente interessante in situ-

azioni dove le soluzioni migliori possono essere raggiunte solo superando certe

difficolta e scegliendo mosse con una valutazione minore. Per identificare

mosse appropriate per superare tali difficolta, deve essere creata una fun-


zione di memoria per classificare l’attrattivita di mosse all’interno di una

data classe di distanza.

Il concetto di distanza di una mossa deriva dal fatto che una mossa puo

produrre modifiche maggiori alla soluzione corrente di quelle prodotte da

altre. Per esempio, in un’applicazione del TSP, una mossa che trasferisce un

nodo diverse posizioni lontano da quella che tale nodo aveva precedentemente

nel circuito, e caratterizzata da una distanza maggiore rispetto ad una mossa

che sposta un nodo di una sola posizione nel circuito.

In genere, mosse di grande distanza comportano costi maggiori, quando

sono valutate da stimatori standard, rispetto a mosse che coprono distanze

minori. Tali mosse sono valutate meno attrattive dagli stimatori rispetto a

quelle che coprono una distanza minore; per questo motivo, saranno rara-

mente scelte durante il processo di ricerca, pur essendo necessarie per su-

perare le difficolta presenti. Quando gli stimatori standard perdono la loro

efficacia, si puo ottenere un effetto di diversificazione selezionando le mosse

migliori appartenenti a classi raramente utilizzate.

Si possono quindi utilizzare informazioni storiche per determinare quale

classe di distanza scegliere, e quindi comparare, mediante uno stimatore, le

mosse che appartengono a tale classe.

Puo risultare utile, allora, effettuare un numero limitato di iterazioni pre-

liminari per identificare statistiche storiche, relative alle valutazioni delle

mosse di ogni classe di distanza, e, per le iterazioni successive, applicare

la target analysis al fine di ottenere scelte efficienti (comparando la valu-

tazione delle mosse di ogni classe, associata all’iterazione corrente, con queste

statistiche)

Queste nozioni possono essere utilizzate per sviluppare processi paralleli.

Di solito, le mosse di grande distanza sono le piu difficili da valutare, ma

proprio esse producono grossi cambiamenti. Comunque, e possibile iden-

tificare un insieme ristretto di mosse di grande distanza (tra le quali al-

meno una ha una buona valutazione), senza precisare quale di esse sia la

migliore. L’applicazione di processi paralleli per esaminare le conseguen-

ze di tali mosse alternative, puo rappresentare una tecnica piu efficace per

effettuare la selezione.


L’uso di processi paralleli puo essere particolarmente utile se l’effettuazione

di una mossa rendesse difficoltoso ottenere di nuovo soluzioni precedente-

mente accessibili; in tali casi si potrebbero svolgere in parallelo due processi

di ricerca, uno effettuando quella mossa, l’altro non effettuandola.

Generazione di nuovi punti di partenza

In generale, un mezzo per migliorare le prestazioni di una tecnica euristica,

e quello di ricominciare, il processo risolutivo, da soluzioni differenti gener-

ate casualmente o prese da un insieme di soluzioni selezionate. In genere,

si possono utilizzare le informazioni raccolte durante la ricerca per favorire

la creazione di soluzioni distanti da quelle visitate; nel fare questo si deve

considerare che la scelta di una soluzione di partenza non opportuna puo far

ripresentare su larga scala soluzioni gia visitate.

Un metodo per scegliere una soluzione di partenza adatta, si basa sui

parametri di frequenza e di residenza di particolari attributi nelle soluzioni

finora esplorate.

In questo modo, volendo costruire nuovi punti di partenza, o diversifi-

care la ricerca, si possono penalizzare le mosse che contengono attributi piu

frequentemente occorsi nel passato.

Tabu Search con liste dinamiche

Per implementare la tabu search si puo utilizzare una particolare struttura

dinamica, che permetta allo stesso tempo di mantenere un certo numero di

mosse tabu e di lasciare ai criteri d’aspirazione la possibilita di modificare lo

stato tabu di una certa mossa.

Nel caso in cui ogni mossa sia caratterizzata da un solo attributo, la TL e

un vettore di attributi che associa, uno stato tabu, alle mosse che contengono

tali attributi:

TL = (e(p), . . . , e(q − 1), e(q))

Corrispondentemente, possiamo identificare la lista di soluzioni:

SL = (x(p), . . . , x(q − 1), x(q))

tale che, per ogni i, e(i) e l’attributo associato con la mossa applicata


alla soluzione x(i), che impedisce di ripassare per x(i) applicando la mossa

inversa. Due soluzioni x(h) e x(k) con h < k possono essere considerate

uguali se all’interno della successione e(h), . . . , e(k), per ogni e(r), e possibile

individuare un e(s) che sia l’inverso di e(r). In tal caso si dice che e(s)

cancella e(r).

Nelle procedure che fanno uso di liste dinamiche, un attributo presente

in tali liste non rende automaticamente tabu una mossa, a meno che, tale

mossa, non porti effettivamente ad una soluzione visitata in precedenza.

Come esempio, si puo considerare una lista tabu attiva, ATL, che consista

solo degli elementi di TL che non sono stati cancellati:

ATL = (e(p), . . . , e(q − 1), e(q))

Se si inserisce nell’ATL un nuovo elemento e(q+1) che cancelli un elemen-

to e(i) dell’ATL stessa, non si ritorna ad un soluzione precedente a meno che

non siano cancellati tutti gli elementi compresi tra e(i) ed e(q + 1); tale se-

quenza e detta sequenza di cancellazione. Quindi una mossa sara considerata

tabu se e solo se essa e l’ultima rimasta di una data sequenza di cancellazione,

una volta che tutti gli altri elementi della lista sono stati cancellati. Si puo

mantenere, comunque, parallelamente una lista tabu del vecchio tipo ma di

lunghezza molto limitata (1÷3), che quindi rendera tabu tutti gli attributi

in essa presenti.

4.4.2 Implementazione del TS nello SLDP

La procedura euristica implementata provvede, ad ogni passo della procedura

iterativa (mossa), alla sostituzione degli archi di una data cella, presenti

attualmente nel loop, con quelli della stessa non ancora inclusi. La cella

selezionata per effettuare questa sostituzione e quella che fornisce il miglior

apporto alla funzione obiettivo. La ricerca procede in questo modo per un

numero prefissato di passi, stabilito dall’utente, per poi fornire come risultato,

il migliore fra quelli trovati durante la procedura di ricerca.

Per evitare che la procedura cicli in una certa sequenza di mosse, e per

permettere quindi un’efficiente scansione di tutte le possibili zone del layout,

si utilizzano alternativamente due strategie ben distinte:


• quella di breve periodo (intensificazione) permette di ricercare la soluzione

piu attrattiva nell’intorno della soluzione corrente, tenendo conto della

storia recente della sequenza di mosse;

• quella di lungo periodo (diversificazione) permette di ispezionare ef-

ficacemente lo spazio delle possibili soluzioni abbandonando, quando

opportuno, la zona attualmente esplorata, in modo da svincolarsi da

eventuali minimi locali.

Mossa

Uno dei concetti fondamentali nell’implementazione di un algoritmo di tipo

tabu search e la definizione della mossa. Durante una generica iterazione

dell’algoritmo, infatti, vengono individuate e valutate diverse possibilita, ot-

tenibili ciascuna a seguito di una particolare mossa. Nel caso in esame, la

mossa puo essere definita in termini di XOR su una determinata cella. As-

segnato un certo loop e identificata una cella, effettuare l’XOR del loop sulla

cella significa modificare opportunamente il loop in modo che:

• gli spigoli della cella che sono inizialmente sul loop non vi siano piu

dopo l’applicazione mossa

• gli spigoli della cella non presenti inizialmente nel loop vi entrino dopo

l’esecuzione della mossa

A titolo di esempio, si consideri la situazione in figura 4.5, che rappresenta

l’operazione di XOR sulla cella 6 del layout in esame nel loop considerato.

Soluzione iniziale

La determinazione di una soluzione iniziale ammissibile da cui avviare il

processo di ricerca non e, in generale, immediato. Esistono casi in cui trovare

una soluzione ammissibile non e possibile. Si consideri, ad esempio, il layout

in figura 4.6, riportato in letteratura in [4]: in questo caso e evidentemente

impossibile identificare un unico loop che contenga almeno uno spigolo di

ciascuna cella.


Figura 4.5: Esempio d XOR su celle

Figura 4.6: Layout non servibile con un unico loop


L’approccio seguito nella determinazione della soluzione iniziale sfrutta la

procedura di TS stessa. Viene, infatti, eseguita una prima intensificazione a

partire dalla soluzione, in generale non ammissibile, costituita dal perimetro

esterno del layout. Durante questa intensificazione preliminare, viene utiliz-

zato, come funzione obiettivo, il numero di celle toccate in almeno uno spigolo

dal loop. Se, dopo un numero stabilito di iterazioni, non e stata individuata

una soluzione ammissibile, il problema viene considrato inammissibile. Se

si perviene prima del numero prefissato di iterazioni ad un loop ammissi-

bile, l’intensificazione preliminare viene conclusa e la soluzione trovata viene

adoperata come soluzione iniziale per il TS.

Funzione obiettivo

La funzione obiettivo, da minimizzare, e costituita dalle movimentazioni com-

plessive genrate in reparto. Ad ogni valutazione della funzione obiettivo e

quindi necessario posizionare i punti di P/D. A tal fine viene utilizzato il

modello matematico introdotto nella fase 4 della metodologia OSL presenta-

ta in [22]. Viene quindi calcolato, per ogni coppia di celle, il contributo alla

funzione obiettivo dato dal prodotto della quantita di flusso previsto per la

distanza tra i punti di P/D delle celle considerate.

Intensificazione

La strategia di breve periodo permette alla ricerca di evolvere verso la zona

di maggior beneficio, per la funzione obiettivo, nell’intorno della soluzione

corrente, mantenendo allo stesso tempo traccia dell’evoluzione, nel breve pe-

riodo, in modo tale da evitare l’insorgenza di cicli nella sequenza delle mosse

selezionate. I passi della strategia di breve periodo sono:

• valutazione e attuazione della mossa;

• valutazione dei punti di P/D;

• mantenimento di una lista variabile di mosse tabu;

• valutazione del criterio di terminazione dell’intensificazione;


• valutazione del criterio di terminazione dell’euristica.

Valutazione e attuazione della mossa. Ad ogni passo dell’intensificazione,

vengono esaminate le diverse evoluzioni ottenibili eseguendo l’XOR sulle di-

verse celle purche rimanga garantita l’ammissibilita. Si scartano quindi tutte

le mosse che comportano la perdita dell’ammissibilita, quelle che risultano

tabu e, fra le mosse rimanenti, si sceglie quella che minimizza la funzione

obiettivo. Selezionata la mossa piu appetibile, in fase di attuazione, il relati-

vo valore della funzione obiettivo, viene confrontato con quello associato alla

migliore soluzione corrente, ed in caso di miglioramento della stessa viene

tenuta traccia del numero d’ordine dell’iterazione in questione, del valore

della funzione obiettivo e del loop relativo.

Valutazione dei punti di P/D. Ogni volta che viene eseguita una mossa

vengono ricollocate le stazioni di P/D in funzione del verso di percorrenza del

loop, selezionando la disposizione relativa al verso associato al minor valore

della funzione obiettivo. Per una descrizione dettagliata della procedura di

localizzazione delle stazioni di P/D si faccia riferimento a [22].

Mantenimento della lista tabu variabile. Per evitare l’insorgenza di cicli

nella sequenza delle mosse, ogni qual volta una mossa viene selezionata essa

viene etichettata come tabu. La permanenza di una mossa, fra quelle tabu,

e associata ad un indice di penalizzazione variabile in maniera casuale fra

un numero minimo ed uno massimo di iterazioni della procedura, stabiliti

in fase di settaggio dei parametri dell’euristica. All’atto della valutazione di

una mossa, vengono quindi escluse, dall’insieme delle mosse possibili, tutte

quelle che figurano nella lista tabu. Ad ogni iterazione viene decrementato

di un’unita il valore relativo all’indice di penalita di tutti gli elementi del-

la lista tabu. Una mossa rimane tabu fino a quando il relativo indice di

penalizzazione e diverso dal valore nullo.

Valutazione del criterio di terminazione dell’intensificazione Alla fase

di intensificazione e associato un contatore che indica la distanza, intesa

come numero di iterazioni, dall’ultima mossa migliorativa. Quando il val-

ore di questo contatore raggiunge il valore nD, fissato in fase di settaggio dei

parametri dell’euristica, la fase di intensificazione ha termine, e si avvia la fase


di diversificazione. Questo contatore viene incrementato in corrispondenza

di ogni iterazione che non produce un miglioramento della migliore soluzione

corrente, viene invece azzerato ogni qualvolta la migliore soluzione corrente

e aggiornata, o all’inizio di una nuova fase di intensificazione. La durata di

una singola intensificazione e quindi variabile e dipende dalla frequenza degli

aggiornamenti della migliore soluzione corrente.

Valutazione del criterio di terminazione dell’euristica. In fase di settaggio

dei parametri dell’euristica, viene stabilito il numero complessivo delle iter-

azioni dell’euristica. Quando questo numero viene raggiunto, la procedura di

ricerca ha termine e si produce, come risultato, quello relativo all’iterazione

in corrispondenza della quale si e ottenuta la migliore soluzione corrente.

La valutazione del criterio di terminazione totale e effettuata sia durante

l’intensificazione, che durante la differenziazione.

Diversificazione

La diversificazione e una strategia attuata per far sı che la ricerca si allontani

da quella che e la zona attualmente esplorata dello spazio delle soluzioni, in

modo da cercare di raggiungere delle zone che, per particolari topologie di

layout e particolari matrici di flusso, sono difficilmente raggiungibili seguendo

i normali criteri d’evoluzione. Durante le fasi di diversificazione viene rilas-

sato il vincolo sull’ammissibilita del loop esaminato: vengono presi, cioe, in

considerazione anche quei loop che non toccano in almeno uno spigolo tutte

le celle. Subito dopo ogni fase di diversificazione, la funzione obiettivo con-

siderata diventa la massimizzazione del numero di celle toccate dal loop in

almeno uno spigolo finche questo non raggiunge il numero totale delle celle,

ripristinando coı l’ammissibilita. La valutazione di una mossa, durante le

iterazioni di diversificazione, e basata sui seguenti criteri:

• ripristino delle condizioni in corrispondenza della migliore soluzione

corrente;

• abbandono della condizione di ammissibilita;

• penalizzazione degli archi piu coinvolti nell’intensificazione precedente;


• selezione della mossa a minor funzione obiettivo.

Penalizzazione degli archi. Ad ogni possibile arco del layout viene associato

un contatore che, ad ogni iterazione, viene incrementato di una unita se il

relativo arco e presente nel loop risultante dalla mossa applicata. All’atto

dell’avvio di una diversificazione, gli archi maggiormente utilizzati nell’in-

tensificazione precedente e presenti nel loop associato alla migliore soluzione

corrente, vengono marcati come archi tabu ed allo stesso tempo tutti i con-

tatori associati agli archi vengono azzerati. Da questo momento in poi, per

tutta la durata della diversificazione, e nel corso della successiva intensifi-

cazione, in fase di valutazione della mossa, la presenza di questi archi nei

loop risultanti dalle possibili mosse, comportera una penalizzazione per gli

archi in questione. La penalizzazione, espressa in termini di lunghezza del-

l’arco in questione sara pari alla lunghezza del loop iniziale, il che si tradurra

in un maggior valore della funzione obiettivo, per tutti i loop contenenti gli

archi tabu, in maniera proporzionale al numero di questi inclusi.

Durante la fase di diversificazione, ripristinata la migliore soluzione cor-

rente, e abbandonato il criterio d’ammissibilita nella valutazione delle mosse.

Lo scopo di tale variante e quello di permettere, alla sequenza di soluzioni,

di passare, anche se per un numero di passi limitato, attraverso regioni di

ricerca inammissibili in modo da superare quelle regioni di possibili minimi

locali che possono caratterizzare la ricerca. In queste iterazioni, l’unico cri-

terio guida sara quindi quello della minimizzazione della funzione obiettivo,

che considerando la penalizzazione introdotta sugli archi piu frequentati, nel-

l’intensificazione precedente, tendera a produrre, nel corso delle iterazioni di

diversificazione, l’espulsione degli stessi attraverso la selezione di quelle celle

che li contengono e, di conseguenza, l’allontanamento dalle regioni di minimo

locale in cui la ricerca potrebbe essersi arenata. La penalizzazione degli archi

tabu avra i suoi effetti solo in fase di valutazione della mossa, non sara invece

considerata in fase d’attuazione della stessa. Anche le mosse effettuate du-

rante la diversificazione andranno a far parte della lista tabu che continuera

a condizionare l’evoluzione nel breve periodo, anche durante questa fase, per

gli stessi motivi espressi in precedenza.


La durata della fase di diversificazione e costituita da un numero fissato di

iterazioni, collegato al numero degli archi tabu, e stabilito, come quest’ulti-

mo, in fase di settaggio dei parametri dell’euristica. Qualora, durante la fase

di diversificazione, si giunga ad una soluzione che soddisfi il criterio di ammis-

sibilita, e presenti un valore della funzione obiettivo inferiore a quello della

migliore soluzione corrente, essa andra, come consuetudine, a rimpiazzare la

migliore soluzione corrente.

Al termine della diversificazione ha inizio una nuova fase di intensifi-

cazione che parte dalla soluzione corrente trovata all’ultima iterazione di

diversificazione, non prima pero di aver ripristinato il criterio di ricerca del-

l’ammissibilita. Durante l’intensificazione, la ricerca tiene conto, in fase di

valutazione della mossa, delle penalizzazioni per gli archi tabu. La nuova

fase di intensificazione ha quindi la possibilita di selezionare nuove soluzioni

che potrebbero ora risultare piu appetibili rispetto a quanto poteva essere

durante la precedente intensificazione.

4.5 Risultati computazionali

4.5.1 Gli esperimenti

Al fine di analizzare le prestazioni dei diversi algoritmi proposti, e stata real-

izzata una campagna sperimentale su problemi di diverso tipo. In particolare,

i problemi sono stati generati in modo da esplorare le diverse possibilita in

termini di:

• complessita del block layout

• complessita della rete di flussi richiesti

Per ottenere risultati significativi relativamente al primo punto, sono stati

utilizzati dei block layout di dimensione variabile da un numero minimo di

10 celle fino ad un numero massimo di 40 celle. Conseguentemente, anche il

numero di spigoli e quello dei vertici risultano ben distribuiti.

Per quanto riguarda la complessita dei flussi richiesti, invece, sono stati

presi in esame, per ciascun layout, diverse matrici di flusso con un numero di


elementi non nulli variabile tra un minimo del 10% e un massimo del 100%

del numero complessivo di flussi possibili. Gli elementi non nulli hanno valore

intero uniformemente distribuito tra 1 e 500. Questo aspetto dei problemi

considerati influisce notevolmente sulla complessita del problema da risolvere.

Uno stesso layout con matrice di flusso sparsa oppure densa puo richiedere

tempi di risoluzione che differiscono anche di ordini di grandezza. In ap-

pendice A sono riportati i layout considerati, mentre nella tabella 4.3 sono

riportate le informazioni principali degli esperimenti condotti; in particolare,

sono riportati:

• il nome dato a ciascun esperimento (LX indica il Layout X il cui schema

e riportato in appendice A, mentre FY . indica la variante Y della

matrice dei flussi per il layout considerato)

• il numero di celle del block layout

• il numero di spigoli del block layout

• il numero di vertici del block layout

• il numero di flussi previsti

• la percentuale di elementi non nulli nella matrice dei flussi

• la complessita del problema, intesa come il numero di elementi non nulli

individuati dalla procedura di MIP Presolve impiegata da CPLEX

4.5.2 Taratura del Tabu Search

Ll’algoritmo tabu search realizzato e caratterizzato, come tutti gli algoritmi

basati su questa meta-euristica, da un comportamento che e fortemente in-

fluenzato dai parametri in ingresso all’algoritmo stesso. Nel caso in esame, i

parametri da tarare sono i seguenti:

• numero complessivo di iterazioni;


Esperimento Celle Spigoli Vertici Flussi % flussi Complessita

L1F1 10 16 25 10 11% 2228L1F2 10 16 25 90 100% 13906L2F1 12 19 30 14 11% 3711L2F2 12 19 30 132 100% 25938L3F1 14 24 37 20 11% 6218L3F2 14 24 37 182 100% 43458L4F1 14 26 39 20 11% 6541L4F2 14 26 39 182 100% 45784L5F1 14 25 38 20 11% 6382L5F2 14 25 38 182 100% 44606L6F1 16 27 42 19 8% 6520L6F2 16 27 42 30 12% 9416L6F3 16 27 42 49 20% 14379L6F4 16 27 42 48 20% 14104L6F5 16 27 42 118 49% 32375L6F6 16 27 42 127 53% 35006L6F7 16 27 42 240 100% 64290L6F8 16 27 42 240 100% 64290L7F1 18 33 50 31 10% 11428L7F2 18 33 50 306 100% 96550L7F3 18 33 50 306 100% 96550

Tabella 4.3: Riepilogo esperimenti


• numero di iterazioni senza miglioramento accettabili prima di forzare

la diversificazione;

• numero di iterazioni durante le fasi di diversificazione;

• numero di spigoli tabu;

• permanenza minima nella lista tabu;

• permanenza massima nella lista tabu.

Effettuando un’accurata fase di taratura su un sottoinsieme ben assortito dei

problemi in esame, e stato possibile definire delle linee guida generali per la

definizione dei parametri da impostare:

• nei casi con matrice dei flussi densa, il TS si dimostra particolarmente

efficiente e non richiede, generalmente, fasi di diversificazione;

• nei casi con matrice dei flussi sparsa, il TS richiede, generalmente, una o

piu fasi di diversificazione e, conseguentemente, un numero di iterazioni

maggiore;

• il numero di iterazioni di diversificazione puo essere fissato a 4 indipen-

dentemente dal problema;

• il numero di spigoli tabu puo essere fissato pari a 2 indipendentemente

dal problema;

• la permanenza minima in lista tabu di una mossa e pari a due iterazioni

indipendentemente dal problema;

• la permanenza massima in lista tabu di una mossa cresce con la dimen-

sione del problema.

Sfruttando le linee guida introdotte, i diversi parametri possono essere rica-

vati secondo le seguenti formule:

• numero complessivo di iterazioni: I = (1 + 100−S90

) · C


• numero di iterazioni di intensificazione: II = 23· I

• numero di iterazioni di diversificazione: ID = 4

• numero di spigoli tabu: TE = 2

• minima permanenza in lista tabu: mT = 2

• massima permanenza in lista tabu: MT = 13· C

Poiche i parametri devono essere numeri interi, i risultati delle formule in-

trodotte vanno arrotondate per eccesso.

4.5.3 Risultati

Gli esperimenti descritti nella sezione 4.5.1 sono stati dati in input ai diversi

algoritmi proposti. In particolare, su ciascun problema trattato sono stati

eseguiti i seguenti algoritmi:

1. risoluzione del modello MILP senza aggiunta di tagli con metodo branch

and bound;

2. risoluzione del modello MILP con aggiunta dinamica di tagli utilizzando

il metodo branch and cut;

3. risoluzione del problema con l’euristica tabu search realizzata;

4. risoluzione del modello MILP con aggiunta dinamica di tagli secondo

l’approccio branch and cut, con impiego, come soluzione iniziale, della

soluzione fornita dal TS.

L’algoritmo TS ha un comportamento che puo variare notevolmente al vari-

are dei parametri in ingresso allo stesso. Una trattazione approfondita del

settaggio dei parametri per il TS e riportata nella sezione 4.5.2.

Per ogni algoritmo impiegato, e stato registrato il tempo complessivo di

esecuzione, che corrisponde, rispettivamente, al tempo necessario per:

1. costruzione del modello MILP, risoluzione con branch and bound;


Esperimento MILP B&C TS+B&C TSt (sec) t t risp. t t risp. t % Err %

L1F1 3 3 0%L1F2 377 219 42% 139 63%L2F1

. . .

Tabella 4.4: Risultati

2. costruzione del modello MILP, aggiunta formale di tutti i tagli al mod-

ello, risoluzione con branch and cut;

3. esecuzione di un numero di iterazioni di TS fissato;

4. esecuzione di un numero di iterazioni di TS fissato, costruzione del

modello MILP, aggiunta formale di tutti i tagli al modello, impostazione

della soluzione iniziale, risoluzione con branch and cut.

In tabella 4.4 sono riportati i risultati che sono stati ottenuti.

Bibliografia

[1] P. Afentakis. A loop layout design problem for flexible manufactur-

ing systems. International Journal of Flexible Manufacturing Systems,

(1):175–196, 1989.

[2] J. M. Apple. Plant Layout and Material Handling. Wiley, 1977.

[3] A. Asef-Vaziri, M. Dessouky, and C. Sriskandarajah. A loop material

flow system design for automated guided vehicles. The International

Journal of Flexible Manufacturing Systems, (33):33–48, 2001.

[4] A. Asef-Vaziri, G. Laporte, and C. Sriskandarajah. The block layout

shortest loop design problem. IIE Transactions, (32):727–734, 2000.

[5] Y. A. Bozer and M. M. Srinivasan. Tandem configurations for auto-

mated guided vehicle systems offer simplicity and flexibility. Industrial

Engineering, (21):23–27, 1989.

[6] L. R. Foulds and D. F. Robinson. Graph theoretic heuristics for the

plant layout problem. International Journal of Production Research,

(16):27–37, 1978.

[7] R. L. Francis, L. F. McGinnis, and J. A. White. Facility Layout and

Location: An Analytical Approach. Prentice-Hall, 1992.

[8] T. Ganesharajah, N. G. Hall, and C. Sriskandarajah. Design and

operational issues in AGV-served manufacturing systems. Annals of

Operations Research, (76):109–154, 1998.

68

BIBLIOGRAFIA 69

[9] R. J. Gaskins and J. M. A. Tanchoco. Flow path design for automated

guided vehicle systems. International Journal of Production Research,

25(5):667–676, 1987.

[10] F. Glover. Tabu search, part I. ORSA Journal on Computing, 1(3):190–

206, 1989.

[11] F. Glover and M. Laguna. Tabu search. In C. Reeves, editor, Mod-

ern Heuristic Techniques for Combinatorial Problems, Oxford, England,

1993. Blackwell Scientific Publishing.

[12] S. Heragu. Facilities Design. PWS Publishing Company, 1997.

[13] M. Kaspi and J. M. A. Tanchoco. Optimal flow path design of unidi-

rectional AGV systems. International Journal of Production Research,

28(6):915–926, 1990.

[14] A. S. Kiran and S. Karabati. Exact and approximate algorithms for

the loop layout problem. Journal of Production Planning and Control,

(4):253–259, 1993.

[15] P. Kouvelis and M. W. Kim. Unidirectional loop network layout problem

in automated manufacturing systems. Operations Research, (40):533–

550, 1992.

[16] W. L. Maxwell and J. A. Muckstadt. Design automated vehicle systems.

IIE Transactions, (2):114–124, 1982.

[17] R. Muther. Systematic Layout Planning. Management and Industrial

Research Publications, 1973.

[18] L. M. Nicol and R. H. Hollier. Plant layout in practice. Material flow,

1:177–188, 1983.

[19] D. Sinriech and J. M. A. Tanchoco. Solution methods for the mathe-

matical models of single-loop AGV systems. International Journal of

Production Research, 31(3):705–725, 1993.

BIBLIOGRAFIA 70

[20] D. Sinriech, J. M. A. Tanchoco, and Y. T. Herer. The segment-

ed bi-directional single-loop topology for material flow systems. IIE

Transactions, 28:40–54, 1996.

[21] D. R. Sule. Manufacturing Facilities: Location, Planning & Design.

PWS Publishing Company, 1991.

[22] J. M. A. Tanchoco and D. Sinriech. OSL - optimal single-loop

guide paths for AGVS. International Journal of Production Research,

30(3):665–681, 1992.

[23] B. C. Tansel and C. Bilen. Move based heuristics for the unidirectional

loop network layout problem. European Journal of Operational Research,

(108):36–48, 1998.

[24] A. Tompkins, J. A. White, Y. A. Bozer, E. H. Frazelle, J. M. A.

Tanchoco, and J. Trevino. Facilities Planning. Wiley, 1996.

[25] J. S. Usher, G. W. Evans, and M. R. Wilhelm. AGV flow path design

and load transfer point location. Proceedings of the 1998 IIE Conference,

pages 174–179, 1988.

Appendice A

Layout utilizzati

Vengono di seguito riportati gli schemi dei layout impiegati nella campagna

sperimentale illustrata nella sezione 4.3 relativa agli algoritmi per il problema

SLDP.

71

APPENDICE A. LAYOUT UTILIZZATI 72

Figura A.1: Layout 1

Figura A.2: Layout 2

tesi

Documents

Transcript of tesi