Информация о пробках появилась на Яндексе в 2006 году.
Начали с необходимого - узнали построить диаграмму рабочей нагрузки улицы города и учитывать текущую ситуацию при планировании маршрутов .
Автомобилисты, ориентируясь на эту информацию перед выездом, уже могли сэкономить время в пути: 
Затем, чтобы помочь водителям непосредственно во время вождения, мы добавили мобильные Яндекс.
Карты (и, как следствие, в Яндекс.
Навигатор ) автоматическая реструктуризация маршрута.
Приложения научились адаптировать маршрут при каждом заметном изменении ситуации в городе.
Собрав информацию о «сейчас» на десктопе и мобильном, мы перешли к решению вопроса «что будет потомЭ»: 
Первым шагом было статистическая карта трафика - на нем можно увидеть, как стоит и едет город в среднем в конкретный час конкретного дня недели.
Мы предположили, что карта «обычных» пробок может иметь полезный побочный эффект — возможность использовать их для прогнозирования заторов в ближайшем будущем.
Но практика показала, что усредненная картинка помогает лишь примерно спланировать, например, завтрашнюю поездку в аэропорт – но не помогает выезжающим сейчас избежать новых пробок.
По нашим замерам, даже в конце часового маршрута картина пробок на момент выезда обычно ближе к реальной, чем в среднем: 
Неделю назад появился на Яндекс.
Картах возможность увидеть изменения в пробках в ближайший час — наш следующий шаг в решении вопроса будущего.
Для тех, кто не смог присутствовать в этом году Еще одна конференция , сегодня мы расскажем вам, что находится внутри нашего прогноза и как он туда попал.
Собственно, задача
Прогнозируем изменения средней скорости движения на разных участках дорог.Технически дорожная карта — это график.
Каждый перекресток является вершиной этого графа, а участки дороги между двумя перекрестками — ребрами.
Последние имеют атрибут «длина» и атрибут «скорость».
Длина, конечно, известна заранее, а скорость рассчитывается в реальном времени — в зависимости от нее участок дороги окрашивается в зеленый, желтый и красный цвета.
На самом деле, это второй атрибут, который мы намеревались предсказать.
Конечно, не мы придумали эту задачу; Над этим работают различные специалисты по всему миру.
В России, например, над моделированием и прогнозированием движения работают авторы учебника по одному из основных направлений в этой области - «Введение в математическое моделирование транспортных потоков» .
И хотя тема известна довольно давно, автомобильная навигация, использующая прогнозы на основе свежих данных, пока не доступна российским пользователям.
Лишь в редких случаях при построении маршрута учитывается средняя статистика пробок.
Во всем мире прогнозы заторов используются для автоматическое регулирование дорожного движения в некоторых городах.
Появились первые прототипы, в которых применялись предсказания появился в 1998 году в США.
И первое пилотное применение системы, «смотрящей в будущее» началось в 2006 году в Сингапуре.
Впервые мы коснулись прогнозирования на интернет-конкурсе «Математика» в 2010 году.
Этот опыт помог нам понять, как следует ставить задачу и какие данные нужны для достижения хорошего результата.
Источник данных
Во многих странах используются стационарные датчики расхода, которые измеряют скорость и плотность движения на ключевых автомагистралях.Это хороший источник чистых данных о пробках на дорогах, но для покрытия даже одной Москвы потребуются огромные инвестиции.
Мы ограничились обезличенными GPS-треками, которые приходят от пользователей мобильных Карт и Навигатора.
Каждый трек представляет собой цепочку сигналов о местоположении (широте и долготе) автомобиля в определенное время.
Мы привязка GPS-треков к дорожному графику , то есть определяем, по каким улицам они прошли.
Затем мы усредняем скорость всех путей, проходящих по одним и тем же краям.
Эти данные имеют ряд особенностей, которые затрудняют получение качественного прогноза.
Бытовые GPS-устройства определяют координаты с ошибкой, поэтому треки очень зашумлены.
Это усложняет не только расчет средней скорости, но и привязку треков к графику, например, когда дороги расположены близко друг к другу: 
Кроме того, иногда на некоторых улицах мало машин, передающих данные.
Да и сама ситуация на дорогах не всегда стабильна.
Например, полосы шоссе движутся с разной скоростью, поэтому на одном и том же участке пути могут одновременно показывать существенно разные скорости.
Выбор метода
В этой области используются самые разнообразные методы.Среди них: Модель параметрической регрессии .
Он заранее предполагает определенный тип функции в зависимости от В будущее = Ф ( В прошлое , В текущий ), а параметры выбираются в Ф .
Особенность модели в том, что выбор функции накладывает ограничения на результат. С одной стороны, это защищает от серьезных ошибок, неизбежных при использовании зашумленных данных — параметрическая функция позволяет уменьшить разброс прогнозируемых значений.
С другой стороны, если функция выбрана неправильно, модель может давать систематически неправильные ответы.
Непараметрическая модель ( "k ближайших соседей" ).
Он просто ищет в прошлом ситуацию, аналогичную нынешней, и в качестве прогноза дает, как развивались события дальше.
Эта модель более гибкая — используя ее, можно сказать: «Если после затишья 10 раз возникла буря, то после нового затишья тоже будет буря».
Если, например, мы возьмем линейная функция в параметрической модели , мы не сможем этого предсказать, так как ограничены гипотезой, что будущее может быть только линейной комбинацией прошлого.
Однако на зашумленных данных линейная модель обеспечивает большую точность, чем непараметрическая.
Другая классификация методов регрессии основана на скаляр И вектор .
В первом предполагается, что ситуация в выбранном районе не зависит от того, что происходит в соседних; во втором, наоборот, учитываются зависимости.
Отсюда и разница в объёмах вычислений.
Если в городе 10 тысяч участков дорог, то для построения скалярной модели достаточно выбрать 10 тысяч параметров.
А для векторной модели может понадобиться до 100 миллионов параметров.
В нашем случае очевидно, что ситуации в разных сферах влияют друг на друга.
И ключевым вопросом становится, как ограничить круг соседей, чтобы расчет завершился в разумные сроки.
Методы моделирования потока учитывать природу процесса, а не просто оперировать абстрактными цифрами.
Используется уравнение течения жидкости с переменной вязкостью: выше плотность – ниже скорость.
Методы широко используются при планировании дорог и перспективны для прогнозов, но слишком требовательны к точности и полноте данных.
Они обеспечивают хорошее качество на потоковых датчиках, но почти не работают на «шумных» GPS-треках.
Поэкспериментировав с различными методами и оценив их точность и вычислительную сложность, мы остановились на линейной векторной авторегрессии.
Он предполагает, что будущая скорость представляет собой линейную комбинацию текущей и нескольких прошлых скоростей на нескольких участках: непосредственно на рассматриваемом, а также на соседних.
Что и как рассчитывается
Наша модель обучается один раз в день.На основе развития событий за определенный период времени в прошлом она строит прогноз.
Этот прогноз сравнивается с последующим развитием событий.
Модель подбирает коэффициенты, чтобы минимизировать расхождение между прогнозом и тем, как все обернулось на самом деле.
Для каждого времени суток система рассчитывает свои коэффициенты, поскольку в течение суток характер движения транспорта незначительно меняется.
Каждые несколько минут рассчитывается прогноз на следующий час с использованием готовой модели и свежих треков.
При обучении модели используется огромный объем данных.
Граф дорог занимает около 100 гигабайт: это информация о топологии – какое ребро с каким соединено, а также геометрия – GPS-координаты начала, конца и точек изгиба каждого сегмента дороги.
История треков, которую мы храним, занимает десятки терабайт. При таких объемах подбор коэффициентов на день занял бы 2 недели на одном сервере.
Чтобы сделать это за приемлемые несколько часов, мы используем кластер из 30 серверов.
Но в нашей задаче мы не можем просто поровну разделить входные данные между серверами, обеспечить каждому серверу полный цикл вычислений со своей стороны и собрать окончательные результаты.
Помогает наша платформа распределенных вычислений .
Он берет на себя сбор и перераспределение промежуточных результатов, а также автоматически переносит задачи с вышедших из строя серверов на работающие и значительно упрощает масштабирование по мере роста объема вычислений.
Но даже при распараллеливании такие объемы в оперативную память, конечно, не поместятся.
Поэтому мы используем собственную библиотеку Memory Mapped Storage, которая позволяет приложению работать с данными на диске так, как если бы они хранились в оперативной памяти.
Обычно мы дублируем любую обработку данных между несколькими дата-центрами (ЦОД), чтобы сбой в любом из них не привел к недоступности сервиса для пользователя.
Но при подготовке модели мы сознательно этого не сделали.
Качество прогноза вряд ли пострадает, если использовать вчерашнюю модель в течение нескольких часов.
Но сам прогноз всегда должен быть свежим – ситуация на дороге постоянно меняется.
Поэтому он готовится с тройным дублированием вычислений в разных ДЦ, полностью автономных друг от друга.
Даже если сбой произойдет одновременно в двух ДЦ, пользователь этого не заметит. Результаты вычислений разных реплик не синхронизированы между собой; для каждого запроса просто берется самый последний из трех прогнозов.
Новый прогноз рассчитывается каждые 10 минут. Сначала обрабатываются свежие треки от пользователей: они привязываются к графику, усредняется скорость движения автомобилей на одном сегменте и рассчитывается прогноз на основе модели, построенной на текущий день.
Это занимает 1–2 минуты.
Затем эти данные подготавливаются для нанесения на карту дорожного движения.
Резкие изменения скорости сглаживаются; Для каждой скорости выбирается цвет с учетом категории дороги и масштаба просмотра карты.
Это занимает еще 2 минуты.
Контроль качества
Надежное измерение качества прогноза само по себе является интересной задачей.Изучив несколько методов, мы выбрали следующий.
Метрика качества должна отражать, насколько прогноз помогает людям.
В отсутствие прогноза, пытаясь спрогнозировать скорость движения по определенной дороге через час, мы вынуждены использовать текущую информацию о пробках.
Понятно, что в течение часа пробки изменятся и наша оценка будет неверной.
Оценка, полученная с помощью прогноза, также не идеальна, но она должна быть ближе к реальности.
Насколько ближе то, что мы попытаемся измерить.
Обратите внимание, что мы можем принимать различные приближения к реальной ситуации.
Самое простое — положиться на пользовательские треки.
Таким образом, мы получили оценку в 15%.
Однако сами эти данные могут иметь систематические отклонения.
Тогда наша метрика качества будет отдавать предпочтение прогнозу, который тщательно воспроизводит эти отклонения.
Чтобы этого избежать, мы использовали замеры оценщиков — специальных людей, которые помогают измерить качество обслуживания.
Они выгнали автомобили с высокоточными GPS-устройствами на самые представительные магистрали и вернули следы.
Сравнивая прогноз с треками оценщика, мы получили другой показатель качества — 12%.
Рекомендуем к прочтению
Мы можем порекомендовать классический учебник всем, кто серьезно интересуется темой анализа данных.Элементы статистического обучения (Хасти Т.
, Тибширани Р.
, Фридман Дж.
- Спрингер .
Там вы можете найти более подробную информацию обо всех методах машинного обучения, использованных в нашем исследовании.
На сайте доступно большое количество материалов на русском языке.
Хорошим введением в проблемы транспортного моделирования станет учебник под редакцией А.
В.
Гасникова «Введение в математическое моделирование транспортных потоков» .
Специалистам будут интересны результаты зарубежных исследовательских групп, занимающихся тематикой прогнозирования дорожных ситуаций.
Из множества доступных публикаций хотелось бы выделить несколько:
- Ванли Мин, Лаура Винтер, Ясуо Амемия — Прогнозирование дорожного движения с помощью пространственно-временных корреляций .
Та статья исследовательского отдела IBM, описывающая успешный опыт использования авторегрессии, помогла нам поверить в то, что проблему прогнозирования пробок можно решить.
- Р.
Дж.
Гиббенс, Ю.
Саакти — Анализ дорожного движения с использованием данных MIDAS: прогноз времени в пути
.Отчет исследовательской группы Кембриджского университета содержит экспериментальное сравнение метода линейной регрессии и метода k-ближайших соседей.
- Вэйчжун Чжэн, Дер-Хорнг Ли и Цисинь Ши - Краткосрочное прогнозирование транспортных потоков на автомагистралях: подход байесовских комбинированных нейронных сетей .
Помимо описанных нами методов, существует множество других подходов к задаче прогнозирования дорожной ситуации.
Например, в этой статье описан успешный опыт использования нейронных сетей.
- Ян Чжан, Юньцай Лю — Сравнение параметрических и непараметрических методов прогнозирования трафика в непиковые часы .
Здесь сравниваются еще несколько параметрических и непараметрических методов прогнозирования.
карты #Геоинформационные сервисы #прогнозирование #пробки
-
Рассчитать Linux 11.6
19 Oct, 24 -
Успейте Запустить На Марс
19 Oct, 24 -
Контроль Доступа И Что Это Такое
19 Oct, 24 -
Задачи На Собеседовании (Интерфейс)
19 Oct, 24 -
Дайте Нам Тактильные Интерфейсы!
19 Oct, 24 -
О Молекулах Рнк
19 Oct, 24
