Научно о пробках на дорогах

[korzhimanov]

Думаю, для пользователей ЖЖ не секрет, что сейчас развёрнута широкая дискуссия о проблеме пробок на дорогах и о методах борьбы с ними. С одной стороны такие деятели как Макс Кац (maxkatz) и Илья Варламов (zyalt), с другой - условно «автомобильно-строительное лобби

Comments

[kouprianov]

Мне что-то подсказывает, что это с трудом натягивается на ситуацию в Питере (к слову, вовсе не безнадежную в плане пробок). У нас есть несколько катастрофически узких мест -- железные дороги (в большей степени) и Нева с ее рукавами (в меньшей) довольно сильно сегментируют город, и проезд из одного сегмента в другой оказывается довольно затруднительным, в то время как циркуляция в пределах сегментов, в общем, вполне удовлетворительная. Кроме того, платным, почему-то, собираются сделать (и уже сделали отчасти) т. н. Западный скоростной диаметр, который не очень ассоциируется у меня с неэффективными дорогами (или я совершенно не понимаю, что такое эффективность).

[korzhimanov]

Сомневаюсь, что в Питере решение о платности тех или иных дорог принимали с учётом равновесия Нэша и парадокса Брайеса.

[kouprianov]

Вот и мне как-то кажется, что это все немного не про нас.

[kurgus]

Самое интересное, что парадокс Брайеса не является роковым и неизбежным.

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

Такие же проблемы возникали в "ранних Интернетах" при использовании статических и ранних динамических протоколов маршрутизации - вроде RIP и прочих distance-vector routing protocol, когда маршрутизатор-"водитель" знал варианты маршрутов, включающих различное число промежуточных узлов-"перекрестков" и слал пакеты по кратчайшему - как Брайесов эгоистичный водитель.

Проблема решилась достаточно просто - взаимным информированием о состоянии линков и переходом в кооперативную игру - т.е. переходом на link-state routing protocols.

В случае дорожного движения технически собирать информацию о трафике и загруженности линков в реальном времени нет проблем - берем логи запросов на регистрацию мобильных телефонов на

[korzhimanov]

Честно признаться, немного не понял.

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

Система link-state routing может, например, подавлять нежелательные осцилляции около состояния равновесия, но вряд ли поможет поиску глобального оптимума.

[kurgus]

Прелесть ситуации в том, что равновесия Нэша не совпадают с состояниями максимумов средней пропускной способности сети - о чем и пишется в статье.
Задача системы управления/протокола - обеспечить этот самый неравновесный максимум и поддерживать его.

В динамической маршрутизации с link state advertizing к метрике маршрута по числу хопов/промежуточных узлов добавляется весовой коэффициент линка, зависящий его текущей свободной пропускной способности в результате перегруженные линки при выборе маршрута при отправке текущего пакета становятся "дорогими" - т.е. тот же механизм, что и с выравниванием трафика с оплатой перегруженных маршрутов в статье: они не закрываются, но за счет платности меняется нагрузка на входе.

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

[korzhimanov]

Ок, теперь я вроде понял.

Ещё, кстати, я только сейчас осознал, что социально оптимальное распределение трафика не является равновесным - тоже не самое очевидное свойство системы.

[stephan_nn]

proboknet куда отнести? «Антитрамвайник» Шульц, вроде, и их клеймит. Хотя, и Кацу это явный конкурент.

[korzhimanov]

Думаю, стратегически Пробок.нет и Горпроекты на одной стороне, но тактически по каким-то причинам «пробки» ближе к строительному лобби.