Solver-Informed Evolution of Interpretable Dispatching Rules for the Stochastic Team Orienteering Problem with Time Windows

Imagina una flota de vehículos compitiendo contra el reloj para visitar una colección dispersa de ubicaciones, cada una de las cuales ofrece una recompensa diferente. El objetivo es simple: recolectar tanto valor como sea posible antes de que se agote el tiempo. Pero el mundo no es una hoja de cálculo. El tiempo que toma completar una tarea en cualquier lugar es incierto; una ráfaga repentina de viento podría retrasar a un dron, o mares agitados podrían ralentizar a un bote. Además, cada ubicación está disponible solo durante una ventana de tiempo específica. Si un vehículo llega demasiado temprano, debe esperar; si llega demasiado tarde, la oportunidad desaparece para siempre. Esta es la esencia de un desafío logístico complejo conocido como el problema de orientación de equipos con ventanas de tiempo. En el mundo real, este escenario ocurre cuando los bomberos intentan contener un incendio forestal, las cuadrillas de limpieza de derrames de petróleo compiten por contener una mancha antes de que llegue a la costa, o los equipos médicos deben visitar a pacientes dentro de marcos de tiempo críticos. La dificultad radica en tomar la siguiente decisión instantáneamente, sin saber exactamente cuánto tiempo tomará la tarea actual, y sin el lujo de un supercomputador para recalcular todo el plan cada segundo.

Durante años, los investigadores han intentado resolver esto enseñando a las computadoras a evolucionar reglas de decisión simples. Estas reglas actúan como un controlador de tráfico, observando la situación actual y decidiendo inmediatamente qué cliente visitar a continuación. El método más exitoso hasta ahora, conocido como NS-GP, se basa en un conjunto fijo de once características básicas —como qué tan lejos está un cliente o cuánto tiempo queda— para tomar estas decisiones. Aunque es efectivo, este enfoque tiene un techo. Utiliza un vocabulario limitado para describir el mundo, muy parecido a intentar escribir una novela usando solo cien palabras. Los investigadores detrás de este nuevo estudio, liderados por Augusto Mendonça y su equipo en universidades de Brasil, se hicieron una pregunta audaz: ¿qué pasaría si la computadora pudiera aprender un vocabulario más rico observando cómo un planificador experto resuelve el problema de forma fuera de línea (offline)? Querían ver si podían extraer la lógica oculta de las soluciones de alta calidad y convertir esos conocimientos en reglas simples y legibles que funcionen en tiempo real.

El equipo desarrolló un nuevo método llamado SI-GP, que significa Programación Genética Informada por el Solucionador (Solver-Informed Genetic Programming). El proceso comienza no con la computadora adivinando, sino con la computadora observando. Primero, los investigadores utilizaron potentes solucionadores de alta velocidad para encontrar las mejores rutas posibles para un conjunto de cuarenta problemas de prueba diferentes, asumiendo que todo saldría perfecto. Luego, tomaron esas rutas perfectas y las reprodujeron en un mundo simulado donde ocurrían retrasos de forma aleatoria, tal como sucede en la realidad. Al comparar los planes perfectos con lo que realmente sucedió, el equipo identificó operaciones específicas que los planes perfectos realizaban pero que las reglas estándar pasaban por alto. Por ejemplo, notaron que los mejores planes a menudo miraban varios pasos adelante para ver qué recompensas seguirían siendo alcanzables, o calculaban el riesgo de perder una oportunidad futura si se comprometían con una tarea actual.

A partir de estas observaciones, los investigadores construyeron una nueva biblioteca de dieciocho características de decisión. Dieciséis de ellas se basaron en conceptos establecidos de programación, mientras que dos eran combinaciones completamente nuevas diseñadas para sopesar el costo de una decisión frente a la ganancia potencial. Este nuevo vocabulario le dio a la computadora una forma mucho más matizada de entender el problema. Sin embargo, tener más opciones no significa automáticamente mejores resultados; a veces, demasiadas opciones confunden al sistema. Para resolver esto, el equipo utilizó una segunda capa de inteligencia para seleccionar el mejor subconjunto de estas características para cada problema específico. Trataron el proceso de selección como un torneo, evolucionando diferentes combinaciones de características y probándolas rigurosamente. Esto fue posible gracias a un motor personalizado que se ejecuta en tarjetas gráficas, lo que les permitió probar miles de combinaciones en el tiempo que antes se usaba para probar solo una.

Los resultados fueron impactantes. En los cuarenta problemas de referencia, el nuevo método nunca funcionó peor que el estándar anterior. En treinta y ocho de los casos, el sistema evolucionó una nueva regla que superó al mejor anterior. En promedio, las nuevas reglas mejoraron la recompensa total recolectada en un 1.0 por ciento en todas las pruebas, y en un 1.3 por ciento en los problemas donde todavía había margen de mejora. En diez casos específicos, la mejora fue estadísticamente significativa y lo suficientemente grande como para ser considerada un gran avance para ese escenario específico. Quizás lo más importante es que las nuevas reglas siguieron siendo simples y legibles. No eran algoritmos de "caja negra" que nadie podía entender; eran expresiones matemáticas compactas que un humano podía leer y verificar. En muchos casos, las nuevas reglas también fueron más estables, produciendo resultados consistentes incluso cuando los retrasos aleatorios variaban, mientras que las reglas antiguas a veces oscilaban violentamente entre buenos y malos resultados.

El estudio también reveló por qué ocurrieron las mejoras. Las nuevas reglas fueron particularmente efectivas en situaciones donde el sistema base tenía dificultades para visitar a todos los clientes posibles. En estos escenarios "no saturados", el nuevo vocabulario permitió al sistema navegar por compensaciones complejas, como visitar a un cliente distante de alto valor incluso si eso significaba saltarse a uno cercano de bajo valor. Los investigadores encontraron que las nuevas características ayudaron al sistema a regularizar su búsqueda, lo que significa que era menos probable que se quedara atrapado en una trampa local y más probable que encontrara un camino robusto hacia adelante. El método funcionó aprendiendo de la estructura de las soluciones de alta calidad sin simplemente copiarlas. No intentó imitar la ruta exacta del planificador experto; en cambio, aprendió los principios que hicieron que esas rutas fueran exitosas y los aplicó a un nuevo entorno incierto.

Este trabajo demuestra que es posible cerrar la brecha entre la optimización compleja fuera de línea y la toma de decisiones rápida en línea. Al utilizar los conocimientos de los solucionadores de alta calidad para construir un mejor vocabulario, y luego seleccionar cuidadosamente las herramientas adecuadas para cada trabajo específico, los investigadores crearon un sistema que es tanto poderoso como transparente. El producto final es un conjunto de reglas de decisión que pueden integrarse directamente en vehículos o drones, permitiéndoles tomar decisiones inteligentes en microsegundos sin necesidad de conectarse a una computadora central o ejecutar simulaciones compleas. El enfoque sugiere un nuevo camino para la inteligencia artificial en la logística: uno que valore la interpretabilidad y la adaptabilidad, asegurando que las máquinas que toman decisiones críticas puedan ser comprendidas por los humanos que dependen de ellas. Los investigadores han puesto su código, datos y las reglas específicas que descubrieron a disposición del público, invitando a otros a construir sobre esta base para futuros desafíos en entornos inciertos.