Bromas aparte, he tenido un problema de enrutamiento que es casi un problema del viajante (TSP):
- el punto de partida se define
- el punto final coincide con el punto de partida
- cada nodo tiene que ser visitado
- el costo total debe ser minimizado
Hace dos años yo pensaba CUCHARADITA sería un partido perfecto, así que me fui corriendo algunos datos de la muestra a través de la tsp_solve y Concordia. Por suerte, fue rápidamente evidente que el TSP camino más corto es el camino más corto, ya que el problema se hace más fácil por poco realista, que requieren los nodos ser visitado exactamente una vez. Esta imagen es sólo un paso manual intento de la optimización de la calculada de la solución y ya se guarda sobre la distancia de los más utilizados borde.
El problema resurgió, como estoy tratando de encontrar rutas óptimas a los subconjuntos de asignación/sitios de monitoreo. La ubicación y la red de carreteras data es bastante exacta y precisa, por lo que un ejercicio como este, hace sentido.
He mirado en las generalizaciones de la TSP, pero no encontró un algoritmo apropiado. Árboles de expansión mínimos no cuenta para la devolución de las ramas (la 1ª solución aquí cuesta 3 más). Por lo que entiendo, el problema de la ruta más corta , que finalmente sólo se preocupa por dos nodos y los que están fuera de la ruta más óptima sería la izquierda. Un caso especial de los problemas de enrutamiento de vehículos parece encajar mejor, aunque no sé si se considera no-rutas directas.
Mi pregunta: ¿hay alguna asentado el nombre, la definición de este tipo de problema (de la familia)? Qué algoritmo de la herramienta y la usaría para resolverlo?
Estoy seguro de que sería computacionalmente pesado, pero estoy interesado en general (recursos infinitos) y respuestas concretas.
