Esercitazione n
o5 per il corso di Ricerca Operativa
Il modello di PL `e estratto dall’articolo
A. Ciancimino, L.Palagi, G. Inzerillo, S. Lucidi. ”A mathematical programming approach for the solution of the railway yield management problem”, Transportation Science, 33, pp. 168-181, 1998.
Un problems di Yield management ferroviario.
Una compagnia ferroviaria vende i biglietti per il treno che effettua il percorso dalla citt`a A (Napoli) alla B (Milano) effettuando tre fermate intermedie (Roma, Firenze, Bologna).
Le tariffe di vendita dei biglietti per ciAscuna Origine-Destinazione sono fissate dalla compagnia e dipendono solo dalla distanza. In particolare i prezzi in Euro (2a classe) per ciascuna possibile Origine-Destinazione (Oi-Dj) coperta dal treno sono riportati nella Tabella .
Napoli Roma Firenze Bologna Milano
Napoli - 45 72 80 100
Roma - - 45 59 91
Firenze - - - 25 53
Bologna - - - - 42
Table 1: Tariffe per le possibili O-D coperte dal treno Il numero di posti disponibili sul treno `e pari a 700.
All’inizio del periodo di prenotazione la domanda effettiva per ciascuna origine-destinazione (Oi-Dj) `e incerta, ma `e nota una previsione sulla domanda il cui valor (medio) µij `e ri- portato in Tabella .
Si suppone che la domanda effettiva per ciascuna Oi-Dj sia almeno pari al valor medio della domanda µij.
Napoli Roma Firenze Bologna Milano
Napoli - 420 355 335 480
Roma - - 150 200 375
Firenze - - - 250 300
Bologna - - - - 160
Table 2: Tariffe per le possibili O-D coperte dal treno
Il problema consiste nel determinare quanti posti vendere su ciascuna Oi-Dj coperta dal treno in modo da massimizzare il profitto derivante dalla vendita dei biglietti.
1
Analisi sintetica del problema.
Nel seguito chiameremo tratta il percorso tra due stazioni consecutive. Dunque nel nostro esempio ci sono quattro tratte che compongono il percorso dalla stazione A alla stazione B.
1 2 3 4 5
Napoli Roma Firenze Bologna Milano
Figure 1: Un treno con percorso composto da quattro tratte
- la richiesta di posti per ciascuna origine-destinazione `e incerta, ma non inferiore al valor medio
- i posti assegnati a ciascuna origine-destinazione sono venduti con certezza.
Formulazione.
– Variabili. `E naturale associare la variabili di decisione alle quantit`a di posti prenotabili su ciascuna Origine-Destinazione possibile. In questo caso, si tratta di dieci variabili che rappresentano i posti prenotabili (booking limit)sulle Oi-Dj per i = 1, . . . , 4 e j = i+ 1, . . . , 5.
– Funzione obiettivo. `E rappresentata dal profitto relativo alla vendita che deve essere massimizzata. Quindi, nell’ipotesi che tutti i posti assegnati siano venduti, `e data da
max 45x12+ 72x13+ 80x14+ 100x15+ 45x23+ 25x24+ 53x25+ 59x34+ 91x35+ 42x45
– Vincoli.
2
Napoli Roma Firenze Bologna Milano
1 2 3 4 5
Napoli 1 - x12 x13 x14 x15
Roma 2 - - x23 x24 x25
Firenze 3 - - - 2 x34 x35
Bologna 4 - - - - x45
Table 3: Variabili di decisione Vincoli di capacit`a
Devono essere imposti i vincoli legato alla capacit`a di posti del treno. In particolare, nel primo tratto da A ad F1 sono presenti sia i viaggiatori che si recano da A ad ogni posisbile destinazione. Avremo quindi quattro vincoli
X5
j=2
x1j ≤700
X5
j=3
(x1j + x2j) ≤ 700
X5
j=4
(x1j + x2j + x3j) ≤ 700
X4
i=1
xi5≤700
Vincoli di domanda.
Poich´e per ipotesi si avranno almeno µ domande per ciascuna Origine-Destinazione, `e necessario imporre i vincoli che impongono di non allocare su ciascuna origine-destinazione un numero di posti superiore alla domanda effettiva, cio`e xij ≤µij:
x12 ≤420 x13 ≤355 x14 ≤335 x15 ≤480 x23 ≤150 x24 ≤200 x25 ≤375 x34 ≤250 x35 ≤300 x45 ≤160
Infine si deve esplicitare il vincolo di non negativit`a sulle variabili cio`e xij ≥0.
3
In principio le variabili rappresentano dei posti, e quindi si dovrebbero esplicitare anche i vincoli di interezza. Questi vincoli possono essere omessi come sar`a chiarito in un prossimo capitolo.
Quindi la formulazione finale `e
max 45x12+ 72x13+ 80x14+ 100x15+ 45x23+ 25x24+ 53x25+ 59x34+ 91x35+ 42x45
X5
j=2
x1j ≤700
X5
j=3
(x1j+ x2j) ≤ 700
X5
j=4
(x1j+ x2j + x3j) ≤ 700
X4
i=1
xi5≤700 0 ≤ x12≤420 0 ≤ x13≤355 0 ≤ x14≤335 0 ≤ x15≤480 0 ≤ x23≤150 0 ≤ x24≤200 0 ≤ x25≤375 0 ≤ x34≤250 0 ≤ x35≤300 0 ≤ x45≤160 (xij intere)
Il modello generale per un treno che procede dalla citt`a 1 alla citt`a n si scrive:
max
n−1X
i=1
Xn
j=i+1
cijxij
Xk
i=1
X5
j=k+1
xij ≤ck per ogni k = 1, n − 1 0 ≤ xij ≤uij
(xij intere)
4
