Paradoks Braessa
Paradoks Braessa – twierdzenie 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
Model ruchu drogowego w paradoksie Braessa ma następujące cechy:
- Sieć drogowa składa się ze skończenie wielu węzłów i łączących je odcinków dróg
- Po sieci porusza się skończenie wiele pojazdów, każdy z nich ma wyznaczony węzeł startowy i węzeł docelowy
- Odcinki dróg mają przypisane sobie czasy przejazdu, przy czym czasy te mogą zależeć od liczby pokonujących dany odcinek pojazdów.
- Układ sieci drogowej i czasy przejazdu poszczególnych odcinków są znane pojazdom
- 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
- Decyzje o wyborze tras pojazdy podejmują indywidualnie i niezależnie od siebie
Sformułowanie w teorii gier
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
- oraz istnieje układ drogowy uzyskany z przez dodanie jednego odcinka drogowego,
- takie, że w grze odpowiadającej czasy przejazdu wszystkich pojazdów w równowadze Nasha są większe niż w równowadze Nasha gry uzyskanej z
Przykład
Poniższy przykład pochodzi z oryginalnego artykułu Dietricha Braessa[1]. Został opisany w mniej formalnej terminologii.
Wyjściowy układ drogowy
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/bb/BraessParadox1.svg/220px-BraessParadox1.svg.png)
Sieć drogowa i auta
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 oznacza gęstość ruchu w tysiącach aut.
- z A do X prowadzi autostrada AX z czasem przejazdu minut
- z Y do B prowadzi autostrada YB z czasem przejazdu minut
- z X do B prowadzi droga lokalna XB z czasem przejazdu minut
- z A do Y prowadzi droga lokalna AY z czasem przejazdu minut
Aut jest 6000 i wszystkie mają za zadanie przejechać trasę z A do B.
Analiza równowagi Nasha
Każdy kierowca 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 i to liczby aut w tysiącach pokonujących odpowiednio trasy AXB i AYB, otrzymujmy równania:
czyli
których rozwiązaniem jest
Przy tej gęstości ruchu pokonanie obu dostępnych tras zabiera minuty.
Uzupełniony układ drogowy
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e6/BraessParadox2.svg/220px-BraessParadox2.svg.png)
Sieć drogowa i auta
Do wyjściowego układu drogowego dodana zostaje droga:
- jednokierunkowa autostrada z Y do X z czasem przejazdu minut
Aut jest nadal 6000 i wszystkie mają za zadanie przejechać trasę z A do B.
Analiza równowagi Nasha
Tym razem każdy kierowca 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 i to liczby aut w tysiącach pokonujących odpowiednio trasy AXB, AYB i AYXB, otrzymujmy równania:
czyli
których rozwiązaniem jest Czas przejazdu każdej z tych dróg wynosi wówczas minuty.
Założenie jednokierunkowości YX
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
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
Znane są przykłady sytuacji, gdy w prawdziwym ruchu drogowym wystąpiły efekty przewidywane przez paradoks Braessa. Wielokrotnie też były dyskutowane sytuacje, rzekomo negujące jego zasadność.
Warunki niewystępowania paradoksu Braessa
Przez kilkadziesiąt lat, utrwaliły się w literaturze reguły dotyczące sytuacji, gdy paradoksu Braessa nie zaobserwujemy[2]:
- Mała liczba pojazdów w ruchu (niski popyt na przestrzeń transportową)
- Bardzo duża liczba pojazdów w ruchu (bardzo wysoki popyt)
- Czas przejazdu poszczególnych odcinków jest stosunkowo mały (pomijalny) – paradoks występuje, lecz czas przejazdu nie ulegnie zmianie przy rozbudowie sieci transportowej.
Sytuacje i przykłady występowania paradoksu 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[3].
W Nowym Jorku w 1990 czasowe zamknięcie 42. Ulicy zwiększyło płynność ruchu w jej okolicy[4].
Wskazywano także na symptomy wystąpienia paradoksu Braessa na drogach Winnipeg[5].
Praca Rapoporta i in.[6] 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.[7] 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.
Analogi fizyczne paradoksu Braessa
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cc/Braess-Paradoxon_der_Mechanik.svg/220px-Braess-Paradoxon_der_Mechanik.svg.png)
Istnieją także fizyczne analogi paradoksu Braessa. Prace Cohena i in.[8] oraz Penchiny i in.[9] 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 albo ich analogie.
Zobacz też
- paradoks Downsa-Thomsona
Przypisy
- ↑ a b Dietrich Braess. Über ein Paradoxon aus der Verkehrsplanung. „Unternehmensforschung”. 12, s. 258–268, 1968. (niem.).
- ↑ JanJ. Paszkowski JanJ., RafałR. Kucharski RafałR., Paradoksy przepustowości miejskiej sieci drogowej i sposoby ich odwzorowania w modelu czterostadiowym, „Transport Miejski i Regionalny”, Stowarzyszenie Inżynierów i Techników Komunikacji Rzeczpospolitej Polskiej, październik 2017, s. 5-11, ISSN 1732-5153 [dostęp 2023-03-22] (pol.).
- ↑ Wolfgang Blum. Ewig lockt die Schnellstraße. „Süddeutsche Zeitung”, 2006-01-24. [dostęp 2011-11-20]. (niem.).
- ↑ G. Kolata. What if they closed 42nd Street and nobody noticed?. „New York Times”, 1990-12-25. [dostęp 2011-11-20]. (ang.).
- ↑ C. Fisk, S. Pallotion. Empirical Evidence for Equilibrium Paradoxes With Implications for Optimal Planning Strategies. „Transportation Research”. 15A, s. 245–248, 1981. (ang.).
- ↑ 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.).
- ↑ Hyejin Youn, Michael T. Gastner, Hawoong Jeong. Price of Anarchy in Transportation Networks: Efficiency and Optimality Control. „Physical Review Letters”. 101, 2008. [dostęp 2011-11-22]. (ang.).
- ↑ Joel E. Cohen, Paul Horowitz. Paradoxical behaviour of mechanical and electrical networks. „Nature”. 352, s. 699–701, 1991-08-22. (ang.).
- ↑ Claude M. Penchina, Leora J. Penchina. The Braess paradox in mechanical, traffic, and other networks. „American Journal of Physics”. 71, s. 479, 2003. (ang.).