Маршрутизация по карте, как в Google Maps?

Question

Меня всегда интересовала Map Routing, но я никогда не находил по ней хороших руководств вводного (или даже продвинутого!) уровня.Есть ли у кого-нибудь какие-либо указатели, подсказки и т.д.?

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

Answer 1

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

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

Answer 2

Барри Брамитт, один из инженеров функции поиска маршрутов на картах Google, написал пост на тему, которая может представлять интерес:

Путь к лучшему поиску пути06.11.2007 15:47:00

Answer 3

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

Answer 4

Под картографической маршрутизацией вы подразумеваете поиск кратчайшего пути в уличной сети?

Алгоритм поиска кратчайшего пути Дейкстры является наиболее известным.В Википедии есть неплохое вступление: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Здесь есть Java-апплет, где вы можете увидеть его в действии: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html и Google вы приведете вас к исходному коду практически на любом языке.

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

Answer 5

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

«Mapstraction — это библиотека, которая предоставляет общий API для различных API-интерфейсов сопоставления JavaScript»

Я бы посоветовал вам перейти по URL-адресу и изучить общий API.Также имеется большое количество инструкций.

Answer 6

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

Существуют приложения маршрутизации GPL, которые используют данные Openstreetmap, например. Госмор который работает на Windows (+ mobile) и Linux.Существует ряд интересных [приложений, использующих одни и те же данные, но у Gosmore есть несколько интересных вариантов использования. напримеринтерфейс с веб-сайтами.

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

Answer 7

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

Конечно, алгоритму придется искать некоторую долю путей из n^2 по мере увеличения расстояния n.Вы должны занять исходную позицию и проверить все доступные пути из этой точки.Затем рекурсивно вызывайте точки в конце этих путей и так далее.

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

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

РЕДАКТИРОВАТЬ @ Спики

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

Вам нужно будет сохранить карту как сеть.Это просто набор nodes и edges между ними.Набор nodes представляют собой route.Ребро соединяет два узла (возможно, один и тот же узел) и имеет связанный cost такой как distance или time чтобы пересечь край.Край может быть двунаправленным или однонаправленным.Вероятно, проще всего иметь однонаправленные и удвоить их для двустороннего перемещения между узлами (т. е.одно ребро от A до B и другое от B до A).

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

Обозначьте узлы, начиная снизу слева, слева направо и вверх, как A,B,C,D,E,F (F вверху).

Предположим, что края можно пересекать в любом направлении.Каждое ребро имеет стоимость 1 км.

Итак, мы хотим проложить маршрут от нижней левой станции A до верхней станции F.Существует много возможных маршрутов, в том числе те, которые возвращаются в себя, например.АБЦЕБДЕФ.

У нас есть рутина, скажем: NextNode, который принимает node и cost и вызывает себя для каждого узла, к которому он может отправиться.

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

Если мы достигнем целевого узла, мы также выйдем из процедуры.

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

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

Узел A – (общая) стоимость 0 – с узла Нет
Узел B – Стоимость 1 – от узла A
Узел C – Стоимость 2 – от узла B
Узел D – Стоимость 1 – От узла A
Узел E — Стоимость 2 — От узла D / Стоимость 2 — От узла B (это исключение, поскольку стоимость одинаковая)
Узел F – Стоимость 2 – от узла D

Итак, кратчайший путь — ADF.

Answer 8

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

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

Сам алгоритм A* хорошо описано в Википедии.Ключевое место оптимизации — выбор лучшей ноды из открытого списка, для чего нужна высокопроизводительная приоритетная очередь.Если вы используете C++, вы можете использовать адаптер STL Priority_queue.

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

Answer 9

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

Пример: Согласно GoogleMaps, я могу (там, где я живу) добраться из пункта А в пункт Б тремя способами.Устройства Garmin предлагают каждый из этих трех путей в Quickest расчет маршрута.После многократного прохождения каждого из этих маршрутов и усреднения (очевидно, будут ошибки в зависимости от времени суток, количества кофеина и т. д.), я чувствую, что алгоритмы могут учитывать количество поворотов на дороге для высокого уровня точности. , например прямая дорога длиной в 1 милю будет быстрее, чем дорога длиной в 1 милю с крутыми поворотами.Это не практичное предложение, но я определенно использую его для улучшения результатов своих ежедневных поездок на работу.