Claudio Arbib
Università di L’Aquila
Ricerca Operativa
Esercitazione VII
Un viaggio in autostrada
Lo scenario
• Il dottor Strangelove vive a Roma e insegna a l’Aquila, e per
questo motivo viaggia periodicamente tra le due città.
• Normalmente il tragitto viene percorso con i colleghi in
automobile lungo quella che un tempo si chiamava A24 (oggi,
più pomposamente, “Autostrada dei Parchi”: del resto la
società che la gestisce, un tempo banalmente denominata
Società Autostrade, ora si chiama “Autostrade per l’Italia” –
manco fosse un partito politico).
• Tra una chiacchiera e l’altra, per passare il tempo, il prof si
pone il problema di ridurre i consumi di carburante.
• Questi dipendono da vari fattori, tra cui:
– le pendenze superate
– le velocità mantenute
durante il viaggio.
Profilo altimetrico
Tra Roma GRA e l’Aquila Ovest la A24 presenta il seguente
profilo altimetrico
1100
800
580
750
700
300
12,8
15,4
L’Aquila Ovest
11,2
Tornimparte
10,2
Torano
17,4
Tagliacozzo
9,0
Carsoli
11,9
Vicovaro
Tivoli
Roma GRA
14,6
Castel Madama
130
60
Ottimizzare i consumi
Il dottor Strangelove ha messo a punto una formula empirica
che lega il consumo c della propria vettura (litri di benzina
ogni 100 km) alla velocità mantenuta u (km/ora) e alla
pendenza superata p (%):
c(u, p) =
100
100 – p
 u
Il problema da risolvere può formularsi come segue:
dividere il tragitto in tratte opportune e assegnare a ciascuna
tratta una velocità in modo da minimizzare la quantità di
carburante consumata per arrivare a destinazione entro un
tempo dato T
Ottimizzare i consumi
Tramite un foglio di calcolo è facilissimo individuare tratte di
pendenza più o meno costante
Tratta
km dislivello (m) pendenza (%)
Roma - Tivoli
14,6
60,0
4,1
Tivoli - Castel Madama
Castel Madama - Vicovaro
11,9
9,0
70,0
170,0
5,9
18,9
Vicovaro - Carsoli
Carsoli - Tagliacozzo
17,4
10,2
280,0
220,0
16,1
21,6
Tagliacozzo - Torano
11,2
-100,0
-8,9
Torano - Tornimparte
Tornimparte - L'Aquila Ovest
12,8
15,4
400,0
-350,0
31,3
-22,7
102,5
750,0
7,3
Totale
Ottimizzare i consumi
Tramite un foglio di calcolo è facilissimo individuare tratte di
pendenza più o meno costante e calcolare il relativo consumo
Tratta
km pend. (%)
Roma - Tivoli
14,6
4,1
1,4
1,5
1,6
1,7
1,7
Tivoli - Castel Madama
Castel Madama - Vicovaro
11,9
9,0
5,9
18,9
1,2
1,1
1,3
1,1
1,3
1,2
1,4
1,2
1,4
1,3
Vicovaro - Carsoli
Carsoli - Tagliacozzo
17,4
10,2
16,1
21,6
2,0
1,2
2,1
1,3
2,2
1,4
2,3
1,4
2,4
1,5
Tagliacozzo - Torano
11,2
-8,9
1,0
1,0
1,1
1,1
1,2
Torano - Tornimparte
Tornimparte - L'Aquila Ovest
12,8
15,4
31,3
-22,7
1,8
1,2
1,9
1,3
2,0
1,3
2,0
1,4
2,1
1,4
102,5
7,3
90
100 110 120 130
Totale
consumo (lt)
velocità
Ottimizzare i consumi
Tramite un foglio di calcolo è facilissimo individuare tratte di
pendenza più o meno costante e calcolare il tempo impiegato
a percorrerle
Tratta
km
Roma - Tivoli
14,6
9,7
8,8
8,0
7,3
6,7
Tivoli - Castel Madama
Castel Madama - Vicovaro
11,9
9,0
7,9
6,0
7,1
5,4
6,5
4,9
6,0
4,5
5,5
4,2
Vicovaro - Carsoli
Carsoli - Tagliacozzo
17,4
10,2
11,6 10,4 9,5
6,8 6,1 5,6
8,7
5,1
8,0
4,7
Tagliacozzo - Torano
11,2
7,5
6,7
6,1
5,6
5,2
Torano - Tornimparte
Tornimparte - L'Aquila Ovest
12,8
15,4
8,5
10,3
7,7
9,2
7,0
8,4
6,4
7,7
5,9
7,1
102,5
90
Totale
tempo (min)
100 110 120 130
velocità
Ottimizzare i consumi
Una soluzione del problema corrisponde a un assegnamento di
velocità a tratte.
61,9
A ogni assegnamento corrisponde un tempo di viaggio
minuti
Tratta
km
Roma - Tivoli
14,6
9,7
8,8
8,0
7,3
6,7
Tivoli - Castel Madama
Castel Madama - Vicovaro
11,9
9,0
7,9
6,0
7,1
5,4
6,5
4,9
6,0
4,5
5,5
4,2
Vicovaro - Carsoli
Carsoli - Tagliacozzo
17,4
10,2
11,6 10,4 9,5
6,8 6,1 5,6
8,7
5,1
8,0
4,7
Tagliacozzo - Torano
11,2
7,5
6,7
6,1
5,6
5,2
Torano - Tornimparte
Tornimparte - L'Aquila Ovest
12,8
15,4
8,5
10,3
7,7
9,2
7,0
8,4
6,4
7,7
5,9
7,1
102,5
90
Totale
tempo (min)
100 110 120 130
velocità
Ottimizzare i consumi
Una soluzione del problema corrisponde a un assegnamento di
velocità a tratte.
11,5
A ogni assegnamento corrisponde un consumo
litri
Tratta
km pend. (%)
Roma - Tivoli
14,6
4,1
1,4
1,5
1,6
1,7
1,7
Tivoli - Castel Madama
Castel Madama - Vicovaro
11,9
9,0
5,9
18,9
1,2
1,1
1,3
1,1
1,3
1,2
1,4
1,2
1,4
1,3
Vicovaro - Carsoli
Carsoli - Tagliacozzo
17,4
10,2
16,1
21,6
2,0
1,2
2,1
1,3
2,2
1,4
2,3
1,4
2,4
1,5
Tagliacozzo - Torano
11,2
-8,9
1,0
1,0
1,1
1,1
1,2
Torano - Tornimparte
Tornimparte - L'Aquila Ovest
12,8
15,4
31,3
-22,7
1,8
1,2
1,9
1,3
2,0
1,3
2,0
1,4
2,1
1,4
102,5
7,3
90
100 110 120 130
Totale
consumo (lt)
velocità
Formulazione
Consideriamo un grafo bipartito completo G = (U, V, E) dove U è
l’insieme delle velocità ammissibili e V quello delle tratte
Roma GRA – Tivoli
90
Tivoli – Castel Madama
100
Castel Madama – Vicovaro
110
Vicovaro – Carsoli
120
130
Carsoli – Tagliacozzo
Tagliacozzo – Torano
Torano – Tornimparte
Tornimparte – L’Aquila Ovest
Formulazione
Ogni insieme di archi che rappresenti un assegnamento di tratte a
velocità ha due pesi: tempo e consumo
61,9 < T
90
Roma GRA – Tivoli
Tivoli – Castel Madama
100
Castel Madama – Vicovaro
110
Vicovaro – Carsoli
Carsoli – Tagliacozzo
120
Tagliacozzo – Torano
130
Torano – Tornimparte
11,5 = min
Tornimparte – L’Aquila Ovest
Formulazione
Sia xuv una variabile di decisione binaria:
xuv = 1
se si percorre il tratto v a velocità u
xuv = 0
altrimenti
Si indichino inoltre con cuv e con tuv i pesi corrispondenti
(consumo e tempo).
Il problema si formula come segue:
min
uU vV cuvxuv
uU vV tuvxuv <
uU xuv = 1
(consumo complessivo)
T
0 < xuv < 1, intero
(rispetto dei tempi)
vV (ogni tratta va percorsa)