KAYROS: An Anytime and Exact Open-Source Solver for Duration-Minimization Time-Dependent Vehicle Routing. A Technical Report and a Case Study in Human-AI Engineering

Imagina que eres el despachador de una flota de camiones de reparto en una ciudad bulliciosa. Tu objetivo es simple: entregar los paquetes a los clientes y hacer que los conductores vuelvan a casa lo más rápido posible para ahorrar dinero en salarios. Pero hay un truco: la ciudad está viva. Una carretera que tarda diez minutos a las 8:00 AM podría tardar cuarenta minutos a las 9:00 AM debido al tráfico de la hora punta. Este es el mundo del Ruteo de Vehículos Dependiente del Tiempo. Es un rompecabezas clásico en el campo de la Investigación de Operaciones, que es básicamente la ciencia de tomar las mejores decisiones posibles cuando tienes recursos limitados y reglas complejas.

Durante décadas, las computadoras han sido excelentes resolviendo estos acertijos, pero generalmente con una gran simplificación: fingen que el tráfico es estático, como un mapa donde las carreteras nunca cambian. La vida real, sin embargo, es un río que fluye, no un estanque quieto. Para resolver el rompecabezas perfectamente, necesitas saber exactamente cuándo sale un camión del depósito, porque salir cinco minutos más tarde podría significar encontrarse con un atasco que añada una hora al viaje, o podría significar evitar un semáforo en rojo que ahorre diez minutos. El desafío es que las matemáticas para determinar el tiempo de salida "perfecto" para cada camión, respetando las ventanas de tiempo de los clientes y los patrones de tráfico, es increíblemente difícil. Es como intentar resolver un Cubo de Rubik donde los colores cambian de posición mientras giras las caras.

Aquí es donde entra en juego una nueva herramienta llamada KAYROS. Piensa en KAYROS como un mago del tráfico súper inteligente e incansable que no solo adivina, sino que calcula el mejor horario posible. Pero este es el truco de magia: no solo te da una respuesta "suficientemente buena" después de esperar una hora. Comienza a darte respuestas cada vez mejores desde el primer segundo en que empieza a pensar y, si lo detienes, te ofrece la mejor solución que encontró hasta el momento. Aún más genial, puede demostrar que una solución es matemáticamente perfecta, no solo un golpe de suerte. El artículo también introduce un nuevo y masivo conjunto de acertijos de práctica llamados Poryos2026, construidos a partir de mapas de ciudades reales, para probar si estos magos son realmente buenos en su trabajo.

La Magia de KAYROS: Un Solucionador que Nunca Duerme

El artículo presenta KAYROS, una herramienta de software de código abierto diseñada para resolver el "Problema de Ruteo de Vehículos Dependiente del Tiempo". Imagina que estás intentando planificar un viaje por carretera para una flota de repartidores. Tienes una lista de paradas y cada parada tiene una ventana de tiempo específica en la que el cliente está en casa (por ejemplo, "Solo se puede entregar el paquete entre las 2:00 PM y las 4:00 PM"). La parte complicada es que el tiempo que se tarda en conducir entre paradas cambia dependiendo de a qué hora del día salgas.

KAYROS es especial porque hace dos cosas a la vez, una combinación poco común en el mundo de los solucionadores computacionales:

1. Es "Anytime" (En cualquier momento): Cuando ejecutas KAYROS, no se queda en silencio durante horas. Comienza a arrojar soluciones inmediatamente. La primera puede ser aceptable, pero la siguiente es mejor, y la siguiente es aún mejor. Es como un chef que prueba una sopa y añade especias continuamente; puedes detener la cocción en cualquier momento y tendrás la mejor sopa posible para esa cantidad de tiempo.
2. Es "Exacto": Si lo dejas correr el tiempo suficiente, no solo adivina la mejor respuesta, sino que demuestra que es la mejor respuesta posible. Genera un "certificado", que es como un recibo matemático que cualquiera puede verificar para comprobar que no existe otra ruta que pueda ser más rápida.

Los autores construyeron esta herramienta para que sea completamente gratuita y abierta. Puedes instalarla con un solo comando en tu computadora y no requiere ningún software costoso o secreto de grandes empresas. Utiliza un motor ingenioso que trata el tiempo de viaje no como un número único, sino como una función fluida: una línea que sube y baja dependiendo de la hora del día. Esto le permite manejar patrones de tráfico complejos del mundo real donde una carretera podría congestionarse repentinamente en un minuto específico.

La Historia de la "Autorefutación": Cómo Atraparon su Propio Error

Una de las partes más fascinantes del artículo es una historia sobre la honestidad. Los autores querían asegurarse de que sus certificados "perfectos" fueran realmente perfectos. Establecieron una regla estricta: para afirmar que una solución es la mejor, cuatro ejecuciones diferentes de la computadora deben coincidir en la misma respuesta exacta.

Durante una prueba, encontraron un problema. KAYROS había emitido 160 "certificados" afirmando que ciertas rutas eran las mejores posibles. Pero luego, su propio solucionador "anytime" (el que sigue mejorando) encontró rutas que eran en realidad más rápidas que esos certificados "perfectos". ¡Esto fue una sorpresa! Resultó que KAYROS había estado usando un truco de "suavizado" para manejar saltos repentinos en los datos de tráfico (como una carretera que instantáneamente se convierte en un estacionamiento). Este truco era ligeramente erróneo, lo que causaba que la computadora calculara mal el tiempo.

Los autores no ocultaron esto. Retractaron públicamente todos los 160 certificados, corrigieron el código para manejar estos "saltos" de forma exacta y repitieron las pruebas. Esta historia se incluye para mostrar que su sistema es robusto: incluso cuando la IA comete un error, las reglas de verificación lo detectan y la verdad gana.

El Nuevo Patio de Juegos: Poryos2026

Para probar si KAYROS realmente funciona, los autores necesitaban un patio de juegos que se pareciera al mundo real. Crearon Poryos2026, una familia de 1,080 nuevos acertijos de prueba. En lugar de usar mapas falsos e inventados, extrajeron redes de carreteras reales de cinco ciudades importantes: Lyon, París, San Francisco, Hong Kong y Tokio, utilizando datos de OpenStreetMap (un mapa gratuito construido por la comunidad).

Luego añadieron tráfico sintético (falso pero realista), demandas de clientes y ventanas de tiempo a estos mapas reales. Esto creó un enorme conjunto de desafíos que mezclan la geografía real con escenarios de tráfico controlados. Para cada uno de estos 1,080 acertijos, generaron una "mejor solución conocida" utilizando su propio solucionador. Esto ofrece a otros investigadores una forma justa y realista de probar sus propias herramientas contra un estándar que refleja la conducción urbana real, no solo problemas matemáticos abstractos.

El Equipo Formado por Humanos e IA

Quizás la parte más única de este artículo es cómo fue escrito. El autor, un estudiante de doctorado, trabajó en una colaboración intensa con un agente de IA (un modelo de lenguaje de gran tamaño) durante aproximadamente dos semanas. El humano estableció los objetivos, tomó las decisiones importantes y revisó el trabajo, mientras que la IA realizó el trabajo pesado: escribir código, ejecutar miles de experimentos computacionales y depurar errores.

El autor estima que esta colaboración de dos semanas realizó el trabajo que le habría tomado dos o más años hacer solo. Sin embargo, el artículo es muy cuidadoso al notar que esto no fue simplemente "escribir más rápido". El humano tuvo que dedicar mucho tiempo a preparar a la IA con el contexto adecuado, revisar su trabajo y asegurar que los resultados fueran científicamente sólidos. El artículo argumenta que este tipo de asociación es el futuro de la investigación, pero solo si existen reglas estrictas (como el sistema de "certificados") para verificar que la IA no inventó hechos o alucinó resultados.

Lo Que Esto Significa para el Futuro

El artículo no afirma que KAYROS sea el solucionador más rápido del mundo (aún no se han comparado frente a frente con todas las otras herramientas), ni afirma haber resuelto todos los problemas de ruteo posibles. En cambio, ofrece una herramienta sólida, verificada y gratuita que finalmente trae la resolución "exacta" y "anytime" a los complejos problemas de tráfico dependientes del tiempo.

Al combinar un nuevo y potente solucionador, un enorme conjunto de casos de prueba del mundo real y una historia transparente sobre cómo los humanos y la IA pueden trabajar juntos de manera responsable, los autores han proporcionado una nueva base para la logística. Ya sea entregando pizza, gestionando camiones de basura o planificando rutas de respuesta de emergencia, la capacidad de calcular el momento perfecto para salir, sabiendo que puedes detenerte y obtener una buena respuesta en cualquier momento, es un paso significativo hacia adelante en la ciencia de mover las cosas en nuestro mundo bullicioso.