¿Qué algoritmos calculan las direcciones del punto A al punto B en un mapa?

¿Cómo sugieren los proveedores de mapas (como Google o Yahoo Maps)?

Quiero decir, es probable que tengan datos del mundo real de alguna forma, incluyendo distancias, pero también cosas como velocidades de manejo, presencia de aceras, horarios de trenes, etc. Pero supongamos que los datos están en un formato más simple, digamos un gráfico dirigido muy grande con pesas de borde que reflejan distancias. Quiero ser capaz de calcular rápidamente las direcciones de un punto arbitrario a otro. A veces estos puntos estarán muy juntos (dentro de una ciudad) mientras que a veces estarán muy separados (campo a través).

Los algoritmos de gráficos como el algoritmo de Dijkstra no funcionarán porque el gráfico es enorme. Afortunadamente, los algoritmos heurísticos como A * probablemente funcionen. Sin embargo, nuestros datos son muy estructurados, ¿y tal vez algún tipo de enfoque escalonado podría funcionar? (Por ejemplo, almacene las direcciones precalculadas entre ciertos puntos “clave” muy alejados, así como algunas direcciones locales. Luego, las direcciones para dos puntos lejanos implicarán direcciones locales a puntos clave, direcciones globales a otro punto clave, y luego local direcciones de nuevo.)

¿Qué algoritmos se usan realmente en la práctica?

PD. Esta pregunta fue motivada por la búsqueda de caprichos en las direcciones de mapas en línea. Contrariamente a la desigualdad del triángulo, a veces Google Maps piensa que XZ lleva más tiempo y está más lejos que usar un punto intermedio como en XYZ . Pero tal vez sus indicaciones para caminar optimizan para otro parámetro, también?

PPS. Aquí hay otra violación de la desigualdad triangular que sugiere (para mí) que usan algún tipo de enfoque escalonado: XZ versus XYZ . El primero parece usar el destacado Boulevard de Sebastopol a pesar de que está un poco alejado del camino.

Editar : Ninguno de estos ejemplos parece funcionar más, pero ambos lo hicieron en el momento de la publicación original.

Hablando como alguien que pasó 18 meses trabajando en una compañía de cartografía, lo que incluyó trabajar en el algoritmo de enrutamiento … sí, el de Dijkstra funciona, con un par de modificaciones:

  • En lugar de hacer Dijkstra una vez de la fuente al destino, comienzas en cada extremo y expandes ambos lados hasta que se encuentran en el medio. Esto elimina aproximadamente la mitad del trabajo (2 * pi * (r / 2) ^ 2 vs pi * r ^ 2).
  • Para evitar explorar los callejones de cada ciudad entre su origen y destino, puede tener varias capas de datos de mapas: una capa de ‘autopistas’ que contiene solo carreteras, una capa ‘secundaria’ que contiene solo calles secundarias, y así sucesivamente. Luego, explora solo secciones más pequeñas de las capas más detalladas, expandiéndolas según sea necesario. Obviamente, esta descripción deja de lado muchos detalles, pero entiendes la idea.

Con modificaciones a lo largo de esas líneas, puede hacer incluso el enrutamiento a campo traviesa en un marco de tiempo muy razonable.

Esta pregunta ha sido un área activa de investigación en los últimos años. La idea principal es hacer un preprocesamiento en el gráfico una vez , para acelerar todas las consultas siguientes . Con esta información adicional, los itinerarios se pueden calcular muy rápido. Aún así, el algoritmo de Dijkstra es la base de todas las optimizaciones.

Arachnid describió el uso de búsqueda bidireccional y poda de borde en base a información jerárquica. Estas técnicas de aceleración funcionan bastante bien, pero los algoritmos más recientes superan por mucho a estas técnicas. Con los algoritmos actuales, las rutas más cortas se pueden calcular en un tiempo considerablemente menor que un milisegundo en una red vial continental. Una implementación rápida del algoritmo no modificado de Dijkstra necesita aproximadamente 10 segundos .

El artículo Engineering Fast Route Planning Algorithms da una visión general del progreso de la investigación en ese campo. Ver las referencias de ese documento para más información.

Los algoritmos más rápidos conocidos no utilizan información sobre el estado jerárquico de la carretera en los datos, es decir, si se trata de una carretera o una carretera local. En cambio, calculan en un paso de preprocesamiento una jerarquía propia que se optimiza para acelerar la planificación de rutas. Esta precomputación se puede utilizar para podar la búsqueda: lejos del inicio y el destino, las carreteras lentas no necesitan considerarse durante el algoritmo de Dijkstra. Los beneficios son muy buen rendimiento y una garantía de corrección para el resultado.

Los primeros algoritmos de planificación de rutas optimizados solo trataban con redes de carreteras estáticas, lo que significa que un borde en el gráfico tiene un valor de costo fijo. Esto no es cierto en la práctica, ya que queremos tener en cuenta la información dinámica como atascos de tráfico o restricciones de vehículos dependientes. Los últimos algoritmos también pueden tratar estos problemas, pero aún hay problemas por resolver y la investigación continúa.

Si necesita las distancias de ruta más cortas para calcular una solución para el TSP , entonces probablemente esté interesado en matrices que contengan todas las distancias entre sus fonts y destinos. Para esto, podría considerar el cálculo de trayectos cortos de muchos a muchos utilizando jerarquías de carreteras . Tenga en cuenta que esto se ha mejorado con enfoques más nuevos en los últimos 2 años.

Solo abordando las violaciones de la desigualdad triangular, con suerte el factor adicional para el que están optimizando es el sentido común. No necesariamente quiere la ruta más corta o más rápida, ya que puede provocar caos y destrucción . Si desea que sus instrucciones prefieran las principales rutas que son aptas para camiones y puede hacer frente a que cada controlador de navegación por satélite las envíe, descarta rápidamente la desigualdad de triángulo [1].

Si Y es una calle residencial estrecha entre X y Z, probablemente solo desee utilizar el acceso directo a través de Y si el usuario solicita XYZ explícitamente. Si preguntan por XZ, deberían apegarse a las carreteras principales, aunque sea un poco más lejos y demore un poco más. Es similar a la paradoja de Braess : si todos intentan tomar la ruta más corta y más rápida, la congestión resultante significa que ya no es la ruta más rápida para nadie. A partir de aquí, nos desviamos de la teoría de grafos hacia la teoría de juegos.

[1] De hecho, cualquier esperanza de que las distancias producidas sean una función de distancia en el sentido matemático muere cuando permite carreteras de un solo sentido y pierde el requisito de simetría. Perder la desigualdad del triángulo también es solo frotar sal en la herida.

Aquí están los algoritmos de enrutamiento más rápidos del mundo comparados y probados para ser correctos:

http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf

Aquí hay una charla técnica de google sobre el tema:

http://www.youtube.com/watch?v=-0ErpE8tQbw

Aquí hay una implementación del algoritmo de jerarquías de autopistas discutido por schultes (actualmente solo en Berlín, estoy escribiendo la interfaz y también se está desarrollando una versión móvil):

http://tom.mapsforge.org/

Los algoritmos de gráficos como el algoritmo de Dijkstra no funcionarán porque el gráfico es enorme.

Este argumento no necesariamente se cumple porque Dijkstra generalmente no mira el gráfico completo sino más bien un subconjunto muy pequeño (cuanto mejor se interconecta el gráfico, más pequeño es este subconjunto).

Dijkstra en realidad puede funcionar bastante bien para gráficos de buen comportamiento. Por otro lado, con una parametrización cuidadosa, A * siempre funcionará igual de bien o mejor. ¿Ya has probado cómo funcionaría en tus datos?

Dicho esto, también estaría muy interesado en conocer las experiencias de otras personas. Por supuesto, ejemplos prominentes como la búsqueda de Google Map son particularmente interesantes. Podría imaginar algo así como una heurística dirigida al vecino más cercano.

No he trabajado en Google, Microsoft o Yahoo Maps antes, así que no puedo decir cómo funcionan.

Sin embargo, diseñé un sistema de optimización de cadena de suministro personalizado para una compañía de energía que incluía una aplicación de progtwigción y enrutamiento para su flota de camiones. Sin embargo, nuestros criterios sobre el enrutamiento eran mucho más específicos de un negocio que dónde se ralentiza la construcción o el tráfico o el cierre de carriles.

Empleamos una técnica llamada ACO (optimización de colonia de ants) para progtwigr y enrutar camiones. Esta técnica es una técnica de IA que se aplicó al problema del vendedor ambulante para resolver problemas de enrutamiento. El truco con ACO es construir un cálculo de error basado en hechos conocidos del enrutamiento para que el modelo de resolución de gráficos sepa cuándo dejarlo (cuando el error es lo suficientemente pequeño).

Puede buscar en Google ACO o TSP para obtener más información sobre esta técnica. Sin embargo, no he usado ninguna de las herramientas de código abierto de inteligencia artificial para esto, así que no puedo sugerir una (aunque escuché que SWARM era bastante completo).

El estado actual de la técnica en términos de tiempos de consulta para redes estáticas de carreteras es el algoritmo de etiquetado Hub propuesto por Abraham et al. http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20 . Recientemente se publicó una encuesta exhaustiva y bien escrita del campo como un informe técnico de Microsoft http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf .

La versión corta es …

El algoritmo de etiquetado de Hub proporciona las consultas más rápidas para redes de carreteras estáticas, pero requiere una gran cantidad de ram para ejecutar (18 GiB).

El enrutamiento del nodo de tránsito es un poco más lento, aunque solo requiere alrededor de 2 GiB de memoria y tiene un tiempo de preprocesamiento más rápido.

Las jerarquías de contracción proporcionan una buena compensación entre tiempos de preprocesamiento rápidos, requisitos de espacio reducido (0,4 GiB) y tiempos de consulta rápidos.

Ningún algoritmo es completamente dominante …

Esta charla técnica de Google por Peter Sanders puede ser de interés

https://www.youtube.com/watch?v=-0ErpE8tQbw

También esta charla de Andrew Goldberg

https://www.youtube.com/watch?v=WPrkc78XLhw

Una implementación de fuente abierta de las jerarquías de contracción está disponible en el sitio web del grupo de investigación Peter Sanders en KIT. http://algo2.iti.kit.edu/english/routeplanning.php

También una publicación de blog de fácil acceso escrita por Microsoft sobre el uso del algoritmo CRP … http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/

Estoy un poco sorprendido de no ver el algoritmo de Floyd Warshall mencionado aquí. Este algoritmo funciona muy parecido al de Dijkstra. También tiene una característica muy buena que le permite calcular todo el tiempo que desee para continuar permitiendo más vértices intermedios. Por lo tanto, encontrará naturalmente las rutas que utilizan carreteras interestatales o carreteras con bastante rapidez.

Lo he hecho muchas veces, de hecho, probando varios métodos diferentes. Dependiendo del tamaño (geográfico) del mapa, es posible que desee considerar el uso de la función haversine como una heurística.

La mejor solución que he hecho fue usar A * con una distancia en línea recta como función heurística. Pero luego necesita algún tipo de coordenadas para cada punto (intersección o vértice) en el mapa. También puede probar diferentes ponderaciones para la función heurística, es decir,

f(n) = k*h(n) + g(n) 

donde k es una constante mayor que 0.

Probablemente similar a la respuesta en rutas pre calculadas entre ubicaciones principales y mapas en capas, pero tengo entendido que en los juegos, para acelerar A *, tienes un mapa que es muy grueso para la macro navegación, y un mapa de grano fino para navegación hacia el límite de direcciones macro. Entonces tiene 2 pequeños caminos para calcular y, por lo tanto, su espacio de búsqueda es mucho más pequeño que simplemente hacer una ruta única al destino. Y si está en el negocio de hacer esto mucho, tendría una gran cantidad de datos precalculados, por lo que al menos parte de la búsqueda es una búsqueda de datos pre calculados, en lugar de una búsqueda de una ruta.

Tenía más pensamientos sobre esto:

1) Recuerde que los mapas representan una organización física. Almacena la latitud / longitud de cada intersección. No necesita verificar mucho más allá de los puntos que se encuentran en la dirección de su objective. Solo si te encuentras bloqueado necesitas ir más allá de esto. Si almacena una superposición de conexiones superiores, puede limitarla aún más: normalmente, nunca pasará por una de ellas de una manera que se aleje de su destino final.

2) Divida el mundo en un conjunto de zonas definidas por conectividad limitada, defina todos los puntos de conectividad entre las zonas. Encuentra en qué zonas se encuentran tu fuente y tu objective, para la ruta de la zona de inicio y final desde tu ubicación hasta cada punto de conexión, para las zonas entre simplemente el mapa entre los puntos de conexión. (Sospecho que mucho de esto último ya está precalculado).

Tenga en cuenta que las zonas pueden ser más pequeñas que un área metropolitana. Cualquier ciudad con características de terreno que la dividan (por ejemplo, un río) sería de zonas múltiples.

Tenía mucha curiosidad acerca de la heurística utilizada, cuando hace un tiempo atrás recibimos rutas desde el mismo lugar de inicio cerca de Santa Rosa, a dos campamentos diferentes en el Parque Nacional Yosemite. Estos diferentes destinos produjeron rutas bastante diferentes (a través de I-580 o CA-12) a pesar de que ambas rutas convergieron durante las últimas 100 millas (a lo largo de CA-120) antes de desviarse de nuevo unas pocas millas al final. Esto fue bastante repetible. Las dos rutas se encontraban a una distancia de hasta 50 millas por alrededor de 100 millas, pero las distancias / tiempos eran bastante cercanas entre sí como era de esperar.

Por desgracia, no puedo reproducir eso: los algoritmos deben haber cambiado. Pero me tenía curiosidad sobre el algoritmo. Todo lo que puedo especular es que hubo una poda direccional que resultó ser exquisitamente sensible a la pequeña diferencia angular entre los destinos como se ve desde lejos, o hubo diferentes segmentos precalculados seleccionados por la elección del destino final.

Hablando de GraphHopper , un rápido planificador de rutas de código abierto basado en OpenStreetMap, he leído un poco de literatura e implementado algunos métodos. La solución más simple es un Dijkstra y una mejora simple es un Dijkstra bidireccional que explora aproximadamente solo la mitad de los nodos. Con Dijkstra bidirccional una ruta a través de toda Alemania toma ya 1 segundo (para el modo automóvil), en C sería probablemente de solo 0.5s o así;)

He creado un gif animado de una búsqueda de ruta real con Dijkstra bidireccional aquí . También hay algunas ideas más para hacer Dijkstra más rápido como hacer A *, que es un “Dijkstra orientado a objectives”. También he creado una animación gif para ello.

Pero, ¿cómo hacerlo (mucho) más rápido?

El problema es que para una búsqueda de ruta todos los nodos entre las ubicaciones deben ser explorados y esto es realmente costoso, ya que en Alemania hay varios millones de ellos. Pero un punto de dolor adicional de Dijkstra, etc. es que tales búsquedas utilizan mucha RAM.

Hay soluciones heurísticas pero también soluciones exactas que organizan el gráfico (red de carreteras) en capas jerárquicas, ambos tienen ventajas y desventajas y resuelven principalmente el problema de velocidad y RAM. He enumerado algunos de ellos en esta respuesta .

Para GraphHopper, decidí utilizar las jerarquías de contracción porque es relativamente fácil de implementar y no toma años para preparar el gráfico. Todavía resulta en tiempos de respuesta muy rápidos, como puede probar en nuestra instancia en línea GraphHopper Maps . Por ejemplo, desde el sur de África hasta el este de China, lo que da como resultado una distancia de 23000 km y casi 14 días de tiempo de conducción para el automóvil, y solo tomó ~ 0.1 s en el servidor.

Esto es pura especulación de mi parte, pero supongo que pueden usar una estructura de datos de mapa de influencia que se superpone al mapa dirigido para restringir el dominio de búsqueda. Esto permitiría que el algoritmo de búsqueda dirija la ruta a las rutas principales cuando el viaje deseado sea largo.

Dado que esta es una aplicación de Google, también es razonable suponer que gran parte de la magia se realiza a través de un almacenamiento en caché completo. 🙂 No me sorprendería si el almacenamiento en caché del 5% más frecuente de las solicitudes de ruta de Google Map permitiera que una gran parte (20%? 50%?) De las solicitudes se respondiera mediante una simple búsqueda.

He trabajado en enrutamiento durante algunos años, con una actividad reciente impulsada por las necesidades de mis clientes, y he descubierto que A * es lo suficientemente rápido; realmente no hay necesidad de buscar optimizaciones o algoritmos más complejos. Enrutar sobre un gráfico enorme no es un problema.

Pero la velocidad depende de tener toda la red de enrutamiento, me refiero al gráfico dirigido de arcos y nodos que representan los segmentos de ruta y las uniones, respectivamente, en la memoria. La sobrecarga de tiempo principal es el tiempo necesario para crear esta red. Algunas cifras aproximadas basadas en una computadora portátil ordinaria con Windows, y enrutamiento en toda España: tiempo necesario para crear la red: 10-15 segundos; tiempo necesario para calcular una ruta: demasiado corto para medir.

La otra cosa importante es poder reutilizar la red para tantos cálculos de enrutamiento como desee. Si su algoritmo ha marcado los nodos de alguna manera para registrar la mejor ruta (el costo total para el nodo actual y el mejor arco), como debe hacerlo en A *, debe restablecer o borrar esta información anterior. En lugar de atravesar cientos de miles de nodos, es más fácil usar un sistema de número de generación. Marque cada nodo con el número de generación de sus datos; incremente el número de generación cuando calcule una nueva ruta; cualquier nodo con un número de generación anterior está obsoleto y su información puede ignorarse.

Veo qué pasa con los mapas en el PO:

Mire la ruta con el punto intermedio especificado: la ruta va ligeramente hacia atrás debido a que la ruta no es recta.

Si su algoritmo no retrocede, no verá la ruta más corta.

Un algoritmo de ruta más corta para todas las parejas calculará las rutas más cortas entre todos los vértices en un gráfico. Esto permitirá precalcular las rutas en lugar de requerir que se calcule una ruta cada vez que alguien quiera encontrar la ruta más corta entre una fuente y un destino. El algoritmo de Floyd-Warshall es un algoritmo de ruta más corta para todas las parejas.

Los mapas nunca toman en consideración todo el mapa. Supongo que: 1. Según su ubicación, cargan un lugar y los puntos de referencia en ese lugar. 2. Cuando busca el destino, es cuando cargan la otra parte del mapa y hacen un gráfico de dos lugares y luego aplican los algoritmos de ruta más cortos.

Además, hay una técnica importante. La progtwigción dinámica que sospecho se usa en el cálculo de las rutas más cortas. Puedes referirte a eso también.