Programa de Pós Graduação em Modelagem Matemática e Computacional - PPGMMC

URI Permanente desta comunidade

https://repositorio.cefetmg.br//handle/123456789/646

Navegar

Navegando Programa de Pós Graduação em Modelagem Matemática e Computacional - PPGMMC por Autor "Alexandre, Rafael Frederico"

Agora exibindo 1 - 1 de 1
  • Imagem de Miniatura
    Item
    Um algoritmo híbrido baseado em colônia de formigas e programação linear aplicado ao problema de roteamento de veículos capacitados
    (Centro Federal de Educação Tecnológica de Minas Gerais, 2017-08-10) Papa, Larissa Camila; Martins, Flávio Vinicius Cruzeiro; Cardoso, Rodrigo Tomás Nogueira; http://lattes.cnpq.br/5174842920583671; http://lattes.cnpq.br/3199420233273400; http://lattes.cnpq.br/8327916913062595; Martins, Flávio Vinicius Cruzeiro; Cardoso, Rodrigo Tomás Nogueira; Alexandre, Rafael Frederico; Santos, Vinicius Fernandes dos; Sarubbi, João Fernandes Machry
    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.