¿Hay algoritmos de enrutamiento más nuevos (que Dijkstra, A *) en las bases de datos GIS?

La verdad es que la mayoría de las personas utilizan 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 las heurísticas es Muy dependiente de los conjuntos de datos que utilizan.

Ya mencionó pgrouting , lo cual 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 intenta resolver y el enrutamiento es un problema graph .

Una vez más, los "chicos grandes" suelen tener 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 viaje multimodales (donde también tiene la opción de planificar "modos", sin caminos para bicicletas, solo transporte público, ese tipo de cosas). Puede pensar que la planificación del viaje también se convierte en un tema sensible al tiempo (es decir, si retrocede un poco atrás, podrá tomar el metro que lo lleva a su destino adelante mucho más rápido que si intentara navegar los bordes hacia adelante utilizando el costo más bajo).

Los "chicos grandes" no almacenan sus datos en una base de datos tradicional per se, utilizan gráficos precalculados (¡bienvenidos clusters de hadoop / mapreduce!). Como puedes 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 vea algunos proyectos de gráficos de enrutamiento multimodales:

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

Otra opción sería la OpenTripPlanner que tiene detrás mucha gente inteligente (incluidas las personas de graphserver).

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

  

El algoritmo Shooting-Star es el último   de los algoritmos pgRouting ruta más corta.   Su especialidad es que va desde   enlace a enlace, no desde vértice a   vértice como Dijkstra y A-Star   Los algoritmos hacen. Esto lo hace posible   para definir las relaciones entre los enlaces para   Ejemplo, y resuelve algunos otros.   problemas de algoritmos basados en vértices como   “Enlaces paralelos”, que tienen los mismos   Origen y destino, pero diferentes costos.

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

  

Buscando la ruta más corta exacta en un   conjunto de datos de red nacional es   consume mucho tiempo debido a la gran cantidad   de bordes que necesitan ser buscados. A   mejorar el rendimiento, datasets de red   puede modelar la jerarquía natural en una   sistema de transporte donde se conduce   una carretera interestatal es preferible   Conducir en carreteras locales. Una vez   Se ha creado una red jerárquica,   Una modificación del bidireccional.   Dijkstra se utiliza para calcular una ruta   entre un origen y un destino.

Hay una sección de las partes de las actividades de la empresa, que es muy sencilla, y está muy detallada en las partes de las actividades de la comunidad. con ejemplos de este enfoque en el sitio de ESRI, sin embargo, se requiere que inicie sesión para descargar (Informe de Rutas Jerárquicas en ArcGIS Network Analyst).

Contraction es un algoritmo muy rápido:

• enlace

Este algoritmo es compatible con la memoria RAM al ejecutar una consulta (para mantener un gráfico contratado es necesario algo más de RAM, así como un preprocesamiento masivo)

Hay algunos otros algoritmos, incluidos los que resuelven el enrutamiento de tránsito público:

• enlace

Microsoft también está haciendo algunas investigaciones:

• enlace

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

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

• enlace

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

actualizacion

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