Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows

El artículo demuestra que un método exacto sencillo resuelve casi todas las instancias clásicas de referencia del problema del viajante con ventanas de tiempo en menos de diez segundos, lo que indica que estas ya no son representativas para evaluar algoritmos ni para diseñar conjuntos de entrenamiento difíciles para aprendizaje automático.

Lo esencial

¡Hola! Imagina que eres el jefe de una empresa de reparto de paquetes. Tienes un camión, un depósito de salida y una lista de clientes. Cada cliente tiene una "ventana de tiempo": solo puedes entregarles el paquete entre las 10:00 y las 11:00, por ejemplo. Si llegas antes, tienes que esperar; si llegas tarde, el cliente se enoja. Tu misión es encontrar la ruta perfecta para visitar a todos y volver a casa lo más rápido posible.

Este problema se llama Problema del Viajante de Comercio con Ventanas de Tiempo.

El artículo que me has pedido explicar es como un "chisme" muy importante en el mundo de la inteligencia artificial y la logística. El autor, Francisco Soulignac, nos cuenta una historia sobre cómo hemos estado entrenando a nuestros "cerebros digitales" (algoritmos) con ejemplos que son demasiado fáciles y, por lo tanto, nos están mintiendo sobre lo inteligentes que son realmente.

Aquí te lo explico con analogías sencillas:

1. El problema de los "Videojuegos en Modo Fácil"

Durante décadas, los científicos han usado un conjunto de "niveles" o ejemplos clásicos (llamados benchmarks) para probar si sus algoritmos son buenos resolviendo este problema de reparto.

El autor descubre algo sorprendente: sus nuevos niveles son como jugar al ajedrez contra un niño de 5 años que acaba de aprender a mover las piezas.

• La analogía: Imagina que quieres entrenar a un boxeador para una pelea mundial. Pero, en lugar de hacerlo pelear contra otros boxeadores profesionales, lo haces pelear contra muñecos de cartón que no se mueven. Cuando el boxeador gana todos los combates en 10 segundos, todos gritan: "¡Es el mejor del mundo!". Pero, ¿es realmente el mejor? No sabemos, porque nunca ha enfrentado un golpe real.

2. El "Truco" del Autor

El autor creó un algoritmo muy simple (llamémoslo "El Lápiz y Papel"). No es una supercomputadora con inteligencia artificial compleja; es un método básico y directo.

• Lo que pasó: Cuando probó este "Lápiz y Papel" contra los niveles clásicos (con 50 o más clientes), ¡lo resolvió en menos de 10 segundos!
• La revelación: Esto significa que esos niveles clásicos tienen una estructura tan predecible y "abierta" que cualquier método, incluso uno tonto, puede encontrar la solución casi al instante.

El autor dice: "Oigan, si mi método simple gana tan fácil, los métodos complejos que usan las grandes empresas de IA no están siendo tan geniales como dicen. Solo están adivinando bien porque el examen es demasiado fácil".

3. ¿Por qué fallan los niveles clásicos?

Los niveles clásicos se crearon hace años con una regla muy específica: las ventanas de tiempo eran un poco "apretadas" (como tener que llegar entre las 10:00 y las 10:15).

• La analogía: Imagina que tienes que entrar a una sala donde la puerta se abre solo 15 segundos. Es difícil, pero si sabes exactamente cuándo se abre, puedes planearlo. Los niveles clásicos son como tener una lista de puertas que se abren en momentos muy predecibles.
• El problema real: En la vida real, las cosas son más caóticas. A veces la puerta se abre 1 hora antes, a veces 1 hora después. Los niveles nuevos (llamados Rifki o Fontaine) tienen ventanas de tiempo "flojas" (puedes llegar a cualquier hora). Ahí es donde el "Lápiz y Papel" del autor se queda atascado y falla, mientras que los algoritmos complejos deberían brillar.

4. La Peligrosa Trampa para la Inteligencia Artificial

Hoy en día, muchas empresas usan Inteligencia Artificial (Machine Learning) para crear rutas de reparto. Para entrenar a estas IAs, necesitan miles de ejemplos.

• El error: Muchos investigadores toman los mismos "niveles fáciles" clásicos, los copian y los pegan para crear miles de ejemplos de entrenamiento.
• El resultado: Están entrenando a sus IAs para que sean maestras en resolver el "Modo Fácil", pero cuando las ponen en la calle real (con tráfico, retrasos y ventanas de tiempo locas), fallan estrepitosamente. Es como enseñar a un estudiante a resolver ecuaciones matemáticas solo con números del 1 al 10, y luego sorprenderse cuando no puede sumar 100 + 100.

5. La Conclusión (El mensaje principal)

El autor nos da un consejo de oro: Dejemos de usar solo esos niveles clásicos.

• Si quieres saber si tu algoritmo es realmente bueno, debes probarlo con niveles que tengan ventanas de tiempo más "flojas" y caóticas.
• Si un algoritmo parece increíblemente rápido en los niveles clásicos, no te emociones demasiado; probablemente solo está aprovechando un "bug" o una ventaja en el diseño de esos niveles, no su verdadera inteligencia.

En resumen:
El artículo es una llamada de atención para que dejemos de entrenar a nuestros robots con "videojuegos en modo fácil". Si queremos que la logística del futuro funcione en el mundo real, necesitamos ponerles problemas difíciles, desordenados y reales, no solo esos ejemplos perfectos y predecibles que nos han estado engañando durante años.

¡Espero que esta explicación te haya ayudado a entender la importancia de este descubrimiento!

Resumen técnico

Aquí tienes un resumen técnico detallado del artículo en español, estructurado según los puntos solicitados:

Título: Cuidado con las Instancias de Referencia Clásicas para el Problema del Viajante de Comercio con Ventanas de Tiempo (TSPTW)

Autor: Francisco J. Soulignac
Publicación: Computers & Operations Research (2026)

---

1. El Problema

El artículo se centra en el Problema del Viajante de Comercio con Ventanas de Tiempo (TSPTW), donde un vehículo debe visitar un conjunto de clientes dentro de sus ventanas de tiempo predefinidas, comenzando y terminando en un depósito. El autor analiza tres variantes principales del objetivo:

• TSPTW-M (Makespan): Minimizar el tiempo de finalización de la ruta (tiempo de retorno al depósito).
• TSPTW-D (Duration): Minimizar la duración total de la ruta (tiempo transcurrido entre la salida y el retorno, incluyendo tiempos de espera).
• TSPTW-TT (Travel Time): Minimizar solo el tiempo de viaje, ignorando las esperas.

El problema crítico identificado es que la comunidad científica evalúa la mayoría de los algoritmos (exactos, heurísticos y de aprendizaje automático) utilizando un subconjunto de instancias de referencia clásicas (compiladas por López-Ibáñez y Blum, 2023). El autor argumenta que estas instancias, especialmente aquellas con 50 o más clientes, ya no son representativas ni desafiantes debido a su estructura específica.

2. Metodología

El autor propone y evalúa un método simple pero exacto basado en una búsqueda informada hacia atrás (Backward Best-First Search).

• Algoritmo Principal (Algoritmo 1):
  • Realiza una búsqueda en un árbol de rutas parciales en dirección inversa (desde el depósito final hacia el inicial).
  • Utiliza una heurística que prioriza las rutas parciales que llegan al depósito final lo antes posible, maximizando la oportunidad de esperar en clientes anteriores sin violar las ventanas de tiempo.
  • Implementa estrategias de poda (pruning) avanzadas:
    1. Función de Inalcanzabilidad ($U$): Preprocesa el grafo para identificar vértices que no pueden visitarse antes de un cierto tiempo, descartando ramas del árbol de búsqueda que violen esta restricción.
    2. Dominancia ($ub$-dominated): Descarta rutas parciales si existe otra ruta con el mismo conjunto de vértices visitados que permite una salida más tardía o una llegada más temprana, haciendo innecesaria la exploración de la ruta actual.
• Resolución de TSPTW-D (Algoritmo 3):
  • Para la variante de duración, el método ejecuta el solucionador de TSPTW-M dentro de una ventana deslizante sobre el horizonte de tiempo, utilizando heurísticas de búsqueda local (swap, 2-opt, shift) para acelerar el proceso.

3. Contribuciones Clave

1. Desenmascaramiento de las Instancias Clásicas: Se demuestra que un algoritmo simple y exacto puede resolver todas las instancias clásicas con 50 o más clientes en menos de 10 segundos para TSPTW-M y en menos de 30 minutos para TSPTW-D.
2. Advertencia sobre Sesgo en Benchmarks: Se concluye que las instancias clásicas (Asc, Dum, Gen, Lan, Ohl, DaS) tienen una estructura de ventanas de tiempo "apretadas" (tight) que crea un espacio de búsqueda reducido y predecible. Esto permite que métodos simples parezcan excepcionales, pero fallan estrepitosamente en instancias con ventanas más amplias (loose).
3. Impacto en Aprendizaje Automático: Se advierte que muchos conjuntos de datos de entrenamiento para algoritmos de aprendizaje automático se generan utilizando procedimientos similares a los de las instancias clásicas (ventanas basadas en rutas de vecinos más cercanos con anchos fijos). Esto puede llevar a un overfitting y a conclusiones sesgadas sobre la eficiencia real de los modelos.
4. Nueva Perspectiva sobre la Dificultad: Se refuerza la idea de que la dificultad del TSPTW depende más de la relación entre el ancho de la ventana de tiempo y el horizonte de planificación que del número de clientes.

4. Resultados Computacionales

El autor evaluó su algoritmo (Algoritmo 2 para M, Algoritmo 3 para D) contra el estado del arte (Ler22, Rud23, Fon24) en 1337 instancias:

• En Instancias Clásicas (50+ clientes):
  • El algoritmo propuesto resolvió todas las instancias de los conjuntos Asc, DaS, Gen, Lan y Ohl en tiempos promedio de segundos.
  • Superó a los métodos más avanzados en estas instancias, resolviendo incluso las 4 instancias que permanecían sin resolver en estudios anteriores.
  • Paradoja: El algoritmo falló o se quedó sin memoria en instancias pequeñas (<50 clientes) con ventanas de tiempo muy amplias, mientras que otros algoritmos especializados (como Ler22) las resolvían.
• En Instancias "Duras" (Benchmarks Rifki/Fontaine):
  • En el conjunto Rif (con ventanas de tiempo más amplias controladas por un parámetro $\beta$), el algoritmo propuesto fue el peor en rendimiento, especialmente cuando $\beta$ era bajo (ventanas muy amplias).
  • Los métodos existentes (Ler22, Rud23) demostraron ser mucho más robustos en estos escenarios difíciles.
• Conclusión de los Resultados: Las instancias clásicas son "fáciles" para la búsqueda informada hacia atrás debido a sus ventanas ajustadas, lo que invalida su uso como único criterio de evaluación.

5. Significado e Implicaciones

• Reevaluación de Benchmarks: Las instancias clásicas con 50+ clientes no deben usarse solas para evaluar nuevos algoritmos de TSPTW-M o TSPTW-D. Su uso exclusivo puede llevar a conclusiones falsas sobre la superioridad de un método.
• Diseño de Nuevos Conjuntos de Datos: Para evaluar correctamente la eficiencia y generalización de los algoritmos (especialmente en IA y aprendizaje por refuerzo), es necesario utilizar instancias con ventanas de tiempo más amplias (mayor $\beta$) o generadas bajo criterios que no favorezcan estructuras de búsqueda triviales.
• Precaución en ML: Los investigadores deben ser cautelosos al diseñar conjuntos de entrenamiento para algoritmos de aprendizaje automático. Si los datos de entrenamiento replican la estructura de las instancias clásicas, los modelos aprenderán a explotar sesgos específicos en lugar de resolver el problema general.
• Validación de Métodos: Un método que funcione bien en las instancias clásicas podría no ser generalizable a escenarios del mundo real, donde las ventanas de tiempo pueden ser más flexibles o impredecibles.

En resumen, el artículo es una llamada de atención para la comunidad de investigación operativa y de inteligencia artificial: las instancias de referencia tradicionales han dejado de ser un desafío válido y su uso continuo sin complementos con instancias más difíciles está distorsionando el progreso real en la resolución del TSPTW.