Um algoritmo híbrido baseado em colônia de formigas e programação linear aplicado ao problema de roteamento de veículos capacitados
Nenhuma Miniatura disponível
Data
2017-08-10
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Centro Federal de Educação Tecnológica de Minas Gerais
Resumo
Neste trabalho é abordado o Problema de Roteamento de Veículos Capacitados. Ele compreende a obtenção de um conjunto de rotas, que devem ser percorridas por uma frota de veículos homogêneos e de igual capacidade, atendendo assim as demandas de um conjunto de clientes. Seu objetivo é a minimização do custo total das rotas, sabendo-se que elas devem iniciar e terminar no depósito central, além de cada cliente somente pode ser atendido uma única vez por um único veículo. Este problema possui natureza NP-difícil, sendo comumente resolvido por meio de heurísticas. Outra técnica utilizada é a programação linear inteira, cuja particularidade corresponde a confiança na solução obtida, uma vez que por meio da solução final retornada pode-se provar que é o ótimo global. Como desvantagem, os problemas de natureza combinatória são, na maioria dos casos, computacionalmente custosos, tornando improvável encontrar uma solução ótima em tempo computacional aceitável. A proposta deste trabalho é desenvolver um algoritmo híbrido que combine a natureza ágil das heurísticas com a precisão dos métodos de solução por Programação Linear. A heurística utilizada foi a Otimização por Colônia de Formigas (ACO), a qual irá trabalhar de forma híbrida com o CPLEX, software distribuído pela IBM. Estuda-se a melhor forma de interação entre estes dois métodos, analisando os seus possíveis modos de comunicação. Estes compreendem duas diferentes formas de hibridização, uma caracterizada pela ausência do processo de realimentação, e a outra fazendo uso deste recurso. Os resultados obtidos pelas hibridizações foram comparados com os produzidos pelos métodos executados individualmente, bem como com as soluções presentes na literatura.
Descrição
Palavras-chave
Sistemas multiagentes, Processamento de dados, Programação linear, Algoritmos