Наши предки строили свой путь, ориентируясь по звёздам и деревьям. Намного позже появились карты, а сейчас маршрут до кофейни можно построить с помощью навигатора. Но как он работает и рассчитывает время пути?
Как делают электронные карты
Чтобы навигаторы работали точно, нужны детализированные карты, на которых будут все дома, дороги, мосты и многие другие объекты. С технической точки зрения дорожная карта представляет собой граф, перекрёстки представлены как вершины с точными координатами, а дороги между перекрёстками отображаются в виде рёбер графа.
Дорожная модель навигаторов содержит почти 200 миллионов связей между вершинами. Там содержится много важной информации: от направлений движения до длин магистралей. Разработчикам работать с графами довольно сложно, так как данных очень много, а транспортные системы постоянно меняются.
Чтобы в навигатор внести новые данные, нужно получить актуальную информацию — в этом помогают отзывы пользователей и анонимные отчёты о их геолокации. После получения данных специалисты проверяют их, отправляя запросы, например, в ГИБДД, анализируют информацию на сайтах администрации городов и так далее. Если комментарий пользователя подтверждается, в карту вносят изменения.
Как работает автомобильный навигатор
Информацию о том, есть ли в этом районе дороги и есть ли там пробки, приложение получает от навигаторов пользователей. Единственные погрешности, которые система не учитывает, — это, например, если автомобилист едет по крыше завода или двигается медленно там, где разрешено движение.
Данные о том, с какой скоростью движутся автомобили на одной дороге, и данные графа сравниваются, чтобы сделать вывод о наличии пробок. Обычно загруженность дорог обозначают цветами, нам уже привычными: зелёный — движение свободное, красный — многокилометровые пробки. Некоторые оценивают загруженность по десятибалльной шкале, но это не совсем корректно отображает ситуацию: пробка в 10 баллов в Москве и в небольшом городе — это совершенно разные вещи. Поэтому более корректно отображать трафик цветом.
Как навигатор выстраивает маршрут
После того как человек вводит в навигатор точку от пункта А до пункта Б, маршрутизатор прокладывает путь. Он делает это, опираясь на алгоритм Эдсгера Дейкстра — поиска кратчайшего пути в графах с неотрицательными весами рёбер, который был предложен голландским учёным в 1959 году.
Навигатор строит оптимальный путь, учитывая множество факторов — например, хочет ли человек ехать по платной дороге или будет избегать грунтовых дорог. После этого рассчитывается время с помощью модели машинного обучения — CatBoost.
Она работает просто: берутся все данные о выбранном пути, включая день недели, наличие пробок и среднюю скорость движения, и сравниваются с временем, которое тратили другие люди, двигавшиеся по этому маршруту. Например, ночью дороги могут быть менее загруженными, так что добраться до места можно намного быстрее, чем в пятницу вечером.
Когда человек начинает движение, система постоянно обновляет информацию, собирая данные о пробках, авариях и других событиях. Поэтому навигатор на ходу может изменить маршрут, чтобы пользователь добрался до места назначения быстрее.
Самое удивительное в том, что, несмотря на то что ситуацию на дорогах трудно предсказать (в любой момент может случиться авария или перекрытие дороги), информация навигатора невероятно точна! Отклонения составляют не больше 12%. Конечно, навигатор может работать некорректно, особенно если в месте нахождения нет интернета или работают глушилки — тогда устройство опирается на данные сотовых вышек.
Конечно, мы описали лишь малую часть работы навигаторов: за вашим маршрутом от дома до кофейни стоят огромные массивы данных, информация от миллионов пользователей и работа большой команды, которая проверяет актуальность дорожного движения и прочее.
ПОДПИСЫВАЙТЕСЬ на наш YouTube канал!
Ставьте ПАЛЕЦ ВВЕРХ и ПОДПИСЫВАЙТЕСЬ на Дзен канал
Читайте также: