Моделирование Транспортной Сети Города
Введение в задачу
  • 1
    Применение
    Чтобы принимать взвешенные решения о модернизации транспортной инфраструктуры (например - строительство новой дороги) необходимо уметь моделировать транспортные потоки
  • 2
    Существующие решение
    До этого данная задача решалась с помощью иностранных транспортных пакетов и не современными методами
  • 3
    Актуальность исследования
    Для поддержки технологического суверенитета страны актуальна разработка собственных транспортных пакетов
Зная характеристики районов и дорог транспортной сети мы хотим определить объём перемещений между районами и потоки на дорогах в условиях равновесия.
Цель нашего исследования - реализовать и сравнить различные алгоритмы поиска равновесия транспортной модели
Предлагаем познакомиться с парадоксом Браеса: при добавлении новой дороги в транспортную сеть общие издержки водителей увеличились
В видео мы искали состояние равновесия, но делать это для больших городов, например, для Москвы, гораздо сложнее. Транспортные пакеты направлены на то, чтобы решать такую задачу.
транспортная задача может быть
представлена как задача оптимизации

Нам дано число жилых мест l и рабочих мест w для каждого района и граф транспортной сети. На выходе мы хотим определить объем перемещений из района i в район j: dij и кол-во перемещений по всем дорогам (рёбрам) f.

Tij - это минимальные затраты на пути из района i в район j, для определений кратчайшего пути запускается алгоритм Дейкстры из всех истоков.
Важные характеристики задачи
  • задача выпуклая;
  • оптимизация функции по трем введённым двойственным переменным: λ, μ, t;
  • функция негладкая по блоку t (затраты на рёбрах); расчёт градиента вычислительно затратен, так как надо определять кратчайшие пути на графе;
  • функция гладкая по блоку λ, μ; расчет градиента вычислительно не затратен;

Математическая модель
  • по двойственным переменным можно восстановить прямые: по λ, μ можно восстановить матрицу перемещений;
  • t - затраты на рёбрах графа, по ним можно восстановить потоки по рёбрам, просуммировав корреспонденцию по кратчайшим путям;

Восстановление матрицы перемещений по λ, μ
Тестовая задача
чтобы проверить эффективность покомпонентных методов
была введена "искусственная" задача
Важные характеристики задачи
  • у нас есть два блока переменных x, y;
  • по одному блоку задача гладкая - по другому блоку нет;
  • по гладкому блоку градиент раcсчитывается вычислительно сложнее; (dim(x) ≪ dim(y))
  • параметр γ определяет гладкость задачи по блоку x;

Математическая модель тестовой задачи
Алгоритмы оптимизации
были реализованы и сравнены 3 различных алгоритма
  • Universal Method of Similar Triangles
    USTM
    Универсальный адаптивный градиентный метод, включающий ускорение Нестерова
  • Universal Method of Similar Triangles + Sinkhorn
    USTM + Sinkhorn
    Применяем USTM по блоку t и
    решаем задачу по λ и μ с помощью
    алгоритма Синхорна
  • Accelerated by Coupling Randomized Coordinate Descent
    ACRCD*
    Ускоренный
    блочно-покомпонентный метод позволяет учитывать специфику задачи, выполняя градиентный шаг за раз только по одному блоку
Эксперименты
Мы провели тестирование алгоритмов на реальных данных транспортных сетей городов Су-Фолс, Анахайм
и на тестовой "искусственно" созданной задаче
Визуализация экспериментов
Были построены графики: кол-во вызовов расчёта градиентов в зависимости от значения метрики.
  • чем выше метрика - тем лучше.
  • чем меньше кол-во оракульных вызовов - тем лучше

Графики
  1. Город Анахайм
  2. Город Су-Фолс
  3. Тестовая задача


Можно заметить что на транспортной задаче (1, 2) покомпонетный метод работает сравнимо с USTM, но значительно хуже USTM+Sinkhorn.
Для тестовой задачи (3) ситуация обратная - такого же значения метрики можно достичь за гораздо меньшее кол-во обращений к "дорогому" оракулу.
Результаты и выводы
  • 1
    Транспортная задача
    Результаты показали, что из-за того, что оракул по негладкому блоку сильно дороже оракула по гладкому, эффект от расщепления оракулов покомпонентными методами наблюдается не так сильно
  • 2
    Покомпонентные методы
    Продемонстрирована возможность уменьшения времени оптимизации задач определенного класса за счет расщепления оракульной сложности
  • 3
    Масштабирование
    Один из вариантов продолжения работы над проектом - добавление адаптивности по каждому блоку переменных в метод ACRCD
Наша команда
Те, кто
  • Гасников Александр
    Руководитель проекта
  • Ярмошик Демьян
    Руководитель проекта
    yarmoshik.dv@phystech.edu
  • Ильтяков Никита
    Math, transport model, USTM
    iltyakov.nik@mail.ru
  • Обозов Марк
    Math, ACRCD*
    obozovmark9@gmail.com
  • Дышлевский Игорь
    Math, USTM + Sinkhorn
    igordyslevski@gmail.com

© Катарсис