Pregunta ¿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 X-Z lleva más tiempo y está más lejos que usar un punto intermedio como en X-Y-Z. Pero tal vez sus indicaciones para caminar optimizan para otro parámetro, también?

PPS. Aquí hay otra violación de la desigualdad del triángulo que sugiere (para mí) que usan algún tipo de enfoque escalonado: X-Z versus X-Y-Z. 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.


509
2018-01-09 23:35


origen


Respuestas:


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

  • En lugar de hacer Dijkstra's una vez desde el origen 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.


476
2018-01-11 12:41



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, a acelerar todas siguientes consultas. Con esta información adicional, los itinerarios se pueden calcular muy rápido. Todavía, Algoritmo de Dijkstra es la base de todas las optimizaciones.

Arácnido 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 de carreteras continentales. Una implementación rápida del algoritmo no modificado de Dijkstra necesita aproximadamente 10 segundos.

El artículo Ingeniería de algoritmos de planificación de rutas rápidas 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 usan información sobre el estado jerárquico de la carretera en los datos, es decir, si es 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 buenos actuación y un exactitud garantía 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 contienen todas las distancias entre sus fuentes y destinos. Para esto, podrías considerar Cálculo de trayectos cortos de muchos a muchos utilizando jerarquías de autopistas. Tenga en cuenta que esto se ha mejorado con enfoques más nuevos en los últimos 2 años.


102
2018-02-21 22:12



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 conducir a 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 explícitamente X-Y-Z. Si solicitan X-Z, 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.


16
2018-02-24 23:52



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/


14
2017-10-26 17:37



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.


8
2018-01-10 00:47



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 programació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 hormigas) para programar 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).


8
2018-02-25 14:50



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 . A través de una encuesta excelente y escrita del campo fue publicada recientemente 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/


7
2017-08-25 18:55



Estoy un poco sorprendido de no ver 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.


7
2017-12-09 00:04



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.


6
2017-11-02 17:29



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.


4
2018-02-26 01:21