[Из песочницы] Как создать мультиагентную транспортную модель
Привет, Хабр!
Представим, что у нас есть задача построить новую дорогу. Можно построить магистраль с двумя полосами в каждую сторону, но что, если этого будет недостаточно? Или, наоборот, окажется, что хватило бы и одной полосы, но для реализации проекта пришлось выкупать множество земельных участков? В обоих случаях принятое решение будет неэффективным. Чтобы минимизировать подобные риски, транспортные планировщики обращаются за помощью к компьютерному моделированию. Эта статья — краткий экскурс в мир мультиагентного моделирования.
С помощью модели, которая представляет собой копию реальной транспортной системы, можно оценить необходимую пропускную способность на каждом участке проектируемой дороги, попробовать различные варианты трассировки или, например, прикинуть срок окупаемости проекта, если речь идет о платной дороге в рамках государственно-частного партнерства. Но могут быть решены и другие немаловажные задачи: как организовать оптимальные маршруты общественного транспорта и посчитать потенциальную выручку операторов, как оценить наличие дефицита парковочных мест в том или ином районе и многие другие.
Что самое интересное — построить подобную модель в эпоху свободного ПО может каждый!
Одним из самых распространенных инструментов для мультиагентного моделирования является программа с открытым исходным кодом MATSim (Multi-Agent Transport Simulation).
В MATSim симулируется поведение отдельных агентов. Агент — это компьютерное представление отдельного жителя в реальном мире. У каждого такого агента есть дневной план, на основании которого он перемещается от одной активности к другой (например, дом-работа-дом, дом-институт-работа-дом, дом-магазин-работа1-работа2-дом и др.), создавая таким образом спрос на дорожную инфраструктуру. Схематичное представление дневного плана выглядит примерно так:
Для создания реалистичных планов агентов, которые будут отражать реальное поведение людей в течение дня, принимается во внимание общее число жителей-агентов, их расселение, места работы, учебы, расположение магазинов, торговых центров, вокзалов и иных мест активностей. Для валидации спроса также производится калибровка модели на основании натурных обследований: распознавание и подсчет потоков камер видеонаблюдения и дронов с помощью нейросети или, например, ручные замеры интенсивности на дорогах.
В ходе симуляции агенты распределяются по сети, имитируя реалистичное поведение людей: осуществляя свой план автомобили занимают место на дороге и парковочные места, пользователи общественного транспорта занимают места в автобусе, а еще взаимодействуют друг с другом и, в случае единовременного выбора множеством агентов одной дороги, создаются пробки и заторы. Все как в реальном мире!
После завершения симуляции происходит оценка выполнения дневных планов агентов, называемая скоринг. Агент приобретает единицы полезности в процессе осуществления активности и теряет их во время перемещений. Соответственно, агенты, оказавшиеся в заторе, теряют больше единиц полезности, нежели агенты, передвигающиеся по свободным дорогам.
Часть агентов после каждой итерации перестраивает свой план на основании сведений о загрузке улично-дорожной сети таким образом, чтобы улучшить свои показатели: агенты могут изменить время выезда, поменять вид транспорта или сменить маршрут. Остальные агенты придерживаются своих предыдущих планов, которые хранятся в памяти программы.
В идеале после симуляции должно быть достигнуто равновесие Нэша — то есть ситуация, когда ни один агент не может улучшить свое положение, не ухудшив положение других агентов. Обычно именно такая ситуация складывается с течением времени на дорогах города, учитывая ежедневное переосмысление опыта предыдущего дня его жителями. Для этого в рамках одного сценария проводится не менее 200 итераций. Весь цикл работы MATSim выглядит примерно так:
От теории — к практике!
Для запуска первого сценария нам потребуется Intellij IDEA (или Eclipse) с Java 1.8 на борту.
Открываем IDE, клонируем репозиторий MATSim с гитхаба и наш первый сценарий уже готов к запуску! Вот так просто. Но давайте сначала посмотрим, какие входные файлы мы используем. Для самой простой симуляции их три: network, plans, config.
Network
Файл network представляет из себя сеть, по которой передвигаются агенты. Он состоит из узлов (nodes) и ребер/линков (links). У каждого линка задаются различные атрибуты: тип, длина отрезка, пропускная способность, максимальная скорость движения, количество полос, наличие одностороннего движения, разрешенные виды транспорта и др.
Создавать сетку города вручную сложно, непрактично и неэффективно. Например, наша сетка Петербурга состоит из 26 тысяч узлов и 46 тысяч линков. Но есть и хорошие новости. Сетку можно конвертировать из OpenStreetMap и затем редактировать с помощью JOSM, который также open-source.
Plans
Файл plans — это структурированное представление дневных планов агентов. В начальном сценарии у нас есть 100 агентов, которые выезжают на машине (mode=«car») утром (end_time=»05:59») из дома (type=«h», link=»1») на работу (type=«w», link=»20»), после чего спустя какое-то время (dur=»02:30») возвращаются домой.
Config
Наконец, в файле config задаются все необходимые настройки для запуска сценария. MATSim состоит из модулей, которые можно настраивать, добавлять или удалять при необходимости.
Многие настройки в файле config интуитивно понятны, но также всегда можно заглянуть в т. н. MATSim Book. Сейчас рассмотрим только два модуля.
В модуле planCalcScore задаются параметры скоринга: так, за опоздание (lateArrival) агент получает штраф в размере 18 ед. полезности в час (соответственно, опоздание на 10 минут эквивалентно потери 3 ед. полезности); выполнение какой-то активности (например, работы (performing) приносит 6 ед. полезности в час, а передвижение на авто имеет издержки в размере тех же 6 ед. полезности в час. Для поиска реалистичных параметров скоринга чаще всего используются соцопросы для анализа «стоимости времени».
В модуле strategy настраиваются параметры перепланирования, например, какая доля агентов (ModuleProbability) попробует новый маршрут (ReRoute) в ходе следующей итерации.
Таким образом, цель симуляции — помочь агенту добраться из точки A в точку B с наименьшими затратами.
Запуск сценария
Время открывать раннер RunMatsim и запускать наш первый сценарий!
Результаты симуляции будут лежать в папке output в корне проекта. Основные файлы для визуализации — network и events. Файл events содержит посекундную информацию обо всех действиях каждого агента, поэтому на основе этого файла можно восстановить полную картину передвижения всех агентов. Визуализировать результаты можно с помощью Via.
Для более показательных результатов я увеличу количество агентов до 500. Вот так выглядит распределение 500 агентов после первой итерации…
В начале итерации агенты просчитали наиболее короткий путь с помощью Dijkstra, в результате чего интенсивность движения на одном участке сети превысила его пропускную способность, образовался затор. Но что, если дать им возможность попробовать разные маршруты?
После 200 итераций (~5 минут) агенты перераспределились по сети, уровень загрузки линков теперь не превышает 0.5, а среднее время в пути для всех агентов снизилось на 14% (5 минут). Ура, мы побороли пробку!
Ох, если бы все было так просто! В реальности же транспортные системы намного сложнее. В следующих статьях я расскажу, как участвовал в разработке моделей Санкт-Петербурга и других городов и как мы решали практические задачи на реальных кейсах. Scientia potentia est!
Автор — Андрей Коломацкий, транспортный аналитик в ОТСЛаб.
