Braessův paradox

Technology

12 hours ago

Author

Braessův paradox připisovaný matematiku Dietrichu Braessovi je svým způsobem překvapivý jev týkající se toků v sítích: Totiž že pokud si pohybující se objekty volí sobecky a bez domluvy svou co nejlepší trasu, pak přidání cesty navíc může zhoršit celkový výkon. To je dáno tím, že Nashova rovnováha systému nepředstavuje nejlepší řešení z hlediska celkového výkonu systému.

V řeči silniční sítě lze paradox vyjádřit takto: „Nechť je pro každý uzel silniční sítě dán počet automobilů, které v něm začínají, a jejich cíle. Snažme se odhadnout rozložení provozu. +more Zda dá řidič té které silnici přednost, to ovšem nezávisí jen na kvalitě silnice jako takové, ale také na hustotě jejího provozu. Pokud se každý řidič rozhodne dát přednost té silnici, která pro něj samotného vypadá výhodně, pak celkový čas strávený řidiči na silnicích nemusí být nejmenší možný. Dokonce platí, že rozšíření sítě o další silnici může přinést nový rovnovážný stav, který situaci zhorší. “.

Nashova rovnováha odpovídá situaci, kdy žádný z řidičů nemůže situaci ve svém sobeckém zájmu svým rozhodnutím změnit. Naopak pokud není systém v Nashově rovnováze, pak alespoň jeden ze řidičů může svou soukromou situaci zlepšit změnou své trasy. +more V případě Braessova paradoxu budou řidiči pokračovat v měnění svých tras, dokud nedosáhnou Nashovy rovnováhy, a to bez ohledu na to, že se třeba bude situace celkově zhoršovat.

Příklad

Ilustrační příklad k Braessovu paradoxu Předpokládejme silniční síť naznačenou na obrázku, kde se čtyři tisíce automobilů snaží cestovat ze Startu do Cíle. +more Cestovní čas v minutách na silnici Start-A není konstantní, ale odpovídá počtu řidičů dělenému stem, cestovní čas na silnici Start-B je vždy 45 minut, stejné cestovní časy jsou na protilehlých silnicích.

Pokud by neexistovala čárkovaná silnice, pak by trasa přes A trvala \tfrac{A}{100} + 45 a trasa přes B by trvala \tfrac{B}{100} + 45. Dokud by se neustálila rovnováha, řidiči by se snažili měnit své trasy z delší na kratší. +more Rovnováhou je v tomto případě stav, kdy cesta oběma cestami trvá stejně, tedy kdy A = B = 2000 a obě cesty trvají \tfrac{2000}{100} + 45 = 65 minut.

Předpokládejme, že do systému byla přidána velmi rychlá zkratka, ona čárkovaná čára, jejíž projetí nezabere ani minutu. V takové situaci se budou řidiči snažit nejprve jet silnicí spojující Start s A, která zabere v nejhorším případě \tfrac{T}{100} = \tfrac{4000}{100} = 40 minut, zatímco silnice ze Startu do B zabere vždy 45 minut. +more Z bodu A pak je jistě nejlepší projet rychlou spojkou do B, neboť při rozhodování mezi silnicemi A-Cíl a B-Cíl platí stejný argument. Pokud takto pojedou všichni, pak jim celkový čas zabere \tfrac{4000}{100} + \tfrac{4000}{100} = 80 minut, což je horší než původních 65 minut. Žádný z řidičů navíc nemůže svou situaci sám o sobě zlepšit. Původní trasy Start-A-Cíl a Start-B-Cíl nyní trvají 85 minut.

Šance na výskyt v praxi

V roce 1983 našli Steinberg a Zangwill při reálných předpokladech nutné a postačující podmínky k vzniku Braessova paradoxu v běžné dopravní síti. Z jejich výsledků vyplývá, že k Braessovu paradoxu dojde zhruba v polovině případů - to se ovšem samozřejmě netýká situace, kdy jsou nové cesty přidávány promyšleně a je bráno v úvahu riziko Braessova paradoxu.

Příklady ze života

V jihokorejském Soulu došlo ke zrychlení provozu poté, co byla v rámci projektu Čchŏnggječchŏn odstraněna rychlostní silnice. V Stuttgartu v Německu se po investicích do silniční sítě v roce 1969 dopravní situace nezlepšila, dokud nebyla část nově postavené silnice opět uzavřena.

V roce 1990 způsobilo uzavření 42. ulice v New Yorku snížení míry zácpy v oblasti, což mohlo být také případem Braessova paradoxu.