Estoy construyendo un sistema de planificación de rutas, pero aún tengo que decidir qué motor de enrutamiento subyacente usaré. Hasta ahora he encontrado pgrouting y neo4j.
Tengo mi red de rutas en una base de datos postgresql / postgis (importada de un archivo shape). He realizado consultas para extraer nodos (puntos finales de formas en las que tiene que tomar una decisión en qué dirección ir o callejones sin salida) y extraer bordes (a menudo formados por varias formas consecutivas). Todos mis bordes son bidireccionales.
Mi objetivo principal es calcular rutas en esta red utilizando un algoritmo de estrella A donde la distancia = costo.
Mi sensación me dice que una base de datos de gráficos como neo4j es el camino a seguir (ya que parece estar hecho solo para este propósito), pero no parecen admitir la estrella A por defecto y tampoco hay un sentido real de geometría . Parece más adecuado para redes sociales en lugar de mapas.
- ¿Pgrouting satisfaría mis necesidades?
- ¿Es lo suficientemente rápido para consultas sobre la marcha (+ -2000 nodos, + -4000 aristas)? Normalmente, esto sería unos pocos ms para A-star, pero no estoy seguro acerca de esta implementación en sql.
- ¿Pgrouting A-star me da una lista de nodos y aristas?
- En la mayoría de los ejemplos que veo sobre pgrouting, noto que generalmente hay una lista de comandos después del cálculo de la ruta (como "En X gire a la izquierda, etc."). ¿Pgrouting produce esto o es de otro sistema?
Espero que alguien pueda darme información sobre qué sistema elegir. Neo4j, pgrouting u otro sistema.
Respuestas:
Actualmente estoy explorando el mismo problema que tú, con el propósito de un trabajo de investigación. Antes de comenzar a probar estas dos bases de datos, tenía la misma presunción que tú. Esa base de datos de gráficos Neo4j sería la solución perfecta para este tipo de problema. Y en parte lo es, pero con muchos problemas.
El primer problema es que A-Star solo se implementa si está utilizando una base de datos integrada, no a través de REST API (servidor). Si desea utilizar Neo4j con REST API, solo se admite el algoritmo Dijkstra. El segundo problema son los requisitos de memoria de hardware para Neo4j. Para el enrutamiento (Dijkstra) en redes "más grandes" necesita mucha RAM. Para una red grande me refiero a algo como el tamaño de la base de datos de carreteras OSM de Alemania . He realizado mis pruebas en un servidor RAM de 6 GB (eso es todo lo que tengo actualmente) y solo las redes más pequeñas podrían enrutarse sin errores de excepción OutOfMemory. Las redes "pequeñas" en mis casos de prueba son, por ejemplo, la base de datos de carreteras OSM para Austria o Croacia. Consultas concurrentes que todavía no he probado con Neo4j.
Todos estos problemas no existen en pgRouting. La memoria no es un problema, pero las consultas concurrentes aumentan la cantidad de memoria necesaria. Por ejemplo, si tiene dos solicitudes simultáneas, se necesita el doble de memoria. Esto no fue un problema incluso para un conjunto de datos OSM de Alemania, pgRouting enrutado sin problemas todas las solicitudes concurrentes.
Rendimiento: en la mayoría de los casos, Neo4j supera a pgRouting. Pero solo si hay suficiente memoria para el conjunto de datos dado y si todos los nodos y relaciones están en la memoria (inicio en caliente). El aumento / disminución del rendimiento depende de muchos factores, pero principalmente del tamaño de la red y la distancia (saltos) entre el nodo de origen y el de destino.
El tamaño de su red es bastante pequeño, por lo que no debería tener ningún problema con la memoria. Probablemente Neo4j no sea una mala elección, pero debe adaptarse a un "pequeño" modelo de datos diferente al de las bases de datos de relaciones estándar.
Para responder a sus preguntas:
No sé si te ayudará directamente, pero uno de los servidores de enrutamiento más rápidos que encontré es osm2po . Funciona con el conjunto de datos OSM y es bastante rápido. Actualmente solo se ha implementado dijkstra, pero el desarrollador también anunció AStar. Espero que algo de esto te ayude. :)
fuente
También puede echar un vistazo a nuestro paquete RW Net 4 (www.routeware.dk). Puede hacer cálculos de ruta más cortos utilizando A * directamente desde un archivo SHP. El paquete básico de 500 € parece suficiente para sus necesidades.
fuente