cerca
Ricerca Operativa - PLI - Equipaggi - 15.02.00
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Ricerca Operativa - PLI - Equipaggi - 15.02.00

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