Pronto visitaré algunos lugares de Estados Unidos en coche. Me gustaría visitar n lugares. ¿Cómo puedo ver cuál es la ruta de conducción más rápida que pasa por esos n lugares?
Google Maps permite a los usuarios indicar varias paradas, pero sólo da la duración de la ruta para el orden dado de las paradas y no quiero probar todas las permutaciones.
Como se ha señalado en los comentarios, se trata del clásico problema del viajante de comercio.
Es matemáticamente difícil de resolver. Siempre se puede hacer fuerza bruta probando todas las rutas posibles, pero el número de permutaciones aumenta con el factorial del número de ciudades, por lo que se vuelve difícil de manejar muy rápidamente.
Dicho esto, para 5-20 ciudades, incluso algo tan simple como Microsoft Excel puede resolver esto bastante bien. He aquí un ejemplo: https://www.youtube.com/watch?v=-E3rSoClgMI sobre cómo hacerlo.
La entrada del algoritmo es la matriz de distancia. Puede utilizar la distancia o el tiempo, cualquiera de los dos funcionaría. Es necesario obtenerlas manualmente de Google Maps o utilizar una de las APIs existentes. Para 10 ciudades, son 45 números que necesitas sacar de Google Maps. Supongo que depende de ti decidir si vale la pena el esfuerzo o no.
Hice una simulación de 13 ciudades y me llevó menos de un minuto en mi portátil. (fuente https://developers.google.com/optimization/routing/tsp ).
Para algo más grande probablemente necesites un algoritmo más avanzado y un lenguaje de programación decente (como Python o Matlab/Octave). Véase, por ejemplo: https://www.youtube.com/watch?v=c5395m-nVz4
Aquí están los resultados: Puedes cubrir 13 ciudades principales de los EE.UU. en 7386 millas.
Gracias por las ideas y el código. Esperaba que algún sitio web de mapas tuviera esta función. Concorde TSP se puede utilizar si uno construye su propia solución y necesita un solucionador TSP más rápido.
Todo depende de lo elegante que quieras ser. Tengo una versión que utiliza una base de datos pública de ciudades de EE.UU. para obtener la latitud y la longitud y que crea automáticamente la matriz de distancias basándose en una lista de ciudades. Esto supone que la distancia en coordenadas es proporcional a la distancia o al tiempo de viaje, lo que puede ser o no lo suficientemente bueno. En mi zona, el tiempo de viaje al aeropuerto varía entre 30 minutos y 2 horas, según la hora del día (es decir, el tráfico).
Gracias, efectivamente tener en cuenta la duración real del viaje sería más útil. Además, en algunos casos mis n ubicaciones están dentro de la misma área metropolitana.
La aplicación Android Wanderlog tiene una función de pago para ver la ruta de conducción más rápida es que pasa por todos estos n lugares:
Usuario de Reddit quatrotires me señaló a ella.
Roadtrippers también tiene esta característica. En https://support.roadtrippers.com/hc/en-us/articles/201310953-Quickly-Customize-a-Trip-s-Route :
Nuestro planificador de viajes busca por defecto la ruta más eficiente entre los waypoints. Si quieres tomar una ruta diferente, en nuestro sitio de escritorio puedes personalizar fácilmente la ruta haciendo clic y arrastrando en el mapa.
Usuario de SE Moo me lo indicó.
La API de Google Directions también tiene esta función:
En caso de que te sientas inclinado a hacer algo de codificación, Google tiene soporte para eso en su Direcciones API . Consulte los documentos de la
optimize:trueparámetro. Sin embargo, el servicio no es gratuito, pero Google concede algunos créditos gratuitos cada mes aproximadamente. sourcream Hace 4 horas
ViajeroSabio es una comunidad de viajeros en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros viajeros, hacer tus propias preguntas o resolver las de los demás.
9 votos
es.wikipedia.org/wiki/Problema del vendedor ambulante ¿cómo de grande es n?
0 votos
@jcaron gracias, sí que es un TSP, n está entre 5 y 20 dependiendo del temario.
0 votos
Estaría encantado de recibir alguna opinión de los que votan a la baja.
3 votos
En caso de que te sientas inclinado a hacer algo de codificación, Google tiene soporte para eso en su Direcciones API . Consulte los documentos de la
optimize:trueparámetro. Sin embargo, el servicio no es gratuito, pero Google concede algunos créditos gratuitos cada mes aproximadamente.0 votos
¡@sourcream gracias, gran hallazgo!
5 votos
Veo que hay 3 votaciones ajustadas con el motivo " ... la construcción de itinerarios de viajes y excursiones (incluyendo la programación y el presupuesto) están fuera de lugar ". Como sólo falta un voto para que se cierre, quería señalar que el autor de la pregunta no está pidiendo un itinerario, sino una herramienta que pueda crear un itinerario para ellos dadas algunas restricciones. Creo que pedir herramientas en lugar de resultados es encomiable y no entra dentro del motivo de cierre de la votación.
0 votos
@SaaruLindestøkke estuvo de acuerdo travel.meta.stackexchange.com/a/8199/1810 Por ejemplo, el mismo problema con 4 votantes cercanos que no entienden WANTA en travel.stackexchange.com/q/174315/1810