«Скоро приедем?»: как оценить время в пути
За прошедший год мы много работали над качеством предсказания времени в пути (ETA) в навигаторе 2ГИС и на 30% увеличили количество маршрутов, у которых прогнозное время совпадает с реальным с точностью до минуты. Меня зовут Кирилл, я Data Scientist в 2ГИС, и я расскажу, как максимально точно рассчитывать время прибытия из точки А в точку Б в условиях постоянного изменения дорожной ситуации.
Поговорим про то, как мы постепенно меняли подходы к оценке времени в пути: от простой аддитивной модели до использования ML-моделей прогноза пробок и корректировки ETA. Ввели Traversal Time на смену GPS скоростей, а ещё проводили эксперименты и оценивали качество изменений алгоритма, чистили мусор из данных и закатывали модели в продакшн. Обо всём по порядку.
Почему нам важно правильно оценивать время в пути
Во-первых, оценка времени пути помогает выбрать подходящий маршрут из точки А в точку Б (сравнить время и решить, что подходит лучше).
Во-вторых, от времени в пути зависит стоимость поездки в такси или доставки товара, поэтому правильная оценка времени напрямую влияет на ценообразование для наших партнеров.
Важно определить, что мы понимаем под оценкой времени. Для этого используем два типа времени в пути (Time of Arrival):
ETA (Estimated Time of Arrival) — это ожидаемое время в пути (наша оценка времени);
RTA (Real Time of Arrival) — это реальное время в пути (время, которое прошло от начала и до завершения поездки пользователем).
Мы должны сделать так, чтобы наше ETA было как можно ближе к RTA.
Для предложенного маршрута ETA равен 8 минутам, RTA в этот момент ещё неизвестно
Какие метрики оцениваем
Оценка ETA — задача регрессионного анализа. Его классические метрики MAE (Mean Absolute Error) и RMSE (Root Mean Squared Error) отражают, на сколько минут в среднем отличается прогнозное время от реального (для некоторой случайной поездки):
Однако у такого подхода есть несколько проблем:
Длительность поездок может быть разной: 5 минут, 60 минут или даже несколько часов. Одна и та же ошибка прогноза — например, в 5 минут — будет восприниматься во всех трех случаях по-разному. Чем длиннее поездка, тем менее критичной будет казаться ошибка. Вспоминая, что ETA влияет на ценообразование, этот пример становится еще более актуальным.
Есть проблемы с интерпретацией результатов: если алгоритм в среднем ошибается на 10 минут — это хорошо или плохо? Ответить на этот вопрос невозможно, если мы не знаем среднюю длительность поездки. То есть в каждом новом эксперименте должна быть такая же средняя длительность поездки, как и в предыдущих. Если это требование нарушено, метрики экспериментов некорректно сравнивать между собой.
Нет сведений о том, в какую сторону алгоритм ошибается чаще. Постоянное занижение или завышение ETA — это очень плохо, даже если средняя ошибка низкая. Пользователи это заметят и попытаются скорректировать время в пути самостоятельно: например, прибавить 5 минут к прогнозному времени. Нашей оценке будут доверять меньше.
Поэтому для оценки качества ETA мы используем две другие метрики одновременно:
MAPE (Mean Absolute Percentage Error) показывает, на сколько процентов в среднем прогнозное время отличается от реального. Чем меньше ошибка, тем лучше.
Эта метрика решает трудности, связанные с интерпретацией результатов: теперь не нужно ничего знать о длительности поездки, чтобы понять, хорошо ли работает алгоритм и насколько большой будет ошибка для различных поездок.
ETA/RTA (Estimated Time of Arrival / Real Time of Arrival) показывает среднее значение отношения прогнозного времени к реальному. В идеале оно должно быть около единицы, то есть в среднем алгоритм не должен стабильно завышать или занижать прогнозное время в пути.
ETA/RTA — вспомогательная метрика для проверки того, насколько (и в какую сторону) в среднем сдвинуто предсказанное время относительно реального. Для оценки качества предсказаний алгоритма в первую очередь нужно смотреть на MAPE.
Для анализа мы также используем и множество других метрик, однако эти две — наиболее значимые.
Вычисляем базовый алгоритм расчёта ETA
С метриками определились, а что дальше?
В нашем распоряжении есть дорожный граф, в котором ребра — это маленькие кусочки дорог, соединённые между собой. Каждое ребро такого графа может включать в себя несколько дорожных полос, но обязательно является однонаправленным. Помимо этого, есть также множество других постоянных характеристик ребра, например:
геометрия (длина и ширина);
ограничение на максимальную скорость;
наличие на ребре светофора.
Таким образом, считаем, что маршрут из А в Б — это путь в дорожном графе, начинающийся в вершине А и заканчивающийся в вершине Б.
Пример маршрута: точки — это вершины графа, отрезки, их соединяющие — рёбра
Также мы получаем GPS-данные с устройств пользователей-автомобилистов. Это текущее местоположение (широта и долгота) устройства, скорость, с которой устройство движется, азимут и прочее. Эти GPS-точки с каждого устройства приходят с интервалом в несколько секунд, что позволяет не просто собирать данные, но и анализировать целые траектории движения.
Более того, есть также алгоритм, который умеет притягивать GPS-точки к соответствующему ребру дорожного графа с довольно хорошей точностью. Поэтому для каждого ребра можно насчитать различные статистики:
текущая загруженность (например, число GPS-точек в единицу времени);
«обычная» скорость в это время (например, средняя за всю предыдущую неделю).
Есть несколько вариантов расчёта статистик. Первый: пересчитывать их постоянно, с приходом новых точек — например, считать скорость на основе последних 100 точек. Второй: пересчитывать статистики каждые N минут на основе всех точек, полученных за это время.
Мы остановились на втором варианте и пересчитываем текущие статистики раз в пять минут, а «обычные» статистики — раз в неделю. Эти значения оказались оптимальными: если пересчитывать чаще, то данные не успевают накопиться (из-за чего статистики сильно «скачут»), а если реже, то не успеваем быстро адаптироваться к новой дорожной ситуации.
Всё готово к тому, чтобы рассказать про базовый алгоритм расчёта ETA:
Считаем время проезда по каждому ребру в маршруте на основе текущей скорости на ребре.
Добавляем к полученному времени «штрафы» — дополнительное время за совершение сложных манёвров, таких как повороты и развороты.
Алгоритм можно выразить простой формулой:
С преимуществами алгоритма всё понятно: он простой, быстрый и даже работает, предсказывая что-то близкое к правде! Но в таком виде у него есть существенные недостатки. Посмотрим на них.
Какие недостатки алгоритма нужно исправить
1. Алгоритм сильно зависит от текущих скоростей на ребрах
Эта скорость должна быть не какой-то абстрактной величиной, а точной оценкой средней скорости водителя на этом ребре. Поэтому нужно очень тщательно настроить алгоритм расчёта скоростей на ребрах, иначе предсказания будут далеки от истинных значений.
2. Не учитывается изменение скоростей по рёбрам во время движения
Некорректно брать текущую скорость на ребре, если мы приедем к нему, например, только через 40 минут. За это время на ребре может, например, начаться пробка, и скорость упадет в несколько раз, что повлияет на итоговое время в пути.
3. Нет персонализации предсказаний
Для любого пользователя на одном и том же маршруте будет предсказано одно и то же ETA, без учёта его манеры вождения.
4. Не учитывается общая дорожная ситуация и особенности построенного маршрута
Игнорируется много информации о состоянии дорог в маршруте, о текущих пробках в городе и конкретном районе, по которому предстоит ехать, количество участков с затрудненным движением и так далее.
5. Проблема с подбором корректных «штрафов»
В разных городах время на маневры может значительно отличаться. Более того, оно может быть уникальным для каждого перекрестка: нужно учитывать наличие светофоров, количество полос, качество и геометрию дороги и так далее. Эта задача ещё сложнее, чем расчет текущей скорости на ребре графа, поэтому в первых версиях алгоритма мы использовали постоянные штрафы на каждый вид манёвров.
Дальше расскажу про то, как мы поэтапно исправляли описанные недостатки.
Настраиваем схему экспериментов
Прежде чем модифицировать существующий алгоритм, нужно научиться оценивать эффект от изменений. Первая сложность — как оптимизировать две метрики? Что делать в ситуациях, когда одна метрика стала лучше, а другая — хуже?
Мало того, что две метрики в целом неудобно оптимизировать, так у них ещё есть особенности, которые мешают интерпретировать результат:
Во-первых, может быть ситуация, когда обе метрики стали лучше, а алгоритм — хуже.
Во-вторых, эти метрики взаимосвязаны: оптимальное значение MAPE достигается при ETA/RTA чуть меньшем, чем 1 (например, при ETA/RTA = 0.95). Из-за этого изменения (которые не делают ничего, кроме как немного двигают ETA всех маршрутов) могут влиять в том числе на MAPE.
Предположим, что мы как-то меняем существующий алгоритм и сравниваем его со старым по метрикам ETA/RTA и MAPE. По ним очевидный вывод: алгоритм стал лучше.
Теперь посмотрим на значения ETA/RTA поездок, полученные старым алгоритмом:
Видно, что в течение дня ETA/RTA смещён в среднем на 20% в сторону недопредсказания, но дисперсия значений очень низкая, что хорошо. Однако MAPE — это среднее отклонение относительно зелёной линии (то есть значения ETA/RTA=1), а не относительно среднего значения синих точек. Поэтому в данном случае MAPE высокий.
Если компенсировать этот сдвиг путем умножения ETA на 1.25, то получаем практически идеальный алгоритм с оптимальным ETA/RTA и низким MAPE:
А теперь посмотрим на график ETA/RTA поездок, полученных новым алгоритмом:
Он несмещённый, но имеет огромную дисперсию! Алгоритм однозначно стал хуже, но по метрикам этого не было видно. По графикам получаем один вывод, по метрикам — другой. Нужно что-то с этим сделать.
Чтобы выйти из этой ситуации, мы придумали свою метрику и назвали её NFCAM — Normalized First Central Absolute Momentum.
Фактически она показывает MAPE алгоритма при «идеальном» ETA/RTA, равном единице, и лишена двух вышеописанных недостатков. Заметим также, что любой смещённый алгоритм можно подвинуть к «идеальному» ETA/RTA путём умножения на величину, обратную ETA/RTA (которую можно насчитать из статистики).
По NFCAM видно, что алгоритм до добавления фичи был лучше, чем после, а простой сдвиг умножением не влияет на значение метрики. FCAM отличается от NFCAM отсутствием нормирующего члена в знаменателе, поэтому неустойчив к умножению.
После того, как определились с метрикой, появился следующий вопрос: а как проводить эксперименты?
Все эксперименты мы проводим в два этапа:
Офлайн-тестирование: делаем датасет из поездок, для которых известна построенная геометрия маршрута и RTA. Заменяем скорости на ребрах/штрафы за манёвры на вычисленные новым алгоритмом и замеряем метрики.
Онлайн-тестирование: А/Б тестирование на реальных маршрутах.
Онлайн-тестирование нужно, чтобы проверить, не испортилось ли качество построения маршрутов (для этого у нас тоже есть специальная метрика). В офлайн-тестировании мы этого проверить не можем, так как RTA есть только для построенного маршрута, а значит, мы не можем перестраивать его в соответствии с новым алгоритмом — ведь тогда пользователь поехал бы иначе, а значит, RTA был бы другим.
Если обновленный алгоритм успешно проходит оба этапа, то есть для контрольной группы NFCAM становится лучше, то изменение выкатывается в продакшн.
Важно также отметить, что датасет мы формируем не из всех доступных поездок: среди поездок встречается очень много «мусора», который нужно отфильтровать. Чтобы попасть в датасет, «хорошая» поездка должна удовлетворять нескольким критериям:
Начинается и заканчивается недалеко от точек А и Б.
Реальная траектория движения не слишком отличается от предложенной (например, если предложенный маршрут был длиной 1 км, а пользователь проехал 8 км, такой маршрут отбросится).
Средняя скорость пользователя не аномальная (исключаем «телепортации» из-за некачественного GPS-устройства).
При этом мы не требуем, чтобы траектория движения полностью совпадала с предложенным маршрутом.
Улучшаем шаг за шагом
Traversal time
Решаем проблему 1. Улучшаем расчет текущих скоростей.
Мы уже упомянули о том, что сейчас алгоритм вычисления ETA по большей части зависит от текущих скоростей на рёбрах. Как правильно вычислять эти скорости?
Вспоминаем, что у нас есть GPS-точки, которые притягиваются к рёбрам. Первый и самый простой способ — усреднить все скорости GPS-точек на ребре и полученное число считать текущей скоростью. У такого подхода есть серьезные недостатки:
GPS-скорости очень ненадежны и часто значительно отличаются от настоящих.
Поскольку точки идут с интервалом в несколько секунд, неизвестно, какая скорость была между ними (фактически — игнорируем ускорение при расчетах).
Большое влияние на среднюю скорость оказывают выбросы: например, при каждой остановке будет присылаться нулевые скорости, которые нужно как-то фильтровать.
Более удачным способом вычислить текущую скорость оказался подход, использующий не GPS-скорости, а GPS-координаты. В нём мы пытаемся найти среднее время прохождения ребра пользователем (от начала и до конца ребра):
(суммирование происходит по всем пользователям, которые проезжали по ребру в выбранный период)
А уже на основе полученного времени — traversal time — мы считаем текущую скорость. Traversal time позволил значительно улучшить качество предсказания ETA по сравнению с подходом, в котором считали скорость только на основе GPS-скоростей.
Скорости из статистики
К сожалению, на ребре может быть недостаточно данных для расчёта скорости, которую можно было бы использовать для расчёта времени в пути по этому ребру. Но чтобы построить маршрут через это ребро, какая-то скорость всё же нужна. Для этого мы используем скорости из статистики следующим образом:
если недавно для этого ребра была рассчитана текущая скорость, берём её;
определяем «класс» ребра и берём скорость, типичную для этого класса;
если «класс» ребра не получается определить, берём ограничение скорости по знаку.
Раньше мы использовали скорости, которые «обычно» бывают в это время, но без них метрики оказались лучше.
Модель прогноза скоростей
Решаем проблему 2. Прогнозируем изменение скоростей по мере движения пользователя по маршруту.
Дальше нужно было научиться предсказывать изменение скоростей (дорожной ситуации) по мере того, как пользователь двигается по маршруту. Для этого нужно заменить константные скорости на рёбрах на скорости, которые зависят от ETA кусочка маршрута, построенного из точки старта до выбранного ребра.
Для этого создали новую характеристику ребра — прогнозные скорости. Это скорости на час вперед от текущего момента с пятиминутным шагом, то есть 12 чисел для каждого ребра, которые, как и текущие скорости, пересчитываются раз в пять минут. Шаг в пять минут выбрали по аналогии с интервалом обновления текущих скоростей. Больший период прогноза, чем час, не оказывает никакого влияния на метрики ETA/RTA и MAPE.
Для формирования прогнозных скоростей сделали отдельный сервис с ML-моделями прогноза:
для каждого города свой набор моделей;
для каждого пятиминутного шага используется отдельная модель.
На вход сервис ждёт текущие скорости рёбер в дорожном графе. Затем они добавляются в БД Clickhouse, которая быстро считает признаки для нашего огромного объёма данных: среднюю и медианную скорости за последний час, неделю; количество полос на ребре; текущее время и прочее. Для тех рёбер, по которым недостаточно актуальной статистики, прогнозные скорости не вычисляются.
Сформированные признаки подаются на вход моделям, которые возвращают прогнозные скорости. Всё это упаковывается в файл и возвращается в сервис расчёта ETA.
Модели периодически автоматически переобучаются, чтобы учитывать изменение сезона и общей дорожной ситуации в городах. Качество каждой модели вычисляется так:
Выбираем некоторый момент в прошлом, предсказываем для него скорости через N минут (зависит от модели).
Считаем уже знакомую метрику RMSE между полученными скоростями и скоростями, которые будут текущими через N минут (то есть с «реальными» скоростями из будущего относительно момента предсказания).
Новые модели сравниваем со старыми на одинаковом наборе данных: если RMSE стал лучше, то модель меняется на новую. Также на стейджинге у нас развёрнут отдельный сервис прогноза для экспериментов.
Для ускорения работы сервиса мы убрали самые вычислительно тяжёлые признаки и конвертируем обученные модели в onnx-формат.
С добавлением прогнозных скоростей общая схема получения скорости на ребре выглядит так:
Модель корректировки ETA
Решаем проблемы 3 и 4. Добавляем персонализацию и учитываем дополнительные данные при предсказании ETA.
Затем нужно было как-то разобраться со сдвигом ETA/RTA: из-за того, что во всех городах используется один и тот же алгоритм, трудно отрегулировать все параметры так, чтобы ETA/RTA везде был около 1. В некоторых городах он был сильно занижен, а в других — завышен.
Пример распределения ETA/RTA по дням для двух разных городов: зелёной зоной обозначена та, в которой ETA/RTA считается допустимым
К тому же мы столкнулись с тем, что все пользователи навигатора делятся на две совершенно разные по стилю вождения группы: обычные пользователи и… таксисты 🙂
Последние ездят значительно быстрее, и для них ETA/RTA получается выше, чем для обычных пользователей. В итоге трудно сделать так, чтобы у обеих групп ETA/RTA не был сдвинут.
Пример распределений ETA/RTA обычных пользователей и таксистов в одном городе
Первоначально мы с этим боролись так, как было описано выше: на основе статистических данных рассчитывали коэффициент коррекции.
… по каждому городу для обеих групп пользователей, а затем ETA поездок умножали на этот коэффициент. Таким образом решили проблему сдвига ETA/RTA и добавили персонализацию — для обычных пользователей и таксистов время в пути отличается.
Графики распределения ETA/RTA после введения корректировки для того же города, что и на прошлом изображении. Видно, что константная корректировка работает не идеально, и иногда ETA/RTA всё равно выходит за границы
Затем мы улучшили этот механизм, и на смену константной корректировке пришла модельная корректировка, которая учитывает особенности каждого построенного маршрута.
Модельная корректировка держит ETA/RTA в необходимом диапазоне, а сами значения стабильны ото дня ко дню
После построении маршрута и вычисления ETA считаются также его различные признаки, связанные со скоростями, геометрией, местоположением промежуточных точек и текущим временем. Затем эти признаки подаются на вход ML-модели, которая пытается скорректировать прежде посчитанный ETA. То есть модель не полностью заменяет базовый алгоритм, а только улучшает его результаты, используя дополнительную информацию.
В итоге вычисление ETA можно представить так:
Модели обучаются каждый день, потому что, во-первых, они получаются гораздо «легче» моделей прогноза, а во-вторых, они сильнее зависят от изменений дорожной ситуации.
Немного про штрафы
Решаем проблему 5. Уменьшаем влияние штрафов на итоговый результат.
В модели корректировки уже используется полная информация о манёврах в маршруте, поэтому определение штрафов за них мы переложили на модель. Формула расчета ETA немного упростилась, а качество — улучшилось:
Однако полностью от штрафов мы не отказались: они до сих пор используются при поиске оптимального маршрута (оптимальным мы считаем тот, у которого наилучший ETA), чтобы не строить геометрически слишком сложные маршруты. Поэтому в итоге у нас есть три разных времени в пути, каждое из которых очень важно:
ETA со штрафами: используется при построении маршрута.
ETA без штрафов: используется как признак в модели корректировки.
ETA скорректированный: используется как финальная оценка времени в пути по маршруту.
Результаты
Теперь, наконец, посмотрим, как повлияли все эти улучшения на метрики.
ETA/RTA
В результате ETA/RTA во всех городах теперь находится в пределах от 0.95 до 1.05, а в большинстве из них практически равен единице. Проблему сдвига ETA/RTA получилось полностью решить при помощи модели коррекции.
MAPE улучшился в среднем на 0.08, а в отдельных городах улучшение достигло 0.13. Теперь в среднем мы ошибаемся менее чем на 20% при прогнозировании времени в пути.
Процент плохих маршрутов
Плохим маршрутом мы считаем тот, в котором ошибка прогнозирования оказалось больше 50%. Их количество удалось снизить на 4.5% от общего количества маршрутов, и теперь вероятность подобной ошибки — менее 10%.
Можно с уверенностью сказать, что время в пути теперь определяется намного точнее, чем это было раньше, а значительных ошибок прогнозирования стало существенно меньше. Последнее особенно радует, потому что пользователи воспринимают эти ошибки крайне негативно.
Мы не останавливаемся на достигнутом и продолжаем улучшать алгоритмы вычисления времени в пути, в особенности, хотим учитывать личные предпочтения при построении геометрии маршрута.
Как Навигатор рассчитывает время в пути
Зная длину участка дороги и среднюю скорость движения, навигатор вычисляет точное время. Мы изменили главное — способ получения и расчёта информации о скорости на дорогах. Для прогноза времени в пути мы использовали информацию о скорости в каждой точке дороги от датчиков GPS.
Как Яндекс Навигатор определяет время в пути?
Навигатор рассчитывает предполагаемое время на маршрут? По логике, система Яндекс. Навигатор, рассчитывает максимальную разрешенную скорость по данным участкам дорог маршрута, с учётом пробок и количества светофоров на пути следования.
Cached
Какая средняя скорость в навигаторе?
При построении пешего маршрута время рассчитывается на основе данных о средней скорости человека — 5 км/ч. А в автомобильном навигаторе для расчёта времени поездки и времени прибытия берётся средняя скорость транспортного потока и расстояние между заданными адресами.
Cached
Как Яндекс рассчитывает время в пути пешком?
Время пешеходного маршрута на «Яндекс. Картах» рассчитывается по средней скорости ходьбы, то есть 5 км/ч. В приложении теперь удобно сравнивать, сколько времени один и тот же маршрут займёт пешком, на общественном транспорте или на автомобиле.
Как в навигаторе проложить маршрут через несколько точек?
Для этого нужно выбрать нужную точку маршрута на карте, зажать левую кнопку мыши и, не отпуская, перетащить её в нужную область. Также вы можете изменить порядок промежуточных точек. Для этого нужно зажать курсор на иконке = (она находится справа от адреса точки маршрута) и перенести пункт маршрута на нужную строчку.
Как Навигатор определяет время прибытия?
Зная длину участка дороги и среднюю скорость движения, навигатор вычисляет точное время. Мы изменили главное — способ получения и расчёта информации о скорости на дорогах. Для прогноза времени в пути мы использовали информацию о скорости в каждой точке дороги от датчиков GPS.
Как Навигатор определяет маршрут?
Маршрут в онлайн-версии прокладывается с помощью картографии и данных о пробках, которые берутся у Яндекс. Пробок. С первой всё понятно – есть регулярно обновляемая картография HERE. А вот с пробками возникают сложности: они поступают в виде точек с 4-мя основными характеристиками: ID, скорость, направление и цвет.
Как навигатор определяет время прибытия?
Зная длину участка дороги и среднюю скорость движения, навигатор вычисляет точное время. Мы изменили главное — способ получения и расчёта информации о скорости на дорогах. Для прогноза времени в пути мы использовали информацию о скорости в каждой точке дороги от датчиков GPS.
Как узнать скорость в навигаторе?
Включение или выключение спидометра
- Откройте приложение "Google Карты" на устройстве Android.
- Нажмите с вашим значком профиля Настройки Настройки навигации.
- В разделе "На автомобиле" передвиньте переключатель Спидометр вправо или влево.
Откуда берет данные Яндекс навигатор?
Треки поступают не только от частных водителей, но и от машин компаний-партнеров Яндекса (организации с большим парком автомобилей, курсирующих по городу). Помимо своих координат автомобилисты могут сообщать сервису дополнительную информацию об авариях, ремонтных работах или других дорожных неприятностях.
Что означает синяя полоса в навигаторе?
В навигаторе карта отображается синими линиями, при приближении на карте линии принимают цвет, соответствующий загруженности стоянки.
Что значит серая полоса в навигаторе?
Серый цвет означает, что на данный момент у нас нет данных о загруженности на этом участке.
Какой самый точный Навигатор?
Рейтинг лучших GPS навигаторов в 2023 году
- 2 место «Семь дорог»
- 1 место TourMap.
- Лучшие навигаторы для Андроид
- 5 место iGO Navigation.
- 4 место MapFactor.
- 3 место Навител GPS & Карты
- 2 место Sygic.
- 1 место CityGuide.
Как работает навигатор?
Спутники на околоземной орбите играют в GPS роль маркерных объектов. Они быстро вращаются, но их местоположение постоянно отслеживается, а в каждом навигаторе есть приемник, настроенный на нужную частоту. Спутники посылают сигналы, в которых закодирован большой объем информации, включая точное время.
Почему скорость на спидометре и в навигаторе отличается?
Таким образом, скорость на спидометре будет всегда чуть выше реальной скорости. Скорость по gps всегда идёт немного с отставанием в веду различных погрешностей (тип местности, количество спутников и т. д.). Поэтому реальная скорость — это что-то среднее между спидометром и gps.
Как узнать время если дано скорость и расстояние?
Если известны скорость и расстояние, то можно найти время: t = s : v.
Почему у таксистов фиолетовые карты?
Навигатора фиолетовым цветом разной интенсивности отображается слой повышенного спроса Яндекс. Такси.
Что означает серая дорога в навигаторе?
Серый цвет означает, что на данный момент у нас нет данных о загруженности на этом участке.
Что означает синяя дорога в навигаторе?
В навигаторе карта отображается синими линиями, при приближении на карте линии принимают цвет, соответствующий загруженности стоянки.
Что означает синяя дорога на навигаторе?
Здравствуйте. Синий — стандартный цвет маршрута.
Что лучше телефон или навигатор?
Внутри навигатора батарейки лучше переносят мороз, чем внутри смартфона. В тяжёлых условиях навигатор лучше ловит сигнал, об этом я уже писал выше. Наличие независимого устройства в походе тоже большой плюс. Если смартфон помимо навигации будет использоваться и как фотоаппарат, и как средство связи, блокнот, книга и т.
Какой навигатор работает без интернета?
8 лучших офлайн-карт для Android
- OsmAnd — Карты & GPS Офлайн OsmAnd. Цена: Бесплатно …
- MapFactor Navigator. MapFactor. …
- CityMaps2Go — Офлайн-карты CityMaps2Go. …
- MAPS.ME: Offline maps GPS Nav. MAPS.ME (CYPRUS) LTD. …
- Google Карты Google LLC. …
- Яндекс Карты и Навигатор Intertech Services AG. …
- Mapy.cz navigation & off maps. Seznam.cz, a.s.
Как навигатор определяет местоположение?
Определение дистанции производится путем анализа информации высокочастотного радиосигнала от сателлитов GPS из космоса. Радиоволна движется, не уступая скорости света (расчетная 300000 км в секунду в вакууме). Навигатор определяет, как долго по времени следовал сигнал и на основании этого устанавливает расстояние.
Как работает GPS для чайников?
GPS-приемник настраивается на 4 спутника, определяет расстояние до каждого из них, опираясь на время, нужное для отправки данных, и скорость света. Потом приемник определяет свое 3-мерное месторасположение в пространстве относительно этих 4-х спутников и нашей планеты.
Кому верить спидометру или навигатору?
Показания обоих приборов для определения скорости не идеальны и они не показывают точную скорость, потому как не имеют на это возможностей, различных факторов и погрешностей. Но лучше доверять скорости навигатора, так как он не ограничен в возможностях и показывает действительную скорость снятую по спутникам.
Что точнее показывает скорость спидометр или навигатор?
У GPS тоже есть погрешности, но их намного меньше и они не меняются со временем. Таким образом, можно сказать, что GPS (трекер, или навигатор) всегда показывает скорость движения гораздо более близкую к реальной, чем любой штатный автомобильный спидометр, даже в абсолютно новой машине.
Как автомобильный навигатор находит самый быстрый путь
Когда вы пользуетесь навигатором, вы указываете точку А и точку Б, и дальше навигатор как-то сам строит маршрут. Сегодня посмотрим, что лежит в основе алгоритма, который это делает. Просто ради интереса.
Графы и «задача коммивояжёра»
Ещё до появления навигаторов у людей была такая же проблема: как найти кратчайший путь из одного места в другое, если есть ограниченное количество промежуточных точек? Или как объехать ограниченное количество точек, затратив минимальные усилия. В общем виде это называется «задачей коммивояжёра», и мы уже рассказывали, в чём там идея:
- есть несколько городов, и мы знаем расстояния между двумя любыми городами;
- в классической задаче нельзя дважды заезжать в один и тот же город, но в жизни — можно;
- если городов мало, то компьютер справится с задачей простым перебором, а если их больше 66 — то уже нет;
- кроме расстояния, иногда важно учесть время, комфорт и общую длительность поездки;
- есть много приблизительных алгоритмов, которые дают более-менее точный результат.
Если взять просто города и расстояния между ними, то с точки зрения математики это называется графом: города будут вершинами графа, а дороги между ними — рёбрами графа. Если мы знаем длину каждой дороги, то это будет значением (весом) рёбер графа. Этой теории нам уже хватит, чтобы понять, как работает навигатор в машине.
Алгоритм Дейкстры — ищем самый быстрый путь
Как только появилось решение полным перебором, математики стали искать другой подход, который работал бы гораздо быстрее и не требовал бы вычисления такого огромного объёма данных. В 1959 году Эдсгер Дейкстра придумал свой алгоритм, которым пользуются до сих пор. Идея его в том, чтобы не перебирать все варианты, а находить самый короткий путь только между соседними графами — и так, шаг за шагом, продвигаться к конечной точке.
Допустим, у нас есть улицы, перекрёстки и мы знаем время пути между ними. Нарисуем это в виде графа, а чтобы было проще ориентироваться — сделаем визуально всё одинаковой длины:
Чтобы найти самый быстрый путь из А в Б, мы смотрим сначала, какие пути у нас выходят из точки А. Видно, что поехать вниз будет быстрее, чем поехать направо:
Значит, выбираем путь вниз. Теперь делаем то же самое для этой точки — смотрим, где быстрее: справа или внизу. Вниз быстрее (1 меньше, чем 4), поэтому едем по ней:
При этом мы не отбрасываем уже сделанные вычисления (всё равно уже посчитали), а запоминаем их на всякий случай. Из нижней точки есть только одна дорога — направо, поэтому едем по ней:
А теперь у нас получилась интересная ситуация: в центральную точку мы можем попасть как сверху, так и снизу, при этом и там, и там у нас одинаковое время — 3 минуты. Значит, посчитаем оба варианта — вдруг сверху будет быстрее и нам нужно будет перестроить маршрут заново:
Оказывается, снизу ехать до центра быстрее, чем сверху — 4 минуты вместо 6, поэтому оставляем нижний маршрут. Наконец, из центральной точки до точки Б всего один путь — направо, поэтому выбираем его:
Как видите, нам не пришлось считать все варианты со всеми точками, а до некоторых мы просто не добрались. Это сильно сэкономило время и потребовало меньше ресурсов для вычисления.Такой алгоритм и лежит в основе автомобильных навигаторов — с вычислениями справится даже бюджетный смартфон.
Что ещё учитывает навигатор
Чтобы алгоритм оставался простым и работал только со временем, все остальные параметры дорог тоже привязывают ко времени. Покажем, как это работает, на паре примеров.
Комфорт. Если нам нужно построить не самый быстрый, а самый комфортный маршрут, то мы можем отдать предпочтение автомагистралям и дорогам с несколькими полосами — на них обычно и асфальт получше, и резких поворотов поменьше. Чтобы навигатор выбирал именно такие дороги, им можно присвоить коэффициент 0,8 — это виртуально сократит время на дорогу по ним на 20%, а навигатор всегда выберет то, что быстрее.
С просёлочными и грунтовыми дорогами ситуация обратная. Они редко бывают комфортными, а значит, им можно дать коэффициент 1,3, чтобы они казались алгоритму более долгими и он старался их избегать. А лесным дорогам можно поставить коэффициент 5 — навигатор их выберет, только если это единственная дорога то точки назначения.
Сложность маршрута и реальное время. Маршрут из А в Б почти никогда не бывает прямым — на нём всегда есть повороты, развороты и съезды, которые отнимают время. Чтобы навигатор это учитывал, в графы добавляют время прохождения поворота — либо коэффициентом, либо отдельным параметром. Из-за этого алгоритм будет искать действительно быстрый маршрут с учётом геометрии дорог.
Пробки. Если есть интернет, то всё просто: навигатор получает данные о состоянии дорог и добавляет разные коэффициенты в зависимости от загруженности. Иногда навигатор ведёт дворами, когда трасса свободна — это не ошибка навигатора, а его прогноз на время поездки: если через 10 минут в этом месте обычно собираются пробки, то там лучше не ехать, а заранее поехать в объезд.
Если интернета нет, то алгоритм просто использует усреднённую модель пробок на этом участке. Эта модель скачивается заранее и постоянно обновляется в фоновом режиме.
Как построить маршрут по всей России
Если нам нужно построить маршрут из Брянска в Тулу, то с точки зрения компьютера это безумно сложная задача: ему нужно перебрать десятки тысяч улиц и миллионы перекрёстков, чтобы понять, какой путь выбрать. С этим плохо справляется даже обычный компьютер, не говоря уже о телефоне.
Если мы в Яндекс Картах построим такой маршрут, то навигатор нам предложит сразу 4 варианта:
Но мы не ждали полчаса, пока сервер на той стороне посчитает все перекрёстки, а получили результат через пару секунд. Хитрость в том, что алгоритм использует уже заранее просчитанные варианты маршрутов и подставляет их для ускорения.
Например, если мы поедем в Тулу не из Брянска, а из Синезёрок, то поменяется только начальный маршрут по трассе М3, а всё остальное останется прежним:
Получается, что навигатору не нужно всё пересчитывать — он находит только ключевые точки пути, а маршрут между ними уже просчитан до этого. Этот приём работает и при перестроении маршрута во время движения: навигатор смотрит, как нужно поменять путь, чтобы вернуть вас на уже известную дорогу.
Что дальше
Следующий этап — напишем алгоритм Дейкстры сами и посмотрим, как он работает по шагам.
Как навигатор рассчитывает время маршрута
Задумывались ли вы над тем, как навигатор узнаёт и рассчитывает время от пункта «А» к пункту «Б»? Откуда он «знает», с какой скоростью вы будете ехать? Ведь он же не только прокладывает маршрут, а ещё и указывает предполагаемое время прибытия.
Дело в том, что в него заложены не просто карта с сетью дорог, а этим дорогам назначены ещё и определённые свойства.
Не будем вдаваться в саму технологию создания карт: из каких источников берутся данные, в каких программах они создаются — это материал отдельной статьи. Сейчас коснёмся только особенностей прокладки маршрута. При нанесении сети дорог, улиц, переулков, паромных переправ и тому подобное, всем этим участкам дорожной сети назначаются определённые атрибуты. Прежде всего, и это основной параметр — это ограничение скоростного режима, причём эти ограничения строго соответствуют правилам дорожного движения. Например, максимально установленная скорость для загородных дорог — 90 км/ч, на автострадах, отмеченных специальным знаком — 110 км/ч, по городу — не более 60-ти и т. п. Конечно, есть дороги, где скоростной режим меняется интерактивно относительно потока машин, и данные по ограничению скорости выводятся на специальные электронные табло, но это частный случай по отношению к создаваемой карте.
Дорогам назначается ограничение по скорости. Возможен такой случай, когда, например, две улицы в городе по умолчанию имеют одно и то же ограничение максимальной скорости, но одна из них хорошо асфальтирована, имеет несколько полос, а другая однополосная и с худшим дорожным покрытием. В таком случае на карте для навигатора этим дорогам можно назначить ещё и разный статус.
Так вот, когда навигатор строит маршрут, он берёт данные со всех участков вашего пути, как по ограничению скорости, так и по классу того или иного отрезка дороги. И выбирает при равных скоростных ограничениях более высокий класс дороги, предполагая, что при движении вам будет комфортней и быстрее двигаться по дороге с более высоким классом. Затем он суммирует время, которое вы можете потратить на путешествие и таким образом выдаёт предполагаемое время прибытия. Понятно, что сейчас навигационные программы могут содержать более интеллектуальные алгоритмы по вычислению времени, ведь они ещё учитывают — двигаетесь вы в данный момент или стоите, вычисляют вашу среднюю скорость на том или ином участке.