Научно о пробках на дорогах
Думаю, для пользователей ЖЖ не секрет, что сейчас развёрнута широкая дискуссия о проблеме пробок на дорогах и о методах борьбы с ними. С одной стороны такие деятели как Макс Кац (maxkatz) и Илья Варламов (zyalt), с другой - условно «автомобильно-строительное лобби
( Read more... )
Чисто математически, Брайесов парадокс - частный случай равновесия Нэша, которое, в свою очередь, проявляется в некооперативных играх - т.е. при условии статических граничных условий (правила во время игры не меняются) и взаимной неинформированности игроков.
Такие же проблемы возникали в "ранних Интернетах" при использовании статических и ранних динамических протоколов маршрутизации - вроде RIP и прочих distance-vector routing protocol, когда маршрутизатор-"водитель" знал варианты маршрутов, включающих различное число промежуточных узлов-"перекрестков" и слал пакеты по кратчайшему - как Брайесов эгоистичный водитель.
Проблема решилась достаточно просто - взаимным информированием о состоянии линков и переходом в кооперативную игру - т.е. переходом на link-state routing protocols.
В случае дорожного движения технически собирать информацию о трафике и загруженности линков в реальном времени нет проблем - берем логи запросов на регистрацию мобильных телефонов на базовых станциях и дискриминируем по скорости - но здесь законодательные и орг. проблемы.
Вопрос в информировании водителей.
Но единственный действующий пример link-state routing в городском движении я видел в Бангкоке, где на главных улицах перед разветвлениями / объездами висят электр. табло, показывающие загрузку разветвлений.
Reply
Вот скатились мы в парадокс Брайеса - локальное устойчивое равновесие Нэша. Как из него выбраться, даже если знать загруженность всех маршрутов? Ведь по всем маршрутам время следования в равновесии одно и то же. Плавно в соседний оптимум перейти нельзя - только скачком, полностью закрыв одно из рёбер.
Система link-state routing может, например, подавлять нежелательные осцилляции около состояния равновесия, но вряд ли поможет поиску глобального оптимума.
Reply
Задача системы управления/протокола - обеспечить этот самый неравновесный максимум и поддерживать его.
В динамической маршрутизации с link state advertizing к метрике маршрута по числу хопов/промежуточных узлов добавляется весовой коэффициент линка, зависящий его текущей свободной пропускной способности в результате перегруженные линки при выборе маршрута при отправке текущего пакета становятся "дорогими" - т.е. тот же механизм, что и с выравниванием трафика с оплатой перегруженных маршрутов в статье: они не закрываются, но за счет платности меняется нагрузка на входе.
Т.е. совершенно необязательно блокировать перегруженное ребро - достаточно анонсировать незагруженные ребра напрямую - как это сейчас делается приличными программами навигации, принимающими информацию о пробках - или как в случае Бангкока.
Reply
Ещё, кстати, я только сейчас осознал, что социально оптимальное распределение трафика не является равновесным - тоже не самое очевидное свойство системы.
Reply
И главный практический вывод из этих классических моделей - это то, что классические же "управленческие методы" - от строительства новых дорог "на здравом смысле" до тупого введения платности внутригородских дорог / городских зон математически некорректны, т.к. без обеспечения информированности водителей/автомобилей невозможен вывод системы в кооперативный режим и неизбежно сваливание в равновесие Нэша.
В США и ЕС это прекрасно понимают и сейчас там идут интенсивные разработки по intelligent transportation systems (ITS), включающей системы информирования vehicle-to-infrastructure и (V2I) и управления vehicle-to-vehicle.
Так что автоуправляемые гугломобили, столь любимые прессой, отллько верхушка айсберга :-)
Reply
Leave a comment