Новые дороги и вечные пробки
Будем считать, что у каждого участка дороги есть некоторая фиксированная пропускная способность — сколько машин в час может проехать через этот участок. Это предположение довольно близко к действительности: пока машин не слишком много, они могут ехать с максимальной скоростью. Когда их становится слишком много, дистанция между машинами падает, соответственно падает и скорость, ведь дистанция между машинами примерно пропорциональна скорости.
Пропускную способность реальной дороги можно грубо оценить по количеству полос и скорости, с которой можно по данной дороге ехать (в данную погоду). Например, если полоса всего одна, а скорость движения 80 км/ч, то за час «проедет» 80 000 м автомобилей. При такой скорости интервалы между машинами можно оценить в 32 м, и тогда это дает пропускную способность около 80 000 / 32 = 2500 машин в час.
Пропускная способность реальной дороги зависит от множества факторов: от погоды (в дождь и снег скорость падает), от потока грузовиков, от количества ям. Более того, пропускная способность реальной дороги при увеличении потока начиная с некоторого момента начнет падать: невежливые водители всё время будут пытаться объехать по обочине, проскочить в любые щели — это создает беспорядок в движении, который снижает скорость. Однако для нас это всё не важно; будем считать, что у каждого участка задана фиксированная пропускная способность (никак не связанная с оценками выше).
Что будет, если по дороге с пропускной способностью 2500 машин в час соберется проехать 10 000 машин? Они будут проезжать в четыре раза медленнее: ведь через каждый кусок не может проехать больше 2500 машин за час — если уплотнять машины и уменьшать интервалы, то пропорционально будет падать скорость, что вполне естественно. Для нас это будет означать, что водитель потратит в 4 раза больше времени, чем при движении по незагруженной дороге.
Далее будем считать, что перед выездом каждый водитель заходит на сайт «Яндекс. Пробки» и узнает маршрут, который займет у него наименьшее время с учетом пробок на данный момент, а далее следует этому маршруту.
В реальности у каждого водителя своя цель, однако чтобы понять идею (и увидеть причину некоторых реальных пробок), достаточно считать, что все водители едут из пункта A в пункт B.
Задача
Придумайте простую дорожную сеть (то есть граф, ребра которого изображают дороги, и на каждом ребре написана его пропускная способность), такую, что после строительства новой дороги при подходящей интенсивности движения время движения абсолютно всех участников дорожного движения увеличится.
Подсказка 1
Как придумать дорожную сеть
Если в сети есть хотя бы два места с постоянными пробками, то, построив новую дорогу, можно «заставить» многих постоять в обоих.
Подсказка 2
Как посчитать время
Для любой дорожной сети, в которой все участники едут из A в B, время движения по всем используемым маршрутам одинаково.
Решение
Для начала заметим, что для любой дорожной сети, в которой все участники едут из A в B, время движения по всем используемым маршрутам с какого-то момента устаканится и будет одинаково. Действительно, если какой-то маршрут будет быстрее, то «Яндекс. Пробки» предложит именно его. Тогда очередной водитель выберет его, и тем самым не изменит или даже увеличит время движения по этому маршруту. Значит, рано или поздно времена выравняются и уже не будут меняться. Такая ситуация называется равновесием Нэша: система приходит в такое состояние, в котором всем заинтересованным лицам невыгодно его менять — в данном случае водители потеряют из-за этого лишнее время.
Теперь возьмем такую дорожную схему:
По синей и по всем зеленым дорогам можно двигаться со скоростью 90 км/ч, по красным — всего 30 км/ч (очень уж плохая дорога); длины красных участков 5 км, длины зеленых — 90 км, а синим отмечена новая четырехполосная дорога длиной 45 км. Пусть в течение каждого часа из A в B хотят проехать 4000 машин. Тогда они поровну разделятся по левому и правому маршруту и будут тратить 60 минут на зеленый участок (2000 < 5000) и 20 минут на красный (желающих проехать вдвое больше пропускной способности, поэтому скорость упадет в два раза), то есть в сумме 80 минут.
Посмотрим, что же произойдет после строительства новой дороги. В момент открытия дороги «Яндекс. Пробки» обнаружит новый путь, время движения по которому будет равно 20 + 30 + 20 = 70 минут. Это быстрее, чем 80 минут по старым путям, поэтому система предложит поехать по новому пути. Но всякий, кто так поедет, будет два раза стоять в пробке, увеличивая тем самым время ее прохождения. Значит, время движения по «старому» пути должно увеличиться! Следовательно, еще больше машин поедет по новому пути. Так будет происходить, пока время движения по всем путям не уравняется.
Вычислим это время.
Раньше по зеленой дороге из A начинали движение 2000 машин в час. Пусть после строительства синей дороги по зеленой будут ехать x машин в час. По красной дороге тогда поедут 4000 – x машин в час. Пусть на развилке синей и зеленой дорог зеленую выбирают y машин в час, а по синей поедут оставшиеся 4000 – x – y. Поскольку и x, и y в нашем примере меньше 5000 (пропускной способности зеленых дорог), время по этим отрезкам пути будет по-прежнему равно 60 минутам. Разберемся с красными участками. Если по такой дороге поедут 1000 машин в час, то они потратят 10 минут. Поэтому, как уже обсуждалось выше, каждая из 4000 – x машин, едущих по нижнему красному отрезку, потратит на него 10 · [(4000 – x) / 1000] минут. По верхнему красному отрезку поедут 4000 – y машин, и потратят на него 10 · [(4000 – y) / 1000] минут. Но времена по зелено-красному и по красно-зеленому путям должны быть равны, поэтому 90 + 10 · [(4000 – y) / 1000] = 10 · [(4000 – x) / 1000] + 90. Отсюда получаем, что x = y. Симметричность схемы дорог влечет за собой и симметрию в распределении потоков!
Значит, по синей дороге едут 4000 – 2x машин, которые дважды оказываются в пробках на красных участках. И тратят они на весь путь 30 + 2 · 10 · [(4000 – x) / 1000] минут. Это время тоже равно времени остальных участников движения на весь путь, поэтому получаем уравнение
Решив его, найдем, что x = 1000 машин, а время движения — 90 минут.
Поразительно! Строительство новой хорошей дороги привело к увеличению времени движения всех участников с 80 до 90 минут!
Можно придумать и куда более сложные примеры с множеством целей и путей. Но проблема всегда одна и та же — «бутылочные горлышки» в дорожном графе.
В следующий раз, стоя в пробке, обратите внимание, вдруг именно хорошая новая широкая дорога ведет сюда?
Послесловие
Наша модель была сильно упрощенной по сравнению с теми, которые используются учеными и проектировщиками при планировании дорожных сетей. Но и она хорошо отражает основные закономерности распределения транспортных потоков. Для этого ее использовал немецкий математик Дитрих Браейсс, а сама ситуация, когда строительство новой дороги ухудшает дело, называется парадоксом Брайесcа (Braess's paradox).
Что самое забавное, парадокс Брайесса несколько раз случался и в реальной жизни. Например, в Штутгарте в 1969 году после увеличения дорожной сети ситуация с пробками улучшилась только после того, как некоторые новые дороги были закрыты.
Важное, и в то же время очень правдоподобное, допущение, сделанное нами в самом начале — это что водители выбирают свой маршрут, руководствуясь только личной выгодой, чтобы минимизировать время на свою дорогу. Это как раз и приводит к проблемам. Если бы они все имели возможность перед выездом договориться, как ехать, то новой дорогой можно было бы совсем не пользоваться, вернув время движения к 80 минутам. Но в нашей модели (и в жизни!) водители эгоистичные, и, несмотря на то что каждый стремится выбрать для себя быстрейший маршрут и действует при этом абсолютно логично, получается парадоксальный итог: все дружно оказываются в проигрыше. Все это понимают, но менять что-то невыгодно: система находится в равновесии Нэша.
Отметим, что если бы можно было как-то влиять на предпочтения водителей в выборе дорог, то синяя дорога вполне могла бы принести пользу. Например, если сделать ее платной, то далеко не все решат по ней поехать. Меняя цену проезда, можно управлять долей водителей, которые выберут новую дорогу и добиться снижения общего времени пути из A в B.
