tesi

Problemi di ottimizzazione

nel Facility Design

Tesi di Dottorato

in Ricerca Operativa - XV Ciclo

Universita della Calabria - Rende (CS)

Pierpaolo Caricato

Indice

Introduzione 7

I problemi di Facility Design . . . . . . . . . . . . . . . . . . . 7

Struttura del lavoro di tesi . . . . . . . . . . . . . . . . . . . . 8

1 Problemi di Facility Layout 10

1.1 Systematic Layout Planning . . . . . . . . . . . . . . . . . . . 11

1.1.1 Misurazione dei flussi (Diagrammi From-To) . . . . . . 12

1.1.2 Analisi Attivita/Relazioni (Diagrammi REL) . . . . . . 15

1.1.3 Progettazione del layout fisico . . . . . . . . . . . . . . 16

1.2 Modelli matematici per i problemi di FL . . . . . . . . . . . . 21

1.2.1 QAP* . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.2.2 ABSMODEL* . . . . . . . . . . . . . . . . . . . . . . . 23

2 Problemi di Material Handling 29

2.1 Topologie per il Material Handling . . . . . . . . . . . . . . . 30

2.2 Stato dell’arte nelle configurazioni basate su loop . . . . . . . 30

2.2.1 SSP - Station Sequencing Problem . . . . . . . . . . . 31

2.2.2 CLP - Cell Location Problem . . . . . . . . . . . . . . 32

2.2.3 LCP - Loop Configuration Problem . . . . . . . . . . . 34

2.2.4 TCP - Tandem Configuration Problem . . . . . . . . . 35

3 Single Loop Design Problem (SLDP) 37

3.1 Formulazione MILP . . . . . . . . . . . . . . . . . . . . . . . . 40

3.2 Branch and cut . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.2.1 Tagli aggiuntivi di tipo 1 . . . . . . . . . . . . . . . . . 44

1

INDICE 2




3.2.5 Algoritmo Branch & Cut . . . . . . . . . . . . . . . . . 48

4 Tabu Search per lo SLDP 50

4.1 Le meta-euristiche Tabu Search . . . . . . . . . . . . . . . . . 50

4.1.1 Descrizione . . . . . . . . . . . . . . . . . . . . . . . . 51

4.1.2 Attributi di mossa e restrizioni tabu . . . . . . . . . . . 53

4.1.3 Criteri di aspirazione . . . . . . . . . . . . . . . . . . . 55

4.1.4 Strategia basata sulla frequenza delle mosse e delle

soluzioni . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.1.5 Intensificazione e diversificazione . . . . . . . . . . . . 58

4.1.6 Target Analysis . . . . . . . . . . . . . . . . . . . . . . 60

4.1.7 Diversificazione basata sulla distanza . . . . . . . . . . 61

4.1.8 Generazione di nuovi punti di partenza . . . . . . . . . 62

4.1.9 Tabu Search con liste dinamiche . . . . . . . . . . . . . 63

4.2 Implementazione del TS nello SLDP . . . . . . . . . . . . . . 64

4.2.1 Mossa . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

4.2.2 Soluzione iniziale . . . . . . . . . . . . . . . . . . . . . 65

4.2.3 Funzione obiettivo . . . . . . . . . . . . . . . . . . . . 66

4.2.4 Intensificazione . . . . . . . . . . . . . . . . . . . . . . 67

4.2.5 Diversificazione . . . . . . . . . . . . . . . . . . . . . . 68

5 Risultati computazionali 71

5.1 Gli esperimenti . . . . . . . . . . . . . . . . . . . . . . . . . . 71

5.2 Taratura del Tabu Search . . . . . . . . . . . . . . . . . . . . 72

5.3 Risultati* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Conclusioni e sviluppi futuri 79

Conclusioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

Sviluppi futuri . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

Bibliografia 81

INDICE 3

A Layout utilizzati* 86

N.B.

I capitoli contrassegnati con * saranno integrati, nella versione definitiva, con

ulteriori contenuti

Elenco delle figure

1.1 Matrici From-To . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.2 Confronto tra matrici from-to . . . . . . . . . . . . . . . . . . 15

1.3 Diagramma REL . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.4 Layout e diagramma REL . . . . . . . . . . . . . . . . . . . . 18

1.5 Grafo planare . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.6 Grafi non-planari . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.7 Facce di un grafo planare . . . . . . . . . . . . . . . . . . . . . 19

1.8 Duale di un grafo planare . . . . . . . . . . . . . . . . . . . . 20

1.9 Diverse rappresentazioni planari . . . . . . . . . . . . . . . . . 21

1.10 Layout di un aeroporto . . . . . . . . . . . . . . . . . . . . . . 22

1.11 Layout su singola linea . . . . . . . . . . . . . . . . . . . . . . 23

1.12 Facility ben approssimabili . . . . . . . . . . . . . . . . . . . . 24

1.13 Facility poco approssimabili . . . . . . . . . . . . . . . . . . . 24

1.14 Parametri e variabili decisionali nel FL su singola linea . . . . 25

1.15 Esempio di layout a linea singola . . . . . . . . . . . . . . . . 26

1.16 Parametri e variabili decisionali negli ABSMODEL 2 . . . . . 27

2.1 Configurazioni per la movimentazione dei materiali . . . . . . 31

2.2 Esempio di layout con 7 celle posizionate intorno ad un loop . 33

2.3 Esempio di layout generale con sistema di movimentazione a

loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.1 Flussi tra celle disgiunte . . . . . . . . . . . . . . . . . . . . . 45

3.2 Flussi tra celle confinanti . . . . . . . . . . . . . . . . . . . . . 46

3.3 Flussi tra vertici di frontiera . . . . . . . . . . . . . . . . . . . 48

4

ELENCO DELLE FIGURE 5

4.1 Andamento della f.o. in un TS . . . . . . . . . . . . . . . . . . 52

4.2 Esempio d XOR su celle . . . . . . . . . . . . . . . . . . . . . 65

4.3 Layout non servibile con un unico loop . . . . . . . . . . . . . 66

A.1 Layout 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

A.2 Layout 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

Elenco delle tabelle

1.1 ABSMODEL 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 26

1.2 ABSMODEL 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.1 Formulazione MILP . . . . . . . . . . . . . . . . . . . . . . . . 42

5.2 Riepilogo esperimenti . . . . . . . . . . . . . . . . . . . . . . . 73

5.3 Parametri del Tabu Search . . . . . . . . . . . . . . . . . . . . 76

5.4 Risultati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

6

Introduzione

I problemi di Facility Design

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 (Heragu, 1997). Nel

settore manifatturiero, ad esempio, facility possono essere macchinari, work-

station, 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

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

7

ELENCO DELLE TABELLE 8

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 (Sule, 1991). I problemi relativi alla movi-

mentazione dei materiali sono noti in letteratura come Material Handling

Problems.

Struttura del lavoro di tesi

I problemi di Facility Design Il lavoro di tesi affronta le complesse problem-

atiche relative al FD fornendo un approfondito studio dello stato dell’arte;

viene quindi proposto un contributo originale e migliorativo dello stato del-

l’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

ELENCO DELLE TABELLE 9

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

FL, mentre il capitolo 2 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 alterna-

tiva a quella recentemente introdotta. Viene quindi proposto un approccio

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

lazione, consente la risoluzione di istanze del problema di medie dimensioni.

Viene, quindi, proposto un metodo risolutivo euristico basato sul Tabu Search

che permette la risoluzione di istanze del problema di grandi dimensioni. La

validita dell’euristica prodotta viene provata tramite confronto con i risultati

ottenuti utilizzando l’algoritmo esatto nei casi di piccola e media dimensione.

Capitolo 1

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 (Nicol

and Hollier, 1983). La frequenza con cui si sono avuti cambiamenti nei lay-

out aziendali e aumentata nelle ultime decadi a causa dei cambiamenti nei

product mix che sono accaduti 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 oggetti

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-

10

CAPITOLO 1. PROBLEMI DI FACILITY LAYOUT 11

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.

1.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 (Muther,

1973), 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.

1.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 necessiti 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 1.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 1.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 1.1b e un esempio di matrice con soli flussi ordinati, mentre

le figure 1.1c e 1.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 1.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 1.2: Confronto tra matrici from-to

Pertanto, la matrice in figura 1.2b e da preferire a quella in figura 1.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).

1.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 1.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 1.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.

1.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 1.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 1.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 interessati soltanto ai grafi planari, in quanto sono

gli unici a cui e possibile assegnare un layout.

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

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

con archi che si intersecano e riportato in forma planare.


Figura 1.4: Layout e diagramma REL

Figura 1.5: Grafo planare


Figura 1.6: Grafi non-planari

Figura 1.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 1.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

1.7 e riportato il grafo planare della figura 1.4 con l’aggiunta dell’indicazione

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


Figura 1.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 1.8 e riportato il grafo planare

della figura 1.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 utilizzata, il duale

corrispondente puo essere anche molto diverso. In figura 1.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 1.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 Foulds

and Robinson, 1978.

1.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 necessariamente 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 aeroporto (figura 1.10). Tipicamente, un aereo che arriva in aeroporto

trasporta sia passeggeri per i quali l’aeroporto considerato e la destinazione

finale, sia passeggeri in transito verso altre destinazioni. Nell’arco di poche

ore, molti aerei possono atterrare nell’aeroporto. E’ necessario, quindi, min-

imizzare la distanza complessiva che i passeggeri devono coprire, a piedi,

nell’aeroporto (al fine, ad esempio, di ridurre i disagi per i passeggeri stessi),

cercando di assegnare a gate adiacenti voli con forte interazione.

1.2.1 QAP*

1.2.2 ABSMODEL*

ABSMODEL 1

I modelli ABSMODEL 1 sono una formalizzazione del problema di FL su

singola linea tramite un modello non lineare, ma linearizzabile mediante l’in-

troduzione 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 1.11;

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


Figura 1.10: Layout di un aeroporto

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 1.12, o in maniera rilevante, nei casi come quelli

Figura 1.11: Layout su singola linea


Figura 1.12: Facility ben approssimabili

Figura 1.13: Facility poco approssimabili

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

forme come quelle in figura 1.13 sono piuttosto rari.

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 essere 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;


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

`i 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 1.14.

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

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

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

facility.


minn−1∑i=1

n∑j=i+1

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

s.v.

|xi − xj| ≥1

2(ì + `j) + dij i = 1, 2, . . . , n− 1 j = i + 1, . . . , n (1.2)

Tabella 1.1: ABSMODEL 1

Figura 1.15: Esempio di layout a linea singola

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 1.3:

H − 1

2ì ≥ xi ≥

1

2ì i = 1, 2, . . . , n (1.3)

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

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

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

Si noti che il vincolo 1.3 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,

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


minn−1∑i=1

n∑j=i+1

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

s.v.

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

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

Tabella 1.2: ABSMODEL 2

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 multi-linea,

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

introdotto in 1.2.1, 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

orizzontale (Horizontal Reference Line - HRL).

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

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

1.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 1.5 e 1.6 assicurano che le facility non si sovrappongano. Il

vincolo di integrita 1.6 non e imposto per garantire l’integrita delle variabili,


Figura 1.16: Parametri e variabili decisionali negli ABSMODEL 2

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

una soluzione ammissibile rilassando il set di vincoli 1.6 che abbia i seguenti

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

vincoli 1.5, 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 2

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 Apple, 1977 viene messo in evidenza quanto sia fon-

damentale affrontare le problematiche relative ai sistemi di movimentazione

gia nella progettazione del layout. In Tompkins et al., 1996 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 effet-

tuare 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 Francis

et al., 1992 per una panoramica d’insieme sui problemi di MH e a Ganeshara-

jah et al., 1998 per lo stato dell’arte nell’ambito dei sistemi di movimentazione

basati su veicoli a guida automatica. Un particolare rilievo e dato, sia in let-

teratura che nell’utilizzo aziendale (come riportato in Afentakis, 1989), 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.

30

CAPITOLO 2. PROBLEMI DI MATERIAL HANDLING 31

2.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 2.1a): introdotta da Maxwell

and Muckstadt, 1982, consiste in una rete unidirezionale che copre tutti

gli spigoli del layout;

• loop unidirezionale (figura 2.1b): esaminata in Tanchoco and Sinriech,

1992, permette una gestione semplificata delle collisioni tra i veicoli,

che puo risultare comunque complicata se il numero di veicoli richiesti

e elevato;

• configurazione tandem (figura 2.1c): introdotta in Bozer and Srini-

vasan, 1989, consiste nella scomposizione della rete di flussi di materiali

in piu sotto-reti, ciascuna servita da un unico veicolo che circola su di

un loop, collegate tramite punti di trasbordo;

• loop segmentato (figura 2.1d): esaminato in Sinriech et al., 1996, con-

siste in una configurazione loop “spezzato” su diverse tratte, ognuna

servita da un singolo veicolo.

2.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 viaggi.

Le problematiche relative alla progettazione dei sistemi di movimentazione

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


(a) rete convenzionale unidirezionale (b) loop unidirezionale

(c) configurazione tandem (d) loop segmentato

Figura 2.1: Configurazioni per la movimentazione dei materiali

2.2.1 SSP - Station Sequencing Problem

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 1.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 Afentakis, 1989 ed e stato

dimostrato essere NP-hard in Kouvelis and Kim, 1992. Sia pij il flusso atteso

dalla cella i verso la cella j e sia definito cij = pji − pij (i < j). La variabile

binaria xij assume valore unitario se e solo se alla cella i viene assegnata la

posizione k e alla cella j la posizione ` con k < `. La formulazione dell’SSP

e allora:


min∑i<j

pij +∑i<j

cijxij

s.v.xij + xjk − xik ≤ 1 (i<j<k)

xij − xjk + xik ≤ 0 (i<j<k)

xij ∈ {0; 1}

In Afentakis, 1989, l’SSP viene risolto in maniera euristica attraverso

una procedura di scambio. Mediante l’impiego delle relazioni di dominanza

introdotte in Kouvelis and Kim, 1992 e stato possibile ridurre lo spazio delle

soluzioni da esplorare e quindi e stata sviluppata una procedura euristica

piu efficiente e un algoritmo di tipo branch and bound in grado di risolvere

istanze con un massimo di 12 celle. In Kiran and Karabati, 1993 vengono

proposte delle relazioni di dominanza alternative e viene individuato un caso

di SSP risolvibile in tempo polinomiale; viene inoltre sviluppata un’euristica

e un algoritmo esatto, sperimentato su layout con al piu 12 celle.

E’ stata anche data una formulazione dell’SSP come caso particolare del

problema di assegnamento quadratico (QAP) in Kiran and Karabati, 1993,

mentre in Tansel and Bilen, 1998 e stata proposta una procedura euristica

di post-ottimizzazione basata sugli scambi. Ai fini pratici, tuttavia, e possi-

bile risolvere esattamente solo istanze piccole del QAP (vedi 1.2.1). E’ raro

trovare risolti problemi con piu di 20 celle, anche se esistono lavori recenti sul

QAP, come Anstreicher et al., 2002, che migliorano l’efficienza degli algoritmi

risolutivi, sfruttando anche le architetture basate su griglie computazionali.

2.2.2 CLP - Cell Location Problem

Mentre nell’SSP le caratteristiche geometriche delle celle vengono ignorate,

il problema noto in letteratura come CLP - Cell Location Problem ne tiene

conto. Il problema consiste nella determinazione della posizione, della dimen-

sione e dell’orientamento di n celle in modo tale che esse siano servibili da un

loop con l’obiettivo di minimizzare i costi di trasporto complessivi. Se, come


Figura 2.2: Esempio di layout con 7 celle posizionate intorno ad un loop

nel caso di edifici senza vincoli di spazio occupabile, tutte le celle possono

essere posizionate intorno (al di fuori) di un loop, allora il CLP puo essere

ricondotto ad SSP (come, ad esempio, in figura 2.2). In un layout generale, in

cui non e possibile distanziare ugualmente le stazioni, i costi di trasporto non

possono essere ridotti al semplice conteggio del numero di passaggi di ogni

parte dalla stazione 0, ma devono essere calcolati come distanza complessiva

percorsa da tutte le parti.

Il CLP e, in generale, piu complesso in quanto le celle possono essere po-

sizionate sia all’interno che all’esterno del loop (come illustrato in figura 2.3).

Sono state studiate diverse varianti del problema. Un articolo fondamentale

e Montreuil, 1991, dove viene proposta una formulazione MILP per la pro-

gettazione integrata del layout e del sistema di movimentazione. Si assume

che la forma delle celle sia rettangolare, ma le loro dimensioni sono assunte

essere variabili decisionali del problema. Il modello proposto e piu flessibile

dell’approccio tradizionale tramite QAP, ma, anche in questo caso, e possi-

bile risolvere solo istanze di problema molto piccole. Definendo la distanza

tra le celle come la distanza tra i rispettivi centroidi, in Tompkins et al., 1996

e stata risolta un’istanza con layout a 8 celle utilizzando la formulazione di

Montreuil, 1991. Procedure euristiche basate su algoritmi genetici sono stati

proposti in Das, 1993 ed in Rajeasekharan et al., 1998 per risolvere istanze

di dimensioni maggiori.

In Goetschalckx and Palliyil, 1994 viene risolta una versione semplificata


Figura 2.3: Esempio di layout generale con sistema di movimentazione a loop

del problema, in cui il block layout e noto. Viene sviluppata una formulazione

MILP per localizzare un loop che copra almeno uno spigolo di ciascuna cella

e per posizionare i punti di P/D. Sono considerate ammissibili soluzioni con

archi bidirezionali e con celle con piu punti di P/D. La funzione obiettivo

comprende un contributo relativo alla costruzione del loop ed uno relativo

alle movimentazioni effettuate sia a vuoto che a pieno carico. E’ possibile

risolvere solo problemi di piccole dimensioni (inferiori a 15 celle).

In Banerjee and Zhou, 1995 viene adattata la formulazione presentata in

Montreuil, 1991 per trattare una configurazione a loop unidirezionale, con un

solo punto di P/D per ogni cella e con funzione obiettivo la minimizzazione

delle distanze percorse a pieno carico. Viene introdotta una procedura per

identificare sequenze di punti di P/D promettenti per essere visitate in ordine.

Infine, in Chae and Peters, 2000 viene proposta una procedura di tipo sim-

ulated annealing per il CLP con celle rettangolari e punti di P/D combinati

e posizionati sui vertici delle celle.

2.2.3 LCP - Loop Configuration Problem

La configurazione a singolo loop (vedi figura 2.1 e stata originariamente imp-

iegata su larga scala per i sistemi a nastro trasportatore (vedi Muth, 1972,

Muth, 1974 e Muth, 1975). La sua applicazione ai sistemi basati su AGV e

recente: l’articolo Tanchoco and Sinriech, 1992 puo essere preso come rifer-

imento iniziale. Viene presa in esame la progettazione di un sistema a loop

unidirezionale su di un layout assegnato; vengono considerati due obiettivi:


la minimizzazione della lunghezza del loop e la minimizzazione del tempo (o

della distanza) richiesto per effettuare tutte le movimentazioni richieste.

Il problema noto in letteratura come LCP - Loop Configuration Problem

consiste nella determinazione del loop di lunghezza minima che comprenda

almeno uno spigolo per ciascuna cella. In DeGuzman et al., 1997 e stato

provato che il problema e NP-hard. La sua formulazione fornita in Tanchoco

and Sinriech, 1992 e di tipo MILP con vincoli di grado sui nodi e vincoli

di eliminazione di sotto-loop, come nel TSP. Nello stesso lavoro viene anche

sviluppata una procedura enumerativa basata sull’eliminazione delle soluzioni

dominate (vedi 3). Una trattazione piu approfondita di questo problema e

riportata nel capitolo 3.

2.2.4 TCP - Tandem Configuration Problem

Dato il block layout di un impianto, la matrice dei flussi previsti e la posizione

dei punti di P/D, il problema noto in letteratura come TCP - Tandem Con-

figuration Problem consiste nel partizionamento del flusso complessivo su piu

insiemi di loop indipendenti, ognuno servito da un singolo veicolo. La po-

sizione dei loop non e necessariamente vincolato agli spigoli delle celle: una

griglia viene sovrapposta, infatti, al layout e i loop vengono definiti su di

essa.

La configurazione tandem e stata introdotta per la prima volta in Bozer

and Srinivasan, 1989. Gli stessi autori, in Bozer and Srinivasan, 1991, hanno

presentato una procedura euristica basata sulla generazione di un insieme di

loop promettenti e sulla selezione di un sottoinsieme ottimo per mezzo di un

algoritmo di partizionamento. Infine, sempre gli stessi autori, in Bozer and

Srinivasan, 1992, hanno esaminato le prestazioni delle configurazioni tandem

rispetto alle configurazioni tradizionali, provandone la maggiore efficienza con

l’aumentare dei numeri di AGV utilizzati.

In Choi et al., 1994 e stato sviluppato un modello di simulazione per

confrontare configurazioni a singolo loop e tandem: il loop singolo ha tempi

di lavoro e di inutilizzo minori, ma la configurazione tandem presenta una

frequenza di completamento dei lavori maggiore. In Lin et al., 1994 e sta-


to misurato l’impatto dell’instradamento dei carichi sulle performance delle

configurazioni tandem. In Bischak and Stevens, 1995, infine, utilizzando la

simulazione, e stato dimostrato che i sistemi tandem hanno un tempo di la-

voro per carico maggiore rispetto alla configurazione a singolo loop: questo

avviene a causa dei tempi extra richiesti per il trasferimento dei carichi tra

diversi loop.

Capitolo 3

Single Loop Design Problem

(SLDP)

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:

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

flussi tra i diversi reparti;

38

CAPITOLO 3. SINGLE LOOP DESIGN PROBLEM (SLDP) 39

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

per eseguire le consegne.

In Gaskins and Tanchoco, 1987 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 Usher et al., 1988 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

Gaskins and Tanchoco, 1987 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 pro-

posta e molto onerosa computazionalmente col crescere del numero di reparti

e, comunque, non fornisce la soluzione ottima. Per poter ottenere l’ottimal-

ita, infatti, e necessario considerare contemporaneamente la progettazione

dei percorsi guida per gli AGV e il posizionamento dei punti di P/D.

In Kaspi and Tanchoco, 1990, vengono considerati assegnati il layout

dell’impianto e la posizione dei punti di P/D e viene proposta una formu-

lazione del problema dell’individuazione 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 Tanchoco and Sinriech, 1992. 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 Sinriech and Tanchoco, 1993.

In Asef-Vaziri et al., 2000 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’individ-

uazione del loop di lunghezza minima. Viene data una formulazione come

problema di programmazione lineare intera con un numero di vincoli inizial-

mente molto elevato; vengono quindi proposti dei metodi per la riduzione dei

vincoli effettivamente 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 Asef-Vaziri et al., 2001. Viene fornita una formulazione del proble-

ma di tipo ILP che determini contemporaneamente il percorso guida per gli

AGV, comprensivo 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 no-

di da esplorare sfruttando le caratteristiche del problema. Gli esperimenti

condotti riguardano layout con 11 e 20 celle e matrici di flusso sparse, carat-

terizzate 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.

3.1 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 3.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;

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

cella c.

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

di materiali nell’impianto.


min∑

(i,j)∈E

∑(c,d)∈Φ

lij · fcd · xijcd (3.1)

s.v.

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

yij ≥ 1 ∀c ∈ C (3.3)

∑i∈Vc

zci = 1 ∀c ∈ C (3.4)

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

i

yij +∑

(j,i)∈EIi

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

∑(j,i)∈EI

i

yji ≤ 1 ∀i ∈ V (3.7)

∑(i,j)∈EO

i

yij ≤ 1 ∀i ∈ V (3.8)

∑(j,i)∈EI

i

yji ≥ zi ∀i ∈ V (3.9)

∑(i,j)∈EO

i

yij ≥ zi ∀i ∈ V (3.10)

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

i

xijcd −∑

(j,i)∈EIi

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

∑(c,d)∈Φ

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

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

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

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

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

Tabella 3.1: Formulazione MILP


La sussistenza delle ipotesi di base del problema SLDP sono assicurate

dai set di vincoli 3.2, 3.3 e 3.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 3.2. Inoltre, ogni cella deve

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

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

set di vincoli 3.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 3.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 3.6).

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

di vincoli 3.7) e al piu uno uscente (set di vincoli 3.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 3.9 e 3.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 3.11).

Il set di vincoli 3.12 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 3.12, 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 3.13.

3.2 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) ∈ Φ.

3.2.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 3.1, ad esempio, sullo spigolo orientato evidenziato


Figura 3.1: Flussi tra celle disgiunte

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 (3.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

riportato in figura 3.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,


Figura 3.2: Flussi tra celle confinanti

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 (3.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 (3.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 3.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 3.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 (3.21)

∑(j,i)∈EI

i

xjicd+xjidc ≤ 2−zck−zdk ∀(c, d) ∈ N∩Φ′, ∀i ∈ V, ∀k ∈ Vc∩Vd (3.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

(3.23)

La relazione 3.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


Figura 3.3: Flussi tra vertici di frontiera

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

Nel caso in figura 3.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.

3.2.5 Algoritmo Branch & Cut

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

ello matematico presentato nella sezione 3.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.

Capitolo 4

Tabu Search per lo SLDP

4.1 Le meta-euristiche Tabu Search

La Tabu Search (TS), presentato da Glover in Glover, 1989, e una proce-

dura meta-euristica utilizzabile per risolvere un’ampia classe di problemi di

ottimizzazione. La caratteristica principale della TS e di consentire al pro-

cesso risolutivo di uscire da situazioni di stallo, costituite dal raggiungimen-

to di punti di ottimo locale. Questo obiettivo viene conseguito grazie alle

tecniche di auto-apprendimento che contraddistinguono la TS. Le direzioni

lungo cui effettuare 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)

51

CAPITOLO 4. TABU SEARCH PER LO SLDP 52

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.

4.1.1 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.1, 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

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.


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.1: Andamento della f.o. in un TS


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.

4.1.2 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.

4.1.3 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 Glover and Laguna, 1993. Una mossa

che coinvolga un attributo 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.


4.1.4 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

sotto-sequenza. 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.

4.1.5 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 Glover and Laguna, 1993 hanno suggerito dei criteri per

caratterizzare tali sequenze. Sia Z(k) = (z(1), z(2), . . . , z(k)) una sequenza

di k soluzioni. Tale sequenza viene definita sequenza di diversificazione se,

definita una metrica nello spazio delle soluzioni, Z(k) e costituita da sotto-

sequenze 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.

4.1.6 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.

4.1.7 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.

4.1.8 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.

4.1.9 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.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.


Figura 4.2: Esempio d XOR su celle

4.2.1 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.2, che rappresenta

l’operazione di XOR sulla cella 6 del layout in esame nel loop considerato.

4.2.2 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.3, riportato in letteratura in Asef-Vaziri et al., 2000: in questo caso


Figura 4.3: Layout non servibile con un unico loop

e evidentemente impossibile identificare un unico loop che contenga almeno

uno spigolo di ciascuna cella.

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 considerato 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.

4.2.3 Funzione obiettivo

La funzione obiettivo, da minimizzare, e costituita dalle movimentazioni com-

plessive generate 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 Tanchoco and Sinriech, 1992. 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.


4.2.4 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 val-

ore della funzione obiettivo. Per una descrizione dettagliata della procedura

di localizzazione delle stazioni di P/D si faccia riferimento a Tanchoco and

Sinriech, 1992.

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.

4.2.5 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 cosı 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.

Capitolo 5

Risultati computazionali

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

72

CAPITOLO 5. RISULTATI COMPUTAZIONALI 73

tempi di risoluzione che differiscono anche di ordini di grandezza. In ap-

pendice A sono riportati i layout considerati, mentre nella tabella 5.2 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

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;

• numero di iterazioni senza miglioramento accettabili prima di forzare

la diversificazione;

• numero di iterazioni durante le fasi di diversificazione;

• numero di spigoli tabu;


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 5.2: Riepilogo esperimenti


• 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.

Indicando con C il numero di celle di cui e composto il layout e con S la

percentuale di elementi non nulli nella matrice dei flussi, sfruttando le linee

guida introdotte e possibile ricavare i valori dei parametri del tabu search

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

introdotte vanno arrotondate all’intero piu vicino.

In tabella 5.3 sono riportati i parametri impiegati per risolvere, con l’al-

goritmo Tabu Search realizzato, gli esperimenti descritti nella sezione 5.1 e

riassunti in tabella 5.2.

5.3 Risultati*

Gli esperimenti descritti nella sezione 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 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 C S I II ID TE mT MT

L1F1 10 10 20 13 4 2 2 3L1F2 10 100 10 7 4 2 2 3L2F1 12 10 24 16 4 2 2 4L2F2 12 100 12 8 4 2 2 4L3F1 14 10 28 19 4 2 2 5L3F2 14 100 14 9 4 2 2 5L4F1 14 10 28 19 4 2 2 5L4F2 14 100 14 9 4 2 2 5L5F1 14 10 28 19 4 2 2 5L5F2 14 100 14 9 4 2 2 5L6F1 16 10 32 21 4 2 2 5L6F2 16 10 32 21 4 2 2 5L6F3 16 20 30 20 4 2 2 5L6F4 16 20 30 20 4 2 2 5L6F5 16 50 25 17 4 2 2 5L6F6 16 50 25 17 4 2 2 5L6F7 16 100 16 11 4 2 2 5L6F8 16 100 16 11 4 2 2 5L7F1 18 10 36 24 4 2 2 6L7F2 18 100 18 12 4 2 2 6L7F3 18 100 18 12 4 2 2 6L8F1 24 10 48 32 4 2 2 8L8F2 24 10 48 32 4 2 2 8L8F3 24 20 45 30 4 2 2 8L8F4 24 20 45 30 4 2 2 8L8F5 24 50 37 25 4 2 2 8L8F6 24 50 37 25 4 2 2 8L8F7 24 100 24 16 4 2 2 8L8F8 24 100 24 16 4 2 2 8

Tabella 5.3: Parametri del Tabu Search


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 5.4 sono riportati i risultati che sono stati ottenuti.

CAPITOLO 5. RISULTATI COMPUTAZIONALI 79E

sp.

B&

BB

&C

TS

Tem

po

Tag

liTem

po

F.O

.Tem

po

Sec

.R

isp.

Dis

p.

Usa

tiF.O

.E

rr.

Sec

.R

isp.

L1F

153

623

30%

00

5820

9%37

<0

L2F

117

984

55

0%52

81

1828

72%

98<

0L3F

180

448

505

105

79%

628

303

8364

74%

196

61%

L5F

153

329

6829

57%

456

440

5332

90%

378

<0

L6F

135

034

121

3503

40%

391

L4F

163

189

7634

55%

468

440

6422

92%

276

<0

L6F

266

611

727

6661

10%

982

L7F

113

3096

928

266

71%

856

420

1330

960%

404

56%

L1F

218

2473

377

219

42%

6180

1458

2002

7810

%21

94%

L6F

410

0175

868

1001

750%

L6F

310

4958

649

1049

580%

402

L2F

242

1759

3664

486

87%

1123

227

2448

0435

14%

7098

%L6F

532

8700

1234

3287

000%

483

L6F

636

1938

2514

3619

380%

275

L3F

297

9853

2802

343

5484

%18

988

5813

9798

530%

9810

0%L5F

280

8668

1157

927

4876

%19

400

4583

8086

680%

325

97%

L4F

271

3469

1042

319

4081

%20

096

3853

7134

690%

154

99%

L6F

773

0663

5721

7332

020%

184

L6F

881

6433

1534

181

6433

0%23

5L7F

219

0070

016

574

1900

700

0%45

0

Tab

ella

5.4:

Ris

ultat

i

Conclusioni e sviluppi futuri

Conclusioni

Il lavoro di tesi ha permesso di individuare un’interessante area di ricerca,

nell’ambito del Facility Design, in cui e stato possibile fornire un contrib-

uto innovativo e originale: la progettazione di sistemi di movimentazione

basati su veicoli a guida automatica (AGV) in configurazione a loop singolo

unidirezionale.

E’ stato fornito un modello di programmazione lineare intera mista per la

formulazione del problema. La risoluzione dello stesso con risolutori matem-

atici standard, tramite l’algoritmo di branch and bound, permette di trattare

problemi di dimensione piccola e media (al piu 16 celle). Il modello ha comp-

lessita decrescente al decrescere del numero di elementi non nulli nella matrice

dei flussi che caratterizza il sistema, consentendo, nel caso di matrici sparse,

di risolvere in maniera ottimale problemi con un numero maggiore di celle.

La formulazione MILP del problema puo essere arricchita mediante l’u-

tilizzo di disuguaglianze valide aggiuntive. L’introduzione dinamica di tali

disuguaglianze in un approccio di tipo branch and cut permette di ridurre

notevolmente i tempi di risoluzione. L’impiego dell’algoritmo branch and cut

ad hoc realizzato permette di trattare problemi con un numero di celle mag-

giore. Anche in questo caso, i tempi di esecuzione scalano proporzionalmente

con il numero di elementi non nulli nella matrice dei flussi.

Infine, per permettere la risoluzione di problemi con un numero di celle

elevato, e stato implementato un algoritmo di tipo Tabu Search. La validita

di questo algoritmo si e dimostrata complementare agli algoritmi esatti. Il

80


TS realizzato, infatti, e caratterizzato da tempi di esecuzione che, a parita di

numero di celle, diminuisce all’aumentare del numero di elementi non nulli

nella matrice dei flussi. La qualita della soluzione fornita e, inoltre, tanto

migliore quanto maggiore e il numero di celle e quanto minore e il livello

di sparsita della matrice dei flussi. Nella quasi totalita degli esperimenti

con dimensione del layout medio-alta, l’euristica TS ha trovato la soluzione

ottima in tempi trascurabili rispetto ai tempi degli algoritmi esatti.

Sviluppi futuri

L’algoritmo Tabu Search realizzato si e dimostrato particolarmente valido su

problemi di medie e grandi dimensioni. Un interessante sviluppo futuro si

potrebbe avere tramite l’integrazione dell’euristica TS con l’approccio Branch

and Cut: e possibile eseguire un run del TS per ottenere una prima soluzione

ammissibile che abbia buona probabilita di essere molto vicina all’ottimo.

L’aggiunta dinamica dei tagli puo quindi portare ad un rapido miglioramen-

to del lower bound. L’effetto combinato dovrebbe portare ad un ulteriore

abbattimento dei tempi di esecuzione e permettere, quindi, di risolvere in

maniera ottima problemi di dimensioni maggiori di quelle trattate nel pre-

sente lavoro. Particolare attenzione andra posta su di una nuova taratura del

TS per questo uso, in modo da non appesantire esageratamente l’algoritmo

di branch and cut.

Nell’ambito dei problemi di Facility Design, l’aspetto relativo alla pro-

gettazione del layout ed alla progettazione del sistema di movimentazione

dei materiali e tradizionalmente affrontato in modo separato e sequenziale.

Un possibile sviluppo del lavoro di tesi potrebbe essere l’integrazione dei due

aspetti sia da un punto di vista teorico, con una formulazione del problema

SLDP che permetta anche di considerare l’assegnamento delle facility alle

aree, che da un punto di vista applicativo, estendendo, ad esempio, l’algorit-

mo TS introdotto per considerare mosse in cui valutare anche gli effetti di

scambi di area tra diversi reparti.

Bibliografia

Afentakis, P. (1989). A loop layout design problem for flexible manufacturing

systems. International Journal of Flexible Manufacturing Systems (1),

175–196.

Anstreicher, K. M., N. Brixius, J. Linderoth, and J. P. Goux (2002). Solving

large quadratic assignment problems on computational grids. Mathematical

Programming Series B (Forthcoming).

Apple, J. M. (1977). Plant Layout and Material Handling. Wiley.

Asef-Vaziri, A., M. Dessouky, and C. Sriskandarajah (2001). A loop mate-

rial flow system design for automated guided vehicles. The International

Journal of Flexible Manufacturing Systems (33), 33–48.

Asef-Vaziri, A., G. Laporte, and C. Sriskandarajah (2000). The block layout

shortest loop design problem. IIE Transactions (32), 727–734.

Banerjee, P. and Y. Zhou (1995). Facilities layout design optimization with

single loop material flow path configuration. International Journal of

Production Research (33), 183–203.

Bischak, D. P. and K. B. Stevens (1995). An evaluation of tandem configura-

tion automated guided vehicle system. Production Planning & Control (6),

438–444.

Bozer, Y. A. and M. M. Srinivasan (1989). Tandem configurations for au-

tomated guided vehicle systems offer simplicity and flexibility. Industrial

Engineering (21), 23–27.

82

BIBLIOGRAFIA 83

Bozer, Y. A. and M. M. Srinivasan (1991). Tandem configurations for auto-

mated guided vehicle systems and the analysis of single vehicle loops. IIE

Transactions (23), 72–82.

Bozer, Y. A. and M. M. Srinivasan (1992). Tandem AGV systems: A par-

titioning algorithm and performance comparison with conventional AGV

systems. European Journal of Operational Research (63), 173–191.

Chae, J. and B. A. Peters (2000). A simulated annealing algorithm based on

the closed loop layout (SA-CL) for facility layout design in flexible manu-

facturing systems. Working paper, Department of Industrial Engineering,

A & M University, Texas.

Choi, H., H. Kwon, and J. Lee (1994). Traditional and tandem AGVs layouts

- a simulation study. Simulation (63), 85–93.

Das, S. (1993). A facility layout method for flexible manufacturing systems.

International Journal of Production Systems (31), 279–297.

DeGuzman, M. C., N. Prabhu, and J. M. A. Tanchoco (1997). Complexity

of the AGV shortest path and single-loop guide path layout problems.

International Journal of Production Research (35), 2083–2092.

Foulds, L. R. and D. F. Robinson (1978). Graph theoretic heuristics for the

plant layout problem. International Journal of Production Research (16),

27–37.

Francis, R. L., L. F. McGinnis, and J. A. White (1992). Facility Layout and

Location: An Analytical Approach. Prentice-Hall.

Ganesharajah, T., N. G. Hall, and C. Sriskandarajah (1998). Design and

operational issues in AGV-served manufacturing systems. Annals of

Operations Research (76), 109–154.

Gaskins, R. J. and J. M. A. Tanchoco (1987). Flow path design for au-

tomated guided vehicle systems. International Journal of Production

Research 25 (5), 667–676.

BIBLIOGRAFIA 84

Glover, F. (1989). Tabu search, part I. ORSA Journal on Computing 1 (3),

190–206.

Glover, F. and M. Laguna (1993). Tabu search. In C. Reeves (Ed.), Mod-

ern Heuristic Techniques for Combinatorial Problems, Oxford, England.

Blackwell Scientific Publishing.

Goetschalckx, M. and G. Palliyil (1994). A comprehensive model for

the concurrent determination of aisle-based material handling systems.

In R. Graves (Ed.), Developments in Material Handling Research, pp.

161–188. Charlotte, NC: Material Handling Institute of America.

Heragu, S. (1997). Facilities Design. PWS Publishing Company.

Kaspi, M. and J. M. A. Tanchoco (1990). Optimal flow path design

of unidirectional AGV systems. International Journal of Production

Research 28 (6), 915–926.

Kiran, A. S. and S. Karabati (1993). Exact and approximate algorithms for

the loop layout problem. Journal of Production Planning and Control (4),

253–259.

Kouvelis, P. and M. W. Kim (1992). Unidirectional loop network layout

problem in automated manufacturing systems. Operations Research (40),

533–550.

Lin, J. T., C. C. K. Chang, and W. C. Liu (1994). A load-routing problem

in a tandem-configuration automated guided-vehicle system. International

Journal of Production Research (32), 411–427.

Maxwell, W. L. and J. A. Muckstadt (1982). Design automated vehicle

systems. IIE Transactions (2), 114–124.

Montreuil, B. (1991). A modeling framework for integrating layout design and

flow network design. In Proceedings of the Material Handling Colloquium,

Charlotte, NC, pp. 43–58. Material Handling Institute of America.

BIBLIOGRAFIA 85

Muth, E. J. (1972). Analysis of closed-loop conveyor systems. AIIE

Transactions (4), 34–143.

Muth, E. J. (1974). Analysis of closed-loop conveyor systems, the discrete

flow case. AIIE Transactions (6), 73–83.

Muth, E. J. (1975). Modeling and system anlysis of multistation closed-loop

conveyors. International Journal of Production Research (13), 559–566.

Muther, R. (1973). Systematic Layout Planning. Management and Industrial

Research Publications.

Nicol, L. M. and R. H. Hollier (1983). Plant layout in practice. Material

flow 1, 177–188.

Rajeasekharan, M., B. A. Peeters, and T. Yang (1998). A genetic algorithm

for facility layout design in flexible manufacturing systems. International

Journal of Production Research (36), 95–110.

Sinriech, D. and J. M. A. Tanchoco (1993). Solution methods for the math-

ematical models of single-loop AGV systems. International Journal of

Production Research 31 (3), 705–725.

Sinriech, D., J. M. A. Tanchoco, and Y. T. Herer (1996). The segment-

ed bi-directional single-loop topology for material flow systems. IIE

Transactions 28, 40–54.

Sule, D. R. (1991). Manufacturing Facilities: Location, Planning & Design.

PWS Publishing Company.

Tanchoco, J. M. A. and D. Sinriech (1992). OSL - optimal single-loop guide

paths for AGVS. International Journal of Production Research 30 (3),

665–681.

Tansel, B. C. and C. Bilen (1998). Move based heuristics for the unidi-

rectional loop network layout problem. European Journal of Operational

Research (108), 36–48.

BIBLIOGRAFIA 86

Tompkins, A., J. A. White, Y. A. Bozer, E. H. Frazelle, J. M. A. Tanchoco,

and J. Trevino (1996). Facilities Planning. New York: Wiley.

Usher, J. S., G. W. Evans, and M. R. Wilhelm (1988). AGV flow path design

and load transfer point location. Proceedings of the 1998 IIE Conference,

174–179.

Appendice A

Layout utilizzati*

Vengono di seguito riportati gli schemi dei layout impiegati nella campagna

sperimentale illustrata nella sezione 5.2 relativa agli algoritmi per il problema

SLDP.

87

APPENDICE A. LAYOUT UTILIZZATI* 88

Figura A.1: Layout 1

Figura A.2: Layout 2

tesi

Documents

Transcript of tesi