Как построить маршрут на смартфоне в яндекс картах с несколькими точками

Маршруты с избранными точками

Выбранная точка будет задана как точка отправления (или назначения) маршрута.

«Яндекс» добавил в «Карты» бесплатную функцию планирования маршрутов для малого бизнеса

Статьи редакции

Например, небольшие магазины и химчистки, развозящие заказы, смогут оптимизировать работу курьеров и водителей.

Построение маршрута

Чтобы построить маршрут на экране автомобиля, нужно задать место назначения: найти его с помощью поиска, выбрать из списка сохраненных мест или тех мест, что вы искали ранее.

А еще маршрут можно построить в приложении на телефоне и передать на головное устройство.

Отправить уведомление на мобильное устройство

Если вы построили маршрут или нашли нужный объект на Яндекс.Картах, вы можете отправить уведомление (информацию о них) на свое мобильное устройство.

Для этого нажмите

Отправить на телефон в карточке маршрута.

Уведомление будет отправлено на номер телефона, указанный в вашем аккаунте Яндекс ID. Если номер не указан, добавьте его в аккаунт и после этого отправьте уведомление.

Для некоторых сложных маршрутов эта функция недоступна (например, для маршрутов поездки на общественном транспорте, проходящих через три и более точек).

Переместить точку

Чтобы переместить точку маршрута, перетащите ее мышкой в нужное место.

Как построить маршрут на карте в «Яндекс. Навигаторе»

При помощи интегрированных навигационных возможностей приложения можно проложить маршрут между городами, а также между текущим местоположением и выбранной точкой на карте. В обоих вариантах доступно включение в маршрут произвольного количества промежуточных точек.

Загружаем автономные карты на телефон

Как известно, Яндекс Навигатор может работать без интернета, для этого достаточно загрузить карты нужных регионов. Сделать это нужно предварительно, зайдя в настройки мобильного приложения.

Используя офлайн-карты, вы также сможете построить маршрут, указав точку назначения. Если сигнал от вышки очень слаб или у вас нет интернет-трафика, автономный режим вас выручит. Единственный минус — вы не сможете получить информацию о пробках на дорогах, для этого понадобятся Яндекс Карты с пробками — а без Интернета они не работают.

Итак, вам необходимо загрузить Яндекс Карты на телефон.

Строим маршрут от текущего местоположения

Маршрут от текущего местоположения до произвольной точки на карте строится в четыре шага:

За несколько секунд навигатор построит все доступные варианты маршрутов и предложит выбрать оптимальный. При этом учитывается текущая загруженность дорог по пути следования, места с пробками помечаются красным цветом, на участках с перекрытым движением установлены соответствующие пометки.

Строим автомаршрут между двумя произвольными точками

Для построения маршрута не от текущего местоположения на карте придётся выбрать две точки: место, откуда будет начато движения, и целевой пункт назначения. Пошагово процесс выглядит следующим образом:

Как и в предыдущем варианте, система предложит несколько доступных способов построения маршрута между точками.

Движение по маршруту

Во время движения по маршруту на экране автомобиля будет доступна следующая информация.

Загруженность дорог показана цветом:

Информацию о пробках предоставляют пользователи сервисов Яндекс.Карты и Яндекс.Навигатор. Данные передаются в обезличенном виде, конфиденциально.

Параметры, которые будут меняться в зависимости от дорожной ситуации:

Полосы отображаются в нескольких крупных городах, на сложных поворотах и перекрестках. Также полосы показываются, если нужно придерживаться определенных полос при движении.

Дорожные события — это точки на карте, к которым привязана информация о ситуации на дорогах, например о ДТП. На экране автомобиля эти точки не являются интерактивными.

В приложении на телефоне вы можете настроить, какие события будут показаны на карте. По умолчанию включены все события, кроме камер. На головном устройстве автомобиля могут отображаться все виды дорожных событий, кроме разговорчиков (произвольных текстовых сообщений пользователей).

О видах дорожных событий можно узнать в Справке Навигатора.

По координатам

Чтобы построить и запомнить точный маршрут в Яндекс Навигаторе, можно использовать точные координаты.

На последнем этапе укажите необходимое действие — Отсюда, Заехать или Сюда в зависимости от целей.

Выбрать вариант маршрута

Чтобы выбрать вариант маршрута, нажмите на строчку с нужным маршрутом на панели Маршруты или на линии маршрута на карте.

Выбранный маршрут будет выделен на карте цветом, а на панели Маршруты — синей полосой слева.

От текущего места

Распространенная ситуация, когда человек видит на карте местоположение и планирует проложить маршрут в Яндекс Навигаторе к конкретному месту. Чтобы построить дорогу:

Чтобы построить маршрут, Яндекс Навигатору необходимо несколько секунд, после чего можно отправляться в дорогу. Если во время движения приложение обнаруживает более удобный вариант, оно информирует об этом пользователя. Чтобы опция сработала, в настройках должна быть включена функция альтернативной дороги. По мере приближения к необходимой точке можно запросить помощь в парковке. При неправильном или неточном определении позиции придется заглянуть в настройки.

Как построить маршрут в Яндекс Навигаторе пешком и на автомобиле

При пользовании приложением нужно знать, как построить путь в Яндекс Навигаторе пешком и при движении на машине.

Общий подход по заданию пути на авто имеет такой вид:

При отсутствии Интернета Яндекс Навигатор продолжает указывать дорогу. Это актуально, если пользователь заранее скачал нужные карты.

Второй вариант — построить пеший маршрут в Яндекс Навигаторе. В этом случае приложение показывает несколько вариантов пути. Человек сам выбирает, какой выбрать — возле трассы, через сквер, по дворам и т. д.

Теперь рассмотрим, как в Яндекс Навигаторе проложить маршрут пешком. Здесь используются те же принципы, что рассмотрены выше. Просто укажите конечную и начальную точку, чтобы устройство подобрало несколько вариантов. Пользователю остается выбрать подходящий пеший маршрут в Яндекс Навигаторе и воспользоваться им. Здесь же можно проверить разницу во времени при движении на разных видах транспорта. Наибольшая длина пути — 50 км.

Для построения маршрута используется пешеходный граф, а именно тропинки, лестницы, зебры и другая информация. Также приведены улицы с тротуарами. Нанесением таких троп занимаются обычные пользователи. Чем больше проходов указано, тем проще найти дорогу к интересующему месту по кратчайшему пути. При анализе нужно учесть возможные препятствия и погрешность предоставленной информации.

Навигация по маршруту

Выше мы рассмотрели, как настроить маршрут в Яндекс Навигаторе. Не меньшее значение имеет навигация по заданному пути. Выделим основные моменты:

Указанный функционал помогает построить свою дорогу в Яндекс Навигаторе и придерживаться ее.

Добавить точку в середине маршрута

Построенный автомобильный маршрут можно уточнить: добавить к нему дополнительные точки (в число маршрутных точек на панели Маршруты эти точки не включаются):

Чтобы удалить дополнительную точку, дважды нажмите на нее.

Поиск пункта назначения

Важно знать, что прокладка маршрута устройством проходит в 5 этапов:

Переустановите Яндекс. Навигатор

Если не один из перечисленных способов не помогает, полностью переустановите приложение. Удалите программу с устройства, перезагрузите систему, а затем установите Яндекс.Навигатор заново. Это может помочь избавиться от ошибки некорректного построения пути.

Как проложить маршрут в Яндекс Навигаторе

В приложении Яндекс Навигатор на iPhone и Android есть несколько способов построить маршрут. Отдельно рассмотрим каждый из них.

Через закладки

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

Чтобы проложить маршрут в Яндекс Навигаторе через закладки, нажмите в приложении на значок сохраненных адресов внизу.

Далее выберите нужную закладку, нажав на нее из списка.

Приложение предложит несколько вариантов маршрутов, сравнив их по километражу и времени поездки. Выберите нужный вариант и нажмите “Поехали”.

Через поиск

Второй вариант построения маршрута в Яндекс Навигаторе — использование поиска. Через поиск можно найти нужный адрес или конкретный объект, после чего построить к нему маршрут. Чтобы это сделать, запустите приложение Яндекс Навигатор и нажмите внизу на значок поиска.

Далее кликните на поисковую строку.

Введите название нужного объекта и выберите его из выпадающего списка.

Объект будет показан на карте. Нажмите кнопку “Маршрут”, чтобы проложить путь до него.

После этого будет предложено несколько вариантов маршрута. Выберите оптимальный и нажмите “Поехали”.

Через карту

Третий вариант построения маршрута в Яндекс Навигаторе — использование карты. После запуска приложения оно сразу определяет местоположение пользователя и показывает карту около него. При помощи жестов карту можно отдать, после чего найти на ней нужное место и нажать на него.

Появится информация о точке, выберите “Поехали”, чтобы показать варианты маршрута.

Далее постройте маршрут кнопкой “Поехали”, выбрав оптимальный вариант движения.

Чтобы построить маршрут:

Нужные точки можно установить нажатием на карте вручную или вводом адреса.

Задать точку можно, либо нажав на нее на карте, либо введя с клавиатуры ее адрес или географические координаты (подробнее о формате ввода). Координаты при вводе автоматически преобразуются в адрес.

После того как начальная и конечная точки маршрута заданы, Яндекс.Карты построят несколько вариантов маршрута. Первый вариант (оптимальный с точки зрения Яндекс.Карт) отображается на карте цветным, остальные — серым:

Если вы строите автомобильный маршрут или маршрут поездки на общественном транспорте, вы можете задать дополнительные параметры маршрута. Нажмите Параметры и отметьте нужные опции:

Для автомобильных маршрутов:

Параметры грузовика — для построения маршрута, учитывающего ограничения движения для автомобилей, определяемые наличием дорожных знаков или физической невозможностью проезда, укажите:

Для маршрутов поездки на общественном транспорте можно указать свои Предпочтения по транспорту : выберите виды транспорта, на которых вам хотелось бы совершить поездку. Если существуют адекватные маршруты с использованием этих видов транспорта, они будут добавлены в выдачу.

Кроме того, для автомобильных маршрутов и маршрутов поездки на общественном транспорте можно назначить день и время поездки, отличающиеся от текущих. Маршрут будет построен в соответствии с заданным временем отправления.

В этом случае в карточке маршрута отображается вычисленное время прибытия.

Чтобы сбросить заданные параметры, нажмите Сейчас :

Маршруты отображаются на карте (и в карточках маршрутов, в которых указано расчетное время для каждого варианта):

Платные участки дорог на карте выделены значками местных валют:

Взаимодействие с телефоном

При подключении к автомобилю основной интерфейс приложения на телефоне блокируется.

Чтобы переключиться на приложение в телефоне, нажмите Продолжить в телефоне на его экране.

Переключитесь на приложение на телефоне, чтобы:

Как в Яндекс Навигаторе построить маршрут через неизвестные точки

Указанная выше инструкция актуальна в том случае, если вы знаете точное название мест, куда нужно заехать, или их точные адреса. Но бывает часто так, что доехать до финальной точки маршрута нужно через определенную зону на карте, но точное название этого места вы не знаете. Либо требуется проехать через определенную улицу, поскольку поездка по ней более комфортна.

Чтобы таким образом построить маршрут через несколько точек, сначала задайте финальную точку поездки и нажмите “Поехали”.

После этого найдите на карте то место, которое нужно включить маршрут. Сделать это можно перемещение по карте, приближением и удалением. Зажмите палец на том месте, которое должно быть в маршруте.

Появится меню. В нем нужно выбрать пункт “Через”.

Теперь маршрут построен через нужную точку.

Чтобы посмотреть маршрут целиком, нажмите

Чтобы вернуться к текущему маршруту, нажмите Отмена.

Дорожные события — это точки на карте, к которым привязана информация о ситуации на дорогах, например о ДТП. О видах дорожных событий можно узнать в Справке Навигатора.

Выбрать, какие события будут показываться, можно в приложении на телефоне. На головном устройстве автомобиля могут отображаться все виды дорожных событий, кроме разговорчиков (произвольных текстовых сообщений пользователей).

Ручной ввод

Еще один доступный метод, позволяющий прокладывать маршрут – это ручной выбор всех пунктов отправки, а также пунктов назначения. Для этого необходимо выполнить следующие действия:

И на этом все – останется лишь подождать, пока программа самостоятельно создаст самый оптимальный маршрут и нажать на кнопку «Поехали».

Прокладываем пешеходный маршрут через Яндекс Карты

В Яндекс Навигаторе отсутствует режим пешехода, однако этот недостаток можно исправить, если дополнить навигатор «Яндекс Картами». Это приложение позволяет прокладывать пешие маршруты, используя для этого функционал одноименного веб-сервиса.

Как в Яндекс Навигаторе указать несколько точек для маршрута

Необходимость проложить маршрут из точки А в точку Б — наиболее частая задача, которую ставят пользователи перед Яндекс Навигатором. Но бывает необходимость выполнить и более сложный маршрут, который проходит через несколько точек. Например, после работы нужно сначала заехать за покупками, а потом направиться домой. Яндекс Навигатор может подсказать оптимальный маршрут, построив его через несколько точек. В этой статье мы расскажем о способе это сделать.

Изменить адрес точки

Чтобы изменить адрес точки маршрута, нажмите на поле задания с адресом точки и исправьте адрес.

Служба поддержки

Чтобы сообщить службе поддержки сервиса Яндекс.Карты об ошибке на маршруте:

Откроется панель обратной связи; ее вид зависит от типа маршрута.

Неправильный манёвр ─ нажмите на узел маршрута, в котором обнаружили неточность, и в открывшемся меню выберите нужное описание;

Я знаю маршрут лучше ─ нарисуйте на карте предпочтительный маршрут.

Взаимодействие с картой

На экране автомобиля можно совершать простые действия с картой.

Алгоритм Дейкстры — ищем самый быстрый путь

Как только появилось решение полным перебором, математики стали искать другой подход, который работал бы гораздо быстрее и не требовал бы вычисления такого огромного объёма данных. В 1959 году Эдсгер Дейкстра придумал свой алгоритм, которым пользуются до сих пор. Идея его в том, чтобы не перебирать все варианты, а находить самый короткий путь только между соседними графами — и так, шаг за шагом, продвигаться к конечной точке.

Допустим, у нас есть улицы, перекрёстки и мы знаем время пути между ними. Нарисуем это в виде графа, а чтобы было проще ориентироваться — сделаем визуально всё одинаковой длины:

Чтобы найти самый быстрый путь из А в Б, мы смотрим сначала, какие пути у нас выходят из точки А. Видно, что поехать вниз будет быстрее, чем поехать направо:

Значит, выбираем путь вниз. Теперь делаем то же самое для этой точки — смотрим, где быстрее: справа или внизу. Вниз быстрее (1 меньше, чем 4), поэтому едем по ней:

При этом мы не отбрасываем уже сделанные вычисления (всё равно уже посчитали), а запоминаем их на всякий случай. Из нижней точки есть только одна дорога — направо, поэтому едем по ней:

А теперь у нас получилась интересная ситуация: в центральную точку мы можем попасть как сверху, так и снизу, при этом и там, и там у нас одинаковое время — 3 минуты. Значит, посчитаем оба варианта — вдруг сверху будет быстрее и нам нужно будет перестроить маршрут заново:

Оказывается, снизу ехать до центра быстрее, чем сверху — 4 минуты вместо 6, поэтому оставляем нижний маршрут. Наконец, из центральной точки до точки Б всего один путь — направо, поэтому выбираем его:

Как видите, нам не пришлось считать все варианты со всеми точками, а до некоторых мы просто не добрались. Это сильно сэкономило время и потребовало меньше ресурсов для вычисления.Такой алгоритм и лежит в основе автомобильных навигаторов — с вычислениями справится даже бюджетный смартфон.

Выберите нужное место из списка сохранённых.

Список доступен только авторизованным пользователям. На экране головного устройства показывается не более шести точек из этого из списка.

Добавлять и удалять места, менять их порядок в списке можно только в приложении на телефоне.

Выберите нужное место из списка тех, что вы искали ранее.

Построить маршрут на телефоне

Продлить маршрут

Построенный маршрут можно продлить, добавив одну или несколько (не более восьми) дополнительных точек в конец маршрута.

На панели появится поле ввода дополнительной точки маршрута ( «C» ).

Чтобы удалить добавленную точку, наведите указатель на нужную строку. Справа появится значок ( Удалить ). Нажмите на него, и маршрут перестроится в соответствии с заданными условиями.

Итак, расскажу теперь, как проложить свой первый маршрут:

Поменять местами точки маршрута

Чтобы поменять местами точки маршрута, если точек больше двух, нажмите кнопку в нужной строке списка точек и перетащите мышкой нужную строку в новую позицию. Маршрут будет перестроен автоматически.

Для построения маршрута нам потребуется загрузить и установить Яндекс Навигатор:

Если бы у Труса из «Операции «Ы» и других приключений Шурика» был Яндекс Навигатор, то он и в три часа ночи смог бы спросить у Алисы «Как пройти в библиотеку?», ведь она точно знает этот маршрут. Попробуем в этом убедиться.

Как мы и предполагали, Алиса смогла за пару секунд построить маршрут, рассчитать время и километры.

Итак, чтобы пройти в библиотеку нам понадобится 40 минут, а весь путь займет около 3,5 километров. Можем проехать на такси или автомобиле, но если время и погода позволяет — почему бы не прогуляться? Теперь выберем маршрут, по которому пойдем.

Навигация от Яндекс была создана специально для автомобилистов, но и пешеходы могут воспользоваться его подсказками.

Главный плюс Навигатора для пешеходов в том, что он показывает не один маршрут, а несколько. И мы можем выбрать где пройти: мимо оживленной трассы или срезать через зелёный сквер неподалеку. Второй маршрут нам вполне подходит, жёлтой стрелочкой показывается наше местоположение, а флажком финиша — нужный адрес.

Попробуем приблизить карту и рассмотреть мимо чего нам идти пешком. Большими белыми стрелками на карте показывается направление движения. Зеленым отмечены безопасные участки дорог, участки с повышенной опасностью — оранжевым и красным. Эта информация пригодится не только автомобилистам, но и пешеходам.

Рядом с основной дорогой показаны все пешеходные дорожки и светофоры — удобно переходить на другую сторону дороги.

Чтобы не скучать в дороге, можно поиграть с Алисой в «Шар судьбы», «Слова» или «Верю-не верю», это довольно забавно.

Добавляем промежуточные точки

Интерфейс приложения предусматривает три способа добавления на маршрут промежуточных точек: через контекстное меню, значок «+» на карте и интегрированный поисковый механизм.

Для добавления промежуточной точки через контекстное меню:

Для добавления дополнительного пункта назначения прямо на карте:

Для добавления промежуточного места назначения через поиск:

Все перечисленные способы одинаково хорошо работают как при построении маршрутов для поездок на машине, так и для пеших прогулок и путешествий.

Актуальные версии «Яндекс.Навигатора» поддерживают управление голосом с помощью встроенного движка «Алиса», который отлично понимает произвольно составленные фразы, вроде: как добраться до Москвы из Киева. Таким образом существует три способа ввода данных: вручную с сенсорной клавиатуры, голосом, через контекстное меню на карте.

«Яндекс.Навигатор» работает в режиме реального времени. Для этого ему нужен постоянный стабильный доступ в интернет. С его помощью можно не только построить наиболее удобный пеший или автомобильный маршрут, но и запустить голосовое сопровождение поездки, добавить промежуточные пункты назначения, узнать о текущей ситуации на дорогах, просмотреть находящиеся в радиусе нескольких километров заправки, кафе, магазины. Если же Интернет недоступен, Яндекс Навигатор автоматически переключится в офлайн-режим и продолжит работать как ни в чем ни бывало.

Напомним: загрузить последнюю версию приложения «Яндекс.Навигатор» можно в магазине Play Market или его адаптированной версии «Яндекс.Маркет».

См. также: Как проложить маршрут в Google Maps

Экспорт объектов карты

Вы можете сохранить объекты вашей карты на Яндекс.Диск в виде файла одного из нескольких форматов.

Эти файлы можно использовать для импорта нужных точек в программы-навигаторы, поддерживающие импорт GPS-координат, для использования совместно с API Яндекс.Карт, для просмотра и сохранения данных в других программах (например, в Google Earth) и т. п.

При экспорте сохраняется информация только об объектах вашей карты.

Перейдите по ссылке Экспорт панели:

В открывшейся форме Экспорт объектов карты выберите тип файла:

KML (от англ. Keyhole Markup Language, язык разметки Keyhole): формат на основе XML. Подходит для импорта объектов на карту, созданную в API Яндекс.Карт или Google Earth.

В файл сохранятсяnметки (координаты, описание, подпись, цвет),nлинии и многоугольники.

Пример использования файлов формата KML в API Яндекс.Карт можно посмотреть в разделе Отображение GPX и KML документации API Яндекс.Карт.

При открытии файла программой, предназначенной для просмотра файлов данного типа (например, Google Earth), вы увидите объекты своей карты:

XLSX (электронная таблица Microsoft Excel).

В файл сохранятсяnметки (координаты, описание, подпись). По столбцам: широта, долгота, описание, подпись:

CSV (от англ. Comma-Separated Values — значения, разделeнные запятыми): текстовый формат, предназначенный для представления табличных данных. Файл такого формата можно открывать в текстовых и табличных редакторах.

Текст разбивается на столбцы с помощью специальных символов — разделителей. Для выбора разделителя нажмите нужную кнопку Разделитель :nЗапятая, Точка с запятой или Табуляция.

В файл сохранятсяnметки (координаты, описание, подпись, номер).

При открытии файла программой, предназначенной для просмотра файлов данного типа, вы увидите данные объектов своей карты:

В файл сохранятсяnметки (только координаты)nи линии (только координаты).

Посмотреть маршрутный лист

Чтобы посмотреть маршрутный лист, нажмите Посмотреть подробнее в карточке маршрута.

Маршрутный лист автомобильного маршрута — это список участков движения в одном направлении, отделенных от соседних отрезков маневрами. Возле каждого отрезка указана его протяженность, название улицы, по которой он проходит, и направление маневра (прямо, направо, налево, круговое движение, разворот).

Для маршрута общественного транспорта отрезок — это поездка на одном из маршрутов общественного транспорта или переход между поездками на разных видах транспорта; возле каждого отрезка указан вид транспорта, номер маршрута и название остановки.

Как проложить пеший маршрут в Яндекс Навигаторе

Яндекс Навигатор не дает возможности проложить пеший маршрут. Единственная возможность использовать приложение для пешей навигации — это двигаться по нему при построенном обычном маршруте для автомобилистов. Но в таком случае не получится узнать примерное время в пути и варианты обхода препятствий на дороге, которые были бы неприемлемы при поездке на автомобиле.

В Яндекс Навигаторе можно найти нужную точку на карте или через поиск и проложить к ней маршрут, сверху переключившись на пеший вариант.

После этого маршрут будет построен, останется только следовать по нему.

Яндекс, ну сколько можно лагать ❓ Постоянно перестраивает маршрут, сбивается с пути и тормозит. Что ещё не так с этим навигатором?

Каждый водитель сталкивается с поиском хорошего навигатора, и я не исключение. Не представляю, как люди раньше ездили по картам или обычным указателям 🤨

Права я получила ещё в 2015, но активно ездить стала год назад. Всё это время пользовалась Яндекс навигатором, и не было никаких проблем. Но в последние 2 месяца что-то пошло не так.

Давно хотела написать этот отзыв, потому что моему возмущению нет предела! Но обо всем по порядку.

✔️ Значок Яндекс навигатора на рабочем столе выглядит так :

Для адекватной работы необходимо включить геолокацию на телефоне.

✔️ Страница поиска выглядит так:

Можно искать нужное место по категориям, а можно по адресу. Второй вариант для меня более удобен.

✔️ Основные настройки :

🚘 Здесь вы можете выбрать отображение на карте различных дорожных событий :

🚘 Какие звуковые оповещения будут приходить:

🚘 Решить, с каким из голосов ездить :

Скачала Серебро, Бузову и Брежневу.

⚠️ Определиться, при каком превышении скорости вас будут предупреждать.

У меня это классика.

✔️ Для «чайников» есть подсказки по всем разделам.

На этом все. Дальше будут тонны моих возмущений.

Найден путь на 6/10/20 минут быстрее

И предлагал выбрать новый маршрут

То сейчас он ставит перед фактом :

Спасибо за внимание к моему отзыву 😊 С вами была Frau_Kritik 🌸

Графы и «задача коммивояжёра»

Ещё до появления навигаторов у людей была такая же проблема: как найти кратчайший путь из одного места в другое, если есть ограниченное количество промежуточных точек? Или как объехать ограниченное количество точек, затратив минимальные усилия. В общем виде это называется «задачей коммивояжёра», и мы уже рассказывали, в чём там идея:

Если взять просто города и расстояния между ними, то с точки зрения математики это называется графом: города будут вершинами графа, а дороги между ними — рёбрами графа. Если мы знаем длину каждой дороги, то это будет значением (весом) рёбер графа. Этой теории нам уже хватит, чтобы понять, как работает навигатор в машине.

Сотни тысяч маршрутов в секунду на ядро. Опыт Яндекс. Маршрутизации

Пару недель назад Даня Тарарухин рассказал на Хабре, как появился наш сервис, Яндекс.Маршрутизация, и как он помогает компаниям с логистикой. Создавая платформу, мы решили несколько интересных проблем, одной из которых и посвящён сегодняшний пост. Я хочу поговорить о самом планировании маршрутов и необходимых для этого ресурсах.

Поиск оптимального маршрута между множеством точек — классическая задача дискретной оптимизации. Для её решения нужно знать расстояния и времена в пути между всеми точками. То есть — знать матрицу расстояний и времён. Ещё два года назад долгое вычисление матрицы было для нас очень критичной проблемой и блокировало развитие. Сам поиск оптимального решения при известной матрице занимал 10 минут, а вот вычисление всех ячеек матрицы для больших задач (на несколько тысяч заказов) занимало часы.

Чтобы решить задачу с пятью тысячами заказов, нужно знать расстояния и времена в пути между всеми точками. Это две матрицы чисел размерностью 5000х5000. Мы планируем маршруты курьеров на весь день, и утром курьер доедет от точки до точки за одно время, а вечером — за другое. Значит, нужно вычислять матрицы времён и расстояний для каждого часа дня. Не все часы дня уникальны, но пробочное время (утро и вечер) нужно покрыть хорошо. Поэтому мы пришли к конфигурации с тринадцатью часовыми срезами. Итого нам нужно два куба (времён и расстояний) размерностью 13х5000х5000 каждый. Это 325 млн маршрутов, посчитанных по реальному графу дорог, в котором 165 млн ребёр. Расчёт одного маршрута в хорошо оптимизированном алгоритме команды Яндекс.Карт занимает порядка 10 мс, суммарно получаем 900 часов вычислений. Даже при распараллеливании на 900 CPU нужно ждать 1 час. Такой сервис мы не могли запустить, нужен был более подходящий алгоритм.

Почти каждый кандидат в разработчики на собеседовании догадывается до первого шага оптимизации такой задачи: можно запускать волну с двух сторон и заканчивать поиск, когда волны встретятся. Суммарная площадь двух волн половинного радиуса меньше одной большой.

Реальный граф дорог достаточно сильно структурирован, и это можно использовать. Когда вы ищете кратчайшее расстояние между Москвой и Питером, в классической Дейкстре вы будете вынуждены распространять волну по кругу и перебирать все улицы и переулки Москвы, подмосковных городов и деревень, улицы Твери и Новгорода. Это огромный объём вычислений, но можно заранее подготовиться и запомнить оптимальные маршруты между городами (aka шорткаты) и не повторять их в рантайме. Тогда для поиска маршрута между двумя точками в иерархической Дейкстре вам останется посчитать кратчайшие расстояния до нужного шортката. Так как уровней иерархии может быть не два, а 5-6, то они драматически снижают время поиска.

Команда роутера Карт уже достаточно давно реализовала такие оптимизации. Именно они позволили достичь 10 мс для поиска маршрута между двумя точками. 🙂 Так что пока мы не приблизились к решению нашей проблемы.

Раз режим поиска точка-точка уже предельно оптимизирован, мы можем оптимизировать расчёт ряда в матрице. Ряд — это расстояния от одной точки до всех остальных. Пока мы ищем расстояние до самой дальней точки, мы попутно вычисляем расстояния до более близких. Значит, вычисление ряда эквивалентно вычислению расстояния до самой дальней точки.

Смотрим на время вычисления ряда по такому алгоритму и вспоминаем, что последовательное вычисление 5000 маршрутов заняло бы порядка 5000 * 10 мс = 50 с:

На графике показано время вычисления строки в матрице расстояний размером 1*N для разных N (по реальным данным). Видно, что вычисление строки интересующего нас размера 1*5000 укладывается в 1,3 секунды. На график добавлена линия тренда, которая показывает, что время вычислений растет чуть медленнее, чем линейно по N, порядок N**0.74

Уже неплохо! С таким алгоритмом мы можем посчитать наш куб за 13 * 5000 * 1,3 с = 84 500 с = почти 24 часа. Он легко параллелится по рядам, и при использовании 50 CPU расстояния вычисляются за полчаса. Порядок сложности алгоритма вычисления куба — O(N**1.74):

График оценочного времени вычисления 13 матриц размером N*N по рядам на 50 CPU (домножили предыдущий график на 13*N/50). По этому графику мы принимали решение, что если к нам придет клиент с 5000 заказов, то мы должны уложиться в полчаса со всеми тринадцатью часовыми срезами. А вот если заказов станет 10 000, то всё плохо: придётся добавлять железо или увеличивать время.

В таком виде два с половиной года назад мы запустили первую версию нашего API, решающего логистическую задачу. Клиенты достаточно часто жаловались на долгое время решения, и их легко понять: ты запустил задачу решаться, ждёшь 1 час, получаешь решение и понимаешь, что забыл поправить время смены у водителя, исправляешь и всё начинается сначала. Водители начинают нервничать, так как рискуют попасть в утренний час пик, а то и вовсе не успеют доставить заказ в срок. Нужно было что-то делать. «Закидывать» проблему железом не хотелось: мы готовились к большим нагрузкам, потребовалось бы много железа, да и закупка серверов происходит не одномоментно.

Изучение академических статей показало, что, оказывается, для этой задачи есть алгоритмы с линейной сложностью*! (В статье по ссылке есть большой обзор всевозможных современных способов ускорения Дейкстры, в том числе и для матричного случая.) Вычислять матрицу за линейное время — это не укладывалось в голове. Один из наших разработчиков вызвался написать прототип, и вот что получилось:

Время вычисления одной матрицы размера N*N на одном CPU с помощью алгоритма «быстрых матриц». Сложность получается порядка O(N**1,1). Высокие N выбиваются из линии тренда, поскольку на время уже больше влияет генерация ответа и его скачивание по сети.

115 секунд на матрицу 5000х5000 при использовании одного ядра и почти линейная зависимость от N. Фантастика стала реальностью! Идея алгоритма комбинирует две описанные выше идеи: Дейкстру для рядов и иерархический поиск. Очевидно, что, начав вычислять второй ряд, мы в какой-то момент вновь будем обходить ту же область графа, которую мы только что проходили, вычисляя предыдущий ряд. Поэтому давайте запоминать в узлах иерархического графа кратчайшие расстояния до всех destinations. Когда мы начнём вычислять следующий ряд, то, дойдя до такого узла, мы разом получим почти все расстояния до других точек.

Полтора года назад это позволило нам сэкономить полчаса времени седения волос логиста и существенно уменьшить потребление железа. Если раньше на один большой запрос нам требовалось 50 ядер на полчаса, то теперь — 13 ядер на 2 минуты. Это примерно 200 000 маршрутов в секунду на ядро. Тот редкий случай, когда новый алгоритм не просто закрывает класс проблем, а расширяет наши представления о возможном.

* Статья «Route Planning in Transportation Networks», см. параграф 2.7.2 «Batched Shortest Paths»

Как сбросить маршрут

Если необходимо удалить маршрут в Яндекс Навигаторе (сбросить его), жмите на кнопку с крестиком в нижней части панели. При отсутствии знака на этом участке прикоснитесь к карте.

Прокладываем маршрут в Яндекс. Навигаторе

В рассматриваемом приложении проложить маршрут достаточно просто. Проделать это можно тремя разными путями, идентичными для Андроид и иОС.

Голосовой ассистент

Проложи маршрут до *название объекта*

Текстовый поиск

Второй вариант тоже достаточно простой – следует задействовать «Поиск».

Последний из доступных методов прокладки маршрута – ручной выбор пунктов отправки и назначения.

Что делать, если Навигатор не ведёт по маршруту

Иногда может случиться так, что маршрут проложен, но навигатор по нему не ведёт. Вот краткая инструкция по решению проблемы:

Урок: Как перезагрузить Android и iPhone

Заключение

Как видим, построить маршрут в Яндекс.Навигаторе очень просто. Эту операцию можно проделать тремя способами, которые подходят для разных категорий пользователей.

Помимо этой статьи, на сайте еще 12232 инструкций. Добавьте сайт Lumpics.ru в закладки (CTRL+D) и мы точно еще пригодимся вам.

Отблагодарите автора, поделитесь статьей в социальных сетях.

, чтобы набрать адрес с экранной клавиатуры.

Проверьте ваше подключение к Интернету

Прежде всего убедитесь, что ваше интернет-подключение работает стабильно. Запустите браузер и попробуйте посетить несколько привычных сайтов. Если переход происходит без каких-либо проблем, идём далее.

Оптимизировать маршрут

Вы можете автоматически оптимизировать маршрут для автомобиля, пешехода или общественного транспорта, если вы строите его по четырем и более точкам.

Точки на маршруте останутся прежними, но порядок их посещения может измениться.

Текстовый ввод

Еще один простой вариант – это текстовый поиск, являющийся аналогом голосового. При таком варианте необходимо выполнить следующие действия:

Но есть и третий способ – ручной.

Увидеть снимки дорог по маршруту

Если вы построили автомобильный маршрут (длиной не более 100 км), в левом нижнем углу карты отобразится плеер, который покажет слайдшоу серии снимков дорог вдоль этого маршрута (подробно о снимках см. Зеркала (снимки дорог):

В полноэкранном режиме вы можете:

Изменить направление движения по маршруту

Когда маршрут построен по двум точкам (из А в B), вы можете изменить направление построенного маршрута на обратное (из B в А).

Для этого нажмите значок со стрелками (

) между названиями точек.

При изменении направления движения маршруты перестраиваются.

Местоположение определяется неточно

Если место определяется неверно, выполните следующие действия:

Включите определение местоположения (Геолокация, GPS)

Включите определение местоположения и подождите, пока устройство не начнет отображать его. Устройство при этом должно находиться на открытой местности.

Определение местоположения лучше никогда не отключать: это заметно сократит время поиска спутников при запуске приложений, которые его используют, а значит они будут работать быстрее.

В настройках устройства вы можете запретить отдельным приложениям доступ к вашему местоположению, если это необходимо.

Проверьте GPS-сигнал с помощью других приложений

Установите стороннее приложение для проверки GPS-сигнала, например GPS Test. Запустите приложение, когда вы видите проблемы в работе Навигатора. Местоположение должно определяться с точностью до 15 метров.

Если другие приложения, которые требуют доступ к местоположению, не работают, скорее всего, проблема в устройстве, и его нужно ремонтировать.

Разрешите приложению получать данные о местоположении

Навигатор не может работать корректно, если не получает данные о геопозиции. Включите доступ к этим данным в настройках устройства.

Включите мобильный интернет

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

Включите точный режим определения местоположения

Включите режим определения местоположения по данным спутников, по сотовым данным и по Wi-Fi.

Другие режимы, например только по спутникам или по Wi-Fi, не позволяют точно определять местоположение и не подходят для работы навигаторов.

Выключите режим энергосбережения

Большинство режимов энергосбережения отключают определение местоположения.

Обеспечьте доступность GPS-сигнала

Держите устройство под лобовым стеклом автомобиля. Преграды, например крыша автомобиля, густая листва или многоэтажные дома, снижают качество GPS-сигнала и могут полностью его блокировать.

Установите официальную версию операционной системы

Многие неофициальные версии операционной системы недостаточно протестированы, и GPS-модули в них работают некорректно.

Как построить маршрут по всей России

Если нам нужно построить маршрут из Брянска в Тулу, то с точки зрения компьютера это безумно сложная задача: ему нужно перебрать десятки тысяч улиц и миллионы перекрёстков, чтобы понять, какой путь выбрать. С этим плохо справляется даже обычный компьютер, не говоря уже о телефоне.

Если мы в Яндекс Картах построим такой маршрут, то навигатор нам предложит сразу 4 варианта:

Но мы не ждали полчаса, пока сервер на той стороне посчитает все перекрёстки, а получили результат через пару секунд. Хитрость в том, что алгоритм использует уже заранее просчитанные варианты маршрутов и подставляет их для ускорения.

Например, если мы поедем в Тулу не из Брянска, а из Синезёрок, то поменяется только начальный маршрут по трассе М3, а всё остальное останется прежним:

Получается, что навигатору не нужно всё пересчитывать — он находит только ключевые точки пути, а маршрут между ними уже просчитан до этого. Этот приём работает и при перестроении маршрута во время движения: навигатор смотрит, как нужно поменять путь, чтобы вернуть вас на уже известную дорогу.