modelli di assegnazione - Università degli Studi di Catania

Corso di Laurea Ingegneria
Civile - AA 1112
C
Corso
di
di:
Fondamenti di Trasporti
Lezione:
Analisi interazione
domanda/offerta: modelli
di assegnazione
Giuseppe Inturri
Università di Catania
Dipartimento di Ingegneria Civile e Ambientale
[email protected]
definizione
 Assegnare la domanda ad una rete di trasporto significa
calcolare
l l
i fl
flussii di utentii e lle prestazioni
i i per ciascun
i
elemento del sistema di offerta (nodi e archi), come risultato
d i flussi
dei
fl i di domanda
d
d O
Origine-Destinazione,
i i D i i
ddeii
comportamenti di scelta del percorso e delle reciproche
i
interazioni
i i fra
f domanda
d
d e offerta
ff
 I modelli di assegnazione sono i modelli matematici
utilizzati per questo scopo
Introduzione del corso
i modelli di assegnazione nella simulazione dei sistemi di trasporto
Introduzione del corso
definizione ed ipotesi
o
d
od
Iod
A
c
C
nodo (zona) origine dello spostamento;
nodo (zona) destinazione dello spostamento;
coppia Origine-Destinazione;
insieme dei percorsi rilevanti per gli utenti della coppia od
p
complessiva
p
matrice di incidenza archi-percorsi
vettore dei costi di arco, ci;
vettore complessivo dei costi di percorso, formato dai vettori
dei costi
di percorso Cod relativi a ciascuna coppia od;
C = AT c
Introduzione del corso
esempio
arco
(1 2)
(1,2)
(1,3)
(2,3)
(2 4)
(2,4)
(3,4)
2
2
2
3
1
1
4
1
3
GRAFO
Introduzione del corso
c
2
1
3
2
1
VETTORE
COSTI DI
ARCO
d
O-D
1-4
1
4 1000
2-4 1500
3-4 800
VETTORE
DOMANDA
OD 1-4
percorsi
OD 2-4
OD 3-4
Introduzione del corso
matrice A di incidenza archi-percorsi
e vettore C dei costi di percorso
Vettore
costi di
percorso
C
6
4
2
4
2
1
A
MATRICE INCIDENZA ARCHI-PERCORSI
coppie O-D
1-4
2-4
3-4
1
2
3
4
5
6
percorsi
(1,2)
1
1
0
0
0
0
(1,3)
0
0
1
0
0
0
(2,3)
1
0
0
1
0
0
(2 4)
(2,4)
0
1
0
0
1
0
(3,4)
1
0
1
1
0
1
archi
Introduzione del corso
Vettore
costi di
arco
arco
(1,2)
(1,3)
(2,3)
(2 4)
(2,4)
(3,4)
c
2
1
3
2
1
vettore F dei flussi di percorso
 per conoscere il vettore F dei flussi di percorso,
percorso bisogna calcolare come il





generico flusso di domanda (dod) del vettore domanda si divide tra i percorsi
possibili
b
bisogna
dunque
d
applicare
l
un modello
d ll di scelta
l del
d l percorso
in generale il modello di scelta del percorso fornisce, per una data coppia O-D
 la probabilità pk che un percorso k sia scelto
 e il flusso di percorso Fk = dod p(k/od)
la probabilità pk dipende dai costi dei percorsi Cod; in termini vettoriali:
F = P(C) d
noto il vettore F dei flussi di percorso, il vettore f dei flussi di arco si calcola
come:
f=AF
qquindi l’espressione
p
del modello di assegnazione
g
è:
f = A F = A P (C) d = A P(ATc) d
Introduzione del corso
reti congestionate e reti non congestionate
 una rete si dice
 non congestionata se il vettore dei costi di arco è costante
c = cost
 congestionata se il vettore dei costi di arco dipende dal vettore dei
f dei
d i fl
flussii di arco
c = c(f)
 nel caso di reti non congestionate i modelli di assegnazione si chiamano
modelli di carico della rete, in inglese Network Loading Models
(NL)
 nel casi di reti congestionate
g
i modelli di assegnazione
g
si chiamano
modelli di equilibrio dell’utente, in inglese User Equilibrium
Models (UE)
Introduzione del corso
reti non congestionate (modelli di carico della rete)
c = cost
 il modello di scelta del percorso può essere
1. deterministico
2. stocastico
 nel primo caso solo il percorso di costo minimo è scelto (p=1),
tutti ggli altri restano scarichi (p
(p=0))
 nel secondo caso ogni percorso viene scelto con probabilità
diversa in funzione dell
dell’utilità
utilità associata a ciascun percorso
Introduzione del corso
modello di carico della rete a
costi costanti (Network
Loading)
c
d
A
P(C)
Introduzione del corso
modello di carico della rete deterministico (DNL)
assegnazione “tutto
tutto o niente
niente” AoN
Introduzione del corso
modello di carico della rete deterministico (DNL)
assegnazione “tutto o niente” AoN
1-4
f
0
1000
0
1500
1800
=
3-4
2-4
1
2
3
4
5
6
1
0
1
0
1
1
0
0
1
0
0
1
0
0
1
0
0
1
0
1
0
0
0
1
0
0
0
0
0
1
VETTORE
FLUSSI
SS DI
ARCO
F
0
0
1000
0
1500
800
VETTORE
FLUSSI DI
PERCORSO
Introduzione del corso
modello di carico della rete deterministico (DNL)
assegnazione “tutto o niente” AoN
FLUSSI DI PERCORSO
2
2
d_14 = 1000
0
0
1
0
2
0
1
2
3
4 1
4
1
1000
0
3
1000
3
d 24 = 1500
2
3
2
1500
4
2
5
0
1
4
0
1
4
1500
3
2
0
1
0
3
d_34 = 800
1000
FLUSSI DI
ARCO
1800
3
1-4
6
4
1
800
f
0
1000
0
1500
1800
=
Introduzione del corso
3
4
2-4
3-4
1
2
3
4
5
6
1
0
1
0
1
1
0
0
1
0
0
1
0
0
1
0
0
1
0
1
0
0
0
1
0
0
0
0
0
1
F
0
0
1000
0
1500
800
modello di carico della rete stocastico (SNL)
Introduzione del corso
modello di carico della rete stocastico (SNL)
1-4
f
133
867
195
1439
1861
=
2-4
3-4
1
2
3
4
5
6
1
0
1
0
1
1
0
0
1
0
0
1
0
0
1
0
0
1
0
1
0
0
0
1
0
0
0
0
0
1
Introduzione del corso
F
16
117
867
179
1321
800
modello di carico della rete
stocastico (SNL)
FLUSSI DI PERCORSO
2
2
d_14 = 1000
117
16
1
117
2
16
1
2
4
3
1
4
1
867
16
3
2
4
867
3
2
d 24 = 1500
3
2
1321
4
1
133
5
179
4
1
1439
4
195
1
4
179
867
3
2
3
d_34 = 800
6
4
1
800
3
1861
FLUSSI DI
ARCO
1
f
133
1
867
=
0
195
1
1439
0
1861
1
Introduzione del corso
3
1-4
2-4
3-4
2
3
4
5
6
1
0
0
1
0
0
1
0
0
1
0
0
1
0
1
0
0
0
1
0
0
0
0
0
1
F
16
117
867
179
1321
800
reti congestionate (modelli di equilibrio UE)
c = c(f)
 anche in questo caso possiamo avere modelli deterministici o
modelli stocastici
 nel caso di modelli di equilibrio deterministici nessun utente
può migliorare il costo di viaggio, modificando unilateralmente
ill suo percorso
 nel caso di modelli di equilibrio stocastici nessun utente può
migliorare il costo di viaggio percepito,
percepito modificando
unilateralmente il suo percorso
 Il costo percepito in generale è differente dal costo che gli
utenti riscontrano sulla rete dopo la scelta, per effetto degli
spostamenti degli utenti da un percorso ad un altro.
Introduzione del corso
reti congestionate (modelli di equilibrio UE)
 Il sistema evolve fino a quando gli utenti riscontrano sulla rete proprio i costi
in base
b ai qualil hhanno scelto.
l
 Pertanto la condizione di equilibrio genera la particolare configurazione di
flussi cui corrispondono
p
dei costi di arco che generano
g
dei costi percepiti
p
p di
percorso che l’utente poi riscontra effettivamente sulla rete.
 Questa condizione può essere espressa matematicamente come un problema
di punto fisso.
fisso
Introduzione del corso
modelli di equilibrio a costi non costanti (UE)
c(f)
c
d
A
P(C)
Introduzione del corso
Introduzione del corso
introduzione al problema dell’equilibrio
Introduzione del corso
introduzione
t odu o e al
a problema
p ob e a dell’equilibrio
de equ b o
Introduzione del corso
algoritmo delle Medie Mobili Successive (MSA) per la soluzione del problema
di equilibrio
Introduzione del corso
esempio
p di MSA
f
 

 p ik cik f i k 1  d od
k
SNL
 

p ik cik f i k 1 
  0.02
e  c1
e   ci
 e  c 2  e  c 3
Introduzione del corso
note sui modelli stocastici di carico della rete (SNL)
 una delle ragioni pratiche per l’uso di modelli stocastici di carico della
rete di tipo è la sensibilità dei flussi, nei modelli deterministici, a
piccoli
i li cambiamenti
bi
i nella
ll rete
 chiariamo con un esempio di una rete con una coppia OD, due
percorsi ed una domanda d
•
D
percorso 2
f1 = 0;
f2 = d
anche per Δt→0, cioè tempi quasi uguali
percorso 1
O
se c1=c2+Δt, si ha
•
se d’altra parte si commettesse un piccolo errore nel
calcolo dei tempi potrebbe aversi
•
c1<c2
•
i modelli stocastici evitano questi problemi e forniscono,
nel caso di ppiccole differenze di costi, flussi vicino al 50%
in entrambi i casi
•
una piccola variazione di costo determina una piccola
variazione
i i
d i flussi
dei
fl i (più
( iù o meno a seconda
d della
d ll
varianza della distribuzione del tempo percepito, che
Introduzione del corso
varia
da caso a caso)
f1 = d;
f2 = 0