💻 computer science

Scheduling and Routing with Degradation-Triggered Job Arrivals: An Application to Forest Firefighting with an Unmanned Aerial Vehicle Fleet

Este artículo aborda el problema entrelazado de programación y rutas de la extinción de incendios forestales con vehículos aéreos no tripulados, donde el retraso en la intervención provoca la llegada de nuevos trabajos debido a la propagación del fuego, mediante el desarrollo de modelos de programación entera mixta e híbridos para maximizar el valor retenido en las regiones amenazadas.

Autores originales: Erdi Dasdemir, Esther Jose, Rajan Batta

Publicado 2026-08-20

📖 4 min de lectura☕ Lectura para el café

CC BY 4.0

Autores originales: Erdi Dasdemir, Esther Jose, Rajan Batta

Artículo original bajo licencia CC BY 4.0 (http://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

En el mundo de alto riesgo de la respuesta ante desastres, el tiempo es a menudo la diferencia entre un incidente contenido y una catástrofe. Esto es particularmente cierto para los incendios forestales, donde el comportamiento de un fuego no es estático, sino una entidad viva y palpitante que cambia en el momento en que se le deja solo. Si un incendio no se aborda de inmediato, no se queda simplemente ahí; crece más, consume más valor y, eventualmente, se propaga a nuevas áreas, creando nuevas emergencias que exigen atención. Esto crea un rompecabezas complejo para los comandantes en el terreno: deben decidir no solo a dónde enviar sus recursos, sino también cuándo, sabiendo que cada segundo de retraso altera el panorama del problema mismo. El desafío es equilibrar la necesidad inmediata de combatir un incendio con la necesidad estratégica de evitar que este provoque nuevos incendios cercanos, todo ello mientras se gestiona una flota de vehículos que deben repostar para seguir trabajando.

Un equipo de investigadores ha abordado este intrincado problema desarrollando una nueva forma de programar y trazar rutas para vehículos aéreos no tripulados, o drones, para la extinción de incendios forestales. Su trabajo se centra en una realidad específica y difícil: fuegos que desencadenan nuevos fuegos. En su modelo, un incendio comienza en una ubicación específica con una ventana de tiempo designada para ser extinguido. Si se deja arder demasiado tiempo, crece hasta alcanzar un tamaño crítico, momento en el cual se propaga naturalmente a áreas vecinas, creando nuevos trabajos que deben ser combatidos. El objetivo no es solo apagar las llamas iniciales, sino intervenir lo suficientemente pronto como para detener esta reacción en cadena, preservando así el valor de la tierra, las viviendas y la infraestructura de la región. Los investigadores crearon un marco matemático que actúa como un motor de toma de decisiones, calculando la ruta óptima para una flota de drones con el fin de maximizar la cantidad de valor salvado en toda un área forestal.

Los investigadores probaron su enfoque utilizando un modelo informático que simula una cuadrícula forestal, donde cada cuadrado representa un parche de tierra con su propio valor y potencial de propagación de incendios. Programaron el modelo para entender que un dron debe visitar una fuente de agua para rellenar su tanque entre misiones, añadiendo otra capa de complejidad al enrutamiento. En sus simulaciones, introdujeron varios escenarios, incluyendo diferentes números de drones, distintas velocidades de vuelo y diferentes patrones de incendios iniciales. Descubrieron que su nuevo método, que combina un cálculo preciso con un proceso de refinamiento flexible y paso a paso, era significativamente más rápido y fiable que los métodos anteriores. Mientras que los modelos antiguos a menudo tenían dificultades para encontrar la mejor solución en un tiempo razonable, especialmente cuando el número de incendios era alto, el nuevo enfoque encontraba consistentemente planes de alta calidad rápidamente. Navegó con éxito la compensación entre apresurarse hacia el incendio más cercano y esperar para evitar que una zona más valiosa ardiera, asegurando que los drones se utilizaran donde pudieran salvar la mayor cantidad.

Para demostrar la practicidad de su trabajo, el equipo aplicó su modelo a escenarios realistas basados en los diversos paisajes de California. Crearon mapas digitales que representaban diferentes tipos de terreno, desde zonas urbanas densamente pobladas con vegetación abundante hasta regiones escasas y deshabitadas. En estas simulaciones, el modelo dirigió con éxito flotas de drones para suprimir incendios y evitar que se propagaran a zonas críticas. Los resultados mostraron que, al utilizar esta programación optimizada, el valor total de la región protegida se mantuvo significativamente más alto en comparación con esfuerzos menos coordinados. Los investigadores también pusieron su código informático a disposición del público, permitiendo que otros expertos prueben el sistema con sus propios datos y perfeccionen las estrategias para su despliegue en el mundo real. Este trabajo ofrece una herramienta tangible para los gestores de desastres, proporcionando una forma de convertir la naturaleza caótica y expansiva de los incendios forestales en un conjunto manejable de decisiones que pueden salvar vidas y propiedades.

Resumen Técnico: Programación y Enrutamiento con Llegadas de Tareas Desencadenadas por Degradación

Definición del Problema
Este artículo aborda una variante novedosa del Problema de Enrutamiento de Vehículos (VRP) y el Problema de Programación de Tareas (JSP) integrados, denominada "Programación y Enrutamiento con Llegadas de Tareas Desencadenadas por Degradación". El desafío central involucra una red de posibles ubicaciones de tareas donde las nuevas tareas no aparecen de forma aleatoria, sino que se activan dinámicamente mediante la degradación de las tareas existentes.

En el contexto específico de la extinción de incendios forestales aérea mediante Vehículos Aéreos No Tripulados (UAV), el problema se define de la siguiente manera:

Estructura de la Red: Un grafo basado en una cuadrícula que representa una región forestal que contiene nodos propensos al fuego, nodos a prueba de fuego (barreras), fuentes de agua y una base para los UAV.
Dinámica de las Tareas: Cada área incendiada (tarea) tiene un intervalo de tiempo designado. Durante este intervalo, el fuego crece (se degrada en tamaño) y el valor del nodo se degrada.
Llegadas Desencadenadas por Degradación: Si un incendio no es suprimido antes de alcanzar un umbral crítico de tamaño ( $t_m$ ), se propaga a los nodos adyacentes, desencadenando la llegada de nuevas tareas. Esto crea una interacción bidireccional: las decisiones de enrutamiento y programación determinan cuándo se propagan los incendios (y, por lo tanto, cuándo llegan las nuevas tareas), mientras que la llegada de nuevas tareas impacta las decisiones de enrutamiento posteriores.
Objetivo: Maximizar el valor restante total de la región. Esto implica suprimir los incendios antes de que causen una pérdida total de valor y evitar la propagación de los incendios hacia nodos adyacentes de alto valor. El modelo tiene en cuenta las restricciones de los UAV, incluyendo la necesidad de visitar recursos hídricos para rellenar los tanques entre tareas y el requisito de liberar las cargas de agua completas independientemente del tamaño del fuego.

Metodología
Los autores desarrollan un marco de optimización matemática que consta de dos modelos principales:

Modelo de Programación Entera Mixta (MIP) Exacto (EM):
- El EM formula el problema utilizando variables binarias para el enrutamiento de vehículos, la selección de tareas y la lógica de propagación del fuego, junto con variables continuas para el tiempo y el valor.
- Incorpora aproximaciones lineales para el crecimiento del tamaño del fuego y la degradación del valor para equilibrar el realismo con la tractabilidad computacional.
- El modelo vincula explícitamente las decisiones de programación (tiempos de llegada) con la lógica de progresión del fuego. Utiliza restricciones "Big-M" para modelar cuatro casos distintos de propagación de incendios basados en si un nodo tiene fuego, si un vehículo llega y el momento de dicha llegada en relación con la fase de crecimiento crítico del fuego.
- La función objetivo maximiza la suma de los valores recolectados de los nodos, penalizando el tiempo tomado para regresar a la base.
Modelo Híbrido: Modelo de Diferimiento de Recarga Guiado por Modelo Exacto (E-RDM):
- Reconociendo que el EM tiene dificultades de escalabilidad debido a las débiles relajaciones de programación lineal (LP) y la complejidad de las restricciones de recarga de agua, los autores proponen un enfoque híbrido.
- EM con Recarga Diferida (RDM): Una versión relajada del EM que omite las restricciones específicas que requieren visitas a recursos de agua entre tareas consecutivas y las restricciones de acoplamiento temporal asociadas.
- Branch-and-Cut con Restricciones Diferidas: El algoritmo E-RDM primero resuelve el RDM para generar soluciones factibles de alta calidad. Luego emplea un marco de branch-and-cut con un callback de restricción diferida. Si una solución viola las restricciones de recarga de agua o de acoplamiento de tiempo omitidas, las restricciones correspondientes se añaden dinámicamente como cortes (cuts).
- Estrategia de Dos Etapas: El algoritmo asigna una parte del tiempo total de resolución para resolver el EM completo (para encontrar soluciones óptimas rápidamente si es posible) y el resto al RDM con generación dinámica de restricciones (para mejorar las cotas y manejar instancias más grandes).

Contribuciones Clave
El artículo identifica tres contribuciones primarias:

Avance Teórico: Introduce el concepto de llegadas de tareas desencadenadas por degradación a la literatura de programación y enrutamiento. A diferencia de los VRP dinámicos estándar donde las llegadas son estocásticas o independientes de las decisiones, este modelo presenta una interacción bidireccional donde las decisiones influyen directamente en la llegada de nuevas tareas.
Aplicación en Gestión de Desastres: Proporciona un modelo de toma de decisiones prescriptivo para la extinción de incendios forestales aérea. El modelo integra la logística (enrutamiento, recarga) con la planificación operativa (tiempo de supresión del fuego) para abordar el "Problema de Protección de Activos" (APP) en escenarios de incendios forestales.
Reproducibilidad y Herramientas: Los autores desarrollaron una interfaz de software (basada en hojas de cálculo) vinculada a su código Python/Gurobi, lo que permite a los profesionales generar instancias de problemas y encontrar soluciones óptimas sin interactuar con el código bruto. El código se comparte vía GitHub para facilitar la reproducibilidad.

Resultados
Los experimentos computacionales se realizaron en una estación de trabajo de 2 núcleos y 28 hilos utilizando Gurobi Optimizer 10.0.1.

Comparación de Rendimiento: El modelo híbrido E-RDM superó significativamente al EM exacto. Mientras que el EM a menudo fallaba en demostrar la optimalidad dentro del límite de tiempo (3,600 segundos) para instancias con altas llegadas de tareas o capacidad de flota limitada, el E-RDM alcanzó consistentemente una brecha de optimalidad inferior al 3% en 1,260 ejecuciones.
Escalabilidad: El E-RDM demostró robustez ante diversas escalas de flota (2 vs. 4 UAV) y velocidades (60 vs. 120 km/h). Resolvió instancias con un tiempo de ejecución promedio de 47 segundos.
Impacto de las Llegadas de Tareas: El estudio confirmó que a medida que aumenta el número de llegadas de tareas (impulsadas por los incendios iniciales y las tasas de propagación), la dificultad computacional para el EM aumenta drásticamente. El E-RDM mitigó esto eficazmente aprovechando la formulación relajada para guiar la búsqueda.
Estudio de Caso: Un estudio de caso basado en las características de los incendios forestales de California (utilizando datos de clasificación de tierras SILVIS) demostró la capacidad del modelo para manejar diversos paisajes, desde interfaces urbanas de alta densidad hasta áreas vegetadas deshabitadas. El modelo generó con éxito planes de supresión que maximizaron la retención de valor a través de siete tipos diferentes de escenarios.

Significancia y Reivindicaciones
El artículo posiciona su trabajo como una aplicación práctica del adagio "más vale prevenir que lamentar" (o "una puntada a tiempo ahorra nueve"), enfatizando que una intervención temprana y bien coordinada evita daños desproporcionados. Los autores afirman que su modelo ofrece una mejora significativa respecto a los enfoques existentes al modelar explícitamente el vínculo causal entre los retrasos en la supresión y la generación de nuevas tareas de incendio (focos secundarios).

El estudio no pretende resolver la física continua del comportamiento del fuego, sino que busca un equilibrio entre el realismo y la tractabilidad mediante el uso de aproximaciones lineales para la propagación del fuego y la degradación del valor. La significancia radica en proporcionar un sistema de apoyo a la decisión que pueda manejar la naturaleza dinámica e interdependiente de la supresión de incendios forestales, donde retrasar una sola tarea puede aumentar exponencialmente la carga de trabajo y reducir el valor total de la región protegida. Los autores concluyen que su enfoque híbrido ofrece una vía viable para resolver problemas de logística de respuesta ante desastres complejos que anteriormente eran computacionalmente intratables.

Más como este