Che materia stai cercando?

Tesi, Sviluppo di principi di allocazione della merce all'interno di magazzini automatizzati mediante modelli Multi-Obiettivo

Tesi di laurea magistrale per la cattedra del professor Gamberi. Titolo tesi: "Sviluppo di principi di allocazione della merce all'interno di magazzini automatizzati mediante modelli Multi-Obiettivo".
Attività di tesi incentrata sul completo sviluppo di un nuovo principio di allocazione della merce all'interno dei magazzini automatizzati serviti da trasloelevatori, con il fine di minimizzare... Vedi di più

Materia di Impianti meccanici e logistica LM relatore Prof. M. Gamberi

Anteprima

ESTRATTO DOCUMENTO

Un problema matematico di ottimizzazione può essere definito come la

minimizzazione o la massimizzazione di una funzione a valori reali su un

insieme specificato. L’importanza di questo modello matematico deriva dal fatto

che molti problemi reali sono affrontati facendovi ricorso.

Tuttavia quasi ogni problema reale di ottimizzazione è caratterizzato dalla

presenza contemporanea di più obiettivi, cioè funzioni a valori reali da

massimizzare e/o minimizzare, spesso in contrasto fra loro.

Un problema di ottimizzazione Multi-Obiettivo può essere rappresentato come

segue [8]: T

min (ƒ (x) (x) … (x)) con k ≥ 2

ƒ ƒ

1 2 k

F

x ∈ (x) simultaneamente.

L’obiettivo è minimizzare tutte le f.o. ƒ

i

k

In assenza di conflitti fra le f.o. una soluzione al problema è ottenibile

id

k

minimizzando indipendentemente le funzioni, ottenendo il vettore z (soluzione

banale). In questo modo non sarebbe necessario applicare nessuna tecnica

specifica di soluzione. iid Z.

Siccome le f.o. sono in conflitto fra loro si suppone che z ∉ 1 2 k

Definizione 3.2.1 – Relazione di dominanza: dati due vettori z , z R , si dice

1 2 1 2

che z domina z secondo Pareto (z ≤ z ) quando risulta:

P

1 2

≤ z per ogni i = 1, …, k

z i i

1 2

< z per almeno un indice j {1, …, k}

z ∈

j j

La relazione binaria ≤ è un ordinamento parziale (non riflessivo) nello spazio

P

delle k-uple di numeri reali. Sfruttando questa relazione possiamo dare la

definizione di ottimalità secondo Pareto.

66 Legenda:

Vettori dominati da A ma non da B

Vettori dominati da B ma non da A

Vettori dominati sia da A sia da B

Vettori dominati ma non da A ne da B

Vettori non dominati

Vettore non ammissibile

Vettore ideale

Figura 2 - Relazione di dominanza F

Definizione 3.2.2 – Ottimo di Pareto: un vettore delle variabili decisionali x* ∈

F

è un ottimo di Pareto se non esiste un altro vettore x tale che:

ƒ(x) ƒ(x*)

P

Ossia quando risulta:

(x) ≤ (x*) per ogni i = 1, …, k

ƒ ƒ

i i

(x) < (x*) per almeno un indice j {1, …, k}

ƒ ∈

ƒ

i i

Corrispondentemente si dirà che un vettore di obiettivi z* Z è ottimo secondo

Pareto quando non esiste un altro vettore z Z tale per cui:

z ≤ z*

P

Quindi se ci troviamo in un punto ottimo secondo Pareto e vogliamo

ulteriormente diminuire il valore di una o più f.o. dobbiamo essere disposti ad

accettare un conseguente aumento in alcune (o tutte) le rimanenti funzioni del

problema. In tal senso possiamo affermare che, nello spazio degli obiettivi, gli

67

ottimi di Pareto sono punti di equilibrio che si trovano sulla frontiera

dell’insieme Z.

Definizione 3.2.3 – Frontiera efficiente di Pareto: si definisce frontiera

efficiente di Pareto l’insieme degli ottimi di Pareto del problema Multi-Obiettivo.

Definita anche come l’immagine, nello spazio degli obiettivi, dell’insieme degli

ottimi di Pareto. Figura 3 - Frontiera di Pareto

Figura 4 - Frontiera di Pareto

68

La definizione 3.2.2 (ottimo di Pareto) è ovviamente una definizione di ottimo

globale date che si richiede la validità della proprietà su tutto l’insieme

ammissibile del problema Multi-Obiettivo. È quindi possibile dare una

definizione di ottimo locale secondo Pareto.

Definizione 3.2.4 – Ottimo locale di Pareto: un vettore delle variabili decisionali

F

x* è un ottimo locale di Pareto se esiste un numero δ > 0 tale che x* è

∈ F B

ottimo secondo Pareto in (x*, δ).

Ogni ottimo globale è anche un ottimo locale di Pareto: il viceversa è vero solo

se sono verificate alcune ipotesi sulla struttura del problema di ottimizzazione.

Figura 5 - Ottimi globali e locali di Pareto

Le definizioni di ottimo globale e locale secondo Pareto possono essere

indebolite per ottenere la definizione di ottimo debole secondo Pareto.

Definizione 3.2.5 – Ottimo debole di Pareto: un vettore delle variabili

F F

decisionali x* è un ottimo debole di Pareto se non esiste un punto x tale

∈ ∈

che: <

ƒ(x) ƒ(x*)

L’insieme degli ottimi di Pareto è contenuto nell’insieme degli ottimi deboli di

Pareto (ma non viceversa). 69

3.3. Metodi risolutivi

Nel corso degli anni i ricercatori hanno sviluppato diverse metodologie utili a

risolvere problemi di ottimizzazione Multi-Obiettivo, sia che si impieghi un

approccio tradizionale sia che si preferisca l’approccio di Pareto.

Matematicamente parlando, nella maggior parte dei casi, il problema Multi-

Obiettivo si considera risolto nel momento in cui è stato individuato l’insieme dei

punti ottimi di Pareto: tuttavia, non sempre ci si può accontentare semplicemente

di aver determinato questo insieme di soluzioni.

Alcune volte, infatti, è necessario ordinare tutte le soluzioni trovate e quindi

selezionare la migliore rispetto a tale insieme. Proprio per questo motivo il ruolo

del decisore è fondamentale in quanto c’è la necessità di qualcuno che ci dica, in

base alle proprie preferenze, come ordinare l’insieme degli ottimi di Pareto del

problema. Le preferenze possono essere esplicitate a monte, a valle o durante

l’applicazione dell’algoritmo di risoluzione. In base al ruolo svolto dal decisore

nella strategia di soluzione del problema, i metodi risolutivi per la

programmazione Multi-Obiettivo sono spesso suddivisi in quattro categorie

principali [8]:

Metodi senza preferenze:

1. nei quali il decisore non ha nessun ruolo ed è

considerato soddisfacente aver trovato un qualunque ottimo di Pareto;

Metodi a posteriori:

2. nei quali si genera l’insieme di tutti gli ottimi di

Pareto e poi lo si presenta al decisore che sceglierà la soluzione a lui più

gradita;

Metodi a priori:

3. nei quali il decisore specifica le sue preferenze prima che

abbia inizio il processo risolutivo. In base alle informazioni ottenute dal

decisore viene direttamente trovata la soluzione ottima migliore, senza

dunque dover generare tutti gli ottimi di Pareto;

70

Metodi interattivi:

4. nei quali il decisore specifica le sue preferenze mano a

mano che l’algoritmo procede, guidando il processo risolutivo verso la

soluzione per lui più soddisfacente.

Al di là della distinzione appena introdotta, tutti i metodi di soluzione di un

problema di ottimizzazione Multi-Obiettivo su basano sul medesima idea di

fondo, ovvero quella di trasformare il problema originario in un problema con

una sola funzione obiettivo. La tecnica mediante la quale si ottiene il problema

mono-obiettivo a partire da un problema Multi-Obiettivo è nota come

scalarizzazione.

Saranno ora descritte le caratteristiche principali di ogni categoria di metodi

risolutivi e per ciascuna di queste saranno presentate a grandi linee le tecniche

maggiormente utilizzate. Per fare ciò ci si baserà su [8].

Nel proseguo del capitolo si farà riferimento a un problema di ottimizzazione

F

Multi-Obiettivo (P) in cui la regione ammissibile è definita da m vincoli di

disuguaglianza: (P)

min ƒ(x)

g(x) ≤ 0

Dove:

n k

: R R con k ≥ 2

à

ƒ n m

R

g : R à

Sia che g sono funzioni differenziabili con continuità.

ƒ 71

3.3.1. Metodi senza preferenze

Nei metodi senza preferenze ci si accontenta di generare una soluzione ottima di

Pareto, qualunque essa sia, senza tenere in considerazione le preferenze del

decisore.

Metodo Goal

Si cerca la soluzione che minimizza, nello spazio degli obiettivi, la

distanza tra la regione ammissibile (Z) e un qualunque punto di

ref

riferimento z Z = Il vettore di riferimento sarà costituito dai

∉ ƒ(F).

valori auspicabili per le singole funzioni obiettivo. In particolare, una

ref ref id

è z = z .

possibile scelta di z

Il problema che si ottiene è perciò il seguente:

id (P )

min || – z ||

ƒ(x) p

p

g(x) ≤ 0 indica la norma p di un vettore (con 1 ≤ p ≤ ∞).

Dove || . || p

In particolare se p = ∞, il problema (P ) è noto come problema di

p

Tchebycheff. Si supponga di conoscere il vettore ideale globale degli

) ammette sempre soluzioni.

obiettivi: sotto tali ipotesi, il problema (P

p

Valgono le seguenti proprietà (dimostrabili):

- Ogni soluzione globale del problema (P ) (con 1 ≤ p ≤ ∞) è un ottimo

p

globale di Pareto per il problema (P); ) (con 1 ≤ p ≤ ∞) è un ottimo

- Ogni soluzione globale del problema (P p

locale di Pareto per il problema (P); ) è un

- Ogni ottimo locale (globale) del problema di Tchebycheff (P ∞

ottimo locale (globale) debole di Pareto per il problema (P);

) ha almeno una soluzione che è ottima

- Il problema di Tchebycheff (P

secondo Pareto. 72

3.3.2. Metodi a posteriori

I metodi appartenenti a questa classe sono anche noti come le tecniche per

generare l’insieme delle soluzioni di Pareto: si tratta quindi delle tecniche

riconducibili all’approccio di Pareto.

Infatti, siccome le preferenze del decisore sono considerate solo al termine del

processo risolutivo, quello che si fa è generare tutti i punti ottimi secondo Pareto,

per poi presentarli allo stesso decisore che sceglierà la soluzione a lui più

congeniale.

L’inconveniente principale di questa tecnica sta nel fatto che molto spesso il

processo di generazione degli ottimi di Pareto è computazionalmente oneroso.

Inoltre, potrebbe non essere semplice per il decisore scegliere una soluzione fra

gli ottimi che gli vengono presentati, in particolar modo se questi sono numerosi.

Proprio per questo motivo è molto importante la modalità con la quale sono

presentate le soluzioni al decisore.

Una tecnica risolutiva ideale dovrebbe presentare alcune caratteristiche, proprietà

[9]:

1. Il metodo dovrebbe generare un insieme di punti di Pareto, equamente

distribuiti nello spazio di progettazione, in modo da non trascurare

nessuna regione;

2. Il metodo dovrebbe essere in grado di generare tutte le soluzioni di Pareto

disponibili;

3. Il metodo dovrebbe generare solo soluzioni di Pareto: soluzioni non di

Pareto sono solitamente non desiderabili per il decisore finale. In

letteratura scientifica sono stati sviluppati numero si strumenti, chiamati

filtri di Pareto, che dato un insieme di punti nello spazio degli obiettivi,

restituisce come output esclusivamente i punti ottimo secondo Pareto;

4. Il metodo dovrebbe essere relativamente semplice da applicare

Saranno ora presentate due tecniche risolutive differenti appartenenti a questa

categoria. 73

Metodo dei pesi

Sia considerato il seguente problema:

k

∑ w (x)

min (P )

ƒ

i i w

i = 1

g(x) ≤ 0 +k

Dove w R e i coefficienti w si intendono normalizzati, cioè tali che:

∈ i

k

∑ w = 1

i

i = 1 ) e i punti di Pareto di (P)

Esiste una relazione fra le soluzioni di (P

w

Questo metodo di risoluzione fornisce un insieme di punti appartenenti

alla frontiera di Pareto e non più un solo punto alla volta: per fare ciò è

necessario è necessario risolvere più colte lo stesso problema di

ottimizzazione multi-obiettivo facendo variare di volta in volta il valore

assegnato ai pesi w . È bene sottolineare che i pesi non rappresentano in

i

alcun modo le preferenze espresse dal decisore, ma sono solo degli

strumenti matematici utili alla risoluzione del problema e quindi alla

generazione della frontiera di Pareto.

La critica che è mossa a questo metodo è che spesso non viene generato

un insieme di punti equamente distribuito sulla frontiera: un cambiamento

uniforme dei pesi non sempre equivale a un’equa distribuzione dei punti

sulla frontiera.

È necessario quindi affrontare il problema, per nulla semplice, di come

variare il vettore dei pesi w ad ogni iterazione del metodo, con il fine di

ottenere un insieme equamente distribuito di punti (quindi soluzioni).

74

Valgono le seguenti proprietà (dimostrabili): ) è un ottimo debole

- Ogni soluzione locale (globale) del problema (P w

locale (globale) di Pareto per il problema (P);

), fissato il vettore dei pesi w ≥ 0, ammette un’unica

- Se il problema (P

w

soluzione allora essa è un ottimo di Pareto per il problema (P);

- Se w > 0 per ogni indice i, ogni soluzione locale (globale) del problema

i

) è un ottimo locale (globale) di Pareto per il problema (P);

(P w *

- Sia x un ottimo di Pareto per il problema (P). Se (P) è convesso allora

+k

esistono dei pesi w R , che soddisfano la condizione di

∈ * è soluzione anche del problema (P ).

normalizzazione, tali che x w

Metodo degli ε-vincoli

Si seleziona una f.o. (x) tra gli obiettivi di (P) e poi si trasformano tutte

ƒ 1

(x) (con i = 1, 2, …, k; i ≠ in vincoli, imponendo degli

le altre f.o. l)

ƒ i

upper bound sui loro valori.

Il problema che si ottiene è allora il seguente: (P )

min (x)

ƒ ε

l

(x) ≤ ε per ogni i = 1, 2, …, k; i ≠ l

ƒ i i

g(x) ≤ 0

Dove: {1, 2, …, k}

l ∈

Valgono le seguenti proprietà (dimostrabili):

) `e un ottimo debole secondo Pareto per il

- Ogni soluzione di (P ε

problema (P); *

- Un vettore x è ottimo secondo Pareto di (P) se e solo se è soluzione

∈  F

) per ogni scelta di {1, 2, …, k} ed essendo ε = (x*) con i ≠

di (P l l;

∈ ƒ

ε i i

F

* è l’unica soluzione del problema (P ) per qualche

- Se il punto x ∈   ε

*

{1, 2, …, k} e con ε = (x ) per ogni j ≠ allora esso è Pareto ottimo

l l,

∈ ƒ

j j

per il problema (P). 75

Negli ultimi anni gli studiosi di ricerca operativa hanno sviluppato numerosi

metodi risolutivi che cercano di soddisfare le quattro proprietà elencate in

precedenza. La descrizione dettagliata di questi metodi esula dalla trattazione.

È riportata la seguente tabella riepilogativa che confronta queste innovative

tecniche in funzione delle quattro proprietà che dovrebbe possedere un metodo

risolutivo a posteriori.

Figura 6 - Efficacia dei metodi per la generazione della frontiera di Pareto

Dove:

PP: Physical Programming method Dennis

NBI: Normal Boundary Intersection method (Das and 1998)

NC: Normal Constraint method

WS: Weighted Sum method

CP: Compromise Programming method (Chen et al. 1999)

Y: Soddisfa la proprietà

N: Non soddisfa la proprietà

Nel paragrafo successivo sarà approfondito un ulteriore metodo a posteriori,

utilizzato per generare la frontiera di Pareto per il problema di ottimizzazione

Multi-Obiettivo descritto nella presente tesi riguardante la progettazione dei

Normalized Normal Constraint Method

magazzini automatizzati: il (NNCM).

76

3.3.2.1. Normalized Normal Constraint Method (NNCM) Normalized Normal

Questo paragrafo presenta lo sviluppo analitico del

Constraint Metohod (NNCM), ossia del metodo che sarà utilizzato nell’elaborato

per generare la frontiera di Pareto [9].

Una generica formulazione di un problema Multi-Obiettivo è la seguente:

Problem P1 (1)

min {µ (x) µ (x) … µ (x)} , (n ≥ 2)

1 2 n

x

Subject to (2)

g (x) ≤ 0 (1 ≤ j ≤ r) Vincoli di disuguaglianza

j (3)

(x) = 0 (1 ≤ k ≤ s) Vincoli di uguaglianza

h k (4)

x ≤ x ≤ x (1 ≤ i ≤ n ) Vincoli laterali

li i ui x

Il vettore x rappresenta le variabili decisionali (variabili di progettazione), mentre

denota la i-esima f.o..

µ i

La risoluzione del problema P1 non fornisce un’unica soluzione: per definire una

singola soluzione ottimale è necessario che il decisore o il progettista esprima

una preferenza. Anchor Points,

Per lo sviluppo del metodo è necessario determinare gli i “punti

i*

di ancoraggio” (µ ), anche detti vertici ottimali o “punti finali della frontiera di

Pareto”. Il generico i-esimo punto di ancoraggio si ottiene minimizzando la

i-esima f.o. indipendentemente dalle altre.

La linea che unisce gli Anchor Points nel caso bi-obiettivo (2-f.o.) prende il

Utopia line,

nome di mentre il piano che comprende gli stessi punti di ancoraggio

Utopia Hyperplane.

per problemi Multi-Obiettivo (n-f.o.) prende il nome di Utopia Point:

L’insieme degli Anchor Points è per definizione detto poiché

questo punto è difficilmente raggiungibile (equivarrebbe alla minimizzazione

contemporanea di tutte le f.o. del problema), questo punto è solitamente escluso

dal piano di Utopia. 77

Gli anchor points sono ottenibili risolvendo il problema PU , definito nel

i

seguente modo:

Problem PU

i

min {µ (x)}, (1 ≤ i ≤ n) (5)

i

x

Subject to (6)

(x) ≤ 0 (1 ≤ j ≤ r) Vincoli di disuguaglianza

g

j (7)

h (x) = 0 (1 ≤ k ≤ s) Vincoli di uguaglianza

k (8)

≤ x ≤ x (1 ≤ i ≤ x ) Vincoli laterali

x li i ui x

È quindi possibile formalizzare quanto fini qui detto nel seguente modo:

i* i* nx

x : vettore decisionale che ottimizza l’i-esima f.o. (x R )

i* i* i*

µ : miglior valore ottenibile per l’i-esima f.o., in particolare µ = µ (x )

i

1* 2* n*

u u T u n

: Utopia point, µ = [µ , µ , …, µ ] , (µ R )

µ ∈

i* i* i* i* i* T i* n

µ : Anchor point i-esimo µ = [µ (x ), µ (x ), …, µ (x )] , (µ R )

1 2 n

u : Utopia plane, iper-piano nel problema n-obiettivo che comprende gli n

P

i*

anchor points, µ (i = 1, …, n)

Una volta analizzati questi concetti è possibile proporre una procedura costituita

di sette passi fondamentali per la generazione dell’insieme dei punti ottimi di

Pareto nello spazio degli obiettivi normalizzato.

Si farà riferimento prima al caso bi-obiettivo e conseguentemente al caso

n-obiettivo: la tecnica bi-obiettivo sarà applicata al problema Multi-Obiettivo

oggetto dell’elaborato di tesi caratterizzato dalla presenza di due differenti f.o. da

minimizzare simultaneamente (tempo ed energia).

78

Normal Constraint per il caso bi-obiettivo

Per completezza di analisi è descritta la procedura in sette passi per generare la

frontiera di Pareto nel caso bi-obiettivo:

Passo 1) Anchors points 1* 2*

Ottenere i due anchor points µ e µ risolvendo rispettivamente i problemi PU e PU .

1 2

Passo 2) Normalizzazione

L’ottimizzazione ha luogo nello spazio degli obiettivi normalizzato per evitare

problemi di scala. Nello spazio degli obiettivi normalizzato gli anchor points

hanno distanza pari all’unità dall’Utopia Point, quest’ultimo situato, per

definizione, nell’origine degli assi. La normalizzazione è utile in quanto rende

più significativo confrontare più soluzioni di compromesso in termini di distanza

dall’Utopia Point. Si indica con µ la forma normalizzata di µ.

1* 2*

Si definisco l e l come le rispettive distanze fra µ e µ :

1 2

2* 1*

= µ (x ) – µ (x )

l (9)

1 1 1

1* 2*

= µ (x ) – µ (x )

l (10)

2 2 2

Per realizzare la normalizzazione vale la seguente espressione:

T

1* 2*

µ (x) – µ (x ) µ (x) – µ (x )

1 1 2 2 (11)

µ = l l

1 2

Figura 7 - Spazio degli obiettivi originale (a) e normalizzato (b)

79

Passo 3) Vettore Utopia line 1* 2*

Determinare la direzione N , definita come la direzione da µ a µ :

1

2* 1*

= µ – µ

N (12)

1

Passo 4) Incrementi normalizzati

Calcolare un incremento normalizzato, δ , lungo la direzione N per un numero

1 1

di soluzioni predefinito m :

1

1

=

δ (13)

1 m – 1

1

Passo 5) Generazione dei punti dell’Utopia line

Calcolare un insieme equamente distribuito di punti sull’Utopia line:

1* 2* (14)

X = α µ + α µ con j {1, 2, …, m }

pj 1j 2j 1

Dove: ≤ 1

0 ≤ α (15)

1j

2 (16)

∑ α = 1

kj

k = 1

Si nota che α è incrementato di δ tra 0 e 1.

1j 1

Figura 8 - Insieme di punti equamente distribuito sull'Utopia line

80

Passo 6) Generazione dei punti di Pareto

Utilizzare l’insieme equamente distribuito di punti sull’Utopia line per generare

un corrispondente insieme di punti di Pareto, risolvendo una successione di lanci

di ottimizzazione del problema P2 sottoesposto.

Ogni lancio di ottimizzazione corrisponde a un punto sull’Utopia line. In

particolare, per ogni punto generato sull’Utopia line, risolvere per il j-esimo

punto il seguente problema:

Problem P2 (per il j-esimo punto)

min µ (17)

2

x

Subject to

g (x) ≤ 0 (1 ≤ j ≤ r) Vincoli di disuguaglianza (18)

j

h (x) = 0 (1 ≤ k ≤ s) Vincoli di uguaglianza (19)

k ≤ x ≤ x (1 ≤ i ≤ n ) Vincoli laterali

x (20)

li i ui x

T

(µ – X ) ≤ 0 Vincolo aggiuntivo

N (21)

1 pj T

µ = [µ (x) µ (x)] (22)

1 2

Figura 9 - Rappresentazione grafica del NNCM per il caso bi-obiettivo

81

Passo 7) De-normalizzazione

Successivamente alla determinazione della frontiera di Pareto nello spazio

normalizzato, è necessario ritornare allo spazio originale al fine di avere a

disposizione i valori reali assunti dagli obiettivi.

Per fare ciò è possibile seguire due strade:

a) In primo luogo, essendo la funzione µ(x) nota ed essendo conosciuto il vettore

x, la valutazione è diretta;

b) In alternativa si può applicare la relazione inversa a quella di normalizzazione,

come segue: 1* 2* T

µ = [µ l + µ (x ) µ l + µ (x )] (23)

1 1 1 2 2 2

È importante ricordare che il metodo appena descritto non genera esclusivamente

punti di Pareto: risulta quindi necessaria, una volta definita la frontiera di Pareto,

filtro di Pareto).

eliminare i punti dominati (attraverso il

Normal Constraint per il caso n-obiettivo

Per completezza di analisi è descritta la procedura in sette passi per generare la

frontiera di Pareto nel caso n-obiettivo (i passaggi fondamentali sono simili a

quelli illustrati nel paragrafo precedente):

Passo 1) Anchors points i*

Ottenere gli n anchor points µ per i {1, 2, …, n} risolvendo i problemi PU .

∈ i

È definito l’iperpiano che contiene tutti i punti di ancoraggio definiti: questo

Utopia Hyperplane Utopia plane).

piano è chiamato (o Come per il caso bi-

obiettivo il vettore decisionale che ottimizza l’-esima f.o., ottenuto risolvendo il

i*

, è indicato con x .

singolo problema PU i 82

Passo 2) Normalizzazione

L’ottimizzazione ha luogo nello spazio degli obiettivi normalizzato per evitare

problemi di scala. Nello spazio degli obiettivi normalizzato gli anchor points

hanno distanza pari all’unità dall’Utopia Point, quest’ultimo situato, per

definizione, nell’origine degli assi.

Con il fine di ottenere i parametri di normalizzazione richiesti è necessario

Nadir Point,

determinare due punti, l’Utopia Point e il rispettivamente definiti

nel seguente modo:

u 1* 2* n* T

µ = [µ (x ) µ (x ) … µ (x )] (24)

1 2 n

1N 1N nN

N T (25)

= [µ µ … µ ]

µ

Dove:

1N 1* 2* n*

µ = max [µ (x ) µ (x ) … µ (x )] con i {1, 2, …, n} (26)

i i i

È definita la matrice L come segue:

l

1

l

2 N u

L = = µ – µ (27)

l

n

Per realizzare la normalizzazione vale la seguente espressione:

i*

µ – µ (x )

i i

µ = i = 1, 2, …, n (28)

i l

i 83

Figura 10 - Utopia Hyperplane per un modello caratterizzato da tre funzioni obiettivo

Passo 3) Utopia line

Vettore k* n*

Determinare le direzioni N , definite come le direzioni da µ a µ per

k

k 2, …, n – 1}:

∈{1,

n* k* (29)

N = µ – µ

k

Passo 4) Incrementi normalizzati

Calcolare gli incrementi normalizzati, δ , lungo le direzioni N per un numero di

k k

soluzioni predefinito m :

k

1 (30)

= (1 ≤ k ≤ n – 1)

δ k m – 1

k

In questa fase si deve prestare molta attenzione nella scelta del numero di si punti

(soluzioni), m , per ciascuna direzione N . Per assicurare una distribuzione

k k

uniforme dei punti sull’Utopia plane n-dimensionale è possibile utilizzare la

, lungo il vettore N ,

seguente relazione. Dato un determinato numero di punti, m 1 1

m è dato da:

k m || N ||

1 k (31)

=

m k || N ||

1 84

Passo 5) Generazione dei punti dell’Utopia Hyperplane

Calcolare un insieme equamente distribuito di punti sull’Utopia Hyperplane:

n k* (32)

X = α µ

pj kj

k = 1

Dove: (33)

≤ 1

0 ≤ α 1j

n (34)

∑ α = 1

kj

k = 1 Figura 11 - Insieme di punti equamente distribuito sull'Utopia Hyperplane

Passo 6) Generazione dei punti di Pareto

Utilizzare l’insieme equamente distribuito di punti sull’Utopia Hyperplane per

generare un corrispondente insieme di punti di Pareto, risolvendo una

successione di lanci di ottimizzazione del problema P3 sottoesposto.

Ogni lancio di ottimizzazione corrisponde a un punto sull’Utopia Hyperplane. In

particolare, per ogni punto generato sull’Utopia Hyperplane, risolvere per il

j-esimo punto il seguente problema: 85

Problem P3 (per il j-esimo punto) (35)

min µ n

x

Subject to (36)

g (x) ≤ 0 (1 ≤ j ≤ r) Vincoli di disuguaglianza

j (37)

(x) = 0 (1 ≤ k ≤ s) Vincoli di uguaglianza

h k

x ≤ x ≤ x (1 ≤ i ≤ n ) Vincoli laterali (38)

li i ui x

T (39)

(µ – X ) ≤ 0 (1 ≤ k ≤ n – 1) Vincoli aggiuntivi

N k pj T

µ = [µ (x) µ (x) … µ (x)] (40)

1 2 n

Il punto iniziale utilizzato nella risoluzione del problema P3 con un algoritmo

basato sul gradiente contribuisce alla generazione di un’efficiente frontiera di

Pareto. Nel particolare caso del NNCM una buona scelta per il punto di partenza

è il punto X .

pj

Passo 7) De-normalizzazione

Successivamente alla determinazione della frontiera di Pareto nello spazio

normalizzato, è necessario ritornare allo spazio originale al fine di avere a

disposizione i valori reali assunti dagli obiettivi.

Si può applicare la relazione inversa a quella di normalizzazione, come segue:

i* (41)

= µ l + µ (x ) con i = {1, 2, …, n}

µ i i i i T

µ = [µ µ … µ ] (42)

1 2 n

Anche in questo caso il metodo appena descritto non genera esclusivamente punti

di Pareto: risulta quindi necessaria, una volta definita la frontiera di Pareto,

filtro di Pareto).

eliminare i punti dominati (attraverso il 86

3.3.3. Metodi a priori

I metodi appartenenti a questa classe sono riconducibili all’approccio

tradizionale. Il decisore fornisce le informazioni riguardo le proprie preferenze

prima che il processo risolutivo abbia inizio. Una volta ottenute queste

informazioni l’algoritmo si arresta solo nel momento in cui è stato individuato un

ottimo di Pareto. In questo modo è determinata direttamente la soluzione ottima

migliore, senza che debbano essere generati tutti gli ottimi di Pareto.

Di seguito saranno presentati due diversi metodi a priori [8]:

Metodo della “value function”

Il decisore specifica l’espressione analitica di una funzione di utilità degli

obiettivi U(z) che va minimizzata nel rispetto dei vincoli del problema

originale. Il problema da risolvere è quindi il seguente: (P )

min U(ƒ(x)) U

g(x) ≤ 0

Si noti che se la funzione U(z) è una funzione lineare si ottiene

nuovamente il problema (P ) del metodo dei pesi. Mentre però il metodo

w

dei pesi è un metodo a posteriori, in cui si vogliono generare tutte le

), il metodo della

soluzioni di Pareto (variando di volta in volta i pesi w i

“value function” è un metodo a priori, in cui cioè il decisore comunica le

le utilità relative delle

sue preferenze imponendo attraverso i pesi w i

diverse funzioni obiettivo. La definizione numerica dei pesi è la principale

valgono solitamente le seguenti

criticità di questo metodo. Per i pesi w i

proprietà:

w ≥ 0

i

k

∑ w = 1

i

i = 1

Nel caso generale, la funzione U(z) potrebbe non essere lineare.

87

Metodo dell’ordinamento lessicografico

Il decisore ordina le funzioni obiettivo in base alla loro importanza

relativa. Una volta che le funzioni obiettivo sono state ordinate, il

processo risolutivo inizia con la minimizzazione della prima funzione

F,

obiettivo sull’insieme ammissibile originario cioè si risolve il

problema:

min (x) (P )

ƒ 1 1

g(x) ≤ 0 ) ha un’unica soluzione allora questa è anche soluzione

Se il problema (P 1

di (P) e l’algoritmo risolutivo termina. Altrimenti si minimizza la seconda

funzione obiettivo nell’ordinamento lessicografico. Questa volta però oltre

ai vincoli originari, si aggiunge un ulteriore vincolo il cui scopo è quello

di garantire che all’ottimo non peggiori il valore della prima funzione

obiettivo. Il problema è quindi impostato come segue:

min (x) (P )

ƒ 1 2

g(x) ≤ 0 1*

(x) ≤ (x )

ƒ ƒ

1 1

1*

Dove x è la soluzione di (P ). Se (P ) ha un’unica soluzione ci si ferma,

1 2

altrimenti si prima, selezionando la successiva funzione obiettivo

nell’ordinamento lessicografico assegnato dal decisore.

Al generico passo h ≤ k la formulazione del problema è la seguente:

min (x) (P )

ƒ h h

g(x) ≤ 0 h – 1*

(x) ≤ (x ) con i = 1, 2, …, h – 1

ƒ ƒ

i i

i*

Dove x è una soluzione del problema (P ).

i

88

Si può dimostrare che ogni soluzione ottenuta con il metodo lessicografico

è ottima secondo Pareto per il problema (P).

Nonostante si tratti di un metodo a priori, il metodo dell’ordinamento

lessicografico non richiede la definizione di alcun coefficiente numerico

da attribuire alle diverse funzioni obiettivo: questo aspetto rappresenta

sicuramente un vantaggio.

Ciò nonostante è necessario compiere una scelta riguardo l’ordinamento

delle funzioni obiettivo in funzione della priorità assegnata ad ogni

obiettivo.

3.3.4. Metodi interattivi

In questa categoria di metodi il decisore specifica le proprie preferenze mentre

l’algoritmo risolutivo procede, indirizzando in questo modo il processo verso la

soluzione a lui più consona.

Lo schema generale di un metodo interattivo è il seguente [8]:

1. Trovare una soluzione ammissibile iniziale;

2. Presentare la soluzione trovata al decisore;

3. Se la soluzione trovata è accettabile allora ci si deve fermare, altrimenti,

sulla base delle indicazioni ottenute, trovare una nuova soluzione iterando

dal punto (2).

STEP method

Si supponga che in un punto di ottimo secondo Pareto il decisore sappia

indicare quali funzioni obiettivo presentano un valore accettabile e quali

no. Si supponga inoltre che tutte le funzioni obiettivo siano limitate sulla

regione ammissibile.

Ad ogni iterazione del metodo un ottimo di Pareto viene presentato al

decisore che, sulla base delle sue conoscenze e dei valori delle funzioni

obiettivo nel punto corrente, specifica le funzioni obiettivo per le quali è

accettabile un aumento del valore al fine di poter ulteriormente ridurre i

valori delle restanti funzioni. 89

In sostanza l’insieme degli indici J = {1, 2, …, k} viene partizionato, ad

ogni iterazione, in due sottoinsiemi:

: insieme degli indici delle funzioni obiettivo i cui valori sono

1. J < insoddisfacenti per il decisore;

= J / J .

2. J > <

Se J = allora l’algoritmo risolutivo si ferma avendo trovato l’ottimo di

<

Pareto che meglio soddisfa il decisore. Altrimenti si chiede al decisore di

bounds

specificare dei ε sulle funzioni obiettivo con indici in J e quindi

i >

si risolve il seguente problema:

1/p

id p

∑ | (x) – z |

min ƒ i i

i J

∈ <

g(x) ≤ 0

(x) ≤ ε con i J

ƒ ∈

i i >

*

(x) ≤ (x ) con i J

ƒ ∈

ƒ i i <

*

Dove 1 ≤ p < ∞ e x è l’ottimo di Pareto trovato nella iterazione

precedente.

Si nota che l’algoritmo si deve fermare, al fine di evitare problemi di

ciclaggio (loop), anche quando è vuoto l’insieme J , cioè quando tutte le

>

funzioni obiettivo presentano valori insoddisfacenti.

90

Capitolo 4

Modelli Multi-Obiettivo per l'allocazione della merce

all'interno di magazzini automatizzati

Nel presente capitolo è presentato il modello innovativo per l’analisi Multi-

Obiettivo applicata alla progettazione di nuovi principi di allocazione della merce

all’interno di magazzini automatizzati. Una volta presentato il modello analitico

saranno descritti gli strumenti utilizzati per risolverlo e sarà approfondito un caso

applicativo. Prima di fare ciò saranno opportunamente definite le espressioni per

calcolare la matrice dei tempi e le matrici delle distanze lungo gli assi X e Z.

Come già detto in precedenza nel corso dell’elaborato, l’obiettivo finale non è

quello di definire la miglior soluzione possibile, bensì quello di approssimare la

frontiera di Pareto, ossia determinare una serie di soluzioni di compromesso, le

quali rappresentano l’input per la scelta del decisore finale.

4.1. Definizione della matrice dei tempi

Scopo di questo paragrafo è definire un metodo per la valutazione dei tempi di

viaggio del trasloelevatore all’interno del magazzino automatizzato considerando

i diversi profili di velocità caratterizzanti il movimento. b

matrice dei tempi: tempo di viaggio per raggiungere la baia nella

t à

bslr *

s l r

campata del livello nella scaffalatura [s]

Per semplicità di progettazione il problema è suddiviso in due parti:

1. Determinazione del tempo di viaggio sul conveyor: T ;

y,bslr

2. Determinazione del tempo di viaggio all’interno del magazzino: T (X/Z).

AS/RS

La matrice dei tempi è data da: (1)

= () + (, )

,, /,  

b, s, l, r, p

*Gli indici sono stati definiti nel paragrafo 2.7 del capitolo 2 (pag.58)

91

1. Conveyor ()

,,

Ipotesi:

Il conveyor si muove a velocità costante: v = costante;

conv

I corridoi e le scaffalature hanno tutti la stessa larghezza: l = costante;

1

Si considera trascurabile il gioco di schiena fra le scaffalature.

Vista dall’alto del magazzino automatizzato: l 1 X

Y Z

l

3 l

2

Nastro di output OUT

Nastro di input IN l

start

Dove:

l : lunghezza nastro di uscita dal fronte del magazzino [m]

start

l : larghezza corridoio + scaffalature [m]

1 : lunghezza nastri di input [m]

l 2

l : lunghezza nastri di output [m]

3

n: n-esimo corridoio, con n = 1, 2, ..., N 92

Ipotesi: l = l (la lunghezza dei nastri di input è considerata uguale alla

2 3

lunghezza dei nastri di output) 1

 +    −  1  ∙    +    +  

1 2

=                    []

2 (2)

,,

Ipotesi: l ≠ l (la lunghezza dei nastri di input non è considerata uguale alla

2 3

lunghezza dei nastri di output)

1 2 3

 +    −  1  ∙   +    +    +  

1  

=                    []

2 2 2

(3)

,,

Le espressioni (2) e (3) si riferiscono alla sola andata o al solo ritorno di una

UdC. Si considera una velocità a regime (v ) del conveyor pari a 0,6 ÷ 1 m/s.

conv

2. Magazzino automatizzato (, )

/  ,

Come fatto per la valutazione della spesa energetica del trasloelevatore anche in

questo caso è necessario distinguere i casi in cui il trasloelevatore si muove con

profilo di velocità triangolare dai casi in cui si muove con profilo di velocità

trapezoidale.

Moto orizzontale del trasloelevatore con profilo triangolare

() = +                              [] (4)

(/  →  ,∧)

Sappiamo che per il moto rettilineo uniformemente accelerato lo spazio

percorso equivale a:

= = =                              []

Da cui: (5)

Sfruttando la (5) possiamo riscrivere la (6) come segue:

(6)

() = + =  2 ∙                []    

(/  →  ,∧)

93

Moto orizzontale del trasloelevatore con profilo trapezoidale

() = + +                              [] (7)

(/  →  ,/    \)

Sappiamo che:

= =                                []   (8)

= 2   = =                                [] (9)

,

Sfruttando le (8), (9) possiamo riscrivere la (7) come segue:

   

,

() = + + = +                      []   (10)

(/  →  ,/    \)

Moto verticale ascendente del trasloelevatore con profilo di velocità

triangolare

() = +                              [] (11)

(/  →  ,,∧)

Sappiamo che per il moto rettilineo uniformemente accelerato lo spazio

percorso equivale a:

= = =                              []

Da cui: (12)

Andando a sostituire nella (12) le corrette accelerazioni otteniamo:

=                            [] (13)

(14)

=                              []

 ∙  )

(    

Sfruttando le (13), (14) possiamo riscrivere la (11) come segue: (15)

() = +                              []

(/  →  ,,∧)  ∙  )

(    

94

Moto verticale discendente del trasloelevatore con profilo di velocità

triangolare

() = +                              [] (16)

(,,∧  →  /)

Sappiamo che per il moto rettilineo uniformemente accelerato lo spazio

percorso equivale a:

=   = =                              []

Da cui: (17)

Andando a sostituire nella (17) le corrette accelerazioni otteniamo:

=                            [] (18)

 ∙  )

(    

=                              []

(19)

Sfruttando le (18), (19) possiamo riscrivere la (16) come segue: (20)

() = +                              []

(,,∧  →  /)  ∙  )

(    

Moto verticale ascendente del trasloelevatore con profilo di velocità

trapezoidale

() = + +                              [] (21)

(/  →  ,,/    \) ,

Sappiamo che:

=                                []   (22)

=                                []

(23)

(      ∙  )

= = =                                [] (24)

,,

95

Andando a sostituire nella (24) le corrette accelerazioni otteniamo:

= +                              [] (25)

,, (      ∙  )

Sfruttando le (22), (23), (24) possiamo riscrivere la (21) come segue (26):

,,

()

= + + = + +  []    

(/  →  ,,/    \) (      ∙  ) (     )

 ∙  

Moto verticale discendente del trasloelevatore con profilo di velocità

trapezoidale (27)

= + +                              []    

(,,/    \  →  /) ,

Sappiamo che:

=                                []   (28)

(      ∙  )

=                                [] (29)

=   = =                                [] (30)

,,

Andando a sostituire nella (30) le corrette accelerazioni otteniamo:

= +                              [] (31)

,, (      ∙  )

Sfruttando le (28), (29), (30) possiamo riscrivere la (27) come segue (32):

() ,,

= + + = + + []    

(,,/    \  →  /) (     ) (      ∙  )

 ∙  

96

Tabella riassuntiva delle espressioni definite per valutare i tempi di viaggio del

trasloelevatore all’interno del magazzino per compiere le missioni di prelievo e

deposito:

Moto Tempi di viaggio del conveyor e del trasloelevatore [s]**

CONVEYOR

1 2 3

+ − 1 ∙ + + +

1 2 2 2

=

,,

TRASLOELEVATORE ∗

()

= 2 ∙

ORIZZONTALE (/  →  ,∧)

()

= +

(/  →  ,/    \)

()

= +

(/  →  ,,∧) ∙ )

( +

VERTICALE

()

= +

(,,∧  →  /) ∙ )

( −

TRASLOELEVATORE

1 1

()

= + +

(/  →  ,,/    \) ( + ∙ )

2 2

1 1

()

= + +

(,,/    \  →  /) ( − ∙ )

2 2

* Le coordinate X e Z saranno successivamemte rappresentate dalle rispettive distanze, definite

nel paragrafo 4.2

** Le espressioni temporali devono essere opportunamente combinate in relazione alle

coordinate X e Z da raggiungere all’interno del magazzino, considerando il fatto che il

trasloelevatore può compiere simultaneamente il movimento lungo questi due assi

97

4.2. Definizione delle matrici delle distanze

Scopo di questo paragrafo è definire un metodo per la valutazione delle distanze

che deve compiere il trasloelevatore all’interno del magazzino automatizzato,

lungo gli assi X (asse orizzontale) e Z (asse verticale).

Le matrici delle distanze sono quindi definite per i due assi di movimentazione:

1. Matrice delle distanze lungo l’asse orizzontale X:

2. Matrice delle distanze lungo l’asse verticale Z:

Vista laterale dell’unità di base del magazzino: Z

a X

a' Y

g' g' g' g' A

A' G' G g

Dove:

A: altezza unità di base [m] b: b-esima baia, con b = 1, 2, …, B

G: lunghezza unità di base [m] s: s-esima campata, con s = 1, 2, …, S

A': altezza UdC [m] l: l-esimo livello, con l = 1, 2, …, L

G': lunghezza UdC [m] r: r-esimo corridoio, con r = 1, 2, …, R

a: spessore corrente/scaffale [m]

g: spessore montante [m]

a': gioco superiore [m]

g': giochi laterali [m]

A, G, A', G', a, g, a', g' sono ipotizzati uguali per ogni b, s, l, r.

Si ipotizza trascurabile il gioco di schiena fra le scaffalature.

98

La matrice delle distanze lungo l’asse orizzontale X rappresenta la distanza

b s l r.

percorsa per raggiungere la baia nella campata del livello nella scaffalatura

La matrice delle distanze lungo l’asse orizzontale X sarà così definita:

=   +     ∙     +     ∙   − 1   +   − 1   ∙   (   ∙   )   +  

   

       

         

       

         

  ∙     −     +   − 1   ∙     ∙                      []

+   (33)

 

 

   

   

       

   

 à        

   

La matrice delle distanze lungo l’asse verticale Z rappresenta la distanza percorsa

b s l r.

per raggiungere la baia nella campata del livello nella scaffalatura

La matrice delle distanze lungo l’asse verticale Z sarà così definita:

=   ∙     − 1   +     ∙     − 1                    []   (34)

   

   

   

   

 

  à     99

4.3. Formulazione del modello Multi-Obiettivo in funzione delle prestazioni

temporali ed energetiche

Scopo di questo paragrafo è definire un modello Multi-Obiettivo caratterizzato

dalle seguenti funzioni obiettivo:

1. Funzione obiettivo temporale;

2. Funzione obiettivo energetica.

Il modello fa riferimento al criterio di allocazione della merce per posti condivisi

e modalità di prelievo e deposito con cicli semplici.

Lo scopo del modello bi-obiettivo è definire la disposizione ottimale dei

materiali sugli scaffali del magazzino automatizzato cercando di minimizzare:

1. Le tempistiche di prelievo e deposito della merce;

2. Il consumo di energia per il prelievo e il deposito della merce;

parametri:

Si definiscono i seguenti p

m : massa della tipologia di prodotto [Kg]

p p

q : quantità della tipologia di prodotto [load]

p p

: frequenza di domanda della tipologia di prodotto [%]

f

p

m : massa del trasloelevatore [Kg]

t b s l

E : energia per raggiungere la baia nella campata del livello nella

bslr r

scaffalatura [J] b s

t : tempo di viaggio per raggiungere la baia nella campata del livello

bslr l r

nella scaffalatura [s]

ξ: massima capacità di carico dello scaffale: 2200 Kg

massima capacità di carico del montante: 22000 Kg (2000 Kg per ogni livello)

:

ω: larghezza della doppia scaffalatura [m]

α: moltiplicatore sismico: 0,0921 (αg = accelerazione sismica)

λ: fattore di sicurezza, caratteristico del telaio della struttura: 1,35

l,

H: altezza del livello ipotizzata uguale per ogni livello

p

h : altezza del baricentro dell’unità di carico della tipologia di prodotto

p 2

g: accelerazione di gravità: 9,80665 m/sec

100

variabile decisionale:

Si definisce la seguente

1          è                

         

=  

 

0  

funzioni obiettivo:

Si definiscono le seguenti

1

=     ∙     ∙ ∙  

1

=     ∙     ∙ ∙  ( +  2   ∙   )   ∙  

Φ Φ

: f.o. temporale : f.o. energetica

1 2

relazioni di vincolo:

Si definiscono le seguenti

=                                ∀  

Tutte le UdC di una tipologia di prodotto devono essere contenute all’interno del

magazzino automatizzato.

≤ 1                              ∀  , , ,

In una posizione del magazzino (baia) può essere stoccata una sola tipologia di

prodotto.

∙ ≤                              ∀  , , = 2, … ,

Il peso delle UdC stoccate in un singolo scaffale deve essere minore o uguale alla

massima capacità di carico dello scaffale stesso. Tale vincolo non considera le

UdC stoccate nel primo livello poiché sono appoggiate sul pavimento del locale.

101

  ∙    

  ∙    

()

+ ≤                              ∀  , = 2, … ,

2 2

Il peso delle UdC stoccate negli scaffali sorretti da un montante deve essere

minore o uguale alla massima capacità di carico del montante stesso. Tale

vincolo non considera il primo montante che deve sostenere solo su un lato gli

scaffali.

1

+ ∙ ∙ ∙   ∙     ∙ − 1 ∙ + ℎ − < 0          ∀  

() 2

Il momento ribaltante che causa il rovesciamento delle UdC dagli scaffali

nell’eventualità di un evento sismico deve essere minore del momento

stabilizzante degli stessi.

 

La matrice per l’assegnazione delle UdC ai vani del magazzino automatizzato è

binaria, cioè può assumere solo i due valori 0 o 1.

Si può quindi scrivere sinteticamente il modello Mʹ′ come segue:

1

f.o. (1): min   ∙     ∙ ∙  

1

f.o. (2): min

  ∙     ∙ ∙  ( +  2   ∙   )   ∙  

Subject to:

=                                ∀  

≤ 1                              ∀  , , ,

∙ ≤                              ∀  , , = 2, … ,

102

  ∙    

  ∙    

()

+ ≤                              ∀  , = 2, … ,

2 2

1

+ ∙ ∙ ∙   ∙     ∙ − 1 ∙ + ℎ − < 0          ∀  

() 2

 

Programmazione Lineare Intera.

Mʹ′ è un problema di 103

4.4. Strumenti a supporto della rappresentazione informatica

La soluzione di un modello di Programmazione Lineare richiede l’utilizzazione

risolutore software.

di un Per poter utilizzare un risolutore è necessario tradurre

linguaggio di modellazione,

il modello analitico in un cioè in un linguaggio

interpretabile dal risolutore.

Il linguaggio di modellazione che si è scelto di utilizzare in questa trattazione è

AMPL (A Mathematical Programming Language), linguaggio ad alto livello,

laboratori Bell,

sviluppato dai per descrivere e risolvere problemi di

Programmazione Matematica non banali (es.: problemi di ottimizzazione e di

scheduling). Il linguaggio AMPL non risolve direttamente il problema, bensì

software solver

chiama in causa un per ottenere le soluzioni. Alcuni esempi di

solver sono CPLEX, FortMP, MINOS, IPOPT, SNOPT, KNITRO e altri.

4.4.1. Software e linguaggio di modellazione AMPL

generatore algebrico di modelli

AMPL è un software detto [10], [11].

Fra gli anni ’50 e ’70 la programmazione matematica compì sostanziali passi in

avanti, cui però non corrispose un’applicazione altrettanto diffusa ai problemi

reali. L’ostacolo maggiore alla loro diffusione fu la difficoltà pratica nello

stendere i modelli, raccogliere e organizzare i dati, programmare gli algoritmi

risolutivi e infine analizzare i risultati ottenuti.

Figura 1 - Schema dell'approccio modellistico per passare

da un problema concreto a una strategia

104

L’approccio modellistico presenta indubbi vantaggi ma, come ricorda la figura 1,

il passaggio dal problema alla strategia è tutt’altro che immediato: si tratta infatti

di formulare un modello, successivamente risolverlo e infine analizzare e tradurre

le soluzioni in azioni concrete che rispecchiano la strategia.

Il passaggio dal problema al modello e dalla soluzione alla strategia operativa

sono passi non banali che richiedono una dose maggiore di creatività e ingegno.

Anche il passaggio intermedio, dal modello alla soluzione, è di complessa

risoluzione e solo apparentemente astratto e matematico.

Infatti, se si utilizza uno strumento informatico questo passaggio non si riduce

all’applicazione di un algoritmo, ma comprende (vedi figura 2):

1. La traduzione del modello (pensato o espresso in linguaggio matematico)

e dei dati (disponibili in formato cartaceo o in un database informatico) in

strutture dati accessibili da un solver;

2. La realizzazione di un solver che trasformi i dati in una soluzione

opportunamente codificata;

3. La traduzione della soluzione in un formato accessibile all’utente, come

tabelle e grafici.

Figura 2 - Dettaglio della fase di risoluzione nell'approccio modellistico

105

L’evoluzione in campo matematico e la disponibilità di un’enorme potenza di

calcolo permettono oggi di creare risolutori molto potenti, che non si rivelano in

ogni modo utili a livello applicativo se l’utente non dispone di una corretta

interfaccia verso il solver: il compito dell’interfaccia, che non è altro che un

software, è quello di gestire i modelli e i dati appartenenti al mondo reale e

interrogare il risolutore.

I generatori algebrici di modelli, fra cui AMPL, costituiscono questa interfaccia,

cioè si occupano del primo e del terzo passo, lasciando il secondo al risolutore.

Le caratteristiche principali dei generatori algebrici di modelli sono:

Fornire un linguaggio semplice per descrivere modelli complessi, un

linguaggio che sia contemporaneamente:

- Ad altro livello, ossia facilmente comprensibile da un essere umano;

- Formalmente strutturato, cioè accessibile da un risolutore.

Permettere all’utente di comunicare con il risolutore attraverso file di testo

anziché attraverso strutture dati, in modo da non richiedergli conoscenze

informatiche approfondite e da poter formulare il modello con un

semplice editor, qualunque sia la piattaforma su cui viene scritto e quella

su cui viene risolto;

Permettere all’utente di comunicare con diversi risolutori, in modo da

poter sfruttare i più potenti sul mercato, ovvero quelli disponibili;

Tenere distinti la struttura logica del modello (variabili decisionali,

obiettivi, vincoli e le loro relazioni) dal valore dei dati numerici.

106

Questa situazione si può descrivere nel modo seguente:

Utilizzando un generatore di modelli algebrici l’utente non si occupa più

direttamente di interrogare il risolutore, ma può concentrarsi sulla stesura del

modello, utilizzando un linguaggio di programmazione ad alto livello che gli

rende più semplice descrivere problemi reali anche di notevole complessità.

Quando necessario la gestione dei dati può essere affidata a un database esterno,

mentre è possibile sostituire il risolutore senza andare a modificare il modello.

Infine la separazione fra la struttura logica e i dati evita che piccole modifiche

nella struttura del modello o nei dati comportino di riscrivere tutto: diventa infatti

semplice usare lo stesso modello su dati differenti o viceversa applicare modelli

diversi allo stesso problema.

Il linguaggio di modellazione AMPL è quindi in utilizzato per tradurre modelli di

Programmazione Matematica in modo da esprimere un problema di

ottimizzazione in una forma che sia comprensibile al risolutore.

Sebbene sia lecito scrivere in un solo file AMPL sia il modello matematico, sia i

dati, è concettualmente preferibile tenere separati questi due termini.

Per questo motivo la rappresentazione del modello è suddivisa in due file

differenti:

File di modello: .mod,

1. obbligatoriamente di estensione che descrive la

struttura logica del modello matematico (indici, variabili decisionali,

funzioni obiettivo, vincoli);

File di dati: .dat,

2. obbligatoriamente di estensione che contiene i valori

numerici del problema. 107

Come detto in precedenza, mantenendo fisicamente separato il modello dai dati è

possibile applicare lo stesso modello a dati diversi (istanze) oppure cambiare i

dati senza dover apportare modifiche al modello, evitando il rischio di introdurvi

errori.

Esistono altre due tipologie di file:

3. File di esecuzione: .run,

obbligatoriamente di estensione che richiama i

due file precedentemente descritti, su cui è possibile scrivere delle

istruzioni da fare eseguire al risolutore.

Su questa tipologia di file saranno quindi scritte le istruzioni relative al

metodo scelto per risolvere il problema di ottimizzazione Multi-Obiettivo,

Normalized Normal Constraint Method

che per questa trattazione è il

(NNCM) per il caso n-obiettivo, approfondito dettagliatamente nel

paragrafo 3.3.2.1 del capitolo 3;

4. File di output: .out,

obbligatoriamente con estensione su cui sono salvati

gli output della risoluzione.

Gli elementi principali di un programma AMPL sono:

Insiemi;

Dati;

Variabili;

Funzione obiettivo;

Vincoli.

Non si entrerà nel dettaglio del linguaggio di modellazione poiché esula dal reale

obiettivo della trattazione. 108

4.5. Caso applicativo

Nel prossimo paragrafo sarà illustrata la frontiera di Pareto (modellazione bi-

obiettivo) ottenuta applicando il modello Multi-Obiettivo espresso nel paragrafo

4.3 all’istanza di dati che sarà successivamente descritta.

Per quanto riguarda i dati delle UdC da stoccare a magazzino il caso applicativo

allegato1.

fa riferimento alle informazioni contenute in Sinteticamente:

p

Le tipologie di prodotto da stoccare a magazzino sono 145;

G

La giacenza che dovrà contenere il magazzino automatizzato è pari a

3310 UdC (capienza magazzino: 4104 UdC, con il 20% in più di vani vuoti).

G

In base alla giacenza di stoccaggio e ai seguenti parametri di progettazione si è

deciso di definire il layout del magazzino in questo modo:

G = 3310 UdC Capienza = 4104 UdC

AS/RS AS/RS

Pallet EUR EPAL* 800 x 1200 x 144h mm

H massima merce 1500 mm

Spessore corrente 0,1 m

Spessore montante 0,1 m

Larghezza corridoi** 1,5 m

Giochi laterali 0,1 m

Gioco superiore 0,1 m

Posizionamento UdC Disposizione di punta

Semplice profondità

G 6 UdC

unità di base

B (lunghezza unità di base) 2,9 m

b

H (altezza unità di base) 1,844 m

b

L (larghezza unità di base) 4,1 m

b

B (lunghezza AS/RS) 55,2 m 19 campate

H (altezza AS/RS) 22,128 m 12 livelli

L (larghezza AS/RS) 12,3 m 3 corridoi/traslo

allegato 2

* Dimensioni pallet EUR EPAL in ** Ipotizzata uguale per tutti i corridoi

Ipotesi: si considerano nulli il gioco di schiena fra le scaffalature e il tempo di carico/scarico

109

Per l’applicazione del metodo NNCM si è optato per un valore di m pari a 21

1

(numero di punti ottenuti sulla frontiera di Pareto), in accordo al valore

comunemente adottato in letteratura scientifica.

I parametri adottatati per il particolare caso applicativo oggetto di analisi sono i

seguenti:

Parametro Valore

m [Kg] Allegato 1

p

q [UdC] Allegato 1

p

f [%] Allegato 1

p

m [Kg] 4000 Kg

t

ξ [Kg] 2200 Kg

22000 Kg

[Kg]

ω [m] 8,2 m

α 0,0921

λ 1,35

H [m] 1,844 m

h [m] 0,922 m

p 2 2

g [m/s ] 9,80665 m/sec

) e la matrice dell’energia (E ) definite rispettivamente

La matrice dei tempi (t

bslr bslr

per valutare i tempi di viaggio e l’energia spesa dal trasloelevatore per

raggiungere un determinato vano del magazzino automatizzato sono state

calcolate mediante l’applicazione delle espressioni definite nei capitoli 2 e 4 su

foglio elettronico di lavoro Excel,

un con i seguenti parametri:

2

l [m] 5 v [m/s] 3 a [m/s ] 0,5 f 0,05

start x x x

2

l [m] 4,1 v [m/s] 0,7 a [m/s ] 0,4 f 0,03

1 z z y

2

l [m] 6 v [m/s] 1 g [m/s ] 9,806 f 0,01

2 conv z

l [m] 3

3 110

Si mostra la frontiera di Pareto ottenuta risolvendo il modello Mʹ′ per l’istanza di

dati descritta nelle pagine precedenti:

Frontiera  di  Pareto  non  Normalizzata  

1400000.00   1  

1200000.00   21  

1000000.00   Utopia  Point  

Energia  [J]   800000.00  

600000.00  

400000.00  

200000.00  

0.00  

56.50   57.00   57.50   58.00   58.50   59.00   59.50   60.00   60.50   61.00   61.50  

Tempo  [s]  

Frontiera  di  Pareto  Normalizzata  

1.2   1  

1.0  

s

Energia  normalizzata   0.8  

0.6  

0.4  

0.2   21  

Utopia  Point  

0.0  

-­‐0.2   0.0   0.2   0.4   0.6   0.8   1.0   1.2  

Tempo  normalizzato  

111

La tabella seguente mostra i valori degli obiettivi per le varie soluzioni ottenute,

fornendo i valori di tempo e di energia sia normalizzati che non normalizzati:

Soluzione Tempo [s] Energia [J] Tempo (norm) Energia (norm)

1 57,13037835 1182311,30173722 0 1

* *

2 57,11313361 1158363,89172796 -0,004568508 0.895430500

3 57,13907784 1137037,16579279 0,002304685 0,802304560

4 57,18743827 1117070,08993237 0,015116415 0,715115710

5 57,25511853 1098275,24047321 0,033046390 0,633045540

6 57,34535299 1080849,06683453 0,056951466 0.556951872

7 57,44443597 1063959,12258306 0,114916786 0,414916510

8 57,56415463 1048321,61808492 0,114916786 0,414916510

9 57,70289851 1033838,26655746 0,151673064 0,351673060

10 57,86002614 1020469,98752773 0,193299596 0,293298720

11 58,03589360 1008238,85522243 0,239890717 0,239889880

12 58,23138004 997198,00442820 0,291679334 0,191678560

13 58,45210234 987688,17152543 0,350153479 0,150152630

14 58,68628906 978995,38043350 0,412194642 0,112194420

15 58,94397962 971728,50102809 0,480462487 0,080462640

16 59,22455617 965849,76322866 0,554793326 0,054792362

17 59,52284504 961046,03133903 0,633816547 0,033816238

18 59,85208016 958119,91212805 0,721038101 0,021038956

19 60,17747175 954961,93267329 0,807241424 0,007249225

20 60,52851193 953358,67444166 0,900239614 0,000248388

21 60,90507736 953301,79122736 1 0

* Il valore temporale normalizzato per la soluzione 2 risulta negativo poiché la risoluzione

preliminare per definire gli Anchor Points (soluzione 1 e 21) sono state effettuate sulla base di 6

ore, mentre per i punti intermedi della Frontiera si è impostato un tempo limite pari a 12 ore.

Avendo a disposizione il doppio del tempo, il risolutore ha determinato una soluzione temporale

migliore di quella utilizzata come base di partenza per l’applicazione. La metodologia rimane in

ogni modo corretta e solida. 112

È possibile calcolare l’indice Il , espresso in percentuale, che rappresenta la

i

distanza di ogni singola soluzione dall’Utopia Point per i diversi obiettivi. Sono

preferibili valori bassi di questo indice, poiché indicano prossimità all’Utopia

Point. È definito come la differenza fra il valore dell’i-esimo obiettivo e il

miglior valore ottenibile per quell’obiettivo rapportato al miglior valore ottimale

per quell’obiettivo. In questo modo il decisore finale sarà facilitato nella scelta

della soluzione di compromesso a lui più congeniale.

∗ ∗

= −    /  

Soluzione Il Tempo [%] Il Energia [%]

i i

1 0,00 24,02

*

2 -0,03 21,51%

3 0,02 19,27

4 0,10 17,18

5 0,22 15,21

6 0,38 13,38

7 0,55 11,61

8 0,76 9,97

9 1,00 8,45

10 1,28 7,05

11 1,58 5,76

12 1,93 4,60

13 2,31 3,61

14 2,72 2,70

15 3,17 1,93

16 3,67 1,32

17 4,19 0,81

18 4,76 0,51

19 5,33 0,17

20 5,95 0,01

21 6,61 0,00

* Vedi nota pagina precedente 113

30.00%  

Distanza  dall'Utopia  Point  per  gli  obiettivi  [%]   25.00%  

20.00%  

15.00%  

10.00%  

5.00%  

0.00%   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21  

Soluzione  

ottimo   ottimo  

temporale     energetico  

Tempo   Energia  

Le frontiera di Pareto non normalizzata e quella normalizzata presentano un

andamento molto simile. La pendenza della curva ottenuta per il caso applicativo

oggetto di analisi non è marcata: utilizzando il grafico soprastante è possibile

individuare rapidamente quali siano le soluzioni di compromesso che si scostano

in maniera minore dalle soluzioni ottimali per entrambi gli obiettivi.

Soluzioni di buon compromesso sono quindi individuabili nelle 13, 14 e 15.

Le prime soluzioni (1, …,7), nonostante non si scostino in maniera importante

dall’obiettivo temporale, presentano uno spiccato divario rispetto all’obiettivo

energetico.

In decisore finale si sposterà quindi verso l’ottimo temporale o verso l’ottimo

energetico, scegliendo la soluzione di allocazione della merce all’interno del

magazzino automatizzato che meglio aderisce alle proprie preferenze di

progettazione. 114

Conclusioni e sviluppi futuri

L’elaborato di tesi sviluppato si è posto l’obiettivo di migliorare, quindi

ottimizzare, la progettazione della configurazione dei magazzini intensivi

automatizzati per quanto riguarda la disposizione delle diverse tipologie di

prodotti al suo interno.

In seguito all’analisi delle principali metodologie di collocazione della merce,

basate sui tempi di prelievo e deposito dei materiali, si è sviluppato un nuovo

criterio di allocazione che si pone l’obiettivo di minimizzare la spesa energetica

dei trasloelevatori presenti nel magazzino.

Avendo quindi a disposizione due criteri differenti con i quali operare (tempo ed

energia) si è illustrata un’innovativa tecnica matematica conosciuta in letteratura

analisi Multi-Obiettivo:

scientifica come l’approccio tradizionale alla risoluzione

di un problema multi-criterio è ormai oggi sostituito dall’approccio di Pareto che

prevede la costruzione di una curva rappresentante un insieme di soluzioni di

compromesso fra i diversi obiettivi.

Il progettista si trova di fronte a un numero definito di soluzioni, tutte ottime

secondo Pareto, dalle quali potrà scegliere una configurazione del magazzino

piuttosto che un’altra in relazione alle proprie esigenze e priorità.

Rispetto alle tecniche tradizionali, nell’approccio di Pareto la soggettività

rappresentata dalle preferenze del decisore entra in gioco solo a valle della

definizione matematica, quindi imprescindibile, dell’insieme delle soluzioni.

La trattazione include l’applicazione del metodo a un caso applicativo reale.

Il metodo di risoluzione utilizzato per determinare le soluzioni di compromesso è

Normalized Normal Constraint Method

il (NNCM).

In questo campo di applicazione, ulteriori passi in avanti possono essere

rappresentati dal miglioramento dei modelli che descrivono i diversi criteri di

allocazione della merce, in modo tale da riprodurre la realtà in maniera sempre

più precisa. Inoltre, oltre ai principi di tempo ed energia analizzati, gli aspetti di

progettazione che possono rientrare a pieno titolo in questa problematica possono

essere estesi a nuovi criteri. 115

Possono quindi essere sviluppate nuove funzioni obiettivo per estendere l’analisi

Multi-Obiettivo, come per esempio quella relativa alla stabilità delle scaffalature

nell’eventualità di un evento sismico (criterio già approfondito all’interno del

dipartimento) oppure legate all’impatto ambientale e quindi all’emissione di

) da parte dei trasloelevatori.

anidride carbonica (CO 2 116

Ringraziamenti

Al termine della trattazione di tesi sviluppata desidero ringraziare il mio relatore,

Professore Mauro Gamberi, per avermi costantemente guidato e aiutato nelle

problematiche che in questi mesi di lavoro sono emerse nella stesura

dell’elaborato. Estendo inoltre il mio ringraziamento all’Ing. Marco Bortolini e

all’Ing. Lucia Botti per essere sempre stati pronti a rispondere a ogni mia

necessità supportandomi nel momento del bisogno.

Il mio ultimo e sentito ringraziamento va ai miei genitori che nel corso dei cinque

anni di studio mi hanno sempre sostenuto, incoraggiato e supportato.

117

Allegati

Allegato 1 – Dati delle UdC da stoccare a magazzino

f m

p p q [UdC]

p p

[prelievi/anno] [kg/UdC]

1 0,002250731 626 30

2 0 626 40

3 0,000675219 626 40

4 0,015304974 626 70

5 0,000675219 626 30

6 0,000450146 626 10

7 0,002475805 626 50

8 0 804 10

9 0,014179608 804 25

10 0,002700878 804 40

11 0,001350439 804 30

12 0,016655413 896 30

13 0,003826244 896 40

14 0,000450146 896 30

15 0,017105559 696 35

16 0,000225073 696 40

17 0,002925951 696 55

18 0 696 10

19 0,02003151 300 30

20 0,005176682 300 20

21 0,008327707 300 20

22 0,012379023 325 20

23 0,000225073 325 30

24 0,006752194 325 30

25 0,025433266 350 40

26 0,007427414 350 10

27 0,008777853 350 20

28 0,01643034 425 20

29 0,005401756 425 20

30 0,004726536 425 20

31 0,027458924 1159 20

32 0,007202341 1159 10

33 0,00855278 1159 10

34 0,024532973 730 30

35 0,007427414 730 10

36 0,009678145 730 10

37 0,029259509 1090 30

38 0,008327707 1090 25

39 0,011028584 1090 20

118

f m

p p

p q [UdC]

p

[prelievi/anno] [kg/UdC]

40 0,011253657 700 10

41 0,031510241 1000 35

42 0,00855278 1000 20

43 0,016205267 1000 10

44 0,011478731 1024 10

45 0,026108485 1024 25

46 0,00427639 1024 10

47 0,005851902 1024 20

48 0,027233851 758 30

49 0,00427639 758 30

50 0,011028584 758 30

51 0,033310826 748 60

52 0,006302048 748 30

53 0,013504389 748 20

54 0,020481657 888 30

55 0,002925951 888 30

56 0,004951609 888 20

57 0,026783705 1150 30

58 0,002925951 1150 30

59 0,008102633 1150 25

60 0,026108485 687 70

61 0,004501463 687 40

62 0,008327707 687 30

63 0,025208193 828 50

64 0,001800585 828 25

65 0,006076975 828 40

66 0,028134144 733 110

67 0,003376097 733 35

68 0,010128292 733 40

69 0,027458924 920 85

70 0,00360117 920 40

71 0,006752194 920 40

72 0,028359217 855 100

73 0,006527121 855 35

74 0,007652487 855 25

75 0,013504389 716 30

76 0,004051317 716 40

77 0,000675219 716 40

78 0,009002926 516 10

79 0,007202341 447 10

80 0,00427639 734 10

81 0,007652487 693 10

82 0,005626829 640 10

119

f m

p p

p q [UdC]

p

[prelievi/anno] [kg/UdC]

83 0,005626829 616 10

84 0,010803511 633 10

85 0,002475805 580 10

86 0,003376097 685 20

87 0,002025658 500 30

88 0,001800585 478 60

89 0,005401756 1185 10

90 0,005176682 593 10

91 0,003151024 1255 10

92 0,00360117 1045 10

93 0,002475805 1095 10

94 0,005626829 457 10

95 0,005851902 765 10

96 0,001800585 524 20

97 0,003151024 404 10

98 0 461 10

99 0 352 10

100 0 217 10

101 0 227 40

102 0 355 10

103 0 357 10

104 0 378 10

105 0 362 10

106 0 372 10

107 0 314 10

108 0 447 10

109 0 320 10

110 0 355 10

111 0 292 10

112 0 357 10

113 0 316 10

114 0 281 10

115 0 196 10

116 0 205 20

117 0 268 30

118 0 252 40

119 0 304 10

120 0,000675219 345 10

121 0 273 10

122 0,000450146 419 10

123 0 377 10

124 0,000900293 437 10

125 0 392 10

120

f m

p p

p q [UdC]

p

[prelievi/anno] [kg/UdC]

126 0,000675219 408 10

127 0 364 10

128 0,000675219 331 10

129 0,001800585 327 10

130 0,002475805 321 10

131 0,001125366 297 10

132 0,001350439 346 10

133 0 350 10

134 0,002700878 245 10

135 0 266 20

136 0,001575512 310 10

137 0 330 10

138 0,00427639 1660 10

139 0,003376097 1200 10

140 0,008327707 1130 10

141 0,010128292 816 10

142 0,011253657 906 10

143 0,007427414 935 10

144 0,012604096 748 10

145 0,006977268 474 10

121

Allegato 2 – Dimensioni pallet EUR EPAL

122


PAGINE

128

PESO

5.68 MB

AUTORE

bens89

PUBBLICATO

+1 anno fa


DESCRIZIONE TESI

Tesi di laurea magistrale per la cattedra del professor Gamberi. Titolo tesi: "Sviluppo di principi di allocazione della merce all'interno di magazzini automatizzati mediante modelli Multi-Obiettivo".
Attività di tesi incentrata sul completo sviluppo di un nuovo principio di allocazione della merce all'interno dei magazzini automatizzati serviti da trasloelevatori, con il fine di minimizzare il consumo di energia richiesto dal movimento di queste particolari attrezzature.
Successivamente è stata effettuata un'analisi Multi-Obiettivo, affiancando al criterio energetico sviluppato il criterio temporale (minimizzazione delle tempistiche di prelievo dei materiali) canonico utilizzato oggi nella maggior parte delle realtà aziendali.


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria gestionale
SSD:
Università: Bologna - Unibo
A.A.: 2014-2015

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher bens89 di informazioni apprese con la frequenza delle lezioni di Impianti meccanici e logistica LM e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Bologna - Unibo o del prof Gamberi Mauro.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in ingegneria gestionale

Lezioni, Valorizzazione delle risorse primarie e secondarie M
Appunto
Logistica industriale T-AB - Appunti prima parte
Appunto
Impianti industriali (2' modulo)
Appunto
Lezioni, Sistemi di produzione avanzati M
Appunto