Mapa de enrutamiento, al estilo Google Maps?

votos
19

Siempre me ha intrigado Map Routing, pero nunca encontré ningún buen tutorial introductorio (¡o incluso avanzado!) Sobre él. ¿Alguien tiene punteros, consejos, etc.?

Actualización: principalmente busco indicadores sobre cómo se implementa un sistema de mapas (estructuras de datos, algoritmos, etc.).

Publicado el 05/08/2008 a las 21:24
fuente por usuario
En otros idiomas...                            


9 respuestas

votos
14

Eche un vistazo al proyecto de mapa de calles abiertas para ver cómo se aborda este tipo de cosas en un proyecto de software verdaderamente gratuito que utiliza solo datos proporcionados por el usuario y con licencia, y tiene un wiki que contiene elementos que puede resultarle interesantes .

Hace unos años, los chicos involucrados fueron bastante fáciles y respondieron muchas preguntas que tenía, así que no veo ninguna razón por la que todavía no sean un buen grupo.

Respondida el 05/08/2008 a las 21:27
fuente por usuario

votos
4

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.

Respondida el 25/09/2008 a las 00:19
fuente por usuario

votos
4

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 podría ser de su interés:

El camino hacia una mejor búsqueda de ruta 11/06/2007 03:47:00 PM

Respondida el 17/09/2008 a las 09:44
fuente por usuario

votos
4

¿Por el enrutamiento de mapas, te refieres a encontrar el camino más corto a lo largo de una red de calles?

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

Hay un applet 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 casi cualquier idioma.

Cualquier implementación real para generar rutas de manejo incluirá bastantes datos en la red de calles que describan los costos asociados con los enlaces y nodos que atraviesan: jerarquía de red vial, velocidad promedio, prioridad de intersección, enlace de señales de tráfico, giros prohibidos, etc.

Respondida el 15/08/2008 a las 05:31
fuente por usuario

votos
2

Desde un punto de vista conceptual, imagine tirar 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 debería buscar una proporción de n ^ 2 caminos a medida que aumenta la distancia n. Usted tomaría la posición inicial y verificaría todos los caminos disponibles desde ese punto. Luego, recursivamente, pida los puntos al final de esos caminos, etc.

Puede aumentar el rendimiento, al no hacer doble respaldo en una ruta, al no volver a verificar las rutas en un punto si ya se ha cubierto y al renunciar a las rutas que llevan demasiado tiempo.

Una forma alternativa es utilizar el enfoque de feromonas de hormigas, donde las hormigas se arrastran aleatoriamente desde un punto de inicio y dejan un rastro de olor, que acumula más hormigas que cruzan una ruta determinada. Si envía (suficientes) hormigas desde el punto de inicio y el punto final, finalmente la ruta con el aroma más fuerte será la más corta. Esto se debe a que el camino más corto se habrá visitado más veces en un período de tiempo determinado, dado que las hormigas caminan a un ritmo uniforme.

EDITAR @ Spikie

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

Tendrá que guardar el mapa como una red. Esto es simplemente un conjunto de nodesy edgesentre ellos. Un conjunto de nodesconstituir a route. Un borde une dos nodos (posiblemente el mismo nodo), y tiene un asociado costcomo distanceo timepara atravesar el borde. Un borde puede ser bidireccional o unidireccional. Probablemente lo más simple es tener unidireccionales y duplicar para un viaje de dos vías entre nodos (es decir, un borde de A a B y uno diferente para B y A).

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

Nodos de etiquetas que comienzan desde abajo a la izquierda, yendo de izquierda a derecha y arriba, como A, B, C, D, E, F (F en la parte superior).

Supongamos que los bordes se pueden atravesar en cualquier dirección. Cada borde tiene un costo de 1 km.

Ok, entonces deseamos pasar de la parte inferior izquierda A a la estación superior F. Hay muchas rutas posibles, incluidas las que se duplican, p. Ej., ABCEBDEF.

Tenemos una opinión de rutina NextNode, que acepta a nodey a costy se llama a cada nodo al que puede viajar.

Claramente, si permitimos que se ejecute esta rutina, eventualmente descubrirá todas las rutas, incluidas las que tienen una longitud potencialmente infinita (por ejemplo, ABABABAB, etc.). Detenimos que esto suceda al verificar en contra de cost. Cada vez que visitamos un nodo que no ha sido visitado anteriormente, colocamos tanto el costo como el nodo del que venimos contra ese nodo. Si se ha visitado un nodo antes de verificar el costo existente y si somos más baratos, actualizamos el nodo y continuamos (recursión). Si somos más caros, salteamos el nodo. Si se omiten todos los nodos, salimos de la rutina.

Si golpeamos nuestro nodo objetivo, también salimos de la rutina.

De esta forma se verifican todas las rutas viables, pero crucialmente solo aquellas con el menor costo. 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. Como almacenamos el nodo del que venimos junto con el costo, simplemente saltamos hacia atrás para construir la ruta. Para nuestro ejemplo, terminaríamos con algo como:

Nodo A - (Total) Costo 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 hay un costo igual)
Nodo F - Costo 2 - Desde el Nodo D

Entonces, la ruta más corta es ADF.

Respondida el 26/09/2008 a las 15:05
fuente por usuario

votos
2

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

Hay aplicaciones de enrutamiento GPL que usan datos de OpenStreetMap, por ejemplo, Gosmore que funciona en Windows (+ móvil) y Linux. Hay una serie de aplicaciones interesantes que usan los mismos datos, pero gosmore tiene algunos usos interesantes, por ejemplo, la interfaz con sitios web .

El mayor problema con el enrutamiento es la mala información, y nunca se obtienen datos suficientemente buenos. Entonces, si quiere probarlo, mantenga su prueba muy local para que pueda controlar mejor los datos.

Respondida el 17/09/2008 a las 09:34
fuente por usuario

votos
2

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

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

Sugeriría que vaya a la URL y aprenda una API general. Hay una buena cantidad de How-Tos también.

Respondida el 06/08/2008 a las 14:35
fuente por usuario

votos
1

Desde mi experiencia de trabajo en este campo, A * hace el trabajo muy bien. Es (como se mencionó anteriormente) más rápido que el algoritmo de Dijkstra, pero es lo suficientemente simple para un programador normalmente competentes para aplicar y comprender.

La construcción de la red de rutas es la parte más difícil, pero que puede ser dividido en una serie de pasos simples: obtener todos los caminos; ordenar los puntos en orden; hacer grupos de puntos idénticos en diferentes carreteras en las intersecciones (nodos); añadir arcos en ambas direcciones donde los nodos se conectan (o en un solo sentido para una carretera de un solo sentido).

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

Personalización del algoritmo de ruta sobre diferentes partes de la red (por ejemplo, peatón, coche, transporte público, etc.) de la velocidad favor, distancia u otro criterio es bastante fácil. Usted hace que al escribir filtros para controlar qué segmentos de ruta están disponibles, cuando la construcción de la red, y que el peso se asigna a cada uno.

Respondida el 15/07/2012 a las 22:13
fuente por usuario

votos
1

Otro pensamiento me ocurre en relación con el costo de cada recorrido, pero aumentaría el tiempo y la potencia de procesamiento necesaria para calcular.

Ejemplo: Existen 3 maneras que puedo tomar (donde vivo) para ir desde el punto A a B, de acuerdo con la GoogleMaps. Unidades de Garmin ofrecen cada una de estas 3 rutas en el Quickestcálculo de la ruta. Después de recorrer cada una de estas rutas muchas veces y promediando (obviamente no habrá errores en función de la hora del día, la cantidad de cafeína, etc.), siento los algoritmos podrían tener en cuenta el número de curvas en la carretera de alto nivel de precisión , por ejemplo, camino recto de 1 milla será más rápida que un camino de 1 milla con fuertes curvas en ella . No es una sugerencia práctica, pero sin duda que yo uso para mejorar el conjunto de resultados de mi viaje diario.

Respondida el 18/09/2011 a las 22:34
fuente por usuario

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more