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

Imagine uma frota de veículos correndo contra o tempo para visitar uma coleção dispersa de locais, cada um oferecendo uma recompensa diferente. O objetivo é simples: coletar o máximo de valor possível antes que o tempo se esgote. Mas o mundo não é uma planilha. O tempo necessário para completar uma tarefa em qualquer ponto é incerto; uma rajada de vento repentina pode atrasar um drone, ou mares agitados podem retardar um barco. Além disso, cada local está disponível apenas para uma janela específica de tempo. Se um veículo chegar cedo demais, deverá esperar; se chegar tarde demais, a oportunidade desaparecerá para sempre. Esta é a essência de um desafio logístico complexo conhecido como problema de orienteamento de equipe com janelas de tempo. No mundo real, este cenário ocorre quando bombeiros tentam conter um incêndio florestal, equipes de contenção de derramamento de óleo correm para conter uma mancha antes que ela atinja a costa, ou equipes médicas precisam visitar pacientes dentro de prazos críticos. A dificuldade reside em tomar a próxima decisão instantaneamente, sem saber exatamente quanto tempo a tarefa atual levará, e sem o luxo de um supercomputador para recalcular todo o plano a cada segundo.

Por anos, pesquisadores tentaram resolver isso ensinando computadores a evoluir regras de decisão simples. Essas regras agem como um controlador de tráfego, observando a situação atual e decidindo imediatamente qual cliente visitar a seguir. O método mais bem-sucedido até agora, conhecido como NS-GP, baseia-se em um conjunto fixo de onze características básicas — como a distância até um cliente ou quanto tempo resta — para fazer essas escolhas. Embora eficaz, essa abordagem tem um teto. Ela utiliza um vocabulário limitado para descrever o mundo, muito parecido com tentar escrever um romance usando apenas cem palavras. Os pesquisadores por trás deste novo estudo, liderados por Augusto Mendonça e sua equipe de universidades do Brasil, fizeram uma pergunta ousada: e se o computador pudesse aprender um vocabulário mais rico ao observar como um planejador especialista resolve o problema offline? Eles queriam ver se poderiam extrair a lógica oculta de soluções de alta qualidade e transformar esses insights em regras simples e legíveis que funcionem em tempo real.

A equipe desenvolveu um novo método chamado SI-GP, que significa Programação Genética Informada pelo Solucionador (Solver-Informed Genetic Programming). O processo começa não com o computador adivinhando, mas com o computador observando. Primeiro, os pesquisadores usaram solucionadores poderosos e de alta velocidade para encontrar as melhores rotas possíveis para um conjunto de quarenta problemas de teste diferentes, assumindo que tudo ocorreria perfeitamente. Eles então reproduziram essas rotas perfeitas em um mundo simulado onde atrasos aconteciam aleatoriamente, tal como ocorre na realidade. Ao comparar os planos perfeitos com o que realmente aconteceu, a equipe identificou operações específicas que os planos perfeitos realizavam, mas que as regras padrão perdiam. Por exemplo, eles notaram que os melhores planos frequentemente olhavam várias etapas à frente para ver quais recompensas ainda seriam alcançáveis, ou calculavam o risco de perder uma oportunidade futura se se comprometessem com uma decisão atual.

A partir dessas observações, os pesquisadores construíram uma nova biblioteca de dezoito características de decisão. Dezesseis delas foram baseadas em conceitos estabelecidos de escalonamento, enquanto duas eram combinações inteiramente novas projetadas para pesar o custo de uma decisão contra o ganho potencial. Este novo vocabulário deu ao computador uma maneira muito mais matizada de entender o problema. No entanto, ter mais opções não significa automaticamente melhores resultados; às vezes, ter muitas escolhas confunde o sistema. Para resolver isso, a equipe utilizou uma segunda camada de inteligência para selecionar o melhor subconjunto dessas características para cada problema específico. Eles trataram o processo de seleção como um torneio, evoluindo diferentes combinações de características e testando-as rigorosamente. Isso foi possível graças a um motor customizado que roda em placas de vídeo, permitindo que testassem milhares de combinações no tempo que antes era usado para testar apenas uma.

Os resultados foram impressionantes. Nos quarenta problemas de referência, o novo método nunca teve um desempenho inferior ao padrão antigo. Em trinta e oito dos casos, o sistema evoluiu uma nova regra que superou o melhor anterior. Em média, as novas regras melhoraram a recompensa total coletada em 1,0% em todos os testes, e em 1,3% nos problemas onde ainda havia espaço para melhoria. Em dez casos específicos, a melhoria foi estatisticamente significativa e grande o suficiente para ser considerada um grande avanço para aquele cenário específico. Talvez o mais importante seja que as novas regras permaneceram simples e legíveis. Elas não eram algoritmos de "caixa-preta" que ninguém conseguia entender; eram expressões matemáticas compactas que um humano poderia ler e verificar. Em muitos casos, as novas regras também foram mais estáveis, produzindo resultados consistentes mesmo quando os atrasos aleatórios variavam, enquanto as regras antigas às vezes oscilavam drasticamente entre bons e ruins resultados.

O estudo também revelou por que as melhorias aconteceram. As novas regras foram particularmente eficazes em situações onde o sistema de base tinha dificuldade em visitar todos os clientes possíveis. Nestes cenários "insaturados", o novo vocabulário permitiu que o sistema navegasse por trocas complexas, como visitar um cliente distante de alto valor mesmo que isso significasse pular um cliente próximo de baixo valor. Os pesquisadores descobriram que as novas características ajudaram o sistema a regularizar sua busca, significando que era menos provável que ficasse preso em uma armadilha local e mais provável que encontrasse um caminho robusto à frente. O método funcionou ao aprender com a estrutura de soluções de alta qualidade sem simplesmente copiá-las. Ele não tentou imitar a rota exata do planejador especialista; em vez disso, aprendeu os princípios que tornavam aquelas rotas bem-sucedidas e os aplicou a um novo ambiente incerto.

Este trabalho demonstra que é possível preencher a lacuna entre a otimização complexa offline e a tomada de decisão rápida online. Ao usar os insights de solucionadores de alta qualidade para construir um vocabulário melhor, e então selecionar cuidadosamente as ferramentas certas para cada tarefa específica, os pesquisadores criaram um sistema que é ao mesmo tempo poderoso e transparente. O produto final é um conjunto de regras de decisão que podem ser incorporadas diretamente em veículos ou drones, permitindo que tomem decisões inteligentes em microssegundos sem a necessidade de se conectar a um computador central ou executar simulações complexas. A abordagem sugere um novo caminho para a inteligência artificial na logística: um que valoriza a interpretabilidade e a adaptabilidade, garantindo que as máquinas que tomam decisões críticas possam ser compreendidas pelos humanos que dependem delas. Os pesquisadores disponibilizaram seu código, dados e as regras específicas que descobriram para o público, convidando outros a construir sobre esta base para desafios futuros em ambientes incertos.