Software para planificar la ruta más corta a muchas direcciones [cerrado]

8

Tengo alrededor de 300 direcciones en una ciudad y estoy tratando de encontrar un software que pueda resolver el problema del vendedor ambulante. He probado OptiMap, una solución basada en navegador que utiliza la API de Google, pero tiene un límite de 100 destinos (incluso cuando cambias los límites codificados) y los navegadores que intento finalmente se quedan sin memoria. Sé que el problema es NP difícil pero este no es un problema nuevo, seguramente alguien ya ha escrito software. Las únicas soluciones comerciales que he visto se basan solo en los EE. UU. (Es una ciudad australiana) o tienen límites bajos.

¿Existe software gratuito o comercial para realizar esta tarea y su tamaño?

software-rec calculator usuario348998
fuente
2
Quizás pueda resolver el problema en trozos de 100. ¿Puede dividir las ubicaciones en grupos y alimentarlos a OptiMap en trozos? Entonces manejar las transiciones manualmente?
uSlackr
Siempre he visto el problema del vendedor ambulante utilizado como ejemplo, algo así como una cosa del mundo hola foobarbaz. Es divertido ver que tiene un potencial tan práctico. Por cierto, NP duro o no, los algoritmos genéticos darán una solución excelente (no perfecta) en minutos o menos. Además, 300 direcciones? Parece el tipo de situación de WTF que los desarrolladores de OptiMap no tenían en cuenta. ¿Presentar un error?
Camilo Martin
Busque con estas palabras clave: optimización de la entrega de software logístico. Hay muchos programas dedicados para este tipo de problemas. duckduckgo.com/…
climenole

Respuestas:

1

No es exactamente "gratuito", pero quizás implemente el algoritmo de aproximación para TSP descrito en este libro de texto .

IIRC, proporciona una solución TSP para gráficos planos con un factor de 2 dentro de la solución óptima.

conjunto vacio
fuente
1
Jaja, +1 para la respuesta "escribe este algoritmo"
Fopedush
Creo que es divertido cuando las personas piensan que van a encontrar un sitio web con un software escrito personalizado para resolver su escenario específico.
emptyset