Modelli di assegnazione

(1)

1

Modelli di assegnazione Modelli di assegnazione

PROGETTAZIONE DEI SISTEMI DI TRASPORTO

prof. ing. Agostino Nuzzolo ottobre 2005

(2)

2

Struttura del sistema di modelli per la simulazione dei sistemi di trasporto

MODELLO DEL SISTEMA DI TRASPORTO

OFFERTA DI INFRASTRUTTURE

E SERVIZI DI TRASPORTO

MODELLO DI LOCALIZZAZIONE E LIVELLO DELLE ATTIVITA’

SISTEMI DELLE ATTIVITA’

Attributi di livello di servizio

(tempi, costi)

MODELLI DI ASSEGNAZIONE

MODELLO DI DOMANDA MODELLO DI

DOMANDA

MATRICI O/D

Funzioni di prestazione MODELLO DI

OFFERTA Reti di trasporto MODELLO DI

OFFERTA Reti di trasporto

Flussi

Valutazione effetti

(3)

3

Definizioni ed ipotesi

Relazione tra costi d’arco e costi di percorso

Detti:

o nodo (zona) origine dello spostamento;

d nodo (zona) destinazione dello spostamento;

od coppia Origine-Destinazione;

I_od insieme dei percorsi rilevanti per gli utenti della coppia od A matrice di incidenza archi-percorsi complessiva

c vettore dei costi di arco, c_l;

C vettore complessivo dei costi di percorso, formato dai vettori dei costi di percorso C_od relativi a ciascuna coppia od;

sarà:

C = A

^T

c

(4)

4

Relazione tra costi d’arco e costi di percorso ^{C = A}

^T

^c

1

2

3

4

GRAFO PERCORSI

3 6 4

4 2

3 4 1

2

3 1 4

2

5 4 1

2

2 4

3

1 3 4

1

2

3

4

G≡ (N,L) 5

N≡{(1,2,3,4)}

L≡{(1,2),(1,3),(2,3),(2,4),(3,4)}

Centroidi origine {1,2,3}Centroide destinazione {4}

⎥⎥

⎥

⎦

⎤

⎢⎢

⎢

⎣

⎡

+ + +

+ +

=

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

⋅

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

⋅

=

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

34 24

34 23

34 13

24 12

34 23

12

5 4 3 2 1

6 5 4 3 2 1

1 0 0 0 0

0 1 0 0 0

1 0 1 0 0

1 0 0 1 0

0 1 0 0 1

1 0 1 0 1

cc

c c

c

c c c c c c

A C

C C C C C C

C ^ADD ^T

1 0 1 1 0 1 ) 4 , 3 ( 5

0 1 0 0 1 0 ) 4 , 2 ( 4

0 0 1 0 0 1 ) 3 , 2 ( 3

0 0 0 1 0 0 ) 3 , 1 ( 2

0 0 0 0 1 1 ) 2 , 1 ( 1

6 5 4 3 2 1

= A

Definizioni ed ipotesi

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

⋅

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

1 2 3 1 2

1 0 0 0 0

0 1 0 0 0

1 0 1 0 0

1 0 0 1 0

0 1 0 0 1

1 0 1 0 1

1 2 4 2 4 6

C = A^T c

(5)

5

Definizioni ed ipotesi

Detti:

f vettore dei flussi di arco, f_l;

F vettore complessivo dei flussi di percorso, formato dai vettori dei flussi di percorso F_od relativi a ciascuna coppia od;

sarà:

f = A F

Relazione tra flussi d’arco e flussi di percorso

(6)

6

Relazione tra flussi d’arco e flussi di percorso f = A F

1

2

3

4

GRAFO PERCORSI

3 6 4

4 2

3 4 1

2

3 1 4

2

5 4 1

2

2 4

3

1 3 4

1

2

3

4

G≡ (N,L) 5

N≡{(1,2,3,4)}

L≡{(1,2),(1,3),(2,3),(2,4),(3,4)}

Centroidi origine {1,2,3}Centroide destinazione {4}

1 0 1 1 0 1 ) 4 , 3 ( 5

0 1 0 0 1 0 ) 4 , 2 ( 4

0 0 1 0 0 1 ) 3 , 2 ( 3

0 0 0 1 0 0 ) 3 , 1 ( 2

0 0 0 0 1 1 ) 2 , 1 ( 1

6 5 4 3 2 1

= A

Definizioni ed ipotesi

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

⋅

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

⋅

=

800 1321

179 867 117 16

1 0 1 1 0 1

0 1 0 0 1 0

0 0 1 0 0 1

0 0 0 1 0 0

0 0 0 0 1 1

1861 1439 195 867 133

F A

f

(7)

7

Il modello di scelta del percorso

Comportamento di scelta del percorso

p[k/od] = Prob[- C_k + C_j ≥ ε_j - ε_k ∀ j ^Є I_od] ∀ od,k

Modello di utilità deterministica Modello di utilità stocastica

= 0

ε ε ≠ 0

(8)

8

Il modello di scelta del percorso

p

_od

= p

_od

(-C

_od

) ∀ od P = P(-C)

p

_od

vettore delle probabilità di scelta dei percorsi che collegano l’origine o con la destinazione d;

P matrice delle probabilità di scelta dei percorsi, con una colonna per ciascuna coppia od e una riga per ciascun percorso k;

l’elemento generico è dato da p[k/od] se il percorso k collega la

coppia od, altrimenti è nullo.

(9)

9

Il modello di assegnazione

F

_k

= d

_od

p[k/od]

F = P (-C) d

f = A F = A P (-C) d = A P (-A

^T

c) d

k = percorso che connette l’origine o e la destinazione d;

F_k = flusso di percorso relativo al percorso k;

d_od = flusso di domanda della coppia od;

F = vettore dei flussi di percorso;

P = matrice delle probabilità di scelta dei percorsi;

C = vettore dei costi di percorso;

d = vettore di domanda;

f = vettore dei flussi di arco;

A = matrice d’incidenza archi-percorsi;

c = vettore dei costi d’arco.

(10)

10

Classificazione dei modelli di assegnazione

SUE equilibrio DUE

c = c(f)

SNL DNL (AoN)

c = cost

Stocastico Deterministico

Modello di scelta del percorso MODELLI DI ASSEGNAZIONE

DNL = Deterministic Network Loading AoN = All or Nothing

SNL = Stochastic Network Loading DUE = Deterministic User Equilibrium SUE = Stochastic User Equilibrium

(11)

11

Modelli di carico della rete con costi costanti

MODELLO DI CARICO DELLA RETE

FLUSSI DI DOMANDA COSTI DI

ARCO

COSTI DI PERCORSO

MODELLO DI SCELTA DEL PERCORSO

PROBABILITA' DI SCELTA DEL PERCORSO FLUSSI DI

PERCORSO FLUSSI DI

ARCO

INCIDENZA ARCHI PERCORSI

X

(12)

12

( )

(

^od,k

)

od,k

n od,n

6

4

exp C

2 p

4 exp C

2 1

⎡ ⎤⎢ ⎥

⎢ ⎥ −

= ⎢ ⎥⎢ ⎥ =

⎢ ⎥ −

⎢ ⎥⎢ ⎥

⎢ ⎥⎣ ⎦ C

∑

[

1.000

]

p 881 ; . 0

119 . p 0

; 867 . 0

117 . 0

016 . 0

p₁₄ ₂₄ ⎥ ₃₄ =

⎦

⎢ ⎤

⎣

= ⎡

⎥⎥

⎥

⎦

⎤

⎢⎢

⎢

⎣

⎡

=

Percorsi Coppie

O-D

1.000 0

0 6

0 0.881

0 5

0 0.119

0 4

0 0

0.867 3

0 0

0.117 2

0 0

0.016 1

3-4 2-4

1-4

⎥⎥

⎥

⎦

⎤

⎢⎢

⎢

⎣

⎡

⋅

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡ = ⋅

800 1500 1000

000 . 1 0

0

0 881

. 0 0

0 119

. 0 0

0 0

867 . 0

0 0

117 . 0

0 0

016 . 0

800 1321

179 867 117 16

d P

F

Modelli di assegnazione SNL

Calcolo dei flussi di percorso

HP: modello di scelta del percorso stocastico.

HP: costi di arco costanti.

(13)

13

Modelli di assegnazione SNL

Calcolo dei flussi di arco

f

_NL

= f

_NL

(c; d) = A P(-A

^T

c) d ∀ ^c

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

⋅

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

800 1321

179 867 117 16

1 0 1 1 0 1

0 1 0 0 1 0

0 0 1 0 0 1

0 0 0 1 0 0

0 0 0 0 1 1

1861 1439 195 867 133

f = A · F

(14)

14

d_1-4 = 1000

16

16 16

3 2

1 4

2

1 4

117 117

3

1 4

867 867

d_2-4 = 1500

1

3 2

179 4

179 2

4 1321

d_3-4 = 800

3 2

1 4

800

Flussi di arco

3 2

1 4

867 1861

195 1439 133

Modelli di assegnazione SNL

(15)

15

[ ]1

1 ; 0

; 1 0 0

1 2 4 2 4 6

34 24

14 ⎥ =

⎦

⎢ ⎤

⎣

= ⎡

⎥⎥

⎥

⎦

⎤

⎢⎢

⎢

⎣

⎡

=

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

= p p p

C

1 0

0 6

0 1

0 5

0 0

0 4

0 0

1 3

0 0

0 2

0 0

0 1

3-4 2-4

1-4 Percorsi

Coppie O-D

⎥⎥

⎥

⎦

⎤

⎢⎢

⎢

⎣

⎡

⋅

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡ = ⋅

800 1500 1000

1 0 0

0 1 0

0 0 0

0 0 1

0 0 0

800 1500

0 1000

0 0

d P

F

Modelli di assegnazione DNL (AoN)

Calcolo dei flussi di percorso

HP: modello di scelta del percorso deterministico.

HP: costi di arco costanti.

(16)

16

f

_NL

= f

_NL

(c; d) = A P(A

^T

c) d ∀ c

Modelli di assegnazione DNL (AoN)

Calcolo dei flussi di arco

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

⋅

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

800 1500

0 1000

0 0

1 0 1 1 0 1

0 1 0 0 1 0

0 0 1 0 0 1

0 0 0 1 0 0

0 0 0 0 1 1

1800 1500

0 1000

0

f = A · F

(17)

17

d_1-4 = 1000

0

0 0

3 2

1 4

2

1 4

0 0

3

1 4

1000 1000

d_2-4 = 1500

1

3 2

0 4

0 2

4 1500

d_3-4 = 800

3 2

1 4

800

Flussi di arco

3 2

1 4

1000 1800

0 1500 0

Modelli di assegnazione DNL (AoN)

(18)

18

Classificazione dei modelli di assegnazione

SUE equilibrio DUE

c = c(f)

SNL DNL (AoN)

c = cost

Stocastico Deterministico

Modello di scelta del percorso MODELLI DI ASSEGNAZIONE

DNL = Deterministic Network Loading AoN = All or Nothing

SNL = Stochastic Network Loading DUE = Deterministic User Equilibrium SUE = Stochastic User Equilibrium

(19)

19

Modelli di assegnazione all’equilibrio con c = c(f)

MODELLO DI CARICO DELLA RETE

FLUSSI DI DOMANDA COSTI DI

ARCO

COSTI DI PERCORSO

MODELLO DI SCELTA DEL PERCORSO

PROBABILITA' DI SCELTA DEL PERCORSO FLUSSI DI

PERCORSO

FLUSSI DI ARCO

INCIDENZA ARCHI PERCORSI

X

FUNZIONI DI COSTO-FLUSSO

(20)

20

Introduzione al problema dell’equilibrio

Esempio

o d

1

2

h veic

d

od =100

0 10 20 30 40 50 60 70 80 90 100

0 20 40 60 80 100 f1

c1

0 10 20 30 40 50 60 70 80 90 100

0 20 40 60 80 100 f2

c2

( ) f f

c

1 ₁ = 30+0.5× ₁

( ) f f

c

₂ ₂ ⁼ ⁵⁰⁺⁰^.⁵^× ₂

(21)

21

Introduzione al problema dell’equilibrio

Esempio

55 10

75 90

50 0

80 50 30 100

2 2

1 1

2 2

1 1

=

→

= → =

=−−→−−−−−=−− −−

= → = + =

=

C

ff C

C

ff C

65 30

65 70

2 2

1

1 = → =

=

→

∗ =

∗

C f

c

0 10 20 30 40 50 60 70 80 90 100

0 20 40 60 80 100

c1 c2

f1

40 20 0

60 80 100

f2

70

30

c

L’evoluzione si arresta in condizioni di equilibrio.

(22)

22

Durante la fase di evoluzione del sistema, gli utenti si spostano sulla rete scegliendo percorsi di minimo costo percepito , che in generale è differente dal costo che essi riscontrano sulla rete dopo la scelta, per effetto degli spostamenti degli utenti da un percorso ad un altro.

Il sistema evolve fino a quando gli utenti riscontrano sulla rete proprio i costi in base ai quali hanno scelto. Pertanto la condizione di equilibrio genera la particolare configurazione di flussi cui corrispondono dei costi di arco che generano dei costi percepiti di percorso che l’utente poi riscontra effettivamente sulla rete.

Questa condizione può essere espressa matematicamente come un problema di punto fisso.

Condizioni di equilibrio stocastico

Cˆk

**f* = A P [ A**

^T

**c( f*) ] d**

Cˆk

Modelli di assegnazione

Modelli di assegnazione Modelli di assegnazione

PROGETTAZIONE DEI SISTEMI DI TRASPORTO

Struttura del sistema di modelli per la simulazione dei sistemi di trasporto

Definizioni ed ipotesi

Relazione tra costi d’arco e costi di percorso

C = A

c

Relazione tra costi d’arco e costi di percorso C = A

c

Definizioni ed ipotesi

Definizioni ed ipotesi

f = A F

Relazione tra flussi d’arco e flussi di percorso

Relazione tra flussi d’arco e flussi di percorso f = A F

Definizioni ed ipotesi

Il modello di scelta del percorso

= 0

ε ε ≠ 0

Il modello di scelta del percorso

p

= p

(-C

) ∀ od P = P(-C)

p

vettore delle probabilità di scelta dei percorsi che collegano l’origine o con la destinazione d;

P matrice delle probabilità di scelta dei percorsi, con una colonna per ciascuna coppia od e una riga per ciascun percorso k;

l’elemento generico è dato da p[k/od] se il percorso k collega la

coppia od, altrimenti è nullo.

Il modello di assegnazione

F

= d

p[k/od]

F = P (-C) d

f = A F = A P (-C) d = A P (-A

c) d

Classificazione dei modelli di assegnazione

Modelli di carico della rete con costi costanti

( )

(

)

∑

[

]

Modelli di assegnazione SNL

Calcolo dei flussi di percorso

Modelli di assegnazione SNL

Calcolo dei flussi di arco

f

= f

(c; d) = A P(-A

c) d ∀ c

Modelli di assegnazione SNL

Modelli di assegnazione DNL (AoN)

Calcolo dei flussi di percorso

f

= f

(c; d) = A P(A

c) d ∀ c

Modelli di assegnazione DNL (AoN)

Calcolo dei flussi di arco

Modelli di assegnazione DNL (AoN)

Classificazione dei modelli di assegnazione

Modelli di assegnazione all’equilibrio con c = c(f)

Introduzione al problema dell’equilibrio

Esempio

d

( ) f f

c

( ) f f

c

Introduzione al problema dell’equilibrio

Esempio

L’evoluzione si arresta in condizioni di equilibrio.

Condizioni di equilibrio stocastico

f* = A P [ A

c( f*) ] d

Relazione tra costi d’arco e costi di percorso ^{C = A}

^c

c) d ∀ ^c

**f* = A P [ A**

**c( f*) ] d**