Hola msacchi, bienvenido al foro. Me anima cuando un ingeniero reconoce un problema aplicado tan bonito y busca asesoría. Tu problema está en el contexto de teoría de grafos, optimización o investigación de operaciones. Hace unos años me tocó resolver un problema de programación lineal para una empresa eléctrica, fue una experiencia muy buena para ambas partes. En ese momento usamos el software GAMS, ya que era el que tenían en esa empresa, pero no sé si es una buena opción para tu problema. Quizás googleando puedas decidir que sirve, y si es así, creo que puedes descargarlo y probarlo. La versión de prueba tiene una limitación en número de variables, pero no creo que tu problema requiera tantas. Pero insisto, no estoy seguro si sirve para tu problema.
Me parece que problema no sería del
camino más corto o
vendedor viajero porque en esos problemas no podrías pasar dos veces por una misma arista sin que se sume el costo más de una vez.
Me parece que lo que buscas es un
Árbol recubridor mínimo. En particular, el
Método de Kruskal. Seguramente está implementado en algún software, pero lo desconozco. De todas formas, el algoritmo no parece difícil de programar.
Y si puedo sumarle complejidad a mi consulta, también les consulto para el caso de que hayan condiciones de borde. Por ejemplo: Caminos existentes que quiera aprovechar. Caminos existentes entre coordenadas (x1,y1;x2,y2) no necesariamente coordenadas iguales a alguno de los puntos que quiero conectar.
En el problema, el "peso" que conecta dos "vértices" (ciudades) es el coste de construir la "arista" (camino) entre ellos. Entonces, si existe un camino construido previamente que conecta dos ciudades, entonces el peso de la arista es es cero.
Por último, debes indicar todos los vértices (ciudades) del grafo y los pesos de las aristas (costos de cada camino). Si quieres puedes crear algunas ciudades artificiales, si tu intuición dice que en tal lugar podría pasar un camino aunque no haya una ciudad.
Cuéntanos cuando termines tu proyecto.