Martins, Flávio Vinicius CruzeiroPapa, Larissa Camila2025-05-202017-08-10https://repositorio.cefetmg.br//handle/123456789/1541Neste 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.ptDissertação2025-05-20Sistemas multiagentesProcessamento de dadosProgramação linearAlgoritmos