Почему навигаторы ведут по списку, а не по кратчайшему пути
Любой навигатор умеет найти лучшую дорогу между двумя адресами и ни один не переставляет адреса местами ради экономии. Это выглядит как недоделка, но это разные задачи, и вторая устроена принципиально сложнее первой. Разбираемся, почему так, во что это обходится и что с этим делать.
Две задачи, которые легко перепутать
Когда человек говорит «навигатор должен построить оптимальный маршрут», он обычно имеет в виду одно из двух. Различие решает всё.
Задача первая: как доехать из А в Б. Есть две точки, между ними дорожная сеть. Нужно найти лучший путь: короткий, быстрый, без перекрытий. Навигаторы решают её отлично, каждый день, миллионы раз.
Задача вторая: в каком порядке объехать двадцать адресов. Точек много, дорога между любыми двумя известна, но неизвестна очерёдность. Эту задачу навигаторы не решают вовсе.
Первую называют поиском кратчайшего пути. У второй тоже есть имя - задача коммивояжёра, и оно старше компьютеров.
Почему вторая задача тяжёлая
Дело не в лени разработчиков. Дело в том, как быстро растёт число вариантов.
Если старт закреплён, а остальные точки можно переставлять как угодно, то количество возможных порядков объезда - это факториал.
Пять адресов - двадцать четыре варианта, их можно перебрать на бумаге. Восемь - уже пять тысяч. Десять - триста шестьдесят две тысячи. Пятнадцать - восемьдесят семь миллиардов.
И это не абстракция: каждый вариант нужно не просто перечислить, а сложить по нему расстояния - причём дорожные, а не по прямой. Расстояние по прямой врёт систематически: два адреса на разных берегах реки по прямой соседи, а по дорогам между ними десять километров до моста.
Почему это не встроили в навигатор
Причин несколько, и все практические.
Считать надо не в телефоне. Чтобы подобрать порядок, нужна матрица расстояний между всеми парами точек: для двадцати адресов это почти четыреста пар. Это работа сервера, а не приложения в дороге.
Ответ нужен до выезда, а не во время. Порядок объезда - решение, которое принимают один раз утром. Навигатор же сделан для того, что происходит в движении: пробки, поворот, перестроение.
У порядка есть условия, которых навигатор не знает. Клиент принимает с 14 до 16. Груз хрупкий и едет последним. У точки обед с 13 до 14. Кратчайший по километрам порядок при этом может оказаться просто невыполнимым.
Ошибка стоит по-разному. Ошибся с дорогой - потерял пять минут и перестроился. Ошибся с порядком - едешь лишние тридцать километров, и исправить это в середине смены уже нельзя.
Поэтому навигаторы честно делают то, что делают хорошо, а очерёдность оставляют человеку. У Яндекс.Карт, 2ГИС, Яндекс.Навигатора и Google Maps подход тут одинаковый.
Сколько это стоит на практике
Человек, который раскладывает адреса руками, обычно делает разумную вещь: группирует их по районам. Сначала весь юг, потом центр, потом север. Это уже неплохо и заметно лучше случайного порядка.
Но «неплохо» и «лучшее из возможного» - разные вещи. На двадцати адресах разложенный по районам список даёт около 153 километров, а посчитанный порядок - около 94. Разница почти сорок процентов, и она возникает целиком из очерёдности: адреса те же, машина та же, дороги те же.
Подробный разбор с цифрами и таблицей расхода - в статье про двадцать адресов за смену.
Как решают эту задачу на самом деле
Перебрать все варианты нельзя: для двадцати точек это больше ста квадриллионов порядков, и никакой сервер такого не считает.
Вместо перебора используют приближённые методы. Идея простая: взять любой разумный порядок и улучшать его, пока улучшается. Например, брать пару участков маршрута и проверять, не станет ли короче, если проехать их в обратную сторону. Такой приём называется 2-opt, и он на удивление хорош: за доли секунды приводит случайный порядок к результату, близкому к лучшему.
Важная честность: приближённый алгоритм не гарантирует идеала. Из двух разных стартовых порядков он может прийти к 94 и 99 километрам - оба ответа хорошие, но разные. Именно поэтому правильно говорить «посчитанный порядок», а не «оптимальный». На фоне 153 километров ручной раскладки эта разница роли не играет.
Что с этим делать
Это разделение труда, а не замена одного другим. Планировщик отвечает на вопрос «в каком порядке», навигатор - на вопрос «как доехать».
Когда считать не нужно
Здравый смысл никто не отменял:
- Точек мало. До пяти-шести адресов человек раскладывает не хуже алгоритма.
- Порядок задан не географией. Срочный заказ едет первым, даже если он дальний.
- Маршрут повторяется каждый день. Один раз посчитали - дальше едете по накатанной.
- Адреса выстроены вдоль одной дороги. Тут и оптимизировать нечего.
Считать стоит там, где точек больше десятка и они разбросаны по городу. Именно в этом случае разница между «по списку» и «по посчитанному порядку» превращается в часы за рулём и литры топлива.
Частые вопросы
Почему навигатор не строит оптимальный маршрут по нескольким точкам
Потому что это другая задача. Навигатор ищет лучшую дорогу между соседними точками, а не лучшую очерёдность всех точек сразу. Вторая задача требует матрицы расстояний и отдельного расчёта, и её решают до выезда.
Есть ли навигатор, который сам меняет порядок точек
Среди массовых навигаторов - нет. Порядок объезда считают планировщики маршрутов, а навигатор используют для езды по уже готовому списку.
Что такое задача коммивояжёра простыми словами
Это вопрос «в каком порядке объехать все точки и вернуться назад, чтобы проехать меньше всего». Сложность в том, что число возможных порядков растёт факториально: у десяти точек их больше трёхсот тысяч.
Можно ли посчитать оптимальный порядок точно
Для небольших списков - да, полным перебором. Для двадцати адресов точный перебор невозможен, поэтому используют приближённые методы: они дают порядок, очень близкий к лучшему, за доли секунды.
Насколько короче получается посчитанный маршрут
Зависит от того, насколько разбросаны адреса и насколько аккуратно составлен исходный список. На наших примерах пересчёт порядка давал от трети до сорока процентов пробега по сравнению с добросовестной ручной раскладкой по районам.
Учитывает ли расчёт порядка пробки
В планировщике - нет, и это осознанно: порядок объезда нужен на всю смену, а пробочная картина меняется за час-другой. Пробки учитывает навигатор, когда вы уже едете между двумя соседними точками.