Tesi, Sviluppo di principi di allocazione della merce all'interno di magazzini automatizzati mediante modelli Multi-Obiettivo
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
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.
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
