¿Qué es un algoritmo para una solución aproximada al problema del vendedor ambulante?

Para mantener la discusión más concreta, centrémonos en el TSP Euclidiano clásico, donde el vendedor visita ubicaciones planas, cubriendo distancias entre las ubicaciones. En particular, pasar de A a B y de B a A requiere el mismo tiempo / recursos, y las distancias de A a B a C y de regreso a A satisfacen la desigualdad del triángulo (las versiones más abstractas introducen asimetría, pueden usar etiquetas arbitrarias de “distancia” y puede prohibir viajar entre algunos pares de puntos).

En la práctica, los mejores algoritmos están basados ​​en la heurística de Lin-Kernighan, especialmente la variedad LKH desarrollada por Keld Helsgaun.
No se ha demostrado que siempre produzcan buenas soluciones, pero de alguna manera tienden a estar dentro del 1-2% de lo óptimo. ¿Cómo sabemos cuáles son los valores óptimos? Usando el solucionador Concorde TSP (que es mucho más lento, pero puede manejar casos de problemas sorprendentemente grandes).

Matemáticamente hablando, existe un esquema de aproximación de tiempo polinómico desarrollado por Sanjeev Arora en Princeton. Muestra cómo encontrar soluciones lo más óptimas posible, pero acercarse lleva más tiempo. Un gran resultado teórico, pero parece de poco valor práctico porque la técnica LKH es muy exitosa. Como LKH es un mejorador incremental, puede comenzar con recorridos producidos por el esquema de aproximación y procesarlos posteriormente con LKH. Esto hará que los resultados sean demostrablemente buenos, pero socavará la ventaja de tiempo de ejecución de LKH.

Como era de esperar, el tema es bastante profundo, por lo que este resumen no pretende ser exhaustivo. Para detalles adicionales, vea Problema de vendedor ambulante – Wikipedia.

No sé si es el mejor enfoque, pero lo haría de la siguiente manera:

Primero haga una aproximación comenzando en una ubicación aleatoria, y luego vaya al siguiente destino que tenga la distancia más corta, y así sucesivamente hasta que se visiten todas las ubicaciones.

Esa es tu solución inicial.

Ahora itera en un bucle infinito, con la condición final de que se alcanza un límite de tiempo determinado T, o después de N intentos consecutivos, no se ha realizado ningún progreso, lo que ocurra primero.

Cada iteración guarda la mejor solución actual y realiza M cambios aleatorios (aunque los cambios se rechazan si no conducen a una nueva solución) y calcula la nueva distancia total. Si es mejor, conserva esa solución, de lo contrario volverá a la solución anterior.

Los parámetros que se deben suministrar:

T: límite de tiempo

N: cantidad máxima de intentos consecutivos que no cambia la mejor solución hasta ahora.

M: número de cambios aleatorios para realizar en cada iteración.

Los valores correctos para T, N y M deben determinarse experimentalmente y, por supuesto, dependen del problema en cuestión (el número de nodos a visitar).

Utilice algoritmos de colonias de abejas para resolver problemas imposibles
En este artículo, se utiliza el algoritmo Simulated Bee Colony (SBC) para resolver el problema del vendedor ambulante.

Cualquier aproximación alfa al TSP general es NP-completa. Sabemos esto porque una aproximación alfa al TSP general nos da una solución al problema del Ciclo Hamiltoniano.