Направо към съдържанието

Парадокс на Браас

от Уикипедия, свободната енциклопедия

Парадоксът на Браас е явление, при което добавянето на нова връзка в дадена мрежа може да доведе до влошаване на пропускливостта на цялата (или голяма част) от мрежата. Парадоксът е открит от германския математик Дитрих Браас през 1968 г.

В първоначалния си труд[1][2] Браас изследва парадоксалната ситуация, при която изграждането на нова улица (т.е. локално увеличение на капацитета на една мрежа) води до удължено време на пътуване за всички участници в движението (т.е. капацитетът на мрежата се намалява). Приема се, че всеки участник в движението избира маршрута си така, че да няма друг маршрут с по-кратко време за пътуване.

Откритие и определение

[редактиране | редактиране на кода]

През 1968 г. Дитрих Браас, математик в Рурския университет в Германия, занимаващ се с моделиране на трафика, забелязва, че потокът в една пътна мрежа може да бъде забавен от добавянето на нов път към нея. Прозрението на Браас било, че ако всеки водач взема оптималното от гледна точка на личния му интерес решение относно маршрута си, то някои преки пътища ще бъдат предпочетени от голям брой водачи, което ще увеличи времето на пътуване (поради задръстване). По-формално казано, равновесието на Наш може да не съвпада с оптималния поток през дадена мрежа.[3]

Парадоксът може да бъде определен по следния начин:

„Нека е дадена пътна мрежа. За всяка точка от мрежата са дадени броя автомобили и желаната им крайна цел. При тези условия се търси разпределението на трафика. Дали дадена улица е за предпочитане пред друга зависи не само от качеството на пътя, а и от натовареността ѝ. Ако всеки водач избере маршрута, който изглежда най-изгоден за него, това може да доведе до време на пътуване над минималното. Освен това се демонстрира с пример, че разширяване на пътната мрежа може да доведе до такова преразпределение на трафика, че времето за пътуване да се увеличи.“

Примери в реални ситуации

[редактиране | редактиране на кода]

В Сеул, Южна Корея, времето за пътуване се съкращава след премахването на магистрална отсечка като част от възстановителния проект Чеонггйечеон. В Щутгарт, Германия, след инвестиции в пътната мрежа трафикът не се подобрява, докато една от новопостроените отсечки не бива затворена.[4] Затварянето на 42-ра улица в Ню Йорк намалява задръстванията в района.[5] През 2008 г. Юн, Гастнър и Йеонг демонстрират, че това може да се случи и при определени маршрути в Бостън, Ню Йорк и Лондон и посочват кои улици трябва да се затворят, за да се съкрати времето за пътуване.[6]

Електроразпределение

[редактиране | редактиране на кода]

През 2012 г. учени от института Макс Планк в Гьотинген, Германия демонстрират чрез компютърна симулация, че този феномен може да се наблюдава и в електроснабдителни мрежи, където производството на електроенергия е децентрализирано[7]. Същата година международен екип от учени публикуват документ, доказващ, че парадоксът на Браас може да се прояви в мезоскопични системи[8] от електрони. По-конкретно те показват, теоретично и експериментално, че добавянето на път за електроните в наноскопична мрежа парадоксално намалява проводимостта ѝ[9].

Нека е дадена пътна мрежа като тази на фигурата вляво и нека има 4000 водача, които желаят да се придвижат от точката, обозначена с английската дума Start, до точка End. Пътят, свързващ Start с точка А, е сравнително тесен и времето на пътуване зависи от натовареността:

,

където е времето за пътуване в минути, а е натовареността на пътя към А, измерена в брой автомобили. От друга страна отсечката Start-B е с висок капацитет (магистрала), но е по-дълга, и времето на пътуване по нея на практика не зависи от натовареността:

От другата срана на мрежата (към точка End) положението е същото, само че магистралната и бавната отсечка са разменени, така че пътуването по маршрут А-End отнема винаги 45 мин., а по другата отсечка зависи от натовареността по гореописания начин.

Ако пътят обозначен с пунктир не съществува, то двата маршрута (през точки A или B) са еквивалентни и времетраенето на пътуването по тях ще е:

Ако водачите действат рационално и избират винаги по-малко натоварения път (защото е по-бърз), се стига до равновесно положение, при което по всеки от двата маршрута преминават 2000 автомобила () и пътуването отнема едно и също време:

.

Нека сега предположим, че пунктираната линия между точки А и B обозначава път с пренебрежимо кратко (или много кратко) време на пътуване. Тогава рационалните шофьори, тръгвайки от Start, винаги ще предпочетат по-тесния, но и по-кратък път Start-А, защото по него пътуването отнема най-много , докато по магистралата е най-малко 45 минути. По същата причина всеки рационален шофьор, щом стигне до втората част на трасето би избрал по-тесния, но къс път (отсечката B-End). Така общото време за пътуване е 80 минути.

Разбира се, шофьорите биха могли да постигнат предварително съгласие да не използват бързата отсечка свързваща А и B, за да спестят 15 минути от пътуването си. Но тъй като за всеки водач поотделно отсечката дава предимство, социално оптималното разпределение не е стабилно и не се осъществява. Така се стига до парадокса на Браас.

  1. D. Braess, Unternehmensforschung 12, 258 (1968) ((de))
  2. D. Braess, On a Paradox of Traffic Planning. Transportation Science, Vol. 39, No. 4, November 2005, pp. 446 – 450 (превод на английски от оригиналната статия)
  3. New Scientist, 42nd St Paradox: Cull the best to make things better, 16 January 2014 by Justin Mullins
  4. Knödel, W. Graphentheoretische Methoden Und Ihre Anwendungen. Springer-Verlag, 31 януари 1969. ISBN 978-3-540-04668-4. с. 57 – 59.
  5. Kolata, Gina. What if They Closed 42d Street and Nobody Noticed? // New York Times, 25 декември 1990. Посетен на 16 ноември 2008.
  6. Youn, Hyejin и др. Price of Anarchy in Transportation Networks: Efficiency and Optimality Control // Physical Review Letters 101 (12). 2008. DOI:10.1103/PhysRevLett.101.128701. с. 128701.
  7. www.rdmag.com
  8. с мащаб между между макроскопичен и микроскопичен.
  9. arxiv.org