Braess paradox

Från Wikipedia
Hoppa till: navigering, sök

Braess paradox säger att en tillagd länk i ett nätverk av förbindelser kan minska den totala framkomligheten i nätverket. Till exempel kan byggandet av en ny väg göra att den totala trafiksituationen försämras. Detta är för att alla bilister agerar rationellt, fast själviskt, och den resulterande Nash-jämvikten inte är optimal sett ur ett helhetspersepktiv.

Exempel[redigera | redigera wikitext]

Exempel

Betrakta ett nätverk av vägar som i bilden till höger. 4000 bilförare vill ta sig från START till END. Restiden från START till A är T/100, där T är antalet förare som väljer den vägen. Restiden från START till B är konstant 45 minuter.

Utan förbindelse mellan A och B[redigera | redigera wikitext]

Om det inte finns någon förbindelse mellan A och B är de två vägarna lika bra och förare som agerer rationellt kommer att fördela sig lika mellan de två alternativen. (Om de inte gör det finns det alltid några som tjänar på att byta). Varje väg kommer att få 2000 förare och restiden blir \tfrac{2000}{100} + 45 = 65 minuter.

Med förbindelse mellan A och B[redigera | redigera wikitext]

Om en snabb förbindelse (approximativt 0 minuter) byggs mellan A och B förändras situationen. Ingen förare kommer nu att välja vägen mellan START och B, eftersom sträckan START-A-B tar 40 minuter i värsta fall, vilket i vart fall är mindre än 45 minuter. Men när alla förare kommer till A står de återigen inför samma val: från A till END tar det alltid 45 minuter, medan sträckan A-B-END tar som mest 40 minuter. Följden blir att alla förare kommer att välja vägen START-A-B-END, vilken tar 40+40=80 minuter. Den nya, snabba, förbindelsen mellan A och B får alltså resultatet att situationen försämras för alla förare.

I praktiken[redigera | redigera wikitext]

Steinberg och Zangwill gav 1983 tillräckliga och nödvändiga villkor för att Braess paradox skall uppkomma i nätverk under vissa antaganden. De fann att paradoxen inträffar ungefär lika ofta som den inte gör det; deras resultat gäller slumpmässiga snarare än planerade nätverk och tillägg.

I Seoul observerades en förbättring av trafiken runt staden när en motorväg togs bort.[1] Trafikstiutationen i Stuttgart förbättrades inte, trots investeringar 1969, förrän en del av en nybyggd väg åter stängdes för trafik.[2] 1990 fick stängningen av den 42:a gatan i New York följden att trafiktätheten i området minskade.[3] Youn, Gastner och Jeong visade specifika leder i Boston, New York och London där detta skulle kunna inträffa och pekade ut vägar som skulle kunna stängas för att minska den förväntade restiden för samtliga resenärer.[4]

Noter[redigera | redigera wikitext]

  1. ^ Easley, D and Kleinberg, J: "Networks", page 71. Cornell Store Press, 2008
  2. ^ Knödel W (1969). Graphentheoretische Methoden und ihre Anwendungen. Springer-Verlag. Sid. 57–9. ISBN 9783540046684 
  3. ^ Kolata G (1990-12-25). ”What if They Closed 42d Street and Nobody Noticed?”. New York Times. http://query.nytimes.com/gst/fullpage.html?res=9C0CE7D81530F936A15751C1A966958260&scp=8&sq=&st=nyt. Läst 16 november 2008. 
  4. ^ Youn H, Gastner MT, Jeong H (2008). ”Price of anarchy in transportation networks: efficiency and optimality control”. Phys. Rev. Lett. "101" (12): ss. 128701. doi:10.1103/PhysRevLett.101.128701. PMID 18851419. http://arxiv.org/abs/0712.1598. 

Vidare läsning[redigera | redigera wikitext]

  • D. Braess, Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12, 258–268 (1969) [1] [2]
  • Katharina Belaga-Werbitzky: „Das Paradoxon von Braess in erweiterten Wheatstone-Netzen mit M/M/1-Bedienern“ ISBN 3-89959-123-2
  • A. D. Irvine. How Braess's Paradox Solves Newcomb's Problem. International Studies in Philosophy of Science, Vol. 7 (1993), no. 2, 145–164.
  • R. Steinberg och W.I. Zangwill. The Prevalence of Braess's Paradox. Transportation Science, Vol. 17 (1983), no. 3, 301–318.
  • T. Roughgarden. "The Price of Anarchy." MIT Press, Cambridge, MA, 2005.
  • Inducerad trafik, ett annat fenomen som innebär att den totala trafikmängden ofta ökar när nya vägar byggs. I Braess paradox är totala trafikmängden konstant.


Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, 6 juni 2010.