Учёт статистической информации о пробках при поиске проезда на автомобиле

    Не так давно на хабре вышла статья про алгоритмы маршрутизации в продуктах 2ГИС. Я продолжу рассказ коллеги, объяснив по каким принципам в ПК-версии мы ищем оптимальный по времени маршрут для автомобиля. Тут хотелось бы напомнить, что ПК-версия 2ГИС работает без подключения к интернету.



    Начнём с того, что искомому маршруту из точки А в точку В могут предъявляться различные требования:
    — длина маршрута (кратчайший);
    — время движения по маршруту (с учётом пробок);
    — промежуточные точки (предпочтения на маршруте) и т.п.

    Текущий алгоритм маршрутизации поддерживает два типа маршрутов — оптимальный по длине (кратчайший по расстоянию) и оптимальный по времени (кратчайший по времени проезда). Если с критерием оценки кратчайшего по расстоянию маршрута все понятно, то правильно оценить время проезда в современном городе, перегруженном транспортом, часто весьма затруднительно. Время проезда по одному и тому же маршруту может существенно отличаться в зависимости от времени суток, дня недели, проводимых ремонтных работ, погодных условий, аварий и т.п. Другими словами, при прокладке маршрута оптимального по времени необходимо уметь достаточно точно оценивать текущую ситуацию на дороге или уметь достаточно близко её аппроксимировать.

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

    Сбор статистики


    Все начинается со сбора статистики о пробках. Она собирается по всем ребрам дорожного графа города и накапливается для каждых 15 минут каждого дня недели. Подготовка статистики состоит из двух основных этапов:
    1. Накопление данных по дням недели. Все точки от устройств, собранные за день, группируются по рёбрам графа и 15-минутным временным интервалам. Далее для каждого ребра по каждому временному интервалу выполняется усреднение скорости. Будем называть такую статистику первичной. Она хранится в базе данных для последних 4-х недель. Данные, старше 4-х недель, удаляются.
    2. Агрегирование накопленных данных. После добавления данных за новый день выполняем перерасчет т.н. статистики «Обычно» за соответствующий день недели.




    Для фиксированного дня недели, для всех рёбер дорожного графа, которые участвуют в расчете пробок, и для каждого 15-минутного временного интервала:
    1. Извлекаем первичную статистику этого дня за последние 4 недели:
      — средняя скорость на ребре,
      — общее число точек от устройств на данном ребре,
      — общее число устройств, от которых пришли точки.
    2. Складываем с разными весовыми коэффициентами скорости за все 4 недели. У каждой недели свой весовой коэффициент, который зависит от актуальности данных (те, что за последнюю неделю, как самые свежие, имеют максимальный вес) и их достоверности (количество устройств и количество пришедших от них точек на конкретном ребре).


    Текущую статистику «Обычно» по Новосибирску можно посмотреть на сервисе Пробки — основное предназначение этой статистики. Вектор статистических скоростей на ребре за неделю, разбитую на 15-минутные интервалы времени, будем называть временным профилем данного ребра. Временной профиль характеризует динамику изменения скорости на ребре в течение недели (удобно изображать в виде графика) и состоит из 672 элементов. При этом, каждый из элемент является целым однобайтовым числом и равен скорости на данном ребре в соответствующий 15-минутный временной интервал.

    Метод анализа данных


    Прямое использование статистики «Обычно», для оценки времени проезда по маршруту, на практике затруднительно. Дорожный граф крупного города состоит из десятков и сотен тысяч рёбер. Хранить отдельный временной профиль для каждого ребра очень дорого, или даже невозможно. Для обхода этой проблемы было решено объединить все имеющиеся временные профили в небольшое число классов. Каждый такой класс — это усредненный сглаженный временной профиль, описывающий динамику скорости транспортного потока на некоторой группе рёбер дорожного графа. Далее все ребра графа распределяются между выделенными классами (классифицируются), а процедуры маршрутизации вместо временных профилей рёбер могут работать с временными профилями классов рёбер.

    Для построения классов временных профилей рёбер использовался факторный анализ. Выбор данного метода обусловлен возможностями факторного анализа по выявлению скрытых (но предполагаемых) закономерностей в изучаемом процессе, выявлению статистических связей и сжатию информации путем описания исходного процесса при помощи общих факторов, число которых (существенно) меньше числа первоначально взятых признаков. У нас первоначальные признаки — это временные профили рёбер, а общие факторы — классы временных профилей.

    Классификация временных профилей рёбер


    Использование факторного анализа можно условно разделить на три основных этапа.

    1. Ковариационная матрица

    Анализ начинается с построения матрицы ковариаций временных профилей рёбер, которая необходима для выделения факторов. Обозначим временной профиль ребра вектором v=(v[1],...,v[m]), где v[i] — скорость транспортного потока на ребре в момент времени i = 1,..., m. Сейчас временной период статистики «Обычно» составляет 1 неделю с 15-минутной дискретизацией, что дает m = 7 × 24 × 60 / 15 = 672.

    Матрица ковариаций временных профилей имеет следующий вид, где E — это математическое ожидание:


    2. Декомпозиция исходной задачи

    Для построения искомых классов временных профилей требуется найти собственные векторы и собственные значения ковариационной матрицы — по сути всё сводится к решению систем линейных уравнений. На практике полная матрица ковариаций для такого города, например, как Новосибирск будет занимать порядка 6 Gb. С другой стороны, все современные алгоритмы поиска собственных значений и векторов матриц имеют кубичную сложность от размерности матрицы. Кроме того, при увеличении размерности матрицы возрастает погрешность вычислений.

    Для обхода перечисленных выше препятствий было решено строить матрицы ковариаций для фрагментов дорожного графа. Экспериментально мы определили, что для наших данных использование матриц размерности, желательно, не больше 1 000 позволяет получить качественные результаты для каждой выборки за приемлемое время. При этом дорожный граф разбивается на относительно небольшое число таких фрагментов – порядка нескольких десятков. Разделение дорожного графа на фрагменты (подмножества рёбер) выполняется динамически при каждом запуске процедуры классификации временных профилей.

    3. Построение классов временных профилей

    Для каждого подмножества, полученного в результате декомпозиции исходной задачи, строится матрица ковариаций, для которой требуется найти собственные векторы и собственные значения. Для этого используется библиотека линейной алгебры Eigen, показавшая лучшую производительность и качество счёта на наших задачах. Не будем сильно углубляться в используемые вычислительные процедуры и их математическое обоснование (желающие могут обратиться к специальной литературе). Только отметим, что собственные числа и векторы необходимы для определения т.н. факторов (терминология факторного анализа) — результат объединения сильно коррелирующих между собой временных профилей. В нашей задаче факторы по построению сами являются временными профилями, полученными как линейная комбинация коррелирующих между собой временных профилей исходных рёбер.

    Следующий шаг классификации заключается в ранжировании всех построенных факторов по значимости. Для этого все временные профили рёбер, составляющих обрабатываемый фрагмент дорожного графа, распределяем между факторами — профиль относится к тому фактору, от которого имеет минимальное отклонение. Отклонение считается по методу наименьших квадратов. В результате каждый фактор получает ранг — число соотнесенных с ним временных профилей. Фактор с наименьшим рангом отбрасывается, а соотнесенные с ним временные профили распределяются между оставшимися факторами.

    Описанная процедура продолжается до тех пор, пока не останется необходимое нам число наиболее значимых фактоов, между которыми уже распределены все временные профили рёбер из данного фрагмента графа. Такие оставшиеся факторы становятся классами, а соотнесенные с ними ребра получают свои классы — временные профили факторов.

    Пример построенных классов для фрагмента дорожного графа Новосибирска представлен на рисунке ниже. По оси X изменяется время в минутах с начала недели, по оси Y — скорость в км/ч. График класса показывает изменение скорости на ребрах данного класса с течением времени за неделю. Колебания графика отражают зависимость скорости транспортного потока от времени суток на ребрах данного класса. Из рисунка видно, что построенные классы заметно отличаются по своим характеристикам – каждому классу соответствует собственный диапазон скоростей.



    В общей сложности для Новосибирска получается порядка 100 подобных классов. Распределение всех временных профилей рёбер по этим классам да1т возможность хранить вместо исходных профилей достаточно компактный набор классов, занимающий на диске всего ~65–70 Кb. Мы называем такой набор классов матрицей скоростей.

    Матрица скоростей в алгоритме маршрутизации


    Подготовка матрицы скоростей является частью процедуры подготовки дорожного графа, а сама матрица — часть бинарного файла, в который упаковывается дорожный граф. Алгоритм поиска маршрута на графе был подробно описан в прошлой статье. Скорость из матрицы скоростей используется при оценке накопленного времени проезда на просмотренных ребрах. Таким образом, данная информация становится ключевой при поиске маршрутов, оптимальных по времени проезда с учётом пробок.

    Рассмотрим типичную картину пробок в Новосибирске в понедельник в 18:00 местного времени (статистика «Обычно»):


    Сравним два маршрута из точки A в точку B — кратчайший по расстоянию и оптимальный по времени проезда. Кратчайший маршрут: длина — 7 330 метров, время проезда с учётом информации о пробках — 1 347 секунд:



    Маршрут, оптимальный по времени проезда: длина — 8 033 метра, время проезда с учётом информации о пробках — 1 295 секунд:



    Таким образом, описанная техника позволяет «упаковать» статистическую информацию о скоростях на десятках тысяч рёбер дорожного графа в относительно небольшой объект объемом ~65–70 Кb. Это даёт возможность использовать её в офлайн-продуктах. Рассмотренный пример показывает, что оптимальный по времени проезда маршрут согласуется с наблюдаемой в указанный момент времени картиной пробок (объезжаем более медленные участки, через которые проходит кратчайший маршрут).
    2ГИС 224,23
    Карта города и справочник предприятий
    Поделиться публикацией
    Похожие публикации
    Комментарии 22
    • –8
      А оффлайн версия под андройд есть?
    • +4
      Даешь алгоритм предсказания пробок для офлайн режима!))
      • +4
        Интересный и познавательный рассказ!

        Сколько всего специалистов вашего уровня существует в стране и как информация о пробках используется для их искоренения?
        То есть, существуют стабильно «узкие» места. Обращаются ли к вам (подобным фирмам) градостроительные организации — для долгосрочного строительства, и сотрудники ГИБДД — для оперативного регулирования ситуации при помощи знаков, указателей, изменения режима работы светофоров...?
        • +5
          Сколько всего специалистов вашего уровня существует в стране и как информация о пробках используется для их искоренения?
          Не искореняйте специалистов, пожалуйста.
          • +1
            Мне почему-то кажется, что у наших градостроительных организаций и гидбб совсем другие интересы
          • +4
            А учитывает ли алгоритм время движения или все расчеты только на момент построения маршрута? То есть если у меня длинный маршрут на 2 часа и строю я маршрут в 7 утра, а на середине маршрута я окажусь в 8 утра, когда все поедут на работу и будет час-пик, то учтет ли это алгоритм в 7 утра при построении маршрута?
            • +2
              Да, алгоритм учитывает время движения.
              Алгоритм построения маршрута подробно был описан в статье (раздел «Собственно поиск», вычисление стоимости достижения новой точки). Я не стал здесь дублировать описание алгоритма, чтобы не перегружать статью и не повторяться. Лишь отметил, что в данном случае «скорость из матрицы скоростей используется при оценке накопленного времени проезда на просмотренных ребрах». Таким образом, вычисление стоимости достижения очередной точки выполняется с учетом накопленного времени.
            • –1
              Это прекрасно, но почему при прокладке маршрута с учётом пробок навигационное ПО совсем не учитывает, что моё перемещение займёт некоторое время и картина пробок за это время может существенно измениться!
              Например: выезжая в 17-00 я вижу на экране навигатора, что город относительно свободен и маршрут прокладывается почти напрямую, но проехав около получаса я оказываюсь в пробке, потому что у людей закончилась работа и половина моего маршрута предсказуемо покраснела…
              Ведь это вполне реально предсказать и проложить маршрут с учётом пробок, которые могут появится.
              • +1
                Наш алгоритм как раз учитывает — с каждым пройденным ребром дорожного графа время накапливается. Здесь ответил чуть подробнее: habrahabr.ru/company/2gis/blog/193116/#comment_6707044
                • +3
                  хотелось бы отметить, что 2ГИС это не совсем навигатор и никогда не позиционировался как таковой.
                  но предсказание пробок, построение маршрута с учетом текущих онлайн-пробок и прочие вкусные плюшки находятся в разработке и будут появляться во всех наших продуктах, включая оффлайновые.
                • +1
                  На данный момент все реализации алгоритмов постройки маршрутов в пробках не учитывают того факта, что скорость движения транспорта в соседних полосах одного потока может быть разной. В следствие чего, по одной дороге можно проехать быстрее, если правильно выбрать полосу движения, чем в другой, которую предлагает алгоритм исходя из меньшей средней скорости движения всего потока.
                  Например, я знаю, что на определенной дороге, левая полоса почти всегда стоит, а правая продвигается, пусть со скоростью 10 км/ч. Какова расчетная средняя скорость потока? Алгоритмы обычно предлагают другой вариант, где скорость потока будет 7 км/ч, и она одинакова для всех полос.
                  • +5
                    Да, вы правы. И у нас тоже нет разделения дороги на полосы движения. Объяснение тут простое — исходные данные (GPS-точки), которые мы используем для расчета пробок, не позволяют достаточно точно позиционировать положение автомобиля, чтобы можно было привязывать точки еще и к полосам движения.
                    • 0
                      Да, я понимаю что точность координат недостаточна, но как насчет варианта распознавания разных групп точек двигающихся с разной скоростью? Например у вас есть данные, что на определенном участке дороги есть точки, двигающиеся со скоростью 5-10 км/ч и 20-25 км/ч. Можно сделать вывод о том что движение идет по двум полосам с различной скоростью. Есть статистические алгоритмы позволяющие определять такие группы. Конечно остается еще задача определения сторон этих полос (какая левая, какая правая), но даже такая неполная информация была бы полезна: вывод на карту того, что на данном участке движение идет с разной скоростью.
                      • +2
                        Такие мысли, конечно, возникали. Проблема в том, что на подавляющем большинстве дорог у нас недостаточно точек в единицу времени, чтобы среди них еще достоверно выделять группы точек с устойчиво различным поведением/скоростью на данном участке дороги. А поскольку в Пробках нет разделения на полосы, то и алгоритм поиска проезда в оффлайн-продуктах также не учитывает число полос — есть только разделение дорог по классам. Возможно в будущем ситуация с количеством/качеством данных измениться, но в любом случае разделение на полосы сначала должно появиться в онлайн-сервисе Пробки, а потом уже можно думать над использованием этой информации в оффлайн-продуктах.
                    • 0
                      Я буду обновлять коментарии перед отправкой. Я буду обновлять коментарии перед отправкой. Я буду обновлять коментарии перед отправкой.
                    • 0
                      А вообще планируется ли сделать навигатор на основе 2ГИС? С удовольствием бы пользовался.
                    • +1
                      А планируется добавление украинских городов?

                      Читаю ваши статьи и очень нравится ваш продукт, в частности android-приложение, но Днепропетровска нет :(. Из украинских городов, я так понял, есть карта только Донецка и Одессы (неожиданный набор, даже Киева нет).

                      Добавляйте города! Пусть пока без 3D-зданий, но хоть с картой.
                      • 0
                        А у меня другой вопрос.
                        Вот Вы рассчитываете маршрут с учетом пробок и с учётом времени проезда между ребрами.
                        А пытались ли Вы оценить, не создадите ли вы пробку на небольшой улочке, которая обычно свободна, но Вашей программой уже пользуется много народа, и все ломанутся именно по ней?
                        • 0
                          Сложно это предсказывать. Но вполне логично когда возникает пробка на основной дороге, через несколько десятков минут возникнет и на дороге дублере.
                          • 0
                            Я немного о другом.
                            Люди пользуются вашим оффлайн приложением. На основной дороге пробки нет, но Ваши пользователи старательно забивают улочку.
                            Как часто вы обновляете данные для «обычной» загрузки улиц?

                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                        Самое читаемое