1 O PARADOKSIE BRAESSA Zbigniew Świtalski Paweł Skałecki Wydział Matematyki, Informatyki i Ekonometrii Uniwersytet Zielonogórski Zakopane 2016

2 O PARADOKSIE BRAESSA 1. Sieci transportowe 2. Formalizmy 3. Paradoks Braessa 4. Wyniki symulacji

3 SIEĆ TRANSPORTOWA (DROGOWA) Graf zorientowany, acykliczny (bez cykli zorientowanych), o dokładnie jednym wierzchołku początkowym i dokładnie jednym wierzchołku końcowym

4 SIEĆ TRANSPORTOWA (DROGOWA) Graf zorientowany, acykliczny (bez cykli zorientowanych), o dokładnie jednym wierzchołku początkowym i dokładnie jednym wierzchołku końcowym S 1, S 2, …, S m – drogi (zorientowane) łączące wierzchołek początkowy z końcowym

5 SIEĆ TRANSPORTOWA (DROGOWA) Graf zorientowany, acykliczny (bez cykli zorientowanych), o dokładnie jednym wierzchołku początkowym i dokładnie jednym wierzchołku końcowym S 1, S 2, …, S m – drogi (zorientowane) łączące wierzchołek początkowy z końcowym Q – zadana wielkość przepływu przez sieć (np. strumień pojazdów wpływający do sieci = liczba pojazdów przejeżdżających w jednostce czasu przez sieć)

6 SIEĆ TRANSPORTOWA (DROGOWA) f k – przepływ wzdłuż drogi S k (liczba pojazdów przejeżdżających w jednostce czasu z wierzchołka początkowego do wierzchołka końcowego)

7 SIEĆ TRANSPORTOWA (DROGOWA) f k – przepływ wzdłuż drogi S k (liczba pojazdów przejeżdżających w jednostce czasu z wierzchołka początkowego do wierzchołka końcowego) Q = f 1 + f 2 + …+ f m

8 SIEĆ TRANSPORTOWA (DROGOWA) f k – przepływ wzdłuż drogi S k (liczba pojazdów przejeżdżających w jednostce czasu z wierzchołka początkowego do wierzchołka końcowego) Q = f 1 + f 2 + …+ f m f ij – przepływ wzdłuż łuku (i, j) (suma przepływów dla wszystkich dróg przechodzących przez łuk (i, j) )

9 PRZYKŁAD Drogi : S 1 : (1, 2, 4, 6) – przepływ f 1 S 2 : (1, 2, 5, 6) – przepływ f 2 S 3 : (1, 3, 5, 6) – przepływ f 3 Q = f 1 + f 2 + f 3

10 FORMALIZMY Definicja Q-siecią nazywamy trójkę (V, A, Q), gdzie V = {1, 2, …., n} (zbiór wierzchołków), A  V  V (zbiór łuków), Q ≥ 0 (przepływ przez sieć).

11 FORMALIZMY Definicja Q-siecią nazywamy trójkę (V, A, Q), gdzie V = {1, 2, …., n} (zbiór wierzchołków), A  V  V (zbiór łuków), Q ≥ 0 (przepływ przez sieć). Założenia 1.(V, A) jest grafem acyklicznym 2.ma dokładnie jeden wierzchołek początkowy 3.ma dokładnie jeden wierzcholek końcowy

12 FORMALIZMY Niech S = {S 1, S 2, …, S m } będzie zbiorem dróg zorientowanych łączących wierzchołek początkowy z końcowym w grafie (V, A)

13 FORMALIZMY Niech S = {S 1, S 2, …, S m } będzie zbiorem dróg zorientowanych łączących wierzchołek początkowy z końcowym w grafie (V, A) Definicja Q-przepływem w Q-sieci (V, A, Q) nazywamy ciąg (f 1, f 2, …, f m ) taki, że f 1 + f 2 + …+ f m = Q oraz f k ≥ 0,  k.

14 FORMALIZMY Niech (i, j)  A (łuk w sieci (V, A, Q)) Oznaczamy: D(i, j) = {k: (i, j)  S k } (zbiór numerów ścieżek przechodzących przez łuk (i, j) )

15 FORMALIZMY Niech (i, j)  A (łuk w sieci (V, A, Q)) Oznaczamy: D(i, j) = {k: (i, j)  S k } (zbiór numerów ścieżek przechodzących przez łuk (i, j) ) Definicja Dla dowolnego Q-przepływu (f 1, f 2, …, f m ) w Q-sieci (V, A, Q) określamy przepływ wzdłuż łuku (i, j) jako f ij =  k  D(i, j) f k

16 CZASY PRZEJAZDU Dla każdego łuku (i, j) w sieci (V, A, Q) określamy funkcję czasu t ij : R   R 

17 CZASY PRZEJAZDU Dla każdego łuku (i, j) w sieci (V, A, Q) określamy funkcję czasu t ij : R   R  t ij (x) – czas przejazdu odcinka (i, j), jeśli przepływ na tym odcinku jest równy x

18 CZASY PRZEJAZDU Dla każdego łuku (i, j) w sieci (V, A, Q) określamy funkcję czasu t ij : R   R  t ij (x) – czas przejazdu odcinka (i, j), jeśli przepływ na tym odcinku jest równy x Zakładamy, że funkcje t ij są niemalejące

19 CZASY PRZEJAZDU Definicja Załóżmy, że w Q-sieci (V, A, Q) określony jest Q-przepływ f = (f 1, f 2, …, f m ) oraz zadana jest rodzina funkcji czasu {t ij }. Czasem przejazdu ścieżki S k dla Q-przepływu f nazywamy liczbę T(f, S k ) =  (i, j)  Sk t ij (f ij )

20 PRZYKŁAD Niech t ij (x) = 5x + 20 dla dowolnego (i, j) Wówczas T(f, S 1 ) = 5(f 1 + f 2 ) + 20 + 5f 1 + 20 + 5f 1 + 20 = 15f 1 +5f 2 + 60

21 PRZEPŁYW OPTYMALNY Definicja Q-przepływ f = (f 1, f 2, …, f m ) jest optymalny, jeśli średni czas przejazdu przez dowolną ścieżkę przy Q-przepływie f jest nie większy niż średni czas przejazdu przez dowolną ścieżkę przy dowolnym innym Q-przepływie g, tzn. jeśli spełniona jest nierówność  k f k T(f, S k )   k g k T(g, S k )

22 PRZEPŁYW RÓWNOWAGI Definicja Q-przepływ f = (f 1, f 2, …, f m ) jest przepływem równowagi, jeśli T(f, S 1 ) = T(f, S 2 ) = … = T(f, S m )

23 PARADOKS BRAESSA Rozważamy sieć Funkcje czasu: t 12 (x) = t 34 (x) = x + 50 t 24 (x) = t 13 (x) = 10x

24 PARADOKS BRAESSA Przepływ równowagi dla Q = 6 f = (3, 3) jest przepływem równowagi T(f, S 1 ) = 3 + 50 + 10  3 = 83 T(f, S 2 ) = 3 + 50 + 10  3 = 83

25 PARADOKS BRAESSA f = (3, 3) jest też przepływem optymalnym  k f k T(f, S k ) = 3  83 + 3  83 = 498 (łatwo sprawdzić, że funkcja  k f k T(f, S k ) jest funkcją kwadratową jednej zmiennej f 1 (bo f 2 = 6 – f 1 ) osiągającą minimum dla f 1 = 3)

26 PARADOKS BRAESSA Wprowadzamy łuk (3, 2) z funkcją t 32 (x) = x + 10

27 PARADOKS BRAESSA Przepływ równowagi dla Q = 6 : f = (2, 2, 2) S 1 = (1, 2, 4), S 2 = (1, 3, 4), S 3 = (1, 3, 2, 4)

28 PARADOKS BRAESSA S 1 = (1, 2, 4), S 2 = (1, 3, 4), S 3 = (1, 3, 2, 4) T(f, S 1 ) = 2 + 50 + 10  4 = 92 T(f, S 2 ) = 10  4 + 2 + 50 = 92 T(f, S 3 ) = 10  4 + 2 + 10 + 10  4 = 92

29 PARADOKS BRAESSA S 1 = (1, 2, 4), S 2 = (1, 3, 4), S 3 = (1, 3, 2, 4) T(f, S 1 ) = 92T(f, S 2 ) = 92T(f, S 3 ) = 92 Przepływ optymalny g = (3, 3, 0) T(g, S 1 ) = 83 T(g, S 2 ) = 83T(g, S 3 ) = 70

30 PROBLEMY 1.Czy podobne paradoksy mogą się pojawiać w sieciach o innej strukturze i przy innych rodzajach funkcji czasu ?

31 PROBLEMY 1.Czy podobne paradoksy mogą się pojawiać w sieciach o innej strukturze i przy innych rodzajach funkcji czasu ? 2.W jaki sposób pojawienie się paradoksu typu Braessa zależy od struktury sieci i od rodzaju funkcji czasu ?

32 PROBLEMY 1.Czy podobne paradoksy mogą się pojawiać w sieciach o innej strukturze i przy innych rodzajach funkcji czasu ? 2.W jaki sposób pojawienie się paradoksu typu Braessa zależy od struktury sieci i od rodzaju funkcji czasu ? 3.Załóżmy, że mamy daną sieć transportową. Jakie jest prawdopodobieństwo tego, że przy losowym wyborze funkcji czasu (z pewnego zbioru możliwych funkcji) pojawi się w takiej sieci paradoks typu Braessa ?

33 EKSPERYMENTY NUMERYCZNE Dla klasycznej sieci Braessa (4 wierzchołki, 4 lub 5 łuków) rozważamy trzy rodzaje funkcji czasu: t x t =  x (L) t t =  x +  (A) x

34 EKSPERYMENTY NUMERYCZNE Funkcje sklejane (S)  x + , jeśli x ≥ PS t = , jeśli 0  x < PS t x  PS

35 EKSPERYMENTY NUMERYCZNE 1. Losujemy parametry , , PS, Q z przedziałów:   (1, 8) ;   (1, 11); PS  (0, 6); Q  [1, 5] (krok 0,2)

36 EKSPERYMENTY NUMERYCZNE 1. Losujemy parametry , , PS, Q z przedziałów:   (1, 8) ;   (1, 11); PS  (0, 6); Q  [1, 5] (krok 0,2) 2.Przeprowadzamy 6 rodzajów eksperymentów:

37 EKSPERYMENTY NUMERYCZNE 1. Losujemy parametry , , PS, Q z przedziałów:   (1, 8) ;   (1, 11); PS  (0, 6); Q  [1, 5] (krok 0,2) 2.Przeprowadzamy 6 rodzajów eksperymentów: I (S) – dla każdego łuku wybieramy losowo funkcję typu S, II (S/A) – funkcje S lub A, III (S/L) – funkcje S lub L, IV (S/A/L) – funkcje S lub A lub L, V (A) – funkcje A VI (A/L) – funkcje A lub L

38 EKSPERYMENTY NUMERYCZNE 3. Dla każdego rodzaju eksperymentu przeprowadzamy 375000 symulacji

39 EKSPERYMENTY NUMERYCZNE 3. Dla każdego rodzaju eksperymentu przeprowadzamy 375000 symulacji 4. W każdym przypadku metodą wyrównywania szukamy  -równowagi (czasy przejazdu na poszczególnych drogach różnią się nie więcej niż o  ). Przyjmujemy  = 0,001

40 EKSPERYMENTY NUMERYCZNE 3. Dla każdego rodzaju eksperymentu przeprowadzamy 375000 symulacji 4. W każdym przypadku metodą wyrównywania szukamy  -równowagi (czasy przejazdu na poszczególnych drogach różnią się nie więcej niż o  ). Przyjmujemy  = 0,001 5. Sprawdzamy w każdym przypadku, czy zachodzi paradoks Braessa

41 WYNIKI Rodzaj eksp.L. symul.  -równ. %PB% PB/  -równ. % I (S)37500035040,9325420,6872,54 II (S+A)375000177734,7495572,5553,77 III (S+L)375000242076,46124253,3151,32 IV (S+A+L)375000202885,41113493,0355,94 V (A)3750004101910,943761610,0391,70 VI (A+L)3750006174416,4794842,5315,36 Łącznie22500001685357,49829733,6949,23

42 WNIOSKI 1.W ok. 7,5 % przypadków znaleziono  -równowagę, a w ok. 3,7 % przypadków PB,

43 WNIOSKI 1.W ok. 7,5 % przypadków znaleziono  -równowagę, a w ok. 3,7 % przypadków PB, 2.Najwięcej  -równowag znaleziono dla przypadku VI (A+L) – wówczas najmniej prawdopodobny jest PB,

44 WNIOSKI 1.W ok. 7,5 % przypadków znaleziono  -równowagę, a w ok. 3,7 % przypadków PB, 2.Najwięcej  -równowag znaleziono dla przypadku VI (A+L) – wówczas najmniej prawdopodobny jest PB, 3.Najwięcej PB znaleziono dla przypadku V (A), wówczas PB jest bardzo prawdopodobny w przypadku istnienia równowagi,

45 WNIOSKI 1.W ok. 7,5 % przypadków znaleziono  -równowagę, a w ok. 3,7 % przypadków PB, 2.Najwięcej  -równowag znaleziono dla przypadku VI (A+L) – wówczas najmniej prawdopodobny jest PB, 3.Najwięcej PB znaleziono dla przypadku V (A), wówczas PB jest bardzo prawdopodobny w przypadku istnienia równowagi, 4.Najmniej  -równowag i najmniej PB znaleziono dla przypadku I (S)

46 OGÓLNE WNIOSKI KOŃCOWE 1. Jeśli w sieci Braessa mamy losowo wybrane funkcje czasu typu A, L lub S, to w około 3-4 % przypadków dochodzi do paradoksu Braessa,

47 OGÓLNE WNIOSKI KOŃCOWE 1. Jeśli w sieci Braessa mamy losowo wybrane funkcje czasu typu A, L lub S, to w około 3-4 % przypadków dochodzi do paradoksu Braessa, 2. Istnieje wiele przypadków, oprócz przypadku opisanego przez Braessa, również z funkcjami sklejanymi, w których zachodzi paradoks typu Braessa.