Algoritmos Meméticos para avaliação de cenários pós-desastre

Vol 57, 2025 - 340972
Pôster
Favoritar este trabalho
Como citar esse trabalho?
Resumo

Desastres naturais frequentemente provocam danos severos às redes de transporte, o que impõe desafios críticos à logística humanitária, especialmente na avaliação rápida e precisa das necessidades da população em áreas afetadas. A coleta de informações é vital para priorizar esforços de socorro e evitar o desperdício de recursos. Para mitigar esse problema, este trabalho foca no Combined Drone Orienteering Problem (CDOP), um problema NP-Difícil que coordena o uso conjunto de drones e caminhões para maximizar a coleta de informações sob restrições severas de tempo e autonomia de bateria. No CDOP, o caminhão atua como uma base móvel, permitindo que o drone visite locais de abrigo, como comunidades, escolas ou hospitais, que se tornaram inacessíveis ou perigosos para veículos terrestres devido a bloqueios e danos na malha viária.
Propõe-se um Algoritmo Memético organizado em uma estrutura de árvore ternária com 13 agentes. Cada agente mantém um par de soluções: a Current, focada na exploração do espaço de busca, e a Pocket, um mecanismo de memória que preserva a melhor solução individual encontrada, garantindo que o líder de cada subpopulação seja sempre superior aos seus filhos. O método integra um algoritmo genético com conhecimento específico do domínio através do procedimento de otimização, que combina uma etapa de ’Educação’ das rotas com algoritmos de Busca Local baseados em inserção. O Warm Start utiliza heurísticas de inserção mais barata (cheapest insertion) para o caminhão e maximização de lucro incremental para o drone, permitindo iniciar o processo evolutivo a partir de soluções de maior qualidade. O processo de educação garante a viabilidade das rotas ao remover sistematicamente nós que violam as restrições operacionais. Já a Busca Local refina as soluções visando o aumento do lucro total respeitando estritamente os limites de tempo.
Para validar a proposta, foram utilizados dois conjuntos de instâncias. O primeiro segue padrões da literatura, enquanto o segundo é uma contribuição original, desenhada para mimetizar a topologia urbana real e os danos causados por desastres. Os resultados experimentais demonstram que a integração da busca local e do operador de cruzamento MMX, baseado na troca de substrings, superam consistentemente variantes baseadas em preservação de ordem relativa (MPX). A abordagem proposta atingiu soluções de alta qualidade com rápida convergência, mostrando-se ideal para apoiar a tomada de decisão crítica em cenários reais.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Universidade Federal de São Carlos
  • 2 University of Newcastle Australia
  • 3 Cerebral Diagnostics (Canada)
  • 4 Universidade Estadual de Campinas (UNICAMP)
Eixo Temático
  • MH – Meta-heurísticas
Palavras-chave
Logística Humanitária
Algoritmo Memético
Drone