Какие алгоритмы вычисляют направления от точки A к точке B на карте?

Question

Как поставщики карт (такие как Google или Yahoo! Maps) предлагают маршруты?

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

Алгоритмы графа, такие как алгоритм Дейкстры, не будут работать, потому что граф огромен. К счастью, эвристические алгоритмы типа A *, вероятно, будут работать. Тем не менее, наши данные очень структурированы, и, возможно, какой-то многоуровневый подход может сработать? (Например, сохраните предварительно вычисленные направления между определенными «ключевыми» точками далеко друг от друга, а также некоторые локальные направления. Тогда направления для двух удаленных точек будут включать локальные направления к ключевым точкам, глобальные направления к другой ключевой точке, а затем локальные направления снова.)

Какие алгоритмы фактически используются на практике?

PS. Этот вопрос был мотивирован нахождением причуд в направлениях картографирования онлайн. Вопреки неравенству треугольника, иногда Карты Google считают, что X-Z занимает больше времени и дальше, чем использование промежуточной точки, как в X-Y-Z . Но, может быть, их маршруты для прогулок тоже оптимизированы для другого параметра?

PPS. Вот еще одно нарушение неравенства треугольника, которое предполагает (для меня), что они используют какой-то многоуровневый подход: X-Z против X-Y-Z . Бывший, кажется, использует выдающийся Севастопольский бульвар, хотя он немного в стороне.

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

Answer 1

Говоря как кто-то, кто провел 18 месяцев, работая в картографической компании, включая работу над алгоритмом маршрутизации ... да, Дейкстра работает, с парой модификаций:

• Вместо того, чтобы делать Дейкстры один раз от источника к месту, вы начинаете с каждого конца и расширяете обе стороны, пока они не встретятся посередине. Это исключает примерно половину работы (2 * pi * (r / 2) ^ 2 против pi * r ^ 2).
• Чтобы избежать изучения переулков каждого города между вашим источником и пунктом назначения, у вас может быть несколько слоев картографических данных: слой «шоссе», содержащий только шоссе, «вторичный» слой, содержащий только второстепенные улицы, и так далее. Затем вы исследуете только более мелкие разделы более подробных слоев, расширяясь по мере необходимости. Очевидно, что это описание оставляет много деталей, но вы поняли идею.

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

Answer 2

Этот вопрос был активной областью исследования в последние годы. Основная идея состоит в том, чтобы выполнить предварительную обработку на графике один раз , чтобы ускорить все после запросов . С помощью этой дополнительной информации маршруты могут быть рассчитаны очень быстро. Тем не менее, Алгоритм Дейкстры является основой для всех оптимизаций.

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

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

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

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

Если вам нужны кратчайшие расстояния для вычисления решения для TSP , то вас, вероятно, интересуют матрицы, которые содержат все расстояния между вашими источниками и пунктами назначения. Для этого вы можете рассмотреть Вычисление кратчайших путей «многие ко многим» с использованием иерархий дорог . Обратите внимание, что это было улучшено новыми подходами за последние 2 года.

Answer 3

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

Если Y является узкой жилой улицей между X и Z, вы, вероятно, захотите использовать ярлык только через Y, если пользователь явно запрашивает X-Y-Z. Если они просят X-Z, они должны придерживаться главных дорог, даже если это немного дальше и занимает немного больше времени. Это похоже на парадокс Брейса - если каждый пытается выбрать самый короткий и быстрый маршрут, то в результате этого затор означает, что это уже не самый быстрый маршрут для кого-либо. Отсюда мы отклоняемся от теории графов в теорию игр.

[1] Фактически, любая надежда на то, что полученные расстояния будут функцией расстояния в математическом смысле, умирает, когда вы разрешаете односторонние дороги и теряете требование симметрии. Потерять неравенство треугольника - это просто растереть соль в ране.

Answer 4

Вот самые быстрые в мире алгоритмы маршрутизации, проверенные на правильность:

http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf

Вот технический доклад Google на эту тему:

http://www.youtube.com/watch?v=-0ErpE8tQbw

Вот реализация алгоритма иерархии шоссе, которая обсуждалась Шультесом (в настоящее время только в Берлине, я пишу интерфейс, а также разрабатывается мобильная версия):

http://tom.mapsforge.org/

Answer 5

Я раньше не работал на Google, Microsoft или Yahoo Maps, поэтому не могу рассказать вам, как они работают.

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

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

Вы можете найти Google ACO или TSP, чтобы узнать больше об этой технике. Однако для этого я не использовал ни один из инструментов AI с открытым исходным кодом, поэтому не могу предложить ни одного (хотя я слышал, что SWARM был довольно всеобъемлющим).

Answer 6

Алгоритмы графа, такие как алгоритм Дейкстры, не будут работать, потому что граф огромен.

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

Дейкстра на самом деле может работать довольно хорошо для графиков с хорошим поведением. С другой стороны, при тщательной параметризации A * всегда будет работать так же хорошо или лучше. Вы уже пробовали, как это будет работать с вашими данными?

Тем не менее, мне также было бы очень интересно услышать об опыте других людей. Конечно, такие интересные примеры, как поиск в Google Map, особенно интересны. Я мог бы представить что-то вроде эвристики, ориентированной на ближайшего соседа.

Answer 7

Современным уровнем техники с точки зрения времени запросов для статических дорожных сетей является алгоритм маркировки концентратора, предложенный Abraham et al. http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20. Сквозное и превосходно написанное исследование области было недавно опубликовано в виде технического отчета Microsoft http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf.

Короткая версия ...

Алгоритм маркировки концентратора обеспечивает самые быстрые запросы для статических дорожных сетей, но для его работы требуется большое количество оперативной памяти (18 ГиБ).

Маршрутизация транзитного узла немного медленнее, хотя для этого требуется всего около 2 ГБ памяти и время для предварительной обработки сокращается.

Иерархии сжатия обеспечивают хороший компромисс между быстрым временем предварительной обработки, низкими требованиями к пространству (0,4 ГиБ) и быстрым временем запроса.

Ни один алгоритм не является полностью доминирующим ...

Этот технический доклад Google Питера Сандерса может представлять интерес

https://www.youtube.com/watch?v=-0ErpE8tQbw

Также этот разговор Эндрю Голдберга

https://www.youtube.com/watch?v=WPrkc78XLhw

Внедрение иерархий сокращений с открытым исходным кодом доступно на веб-сайте исследовательской группы Питера Сандерса в KIT. http://algo2.iti.kit.edu/english/routeplanning.php

Также легко доступное сообщение в блоге, написанное Microsoft об использовании алгоритма CRP ... http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/

Answer 8

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

Answer 9

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

Лучшим решением, которое я принял, было использование A * с расстоянием по прямой линии в качестве эвристической функции. Но тогда вам нужны какие-то координаты для каждой точки (пересечения или вершины) на карте. Вы также можете попробовать разные значения веса для эвристической функции, т.е.

f(n) = k*h(n) + g(n)

, где k - некоторая постоянная, больше 0.

Answer 10

Вероятно, аналогично ответу на предварительно вычисленных маршрутах между основными местоположениями и многоуровневыми картами, но я понимаю, что в играх, чтобы ускорить A *, у вас есть карта, которая очень грубая для макро-навигации, и точная подробная карта для навигации к границе макропередач. Таким образом, у вас есть 2 маленьких пути для расчета, и, следовательно, ваше пространство поиска намного меньше, чем просто сделать один путь к месту назначения. И если вы делаете это много, у вас будет много предварительно вычисленных данных, поэтому, по крайней мере, часть поиска - это поиск предварительно вычисленных данных, а не поиск пути.