Ayuda a elegir un motor de enrutamiento adecuado

16

Estoy creando un sistema de planificación de rutas, pero todavía 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 shapefile). He realizado consultas para extraer nodos (puntos finales de las formas en las que tiene que tomar una decisión sobre qué dirección tomar o callejones sin salida) y extraer bordes (a menudo con varias formas consecutivas). Todos mis bordes son bidireccionales.

Mi principal objetivo es calcular rutas en esta red utilizando un algoritmo A-star donde 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 parece que no son compatibles con A-star por defecto y tampoco hay una verdadera sentido de la geometría. Parece más adecuado para las redes sociales que para los mapas.

  • ¿Cumpliría con mis necesidades?
  • ¿Es lo suficientemente rápido para consultas sobre la marcha (+ -2000 nodos, + -4000 bordes)? Normalmente, esto sería unos pocos ms para A-star, pero no estoy seguro 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 acerca de la ruta, me doy cuenta de que normalmente hay una lista de comandos después del cálculo de la ruta (como "En X girar a la izquierda, etc."). ¿Produce Pgrouting esto o es otro sistema?

Esperemos que alguien me pueda dar alguna información sobre qué sistema elegir. Neo4j, pgrouting, o algún otro sistema.

    
pregunta mrg 24.08.2011 - 11:37

2 respuestas

8

Actualmente estoy explorando el mismo problema que usted, 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 usted. Esa base de datos gráfica Neo4j sería la solución perfecta para este tipo de problema. Y parcialmente 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 la API REST (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" se necesita una gran cantidad de RAM. Para grandes redes me refiero a algo como el tamaño de la base de datos de carreteras de Alemania OSM . He ejecutado mis pruebas en un servidor de RAM de 6GB (eso es todo lo que tengo actualmente) y solo las redes más pequeñas se pueden enrutar sin errores de excepción de 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 simultáneas que todavía no he probado con Neo4j.

Todos estos problemas no existen en pgRouting. La memoria no es un problema de este tipo, pero las consultas simultáneas aumentan la cantidad necesaria de memoria. Por ejemplo, si tiene dos solicitudes simultáneas, se necesita una cantidad doble de memoria. Esto no fue un problema incluso para un conjunto de datos OSM de Alemania, pgRouting enrutado sin ningún problema a 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 tiene que adaptarse a un "pequeño" modelo de datos diferente al de las bases de datos de relaciones estándar.

Para responder tus preguntas:

  • En pgRouting no tiene que preocuparse por la implementación de AStar en sql, que ya está implementado.
  • Sí, pgRouting puede darle una lista de nodos y bordes
  • No creo que pgRouting pueda darte esa información sin Algunos trabajos personalizados alrededor de las consultas. Pero tal vez me equivoque, tal vez alguien ha hecho esto y puede ayudarlo más sobre esta pregunta.

No sé si lo 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. Sólo dijkstra está implementado actualmente, pero el desarrollador anunció AStar también. Espero que algo de esto te ayude. :)

    
respondido por el Mario Miler 23.11.2011 - 13:00
0

También puede echar un vistazo a nuestro paquete RW Net 4 (www.routeware.dk). Puede realizar los cálculos de la ruta más corta utilizando A * directamente desde un archivo SHP. El paquete básico a 500 € parece suficiente para sus necesidades.

    
respondido por el Uffe Kousgaard 25.08.2011 - 09:33

Lea otras preguntas en las etiquetas