Rutas por mapas, ¿al estilo Google Maps?

Question

Siempre me ha intrigado Map Routing, pero nunca encontré buenos tutoriales de nivel introductorio (¡o incluso avanzado!) al respecto.¿Alguien tiene algún consejo, sugerencia, etc.?

Actualizar: Principalmente busco sugerencias sobre cómo se implementa un sistema de mapas (estructuras de datos, algoritmos, etc.).

Answer 1

Échale un vistazo al proyecto de mapa de calles abierto para ver cómo se aborda este tipo de cosas en un proyecto de software verdaderamente libre utilizando únicamente datos proporcionados y con licencia por el usuario y tener una wiki que contiene cosas que te pueden resultar interesantes.

Hace unos años, los muchachos involucrados eran bastante tranquilos y respondieron muchas preguntas que tenía, así que no veo ninguna razón por la que todavía no sean un buen grupo.

Answer 2

Barry Brumitt, uno de los ingenieros de la función de búsqueda de rutas de Google Maps, escribió una publicación sobre el tema que puede ser de su interés:

El camino hacia una mejor búsqueda de caminos06/11/2007 15:47:00

Answer 3

En realidad, A* está mucho más cerca de los algoritmos de mapeo de producción.Requiere bastante menos exploración en comparación con el algoritmo original de Dijikstra.

Answer 4

¿Por enrutamiento por mapa se refiere a encontrar el camino más corto a lo largo de una red de calles?

El algoritmo de camino más corto de Dijkstra es el más conocido.Wikipedia no tiene una mala introducción: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Hay un subprograma de Java aquí donde puedes verlo en acción: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html y Google te lleva al código fuente en prácticamente cualquier idioma.

Cualquier implementación real para generar rutas de conducción incluirá una gran cantidad de datos sobre la red de calles que describen los costos asociados con atravesar enlaces y nodos: jerarquía de la red de carreteras, velocidad promedio, prioridad de intersección, vinculación de semáforos, giros prohibidos, etc.

Answer 5

En lugar de aprender API para cada proveedor de servicios de mapas (como Gmaps, Ymaps api), es bueno aprender Tracción de mapas

"Mapstraction es una biblioteca que proporciona una API común para varias API de mapeo de JavaScript"

Te sugiero que vayas a la URL y aprendas una API general.También hay una buena cantidad de procedimientos.

Answer 6

Todavía tengo que encontrar un buen tutorial sobre enrutamiento, pero hay mucho código para leer:

Existen aplicaciones de enrutamiento GPL que utilizan datos de Openstreetmap, p. Gosmore que funciona en Windows (+ móvil) y Linux.Hay varias [aplicaciones interesantes que utilizan los mismos datos, pero gosmore tiene algunos usos interesantes p.ej.interfaz con sitios web.

El mayor problema con el enrutamiento son los datos incorrectos y nunca se obtienen datos suficientemente buenos.Entonces, si desea probarlo, mantenga su prueba muy local para poder controlar mejor los datos.

Answer 7

Desde un punto de vista conceptual, imaginemos dejar caer una piedra en un estanque y observar las ondas.Las rutas representarían el estanque y la piedra su posición inicial.

Por supuesto, el algoritmo tendría que buscar alguna proporción de n^2 caminos a medida que aumenta la distancia n.Tomaría su posición inicial y verificaría todos los caminos disponibles desde ese punto.Luego llame de forma recursiva a los puntos al final de esos caminos y así sucesivamente.

Puedes aumentar el rendimiento si no retrocedes dos veces en un camino, si no vuelves a comprobar las rutas en un punto si ya ha sido recorrido y si renuncias a los caminos que están tardando demasiado.

Una forma alternativa es utilizar el enfoque de feromonas de hormigas, donde las hormigas se arrastran aleatoriamente desde un punto de partida y dejan un rastro de olor, que se acumula a medida que más hormigas cruzan un camino determinado.Si envías (suficientes) hormigas tanto desde el punto inicial como desde el punto final, eventualmente el camino con el olor más fuerte será el más corto.Esto se debe a que el camino más corto habrá sido recorrido más veces en un periodo de tiempo determinado, dado que las hormigas caminan a un ritmo uniforme.

EDITAR @ Spikie

Como explicación adicional de cómo implementar el algoritmo del estanque, se destacan las posibles estructuras de datos necesarias:

Deberá almacenar el mapa como una red.Este es simplemente un conjunto de nodes y edges entre ellos.Un conjunto de nodes constituir un route.Un borde une dos nodos (posiblemente ambos el mismo nodo) y tiene un borde asociado. cost como distance o time para atravesar el borde.Un borde puede ser bidireccional o unidireccional.Probablemente lo más sencillo sea tener unos unidireccionales y duplicarlos para viajes bidireccionales entre nodos (es decir,una arista de A a B y otra diferente de B a A).

Imaginemos, por ejemplo, tres estaciones de ferrocarril dispuestas en un triángulo equilátero apuntando hacia arriba.También hay otras tres estaciones cada una a medio camino entre ellas.Los bordes unen todas las estaciones adyacentes, el diagrama final tendrá un triángulo invertido dentro del triángulo más grande.

Etiquete los nodos comenzando desde abajo a la izquierda, de izquierda a derecha y hacia arriba, como A,B,C,D,E,F (F en la parte superior).

Suponga que los bordes se pueden atravesar en cualquier dirección.Cada arista tiene un coste de 1 km.

Bien, entonces deseamos encaminarnos desde la parte inferior izquierda A hasta la estación superior F.Hay muchas rutas posibles, incluidas aquellas que retroceden sobre sí mismas, p.ABCEBDEF.

Tenemos una rutina que dice: NextNode, que acepta un node y un cost y se llama a sí mismo para cada nodo al que puede viajar.

Claramente, si dejamos que esta rutina se ejecute, eventualmente descubrirá todas las rutas, incluidas aquellas que tienen una longitud potencialmente infinita (por ejemplo, ABABABAB, etc.).Evitamos que esto suceda comprobando con el cost.Cada vez que visitamos un nodo que no ha sido visitado antes, comparamos tanto el costo como el nodo del que venimos con ese nodo.Si se ha visitado un nodo antes, verificamos el costo existente y si somos más baratos, actualizamos el nodo y continuamos (recurriendo).Si somos más caros, nos saltamos el nodo.Si se omiten todos los nodos, salimos de la rutina.

Si alcanzamos nuestro nodo objetivo, también saldremos de la rutina.

De esta manera se comprueban todas las rutas viables, pero sobre todo sólo aquellas con el coste más bajo.Al final del proceso, cada nodo tendrá el costo más bajo para llegar a ese nodo, incluido nuestro nodo objetivo.

Para obtener la ruta trabajamos hacia atrás desde nuestro nodo objetivo.Dado que almacenamos el nodo del que venimos junto con el costo, simplemente retrocedemos construyendo la ruta.Para nuestro ejemplo terminaríamos con algo como:

Nodo A - Costo (total) 0 - Desde el nodo Ninguno
Nodo B - Costo 1 - Desde el nodo A
Nodo C - Costo 2 - Desde el nodo B
Nodo D - Costo 1 - Desde el nodo A
Nodo E - Costo 2 - Desde el Nodo D / Costo 2 - Desde el Nodo B (esta es una excepción ya que el costo es igual)
Nodo F - Costo 2 - Desde el nodo D

Entonces la ruta más corta es ADF.

Answer 8

Según mi experiencia trabajando en este campo, A* hace el trabajo muy bien.Es (como se mencionó anteriormente) más rápido que el algoritmo de Dijkstra, pero aún así es lo suficientemente simple como para que un programador normalmente competente lo implemente y comprenda.

Construir la red de rutas es la parte más difícil, pero se puede dividir en una serie de pasos simples:conseguir todos los caminos;ordenar los puntos;formar grupos de puntos idénticos en diferentes caminos en intersecciones (nodos);agregue arcos en ambas direcciones donde se conectan los nodos (o en una dirección solo para una carretera de un solo sentido).

El algoritmo A* en sí es bien documentado en Wikipedia.El lugar clave para optimizar es la selección del mejor nodo de la lista abierta, para lo cual necesita una cola de prioridad de alto rendimiento.Si está utilizando C++, puede utilizar el adaptador STL Priority_queue.

Personalizar el algoritmo para enrutar a través de diferentes partes de la red (por ejemplo, peatones, automóviles, transporte público, etc.) en función de la velocidad, la distancia u otros criterios es bastante fácil.Para ello, escriba filtros para controlar qué segmentos de ruta están disponibles, al construir la red, y qué peso se asigna a cada uno.

Answer 9

Se me ocurre otra idea con respecto al costo de cada recorrido, pero aumentaría el tiempo y la potencia de procesamiento necesarios para calcular.

Ejemplo: Hay 3 formas que puedo tomar (donde vivo) para ir del punto A al B, según GoogleMaps.Las unidades Garmin ofrecen cada uno de estos 3 caminos en el Quickest cálculo de ruta.Después de recorrer cada una de estas rutas muchas veces y promediar (obviamente habrá errores dependiendo de la hora del día, la cantidad de cafeína, etc.), creo que los algoritmos podrían tener en cuenta la cantidad de curvas en la carretera para lograr un alto nivel de precisión. , p.ej. Una carretera recta de 1 milla será más rápida que una carretera de 1 milla con curvas cerradas..No es una sugerencia práctica, pero ciertamente la uso para mejorar el conjunto de resultados de mi viaje diario.