Algoritmos evolutivos eficientes para um problema de roteamento de veículo

Abstract

Este trabalho apresenta propostas que visam melhorar o desempenho de algoritmos evolutivos (AEs). Os AEs e em particular, os algoritmos genéticos (AGs), apesar de muito conhecidos, não têm alcançado resultados competitivos com suas versões básicas (AGB) na solução de diferentes problemas de otimização. Diferentes variações dos AGBs têm sido propostas na literatura, com o intuito de tentar reduzir algumas das limitações presentes nestes algoritmos, tais como: dificuldade em efetuar uma busca local de forma eficiente; e a exigência de um tempo computacional maior do que o exigido por outras metaheurísticas. Neste trabalho, propomos alternativas para melhorar o desempenho destes AGBs, que aborda: a substituição dos operadores básicos de reprodução por heurísticas no algoritmo chamado de AG; a inclusão no AG de módulos de busca local que chamaremos AG+BL; e finalmente a inclusão neste último algoritmo de módulos de Mineração de Dados que chamaremos de AG+BL+MD. Numa segunda etapa, passaremos a analisar o problema da redução dos tempos computacionais exigidos por um AG. Procuramos adequar as versões aqui propostas a um Problema de Roteamento de Veículos (PRV), onde buscamos encontrar um percurso otimizado para uma unidade móvel de pistoneio (UMP), de modo a maximizar a extração do petróleo dos poços terrestres não surgentes, respeitando as restrições do problema. Resultados computacionais mostram o bom desempenho dos algoritmos propostos neste trabalho, e em particular, a da versão com mineração de dados