Я строю систему планирования маршрута, но мне еще предстоит решить, какой базовый механизм маршрутизации я буду использовать. До сих пор я нашел pgrouting и neo4j.
У меня есть сеть маршрутов в базе данных postgresql / postgis (импортирована из шейп-файла). Я сделал запросы, чтобы извлечь узлы (конечные точки, где вы должны принять решение, в каком направлении идти или тупики) и извлечь края (часто составленные несколькими последовательными способами). Все мои ребра двунаправлены.
Моя главная цель - рассчитать маршруты в этой сети, используя алгоритм A-star, где расстояние = стоимость.
Мои ощущения подсказывают мне, что база данных графов, такая как neo4j, является подходящим способом (как кажется, она создана именно для этой цели), но они, по-видимому, не поддерживают A-star по умолчанию, а также не имеют реального смысла геометрии. , Кажется, лучше подходит для социальных сетей вместо карт.
- Будет ли pgrouting удовлетворить мои потребности?
- Это достаточно быстро для запросов на лету (+ -2000 узлов, + -4000 ребер)? Обычно это будет несколько мс для A-star, но я не уверен насчет реализации в sql.
- Дает ли pgrouting A-star список узлов и ребер?
- В большинстве примеров, которые я вижу о pgrouting, я замечаю, что обычно есть список команд после расчета маршрута (например, «При повороте влево и т. Д.»). Производит ли pgrouting это или это из другой системы?
Надеюсь, кто-нибудь может дать мне некоторую информацию о том, какую систему выбрать. Neo4j, pgrouting или какая-то другая система.
Ответы:
В настоящее время я изучаю ту же проблему, что и вы, с целью исследования. До того, как я начал тестировать эти две базы данных, у меня была такая же презумпция, как и у вас. Эта графическая база данных Neo4j была бы идеальным решением для такого рода проблем. И отчасти это так, но с множеством проблем.
Первая проблема заключается в том, что A-Star реализуется, только если вы используете встроенную базу данных, а не через REST API (сервер). Если вы хотите использовать Neo4j с REST API, то поддерживается только алгоритм Dijkstra. Вторая проблема - требования к аппаратной памяти для Neo4j. Для маршрутизации (Dijkstra) в «больших» сетях вам нужно много оперативной памяти. Для большой сети я имею в виду размер дорожной базы данных OSM в Германии . Я выполнил свои тесты на сервере ОЗУ 6 ГБ (это все, что у меня есть в настоящее время), и только небольшие сети могли маршрутизироваться без ошибок исключения OutOfMemory. «Маленькие» сети в моих тестовых случаях - это, например, дорожная база данных OSM для Австрии или Хорватии. Параллельные запросы, которые я до сих пор не проверял с Neo4j.
Все эти проблемы не существуют в pgRouting. Память не такая проблема, но параллельные запросы увеличивают необходимый объем памяти. Например, если у вас есть два одновременных запроса, необходим двойной объем памяти. Это не было проблемой даже для немецкого набора данных OSM, pgRouting без проблем маршрутизировал все одновременные запросы.
Производительность: в большинстве случаев Neo4j превосходит pgRouting. Но только если достаточно памяти для данного набора данных и если все узлы и отношения находятся в памяти (горячий старт). Увеличение / уменьшение производительности зависит от множества факторов, но в основном от размера сети и расстояния (прыжков) между исходным и целевым узлом.
Размер вашей сети довольно мал, поэтому у вас не должно быть проблем с памятью. Вероятно, Neo4j - неплохой выбор, но вам нужно адаптироваться к «немного» другой модели данных, чем в стандартных реляционных базах данных.
Чтобы ответить на ваши вопросы:
Я не знаю, поможет ли это вам напрямую, но одним из самых быстрых серверов маршрутизации, который я нашел, является osm2po . Он работает с набором данных OSM и работает довольно быстро. В настоящее время внедряется только dijkstra, но разработчик также объявил AStar. Я надеюсь, что это поможет вам. :)
источник
Вы также можете ознакомиться с нашим пакетом RW Net 4 (www.routeware.dk). Он может выполнять такие вычисления кратчайшего пути, используя A * прямо из файла SHP. Базовый пакет на 500 евро кажется достаточным для ваших нужд.
источник