FACOLTA’ D’INGEGNERIA

CORSO DI RICERCA OPERATIVAa.a. 2001/2002

Problema di assegnamento di una

compagnia aerea

Università degli studi di Cagliari

Studenti:

Alessandro

Gianluca

Docente:

Prof.ssa Paola Zuddas

La compagnia aerea Avion Travel effettua La compagnia aerea Avion Travel effettua giornalmente i seguenti voli da Roma a Londra…giornalmente i seguenti voli da Roma a Londra…

22:0022:0020:0020:0055

21:0021:0019:0019:0044

17:0017:0015:0015:0033

12:0012:0010:0010:0022

11:0011:009:009:0011

Arrivo aArrivo aLONDRALONDRA

Partenza daPartenza daROMAROMAN° voloN° volo

23:0021:00E

22:0020:00D

16:0014:00C

11:009:00B

10:008:00A

Arrivo aROMA

Partenza daLONDRA

N° volo

……e i seguenti da Londra a Romae i seguenti da Londra a Roma

PROBLEMA:PROBLEMA:

minimizzare il tempo di permanenza a terra degli aerei minimizzare il tempo di permanenza a terra degli aerei realizzando l’accoppiamento ottimale tra voli in arrivo e realizzando l’accoppiamento ottimale tra voli in arrivo e

voli in partenza, considerando inoltre la necessità di voli in partenza, considerando inoltre la necessità di almeno un’ora a terra per problemi di manutenzione e almeno un’ora a terra per problemi di manutenzione e

rifornimento sui velivolirifornimento sui velivoli

SOLUZIONE:SOLUZIONE:

Quello in esame è un tipico problema di assegnamento che Quello in esame è un tipico problema di assegnamento che può essere formulato nel modo seguente:può essere formulato nel modo seguente:

jix

jx

ix

xcz

ij

jij

iij

i jijij

,1,0

1

1

min

Avendo indicato con:

• cij il tempo di permanenza a terra dell’aereo che, avendo completato il volo i viene assegnato al

volo j

• xij la variabile binaria indicante l’assegnazione (xij = 1) o la non assegnazione (xij = 0) dell’aereo

proveniente dal volo i, al volo j

• la condizione che tra tutti gli aerei che hanno completato i voli i uno solo possa

ripartire per il volo j

• la condizione che l’aereo che ha completato il volo i possa ripartire per uno solo dei j voli disponibili

i

ijx 1

j

ijx 1

Il tempo di permanenza a terra complessivo sarà determinato dalla somma dei tempi di

permanenza a terra negli aeroporti Leonardo da Vinci di Fiumicino e Heathrow di Londra.

Si rende necessaria quindi la risoluzione di due problemi distinti:

PROBLEMA 1Minimizzazione dei tempi di

permanenza a terra nell’aeroporto Leonardo da Vinci

Assumendo gli indici i e j come:

abbiamo calcolato tutti i tempi di permanenza a Roma come differenza tra l’orario di partenza del generico volo j e l’orario d’arrivo del generico volo i, tenendo conto della necessità che questi non siano inferiori ad un’ora, ottenendo così la seguente tabella dei costi:

i = A, … ,Ej = 1, … ,5

TEMPI DI PERMANENZA A ROMA [ h ]

2120161110E

2221171211D

43231817C

9842322B

10952423A

54321ARRIVO

PARTENZA

MODELLO MATEMATICO

MIN 23XA1 + 24XA2 + 5XA3 + 9XA4 + 10XA5 +

+ 22XB1 + 23XB2 + 4XB3 + 8XB4 + 9XB5 +

+ 17XC1 + 18XC2 + 23XC3 + 3XC4 + 4XC5 +

+ 11XD1 + 12XD2 + 17XD3 + 21XD4 + 22XD5 +

+ 10XE1 + 11XE2 + 16XE3 + 20XE4 + 21XE5

Funzione obiettivo

1) XA1 + XA2 + XA3 + XA4 + XA5 = 1

2) XB1 + XB2 + XB3 + XB4 + XB5 = 1

3) XC1 + XC2 + XC3 + XC4 + XC5 = 1

4) XD1 + XD2 + XD3 + XD4 + XD5 = 1

5) XE1 + XE2 + XE3 + XE4 + XE5 = 1

6) XA1 + XB1 + XC1 + XD1 + XE1 = 1

7) XA2 + XB2 + XC2 + XD2 + XE2 = 1

8) XA3 + XB3 + XC3 + XD3 + XE3 = 1

9) XA4 + XB4 + XC4 + XD4 + XE4 = 1

10) XA5 + XB5 + XC5 + XD5 + XE5 = 1

Condizioni di vincolo

VALORE OTTIMALE DELLA FUNZIONE OBIETTIVO:

1) 39.00000 [h]

VARIABLE VALUE REDUCED COST

XA5 1.000000 0.000000

XB3 1.000000 0.000000

XC4 1.000000 0.000000

XD1 1.000000 0.000000

XE2 1.000000 0.000000

SOLUZIONE OTTIMA

Gli assegnamenti ottimali risultano pertanto:

A C D EB

VOLI IN ARRIVO

VOLI IN PARTENZA

43

510

211

111

34

ATTENZIONE!!

La matrice dei coefficienti (10 x 25):

Ha rango 9

Pertanto le soluzioni ottime possibili sono:

16

L’accoppiamento trovato è ottimale ma non unico

PROBLEMA 2Minimizzazione dei tempi di

permanenza a terra nell’aeroporto Heathrow di Londra

In questo caso i domini degli indici i e j sono:

i = 1, … ,5j = A, … ,E

I tempi di permanenza a Londra, calcolati come differenza (non inferiore ad un’ora) tra l’orario di partenza del generico volo j e l’orario d’arrivo del generico volo i, sono riportati

nella seguente tabella dei costi:

TEMPI DI PERMANENZA A LONDRA [ h ]

23221611105

24231712114

432116153

98221202

109322211

EDCBAARRIVO

PARTENZA

MODELLO MATEMATICO

MIN 21Y1A + 22Y1B + 3Y1C + 9Y1D + 10Y1E +

+ 20Y2A + 21Y2B + 2Y2C + 8Y2D + 9Y2E +

+ 15Y3A + 16Y3B + 21Y3C + 3Y3D + 4Y3E +

+ 11Y4A + 12Y4B + 17Y4C + 23Y4D + 24Y4E +

+ 10Y5A + 11Y5B + 16Y5C + 22Y5D + 23Y5E

Funzione obiettivo

• Y1A + Y1B + Y1C + Y1D + Y1E = 1

• Y2A + Y2B + Y2C + Y2D + Y2E = 1

• Y3A + Y3B + Y3C + Y3D + Y3E = 1

• Y4A + Y4B + Y4C + Y4D + Y4E = 1

• Y5A + Y5B + Y5C + Y5D + Y5E = 1

• Y1A + Y2A + Y3A + Y4A + Y5A = 1

• Y1B + Y2B + Y3B + Y4B + Y5B = 1

• Y1C + Y2C + Y3C + Y4C + Y5C = 1

• Y1D + Y2D + Y3D + Y4D + Y5D = 1

• Y1E + Y2E + Y3E + Y4E + Y5E = 1

Condizioni di vincolo

SOLUZIONE OTTIMA

VALORE OTTIMALE DELLA FUNZIONE OBIETTIVO

1) 37.00000 [h]

VARIABLE VALUE REDUCED COST

Y1E 1.000000 0.000000

Y2C 1.000000 0.000000

Y3D 1.000000 0.000000

Y4A 1.000000 0.000000

Y5B 1.000000 0.000000

Gli assegnamenti ottimali risultano pertanto:

VOLI IN PARTENZA

VOLI IN ARRIVO

4

D3

5

E10

2

B11

1

A11

3

C2

Rango = 9

Pertanto le soluzioni ottime possibili sono:

16

Anche in questo caso la soluzione ottima trovata non è unica in quanto la matrice dei coefficienti (10 x 25) ha la stessa struttura di quella relativa al problema 1:

La sequenza ottima di voli tra Roma e Londra è:

1

2

4

5

3

10

2

11

11

3

E

C

A

B

11

3

10

4

11D

39 h 37 h

Il problema generale di minimizzazione dei tempi di permanenza a terra degli aerei ammette quindi la soluzione ottima rappresentata nella diapositiva

precedente e che implica un costo minimo totale pari a:

z = z1 + z2 = 39 + 37 = 76 h

ore totali di permanenza a terra

La compagnia Avion Travel sta valutando l’opportunità di raddoppiare i collegamenti Roma-Londra.

PROBLEMA bis

Per valutare la convenienza di questa scelta si richiede la conoscenza della variazione dei tempi di permanenza a terra in questa nuova situazione

La nuova tabella oraria giornalieria dei voli La nuova tabella oraria giornalieria dei voli Roma-Londra diventerebbe… Roma-Londra diventerebbe…

24:0024:0022:0022:001010

23:0023:0021:0021:0099

21:0021:0019:0019:0088

20:0020:0018:0018:0077

17:0017:0015:0015:0066

15:0015:0013:0013:0055

14:0014:0012:0012:0044

11:0011:009:009:0033

10:0010:008:008:0022

8:008:006:006:0011

Arrivo aArrivo aLONDRALONDRA

Partenza daPartenza daROMAROMAN° voloN° volo

23:0021:00L

22:0020:00I

21:0019:00H

20:0018:00G

18:0016:00F

16:0014:00E

14:0012:00D

12:0010:00C

11:009:00B

10:008:00A

Arrivo aROMA

Partenza daLONDRA

N° volo

……mentre quella Londra-Romamentre quella Londra-Roma

PROBLEMA 1 bis

I nuovi domini degli indici i e j sono:

i = A, … ,Lj = 1, … ,10

La tabella dei costi associata a questo problema risulta così costituita:

Minimizzazione dei tempi di permanenza a terra nell’aeroporto

Leonardo da Vinci

TEMPI DI PERMANENZA A ROMA [ h ]

232220191614131097L

2423212017151411108I

124222118161512119H

212322191716131210G

43124211918151412F

6532232120171614E

875412322191816D

109763124212018C

111087421222119B

121198532232220A

10987654321ARRIVOPARTENZA

MODELLO MATEMATICO

MIN 20XA1 + 22XA2 + 23XA3 + 2XA4 + 3XA5 + 5XA6 + 8XA7 + 9XA8 + 11XA9 + 12XA10 +

+ 19XB1 + 21XB2 + 22XB3 + 1XB4 + 2XB5 + 4XB6 + 7XB7 + 8XB8 + 10XB9 + 11XB10 +

+ 18XC1 + 20XC2 + 21XC3 + 24XC4 + 1XC5 + 3XC6 + 6XC7 + 7XC8 + 9XC9 + 10XC10 +

+ 16XD1 + 18XD2 + 19XD3 + 22XD4 + 23XD5 + 1XD6 + 4XD7 + 5XD8 + 7XD9 + 8XD10 +

+ 14XE1 + 16XE2 + 17XE3 + 20XE4 + 21XE5 + 23XE6 + 2XE7 + 3XE8 + 5XE9 + 6XE10 +

+ 12XF1 + 14XF2 + 15XF3 + 18XF4 + 19XF5 + 21XF6 + 24XF7 + 1XF8 + 3XF9 + 4XF10 +

+ 10XG1 + 12XG2 + 13XG3 + 15XG4 + 17XG5 + 19XG6 + 22XG7 + 23XG8 + 1XG9 + 2XG10 +

+ 9XH1 + 11XH2 + 12XH3 + 14XH4 + 16XH5 + 18XH6 + 21XH7 + 22XH8 + 24XH9 + 1XH10 +

+ 8XI1 + 10XI2 + 11XI3 + 13XI4 + 15XI5 + 17XI6 + 20XI7 + 21XI8 + 23XI9 + 24XI10 +

+ 7XL1 + 9XL2 + 10XL3 + 12XL4 + 14XL5 + 16XL6 + 19XL7 + 20XL8 + 22XL9 + 23XL10

Funzione obiettivo

1) XA1 + XA2 + XA3 + XA4 + XA5 + XA6 + XA7 + XA8 + XA9 + XA10 = 1

2) XB1 + XB2 + XB3 + XB4 + XB5 + XB6 + XB7 + XB8 + XB9 + XB10 = 1

3) XC1 + XC2 + XC3 + XC4 + XC5 + XC6 + XC7 + XC8 + XC9 + XC10 = 1

4) XD1 + XD2 + XD3 + XD4 + XD5 + XD6 + XD7 + XD8 + XD9 + XD10 = 1

5) XE1 + XE2 + XE3 + XE4 + XE5 + XE6 + XE7 + XE8 + XE9 + XE10 = 1

6) XF1 + XF2 + XF3 + XF4 + XF5 + XF6 + XF7 + XF8 + XF9 + XF10 = 1

7) XG1 + XG2 + XG3 + XG4 + XG5 + XG6 + XG7 + XG8 + XG9 + XG10 = 1

8) XH1 + XH2 + XH3 + XH4 + XH5 + XH6 + XH7 + XH8 + XH9 + XH10 = 1

9) XI1 + XI2 + XI3 + XI4 + XI5 + XI6 + XI7 + XI8 + XI9 + XI10 = 1

10) XL1 + XL2 + XL3 + XL4 + XL5 + XL6 + XL7 + XL8 + XL9 + XL10 = 1

Vincoli…

11) XA1 + XB1 + XC1 + XD1 + XE1 + XF1 + XG1 + XH1 + XI1 + XL1 = 1

12) XA2 + XB2 + XC2 + XD2 + XE2 + XF2 + XG2 + XH2 + XI2 + XL2 = 1

13) XA3 + XB3 + XC3 + XD3 + XE3 + XF3 + XG3 + XH3 + XI3 + XL3 = 1

14) XA4 + XB4 + XC4 + XD4 + XE4 + XF4 + XG4 + XH4 + XI4 + XL4 = 1

15) XA5 + XB5 + XC5 + XD5 + XE5 + XF5 + XG5 + XH5 + XI5 + XL5 = 1

16) XA6 + XB6 + XC6 + XD6 + XE6 + XF6 + XG6 + XH6 + XI6 + XL6 = 1

17) XA7 + XB7 + XC7 + XD7 + XE7 + XF7 + XG7 + XH7 + XI7 + XL7 = 1

18) XA8 + XB8 + XC8 + XD8 + XE8 + XF8 + XG8 + XH8 + XI8 + XL8 = 1

19) XA9 + XB9 + XC9 + XD9 + XE9 + XF9 + XG9 + XH9 + XI9 + XL9 = 1

20) XA10 + XB10 + XC10 + XD10 + XE10 + XF10 + XG10 + XH10 + XI10 + XL10 = 1

…e ancora vincoli!

VALORE OTTIMALE DELLA FUNZIONE OBIETTIVO:

1) 48.00000 [h]

VARIABLE VALUE REDUCED COST

XA9 1.000000 0.000000

XB4 1.000000 0.000000

XC5 1.000000 0.000000

XD6 1.000000 0.000000

XE7 1.000000 0.000000

XF8 1.000000 0.000000

XG10 1.000000 0.000000

XH2 1.000000 0.000000

XI1 1.000000 0.000000

XL3 1.000000 0.000000

SOLUZIONE OTTIMA

Gli assegnamenti ottimali risultano pertanto:

A C D E F G H I LB

VOLI IN ARRIVO

VOLI IN PARTENZA

911

41

51

61

72

81

102

211

18

310

La matrice dei coefficienti (20 x 100):

ha rango 19

Pertanto le soluzioni ottime possibili sono:

81

L’accoppiamento trovato è ottimale ma non unico

PROBLEMA 2 bisMinimizzazione dei tempi di

permanenza a terra nell’aeroporto Heathrow di Londra

Assumendo gli indici i e j come:

i = 1, … ,10j = A, … ,L

e ricalcolando i tempi di permanenza a terra abbiamo ottenuto la seguente tabella dei costi:

TEMPI DI PERMANENZA A LONDRA [h]

21201918161412109810

22212019171513111099

242322211917151312118

12423222018161413127

43212321191716156

6543123211918175

7654224222019184

109875312322213

1110986422423222

13121110863421241

LIHGFEDCBAARRIVOPARTENZA

MODELLO MATEMATICO

MIN 24Y1A + 1Y1B + 2Y1C + 4Y1D + 6Y1E + 8Y1F + 10Y1G + 11Y1H + 12Y1I + 13Y1L +

+ 22Y2A + 23Y2B + 24Y2C + 2Y2D + 4Y2E + 6Y2F + 8Y2G + 9Y2H + 10Y2I + 11Y2L +

+ 21Y3A + 22Y3B + 23Y3C + 1Y3D + 3Y3E + 5Y3F + 7Y3G + 8Y3H + 9Y3I + 10Y3L +

+ 18Y4A + 19Y4B + 20Y4C + 22Y4D + 24Y4E + 2Y4F + 4Y4G + 5Y4H + 6Y4I + 8Y4L +

+ 17Y5A + 18Y5B + 19Y5C + 21Y5D + 23Y5E + 1Y5F + 3Y5G + 4Y5H + 5Y5I + 6Y5L +

+ 15Y6A + 16Y6B + 17Y6C + 19Y6D + 21Y6E + 23Y6F + 1Y6G + 2Y6H + 3Y6I + 4Y6L +

+ 12Y7A + 13Y7B + 14Y7C + 16Y7D + 18Y7E + 20Y7F + 22Y7G + 23Y7H + 24Y7I + 1Y7L +

+ 11Y8A + 12Y8B + 13Y8C + 15Y8D + 17Y8E + 19Y8F + 21Y8G + 22Y8H + 23Y8I + 24Y8L +

+ 9Y9A + 10Y9B + 11Y9C + 13Y9D + 15Y9E + 17Y9F + 19Y9G + 20Y9H + 21Y9I + 22Y9L +

+ 8Y10A + 9Y10B + 10Y10C + 12Y10D + 14Y10E + 16Y10F + 18Y10G + 19Y10H + 20Y10I + 21Y10L

Funzione obiettivo

1) Y1A + Y1B + Y1C + Y1D + Y1E + Y1F + Y1G + Y1H + Y1I + Y1L = 1

2) Y2A + Y2B + Y2C + Y2D + Y2E + Y2F + Y2G + Y2H + Y2I + Y2L = 1

3) Y3A + Y3B + Y3C + Y3D + Y3E + Y3F + Y3G + Y3H + Y3I + Y3L = 1

4) Y4A + Y4B + Y4C + Y4D + Y4E + Y4F + Y4G + Y4H + Y4I + Y4L = 1

5) Y5A + Y5B + Y5C + Y5D + Y5E + Y5F + Y5G + Y5H + Y5I + Y5L = 1

6) Y6A + Y6B + Y6C + Y6D + Y6E + Y6F + Y6G + Y6H + Y6I + Y6L = 1

7) Y7A + Y7B + Y7C + Y7D + Y7E + Y7F + Y7G + Y7H + Y7I + Y7L = 1

8) Y8A + Y8B + Y8C + Y8D + Y8E + Y8F + Y8G + Y8H + Y8I + Y8L = 1

9) Y9A + Y9B + Y9C + Y9D + Y9E + Y9F + Y9G + Y9H + Y9I + Y9L = 1

10) Y10A + Y10B + Y10C + Y10D + Y10E + Y10F + Y10G + Y10H + Y10I + Y10L = 1

Condizioni di vincolo

• Y1A + Y2A + Y3A + Y4A + Y5A + Y6A + Y7A + Y8A + Y9A + Y10A = 1

• Y1B + Y2B + Y3B + Y4B + Y5B + Y6B + Y7B + Y8B + Y9B + Y10B = 1

• Y1C + Y2C + Y3C + Y4C + Y5C + Y6C + Y7C + Y8C + Y9C + Y10C = 1

• Y1D + Y2D + Y3D+ Y4D + Y5D + Y6D + Y7D + Y8D + Y9D + Y10D = 1

• Y1E + Y2E + Y3E + Y4E + Y5E + Y6E + Y7E + Y8E + Y9E + Y10E = 1

• Y1F + Y2F + Y3F + Y4F + Y5F + Y6F + Y7F + Y8F + Y9F + Y10F = 1

• Y1G + Y2G + Y3G + Y4G + Y5G + Y6G + Y7G + Y8G + Y9G + Y10G = 1

• Y1H + Y2H + Y3H + Y4H + Y5H + Y6H + Y7H + Y8H + Y9H + Y10H = 1

• Y1I + Y2I + Y3I + Y4I + Y5I + Y6I + Y7I + Y8I + Y9I + Y10I = 1

• Y1L + Y2L + Y3L + Y4L + Y5L + Y6L + Y7L + Y8L + Y9L + Y10L = 1

Condizioni di vincolo

SOLUZIONE OTTIMA

VALORE OTTIMALE DELLA FUNZIONE OBIETTIVO

1) 56.00000 [h]

VARIABLE VALUE REDUCED COST

Y1B 1.000000 0.000000

Y2D 1.000000 0.000000

Y3E 1.000000 0.000000

Y4G 1.000000 0.000000

Y5F 1.000000 0.000000

Y6I 1.000000 0.000000

Y7L 1.000000 0.000000

Y8A 1.000000 0.000000

Y9C 1.000000 0.000000

Y10H 1.000000 0.000000

Gli assegnamenti ottimali risultano pertanto:

VOLI IN PARTENZA

VOLI IN ARRIVO

1 3 4 5 6 7 8 92 10

3

I2

D3

E1

F4

G19

H1

L1

B11

A11

C

La matrice dei coefficienti (20 x 100):

ha rango 19

Pertanto le soluzioni ottime possibili sono:

81

Anche in questo caso l’accoppiamento trovato è ottimale ma non unico

La sequenza ottima di voli tra Roma e Londra è:1 4 19 2 3 3 1 1 11 11

B G H D I E L F A C1 4 10 2 6 3 7 5 8 9

1 2 11 1 8 2 10 1 11 148 h

56 h

La soluzione ottima del problema di assegnamento nel caso si attuasse il raddoppio del numero dei collegamenti

Roma-Londra è pari a:

z = z1 + z2 = 48 + 56 = 104 h

ore totali di permanenza a terra

CONCLUSIONILimitando l’analisi ai tempi di permanenza a terra risulta più proficua la soluzione con 20 voli giornalieri in quanto:

L’incremento dei tempi di permanenza a terra è circa del 37% in corrispondenza di un incremento del 100% del numero di voli;

Il tempo medio di permanenza a terra per velivolo è pari a 5,2 h contro le 7,6 h che si hanno attualmente.

OSSERVAZIONICome visto in precedenza, per via della particolare struttura delle matrici dei coefficienti, le soluzioni

trovate, pur essendo ottime, non sono uniche.

Questa pluralità di soluzioni consente di modificare la sequenza dei voli che potrebbe rendersi necessaria a

seguito di altri vincoli non considerati in quest’analisi.

E’ facile determinare le soluzioni alternative intervenendo direttamente sulla tabella dei costi una

volta nota una soluzione ottima.

2120161110E

2221171211D

43231817C

9842322B

10952423A

54321AP

Prendiamo in esame la tabella dei costi relativa al PROBLEMA 1 con in evidenza la soluzione ottima trovata:

E’ immediato notare che è possibile scambiare gli assegnamenti dei voli D ed E tra loro (così come tra i voli A e C) ottenendo lo stesso tempo totale di permanenza a

terra

2120161110E

2221171211D

43231817C

9842322B

10952423A

54321AP

2120161110E

2221171211D

43231817C

9842322B

10952423A

54321AP

Le combinazioni di questi scambi (e degli altri possibili non evidenziati) danno luogo all’infinità di soluzioni resa

evidente in precedenza da considerazioni in merito al rango della matrice dei coefficienti.

SOFTWARE UTILIZZATODemo Lindo/PCDemo Lindo/PC

Release 6.1(27 Nov. ‘01)Release 6.1(27 Nov. ‘01)Lindo Systems, Inc.Lindo Systems, Inc.

1415 North Dayton St.1415 North Dayton St.Chicago, IL 60622Chicago, IL 60622

Dimensioni massime del modello:Dimensioni massime del modello:Vincoli 150Vincoli 150

Variabili 300Variabili 300Variabili intere 50Variabili intere 50Nonzeros 2000000Nonzeros 2000000

Homepage Lindo Systems