💻 computer science

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

Este artigo aborda o problema interligado de escalonamento e roteamento de combate a incêndios florestais com veículos aéreos não tripulados, onde o atraso na intervenção desencadeia novas chegadas de tarefas devido à propagação do fogo, desenvolvendo programação inteira mista e modelos híbridos para maximizar o valor retido nas regiões ameaçadas.

Autores originais: Erdi Dasdemir, Esther Jose, Rajan Batta

Publicado 2026-08-20

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Erdi Dasdemir, Esther Jose, Rajan Batta

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

No mundo de alto risco da resposta a desastres, o tempo é frequentemente a diferença entre um incidente contido e uma catástrofe. Isso é particularmente verdadeiro para incêndios florestais, onde o comportamento de um fogo não é estático, mas uma entidade viva e pulsante que muda no momento em que é deixada sozinha. Se um incêndio não for combatido imediatamente, ele não apenas fica parado; ele cresce, consome mais valor e, eventualmente, se espalha para novas áreas, criando novas emergências que exigem atenção. Isso cria um quebra-cabeça complexo para os comandantes no terreno: eles devem decidir não apenas para onde enviar seus recursos, mas também quando, sabendo que cada segundo de atraso altera a própria paisagem do problema. O desafio é equilibrar a necessidade imediata de combater um incêndio com a necessidade estratégica de evitar que ele provoque novos focos de incêndio próximos, tudo isso enquanto gerenciam uma frota de veículos que deve reabastecer para continuar trabalhando.

Uma equipe de pesquisadores abordou esse problema intrincado desenvolvendo uma nova maneira de agendar e roteirizar veículos aéreos não tripulados, ou drones, para o combate a incêndios florestais. O trabalho deles foca em uma realidade específica e difícil: incêndios que desencadeiam novos incêndios. Em seu modelo, um incêndio começa em um local específico com uma janela de tempo designada para ser extinto. Se o fogo for deixado queimando por muito tempo, ele cresce até atingir um tamanho crítico, ponto no qual ele naturalmente se espalha para áreas vizinhas, criando novos trabalhos que devem ser combatidos. O objetivo não é apenas apagar as chamas iniciais, mas intervir cedo o suficiente para interromper essa reação em cadeia, preservando assim o valor da terra, das casas e da infraestrutura na região. Os pesquisadores criaram uma estrutura matemática que atua como um motor de tomada de decisão, calculando a rota ideal para uma frota de drones para maximizar a quantidade de valor salvo em toda uma área florestal.

Os pesquisadores testaram sua abordagem usando um modelo computacional que simula uma grade florestal, onde cada quadrado representa um pedaço de terra com seu próprio valor e potencial de propagação de fogo. Eles programaram o modelo para entender que um drone deve visitar uma fonte de água para reabastecer seu tanque entre as missões, adicionando outra camada de complexidade ao roteamento. Em suas simulações, introduziram vários cenários, incluindo diferentes números de drones, variações de velocidades de voo e diferentes padrões de incêndios iniciais. Eles descobriram que seu novo método, que combina um cálculo preciso com um processo de refinamento flexível e passo a passo, foi significativamente mais rápido e confiável do que os métodos anteriores. Enquanto modelos antigos frequentemente tinham dificuldade em encontrar a melhor solução dentro de um tempo razoável, especialmente quando o número de incêndios era alto, a nova abordagem consistentemente encontrou planos de alta qualidade rapidamente. Ela navegou com sucesso pelo equilíbrio entre correr para o incêndio mais próximo e esperar para evitar que uma área mais valiosa queimasse, garantindo que os drones fossem usados onde poderiam salvar o máximo possível.

Para provar a praticidade de seu trabalho, a equipe aplicou seu modelo a cenários realistas baseados nas diversas paisagens da Califórnia. Eles criaram mapas digitais representando diferentes tipos de terreno, desde áreas urbanas densamente povoadas com vegetação pesada até regiões esparsas e desabitadas. Nessas simulações, o modelo direcionou com sucesso frotas de drones para suprimir incêndios e evitar que se espalhassem para zonas críticas. Os resultados mostraram que, ao usar esse agendamento otimizado, o valor total da região protegida permaneceu significativamente mais alto em comparação com esforços menos coordenados. Os pesquisadores também disponibilizaram o código de computador ao público, permitindo que outros especialistas testassem o sistema com seus próprios dados e refinassem as estratégias para implantação no mundo real. Este trabalho oferece uma ferramenta tangível para gestores de desastres, proporcionando uma maneira de transformar a natureza caótica e disseminadora dos incêndios florestais em um conjunto gerenciável de decisões que podem salvar vidas e propriedades.

Resumo Técnico: Escalonamento e Roteamento com Chegadas de Tarefas Gatilhadas por Degradação

Definição do Problema
Este artigo aborda uma nova variante do Problema de Roteamento de Veículos (VRP) e do Problema de Escalonamento de Tarefas (JSP) integrados, denominada "Escalonamento e Roteamento com Chegadas de Tarefas Gatilhadas por Degradação". O desafio central envolve uma rede de potenciais locais de tarefas onde novas tarefas não aparecem aleatoriamente, mas são dinamicamente gatilhadas pela degradação de tarefas existentes.

No contexto específico de combate a incêndios florestais aéreos utilizando Veículos Aéreos Não Tripulados (VANTs/UAVs), o problema é definido como:

Estrutura da Rede: Um grafo baseado em grade representando uma região florestada contendo nós propensos ao fogo, nós à prova de fogo (barreiras), fontes de água e uma base para o VANT.
Dinâmica das Tarefas: Cada área incendiada (tarefa) possui uma janela de tempo designada. Durante esta janela, o fogo cresce (degrada em tamanho) e o valor do nó degrada.
Chegadas Gatilhadas por Degradação: Se um incêndio não for suprimido antes de atingir um limiar crítico de tamanho ( $t_m$ ), ele se espalha para nós adjacentes, gatilhando novas chegadas de tarefas. Isso cria uma interação de duas vias: as decisões de roteamento e escalonamento determinam quando os fogos se espalham (e, portanto, quando novas tarefas chegam), enquanto a chegada de novas tarefas impacta as decisões de roteamento subsequentes.
Objetivo: Maximizar o valor total remanescente da região. Isso envolve suprimir incêndios antes que eles causem perda total de valor e evitar a propagação de incêndios para nós adjacentes de alto valor. O modelo considera as restrições do VANT, incluindo a necessidade de visitar recursos hídricos para reabastecer tanques entre tarefas e o requisito de liberar cargas de água cheias, independentemente do tamanho do fogo.

Metodologia
Os autores desenvolvem uma estrutura de otimização matemática composta por dois modelos primários:

Modelo de Programação Inteira Mista Exata (EM):
- O EM formula o problema utilizando variáveis binárias para roteamento de veículos, seleção de tarefas e lógica de propagação de fogo, juntamente com variáveis contínuas para tempo e valor.
- Incorpora aproximações lineares para o crescimento do tamanho do fogo e a degradação do valor para equilibrar realismo com tratabilidade computacional.
- O modelo vincula explicitamente as decisões de escalonamento (tempos de chegada) com a lógica de progressão do fogo. Utiliza restrições "Big-M" para modelar quatro casos distintos de propagação de fogo baseados em se um nó possui fogo, se um veículo chega e o tempo dessa chegada em relação à fase de crescimento crítico do fogo.
- A função objetivo maximiza a soma dos valores coletados dos nós, penalizando o tempo gasto para retornar à base.
Modelo Híbrido: Modelo de Adiamento de Reabastecimento Guiado pelo Modelo Exato (E-RDM):
- Reconhecendo que o EM tem dificuldades de escalabilidade devido a relaxações fracas de programação linear (LP) e à complexidade das restrições de reabastecimento de água, os autores propõem uma abordagem híbrida.
- EM com Reabastecimento Adiado (RDM): Uma versão relaxada do EM que omite as restrições específicas que exigem visitas a recursos de água entre tarefas consecutivas e as restrições de acoplamento temporal associadas.
- Branch-and-Cut com Restrições Adiadas: O algoritmo E-RDM primeiro resolve o RDM para gerar soluções viáveis de alta qualidade. Em seguida, emprega uma estrutura de branch-and-cut com um callback de restrição adiada. Se uma solução violar as restrições de reabastecimento de água ou de acoplamento temporal omitidas, as restrições correspondentes são adicionadas dinamicamente como cortes (cuts).
- Estratégia de Dois Estágios: O algoritmo aloca uma parte do tempo total de execução para resolver o EM completo (para encontrar soluções ótimas rapidamente, se possível) e o restante para o RDM com geração dinâmica de restrições (para melhorar os limites e lidar com instâncias maiores).

Principais Contribuições
O artigo identifica três contribuições primárias:

Avanço Teórico: Introduz o conceito de chegadas de tarefas gatilhadas por degradação na literatura de escalonamento e roteamento. Diferente dos VRPs dinâmicos padrão, onde as chegadas são estocásticas ou independentes das decisões, este modelo apresenta uma interação de duas vias onde as decisões influenciam diretamente a chegada de novas tarefas.
Aplicação em Gestão de Desastres: Fornece um modelo de tomada de decisão prescritivo para o combate a incêndios florestais aéreos. O modelo integra logística (roteamento, reabastecimento) com planejamento operacional (tempo de supressão de incêndio) para abordar o "Problema de Proteção de Ativos" (APP) em cenários de incêndios florestais.
Reprodutibilidade e Ferramental: Os autores desenvolveram uma interface de software (baseada em planilhas) vinculada ao seu código Python/Gurobi, permitindo que profissionais gerem instâncias de problemas e encontrem soluções ótimas sem interagir com o código bruto. O código-fonte é compartilhado via GitHub para facilitar a reprodutibilidade.

Resultados
Experimentos computacionais foram realizados em uma estação de trabalho de 2 núcleos e 28 threads usando o Gurobi Optimizer 10.0.1.

Comparação de Desempenho: O modelo híbrido E-RDM superou significativamente o EM exato. Enquanto o EM frequentemente falhava em provar a otimalidade dentro do limite de tempo (3.600 segundos) para instâncias com alto número de chegadas de tarefas ou capacidade de frota limitada, o E-RDM alcançou consistentemente um hiato de otimalidade (optimality gap) inferior a 3% em 1.260 execuções.
Escalabilidade: O E-RDM demonstrou robustez em variações de tamanho de frota (2 vs. 4 VANTs) e velocidades (60 vs. 120 km/h). Resolveu instâncias com um tempo médio de execução de 47 segundos.
Impacto das Chegadas de Tarefas: O estudo confirmou que, conforme o número de chegadas de tarefas aumenta (impulsionado pelos incêndios iniciais e taxas de propagação), a dificuldade computacional para o EM aumenta drasticamente. O E-RDM mitigou isso efetivamente, aproveitando a formulação relaxada para guiar a busca.
Estudo de Caso: Um estudo de caso baseado nas características de incêndios florestais da Califórnia (usando dados de classificação de terra SILVIS) demonstrou a capacidade do modelo em lidar com diversos tipos de paisagens, desde interfaces urbanas de alta densidade até áreas vegetadas inabitadas. O modelo gerou com sucesso planos de supressão que maximizaram a retenção de valor em sete tipos diferentes de cenários.

Significância e Alegações
O artigo posiciona seu trabalho como uma aplicação prática do ditado "um ponto preventivo economiza nove", enfatizando que a intervenção precoce e coordenada evita danos desproporcionais. Os autores alegam que seu modelo oferece uma melhoria significativa em relação às abordagens existentes ao modelar explicitamente o elo causal entre atrasos na supressão e a geração de novas tarefas de incêndio (spotfires).

O estudo não pretende resolver a física contínua do comportamento do fogo, mas sim estabelecer um equilíbrio entre realismo e tratabilidade ao utilizar aproximações lineares para a propagação do fogo e a degradação do valor. A significância reside em fornecer um sistema de suporte à decisão que possa lidar com a natureza dinâmica e interdependente da supressão de incêndios florestais, onde atrasar uma única tarefa pode aumentar exponencialmente a carga de trabalho e reduzir o valor total da região protegida. Os autores concluem que sua abordagem híbrida oferece um caminho viável para resolver problemas complexos de logística de resposta a desastres que anteriormente eram computacionalmente intratáveis.

Mais como este