Не так давно на хабре вышла статья про алгоритмы маршрутизации в продуктах 2ГИС. Я продолжу рассказ коллеги, объяснив по каким принципам в ПК-версии мы ищем оптимальный по времени маршрут для автомобиля. Тут хотелось бы напомнить, что ПК-версия 2ГИС работает без подключения к интернету.
Начнём с того, что искомому маршруту из точки А в точку В могут предъявляться различные требования:
— длина маршрута (кратчайший);
— время движения по маршруту (с учётом пробок);
— промежуточные точки (предпочтения на маршруте) и т.п.
Текущий алгоритм маршрутизации поддерживает два типа маршрутов — оптимальный по длине (кратчайший по расстоянию) и оптимальный по времени (кратчайший по времени проезда). Если с критерием оценки кратчайшего по расстоянию маршрута все понятно, то правильно оценить время проезда в современном городе, перегруженном транспортом, часто весьма затруднительно. Время проезда по одному и тому же маршруту может существенно отличаться в зависимости от времени суток, дня недели, проводимых ремонтных работ, погодных условий, аварий и т.п. Другими словами, при прокладке маршрута оптимального по времени необходимо уметь достаточно точно оценивать текущую ситуацию на дороге или уметь достаточно близко её аппроксимировать.
В связи с этим возникла достаточно естественная идея: при поиске маршрута, оптимального по времени, использовать статистику, накапливаемую сервисом Пробки (Новосибирск). Эта статистика отражает загруженность дорог в зависимости от времени суток, дня недели и сезона. При этом в случае онлайн-версии сервиса поиска проезда появляется возможность использовать самые свежие данные, которые дополнительно могут учитывать проводимые ремонтные работы, погодные условия и аварии. Далее в данной статье пойдет речь об использовании такой информации при поиске проезда в офлайн-продуктах.
Сбор статистики
Все начинается со сбора статистики о пробках. Она собирается по всем ребрам дорожного графа города и накапливается для каждых 15 минут каждого дня недели. Подготовка статистики состоит из двух основных этапов:
- Накопление данных по дням недели. Все точки от устройств, собранные за день, группируются по рёбрам графа и 15-минутным временным интервалам. Далее для каждого ребра по каждому временному интервалу выполняется усреднение скорости. Будем называть такую статистику первичной. Она хранится в базе данных для последних 4-х недель. Данные, старше 4-х недель, удаляются.
- Агрегирование накопленных данных. После добавления данных за новый день выполняем перерасчет т.н. статистики «Обычно» за соответствующий день недели.
Для фиксированного дня недели, для всех рёбер дорожного графа, которые участвуют в расчете пробок, и для каждого 15-минутного временного интервала:
- Извлекаем первичную статистику этого дня за последние 4 недели:
— средняя скорость на ребре,
— общее число точек от устройств на данном ребре,
— общее число устройств, от которых пришли точки. - Складываем с разными весовыми коэффициентами скорости за все 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. Это даёт возможность использовать её в офлайн-продуктах. Рассмотренный пример показывает, что оптимальный по времени проезда маршрут согласуется с наблюдаемой в указанный момент времени картиной пробок (объезжаем более медленные участки, через которые проходит кратчайший маршрут).
Автор: ILOT
