Aplicação de Algoritmo Evolucionário Populacional ao Problema de Fluxo Multiproduto Inteiro

Abstract

O objetivo deste trabalho é analisar o comportamento de um algoritmo evolucionário populacional aplicado à solução do Problema de Fluxo Multiproduto Inteiro (PFMI). Este problema pertence à classe de problemas NP-difíceis, tendo forte aplicação de cunho econômico. O uso de técnicas heurísticas é justificada pela elevada dimensão do problema em relação à quantidade de variáveis e restrições. Assim, mesmo sem garantir otimalidade, técnicas heurísticas (locais e populacionais) podem conseguir boas soluções e em menor tempo computacional, quando comparadas a algoritmos exatos. Neste trabalho, é proposta uma abordagem do problema via algoritmos genéticos, associado a uma heurística de busca local, para resolver o PFMI capacitado. Busca-se determinar o fluxo dos produtos pelos arcos da rede ao menor custo possível, respeitando-se as restrições de conservação de fluxo e de capacidade. São desenvolvidas heurísticas aplicadas aos indivíduos da população inicial, em particular utilizando-se o Método da Descida Randômica. Para verificar a eficiência do algoritmo proposto, foram feitos testes computacionais com instâncias de teste da literatura. Os resultados obtidos pelo método proposto foram comparados a resultados obtidos por métodos exatos. Em especial, para uma das instâncias foi encontrada uma solução factível, fato não atingido pelo método exato utilizado na comparação.