Torna alla pagina di Ricerca Operativa
:: Ricerca Operativa - PLI - Equipaggi - 15.02.00 ::
Testo del problema
Una linea aerea deve decidere quali voli assegnare a quali equipaggi (pilota, stewards e hostesses). Ogni equipaggio deve volare in modo da tornare a casa dopo un certo numero di voli: perciò la compagnia aerea ha già identificato tutte le possibili sequenze cicliche di voli che possono essere attribuiti ad uno stesso equipaggio.
Ciascuna di tali sequenze ha dei costi, che corrispondono ai tempi morti al di fuori del normale orario di riposo, durante i quali l'equipaggio potrebbe essere impiegato ma resta in attesa.
Il problema che la compagnia aerea deve risolvere è quindi quello di attribuire un equipaggio a tutti i voli, scegliendo l'insieme di sequenze cicliche di costo minimo.
E' possibile che ad uno stesso volo siano assegnati anche due o più equipaggi, alcuni dei quali (tutti tranne uno) viaggiano da semplici passeggeri (volo di trasferimento).
Formulare il problema, classificarlo e risolverlo con i dati del file EQUIPAGGI.TXT.
Dati
Ogni volo è contraddistinto da un numero tra 1 e 30.
Ogni sequenza di voli è contraddistinta da una lettera seguita da un numero
tra 01 e 50.
Di seguito è indicata la composizione di ogni sequenza ed il suo costo.
Sequenza Costo Voli
A01 1200 1 2 3 4 5
A02 1250 1 2 3 6 7
A03 2650 1 2 4 7 8
A04 1400 1 2 4 9 10
A05 1200 3 4 11 12 15
A06 1600 3 8 16 18 20
A07 2250 10 12 13 14 15
A08 1400 10 14 16 17 19
A09 1600 14 15 18 19 20
A10 2300 15 16 17 19 20
B11 2450 2 5 7 11 13 16
B12 2250 3 9 10 12 16 18
B13 1900 5 6 12 15 18 19
B14 1800 7 8 9 11 13 16
B15 1300 8 9 12 14 16 19
B16 1600 9 15 16 18 19 20
B17 1550 10 12 14 17 19 20
B18 1800 10 11 13 15 18 19
B19 2900 11 13 14 16 17 18
B20 1250 14 15 16 17 18 19
C21 1450 1 3 5 7 9 14 21
C22 2250 2 3 5 6 8 15 22
C23 2800 3 5 6 9 13 16 23
C24 1500 4 8 9 11 12 17 24
C25 1200 5 9 13 14 16 20 25
C26 1100 6 8 14 15 19 20 26
C27 1100 7 9 10 11 12 28 27
C28 2050 8 10 11 13 16 17 28
C29 2750 9 12 14 15 18 19 29
C30 1850 10 11 13 16 18 20 30
D31 1900 2 6 14 16 21 24 29 30
D32 1000 1 4 13 17 23 25 28 30
D33 1450 5 10 11 15 21 25 27 28
D34 2650 5 10 14 17 21 25 29 30
D35 2050 8 12 13 19 22 26 28 29
D36 2900 8 13 17 20 23 24 26 27
D37 1950 9 10 18 19 25 26 29 30
D38 1250 9 10 13 15 21 23 28 29
D39 1400 9 10 11 13 21 22 24 28
D40 1400 9 10 15 18 23 25 27 29
E41 1100 2 4 8 12 15 19 21 24 27
E42 1100 3 4 7 11 13 15 21 22 24
E43 2750 4 5 6 13 14 16 21 23 26
E44 2550 4 7 8 13 15 18 21 24 27
E45 2350 5 7 8 13 15 17 22 23 28
E46 2550 5 8 9 13 16 19 22 24 27
E47 2700 6 7 9 14 15 18 22 25 30
E48 1850 6 8 9 14 17 20 23 24 30
E49 1300 7 8 10 16 17 19 23 25 29
E50 1950 8 9 10 17 18 20 24 26 30
Formulazione del problema
Dati
- e = 7 (numero equipaggi)
- v = 30 (numero di voli)
- s = 50 (numero di sequenze individuate)
- costoi (costo della sequenza i=1..50) [€]
- voloij (associazione volo j=1..30 alla sequenza i=1..50) (binaria)
Variabili
- xi (indica se la sequenza i=1..50 è adottata o no) (binaria)
Funzione obiettivo
Dobbiamo minimizzare il costo delle sequenze adottate:
min (somma)i xi * costoi
Vincoli
- vincolo perché ad ogni volo sia associato almeno un equipaggio:
xi * voloij >= 1 (per ogni j)
- vincolo che limita a e = 7 il numero di equipaggi disponibili:
(somma)i xi = 7
Lindizzazione del problema
! esercizio - equipaggi
! variabili: x(i) = indica se la sequenza i è adottata o no (binaria)
! le variabili sono binarie
! funzione obiettivo
min + 1200 x1 + 1250 x2 + 2650 x3 + 1400 x4 + 1200 x5
+ 1600 x6 + 2250 x7 + 1400 x8 + 1600 x9 + 2300 x10
+ 2450 x11 + 2250 x12 + 1900 x13 + 1800 x14 + 1300 x15
+ 1600 x16 + 1550 x17 + 1800 x18 + 2900 x19 + 1250 x20
+ 1450 x21 + 2250 x22 + 2800 x23 + 1500 x24 + 1200 x25
+ 1100 x26 + 1100 x27 + 2050 x28 + 2750 x29 + 1850 x30
+ 1900 x31 + 1000 x32 + 1450 x33 + 2650 x34 + 2050 x35
+ 2900 x36 + 1950 x37 + 1250 x38 + 1400 x39 + 1400 x40
+ 1100 x41 + 1100 x42 + 2750 x43 + 2550 x44 + 2350 x45
+ 2550 x46 + 2700 x47 + 1850 x48 + 1300 x49 + 1950 x50
st
! vincoli perché a ogni volo sia associato un equipaggio
volo1) + x1 + x2 + x3 + x4 + x21 + x32 >= 1
volo2) + x1 + x2 + x3 + x4 + x11 + x22 + x31 + x41 >= 1
volo3) + x1 + x2 + x5 + x6 + x12 + x21 + x22 + x23 + x42 >= 1
volo4) + x1 + x3 + x4 + x5 + x24 + x32 + x41 + x42 + x43 + x44 >= 1
volo5) + x1 + x11 + x13 + x21 + x22 + x23 + x25 + x33 + x34 + x43 + x45
+ x46 >= 1
volo6) + x2 + x13 + x22 + x23 + x26 + x31 + x43 + x47 + x48 >= 1
volo7) + x2 + x3 + x11 + x14 + x21 + x27 + x42 + x44 + x45 + x47 + x49 >= 1
volo8) + x3 + x6 + x14 + x15 + x22 + x24 + x26 + x28 + x35 + x36 + x41 + x44
+ x45 + x46 + x48 + x49 + x50 >= 1
volo9) + x4 + x12 + x14 + x15 + x16 + x21 + x23 + x24 + x25 + x27 + x29 + x37
+ x38 + x39 + x40 + x46 + x47 + x48 + x50 >= 1
volo10) + x4 + x7 + x8 + x12 + x17 + x18 + x27 + x28 + x30 + x33 + x34 + x37
+ x38 + x39 + x40 + x49 + x50 >= 1
volo11) + x5 + x11 + x14 + x18 + x19 + x24 + x27 + x28 + x30 + x33 + x39
+ x42 >= 1
volo12) + x5 + x7 + x12 + x13 + x15 + x17 + x24 + x27 + x29 + x35 + x41 >= 1
volo13) + x7 + x11 + x14 + x18 + x19 + x23 + x25 + x28 + x30 + x32 + x35
+ x36 + x38 + x39 + x42 + x43 + x44 + x45 + x46 >= 1
volo14) + x7 + x8 + x9 + x15 + x17 + x19 + x20 + x21 + x25 + x26 + x29 + x31
+ x34 + x43 + x47 + x48 >= 1
volo15) + x5 + x7 + x9 + x10 + x13 + x16 + x18 + x20 + x22 + x26 + x29 + x33
+ x38 + x40 + x41 + x42 + x44 + x45 + x47 >= 1
volo16) + x6 + x8 + x10 + x11 + x12 + x14 + x15 + x16 + x19 + x20 + x23 + x25
+ x28 + x30 + x31 + x43 + x46 + x49 >= 1
volo17) + x8 + x10 + x17 + x19 + x20 + x24 + x28 + x32 + x34 + x36 + x45
+ x48 + x49 + x50 >= 1
volo18) + x6 + x9 + x12 + x13 + x16 + x18 + x19 + x20 + x29 + x30 + x37
+ x40 + x44 + x47 + x50 >= 1
volo19) + x8 + x9 + x10 + x13 + x15 + x16 + x17 + x18 + x20 + x26 + x29
+ x35 + x37 + x41 + x46 + x49 >= 1
volo20) + x6 + x9 + x10 + x16 + x17 + x25 + x26 + x30 + x36 + x48 + x50 >= 1
volo21) + x21 + x31 + x33 + x34 + x38 + x39 + x41 + x42 + x43 + x44 >= 1
volo22) + x22 + x35 + x39 + x42 + x45 + x46 + x47 >= 1
volo23) + x23 + x32 + x36 + x38 + x40 + x43 + x45 + x48 + x49 >= 1
volo24) + x24 + x31 + x36 + x39 + x41 + x42 + x44 + x46 + x48 + x50 >= 1
volo25) + x25 + x32 + x33 + x34 + x37 + x40 + x47 + x49 >= 1
volo26) + x26 + x35 + x36 + x37 + x43 + x50 >= 1
volo27) + x27 + x33 + x36 + x40 + x41 + x44 + x46 >= 1
volo28) + x27 + x28 + x32 + x33 + x35 + x38 + x39 + x45 >= 1
volo29) + x29 + x31 + x34 + x35 + x37 + x38 + x40 + x49 >= 1
volo30) + x30 + x31 + x32 + x34 + x37 + x47 + x48 + x50 >= 1
! vincolo che limita a 7 il numero degli equipaggi disponibili
limEqu) + x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10
+ x11 + x12 + x13 + x14 + x15 + x16 + x17 + x18 + x19 + x20
+ x21 + x22 + x23 + x24 + x25 + x26 + x27 + x28 + x29 + x30
+ x31 + x32 + x33 + x34 + x35 + x36 + x37 + x38 + x39 + x40
+ x41 + x42 + x43 + x44 + x45 + x46 + x47 + x48 + x49 + x50 = 7
end
! sono utilizzate 50 variabili binarie
int 50
Altre domande
La compagnia dispone attualmente di 7 equipaggi. Si pone anche il problema di capire se sarebbe possibile diminuire il numero di equipaggi impiegati, coprendo ugualmente tutti i voli, in che misura ciò sarebbe possibile e con quale risparmio in termini di costo e di viaggi di trasferimento.
Con 7 equipaggi il costo minimo è pari a 8000, ed abbiamo 24 voli di trasferimento (basta sommare i valori della colonna "slack or surplus" relativi ai voli). Se togliamo il vincolo che fissa a 7 gli equipaggi di cui disponiamo e riproviamo a risolvere il problema, vedremo che:
- la soluzione ottima ci dice che il costo minimo è 6900
- utilizziamo 6 equipaggi (quelli che hanno la colonna "value" settata a 1)
- abbiamo 18 voli di trasferimento
Torna alla pagina di Ricerca Operativa
