2 – GESTIONE DEI RICAVI

2 – GESTIONE DEI RICAVI

Le tecniche di gestione dei ricavi vengono spesso definite come il modo per allocare il giusto ammontare di capacità, per il giusto cliente, nel momento giusto, imponendo il prezzo giusto, con lo scopo di massimizzare il profitto derivante.

In questo capitolo esploreremo i principali modelli e i relativi metodi di risoluzione usati nelle varie tecniche di gestione dei ricavi, ponendo particolare attenzione a quelli cosiddetti iterativi; il problema che vogliamo risolvere è noto come controllo di capacità, ovvero, l’allocazione ottimale delle risorse disponibili.

Partiremo con l’analisi del caso semplice in cui sia presente una sola risorsa, per arrivare a vedere come si possono adeguare i concetti studiati al caso più complesso con più risorse.

2.1 Gestione dei ricavi: principi

Le tecniche per la gestione dei ricavi sono applicabili in settori aventi certe caratteristiche: - capacità limitata e immediatamente deperibile, ad esempio, un posto su un aereo o una

camera d’albergo;

- le prenotazioni dei clienti devono essere programmate per tempo e questo è un aspetto che permette alle compagnie di poter monitorare preventivamente il bisogno successivo;

- i prezzi cambiano in base all’apertura o chiusura di classi predefinite di prezzo-prenotazione, come succede quando si acquista un biglietto aereo in tempi differenti.

Spesso per analizzare le componenti delle tecniche dei gestione dei ricavi si fa uso della matrice di Kimes in cui si mettono in evidenza il prezzo e la deperibilità quali criteri di scelta del tipo di modello; vediamola meglio.

Figura 15 Matrice di Kimes

Le aziende che tipicamente integrano con successo dei processi di gestione dei ricavi si caratterizzano nel quadrante relativo a prodotti dal prezzo variabile e durata prevedibile; negli ultimi tempi, però, queste tecniche si stanno pian piano espandendo fino a coprire l’intera matrice con buoni esiti.

2.2 Allocazione ottimale di una singola risorsa

Analizziamo come allocare in modo ottimale una certa risorsa fra più classi di domanda; esempi tipici sono il controllo della vendita dei biglietti delle diverse classi di un certo volo, o la prenotazione di camere d’albergo di una certa classe per un certo periodo.

Esistono diversi meccanismi di controllo del prezzo, che si differenziano sostanzialmente per le soglie impostate e per le modalità di aggiornamento; andiamo a illustrarne alcuni:

B B B

Booking limitooking limitooking limitooking limit

Indica le soglie oltre le quali non è possibile vendere un particolare bene ai richiedenti, soglie che limitano, quindi, la capacità di allocazione a una certa classe; spesso la capacità reale eccede il limite posto ma questo può essere utilizzato quale tattica con cui prediligere una o l’altra classe.

I booking limits possono essere di due tipi:

1) partizionati (partitioned), quando dividono la capacità della risorsa in blocchi distinti per ogni classe di domanda, e

2) annidati (nested), quando dividono la capacità in blocchi sovrapponibili gerarchicamente, ovvero, se necessario, la classe superiore può usufruire delle risorse preventivamente dedicate a quella inferiore.

Spesso l’utilizzo di booking limit del primo tipo appare troppo restrittivo se si considera che le classi superiori sono quelle più redditizie, perciò, si propende per il secondo tipo.

P P P

Protection levelrotection levelrotection levelrotection level

Indica il quantitativo di risorsa da considerarsi dedicato a una certa classe o insieme di classi; anch’essi possono essere di tipo partizionati (partitioned) o annidati (nested) con lo stesso significato visto sopra. B B B

Bid priceid priceid priceid price

Consiste nel fissare una soglia di prezzo il cui livello dipende da una serie di fattori; una certa richiesta viene accettata se il ricavo derivante da essa supera questa soglia.

Questa tecnica è più semplice delle precedenti in quanto consiste semplicemente nel fissare una soglia per ogni tempo e non un insieme di livelli per ogni classe; fissare le soglie in maniera statica può diventare, però, dannoso in quanto non si tiene conto delle condizioni reali, perciò, una buona soluzione potrebbe essere esprimere soglie in funzione della capacità residua.

Bid price risulta essere un buon metodo in quei casi in cui è possibile discriminare esattamente le richieste in base ai ricavi.

Formalizzando, definiamo bjil booking limit per una certa classe j; esso equivale alla differenza fra la capacità e il protection level delle classi j-1 e superiori.

Il processo standard che utilizza i booking limit prende il nome di Standard Nesting Standard Nesting Standard Nesting Standard Nesting e si svolge nei seguenti passi:

- una prenotazione per una certa classe j viene accettata se o se vi è della capacità residua

o il numero totale delle prenotazioni accettate per j non eccede il relativo b_j.

La capacità destinata a una certa classe viene calcolata basandosi su previsioni del quantitativo futuro necessario e adeguandola man mano.

Un'altra tecnica meno utilizzata è Theft NestingTheft NestingTheft NestingTheft Nesting:

- si basa sul principio che una prenotazione che venga accettata per la classe j riduce sia la capacità di questa classe che di tutte quelle ad essa inferiori.

Questa tecnica, a differenza della precedente, è detta senza memoria perché le quantità riservate rimangono tali fino alla fine, e non vengono adeguate.

Le due tecniche sono comunque equivalenti solo nel caso poco reale in cui le richieste arrivate seguano un ordine, ovvero, riguardino gerarchicamente le classi, dalla più bassa alla più alta; solitamente,

Standard Nesting Standard Nesting Standard Nesting

Standard Nesting è la tecnica utilizzata. Di seguito andremo a vedere i modelli statici.

Occorre fare delle assunzioni esemplificative necessarie per la nostra modellazione:

1. la domanda per le differenti classi arriva in intervalli di tempo non sovrapposti; questo aspetto è poco reale ma rappresenta comunque una buona approssimazione (ad esempio, per quanto riguarda le prenotazioni aeree spesso arrivano prima quelle a tariffa scontata che quelle a tariffa piena);

2. per semplicità nei calcoli, le domande per le varie classi si suppongono indipendenti;

3. si suppone che i segmenti siano ben formati in modo tale che un soggetto di una certa classe non acquisti nella classe inferiore;

4. si assume che un certo quantitativo di richieste arrivi in un certo periodo e che la decisione sia semplicemente quale porzione di essa accettare, mentre nella realtà si assiste anche delle richieste sequenziali;

5. le richieste di gruppo possono essere parzialmente accettate, ovvero si possono accettare anche solo le richieste di alcuni clienti;

6. non si considera la presenza di rischi legati alle decisioni.

2.2.1 Modello di Littlewood – a 2 classi

Si hanno due classi ognuna con il proprio prezzo p1 > p2 la capacità globale è C

si assume che non si possano avere cancellazioni o overbooking nelle prenotazioni la domanda per la classe j si identifica con Dj e la sua distribuzione con Fj

Posto che la domanda per la classe 2 arriva per prima, il problema è quante prenotazioni accettare prima di sapere quale sarà la domanda per la classe 1.

La soluzione potrebbe essere derivata utilizzando un’analisi marginale:

se si suppone di avere x unità residue e di ricevere una richiesta per la classe 2, se accettiamo, otteniamo un ricavo di p2

quindi il valore atteso dalla vendita dell’x-esima unità per la classe 1 è dato da

)

(

₁ 1

P

D

x

p

⋅

≥

e perciò, ha senso accettare la richiesta per la classe 2 fino a che il relativo prezzo è superiore al valore atteso sopra detto, ovvero fino a che

p

₂

≥

(

p

₁

⋅

P

(

D

₁

≥

x

))

.

Possiamo individuare un protection level ottimale y1* tale che se la capacità residua è superiore ad esso, decidiamo di accettare la richiesta della classe 2; in particolare questo livello è tale che:

))

(

(

1 1 1* 2

p

P

D

y

p

<

⋅

≥

e

))

1

(

(

_{1 1 1}* 2

≥

p

⋅

P

D

≥

y

+

p

Se come spesso accade utilizziamo una distribuzione continua per modellare la domanda, il livello ottimale y1* è dato dalla regola di Littlewoodregola di Littlewoodregola di Littlewoodregola di Littlewood:

)) ( ( * 1 1 1 2 p P D y p = ⋅ > o equivalentemente

(

1

)

1 2 1 1 * 1

p

p

F

y

=

−

−

. Perciò, impostare un protection level a *

1

y , oppure un booking limit a * 1 *

2 c y

b = − o ancora, usare un bid price a

Π

(

x

)

=

p

₁

⋅

P

(

D

₁

>

x

)

sono scelte ottimali.

La formula permette di ottimizzare la decisione senza applicare effettivamente l’algoritmo prima visto. Il booking limit, o il protection level se si preferisce, può essere calcolato partendo dal rapporto fra le due tariffe. Il protection level ottimale è tale che la probabilità che la domanda per la tariffa piena lo superi è uguale al rapporto fra i prezzi.

Si può pensare che il rapporto tra i due prezzi esprima un tasso di conversione fra il ricavo da un biglietto pieno e uno scontato, che uguaglia il rischio di non vendere il biglietto pieno per un posto mantenuto disponibile rifiutando di venderlo prima a prezzo scontato.

2.2.2 Estendiamo il modello di Littlewood a n-classi Si hanno n classi ognuna con il proprio prezzo pi

la domanda per le classi arriva in n intervalli, in ordine crescente in base al prezzo, ovvero, al tempo n, la classe n, al tempo n-1 la classe n-1 e così via.

Questo problema può essere risolto utilizzando la tecnica della programmazione dinamicaprogrammazione dinamicaprogrammazione dinamica, ponendo ogni programmazione dinamica intervallo come uno stato.

Supponendo di conoscere a priori tutte le domande Dj di ogni stato, sintetizziamo una serie di passi: • all’interno dello stato j arrivano delle richieste, quindi, si ha una domanda Dj

• occorre decidere l’ammontare della quantità u da accettare in modo che sia inferiore alla capacità residua x

la quantità ottimale u* sarà in funzione dello stato, della domanda e della capacità residua

)

,

,

(

* * j

D

x

j

u

u

=

• il ricavo derivante è dato da pjue la capacità residuale per lo stato successivo sarà

x

−

u

.

Una buona formalizzazione è ottenibile anche senza supporre di avere completa conoscenza delle domande, e calcolando la quantità u non in funzione di Dj ma del valore che si vuole massimizzare.

Posta Vj(x) la funzione del valore all’inizio dello stato j, una volta rilevata la quantità Dj è possibile calcolare u* in modo che la massimizzi,

perciò, Vj(x) altro non è che il valore ottimale atteso con una domanda pari a Dj, e utilizziamo l’equazione di Bellmanequazione di Bellmanequazione di Bellman per descriverla: equazione di Bellman

C

x

x

V

u

x

V

u

p

E

x

V

_{j u D x j j} j

,...

1

,

0

0

)

(

)}]

(

{

[max

)

(

0 1 } , min{ 0

=

=

−

+

=

≤ ≤ −

Approfondiamo il concetto di programmazione dinamica:

Definiamo

V

(

x

_t

)

=

e

(

x

_t

)

+

V

*

(

x

_t

)

come un’approssimazione iniziale al tempo t

formata dal valore ottimale (V*(x_t)) e da un fattore di errore (e(x_t)). Attuando una qualche azione si passa a

V

(

x

_t+1

)

=

e

(

x

_t+1

)

+

V

*

(

x

_t+1

)

.

Tra le due equazioni esiste una semplice relazione definita dall’equazione di Bellman:

)

(

)

(

)

(

1 * * +

+

=

_{t t} t

e

x

V

x

x

V

γ

dove

γ

rappresenta un fattore di sconto usato per deprezzare o incrementare il contributo degli stati futuri.

Se definiamo una politica

π

la funzione del valore V_π per questa politica rappresenta il costo e ricavo derivante dall’applicazione della politica

π

partendo da uno stato s.

Cerchiamo il valore ottimale V*.

Il valore applicando la politica

π

sarà:

]

1

,

0

[

)

'

(

)

|'

(

))

(

,

(

)

(

' ) (

∈

+

=

∑

∈

γ

γ

π

π π π

s

V

s

s

T

s

s

C

s

V

S s s

quindi, quello ottimale:

] 1 , 0 [ ) ' ( ) |' ( ) , ( min ) ( * ' ) ( * ∈       + =

∑

∈ ∈

γ

γ

T s sV s a s C s V S s a s A a

dove A(s) è l’insieme delle azioni applicabili.

Analizziamo nello specifico il caso in cui si hanno domanda e capacità discrete Analizziamo nello specifico il caso in cui si hanno domanda e capacità discrete Analizziamo nello specifico il caso in cui si hanno domanda e capacità discrete Analizziamo nello specifico il caso in cui si hanno domanda e capacità discrete

Definiamo il valore marginale atteso della capacità nello stato j come l’incremento dato dalla x-esima unità di capacità: ∆Vj(x)≡Vj(x)−Vj(x−1);

esso gode di due proprietà:

1) ∀x, j:∆V_j(x+1)≤∆V_j(x)

ovvero per un certo stato j il valore marginale è decrescente al crescere della capacità residua e per una certa capacità x il valore marginale è crescente al crescere degli stati rimanenti. Consideriamo il valore atteso ottimale allo stato j+1, sfruttando ∆V_j(x) possiamo scrivere:

))}] 1 ( ( { [max ) ( ) ( ₁ 1 } , min{ 0 1 x V x E 1 p u V x z V _{j j} u z x D u j j = + j + −∆ + − = ≤ ≤ + +

∑

Dalla proprietà 1) sappiamo che ∆Vj(x) è decrescente in x, perciò la sommatoria dell’equazione sopra

sarà decrescente in z;

ma allora conviene aumentare u fintanto che il termine della sommatoria [pj+₁u−∆Vj(x+1−z)]

diventi negativo, o fino a che la condizione di minimo [

min{

D

_j+1

,

x

}

] sia raggiunta.

• Individuiamo, un protection level ottimale come

1

,...,

1

)}

(

:

max{

1 *

−

=

∆

<

≡

₊

n

j

x

V

p

x

y

j j j

• e la quantità ottimale accettata sarà

(

1

,

,

)

min{(

)

,

1

}

* 1 * + + +

=

−

+

x

D

_j

x

y

_j

D

_j

j

u

indicando con z+ =max{ x0, }.

In questo modo

(

x

−

y

*_j

)

+ identifica la capacità residua che è possibile vendere alla classe j+1.

Figura 16 Il protection level ottimale nel modello statico

Dalla proprietà 2) discende che y₁* ≤ y*₂ ≤...y*_n, aspetto facilmente rilevabile anche graficamente dalla figura sopra: al crescere di j, pj+1 decresce e la curva ∆V_j(x) decresce, perciò il valore ottimale

y

*_j decresce anch’esso.

Definiamo C b n j y C bj j = = − ≡ * 1 * * ,..., 2 e

u

*

(

j

+

1

,

x

,

D

_j+1

)

=

min{

b

_j+1

−

(

C

−

x

))

+

,

D

_j+1

}

dove (C−x) è la capacità totale residua e

[

b

_j+1

−

(

C

−

x

))

+

]

è la capacità residua per la classe j+1. Infine, vediamo come sia possibile utilizzare anche il sistema con bid price.

Se definiamo Πj+₁(x)≡∆Vj(x) allora

=

+

1

,

,

+

)

(

₁ * j

D

x

j

u

ە ۔ ۓ0 ݏ݁ p_j+1 <Π_j+1(x) )} ( : max{z pj+₁ ≥Πj+₁ x−z altrimenti ۙ ۘ ۗ

ovvero, si decide di accettare la z-esima richiesta nello stato j+1 se il prezzo pj+1 è superiore al valore

) (

1 x z

j −

Π ₊ , in poche parole, per ogni prodotto si confrontano prezzo e valore della capacità residua.

Analizziamo ora il caso Analizziamo ora il caso Analizziamo ora il caso

Analizziamo ora il caso in cui domanda e capacità seguoin cui domanda e capacità seguoin cui domanda e capacità seguoin cui domanda e capacità seguono una distribuzione continuano una distribuzione continuano una distribuzione continuano una distribuzione continua

La modellazione è di poco più complessa rispetto alla precedente; la più importante differenza è il calcolo del valore marginale che ora si ottiene derivando Vj(x) rispetto a x: Vj(x)

x

∂ ∂

. La strategia ottimale per lo stato j+1 consiste nell’aumentare u fintanto che

) ( 1 V x u p _j x j − ∂ ∂ ≥

+ o la domanda Dj+1 sia soddisfatta.

Come in precedenza, possiamo esprimere una regola ottimale usando i protection level:

1 ,..., 1 )} ( : max{ ₁ * − = ∂ ∂ < ≡ ₊ n j x V p x y j x j j

Dobbiamo individuare un vettore Y ottimale di protection level per il vettore D delle domande (D1,…,Dn) definendo n-1 eventi che descrivono che la domanda è superiore al relativo protection level:

1 ,..., 1 } ... ,..., , { ) , ( 1 1 1 2 2 1 − = > + + > + > ≡ n j y D D y D D y D D y Bj j j

Una condizione necessaria e sufficiente affinché il vettore Y* sia ottimale è che soddisfi le n-1 equazioni

descritte da: 1 ,..., 1 )) , ( ( 1 1 * − = = + n j p p D y B P _j j

2.2.3 Un algoritmo adattivo

Guardando alla vera e propria implementazione, abbiamo due possibilità di azione: un procedimento iterativo sfruttando la programmazione dinamica, oppure l’integrazione con un metodo Monte Carlo.

Per quanto riguarda l’approccio iterativo si integra la formula della quantità ottimale u* nell’equazione di Bellman ottenendo:

})]

)

(

,

min{

(

}

)

(

,

min{

[

)

(

=

j j

−

*j₋₁ +

+

j₋₁

−

j

−

*j₋₁ + j

x

E

p

D

x

y

V

x

D

x

y

V

.

Il secondo approccio meglio si adatta al caso continuo, si basa sull’idea di simulare un grande numero k di vettori di domanda, cercando di arrivare a selezionare quello che meglio approssima quello ottimale.

Di seguito riportiamo uno pseudo-codice che ne descrive il funzionamento: passo 0: si generano causalmente K vettori di domanda dk =(d₁k,d₂k,...,d_nk)

foreach k=1, …, K e j=1, …, n-1

calcolo delle somme parziali

S

k_j

=

d

₁k

+

d

₂k

+

...

+

d

_nk

si forma il vettore Sk =(S₁k,S₂k,...,S_nk)

si inizializza una lista K={1, …, K} e un contatore j=1

passo 1: si ordinano i vettori Sk a seconda del valore della j-esima componente Sj k passo 2: calcoliamo         = + j j p p

l* 1 come indice di posizione nella lista K

impostiamo ( ) 2 1 ₁ * * * + + = l j l j j S S y passo 3:

K

←

{

k

∈

K

:

S

k_j

>

y

_j

}

1 + ← j j IF j=n-1 STOP ELSE GOTO passo1

Pur non essendo particolarmente complessa l’implementazione, spesso si preferisce comunque utilizzare delle euristiche per il calcolo dei booking limits e dei protection level; due sono i fondamentali motivi che portano a questa scelta:

- le prime applicazioni delle tecniche di gestione dei ricavi risalgono agli anni ’70 nel campo delle prenotazioni aeree; in quegli anni la formulazione ottimale ancora non era stata formalizzata e l’unico modello a disposizione era quello a 2-classi di Littlewood. Ecco perché si modellarono e si cominciarono ad utilizzare euristiche.

- Inoltre, le euristiche vengono spesso preferite perché sono facili da codificare, veloci da eseguire e di norma producono risultati molto vicini a quelli ottimali.

Di seguito analizzeremo due euristiche molto note, entrambe attribuite a Belobaba, basate sul modello statico di allocazione di un’unica risorsa su n-classi; inoltre, in ambo i casi si assume che le funzioni che descrivono capacità e domanda siano continue.

Expected Marginal Seat Revenue Expected Marginal Seat Revenue Expected Marginal Seat Revenue

Expected Marginal Seat Revenue –––– version A (EMSRversion A (EMSRversion A (EMSRversion A (EMSR----a)a)a) a)

Consideriamo lo stato j+1 nel quale la domanda per la classe j+1 arriva con prezzo pj+1

Ciò che vogliamo calcolare è quanta capacità riservare per le rimanenti classi j, j-1, …, 1, ovvero il

protection level per le classi j e superiori;

consideriamo una classe k far le rimanenti e confrontiamo solo questa con la j+1, possiamo utilizzare la regola di Littlewood e riservare una capacità y_kj+1 in modo tale che

k j j k k p p y D P( > +1)= +1 ;

ripetendo il confronto per ogni altra classe rimanente possiamo calcolare quanta capacità riservare per ogni classe k considerata isolatamente.

L’idea di questa euristica è quindi, quella di sommare queste quantità per approssimare il protection level

totale ottenendo 1 1 + =

∑

=

j k j k j

y

y

.

EMSR-a è un procedimento molto semplice e intuitivo ma spesso genera risultati troppo spartani, conservativi, ovvero, spesso vengono determinati dei livelli eccessivi rispetto all’effettivo fabbisogno. Questo problema lo si incontra soprattutto quando si hanno più classi i cui ricavi sono uguali; per un corretto calcolo queste dovrebbero essere aggregate ed è, perciò, sbagliato considerare un singolo addendo per ognuna di esse.

Expected Marginal Seat Revenue Expected Marginal Seat Revenue Expected Marginal Seat Revenue

Expected Marginal Seat Revenue –––– version version version version BBBB (EMSR(EMSR(EMSR(EMSR----bbbb))))

A differenza della versione A, questa euristica tiene conto delle domande aggregate, e non dei protection level aggregati.

Consideriamo lo stato j+1 per il quale vogliamo determinare il protection level yj Definiamo la domanda aggregata per le classi future j, j-1, …, 1 come

∑

=

=

j k k j

D

S

1

e aggiungiamo il concetto di ricavo medio pesato calcolandolo come

∑

∑

= =

=

_j k k j k k k j

D

E

D

E

p

p

1 1

]

[

]

[

A questo punto il protection level per la classe j e superiori è individuato utilizzando la regola di Littlewood ma con p_j come

j j j j p p y S P( > )= +1 .

Uno studio condotto dallo stesso Belobaba sullo stesso insieme di dati, volto a confrontare le due euristiche ha messo in luce come EMSR-b produca risultati più vicini a quelli ottimali rispetto a EMSR-a; uno studio più recente effettuato sui dati della compagnia aerea Lufthansa ha, invece, mostrato come un uso combinato delle due versioni sia ancora più efficiente.

Metodi adattivi Metodi adattivi Metodi adattivi Metodi adattivi

I metodi adattivi normalmente si configurano su tre passi:

1) si analizzano i dati storici della domanda per poterne individuare ed esaminare la distribuzione; 2) si applicano delle tecniche predittive per modellare i parametri della distribuzione;

3) i dati ricavati nelle due precedenti fasi vengono passati a un solutore che individua il vettore ottimale y*.

I risultati di questo processo vengono, quindi, utilizzati per decidere se accettare o rifiutare una richiesta. Facciamo riferimento a: 1 ,..., 1 } ... ,..., , { ) , ( 1 1 1 2 2 1 − = > + + > + > ≡ n j y D D y D D y D D y Bj j j

e alla condizione di ottimalità:

1 ,..., 1 )) , ( ( 1 1 * − = = + n j p p D y B P _j j

Per l’algoritmo ci è necessario definire anche:

1 ,..., 1 ) , ( 1 ) , ( 1 1 − = − = + n j D y B p p D y H j j j

dove 1(E) è una funzione che assume valore 1 se l’evento E occorre, 0, altrimenti.

La quantità così definita assume valore negativo se il j-esimo evento occore, positivo, altrimenti; questo perché, se con un evento si raggiunge il protection level, ciò suggerisce che questo debba essere modificato.

Perciò, −Hj(y,D) può essere interpretato come una direzione di aggiustamento per il protection level

il cui corrispondente vettore sarà H(y,D)=(H₁(y,D),...,H_n−1(y,D)).

Definendo anche h(y)=(h1(y),...,hn−1(y))con

1 ,..., 1 )] , ( [ )) , ( ( ) ( 1 1 − = = − = + n j D y H E D y B P p p y h j j j j

-h(y) può essere considerato come il vettore degli aggiustamenti atteso

Possiamo, quindi, concludere che il vettore ottimale y* è tale per cui per tutti i protection level

2.2.4 Arrivo di gruppi

Il concetto di gruppo è legato alla richiesta simultanea di più unità di capacità, richiesta che per essere soddisfatta deve esserlo in totale.

Una semplificazione si ha quando la richiesta di gruppo di m quantità può comunque essere soddisfatta parzialmente; in questo caso è possibile vendere una quantità u compresa fra 0 e m.

Il caso più drastico è, invece, quello in cui la richiesta di Dj quantità del gruppo deve essere soddisfatta in totale, quindi, è possibile vendere u tale che 0≤u≤min{Dj,x} dove x è la capacità

totale disponibile.

Questo aspetto complica parecchio il modello descritto fin’ora; occorre conoscere la distribuzione della domanda e la grandezza del gruppo, ma la vera differenza sta nel fatto che la funzione del valore per il gruppo non è concava, ovvero il valore marginale della capacità è crescente, perciò l’uso dei modelli fin’ora descritti che lavorano con protection level, booking limit e bid price non possono essere ottimali.

In generale la risoluzione di questo modello si avvale di calcoli combinatori; ma nella maggior parte dei casi si tratta di gruppi piccoli e la capacità è molto grande, perciò si riesce comunque ad utilizzare i modelli prima descritti ed a ottenere una buona approssimazione.

2.2.5 I modelli dinamici

I modelli dinamici presuppongono che l’arrivo delle domande non sia arbitrario ma che segua un “ordine gerarchico” dalla più bassa alla più alta, in particolare, si ipotizza che la domanda sia descritta da una distribuzione di Poisson; questo aspetto se da una parte semplifica la gestione della variabilità della domanda, dall’altro è uno dei principali limiti all’utilizzo dei modelli dinamici. Inoltre, questo tipo di modelli richiede una previsione delle sequenze di arrivo, cioè, una previsione dei tipi di domande in arrivo, e questo aspetto non sempre è reperibile facilmente.

Tutte le ipotesi fatte per i modelli statici continuano a valere anche per i modelli dinamici: - la domanda è indipendente tra le classi, dal tempo e dal controllo di capacità utilizzato - il modello è esente dai rischi.

Formalizziamo il modello.

Ci sono n classi con associato un prezzo p1 ≥ p2 ≥...≥ pn

Si hanno T periodi

A differenza del modello statico, si utilizzano due diversi indici: j per le classe e t per i periodi.

Per ogni periodo si suppone ci sia un solo arrivo, e la probabilità che ci sia un arrivo nella classe j nel periodo t è data da

λ

_j(t); proprio per il fatto che ci possa essere solo un arrivo si ha che

∑

=

≤

n j j

t

1

1

)

(

λ

.

I periodi dovrebbero avere la solita durata, perciò si procede anche con degli aggiustamenti: nel caso in cui la domanda sia scarsa, si stabiliscono dei periodi piuttosto lunghi, mentre, se al contrario la domanda ha un picco, si definiscono periodi brevi, anche di ore.

Programmazione dinamica Programmazione dinamica Programmazione dinamica Programmazione dinamica

Definiamo x la capacità residua e V_t(x)la funzione del valore in t

Sia R(t) una variabile casuale con R(t)=pj se una domanda per la classe j arriva nel periodo t e 0 altrimenti, quindi P(R(t)=pj) =

λ

_j(t).

Definiamo la variabile u con valore 1 se si accetta l’arrivo e 0 altrimenti, si vuole massimizzare la somma dei ricavi attuali e futuri R(t)u+V_t+1(x−u). L’equazione di Bellman è: }] )) ( ) ( {( [max ) ( )}] ( ) ( { [max ) (x E _{0,1} R t u V ₁ x u V ₁ x E _{0,1} R t V ₁ x u Vt = u∈ + t+ − = t+ + u∈ −∆ t+ dove ∆Vt+1(x)=Vt+1(x)−Vt+1(x−1)è il valore atteso marginale della capacità nel periodo t+1.

Le condizioni da rispettare sono:

0

)

(

1

=

+

x

V

_T con x=0, 1, … , C e Vt(0)=0con t=1, …, T Politica ottimale Politica ottimale Politica ottimale Politica ottimale

Se arriva una richiesta per la classe j, allora sappiamo che R(t)=pj perciò è ottimale accettare la richiesta se e solo se pj ≥∆Vt+₁(x).

Allora, il controllo ottimale può essere implementato impostando un bid price al valore marginale

) ( )

(x V_{t 1} x

t =∆ +

Π ; i ricavi che eccedono questa soglia vengono accettati, gli altri no.

L’incremento ∆Vt(x) della funzione del valore Vt(x) gode di due proprietà:

1) ∆Vt(x+1)≤∆Vt(x), il valore marginale di ogni unità di capacità aggiuntiva è decrescente

2) ∆Vt+1(x)≤∆Vt(x), il valore marginale decresce con l’avanzare del tempo perché diminuisce la

possibilità di vendita.

Così, possiamo definire un protection level ottimale in funzione del tempo:

)}

(

:

max{

)

(

1 1 *

x

V

p

x

t

y

_j

=

_j+

<

∆

_t+ con j=1, 2, …, n-1

ovvero la capacità da riservare per ogni classe j.

Perciò, y₁*(t)≤ y*₂(t)≤...y*n−₁(t) è rappresenta una scelta ottimale accettare la richiesta per la classe j se

e solo se la capacità residua eccede

y

*_j−1

(

t

)

.

Possiamo definire anche un booking limit ottimale dipendente dal tempo:

)

(

)

(

* ₁ *

t

y

C

t

b

_j

≡

−

_j− con j=1, 2, …, n

Il fatto che il protection level e il booking limit siano definiti in funzione del tempo è giustificato dal fatto che la domanda varia nel tempo; perciò, considerato che la funzione del valore non varia rapidamente nel breve periodo, fissare il protection level e il booking limit e aggiornandone il valore periodicamente, è una tecnica molto vicina all’ottimalità.

Quindi, riassumendo, in un modello dinamico, il controllo ottimale può essere implementato come

protection level in funzione del tempo, come booking limit in funzione del tempo o come soglia per un

bid price.

L’assunzione che la domanda per una classe sia totalmente indipendente da quali altre classi siano ancora disponibili è chiaramente irrealistica; si pensi alla richiesta di prodotti a prezzo pieno se e quando ancora sono disponibili quelli a prezzo scontato.

Andiamo ad analizzare una serie di modelli in cui si tiene conto anche di questa dipendenza.

Il fattore buy Il fattore buy Il fattore buy Il fattore buy----upupup up

Questo modello si basa su quello statico a 2 classi e utilizza la regola di Littlewood in modo che una domanda per la classe 2 sarà accettata se e solo se

p

2

≥

p

1

P

(

D

1

>

x

)

dove x è la capacità residua, ovvero se e solo se il ricavo derivante sarà maggiore del valore marginale derivante dall’unità aggiuntiva.

Supponiamo poi che ci sia una probabilità q che un cliente della classe 2 acquisti un’unità della classe 1 nel momento in cui la 2 sia chiusa; perciò il profitto netto è dato da

p

1

−

p

1

P

(

D

1

>

x

)

,

ovvero il ricavo derivante dalla classe 1 decurtato dai costi marginali.

In base a questa definizione, accettare una richiesta per la classe 2 è ottimale se:

1 1 1 2 1 1 1 1 1 2

)

(

)

1

(

))

(

1

(

)

(

qp

x

D

P

p

q

p

x

D

P

qp

x

D

P

p

p

p

+

>

−

≥

≡

>

−

≥

>

−

−

Lo svantaggio di questo modello è che non può essere utilizzato con più di 2 classi; una soluzione spesso attuata è l’integrazione di questo fattore all’interno dei vari modelli visti precedentemente, ad esempio nelle euristiche EMSR trattate nella sezione 2.2.3 nel calcolo dei protection level.

Modello discreto Modello discreto Modello discreto Modello discreto

Un altro modo per evitare i problemi del buy-up sono i modelli discreti; vediamone una possibile formulazione.

Il tempo è discreto scandito da t in ogni periodo può arrivare al più una richiesta con probabilità

λ

Si hanno n classi:

ℵ

=

{

1

,...,

n

}

e per ognuna di esse è definito un prezzo pj

In ogni periodo il venditore sceglie un sottoinsieme S di classi da offrire St ⊆ℵ _{la cui probabilità di}

essere scelto da un cliente è

P

j

(

S

t

)

La probabilità che nel periodo t sia effettuato un acquisto è

λ

P

j

(

S

t

)

Sia C la capacità totale e T la durata del periodo e x la capacità residua

T

t

V

C

x

x

V

S

P

S

P

x

V

x

V

x

V

x

V

x

V

p

S

P

x

V

S

P

x

V

p

S

P

x

V

t T S j j t t t t S j t j j S t S j t j j S t

,...,

1

0

)

0

(

,...,

1

,

0

0

)

(

1

)

(

)

(

)

1

(

)

(

)

(

)

(

)

(

)(

(

max

)

(

)

1

)

(

(

))

1

(

)(

(

max

)

(

1 0 1 1 1 1 1 1 0 1

=

=

=

=

=

+

−

−

=

∆

+













∆

−

=













−

+

+

−

+

=

+ ∈ + + + + ∈ + ℵ ⊆ + ∈ + ℵ ⊆

∑

∑

∑

M

λ

λ

λ

λ

2.3 Allocazione ottimale di più risorse – network capacity control

Il nostro problema è riuscire ad allocare un insieme di risorse connesse fra loro, tenendo conto che una richiesta può essere soddisfatta se e solo se queste sono tutte disponibili, cioè, l’assenza di disponibilità di una delle risorse all’interno del pacchetto (mix) limita la vendita di tutto il pacchetto; i settori interessati a questo tipo di argomento sono il settore aereo, ferroviario, i sistemi di noleggio, gli hotel e in generale tutti i settori in cui i consumatori comprano pacchetti di prodotti sotto diversi termini e condizioni.

In particolare, nel settore aereo il problema chiamato passenger-mix problem o controllo O&D (origineorigineorigine----destinazioneorigine destinazionedestinazionedestinazione), è la gestione della capacità di un insieme di voli, dove i voli sono un mix tra connessioni e traffico locale; in questo caso un prodotto è la combinazione di diversi percorsi origine-destinazione noti nel linguaggio di settore come origin-destination itinerary fare class combination - ODIF.

Mentre, nel caso degli hotel il problema chiamato controllo della controllo della controllo della controllo della durata del soggiornodurata del soggiornodurata del soggiornodurata del soggiorno ( length-of-stay control), è quello di gestire la capacità delle camere, quando i clienti restano per giorni consecutivi in hotel, quando i clienti stanno per periodi di diversa durata e condividono la capacità durante questi giorni.

L’applicazione di modelli di gestione dei ricavi per questo tipo di problemi, apporta reali benefici dal punto di vista economico, ma allo stesso tempo impone alcuni cambiamenti metodologici e proprio per questo occorre seguire delle buone tecniche.

Dal punto di vista implementativo, aumentano la complessità e il volume dei dati che devono essere raccolti e gestiti rendendo più difficili e dispendiose le transazioni di ogni singola risorsa.

E’ importante tenere a mente che ogni singola risorsa all’interno del mix è importante, la perdita di ricavi in un solo punto potrebbe essere dovuto a qualsiasi altro punto di esso.

Per quanto riguarda le previsioni, anche queste si fanno più complesse, si deve prevedere la domanda per ogni singolo prodotto del mix in ogni punto nel processo di prenotazione e ciò non è facilitato dalla radezza dei dati. Inoltre, considerato che il processo di ottimizzazione è molto complesso, per questioni pratiche è impossibile ottenere delle stime corrette e pertanto i metodi di ottimizzazione usano approssimazioni di diversi tipi.

Uno degli obiettivi è, quindi, riuscire a trovare il giusto compromesso tra la buona qualità dell’approssimazione e l’efficienza dei risultati degli algoritmi.

Booking Limit P Booking Limit P Booking Limit P

Booking Limit Partitionedartitionedartitionedartitioned

E’ un’estensione di quello definito per una singola risorsa.

Nel caso multi-risorsa, si alloca un ammontare fisso di capacità di ogni risorsa per ogni prodotto offerto e la domanda di un prodotto ha accesso esclusivo alla sua capacità che gli altri prodotti non possono usare.

Tuttavia anche in questo caso questo tipo di controllo risente di alcuni difetti: l’allocazione di un ammontare fisso di capacità implica dividere la capacità di ogni risorsa in un tante piccole parti e questa frammentazione può risultare molto inefficiente quando la domanda è stocastica.

Proprio per questo motivo i booking limit partitioned vengono usati raramente in pratica anche se giocano un’importante ruolo dal punto di vista teorico e computazionale.

Virtual Nesting Control Virtual Nesting Control Virtual Nesting Control Virtual Nesting Control

I booking limit nested visti per il problema a risorsa singola sono difficilmente applicabili a quello multi-risorsa per due diversi motivi: l’ordinamento delle classi può essere differente da risorsa a risorsa e la diversa capacità delle risorse coinvolte rende difficile specificare dei protection level coerenti con il mix.

Si introduce, allora, il Virtual Nesting Control che utilizza al suo interno una serie di controlli singoli per ogni risorsa del mix:

le classi fra cui si allocano le risorse sono virtuali,

i prodotti sono assegnati a classi virtuali attraverso un processo conosciuto come indicizzazione, che essenzialmente fornisce una tabella che mappa ogni prodotto in una classe virtuale su ogni risorsa. Questa indicizzazione viene modificata periodicamente in base ai cambiamenti nella domanda.

Per decidere se accettare una richiesta per un prodotto, il sistema controlla la disponibilità della classe virtuale di appartenenza di ogni risorsa; se tutte le classi sono disponibili, la richiesta viene accettata, se anche una sola di esse non la è, la richiesta viene rifiutata.

L’utilizzo di questo controllo apporta vantaggi e svantaggi.

Da una parte, l’indicizzazione richiede maggiore complessità computazionale e può creare potenziali difficoltà nell’organizzazione dei dati e nelle previsioni introducendo rumore e confusione, causando delle variazioni scorrette nelle statistiche di domanda sulle classi virtuali in corrispondenza di variazioni della domanda.

Dall’altra, Virtual Nesting Control non richiedono molti cambiamenti infrastrutturali, permettono ad un sistema di gestione dei ricavi di incorporare le informazioni del mix fornendo un compromesso accettabile tra singole risorse e pieno controllo e sono molto efficaci e ben accettati dal punto di vista pratico, specialmente nel settore aereo.

Bid Bid Bid Bid----PricePricePricePrice

Anche questo tipo di controllo è una semplice estensione di quello visto per il modello a risorsa singola.

In questo caso si imposta una soglia di prezzo detta bid-price per ogni risorsa del mix; generalmente si usa come stima il costo marginale del consumo di un’unità incrementale della capacità di risorse.

Quando arriva la richiesta per un prodotto, il ricavo viene confrontato con la somma dei bid-price delle risorse necessarie; se il ricavo eccede questa somma la richiesta viene accettata, altrimenti viene rifiutata.

Molti sono i vantaggi legati all’uso di questo controllo:

- la struttura è semplice, occorre specificare solo un singolo valore per ogni risorsa, quindi il numero di parametri coinvolti è minimo;

- la valutazione di una richiesta per un prodotto richiede solo un semplice confronto, quindi l’esecuzione risulta veloce;

- le soglie dei bid price hanno un’interpretazione economica naturale;

- se implementato correttamente, questo tipo di controllo fornisce buone performance di ricavi e dal punto di vista teorico, si avvicina all’ottimo.

I sistemi di prenotazione alberghieri che non devono sottostare a più complesse regole di carico come quelle del settore aereo, sono nella migliore posizione per adottare questo tipo di controllo.

Modelli di base del problema Modelli di base del problema Modelli di base del problema Modelli di base del problema

Il mix si compone di m risorse e le aziende vendono n prodotti. Definiamo    = altrimenti j prodotto un da usata è i risorsa la se a_{i j} 0 1 ,

Definiamo la matrice di incidenza A=[aij] in cui:

la j-esima colonna Aj è il vettore di incidenza per il prodotto j

la i-esima riga, detta Ai, ha valore 1 in corrispondenza della colonna j , ovvero del prodotto j che usa la risorsa i.

Aj denota l’insieme di risorse usate dal prodotto j e Ai l’insieme di prodotti che usano la risorsa i perciò: i∈A_j indica che la risorsa i è usata dal prodotto j

e j∈Ai indica che il prodotto j usa la risorsa i. Lo stato del sistema:

E’ descritto da un vettore X = (x1, …. , xm) delle capacità delle risorse. Se il prodotto j viene venduto, lo stato del network cambia in X – Aj.

Per semplificare la nostra analisi ignoreremo le cancellazioni e la possibilità di richieste di prenotazione multiple.

Il tempo:

E’ discreto, ci sono T periodi, e l’indice t rappresenta il tempo corrente.

All’interno di ogni periodo t assumiamo che ci sia al massimo una richiesta per un prodotto; per tale motivo è necessaria una discretizzazione del tempo in modo che la probabilità di avere più di una richiesta risulti insignificante.

La domanda al tempo t:

E’ modellata attraverso un vettore riempito casualmente P(t) = (P1(t), …, Pn(t)) in cui:

Pj(t) = pj > 0 indica che c’è un richiesta per il prodotto j e che a questa è associato il prezzo pj

Pj(t) = 0 indica che non ci sono richieste per il prodotto j

P(t) = 0 indica che non ci sono richieste per nessun prodotto al tempo t.

Ad esempio se si hanno 3 prodotti P(t)=(0,0,0) indica che non ci sono richieste, P(t)=(120,0,0) indica una richiesta per il prodotto 1 al prezzo di 120€, mentre un P(t)=(0,70,0) indica che c’è una richiesta per il prodotto 2 di 70€.

La domanda è indipendente dal tempo. I prezzi:

P = (p1,…,pn).

Ciò che vogliamo decidere è data la capacità rimanente X al tempo t accettiamo o rifiutiamo le richieste correnti P(t)?

Consideriamo il vettore n-dimensionale u(t) delle decisioni, dove:

uj(t) = 1 se accettiamo la richiesta per il prodotto j al periodo t

uj(t) = 0 altrimenti.

La decisione di accettare, quindi, il valore di uj(t), è in funzione del vettore delle capacità rimanenti X e del prezzo pj del prodotto j : uj(t) = uj(t,X,pj) da cui deriviamo la regola generale per cui u(t) = u(T,X,P). Inoltre, poiché secondo le nostre ipotesi viene accettata al più una richiesta in un periodo e non possono essere vendute risorse in più, se l’inventario corrente è X, allora u(t) corrisponde a

{ }

{

u Au x

}

X

U( )= ∈ 0,1n : ≤ .

Passiamo al calcolo della politica ottimale Passiamo al calcolo della politica ottimale Passiamo al calcolo della politica ottimale

Passiamo al calcolo della politica ottimale

u

*

(

t

,

x

,

p

)

Definiamo il ricavo atteso massimo V_t(x), dato dalla capacità X rimanente nel periodo t; dovrà soddisfare l’equazione di Bellman:

{

}

x

x

V

x

U

u

Au

x

V

p

x

t

u

t

P

x

Vt

T t T

∀

=













∈

−

+

Ε

=

+ +

,

0

)

(

)

(

)

(

)

,

,

(

)

(

max

)

(

1 1

Un controllo ottimale u*(.)soddisfa la seguente proprietà:







≥

−

−

≤

=

+ +

altrimenti

x

A

e

A

x

V

x

V

p

se

p

x

t

u

_{j j} j t t j j

0

)

(

)

(

1

)

,

,

(

*

1 1

ovvero, si accetta una richiesta per il prodotto j se e solo se esiste sufficiente capacità e il suo prezzo pj eccede il costo-opportunità dato dalla riduzione della capacità di risorse utilizzate per soddisfare la richiesta.

In altre parole un bid price control specifica un insieme di prezzi di offerta per ogni risorsa, in ogni istante di tempo, e per ogni livello di capacità, in modo che una richiesta per un particolare prodotto

possa essere accettata se e solo se c’è capacità disponibile e se il prezzo eccede la somma dei bid price per tutte le risorse usate dal prodotto.

Ma non sempre utilizzare i bid price control è una forma ottimale di controllo. Vediamo un esempio in cui ne mostriamo la non-ottimalità.

Si considera un mix composto da 2 risorse e 2 periodi di tempo. In tabella riportiamo i dati dei prodotti:

periodo ( periodo ( periodo (

periodo (tttt)))) ProdottoProdottoProdottoProdotto AAAAjjjj PrezzoPrezzoPrezzoPrezzo ProbabilitàProbabilitàProbabilitàProbabilità 1 11 1 1 2 3 (1 0) (0 1) (1 1) 250,00€ 250,00€ 500,00€ 0,3 0,3 0,4 2 22 2 3 Nessuna richiesta (1 1) 500,00€ 0,8 0,2

Nel primo periodo possono arrivare domande per tutti e tre i prodotti, per il prodotto 1 e 2 con probabilità 0,3 e prezzo 250,00€ e per il prodotto 3 con probabilità 0,4 e prezzo 500,00€.

Nel secondo periodo c’è una domanda solo per il prodotto 3 sempre del prezzo di 500,00€ ma con una probabilità di 0,8.

Le probabilità sono esclusive, cioè in ogni periodo può essere domandato un solo prodotto.

Una politica ottimale sarebbe quella di non accettare le domande per il prodotto 1 e 2 nel primo periodo ma di accettare la domanda del prodotto 3 in entrambi i periodi; questo è vero perché accettando la richiesta 1 o 2 nel periodo 1 si guadagnano 250,00€ ma perdiamo l’opportunità di accettare il prodotto 3 nel periodo 2 che risulta avere un costo opportunità di 400$(0,8*500$), quindi sarebbe opportuno non accettare le richieste di prodotto 1 e 2 del primo periodo. Chiaramente vogliamo accettare il prodotto 3 del primo periodo perché comunque non possiamo guadagnare più di 500$ nel periodo 2.

Questo implica che i prezzi di offerta,

π

1 e

π

2 nel primo periodo devono soddisfare

π

1>250, 2

π

>250 e

π

1+

π

2<=500, che ovviamente è impossibile. Perciò nessuna politica di prezzo di offerta produce una decisione ottimale nel periodo 1.

Infatti non è difficile dimostrare che in questo esempio la politica ottimale sarebbe quella di rigettare tutte le richieste del periodo 1 e accettare solo quella del periodo 3 (se arriva) nel periodo 2 guadagno 400$ (500$*0,8)di ricavo atteso. La politica ottimale al contrario genera un ricavo di 440$ più del 10% del ricavo atteso.

Due sono i fondamentali motivi per cui la politica dei bid price control può fallire:

1) grandi cambiamenti simultanei sulle capacità di risorse diverse non possono produrre lo stesso ricavo derivato della somma dei cambiamenti individuali;

2) i ricavi futuri possono dipendere in modo non lineare dallo spostamento di capacità, ovvero il opportunità legato all’uso di una singola risorsa può eguagliare esattamente il costo-opportunità di usare entrambe le risorse simultaneamente.

Per ogni mix realistico è molto difficile calcolare esattamente il valore della funzione Vt(x) in quanto spesso le grandi dimensioni dello spazio rendono questo calcolo difficile; basti pensare ad un ambiente in cui ci siano 20 risorse e 100 capacità per ogni risorsa, in esso esistono 100^20 stati.

Quello che realmente si può fare sono delle approssimazioni di vario tipo Quello che realmente si può fare sono delle approssimazioni di vario tipo Quello che realmente si può fare sono delle approssimazioni di vario tipo Quello che realmente si può fare sono delle approssimazioni di vario tipo:

1. il primo metodo a cui faremo riferimento è quello che utilizza un semplice mix;

2. la seconda strategia riguarda la decomposizione del problema in un insieme di sotto-problemi a risorsa singola.

I criteri importanti per giudicare un metodo di approssimazione sono l’accuratezza e la velocità. Dato un metodo di approssimazione M che ricava una stima della funzione

V

(x

)

M

t _{, possiamo}

approssimare il costo riferito al fatto di accettare la richiesta del prodotto j utilizzando:

j T M t j M t M t x V x A V x A V ( )− ( − )≈(∇ ( )) dove

V

(x

)

M t

∇

è il gradiente della funzione

V

(x

)

M

t _{, assumendo che il gradiente esista.}

I bid price sono definiti secondo la seguente formula: ( , ) V (x)

x x t tM i M i ∂ ∂ =

π

Se il gradiente non esiste, allora

V

(x

)

M t

∇

tipicamente viene sostituito da un subgradiente.

L’obiettivo di un metodo di approssimazione è quello di produrre una buona stima della funzione di valore e, ancora più importante, quello di produrre una buona stima del costo e dei prezzi di offerta.

2.3.1 Metodi di approssimazione – utilizzo di mix semplici Il

Il Il

Il modello di programmazione lineare deterministico (DLP)modello di programmazione lineare deterministico (DLP)modello di programmazione lineare deterministico (DLP)modello di programmazione lineare deterministico (DLP)

Posta Dj la domanda aggregata per il prodotto j, nei periodi t, t+1, … T con media

µ

j.

D = (D1, …. Dn) e

µ

=E[D] sono i vettori delle domande e delle medie delle domande, rispettivamente. Il metodo di programmazione lineare deterministico usa la seguente approssimazione:

µ

≤ ≤ ≤ = y e x Ay con y p x V_tDLP T 0 max ) (

Le variabili di decisione y=

(

y1,...,yn

)

rappresentano l’allocazione di capacità divisa fra gli n prodotti.

In pratica l’approssimazione tratta la domanda come se fosse deterministica e uguale alla sua media

µ

e di conseguenza crea un’allocazione partizionata ottimale. Spesso le allocazioni generate dalla risoluzione primale vengono tralasciate e si utilizzano quelle duali

π

DLP; se la soluzione ottimale non è degenere e i vincoli in corrispondenza di essa sono linearmente indipendenti, allora il gradiente

)

(x

V

_tDLP

∇

esiste e corrisponde al vettore

π

DLP; al contrario, se la soluzione è degenere, si avranno più vettori duali, ognuno dei quali è solo un sub-gradiente della funzione.

Il vantaggio principale del modello DLP, è che esso risulta computazionalmente efficiente, semplice e veloce e pertanto molto popolare. L’unica debolezza che presenta è che considera solo la domanda media ignorando qualsiasi incertezza di previsione; alcuni ricercatori hanno comunque

mostrato che con frequenti ri-ottimizzazioni, i risultati del DLP possono migliorare e si ottengono ricavi più alti di quelli ottenuti con modelli di programmazione non lineare probabilistici.

Generalmente la performance del modello DLP dipende dal tipo di mix, dalla varianza nelle previsioni di domanda, dall’ordine con cui le richieste di prodotto arrivano e dalla frequenza della ri-ottimizzazione.

Il modello di programmazione non lineare probabilistico (PNLP) Il modello di programmazione non lineare probabilistico (PNLP) Il modello di programmazione non lineare probabilistico (PNLP) Il modello di programmazione non lineare probabilistico (PNLP) Questo modello usa la seguente approssimazione:

0 }] , [min{ max ) ( 1 ≥ ≤ =

∑

= y e x Ay con y D E p x V j j n j j PNLP t

dove Dj e pj sono definiti analogamente a prima.

Come nel DLP la variabile di decisione yj rappresenta un’allocazione di capacità partizionata del prodotto j, mentre il termine E[min{D_j,y_j}] sono le vendite attese del prodotto j.

Se la domanda è discreta, il modello si può convertire in modello di programmazione lineare, anche se con più variabili; questo si può ottenere assegnando una variabile e un’unità di capacità per ogni prodotto.

Definiamo la variabile z_jdcome la d-esima unità di capacità allocata al prodotto j. Il modello PNLP può essere scritto nel seguente modo:

j jd M d jd j n j M d j jd j PNLP t

M

d

n

j

z

e

x

y

A

e

z

y

con

d

D

P

z

p

x

V

j j

,...,

1

,...,

2

,

1

1

0

)

(

max

)

(

1 1 1

=

=

≤

≤

≤

=

≥

=

∑

∑ ∑

= = =

dove M_j rappresenta il limite superiore alla capacità allocata del prodotto j, ovvero la capacità minima rimanente tra le risorse usate dal prodotto j.

Se i vincoli sono linearmente indipendenti in corrispondenza della soluzione ottimale, allora

)

(x

V

_tPNLP

∇

esiste ed è dato dall’unico vettore dei prezzi duali; al contrario, se c’è dipendenza fra i vincoli, esisteranno più vettori, ognuno dei quali è un sub-gradiente della funzione.

L’approssimazione PNLP appare migliore dell’approssimazione DLP, in quanto il termine

}] , [min{D_j y_j

E nella funzione obiettivo cattura la casualità nella domanda, mentre il DLP presuppone che la domanda sia deterministica; il prezzo della risorsa può essere positivo persino quando la domanda media per la risorsa è strettamente inferiore alla capacità.

Gli studi hanno comunque confermato che dal modello PNLP risultano ricavi inferiori rispetto a quelli del DLP.

Il modello di programmazi Il modello di programmazi Il modello di programmazi

Il modello di programmazione lineare randomizzato (RLP)one lineare randomizzato (RLP)one lineare randomizzato (RLP)one lineare randomizzato (RLP)

Si tratta di un ulteriore approccio per incorporare l’informazione stocastica nel modello DLP; si fa riferimento alla formulazione vista per il DLP e si rimpiazza il vettore D randomizzato nel vincolo:

D y e x Ay con y p D x H_t T ≤ ≤ ≤ = 0 max ) , (

Il valore ottimale H_t(x,D) è una variabile casuale.

L’approssimazione RLP richiede un metodo per computare efficientemente

∇

V

_x

E

[

H

_t

(

x

,

D

)]

. Si simulano k campioni indipendenti di vettori di domanda D(1),....,D(k)e risolviamo il modello di cui sopra ognuno di essi.

Quindi, stimiamo il gradiente usando:

∑

= = k i i RLP D x k 1 ) ( ) , ( 1

π

π

che rappresenta la semplice media dei prezzi duali di k soluzioni di allocazione ad informazione perfetta su domande generate casualmente.

Il metodo RLP:

- è una semplice modifica del metodo DLP, quindi esso può essere incorporato facilmente nei sistemi di gestione dei ricavibasati su quello;

- modella con flessibilità anche distribuzioni di domanda generale;

- la qualità e la complessità del modello possono essere controllati semplicemente variando il numero di campioni k;

- diversamente dal DLP, incorpora informazioni di distribuzione della domanda.

2.3.2 Metodi di approssimazione – decomposizione del problema

Un’altra strategia per generare i controlli del mix è quella di decomporre il problema in m sotto-problemi a risorsa singola, ognuno dei quali incorpora informazioni generali ma viene risolto in modo indipendente.

Un metodo di approssimazione decompone il problema in m sotto-problemi a risorsa singola e applica un metodo a risorsa singola Mi su ogni risorsa i,

con funzioni

V

_tMi

(

x

_i

)

che dipendono dal tempo t e dalla capacità rimanente x_i della risorsa i.

La funzione totale viene approssimata utilizzando:

∑

= = m i i M t t x V x V i 1 ) ( ) (

da cui possiamo ricavare bid price nella forma:

) 1 ( ) ( ) ( ,..., 1 ) ( ) , ( − − = ∆ = ∆ = i M t i M t i M t i M t i x V x V x V con m i x V x t i i i i

π

dove

_∆

V

_tMi

(

x

_i

)

è il valore marginale atteso prodotto dall’applicazione del metodo a singola risorsa alla risorsa i.

Diversi sono i vantaggi che derivano dall’utilizzo dei modelli con decomposizione:

- si basano su modelli a singola risorsa, il trasferimento dei costo e i prezzi di offerta sono tipicamente dinamici, variano in funzione della capacità del tempo e possono essere rappresentati con una tabella (nel caso dei modelli di programmazione dinamica) o con semplici formule (nel caso delle approssimazioni EMSR); perciò è semplice determinare l’effetto dei cambiamenti sia nel tempo rimanente che nella capacità rimanente sui prezzi di

- I modelli a risorsa singola utilizzati permettono di prendere decisioni sequenziali lungo il tempo.

Di contro, lo svantaggio principale riguarda il processo di separazione dei problemi che può generare la perdita di informazioni circa il mix; tuttavia, si tende ad utilizzare versioni ibride dei due approcci per provare ad ottenere maggiori benefici rispetto all’applicazione singola dell’uno o dell’altro.

Modello Origin Modello Origin Modello Origin

Modello Origin----Destination Factors (ODF)Destination Factors (ODF)Destination Factors (ODF) Destination Factors (ODF)

Si tratta di un semplice metodo di approssimazione con decomposizione; si risolvono problemi a risorsa singola per ogni risorsa i senza operare aggiustamenti a priori dei dati in ingresso.

Indichiamo le funzioni valore con il problema sulla risorsa i come

V

_tODF

(

x

_i

)

.

Quando valutiamo una richiesta per un prodotto j su una risorsa i, il prezzo pj viene confrontato con il

bid price calcolato come:

∑

≠ ∈ ∆ + ∆ i l A i l ODF t i ODF t j l i x V x V , ) ( ) (

γ

dove

_∆

V

_tODFi

(

x

_i

)

_{è il valore marginale derivante dal metodo i}

e

γ

è il “fattore OD” globale, tipicamente avente valore <1, calcolato con una simulazione.

L’utilizzo del fattore OD (

γ

) è motivato dal fatto che i problemi a risorsa-singola tendono a sovra-stimare i costi.

Se pj eccede il fattore OD, allora il prodotto j è accettato sulla risorsa i.

Un calcolo simile viene fatto su tutte le risorse usate dal prodotto j, perciò il prodotto j viene accettato se è accettato su tutte le risorse; in altre parole pj, dovrebbe essere maggiore o uguale al massimo dei bid price sulle risorse che consuma.

Da notare che se il prodotto j utilizza soltanto la risorsa i, allora il risultato corrisponde a quello che otterremmo con un modello a risorsa singola, ma se viceversa, il prodotto utilizza più risorse, allora il

bid price sarà più alto perché si deve tener conto dell’utilizzo delle altre l risorse.

Supponendo di avere a disposizione i risultati derivanti dai modelli a risorsa-singola, ODF fornisce un buon metodo per convertirli in stime dei costi dell’intero mix con il vantaggio di non dover richiedere nuove modellazioni o stime.

EMSR Distribuito (Prorated EMSR EMSR Distribuito (Prorated EMSR EMSR Distribuito (Prorated EMSR

EMSR Distribuito (Prorated EMSR ---- PEMSR)PEMSR)PEMSR) PEMSR)

Si tratta di un metodo più sofisticato di decomposizione; la prima formulazione fu ad opera di Williamson, che integrò l’euristica EMSR nel modello multi-risorsa.

Lo schema PEMSR alloca una porzione di ricavi di ogni prodotto alle risorse usate dal prodotto. Si risolvono m problemi a risorsa singola usando l’euristica EMSR e i valori marginali risultanti da ogni risorsa sono usati come bid price.

In particolare, siano

α

=(

α

₁,...,

α

_m) vettori reali non negativi.

Per ogni prodotto j si definiscono i nuovi ricavi, uno per ogni risorsa i usata dal prodotto, usando:

j j A l l i ij p i A p = ∈

∑

∈

α

α