INCERTEZZA DELLA DOMANDA NELLE CATENE DI … · La teoria delle scorte • Il problema del lotto...

INCERTEZZA DELLA DOMANDA NELLE CATENE DI SUPPORTO:

TECNICHE DI RIDUZIONE DINAMICA DELLO SPAZIO DI RICERCA PER UN

MODELLO CP

Tesi di laurea di:Roberto Rossi

Relatore:Prof. Michela Milano

Correlatori:Armagan Tarim 4C, Cork - IrlandaBrahim Hnich 4C, Cork - Irlanda

FACOLTA’ DI INGEGNERIACorso di Laurea Specialistica in Ingegneria Informatica

Applicazioni di Intelligenza Artificiale L-S

La teoria delle scorte

• Il problema del lotto economico (Ford W. Harris 1915)– bilanciare costi di acquisto e di stoccaggio in presenza di una

domanda costante nel tempo e di un determinato costo fisso per ogni acquisto.

cost

time

Overall cost

Order cost

Inventory cost

dh

kt

2* =k = costo fisso di produzioned = domandah = costo di stoccaggio unitario

La teoria delle scorte

• Il problema del lotto economico (Ford W. Harris 1915)– bilanciare costi di acquisto e di stoccaggio in presenza di una

domanda costante nel tempo e di un determinato costo fisso per ogni acquisto.

time

items

*3t*2t*t

*q

h

dkq

2* =Quantità ottima per ordine:

0

Motivazioni

• Davis (1993): il 60% degli investimenti impegnati nel sistema di produzione e distribuzione della Hewlett-Packard sono attribuibili ad incertezza della domanda da parte del mercato

• Come far fronte all’incertezza della domanda?– gestione delle scorte – gestione ottima dei costi di produzione/acquisto e stoccaggio

cost

time

dh

kt

2* = Lotto Economico!

La soluzione presentata

• periodo ottimo di riordino:• quantità ottima di riordino:

• politica ottima: domanda esattamente soddisfatta in ogni ciclo di rifornimento

• algoritmo di risoluzione: h

dkq

2* =

time

items

*3t*2t*t

*q

0

*q

*t

dh

kt

2* =

Lotto economico

domanda deterministicadomanda stocastica

Scarf (1960)(s,S) �politica ottima

domanda statica

EOQ

domanda dinamica

Wagner - Whitin

domanda statica domanda dinamica

Bookbinder & Tan (1988): strategia euristica a due fasistatic-dynamic uncertainty, politica (R,S)

Tarim & Kingsman (2003)modello MIP, politica (R,S),static-dynamic uncertainty

Tarim & Smith (2005)modello CP, politica (R,S),static-dynamic uncertainty

soluzione euristica

soluzione ottima

Lotto economico



domanda statica

EOQ

domanda dinamica

Wagner - Whitin





soluzione euristica

soluzione ottima

t

765 ,, ddd

86411, 12

78910, 11

71010

60089

5558

469567

400456

38445

27734

186123

11412

851

min cost. politica ott.[1]

903864901

808789

710741734

674600

555572

505496469502

462401400

375348

287277

216223186

187114

85

11456

9879

11067

11945

8667

10534

11426

9861

10161

10236

10229

8569

costo ord. domanda

121110987654321(mese)

[1] Viene mostrato solo l’ultimo periodo di ordinazione; 567 indica che la politica ottima per i periodi da 1 a 7 consiste nell’ordinare nel periodo 5 per soddisfare

, adottando una politica ottima per i periodi da 1 a 4 considerati separatamente (planning horizon theorem).

Domanda deterministica e dinamica: Wagner & Whitin (1958)

��

�

�

��

�

�

−+

��

��

�−++= � �

−

= +=<≤

)1(

)1(minmin)(

1

11

tFs

jFdistF

t

t

jh

t

hkkhj

tj

I

tj

1=tδ

js

jd

1=ji

0)0( =F

1)1( sF =

Complessità: N(N+1)/2 nel caso peggiore

Domanda deterministica e dinamica: Wagner & Whitin

Soluzione mediante l'algoritmo DP di Wagner e Whiti n

0

98

29

0

97

61

0

121

60

34

0

179

112

67

0

135

56

0020406080

100120140160180200

1 3 5 7 9 11 13

periodi

scor

te

Wagner e Whitin

Domanda deterministica e dinamica: Wagner & Whitin

Soluzione equivalente per BT e Regola della Radice Quadrata

0

105

52,50

0

105

52,50

00

20

40

60

80

100

120

1 2 3 4 5

periodi

scor

te Soluzione equivalente per BTe Regola della RadiceQuadrata

Lotto economico



domanda statica

EOQ

domanda dinamica

Wagner - Whitin





soluzione euristica

soluzione ottima

Domanda stocastica

• Esaurimento scorte:

– penalizzazione nella funzione obiettivo : si rappresenta il mancato guadagno come un costo

– assegnamento di un livello di servizio in termini percentuali : dunque si assume che l’evento scorte esaurite si verifichi con una certa probabilità(tipicamente bassa < 5%) e lo si trascura nel modello

Domanda stocastica e statica

s

tempo

scorte di sicurezza

unità

esaurimento scorte

incertezza della domanda

t L

b

0

Lzb σ⋅=L tempo di arrivo delle merci

scorte di sicurezza

Lσ deviazione standard delladomanda nell’intervallo L

z livello di servizio

Politica ottima:(s,S) – Scarf 1960

d~

val. atteso per la domanda per periodo

k = costo fisso di produzioneh = costo di stoccaggio unitario

tempo

safety stock

unità

stock out


t

b

0

Domanda stocastica e statica

S

bdLs +⋅= ~

Politica ottima:(s,S) – Scarf 1960

L

Lzb σ⋅=L tempo di arrivo delle merci

scorte di sicurezza

Lσ deviazione standard delladomanda nell’intervallo L

z livello di servizio

d~

val. atteso per la domanda per periodo

bhdkdLS +⋅= ]/~

2,~

max[

k = costo fisso di produzioneh = costo di stoccaggio unitario

s

Lotto economico



domanda statica

EOQ

domanda dinamica

Wagner - Whitin





soluzione euristica

soluzione ottima

• Static uncertainty �

– tutte le decisioni vengono prese all’inizio dell’orizzonte degli eventi

• istanti di ordinazione

• quantità degli ordini

– viene incontro alle esigenze aziendali

– si basa sulla costruzione di un modello deterministicoequivalente risolto con le tecniche note:algoritmo DP Wagner & Whitin

Domanda stocastica e dinamicaBookbinder & Tan


• Dynamic uncertainty �

– Le decisioni sono prese man mano che le domande divengono note: wait-and-see

• periodo dopo periodo si effettuano ordini in funzione dei livelli di servizio richiesti

– Scomoda in termini di politiche aziendali e poco adatta per applicazioni reali (politica nervosa)

– Può tornare utile in scenari Just In Time


• Static-Dynamic Uncertainty �

– Politica (R,S)• R � Istanti in cui fissare gli ordini• S � Livelli a cui portare le scorte in seguito ad un ordine

safety stock

unità

stock out


t

b

0

S

s

Q

tempi di arrivo delle merci supposti nulli � L = 0


• Static-Dynamic Uncertainty �

– Modello per politica (R,S) difficile da risolvere in modo completo

• Silver 1978: trovare la soluzione ottima per la versione stocastica e dinamica del problema del lotto economico risulta proibitivo dal punto di vista computazionale

– Approccio euristico a due fasi• Determinazione dell’insieme R (Wagner & Whitin)• Determinazione dell’insieme S (problema LP deterministico)

Lotto economico



domanda statica

EOQ

domanda dinamica

Wagner - Whitin





soluzione euristica

soluzione ottima

Domanda stocastica e dinamicaTarim & Kingsman

• Modello MIP � completo– il costo totale atteso per la strategia ottenuta con il modello di

Bookbinder e Tan è 19704, mentre per quella di Tarim e Kingsman esso risulta essere 19404

Soluzione di BT e di TK a confronto

0

500

1000

1500

2000

2500

3000

3500

1 3 5 7 9 11

periodi

scor

te Bookbinder e Tan

Tarim e Kingsman

][ kdE

200500600650700800200700850800

10987654321Periodo(k)

333.0/ == ttvc µσ

2500=a

1=h

95.0=α )645.1( 95.0 ==αz

Lotto economico



domanda statica

EOQ

domanda dinamica

Wagner - Whitin





soluzione euristica

soluzione ottima

Domanda stocastica e dinamicaTarim & Smith

• Modello CP �

– completo– meno vincoli vs– Meno variabili decisionali vs

– Tipicamente la risoluzione di tale modello implica l’esplorazione di un numero di nodi maggiore rispetto al MIP, tuttavia i tempi di esecuzione sono migliori:

• MIP � rilassamento continuo su ogni nodo!

2/)5( 2 NN +2/)9( 2 NN +

N2N3


• Modello CP �– programmazione

stocastica

Nt ,...,1=

( )�=

+=N

ttt IhaTCE

1

~][ δmin

s.t.

0~~~

1 ≥−+ −ttt IdI Nt ,...,1=

10~~~

1 =�>−+ − tttt IdI δ Nt ,...,1=

]max,[~

]..1[j

tjt jtI δ

∈Φ≥

}0{~

�+Ζ∈tI }1,0{∈tδ

Nt ,...,1=

�=

−+++ −=Φ

+

i

jkkddd dGji

ijj

~)(],[ 1

...1α

funzione di distribuzione cumulativa



stocastica

Nt ,...,1=

( )�=

+=N

ttt IhaTCE

1

~][ δmin

s.t.

0~~~

1 ≥−+ −ttt IdI Nt ,...,1=

10~~~

1 =�>−+ − tttt IdI δ Nt ,...,1=

]max,[~

]..1[j

tjt jtI δ

∈Φ≥

}0{~

�+Ζ∈tI }1,0{∈tδ

Nt ,...,1=

�=

−+++ −=Φ

+

i

jkkddd dGji

ijj

~)(],[ 1

...1α


I

1−t t

restituzione delle merci vietata!



stocastica

Nt ,...,1=

( )�=

+=N

ttt IhaTCE

1

~][ δmin

s.t.

0~~~

1 ≥−+ −ttt IdI Nt ,...,1=

10~~~

1 =�>−+ − tttt IdI δ Nt ,...,1=

]max,[~

]..1[j

tjt jtI δ

∈Φ≥

}0{~

�+Ζ∈tI }1,0{∈tδ

Nt ,...,1=

�=

−+++ −=Φ

+

i

jkkddd dGji

ijj

~)(],[ 1

...1α


I

1−t t

I

1−t t

1=tδ

01 =∧= tt δδ



stocastica

Nt ,...,1=

( )�=

+=N

ttt IhaTCE

1

~][ δmin

s.t.

0~~~

1 ≥−+ −ttt IdI Nt ,...,1=

10~~~

1 =�>−+ − tttt IdI δ Nt ,...,1=

]max,[~

]..1[j

tjt jtI δ

∈Φ≥

}0{~

�+Ζ∈tI }1,0{∈tδ

Nt ,...,1=

�=

−+++ −=Φ

+

i

jkkddd dGji

ijj

~)(],[ 1

...1α


I

1−t t

livello di servizio


• Tecniche di filtraggio per i domini delle variabili decisionali:

– Primo metodo di riduzione• prima di iniziare la ricerca i domini delle variabili decisionali

vengono opportunamente ridotti ai soli valori candidati ad essere parte di una soluzione ottima

• Stabilisce degli UB sulla lunghezza dei possibili cicli di rifornimento candidati ad essere parte della soluzione ottima

tI

( ) ( )),1(),(),(),1(),( jkRkibjicjkckic +>∨>++}1,...,{ −∈∀ jik

I

ji k

I

ji k






tI


I

ji k

I

ji k






tI


I

ji m�

−

=

=−==∈1

* },...,,~

),(|{m

itt

Smm jmldliRRR ττ�

),( jiTm ∈∀ml =






tI


I

ji m�

−

=

=−==∈1

* },...,,~

),(|{m

itt


),( jiTm ∈∀1+= ml

l






tI


I

ji m�

−

=

=−==∈1

* },...,,~

),(|{m

itt


),( jiTm ∈∀2+= ml

l



– Secondo metodo di riduzione• Si considerano tutti i possibili scenari legati alle decisioni sugli

ordini , aggiungendo man mano ai domini i valori delle scorte per tali scenari verosimili:

– il livello di chiusura in t è pari a quello di apertura in t+1

– I livelli sono differenti: livello di chiusura in t < livello di apertura in t+1 � ordine in t+1

tItδ

I

T0 1+t

I

T0 1+t j

1+t


• Riduzione ulteriore: – Intersezione dei risultati dei due metodi: il sottoinsieme dei valori delle

scorte candidati ad essere parte della soluzione ottima è ulteriormente ristretto

9158220191680650638

{55,91}{22,58}{190,220}{161,191}{638,668,680}{608,638,650}{596,626,638}

{55,91}{22,58,538,568}{190,191,220,221,1858,1888,1900}{161,162,191,192,1801,1829,1831,1843,1859,1871}{638,666,668,680,696,708}{608,636,638,650,666,678}{596,624,626,638,654,666}

{55,91}{18,22,58}{190,220}{16,161,191}{638,668,680}{16,30,608,638,650}{7,18,596,626,638}

1234567

ISiI IIS

iI III Si

Si II � *~

iI

td123011632934733101

7654321Periodo


Tarim e Smith soluzione ottima

0192

91 58

567

220 191

1843

680 650 638

0200400600800

100012001400160018002000

1 2 3 4 5 6 7 8

periodi

scor

te

Tarim e Smith

Domanda stocastica e dinamicaEstensioni…

• Riduzione dinamica dei domini durante la ricerca

– sfrutta la soluzione parziale disponibile in un dato nodo dell’albero decisionale per ridurre i domini delle variabili decisionali eliminando i valori non ammissibili rispetto ad essa

– tre tecniche sviluppate:• rilassamento mediante programmazione dinamica• riduzione basata sul merging lemma• estensione al caso dinamico delle tecniche di filtraggio a priori

presentate da Tarim e Smith


• Rilassamento mediante programmazione dinamica

– Branch and Bound

– Dijkstra per SPP in

1 2 N+1

N+1

i

j

∞

∞ ∞

∞ ∞ ∞

∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞

)1,1(c

)2,( −jic )1,( −jic

)1,1( −+ jic

),( Nic

),1( Nc)1,1( −jc

),( NNc

2/)1( +⋅ NN


?

*CC ≥

*CC <

x

• Rilassamento mediante programmazione dinamica

– Branch and Bound


Merging lemma: • data una soluzione parziale, se in un certo periodo i non è previsto un

rifornimento, è possibile ottenere una formulazione equivalente dell’istanza del problema accorpando tale periodo i al precedente.

• estensione al caso di più periodi– Il valor medio della domanda nel nuovo periodo che accorpa i

precedenti sarà

– La deviazione standard della domanda sarà

�=

=j

ittk µµ '

�=

=j

ittk2

' σσ

I

i 1+i

0=iδ

1−i

I

1+i*)1( −i


Merging lemma

td

td3216319017192401021613462181

242322212019181716151413Periodo

5737161281642818092116128073

121110987654321Periodo

Domini ridotti staticamente valori ammissibili per i livelli di chiusura delle scorte

metodo I di riduzione

0

50

100

150

200

250

300

350

400

1 6 11 16 21

periodi

scor

te


i*iI

iδi*iI iδ

110110010110

9973398886763612310610412391

131415161718192021222324

101101010110

4040701738112810011991889437

123456789101112

Merging lemma

Domini ridotti dinamicamentevalori ammissibili per i livelli di chiusura delle scorte


0

50

100

150

200

250

1 6 11 16 21

periodi

scor

teDomanda stocastica e dinamica

Estensioni…

{40,209}{70,81}{81}{100}{91}{88,190}{37,96}{99,203}{39,107}{88,143}{23,36,91}{106}{104}{91}

532916384219203318427680259214618327615000259211704371533610027593

73128208208192161941819616152209190195

{1,2}{3}{4,5}{6,7}{8,9}{10}{11,12}{13}{14,15}{16}{17,18,19}{20,21}{22}{23,24}

0~~~

1 =−+ −ttt IdI

I

jtit <∧>

j*)1( −i

*i *id 2.)var./( * coeff

iσ *

*iI

Merging lemma



iσ *

*iI

{40,209}{70,81}{81}{100}{91}{88,190}{37,96}{99,203}{39,107}{88,143}{23,36,91}{106}{104}{91}

532916384219203318427680259214618327615000259211704371533610027593

73128208208192161941819616152209190195

{1,2}{3}{4,5}{6,7}{8,9}{10}{11,12}{13}{14,15}{16}{17,18,19}{20,21}{22}{23,24}



0

50

100

150

200

250

1 6 11 16 21

periodi

scor

te

0~~~

1 =−+ −ttt IdI

I

1−i j

jtit <∧>

1

~~~−=+ ttt IdI�

1+ii

Merging lemma



iσ *

*iI

{40,209}{70,81}{81}{100}{91}{88,190}{37,96}{99,203}{39,107}{88,143}{23,36,91}{106}{104}{91}

532916384219203318427680259214618327615000259211704371533610027593

73128208208192161941819616152209190195

{1,2}{3}{4,5}{6,7}{8,9}{10}{11,12}{13}{14,15}{16}{17,18,19}{20,21}{22}{23,24}



0

50

100

150

200

250

1 6 11 16 21

periodi

scor

te

0~~~

1 =−+ −ttt IdI

I

jtit <∧>

1

~~~−=+ ttt IdI�

Nt ,...,1=

( )�=

+=N

ttt IhaTCE

1

~][ δmin

s.t.

0~~~

1 ≥−+ −ttt IdI Nt ,...,1=

10~~~

1 =�>−+ − tttt IdI δ Nt ,...,1=

]max,[~

]..1[j

tjt jtI δ

∈Φ≥

}0{~

�+Ζ∈tI }1,0{∈tδ

Nt ,...,1=

1−i j1+ii

Merging lemma



iσ *

*iI

{40,209}{70,81}{81}{100}{91}{88,190}{37,96}{99,203}{39,107}{88,143}{23,36,91}{106}{104}{91}

532916384219203318427680259214618327615000259211704371533610027593

73128208208192161941819616152209190195

{1,2}{3}{4,5}{6,7}{8,9}{10}{11,12}{13}{14,15}{16}{17,18,19}{20,21}{22}{23,24}



0

50

100

150

200

250

1 6 11 16 21

periodi

scor

te

0~~~

1 =−+ −ttt IdI

I

jtit <∧>

1

~~~−=+ ttt IdI�

Nt ,...,1=

( )�=

+=N

ttt IhaTCE

1

~][ δmin

s.t.

0~~~

1 ≥−+ −ttt IdI Nt ,...,1=

10~~~

1 =�>−+ − tttt IdI δ Nt ,...,1=

]max,[~

]..1[j

tjt jtI δ

∈Φ≥

}0{~

�+Ζ∈tI }1,0{∈tδ

Nt ,...,1=

1−i j1+ii

Merging lemma


• Estensione dinamica al primo metodo di riduzione:

td123011632934733101

7654321Periodo

i ISiI IIS

iI III Si

Si II � *~

iI

9158220191680650638

{55,91}{22,58}{190,220}{161,191}{638,668,680}{608,638,650}{596,626,638}

{55,91}{22,58,538,568}{190,191,220,221,1858,1888,1900}{161,162,191,192,1801,1829,1831,1843,1859,1871}{638,666,668,680,696,708}{608,636,638,650,666,678}{596,624,626,638,654,666}

{55,91}{18,22,58}{190,220}{16,161,191}{638,668,680}{16,30,608,638,650}{7,18,596,626,638}

1234567


• Estensione dinamica al primo metodo di riduzione:– Si considerano le proposizioni alla base del metodo di filtraggio a

priori dei domini e le si estende ipotizzando che una soluzione parziale sia data

• Gli UB sulla lunghezza dei cicli di rifornimento vengono rivisti sulla base della soluzione parziale che si ha a disposizione

– Esempio: • proposizione che stabilisce le condizioni con cui è possibile definire

un upper bound sulla lunghezza di un qualsiasi ciclo di rifornimentoI

i UB

1=iδIP:







i UB

1=iδIP:

k







i UB

1=iδIP:

UBkikk <∧>∃ |k

1=kδand

= minimo di taliUB k�







i UB

1=iδIP:

UBkikk <∧>∃ |k

1=kδand

= minimo di taliUB k�


• Estensione dinamica al primo metodo di riduzione:

td123011632934733101

7654321Periodo

i ISiI

ISiI

},,1,0,1,,1{ ••• III Si

Si II � *~

iIdinamica �

9158220191680650638

{55,91}{22,58}{190,220}{161,191}{638,668,680}{608,638,650}{596,626,638}

I1 2 {55, 91}I2 2 {22, 58}I3 1 {220}I4 1 {191}I5 3 {638, 668, 680}I6 3 {608, 638, 650}I7 3 {596, 626, 638}

{55,91}{18,22,58}{190,220}{16,161,191}{638,668,680}{16,30,608,638,650}{7,18,596,626,638}

1234567

I

3 5

220191

Test – Euristica Most ConstrainedDomanda stagionale

0,001

0,01

0,1

1

10

100

1000

10000

100000

24 26 28 30 32 34 36 38 40 42 44 46 48 50

periodi

seco

ndi

ILOG - CP model

CPLEX - MIP model

Choco - CP model dyn red

Choco - CP model

Domanda stagionale

1

10

100

1000

10000

100000

1000000

10000000

100000000

24 26 28 30 32 34 36 38 40 42 44 46 48 50

periodi

nodi

ILOG - CP model

CPLEX - MIP model

Choco - CP model

Choco - CP model dyn red

Test – Euristica Most ConstrainedRandom runs - 50 instances - 30 periods

00,20,40,60,8

11,21,41,61,8

100 200 400

ordering cost

seco

nds

mean time

Random runs - 50 instances - 30 periods

0

500

1000

1500

2000

2500

3000

3500

4000

100 200 400

ordering cost

node

s

mean nodes number

Conclusioni

• Miglioramento dello stato dell’arte per la formulazione stocastica e dinamica del problema del lotto economico

• Strategia di risoluzione in grado di trattare istanze con dimensioni significative– di fatto applicabile a problemi reali

• Robustezza della strategia verso variazioni nei parametri del modello

• Estensione della strategia per modelli più realistici– vincoli di capacità– merci deperibili

Date post:	14-Feb-2019
Category:	Documents
Upload:	dangthien
View:	215 times
Download:	0 times

INCERTEZZA DELLA DOMANDA NELLE CATENE DI … · La teoria delle scorte • Il problema del lotto...

Documents