© 2021-2023. Нау. Путеводитель по науке в Москве
© 2021-2023. Нау. Путеводитель по науке в Москве
Поставить точку на дорожных пробках. Как ученые решают привычные проблемы
В НИУ ВШЭ первую научную степень доктора компьютерных наук в России получил Павел Двуреченский. Научным консультантом диссертанта выступил Александр Гасников, доктор физико-математических наук. Как между собой связаны компьютерные науки и пробки на дорогах и почему для того, чтобы разгрузить транспортные потоки, в первую очередь приглашают не строителей дорог, а докторов наук? Разбираемся в этом вопросе по материалам статьи «Как и почему образуются пробки на дорогах. Математические модели для анализа транспортных потоков», опубликованной на сайте газеты «Коммерсантъ».
В России в 2018 году НИУ ВШЭ получил право присваивать собственные ученые степени, благодаря чему появилась возможность присваивать степень доктора компьютерных наук. Ранее в России можно было стать только доктором смежных направлений — технических или физико-математических наук.
Исследования Павла Двуреченского на регулярной основе поддерживаются различными научными грантами. В частности в данный момент ученый работает по гранту РФФИ 18–29–03071 мк (руководитель — профессор Е. А. Нурминский, известный специалист в области транспортного моделирования в России).
Комментарий Павла по поводу защиты:
«Не могу сказать, что я испытываю какую-то особенную гордость от того, что я стал первым в России доктором компьютерных наук, но мне приятно это осознавать. Я смотрю на это как на очередной этап в карьере: когда накопилось достаточно наработок для докторской диссертации — защитился. Я планирую продолжить работать в этом направлении, писать статьи на смежные темы и подавать работы в журналы и на конференции».
Исследования Павла Двуреченского на регулярной основе поддерживаются различными научными грантами. В частности в данный момент ученый работает по гранту РФФИ 18–29–03071 мк (руководитель — профессор Е. А. Нурминский, известный специалист в области транспортного моделирования в России).
Комментарий Павла по поводу защиты:
«Не могу сказать, что я испытываю какую-то особенную гордость от того, что я стал первым в России доктором компьютерных наук, но мне приятно это осознавать. Я смотрю на это как на очередной этап в карьере: когда накопилось достаточно наработок для докторской диссертации — защитился. Я планирую продолжить работать в этом направлении, писать статьи на смежные темы и подавать работы в журналы и на конференции».
Откуда берутся пробки на дорогах?
1
Пусть есть два района — 1 и 2, — которые соединены двумя дорогами — A и Б.
При этом максимальная пропускная способность каждой дороги — 2000 автомобилей в час. При потоке меньше максимального время движения по дороге A — 60 минут, а по дороге Б — 30 минут.
2 000 автомобилей в час
Пусть есть два района — 1 и 2, — которые соединены двумя дорогами — A и Б.
При этом максимальная пропускная способность каждой дороги — 2000 автомобилей в час. При потоке меньше максимального время движения по дороге A — 60 минут, а по дороге Б — 30 минут.
2 000 автомобилей в час
2
Если поток автомобилей равен максимальному, то время проезда может быть любым (зависит от размеров пробки на дороге), но не меньше времени свободного проезда.
Поток меньше максимального
Если поток автомобилей равен максимальному, то время проезда может быть любым (зависит от размеров пробки на дороге), но не меньше времени свободного проезда.
Поток меньше максимального
3
Чтобы понять, как образуется пробка, будем постепенно увеличивать поток автомобилей из района 1 в район 2, то есть число автомобилей, которое хочет переместиться из района 1 в район 2 за 60 минут. При маленьком потоке обе дороги не будут загружены, и водители, стремясь уменьшить свои временные затраты, будут выбирать маршрут, проходящий по дороге Б.
Чтобы понять, как образуется пробка, будем постепенно увеличивать поток автомобилей из района 1 в район 2, то есть число автомобилей, которое хочет переместиться из района 1 в район 2 за 60 минут. При маленьком потоке обе дороги не будут загружены, и водители, стремясь уменьшить свои временные затраты, будут выбирать маршрут, проходящий по дороге Б.
4
С увеличением потока из района 1, когда на дороге Б будет достаточно много водителей, из-за ограничения на пропускную способность на дороге Б начнет скапливаться пробка. Например, если на въезде в район 2 в конце дороги Б имеется светофор, на котором будет происходить рост пробки.
С увеличением потока из района 1, когда на дороге Б будет достаточно много водителей, из-за ограничения на пропускную способность на дороге Б начнет скапливаться пробка. Например, если на въезде в район 2 в конце дороги Б имеется светофор, на котором будет происходить рост пробки.
5
Пробка будет расти до тех пор, пока водители не начнут терять в ней 30 минут. Тогда суммарные потери на каждой из двух дорог сравняются, и водители, выезжающие из района 1, начнут использовать дорогу А.
Пробка будет расти до тех пор, пока водители не начнут терять в ней 30 минут. Тогда суммарные потери на каждой из двух дорог сравняются, и водители, выезжающие из района 1, начнут использовать дорогу А.
В поисках оптимального варианта. Как распределить водителей по маршрутам?
Эффективность по Парето является одним из центральных понятий для современной экономической науки. Оптимальное состояние по Парето — ситуация, в которой нельзя улучшить положение любого участника процесса, одновременно не снижая благосостояния как минимум одного из остальных.
Вывод: водителям будет невыгодно отклоняться от выбранного маршрута, так как это повлечет увеличение суммарных затрат. Ситуация, в которой невыгодно отклоняться от выбранной стратегии (в данном случае стратегия — это выбор маршрута для проезда), называется равновесием по Нэшу.
Добавим, что рассмотренная выше ситуация — это модель, когда эгоистически (рационально) настроенные агенты (в нашем случае водители) пользуются общим ресурсом. Если их не регулировать, то настроенная система сломается. Так, если бы по дороге А проезжала 1001 машина в час, а по дороге Б — 1999, то для водителей, едущих по дороге А, ничего бы не изменилось в смысле временных затрат. А вот водители, использующие дорогу Б, добирались бы в два раза быстрее. Таким образом, равновесие по Нэшу может быть неэффективно по Парето. Понятие «равновесие» вовсе не означает (социальный) оптимум.
Добавим, что рассмотренная выше ситуация — это модель, когда эгоистически (рационально) настроенные агенты (в нашем случае водители) пользуются общим ресурсом. Если их не регулировать, то настроенная система сломается. Так, если бы по дороге А проезжала 1001 машина в час, а по дороге Б — 1999, то для водителей, едущих по дороге А, ничего бы не изменилось в смысле временных затрат. А вот водители, использующие дорогу Б, добирались бы в два раза быстрее. Таким образом, равновесие по Нэшу может быть неэффективно по Парето. Понятие «равновесие» вовсе не означает (социальный) оптимум.
Ближе к делу. Теория
Чтобы уравновесить ситуацию на дороге, нужно знать пропускную способность и время свободного прохождения для каждого ее участка. Это можно выяснить исходя из полосности дорог и информации о работе светофоров. Также нужна матрица корреспонденций — информация о том, откуда, куда и сколько людей направляются в единицу времени.
Как узнать, сколько людей собирается отправиться в путь и куда они поедут? Можно провести опрос. Однако эти данные могут измениться со временем.
Как узнать, сколько людей собирается отправиться в путь и куда они поедут? Можно провести опрос. Однако эти данные могут измениться со временем.
Допустим, водитель выходит из дома каждое утро по будням в восемь утра и едет на работу к девяти. Если он сменит работу, место жительства или просто заболеет и решит остаться дома, то данные опроса уже потеряют актуальность. Чтобы уточнить данные, нужно знать модель, которая описывает эти изменения. Такие модели существуют, общая идея для них — люди стремятся работать ближе к месту жительства. В свою очередь, люди имеют мнение по поводу того, каким путем им удобнее ехать, и выбирают дорогу исходя из своих предпочтений, опыта или предположений («Та дорога всегда загружена», «Здесь часто случаются ДТП» и т. д.).
Неподвижная точка. Практика
Все, описанное выше, — теория. В реальности получается, что распределение потоков тоже влияет на матрицу корреспонденций (чтобы выяснить, сколько потребуется, чтобы переместиться из одного района в другой, нужно знать загрузку дороги). На практике эта задача решается следующим образом: ищется неподвижная точка. Это математический термин, который в данном случае обозначает точку соответствия ожидания и реальности (именно так, кстати, и работают навигаторы, которые знают и текущее состояние дел на дороге, и теоретическую длину пути).
То, что неподвижная точка существует, — известно, но то, что распределение потоков и матрица корреспонденций будут сходиться к этой неподвижной точке, пока не было строго обосновано.
В докторской диссертации А. В. Гасникова (руководитель — член-корреспондент РАН профессор А. А. Шананин, научный консультант — профессор Ю. Е. Нестерова) обоснование такой конструкции дано. Гасниковым предложена альтернативная схема, которая гарантированно сходится к нужной неподвижной точке. Причем сходится быстрее и на практике (во всяком случае, в тех экспериментах, которые удалось провести). Теперь эти теоретические решения можно применять к российской реальности.
В докторской диссертации А. В. Гасникова (руководитель — член-корреспондент РАН профессор А. А. Шананин, научный консультант — профессор Ю. Е. Нестерова) обоснование такой конструкции дано. Гасниковым предложена альтернативная схема, которая гарантированно сходится к нужной неподвижной точке. Причем сходится быстрее и на практике (во всяком случае, в тех экспериментах, которые удалось провести). Теперь эти теоретические решения можно применять к российской реальности.
