Paradoks Braessa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Paradoks Braessatwierdzenie matematyczne orzekające, że w pewnym modelu ruchu drogowego czasy podróży pojazdów mogą ulec wydłużeniu po dodaniu do sieci drogowej nowego połączenia. Autorem twierdzenia jest niemiecki matematyk Dietrich Braess[1].

Model ruchu drogowego[edytuj | edytuj kod]

Model ruchu drogowego w paradoksie Braessa ma następujące cechy:

  1. Sieć drogowa składa się ze skończenie wielu węzłów i łączących je odcinków dróg
  2. Po sieci porusza się skończenie wiele pojazdów, każdy z nich ma wyznaczony węzeł startowy i węzeł docelowy
  3. Odcinki dróg mają przypisane sobie czasy przejazdu, przy czym czasy te mogą zależeć od liczby pokonujących dany odcinek pojazdów.
  4. Układ sieci drogowej i czasy przejazdu poszczególnych odcinków są znane pojazdom
  5. Celem pojazdów jest przejazd przez sieć z węzłów początkowych do docelowych po trasie złożonej z odcinków drogowych tak, by zminimalizować łączny czas ich pokonania
  6. Decyzje o wyborze tras pojazdy podejmują indywidualnie i niezależnie od siebie

Sformułowanie w teorii gier[edytuj | edytuj kod]

Przy powyższych założeniach problem wyborów tras przez pojazdy może być badany w ramach teorii gier. Każdemu konkretnemu układowi dróg, pojazdów i ich punktów startowych i docelowych odpowiada gra wieloosobowa:

  • Gracze to poszczególne pojazdy
  • Strategie dostępne graczowi to wszystkie możliwe trasy złożone z odcinków drogowych łączące jego węzeł początkowy z docelowym
  • Wypłata gracza to łączny czas przejazdu całej wybranej przez niego trasy; zależy on także od tras wybranych przez inne pojazdy (założenie 3)
  • Gracze dążą do minimalizacji swojej wypłaty (założenie 5)
  • Wypłaty we wszystkich możliwych układach decyzji wszystkich graczy są znane im wszystkim (założenie 4)

W tym ujęciu czasy podróży poszczególnych pojazdów to wypłaty graczy w równowadze Nasha gry odpowiadającej danemu układowi dróg, ich czasów przejazdu, pojazdów i ich węzłów startowych i docelowych. Zgodnie z definicją, w tej równowadze zmiana strategii przez dowolnego gracza, przy niezmienionych decyzjach pozostałych graczy, powoduje zwiększenie się jego wypłaty.

Paradoks Braessa można teraz sformułować następująco:

Istnieje układ drogowy U
oraz istnieje układ drogowy V uzyskany z U przez dodanie jednego odcinka drogowego,
takie, że w grze odpowiadającej V czasy przejazdu wszystkich pojazdów w równowadze Nasha są większe niż w równowadze Nasha gry uzyskanej z U.

Przykład[edytuj | edytuj kod]

Poniższy przykład pochodzi z oryginalnego artykułu Dietricha Braessa[1]. Został opisany w mniej formalnej terminologii.

Wyjściowy układ drogowy[edytuj | edytuj kod]

Wyjściowy układ drogowy z autostradami AX i YB oraz drogami lokalnymi AY i XB

Sieć drogowa i auta[edytuj | edytuj kod]

Przykład sytuacji, w której ujawnia się paradoks Braessa jest skonstruowany z czterech miast A, B, X i Y. Są one połączone odcinkami drogowymi jak na rysunku i z następującymi czasami przejazdu, przy czym p oznacza gęstość ruchu w tysiącach aut.

  • z A do X prowadzi autostrada AX z czasem przejazdu t_{AX}(p) =  50 + p minut
  • z Y do B prowadzi autostrada YB z czasem przejazdu t_{YB}(p) =  50 + p minut
  • z X do B prowadzi droga lokalna XB z czasem przejazdu t_{XB}(p) =  10p minut
  • z A do Y prowadzi droga lokalna AY z czasem przejazdu t_{AY}(p) =  10p minut

Aut jest 6000 i wszystkie mają za zadanie przejechać trasę z A do B.

Analiza równowagi Nasha[edytuj | edytuj kod]

Każde auto musi zdecydować się na wybór trasy albo AXB albo AYB.

Równowaga Nasha to taka sytuacja, w której każdy z samochodów spowoduje wydłużenie swojego czasu jazdy, zmieniając decyzję co do wyboru trasy przy niezmienionych decyzjach pozostałych aut. Taka sytuacja występuje wówczas, gdy każdą z dwóch dostępnych tras pokonuje się w tym samym czasie, bo wtedy zmieniający decyzję kierowca powoduje zwiększenie czasu jazdy na trasie, na którą się przeniósł, czyli traci na zmianie. Jeśli p i q to liczby aut w tysiącach pokonujących odpowiednio trasy AXB i AYB, otrzymujmy równania:

p+q=6
t_{AX}(p)+t_{XB}(p)= t_{AY}(q)+t_{YB}(q)

czyli

p+q=6
50+p+10p= 10q+50+q

których rozwiązaniem jest p=q=3.

Przy tej gęstości ruchu pokonanie obu dostępnych tras zabiera 50+3+30=83 minuty.

Uzupełniony układ drogowy[edytuj | edytuj kod]

Układ drogowy po dodaniu jednokierunkowej autostrady YX

Sieć drogowa i auta[edytuj | edytuj kod]

Do wyjściowego układu drogowego dodana zostaje droga:

  • jednokierunkowa autostrada z Y do X z czasem przejazdu t_{YX}(p) =  10 + p minut

Aut jest nadal 6000 i wszystkie mają za zadanie przejechać trasę z A do B.

Analiza równowagi Nasha[edytuj | edytuj kod]

Tym razem każde auto musi zdecydować się na wybór jednej z tras: AXB, AYB albo AYXB. Analogicznie jak poprzednio, równowaga Nasha to sytuacja, gdy przejazd każdą z dostępnych tras zabiera tyle samo czasu. Jeśli p, q i r to liczby aut w tysiącach pokonujących odpowiednio trasy AXB, AYB i AYXB, otrzymujmy równania:

p+q+r=6
t_{AX}(p)+t_{XB}(p+r)=t_{AY}(q+r)+t_{YB}(q)=t_{AY}(q+r)+t_{YX}(r)+t_{XB}(p+r)

czyli

p+q+r=6
50+p+10(p+r)= 10(q+r)+50+q=10(q+r)+ 10+r+10(p+r)

których rozwiązaniem jest p=q=r=2. Czas przejazdu każdej z tych dróg wynosi wówczas 50+2+10(2+2)=92 minuty.

Założenie jednokierunkowości YX[edytuj | edytuj kod]

Po obliczeniu czasu jazdy w stanie równowagi można stwierdzić, że założenie o jednokierunkowości autostrady YX jest nieistotne. Najkrótszy możliwy czas przejazdu trasą autostradową AXYB wynosi ponad 110 minut — ponad 50 minut na każdym z odcinków AX i YB oraz ponad 10 minut na XY. Zatem w stanie równowagi Nasha żaden samochód nie wybrałby tego wariantu.

Wyjaśnienie intuicyjne[edytuj | edytuj kod]

Wąskim gardłem systemu są drogi lokalne, na których czas przejazdu bardzo szybko wzrasta wraz z intensywnością ruchu. Po pojawieniu się dodatkowej drogi dostępna staje się nowa trasa, prowadząca oprócz nowego skrótu YX tylko drogami lokalnymi.

Z perspektywy pojedynczego pojazdu, dopóki nową trasą AYXB jeździ mniej aut niż trasami AXB i AYB, kierowca zmieniający trasę na AYXB oszczędza trochę czasu sobie i tym, którzy jadą autostradą, z której użycia zrezygnował, oraz powoduje stratę czasu u tych, którzy jadą drogą lokalną, na którą przeniósł się z autostrady. Ta strata jest 10 razy większa niż zysk w przeliczeniu na jeden samochód. Zatem z każdym kolejnym kierowcą decydującym się na AYXB sumaryczny czas przejazdu wszystkich kierowców rośnie. Ponieważ w stanie równowagi wszyscy kierowcy jadą równie długo a suma czasów podróży wzrosła, nowy stan równowagi jest mniej efektywny od starego.

Z perspektywy całości systemu nowy odcinek drogowy odciąża ruch na autostradach, gdzie jest to mało odczuwalne, a w zamian jeszcze bardziej zagęszcza ruch na drogach lokalnych, powodując wydłużenie czasu podróży.

Paradoks Braessa w sytuacjach rzeczywistych[edytuj | edytuj kod]

Znane są przykłady sytuacji, gdy w prawdziwym ruchu drogowym wystąpiły efekty przewidywane przez paradoks Braessa.

W 1969 w Stuttgarcie inwestycje drogowe w centrum doprowadziły do znacznego pogorszenia się warunków ruchu drogowego w okolicy Schlossplatz, czemu zaradzono dopiero zamykając dla ruchu kołowego fragment Königsstraße[2].

W Nowym Jorku w 1990 czasowe zamknięcie 42. Ulicy zwiększyło płynność ruchu w jej okolicy[3].

Wskazywano także na symptomy wystąpienia paradoksu Braessa na drogach Winnipeg[4].

Praca Rapoporta i in.[5] relacjonuje eksperymenty z uczestnikami biorącymi w warunkach laboratoryjnych udział w symulowanym ruchu drogowym. Eksperymentatorzy wywołali w nich paradoks Braessa.

Praca Youna i in.[6] przedstawia na ilustracji przewidywany w symulacjach efekt zamknięcia poszczególnych głównych ulic w trzech wielkich aglomeracjach: Nowego Jorku, Boston-Cambridge i Londynu. W każdej z nich są ulice, których zamknięcie miałoby negatywny wpływ na czasy przejazdu oraz ulice, których zamknięcie skróciłoby te czasy, czyli wywołało efekt przewidywany w paradoksie Braessa.

Istnieją także fizyczne analogi paradoksu Braessa. Prace Cohena i in.[7] oraz Penchiny i in.[8] opisują przykłady układów sprężyn i cięgieł podtrzymujących wiszący na nich ciężar, w których dodanie dodatkowego cięgła pomiędzy elementami układu powoduje opadnięcie ciężaru niżej. W tych samych pracach wskazano, że efekty analogiczne do paradoksu Braessa występują też w układach elektrycznych, hydraulicznych i przewodnictwa cieplnego, w których obowiązują pierwsze prawo Kirchhoffa i drugie prawo Kirchhoffa.

Zobacz też[edytuj | edytuj kod]

Przypisy

  1. 1,0 1,1 Dietrich Braess. Über ein Paradoxon aus der Verkehrsplanung. „Unternehmensforschung”. 12, s. 258–268, 1968 (niem.). 
  2. Wolfgang Blum. Ewig lockt die Schnellstraße. „Süddeutsche Zeitung” (niem.). 
  3. G. Kolata. What if they closed 42nd Street and nobody noticed?. „New York Times”, 1990-12-25 (ang.). 
  4. C. Fisk, S. Pallotion. Empirical Evidence for Equilibrium Paradoxes With Implications for Optimal Planning Strategies. „Transportation Research”. 15A, s. 245–248, 1981 (ang.). 
  5. Amnon Rapoport, Tamar Kugler, Subhasish Dugar, Eyran J. Gisches. Choice of routes in congested traffic networks: Experimental tests of the Braess Paradox. „Games and Economic Behavior”. 65, s. 538–571, 2009 (ang.). 
  6. Hyejin Youn, Michael T. Gastner, Hawoong Jeong. Price of Anarchy in Transportation Networks: Efficiency and Optimality Control. „Physical Review Letters”. 101, 2008 (ang.). 
  7. Joel E. Cohen, Paul Horowitz. Paradoxical behaviour of mechanical and electrical networks. „Nature”. 352, s. 699-701, 1991-08-22 (ang.). 
  8. Claude M. Penchina, Leora J. Penchina. The Braess paradox in mechanical, traffic, and other networks. „American Journal of Physics”. 71. s. 479 (ang.).