💻 ciencias de la computación

A Statistically Rigorous, Held–Karp- and LKH-Validated Empirical Evaluation of a Classical 2-opt + Or-opt Local Search Pipeline for the Euclidean Traveling Salesman Problem

Este artículo proporciona una evaluación empírica estadísticamente rigurosa, validada mediante Held–Karp y LKH, de un flujo de trabajo de vecino más cercano, 2-opt y Or-opt para el problema del viajante euclidiano (TSP), demostrando su mejora significativa sobre el uso de solo 2-opt y su proximidad constante a los límites de optimalidad certificados en instancias sintéticas y del mundo real.

Autores originales: Mohamad Fatahi, Hamzeh Barati²

Publicado 2026-10-27

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Mohamad Fatahi, Hamzeh Barati²

Artículo original bajo licencia CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Encontrar la ruta más corta posible que visite un conjunto de ubicaciones exactamente una vez y regrese al punto de partida es un problema que ha desconcertado a matemáticos y logisticos durante décadas. Conocido como el Problema del Viajante, no es meramente un rompecabezas abstracto; sustenta desafíos del mundo real como la entrega de paquetes, la perforación de agujeros en placas de circuitos y la secuenciación del ADN. Debido a que el número de rutas posibles crece explosivamente a medida que se añaden más ciudades, encontrar la única ruta perfecta suele ser imposible de calcular en un tiempo razonable. En su lugar, los expertos confían en métodos de "búsqueda local". Estas son estrategias prácticas que parten de una ruta aproximada y realizan mejoras pequeñas e incrementales, intercambiando conexiones o moviendo segmentos de la trayectoria para ver si la distancia total disminuye. Si bien estos métodos son herramientas estándar, a menudo se tratan como cajas negras: sabemos que funcionan, pero rara vez medimos exactamente qué tan cerca llegan del límite teórico, o cuánto mejor es un método que otro, con una prueba estadística estricta.

Un estudio reciente de Mohamad Fatahi y Hamzeh Barati aporta este nivel de precisión a una combinación clásica de estas técnicas de búsqueda local. Los investigadores no inventaron una nueva forma de resolver el problema. En su lugar, tomaron un flujo de trabajo bien conocido —comenzando con un enfoque sencillo de "vecino más cercano" para construir un primer borrador, para luego refinarlo con dos pasos de mejora específicos llamados "2-opt" y "Or-opt"— y lo sometieron a una auditoría estadística rigurosa. Su objetivo era medir exactamente cuánto mejor se desempeñaba el método combinado en comparación con el uso de solo el primer paso de mejora, y determinar qué tan cerca estaban las rutas finales del límite matemático absoluto de perfección. Para hacer esto, generaron miles de mapas de ciudades aleatorias y también probaron el método en cuatro famosos mapas de ciudades del mundo real donde la respuesta perfecta ya es conocida.

Los investigadores ejecutaron sus experimentos en conjuntos de ciudades que variaban de 50 a 500 ubicaciones. Para cada tamaño, ejecutaron el proceso treinta veces para asegurar que los resultados no fueran fruto de la suerte. Compararon un método estándar, que solo utiliza el primer paso de mejora, contra su flujo de trabajo híbrido que añade el segundo paso. Los resultados fueron claros y consistentes: el flujo de trabajo híbrido, que añade la capa extra de refinamiento, produjo rutas más cortas en todos los casos. En promedio, este paso adicional mejoró la longitud de la ruta entre un 2.09% y un 3.48%, dependiendo del tamaño del problema. El análisis estadístico confirmó que estas mejoras no fueron fluctuaciones aleatorias; la diferencia fue lo suficientemente significativa como para ser considerada una ganancia genuina. Además, los investigadores calcularon un "límite inferior", un suelo matemático que representa la distancia más corta que cualquier ruta podría alcanzar teóricamente para ese mapa específico. Encontraron que su método híbrido produjo rutas que eran solo un 4.9% a 5.6% más largas que este suelo teórico, una brecha que se alinea con lo que los expertos han esperado durante mucho tiempo de este tipo de algoritmos.

Para asegurar que sus hallazgos se mantuvieran en el mundo real, el equipo probó su método en cuatro mapas históricos específicos de ciudades como Berlín y otros con soluciones óptimas conocidas. En estas pruebas, cotejaron sus resultados con un resolvedor altamente sofisticado conocido como LKH, que es ampliamente considerado el estándar de oro para encontrar rutas casi perfectas. El resolvedor LKH encontró con éxito las rutas óptimas exactas para los cuatro mapas. El flujo de trabajo híbrido utilizado por los investigadores no igualó esa perfección, pero se acercó notablemente, con rutas finales que fueron entre un 0.94% y un 5.78% más largas que la mejor conocida. Esto confirmó que las mejoras observadas en los mapas sintéticos aleatorios se tradujeron directamente a escenarios del mundo real. El estudio también probó una idea más compleja: utilizar datos matemáticos del límite inferior teórico para guiar el orden en el que se realizaban las mejoras. Este intento de no produjo mejores resultados, un hallazgo que los autores reportaron de manera transparente para evitar que otros investigadores perdieran el tiempo en el mismo callejón sin salida.

La importancia de este trabajo reside no en un nuevo algoritmo, sino en la claridad de su medición. Al combinar un suelo matemático autocalculado con un resolvedor de estándar de oro y pruebas estadísticas rigurosas, los autores proporcionaron una imagen definitiva de lo que un método clásico y no de aprendizaje puede lograr. Demostraron que, si bien estas técnicas antiguas no son perfectas, son notablemente robustas, manteniéndose consistentemente dentro de un margen estrecho de la mejor respuesta posible. El estudio sirve como una base sólida y verificada, demostrando que incluso sin la complejidad del aprendizaje automático moderno, los métodos clásicos siguen siendo herramientas poderosas, predecibles y altamente efectivas para resolver algunos de los desafíos de enrutamiento más complejos del mundo.

Resumen Técnico: Una Evaluación Empírica Estadísticamente Rigurosa de un Pipeline de Búsqueda Local Clásica 2-opt + Or-opt Validada por Held–Karp y LKH

Planteamiento del Problema
El Problema del Viajante (TSP, por sus siglas en inglés) sigue siendo un desafío fundamental en la optimización combinatoria, con aplicaciones que van desde el enrutamiento de vehículos hasta la secuenciación de ADN. Mientras que los algoritmos exactos (por ejemplo, Concorde) y las heurísticas avanzadas (como Lin–Kernighan–Helsgaun, o LKH) están bien establecidos, existe una brecha reportada en la literatura respecto a las evaluaciones empíricas rigurosas y estadísticamente fundamentadas de las heurísticas de búsqueda local clásicas (específicamente 2-opt y Or-opt) contra una referencia de optimalidad certificada. Muchos estudios existentes comparan algoritmos entre sí o contra las mejores soluciones conocidas, en lugar de hacerlo contra un límite inferior probado, y pocos aplican protocolos de pruebas estadísticas estrictos a los pipelines clásicos de forma aislada.

Metodología
Los autores evalúan un pipeline clásico que consiste en una fase de construcción de Vecino Más Cercano (NN) seguida de una búsqueda local híbrida de 2-opt y Or-opt. El estudio emplea un marco metodológico diseñado para la rigurosidad estadística:

Algoritmos Evaluados:
1. Construcción NN por sí sola.
2. NN + búsqueda local 2-opt.
3. NN + 2-opt + Or-opt (reubicación de segmentos con longitudes de trayectoria 1–3) + una iteración final de 2-opt.
Referencia de Optimalidad: En lugar de depender de aproximaciones asintóticas (por ejemplo, la constante de Beardwood-Halton-Hammersley) o de las mejores soluciones conocidas, los autores computan un límite inferior garantizado para cada instancia utilizando la relajación de 1-árbol de Held–Karp mediante optimización de subgradiente.
Diseño Experimental:
- Instancias Sintéticas: 30 ensayos independientes para instancias euclidianas con $n \in \{50, 100, 200, 500\}$ puntos generados uniformemente en un cuadrado de $1000 \times 1000$ .
- Instancias Reales: Cuatro benchmarks de TSPLIB (eil51, berlin52, st70, kroA100) con longitudes de tour óptimas conocidas.
- Restricciones: Todos los algoritmos operaron bajo presupuestos de tiempo de ejecución idénticos (1.0s para $n \le 200$ , 3.0s para $n=500$ ).
Análisis Estadístico: El estudio utiliza pruebas de rango con signo de Wilcoxon con corrección de Bonferroni ( $\alpha = 0.0125$ ), intervalos de confianza de bootstrap (2000 muestras) para las mejoras porcentuales, y tamaños de efecto de par coincidente de razón-biserial ( $r$ ).
Validación: Los resultados se validan cruzadamente con el solver LKH, que sirve como un benchmark casi exacto.

Contribuciones Clave
El artículo establece explícitamente que su contribución es metodológica y empírica, no algorítmica. Los autores no proponen nuevos operadores de búsqueda local; la combinación 2-opt + Or-opt es una técnica clásica. Las contribuciones específicas son:

Rigurosidad Estadística: Aplicación de pruebas estadísticas con corrección de Bonferroni y análisis de tamaño de efecto a la ejecución de la búsqueda local clásica, una práctica que se observa como poco reportada de forma aislada.
Benchmarking Certificado: Comparación del rendimiento de la heurística contra un límite inferior de Held–Karp computado por instancia, en lugar de contra estimaciones asintóticas o soluciones conocidas no verificadas.
Reporte de Resultados Negativos: Reporte transparente de un "resultado negativo" para una extensión probada que intentaba ordenar los movimientos de Or-opt usando información dual de Held–Karp (violaciones de grado), la cual no produjo un beneficio estadísticamente significativo.
Posicionamiento: Situar los resultados de la búsqueda local clásica en relación con el campo de crecimiento rápido de los solvers TSP aprendidos/híbridos (por ejemplo, Zheng et al., Zong et al.), argumentando que la caracterización rigurosa proporcionada aquí puede servir como base para futuros algoritmos de aprendizaje.

Resultos Experimentales

Instancias Sintéticas: El pipeline híbrido (NN + 2-opt + Or-opt) superó consistentemente a 2-opt por sí solo entre un 2.09% y 3.48% en todos los tamaños de problema. Estas mejoras fueron estadísticamente significativas tras la corrección de Bonferroni ( $p < 0.001$ ) con un tamaño de efecto de $r = -1.00$ (indicando que la solución híbrida fue siempre mejor o igual en las 120 comparaciones por pares).
Brechas de Optimalidad: Las soluciones híbridas se mantuvieron dentro de un 4.9% a 5.6% del límite inferior de Held–Karp computado para $n \le 200$ .
Instancias Reales (TSPLIB): En datos del mundo real, el pipeline híbrido logró brechas de entre 0.94% y 5.78% respecto a las longitudes de los tours óptimos conocidos. Estos resultados fueron consistentes con los hallazgos sintéticos.
Validación LKH: El solver LKH recuperó el óptimo publicado exacto (0% de brecha) para las cuatro instancias de TSPLIB, validando la configuración experimental y la transcripción de coordenadas.
Fallo de la Extensión: El intento de guiar el ordenamiento de Or-opt mediante las violaciones de grado de Held–Karp no produjo mejoras (0.00% a 0.05% de cambio, $p > 0.35$ ), lo que sugiere que este ordenamiento heurístico basado en LP no mejora el pipeline clásico bajo las condiciones probadas.

Significancia y Reivindicaciones
Los autores reivindican modestamente que este trabajo proporciona una caracterización metodológicamente rigurosa de un pipeline de búsqueda local clásica. No reclaman novedad algorítmica en el mecanismo de búsqueda en sí. En cambio, la significancia radica en:

Establecer una base estadísticamente sólida para las heurísticas clásicas que pueda utilizarse para evaluar futuros algoritmos, particularmente la emergente clase de solvers aprendidos y de aprendizaje híbrido/exacto.
Demostrar que incluso los pipelines clásicos, no aprendidos, pueden evaluarse con alta confianza estadística contra límites certificados.
Destacar que, si bien los enfoques basados en aprendizaje (por ejemplo, LKH guiado por RL) están avanzando, sus bases suelen medirse contra las mejores soluciones conocidas en lugar de contra límites certificados; el protocolo presentado aquí ofrece un estándar complementario y riguroso para tales comparaciones.

El artículo concluye identificando el trabajo futuro, incluyendo el escalado a instancias más grandes con optimizaciones de lista de candidatos, la incorporación de la selección de 1-árbol optimizada de Righini [20] para obtener límites más ajustados, y la realización de comparaciones directas y con presupuesto de tiempo igualado contra la nueva generación de solvers basados en aprendizaje (incluyendo aquellos de la literatura de 2026).

Más como este