¿Existen nuevos algoritmos de enrutamiento (que Dijkstra, A *) en las bases de datos SIG?

46

Hay trabajos como Reach for A * de investigadores de Microsoft y Highway Hierarchies de Sanders y Schtolz (si deletreo el nombre correctamente) de Karlsruhe Uni . Ambos reducen mucho el orden de los cálculos y se aceleran mil veces en gráficos grandes (vea los resultados en los documentos vinculados). El último trabajo condujo a la Máquina de enrutamiento de código abierto , que desafortunadamente no es lo suficientemente popular y no está adaptada (no pude compilarlo aunque lo intenté mucho).

Al mismo tiempo, los dbs que probé, Spatialite y PgRouting, según sus documentos, ofrecen solo algoritmos Dijkstra y A * . Ni siquiera he mencionado la búsqueda bidireccional mencionada, lo que ahorra tiempo de cálculo dos veces en mi experiencia.

¿Hay mejores algoritmos para bases de datos u otras aplicaciones?

culebrón
fuente
1
¿Ha publicado su pregunta en las listas de correo electrónico de usuarios o desarrolladores de pgRouting? Es posible que obtenga una mejor respuesta directamente de esa comunidad. Lista de usuarios: ( lists.osgeo.org/mailman/listinfo/pgrouting-users ) Lista de desarrolladores: ( lists.osgeo.org/mailman/listinfo/pgrouting-dev )
RyanDalton
+1 Gran pregunta. Me pregunto qué algoritmo usa Google para obtener indicaciones . Pregunta relacionada aquí .
Kirk Kuykendall
1
Dado que Google apoyó al equipo de Karlsruhe ( algo2.iti.uni-karlsruhe.de/english/index.php ) supongo que usan su software, que es esencialmente una máquina de enrutamiento de código abierto.
culebrón

Respuestas:

23

La verdad es que la mayoría de las personas usa una variación personalizada del algoritmo A * . Verá esto en la mayoría de los "grandes" (no puedo decir quiénes son en un foro público, pero puedo decirle que probablemente use uno de ellos, garantizado), donde la modificación de la heurística es muy dependiente de los conjuntos de datos que usan.

Ya mencionaste pgrouting , lo que yo consideraría una opción "tradicional". Es bueno para hacer algoritmos de enrutamiento simples y para la mayoría de los problemas. También es fácil de usar y utiliza una base de datos tradicional en su backend.

Sin embargo, realmente depende de la escala y el tipo de problema que está tratando de resolver y el enrutamiento es un problema gráfico .

Una vez más, los "grandes" generalmente tienen una gran cantidad de datos asociados con su gráfico (por ejemplo, datos de tráfico, rutas de autobuses, rutas de senderismo) que afectan el algoritmo de enrutamiento. Estos se conocen como planificadores de viajes multimodales (donde también tiene la opción de planificar "modos", sin carriles bici, solo transporte público, ese tipo de cosas). Puede pensar cómo la planificación del viaje también se convierte en un asunto sensible al tiempo (es decir, si se camina hacia atrás unos bordes hacia atrás, usted será capaz de coger el metro que le lleva a su destino hacia adelante mucho más rápido que si usted acaba de intentar navegar por los bordes hacia adelante usando el costo más bajo).

Los "grandes" no almacenan sus datos en una base de datos tradicional per se, usan gráficos precalculados (¡bienvenidos clusters de hadoop / mapreduce!). Como puede imaginar, estos gráficos se vuelven realmente grandes, por lo que saber cómo conectar los bordes de los gráficos adyacentes puede ser un desafío.

De todos modos, le recomendaría que mire algunos proyectos de gráficos de enrutamiento multimodales:

Graphserver viene a la mente. No hay mucha documentación, sino mucha genialidad de codificación pura (AFAIK, creo que MapQuest utiliza una variación de este proyecto para algunos de sus productos de enrutamiento).

Otra opción sería OpenTripPlanner, que tiene muchas personas inteligentes detrás (incluidas personas de Graphserver).

Ragi Yaser Burhum
fuente
15

No estoy seguro si es más nuevo pero pgRouting tiene un algoritmo Shooting-Star :

El algoritmo Shooting-Star es el último de los algoritmos de ruta más corta de pgRouting. Su especialidad es que se enruta de enlace en enlace, no de vértice a vértice como lo hacen los algoritmos Dijkstra y A-Star. Esto hace posible definir relaciones entre enlaces, por ejemplo, y resuelve algunos otros problemas de algoritmos basados ​​en vértices como "enlaces paralelos", que tienen el mismo origen y destino pero diferentes costos.

La extensión de Network Analyst de ESRI utiliza el enfoque jerárquico que mencionó para limitar los tiempos de resolución:

Encontrar la ruta más corta exacta en un conjunto de datos de red a nivel nacional lleva mucho tiempo debido a la gran cantidad de bordes que deben buscarse. Para mejorar el rendimiento, los conjuntos de datos de red pueden modelar la jerarquía natural en un sistema de transporte en el que es preferible conducir por una carretera interestatal a las carreteras locales. Una vez que se ha creado una red jerárquica, se utiliza una modificación de Dijkstra bidireccional para calcular una ruta entre un origen y un destino.

Hay una muy detallada de papel blanco con ejemplos de este enfoque en el sitio de ESRI - sin embargo, requiere que iniciar sesión para descargar (Rutas jerárquicos en ArcGIS Network Analyst Libro Blanco).

geographika
fuente
11

La Jerarquía de Contracción es un algoritmo muy rápido:

Este algoritmo es compatible con RAM mientras se ejecuta una consulta (para mantener un gráfico contratado se necesita más RAM, así como un preprocesamiento masivo)

Existen algunos otros algoritmos, incluidos los que resuelven el enrutamiento de transporte público:

Microsoft también está investigando un poco:

(bueno, Daniel Delling también es de Karlsruhe)

Puede obtener una buena introducción y una descripción general de los algoritmos disponibles:

Advertencia: conferencias alemanas (!). ¡pero al menos los encabezados pueden ayudarlo a obtener más información (ALT, Arc-Flags, CHASE, ...) o la literatura adjunta!

actualizar

GraphHopper ahora implementa jerarquías de contracción y también otros algoritmos, también puede probar la demostración .

Karussell
fuente