¿Hay alguna manera 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 los puntos en el orden especificado?Enrutamiento de mapa óptimo con Google Maps
Siempre los pone en orden.
Así que creo que tendrías que encontrar 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.
su respuesta no se corrige ahora. Google ahora es compatible con el problema TSP. La versión gratuita de google map incluye inicio, final y 8 puntos medios. (Totalmente 10 puntos) Espero que vuelva a editar para una referencia de usuario posterior :) – hqt
En un problema típico de TSP, se supone que se 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 tendría que 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 quiera. 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á 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.
¿Cómo recupera la "ruta bastante cercana a la óptima" de la API? Solo puedo obtener puntos en el orden en que los ingreso. – Soldarnal
Google no pedirá los puntos. La ruta óptima que Google calcula es la distancia entre los dos puntos. ¿Cuántas formas hay para ir de Nueva York a California? Cerca de infinito. Google encontrará una buena ruta, que probablemente sea casi óptima, pero puede haber una ruta más corta. – brianegge
Acaba de encontrar http://gebweb.net/optimap/ Parece agradable y fácil. Versión en línea usando google maps.
Wow sitio increíble y me alegro de que ha estado en línea tanto tiempo, ¡esto será de gran utilidad para un amigo mío! – DPSSpatial
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.
Como alternativa, 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 cerca de la óptima (hasta 100 ubicaciones).
Ver http://code.google.com/p/google-maps-tsp-solver/
Se puede ver la biblioteca en acción en www.optimap.net
Hay toda una discusión sobre esta idea en Slashdot: http://ask.slashdot.org/article.pl?sid=08/ 01/09/2311215 – brianegge