Александр Радионов
главный по Data Science
Новый прогноз времени в навигаторе
Качественный навигатор должен обладать множеством функций: удобный интерфейс, понятные и своевременные инструкции, скорость работы. Но в основе лежит самое главное — качественный прогноз времени в пути. Поработали над этим.
Если совсем коротко
Если раньше мы считали прогноз по GPS-скорости, то теперь через среднее время проезда. Прогноз стал лучше примерно на 20%.
Если подробнее
Навигатор 2ГИС получает информацию о движении транспорта во множестве городов — это показания GPS-датчиков партнёров и пользователей 2ГИС. Каждое такое измерение даёт нам информацию о скорости раз в несколько секунд по географическим координатам. Затем последовательности GPS-точек соединяются в трек и для каждого участка дороги определяется средняя скорость движения.
Алгоритмами выбирается несколько вариантов проезда по «удобству» и делается предварительная оценка времени в пути. Зная длину участка дороги и среднюю скорость движения, навигатор вычисляет точное время. Мы изменили главное — способ получения и расчёта информации о скорости на дорогах.
Как было раньше
Для прогноза времени в пути мы использовали информацию о скорости в каждой точке дороги от датчиков GPS. Такой способ хорошо работает только на высокой скорости, когда точность определения позиции достаточная. Это связано с тем, что самое распространённое значение точности GPS — круг радиусом четыре метра.

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

Получается, что выставить нужное значение скорости на дороге не всегда получается в правильной позиции.
Что поменялось
Способ расчёта прогноза. Вместо моментальной скорости GPS мы используем метод конечных разностей и рассчитываем скорость по-другому — через изменение геопозиции. Берём длину трека и время проезда по этому треку. При правильном выборе параметров времени и расстояния такой способ позволяет повысить точность измерения скорости практически на порядок.
Map matching позволяет совмещать полученные координаты GPS с фактическими улицами и проездами
Чтобы решить эту задачу, нам потребовалось реализовать подмножество алгоритма map matching — поиска эталонного маршрута на дорожном графе через несколько GPS-точек. Иными словами, когда мы получаем координаты GPS, мы рассматриваем варианты проезда из предыдущей точки до текущей и выбираем оптимальный трек, по которому проехал автомобиль. В итоге можем точно рассчитать расстояние, которое он преодолел между точками.
Пробки стали актуальнее. Более светлых сегментов посреди пробок, как на скриншоте с проезда Энергетиков в Новосибирске, может появляться больше — значит, там скорость действительно выше
Рассчитав такие треки, мы смогли делать валидацию шума GPS-точек. Если точность геопозиции слишком мала и координата «прыгает» вдоль дороги, то трек считаем шумным и отбрасываем. Такие показания не учитываются при расчёте скорости на звеньях.
Что получилось
Для измерения качества проезда по маршруту брали две метрики — соотношение предсказанного времени к реальному и среднее отклонение в процентах от идеального соотношения.
Как оценивали прогноз
$$MAPE = \frac{1}{n}\overset{n}{\underset{i=1}{\Sigma}}\frac{|RTA_i-ETA_i|}{RTA_i}$$
ETA (Estimated Time of Arrival) — прогнозируемое время прибытия, а RTA (Required Time of Arrival) — требуемое, то есть фактическое. Эти показатели — для оценки маршрутов в авиации, навигации, железнодорожном транспорте.

MAPE (Mean Percentage Absolute Error) — средняя абсолютная ошибка в процентах. Показатель нужен для оценки точности прогноза.

Хорошим сервисом мы считаем тот, который дает соотношение ETA/RTA близко к 1, а MAPE — близким к 0. Но в реальной жизни таких значений не бывает. Водители не всегда строго следуют маршруту, могут ехать по другой дороге, могут заезжать на заправку или кофе.
Чтобы посчитать эти метрики мы брали группу профессиональных водителей — таксистов нашего партнёра Ситимобил. В отличие от обычных водителей, они меньше отклоняются от маршрута и ведут себя предсказуемо, потому что выполняют заказы.

Когда мы начинали работу год назад мы получали метрики MAPE больше 0,2, что означало среднее 20-процентное отклонение предсказанного времени от реального. Например, в Сочи MAPE был ещё ниже — больше 0,3. Это было одно из самых больших значений в городах.

Когда мы реализовали часть функционала, то мы получили MAPE меньше 0,17, а конкретно в Сочи — ~0,16, тут показатель стал лучше в два раза.
Что это значит для пользователей
Пробки теперь рассчитываются через среднее время проезда по дороге, а не по GPS-скорости.
Заодно изменили расчёт скорости в спальных районах. На скриншоте — свободные дороги в Мурино под Санкт-Петербургом
Ещё изменили способ определения скорости на дорогах, по которым за интервал измерения не было ни одного проезда. Это типичная ситуация в спальных районах. Раньше мы брали статистическое значение скорости за большой интервал времени, теперь же используем самое актуальное. Это позволило сгладить среднее значение скорости и избежать некорректной раскраски.


Расчёт времени в пути на маршруте стал заметно точнее. Попробуйте.
Нажимая кнопку «Комментировать», я даю ООО «ДубльГИС» согласие на обработку персональных данных на условиях и в целях, определённых «Политикой конфиденциальности».