example - Enrutamiento de mapa óptimo con Google Maps

infobox google maps

Question

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

Answer 1

Siempre les da en orden.

Así que creo que tendrías que buscar la distancia (o el tiempo) entre cada par de puntos, uno cada vez, y luego resolver el problema del vendedor ambulante. Sin embargo, tal vez podrías convencer a Google Maps para que agregue esa característica. Supongo que lo que constituye una solución "lo suficientemente buena" depende de lo que esté haciendo y de lo rápido que deba ser.

Answer 2

En un problema típico de TSP, la suposición es que uno puede viajar directamente entre dos puntos cualesquiera. Para las 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 normalmente obtiene una ruta bastante cercana a la óptima.

Para calcular una ruta TSP, primero debería pedirle a Google que calcule la distancia en 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 de TSP en ellas.

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

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

Answer 3

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

Answer 4

Hay una opción en Google Maps API DirectionsRequest llamada optimizeWaypoints, que debe hacer lo que desee. Sin embargo, esto solo puede manejar hasta 8 puntos de referencia.

Alternativamente, existe una biblioteca de código abierto (licencia de MIT) que puede usar con la API de Google Maps para obtener una ruta óptima (hasta 15 ubicaciones) o bastante cerca de la ó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