¿Hay vendedores ambulantes inteligentes?

Bromas aparte, he tenido un problema de enrutamiento que es casi un problema de vendedor ambulante (TSP):

• se define el punto de partida
• 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 pensé que TSP sería una combinación perfecta, así que ejecuté algunos datos de muestra a través de tsp_solveConcorde. Afortunadamente, fue rápidamente obvio que la ruta más corta de TSP no es la ruta más corta real , ya que el problema se hace más fácil al exigir de manera poco realista que los nodos se visiten exactamente una vez . Esta imagen es solo un intento manual de un solo paso para la optimización de la solución calculada y ya ahorra aproximadamente la distancia del borde más largo utilizado.

El problema resurgió, ya que estoy tratando de encontrar rutas óptimas a subconjuntos de sitios de mapeo / monitoreo. La ubicación y los datos de la red vial son bastante precisos y precisos, por lo que un ejercicio como este tiene sentido.

He examinado las generalizaciones del TSP, pero no he encontrado un algoritmo apropiado. Los árboles de expansión mínima no representan el regreso de las ramas (la primera solución aquí cuesta 3 más). Por lo que entiendo, el problema de la ruta más corta eventualmente solo se preocupa por dos nodos y los que quedan fuera de la ruta óptima quedarían fuera. Un caso especial del problema de ruta del vehículo parece encajar mejor, aunque no sé si considera rutas no directas.

Mi pregunta: ¿hay algún nombre establecido, definición para este tipo de problema (familia)? ¿Qué algoritmo y herramienta usarías para resolverlo?

Estoy seguro de que sería computacionalmente pesado, pero estoy interesado en respuestas generales (recursos infinitos) y prácticas.

Esto es TSP . Simplemente no ha definido una métrica de distancia válida porque no satisface la desigualdad del triángulo: si hay una ruta de A a C a B que es más corta que la distancia establecida de A a C, entonces la distancia establecida de A a C es, simplemente, incorrecto. La solución es actualizar la matriz de distancia configurando la longitud de A a C para que sea la longitud más corta de todas las rutas de A a C.