Автомобильные пробки: когда рациональность ведет к коллапсу

А. Гасников, Ю. Дорн, Е. Нурминский, Н. Шамрай
«Квант» №1, 2013

Введение

Когда мы только начинали писать эту статью, нам на глаза попался прекрасный слоган в одной социальной рекламе: «Вы не застряли в пробке. Вы и есть пробка». Мало кто из водителей, стоящих в пробке, задумывается о том, что он сам становится причиной задержки тех людей, кто едет вслед за ним, а даже если и задумывается, то не придает этому большого значения. При этом, подрезая очередную машину, водители жалуются на то, как мало строится дорог.

Еще в XVIII веке британский экономист Адам Смит посеял в умах ученых и общественных деятелей увлекательный образ сообщества независимых экономических агентов — потребителей и производителей, каждый из которых, действуя в своих интересах, в результате создает эффективное общественное производство. Можно сказать, что это было первой редакцией лозунга «Анархия — мать порядка!». Однако еще раньше другие, не менее выдающиеся, умы человечества горестно отметили печальное исключение из этого правила — то, что эколог Хардин удачно окрестил «трагедией общей собственности».

Это значит следующее. Если некоторый ресурс находится в общей собственности и для его использования нет никаких ограничений, то он будет подвергаться чрезмерной эксплуатации и исчезнет. Стеллерова корова или почти исчезнувшее Аральское море тому наглядные примеры, и этот горестный список можно продолжить. Экономисты описывают «трагедию общей собственности» как такой вариант общественного устройства, когда с точки зрения отдельного потребителя выгоды от потребления ресурса достаются ему одному, а негативные последствия делятся на всех. В современном мире одним из таких ресурсов являются автомобильные дороги, а «синие мигалки» — наиболее яркое тому свидетельство, усугубленное узурпированным преимущественным правом некоторых пользователей на этот ресурс. Но и независимо от наличия или отсутствия «мигалки» каждый новый автомобиль на дороге приносит своему владельцу определенную пользу или удовлетворение, а негативные последствия — возрастающая плотность автомобилей, замедление движения, заторы и пробки — делятся на всех. Для принципиального выхода из этой ситуации нужна целая система мер, которые примирили бы эгоистическое поведение водителей и общественную пользу, но это слишком обширная тема, для знакомства с которой можно порекомендовать общедоступную книгу В. Вучика «Транспорт в городах, удобных для жизни» (“Transportation for Livable Cities”). Но в любом случае, когда ученые собираются что-то советовать, то они прежде всего изучают явление и определяют, как на него повлияют разные воздействия. В данном случае наиболее видимым и огорчительным являются уличные пробки. Так что же такое пробки и как с ними бороться?

Откуда берутся пробки

Вообще говоря, прежде нужно понять, что такое пробка. Некоторые водители говорят о пробке, когда им приходится ехать со скоростью 20 км/ч из-за плотного движения, вместо желаемых 100 км/ч. Другие же подразумевают под пробкой почти глухой затор. Оба эти случая имеют общую природу — слишком много автомобилистов решили использовать одну и ту же дорогу. Все упирается в то, что понимается под «слишком много».

Можно было бы указывать на то, что у каждой дороги от перекрестка до перекрестка есть вполне конкретные ширина и длина и там «физически» не может поместиться слишком много автомобилей. Но этого аргумента недостаточно, ведь важна еще скорость движения. Если бы водители могли практически без зазоров между машинами ехать на скорости 1000 км/ч, то пропускная способность любой дороги была бы почти неограниченной. Ответ в том, что движение на дороге определяется тем, какие решения принимают водители. Для большинства из них «некомфортно» ехать на скорости 100 км/ч в режиме «бампер к бамперу» — слишком велики риски повредить автомобиль или попасть в крупную аварию. Например, в США еще в школах вождения учат «правилу 3 секунд» — поддерживайте между собой и впереди идущей машиной расстояние, которое вы на данной скорости проедете за 3 секунды. В непогоду это время рекомендуют утраивать. Нечего и говорить о том, что это правило написано кровью тех водителей, которые его не выполняли... Любопытно, что если при этом пренебречь собственными размерами автомобилей, то их поток, т. е. количество автомобилей, пересекающих за единицу времени некоторую контрольную линию, не зависит от скорости и составляет 1200 автомобилей в час на одну полосу движения, что считается нормативной пропускной способностью дороги. Если учесть собственные размеры автомобиля, то пропускная способность существенно уменьшается, особенно при малых скоростях. Но это следует из простейших моделей движения автомобилей, в реальности нужно учитывать массу других факторов, одно перечисление которых может занять не одну страницу. Поэтому ограничимся хорошо установленным экспериментальным фактом — средняя скорость движения на дороге зависит от плотности автомобилей, т. е. их количества на единицу длины дороги, в качестве которой обычно рассматривается километр. При этом чем больше плотность, тем ниже скорость. В простейшем случае предполагается линейная зависимость между плотностью R и скоростью :

R() = –a + R₀,

где a — некоторая константа.

Эта модель была предложена американским инженером-транспортником Брюсом Гриншилдсом (Bruce Greenshields) в 1933 году и до сих пор широко используется в системах моделирования дорожного движения! Недавно в ее честь был даже проведен международный симпозиум, отметивший 75-летие первой публикации. Причина такого внимания к этой модели заключается в том, что она впервые ввела понятие фундаментальной диаграммы поток–скоростьи продемонстрировала наличие максимального потока. Действительно, если мы определим поток Q() автомобилей в единицу времени как произведение R, то

Q() = –a² + R₀,

и график этой квадратичной функции (рис. 1) имеет максимум в точке  = R₀/(2a).

Рис. 1

С тех пор предложена масса модификаций этой зависимости, но сама концепция фундаментальной зависимости поток–скорость остается в основе большинства моделей, как и понятие максимального потока, который может обслужить дорога в единицу времени. Когда на дорогу в единицу времени начинает въезжать больше автомобилей, чем ее пропускная способность, начинает образовываться пробка. Собственно говоря, при этом модель Гриншильдса перестает быть применимой и начинается нерасчетный режим.

Рис. 2

Представьте себе перекресток 1 (рис. 2) и два маршрута, по которым можно доехать до пункта назначения в вершине 3. Причем дорога (1,3) — «короткая», а путь через вершину 2 — длинный объезд. Пусть дорога (1,3) будет двухполосной. В центре дороги (1,3) одна из полос закрыта не ремонт. В начальный момент времени, когда обе дороги пустые (например, в 5 утра), все водители, желающие доехать из 1 в 3, воспользуются дорогой (1,3). Если одна полоса может обслужить 1500 авт./ч, а на дорогу в какой-то момент начнет поступать поток в 2500 авт./ч, встанет вопрос — куда денутся 1000 авт./ч? Конечно, встанут прямо перед узким местом. Более того, из-за необходимости перестраиваться, по работающей полосе поток будет ниже 1500 авт./ч. С течением времени пробка будет расти. Вопрос номер два — когда пробка расти перестанет? Логика и законы сохранения нам подсказывают, что это случится, если количество въезжающих на дорогу водителей сравняется с количеством выезжающих, т. е. станет примерно 1500 авт./ч. Но куда денутся лишние 1000 авт./ч, ранее использовавшие данную дорогу в своем маршруте? Очевидно, начнут (из-за пробки) использовать объезд. Переключение на объездную дорогу произойдет ровно в тот момент, когда водителям будет безразлично, какой из маршрутов (короткий или объездной) использовать. Но ведь если бы объезд использовался с самого начала, пробки бы не возникло! Водителей можно понять, кому же захочется ехать в далекий объезд, если рядом короткая дорога, и пусть она работает на пределе, но уж мы как-нибудь прорвемся (а за нами хоть потоп!). Вот так и начинается пробка.

Модель

В дальнейшем мы рассмотрим модель для описания поведения водителей и транспортной системы в целом на конкретном примере. Сеть, изображенная на рисунке 3, обычно используется для иллюстрации так называемого парадокса Брайеса.

Рис. 3

На время забудем о рисунке 3,б (он понадобится нам позднее) и будем работать только с графом на рисунке 3,а.

Городская транспортная сеть задается взвешенным ориентированным графом Г(V, E, T), или, говоря проще, дороги представляются ребрами графа, они имеют заданное направление (поэтому граф направленный, т. е. ориентированый), перекрестки — вершины графа, при этом каждому ребру соответствует определенное время, которое водитель должен потратить на проезд. Это время и является «весом» ребра (поэтому граф взвешенный). Здесь V — множество вершин графа (множество перекрестков), на рисунке 3,а они обозначены цифрами 1, 2, 3 и 4, а E — множество ребер графа (дороги), на рисунке 3,а дороги обозначены буквами a, b, c и d. Каждой дороге соответствует свой «вес», который, вообще говоря, зависит от того, сколько людей эту дорогу использует. Понятно, что чем больше машин использует какую-то конкретную дорогу, тем больше пробка и тем больше времени потребуется на проезд. «Вес» дороги описывает зависимость времени на проезд по ребру от того, сколько автомобилей его использует. Обозначим функции весов дорог через f_a, f_b, f_c и f_d для ребер a, b, c и dсоответственно.

В нашем модельном примере мы будем считать, что у всех ребер функции весов линейные, в частности, f_a(t) = f_d(t) = 50 + t, f_b(t) = f_c(t) = 10t. Еще раз поясняем, что, например, запись f_d(t) = 50 + t следует понимать примерно так: если по дороге d едет t водителей в единицу времени, то проезд по ребру d займет 50 + t минут.

Предположим, что водители едут из вершины 1 в вершину 4, причем в единицу времени из 1 в 4 направляется одно и то же число водителей. В нашем примере оно равно 6. При этом, как легко показать, из 1 в 4 можно попасть по одному из двух маршрутов: 1-a-3-c-4 и 1-b-2-d-4. В нашей грубой модели водитель не будет тратить время на проезд через перекресток. Тогда время в пути для маршрутов будет определяться как сумма весов входящих в маршрут ребер. Например, для маршрута 1-a-3-c-4 время в пути составит f_a + f_c, а для маршрута 1-b-2-d-4 время в пути составит f_b + f_d. Обозначим через x транспортный поток на маршруте 1-a-3-c-4, а через y — транспортный поток на маршруте 1-b-2-d-4. Под транспортным потоком на маршруте подразумевается количество водителей, выезжающих из 1 в 4 по этому маршруту в единицу времени. При этом, очевидно, x + y = 6.

Легко показать, что для графа на рисунке 3,а поток на ребрах a и c равен x, а поток по ребрам b и d равен y. Соответственно, время в пути для маршрута 1-a-3-c-4 будет равно f_a(x) + f_c(x), а для маршрута 1-b-2-d-4 время в пути будет равно f_b(y) + f_d(y).

Водители, выбирая свой маршрут следования, ведут себя эгоистично. В нашем случае это значит, что они выбирают маршрут с наименьшими ожидаемыми издержками. Но чем больше водителей выбирают тот или иной маршрут, тем выше издержки на данном маршруте. С другой стороны, мы зафиксировали общее число машин, выезжающих из вершины 1 в вершину 4 в единицу времени, а значит, если каким-то маршрутом стало пользоваться большее количество автомобилистов, то есть какой-то маршрут, который стал использоваться меньше. Вероятно, что на этом втором маршруте издержки, напротив, упадут. Таким образом, первый, ранее привлекательный, маршрут становится более обременительным, а альтернативные маршруты при этом становятся более привлекательными. Это мотивирует водителей вновь изменить свой маршрут. Но такая «болтанка» происходит не всегда.

Введем понятие равновесия (Нэша–Вардропа). Назовем распределение потоков по маршрутам равновесным, если время проезда по всем используемым маршрутам одинаково и не превосходит времени в пути на неиспользуемых маршрутах.¹

Смысл этого утверждения очень прост: равновесное распределение потоков по маршрутам — это когда водители так выбирают свои маршруты, что никому в отдельности не выгодно менять свой выбор. Если бы, например, для графа на рисунке 3,а реализовалось равновесие и мы бы рассмотрели произвольного водителя, использующего маршрут 1-b-2-d-4, то мы могли бы сказать, что этому водителю не выгодно менять свой маршрут.

Для нашего примера найти равновесие очень просто. Всего возможны три варианта:

    1) x = 6,  y = 0,  f_a(6) + f_c(6) ≤ f_b(0) + f_d(0);
    2) x = 0,  y = 6,  f_a(0) + f_c(0) ≥ f_b(6) + f_d(6);
    3) x + y = 6,  x > 0,  y > 0,  f_a(x) + f_c(x) = f_b(y) + f_d(y).

Заметим, что в нашем случае f_a(t) + f_c(t) =11t + 50 = f_b(t) + f_d(t). Отсюда имеем f_a(0) + f_c(0) = f_b(0) + f_d(0) = 50 и f_a(6) + f_c(6) = f_b(6) + f_d(6) = 116. Следовательно, варианты 1) и 2) отпадают. Для того чтобы найти равновесное распределение потоков, нужно решить систему уравнений 3):

Легко доказать, что полученное решение удовлетворяет условиям равновесия. Действительно, время в пути на используемых маршрутах совпадает и равно 11·3 + 50 = 83 , а неиспользуемых маршрутов просто нет.

Резюмируя, техника поиска равновесий следующая.

1. Все маршруты делятся на используемые и неиспользуемые в равновесии. Получается огромное количество вариантов разделений.

2. Выбирается конкретное разделение.

3. Ищется такое распределение суммарного потока по используемым маршрутам, чтобы время в пути на всех используемых маршрутах было одинаковым. Если такого не существует, разделение «бракуется». Если есть, переходим к следующему пункту.

4. Проверяется, что для всех неиспользуемых маршрутов время в пути не ниже, чем на используемых.

Если найденное распределение потоков по маршрутам удовлетворяет этим условиям, то оно и есть искомое. Вообще говоря, равновесий может быть несколько или даже бесконечно много. Заметим также, что на практике, конечно, применяются намного более эффективные алгоритмы поиска равновесий. Описанный выше способ — самый примитивный, мы привели его из-за наглядности.

Пример выше иллюстрирует тот факт, что в равновесии ни один из водителей не может выиграть, изменив свой маршрут. Поэтому, если система находится в равновесии, то она в этом равновесии и останется (вообще говоря, мы должны были бы потребовать устойчивость равновесия, но сейчас не хотелось бы говорить об этом). Данное равновесие носит имя Нэша и Вардропа (об этом уже упоминалось чуть выше) по следующим причинам. Если рассмотреть игру, в которой водители являются игроками, маршруты — стратегиями (другими словами, возможными действиями игроков), а издержки, соответствующие маршрутам и взятые со знаком «минус», — выигрышами, то выписанное определение будет являться определением равновесия Нэша в построенной игре. Собственно, существование равновесия гарантируется теоремой Нэша, с которой можно познакомиться в любом учебнике по теории игр. В ней, в общем, и постулируется существование равновесия в играх, подобных рассмотренной нами. Вардроп же предложил два принципа, описывающих возможное поведение водителей. Первый из них предполагает, что все водители действуют оппортунистически и считают собственное влияние ничтожным. Второй принцип, напротив, говорит, что водители могут действовать согласованно с целью минимизировать общественные издержки. Собственно этими двумя принципами и их комбинациями, по мнению Вардропа, и описываются все возможные и существенные для анализа варианты поведения.

Парадокс Брайеса и неэффективные дороги

Немецкий математик Дитхард Брайес вошел в историю как автор простейшего примера, демонстрирующего, к чему приводит эгоистичное поведение.

Брайес рассмотрел простейшую транспортную сеть, соединяющую двумя непересекающимися маршрутами начальный и конечный пункты 1 и 4 (см. рис. 3).

Мы уже искали равновесие для графа на рисунке 3,а и получили, что x = y = 3,

f_a(3) + f_c(3) = f_b(3) + f_d(3) = 83.

Однако Брайес на этом не остановился и рассмотрел модификацию первоначальной сети, где построена дополнительная дорога, напрямую соединяющая промежуточные пункты (рис.3,б), которую мы назовем e. Дорога получилась приличного качества и относительно короткая, так что время проезда по ней определяется формулой

f_e(t) = t + 10.

Заметим, что у водителей, которые едут из 1 в 4, появился новый маршрут 1-b-2-e-3-c-4. Каким будет новое равновесие и каким будет время проезда?

Можно себе представить, что в первое время, пока эта дорога еще мало кому известна, поток по ней равен 0 и, следовательно, у того водителя с нижнего маршрута, который первым свернул на нее, время проезда составит

f_b(3) + f_e(0) + f_c(3) = 30 + 10 + 30 = 70.

Это явно меньше 83 минут. Ура, сворачиваем! Но что происходит дальше? За нами сворачивают новые машины, водители которых, видимо, провели те же самые расчеты! Та же самая логика, которая применялась и для исходной сети, должна быть применена и в этом случае — потоки перераспределятся так, что время проезда по каждому маршруту будет одинаково и никому из водителей не будет смысла менять маршрут. Мы получим новое равновесие.

Действуя по нашей схеме, мы должны определить возможные разделения маршрутов на используемые и неиспользуемые. Всего у нас будет 7 вариантов:

Пусть нам известно, что равновесие получается в случае, когда все маршруты используются. Обозначим через z транспортный поток на новом маршруте 1-b-2-e-3-c-4. Решим систему уравнений, которая получается из условия равновесия:

В первом уравнении мы написали, что времена проезда в равновесии для маршрутов 1-a-3-c-4 и 1-b-2-d-4 равны. Во втором уравнении мы записали то же требование для маршрутов 1-a-3-c-4 и 1-b-2-e-3-c-4.

Преобразуем систему, подставив вместо функций их значения:

Решая систему, получаем x = 2,новые машины y = 2,новые машины z = 2, т. е. в равновесии суммарный поток распределится по маршрутам в равных долях x = y = z = 2, а время в пути для всех маршрутов составит

f_a(2) + f_c(4) = 50 + 2 + 40 = 92.

Замечание. То, что здесь и ранее в равновесии потоки по маршрутам оказались равны между собой, — чистая случайность и результат подбора таких функций весов, чтобы «получилось красиво». В равновесии у маршрутов равны времена в пути (!), а не потоки.

Что замечательно (с исследовательской точки зрения, с практической же точки зрения это ужасно), время в пути после добавления нового ребра для всех водителей возросло. Это увеличение является следствием того, что мы позволили каждому водителю поступать эгоистично, выбирая маршруты так, чтобы никому не было выгодно отклониться от равновесия.

Описанный выше парадокс Брайеса произрастает из неэффективности равновесия Нэша–Вардропа с точки зрения общественного блага. Говоря проще, из-за эгоистичности водителей суммарные издержки всех водителей в равновесии выше, чем вообще могли бы быть при некотором другом распределении.

Определим теперь понятие социального оптимума. Социальный оптимум — это такое распределение потоков по маршрутам, при котором суммарное время в пути у всех водителей минимально.

Тем самым, для того чтобы найти социальный оптимум в нашей системе, нам нужно было бы решить следующую задачу — найти

min (x·(f_a(x) + f_c(x + z)) + y·(f_b(y + z) + f_d(y)) + z·(f_b(y + z) + f_c(x + z) + f_e(z)))

при условии x + y + z = 6, где x, y, z неотрицательны, т. е. найти

min (50·x + 11·x² + 20·xz + 50·y + 11·y² + 20·yz + 21·z² + 10·z).

Выразив z, сводим задачу к поиску

min (816 – 92·x – 92·y + 2·xy + 12·x² + 12·y²).

Можно доказать, что точкой минимума при условии неотрицательности переменных будет тройка (3, 3, 0).

Все описанные проблемы с пробками проистекают из-за того, что социальный оптимум обычно (как в нашем случае) не является равновесием.

Конечно, возможны ситуации, когда равновесие Нэша–Вардропа является социальным оптимумом, но в общем случае это не так.

Заметим, что в социальном оптимуме ребро e не используется. Оно неэффективно. Эгоизм же водителей приводит к его использованию. Можно показать, что это верно для любых неэффективных ребер (т. е. таких, от чьего удаления кто-то из водителей выигрывает, но никто не проигрывает). Их появление является следствием неэффективности равновесия.

Итак, мы показали, что из-за эгоизма водителей могут возникать неэффективные ребра и прочие проблемы. Невелика заслуга. Вопрос только в том, насколько (!) это плохо.

Чтобы ответить на него, нам нужно найти некоторую характеристику или численную меру эффективности распределения транспортных потоков при заданном графе и числе выезжающих автомобилей (в единицу времени). Первое, что приходит в голову, — совокупное время в пути.

Влияние эгоистичности водителей можно оценить по разнице между временем в пути в реализовавшемся распределении (т. е. равновесием) и временем в пути при оптимальном поведении водителей (т. е. социальном оптимуме). В нашем случае эта величина равна 92 – 83 = 9.

Много это или мало? Ответ зависит от графа и загрузок. Традиционно мерой неэффективности является так называемая «цена анархии» — отношение времени в пути в худшем равновесии ко времени в пути при оптимальном распределении потоков. В нашем случае «цена анархии» равна  ≈ 1,1084.

Насколько большой может быть «цена анархии», зависит от того, какие функции весов мы выберем, и «не зависит» от размеров графа транспортной сети. Например, для нашей сети, в которой время в пути по ребру зависит от потока линейно, максимальное значение «цены анархии» равно 4/3.

Платные дороги

Замечательное свойство неэффективных ребер заключается в том, что с ними можно эффективно бороться. Действительно, достаточно запретить проезд по неэффективному ребру, как транспортная ситуация улучшится. Поставил кордон — и дело сделано!

В этот момент самое время вспомнить введение нашей статьи. Мы показали, что участники движения во многом сами являются причиной возникновения пробок. При этом разговоры о том, что нужно строить больше дорог для того, чтобы все поехало, не приведут ни к чему хорошему. Иногда, чтобы все поехало, надо дороги закрывать. Беспорядочное строительство, наоборот, может привести к ухудшению транспортной ситуации.

Только что мы сказали «поставил кордон — и дело сделано». Но ни один чиновник никогда не поставит кордон. Как же так: сначала за 29 миллиардов построим дорогу, а потом ее закрывать? Нонсенс! Уж лучше пусть смоет (как это произошло во Владивостоке в 2012 году). Тем более, ребро является неэффективным только при определенных загрузках. Возможно, ситуация и загрузка сети со временем изменятся и наличие ребра (ранее неэффективного) будет полезным. Было бы неприятно закрыть дорогу, дать ей разрушиться, а через десять лет строить на том же месте новую, так как она снова стала нужна.

Куда более прагматичным будет решение сделать проезд по неэффективным ребрам платным. С одной стороны, установив очень большую плату, мы можем свести поток по неэффективному ребру к минимуму. С другой стороны, мы позволяем планировщикам сохранить лицо. Дорога же работает и исправна — езжай на здоровье! Ну и наконец, если вдруг ситуация поменяется так, что ребро вновь станет эффективным, то плату можно будет снизить или вовсе убрать.

С точки зрения математики, это будет выглядеть так. Назначение платы за проезд по ребру е в размере α соответствует замене f_e(x) на  f_e(x) + α. Это приводит, вообще говоря, к смещению равновесия. Правильное назначение платы делает возможным изменение равновесия в благоприятную сторону. Продемонстрируем это на примере.

Назначим плату за проезд по ребру e графа на рисунке 3,б в размере 6,5. Решая заново систему, мы получим, что новым равновесием будет точка . Издержки за проезд водителей снизились с 92 до 87,5. Отлично! Давайте увеличим плату в 1,5 раза до 9,75. Повторяя процедуру, найдем новое равновесие Издержки снова упадут до 85,25. Вспоминая, что минимальные издержки за проезд, которые вообще возможны (для этого графа и загрузок), составят 83, можно сказать, что мы уже совсем близки к цели. Действительно, лучшее, чего мы могли бы достигнуть, — это оптимальное распределение, поэтому в равновесии при введенных платах издержки не могут быть ниже 83. Когда мы дойдем до платы в 13, по ребру e водители ездить перестанут. При этом нам повезет, и новое равновесие будет социальным оптимумом (что наблюдается не всегда).

Но самое главное свойство платных дорог заключается в том, что, устанавливая подходящую плату, мы можем бороться не только с неэффективными ребрами, но и с возникающими пробками. Мы уже обсуждали выше, что пробки возникают из-за того, что нужно «выровнять» издержки за проезд по быстрым и медленным маршрутам, если быстрые маршруты не могут обслужить самостоятельно весь автомобильный поток. Этого требует принцип Вардропа. Но ведь плата за проезд тоже может выровнять эти издержки! Механика тут будет точно такой же, как в примере выше.

Теперь, когда мы знаем откуда берутся пробки и как можно их побороть, самое время отточить навыки.

Задачи

1. Найдите равновесное распределение потоков для транспортного графа на рисунке 3,б, если суммарно из 1 в 4 в единицу времени направляются 2 автомобиля.

2. Как можно объяснить следующее противоречие: в описанной в статье модели время в пути по дуге есть строго возрастающая функция от величины потока на дуге, а согласно фундаментальной диаграмме Гриншилдса эта зависимость не является однозначной — есть две ветки, одна из которых соответствует малым и умеренным плотностям и согласуется с отмеченной зависимостью, другая, соответствующая большим плотностям, приводит к убывающей зависимости времени в пути от величины потока?

3 (де Пальма). Из жилого района в рабочий район утром должны отправляться 10 000 автомобилей. Водитель каждого автомобиля хочет приехать ровно к 9 часам утра в рабочий район. При этом каждая минута опоздания штрафуется в 10 рублей, а каждая потерянная минута в пути или в ожидании начала рабочего дня, если водитель приехал раньше времени, стоит 3 рубля. Время в пути по свободной дороге занимает 60 минут. Но на середине дороги есть узкое место, пропускная способность которого ограничена 3000 автомобилей в час. Покажите, что равновесное распределение водителей по времени выезда из жилого района n(t) представимо в виде

Найдите n₁, n₂ , t₁, t₂, t₃.

4. Рассмотрите транспортный граф на рисунке 4. Считайте, что характеристики графов, включенных в оранжевые прямоугольники, совпадают с характеристикой транспортного графа на рисунке 3,б. Дороги, соединяющие вершины 1 и 6 с этими графами, такие, что по ним может проехать сколь угодно много автомобилей, причем время в пути будет пренебрежимо мало. Найдите равновесное распределение потоков, если суммарный поток из 1 в 4 равен: а) 2; б) 6; в) 10; г) 14.

Рис. 4

5. Являются ли дороги в графе на рисунке 4, соединяющие вершины 2 и 3, 4 и 5 соответственно, неэффективными, и если да, то при каком суммарном потоке?

¹ Понятие равновесия было определено Джоном Нэшем (тем самым, о котором снят интересный фильм «Игры разума») в конце 40-х годов XX века. Концепция равновесия игры является центральной в теории игр, познакомиться с ней можно в любом учебнике по теории игр или исследованию операций. Позднее, в 1994 году, именно за эту концепцию Джон Нэш получил Нобелевскую премию по экономике. Мы также добавляем фамилию Дж. Г. Вардропа, которой чуть позже Нэша добавил к этой концепции условие «конкурентного рынка»: игрок, принимающий решение, пренебрегает тем, что его решение сколько-нибудь значительно поменяет ситуацию в транспортной системе (в нашей модели это и есть «рынок»). Когда игроков двое или трое (ситуации, рассматриваемые Нэшем), то очевидно, что так делать нельзя. Но когда игроков (водителей) десятки и сотни тысяч...