Enrutamiento óptimo de mapas con Google Maps

Question

¿Hay alguna manera de utilizar la API de Google Maps para recuperar un " optimizado " ruta dada un conjunto de puntos de referencia (en otras palabras, una solución "suficientemente buena" para el problema del vendedor ambulante), o siempre devuelve la ruta con los puntos en el orden especificado?

Answer 1

Siempre los da en orden.

Así que creo que tendrías que encontrar la distancia (o el tiempo) entre cada par de puntos, uno a la vez, y luego resolver el problema del vendedor viajero tú mismo. Sin embargo, quizás puedas convencer a Google Maps de que agregue esa función. Supongo que lo que constituye un "suficientemente bueno" la solución depende de lo que esté haciendo y de lo rápido que deba ser.

Answer 2

Existe una opción en la solicitud de direcciones de la API de Google Maps llamada OptimizeWaypoints, que debe hacer lo que desee. Sin embargo, esto solo puede manejar hasta 8 puntos de referencia.

Alternativamente, hay una biblioteca de código abierto (licencia MIT) que puede usar con la API de Google Maps para obtener una ruta óptima (hasta 15 ubicaciones) o bastante cercana a la ruta óptima (hasta 100 ubicaciones).

Ver http://code.google.com/p/google- maps-tsp-solver /

Puede ver la biblioteca en acción en www.optimap.net

Answer 3

En un problema típico de TSP, se supone que uno puede viajar directamente entre dos puntos. Para carreteras de superficie, este nunca es el caso. Cuando Google calcula una ruta entre dos puntos, realiza una optimización heurística del árbol de expansión, y generalmente encuentra una ruta bastante cercana a la óptima.

Para calcular una ruta TSP, primero tendría que pedirle a Google que calcule la distancia por pares entre cada nodo en el gráfico. Creo que esto requiere n * (n-1) / 2 calcs. Uno podría tomar esas distancias y realizar una optimización TSP en ellas.

OpenStreetMaps.org tiene una aplicación Java WebStart que puede hacer lo que desee. Por supuesto, los cálculos se ejecutan del lado del cliente. El proyecto es de código abierto y puede valer la pena echarle un vistazo.

¿Está tratando de encontrar una ruta recta óptima entre ubicaciones o la ruta de conducción óptima? Si solo desea ordenar los puntos, si puede obtener las coordenadas GPS, se convierte en un problema muy fácil.

Answer 4

Acabo de encontrar http://gebweb.net/optimap/ Parece agradable y fácil. Versión en línea usando google maps.

Answer 5

Google tiene una solución lista para el problema del vendedor de viajes. Es OR-Tools (herramientas de investigación de operaciones de Google) que puede encontrar aquí: https: // desarrolladores .google.com / optimization / routing / tsp

Lo que debes hacer básicamente es 2 cosas:

• Obtenga las distancias entre cada dos puntos utilizando la API de Google Maps: https://developers.google.com/maps/documentation/distance-matrix/start

• Luego alimentarás las distancias en una matriz a OR-Tools y encontrará una solución muy buena para usted (para ciertos casos con millones de nodos, se ha encontrado que las soluciones están dentro del 1% de un recorrido óptimo).

También puede observar que:

  

Además de encontrar soluciones para el vendedor ambulante clásico   Problema, OR-Tools también proporciona métodos para tipos más generales de   TSP, incluidos los siguientes:

•   

  Problemas de costos asimétricos & # 8212; El TSP tradicional es simétrico: la distancia desde el punto A al punto B es igual a la distancia desde el punto B a   punto A. Sin embargo, el costo de envío de artículos desde el punto A al punto B   podría no ser igual al costo de enviarlos del punto B al punto A.   OR-Tools también puede manejar problemas que tienen costos asimétricos.

•   

  TSP de recolección de premios, donde los beneficios se obtienen de los nodos visitantes

•   

  TSP con ventanas de tiempo

Enlaces adicionales:

• Herramientas OR en Github: https://github.com/google/or-tools
• Comience: https://developers.google.com/optimization/introduction/get_started