Существуют ли более новые алгоритмы маршрутизации (чем Dijkstra, A *) в базах данных ГИС?

46

Есть такие работы, как Reach for A * от исследователей Microsoft и Highway Hierarchies Сандерса и Штольца (если я правильно произношу это имя) из Karlsruhe Uni . Оба они значительно уменьшают порядок вычислений и ускоряют работу в тысячи раз на больших графиках (см. Результаты в связанных документах). Последняя работа привела к созданию Open Source Routing Machine , которая, к сожалению, недостаточно популярна и не адаптирована (я не смог скомпилировать ее, хотя и старался).

В то же время, пробные базы данных, Spatialite и PgRouting, согласно их документам, предлагают только алгоритмы Dijkstra и A * . Я даже не упомянул двунаправленный поиск, который в моем опыте экономит время вычислений дважды.

Есть ли лучшие алгоритмы для баз данных или других приложений?

culebrón
источник
1
Вы разместили свой вопрос в списках рассылки пользователей или разработчиков pgRouting? Вы можете получить лучший ответ непосредственно из этого сообщества. Список пользователей: ( lists.osgeo.org/mailman/listinfo/pgrouting-users ) Список разработчиков: ( lists.osgeo.org/mailman/listinfo/pgrouting-dev )
RyanDalton
+1 Отличный вопрос. Интересно, какой алгоритм использует Google для получения маршрутов . Связанный вопрос здесь .
Кирк Куйкендалл
1
Так как Google поддержал команду Карлсруэ ( algo2.iti.uni-karlsruhe.de/english/index.php ), я полагаю, что они используют свое программное обеспечение, которое по сути является машиной с открытым исходным кодом.
culebrón

Ответы:

23

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

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

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

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

«Большие парни» не хранят свои данные в традиционной базе данных как таковые, они используют предварительно вычисленные графы (добро пожаловать в кластеры hadoop / mapreduce!). Как вы можете себе представить, эти графы становятся действительно большими, поэтому знание того, как соединить ребра смежных графов, может стать проблемой.

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

Graphserver приходит на ум. Не много документации, но много чистого кода (AFAIK, я думаю, MapQuest использует вариант этого проекта для некоторых своих продуктов маршрутизации).

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

Раги Язер Бурхум
источник
15

Не уверен, что он новее, но pgRouting имеет алгоритм Shooting-Star :

Алгоритм Shooting-Star является последним из алгоритмов кратчайшего пути pgRouting. Его особенность заключается в том, что он переходит от ссылки к ссылке, а не от вершины к вершине, как это делают алгоритмы Дейкстры и А-Стар. Это позволяет, например, определить отношения между ссылками и решить некоторые другие проблемы, связанные с алгоритмами на основе вершин, такие как «параллельные ссылки», которые имеют одинаковые источник и цель, но разные затраты.

Расширение ESRI Network Analyst использует упомянутый вами иерархический подход для ограничения времени решения:

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

На сайте ESRI есть очень подробная техническая документация с примерами этого подхода, однако для загрузки требуется войти в систему (Иерархические маршруты в документе ArcGIS Network Analyst).

geographika
источник
11

Сократительная иерархия - это очень быстрый алгоритм:

Этот алгоритм дружествен к ОЗУ при выполнении запроса (для хранения сжатого графа требуется еще немного ОЗУ, а также массовая предварительная обработка)

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

Microsoft также проводит некоторые исследования:

(ну, Даниэль Деллинг тоже из Карлсруэ)

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

Внимание: немецкие (!) Лекции. но по крайней мере заголовки могут помочь вам получить больше информации (ALT, Arc-Flags, CHASE, ...) или прилагаемой литературы!

Обновить

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

Karussell
источник