Um algoritmo híbrido baseado em colônia de formigas e programação linear aplicado ao problema de roteamento de veículos capacitados

Página do item simplificado
dc.contributor.advisorMartins, Flávio Vinicius Cruzeiro
dc.contributor.advisor-coCardoso, Rodrigo Tomás Nogueira
dc.contributor.advisor-coLatteshttp://lattes.cnpq.br/5174842920583671
dc.contributor.advisorLatteshttp://lattes.cnpq.br/3199420233273400
dc.contributor.authorPapa, Larissa Camila
dc.contributor.authorLatteshttp://lattes.cnpq.br/8327916913062595
dc.contributor.refereeMartins, Flávio Vinicius Cruzeiro
dc.contributor.refereeCardoso, Rodrigo Tomás Nogueira
dc.contributor.refereeAlexandre, Rafael Frederico
dc.contributor.refereeSantos, Vinicius Fernandes dos
dc.contributor.refereeSarubbi, João Fernandes Machry
dc.date.accessioned2025-05-20T19:13:59Z
dc.date.available2025-05-20T19:13:59Z
dc.date.issued2017-08-10
dc.description.abstractNeste 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.
dc.description.abstractotherIn this work the Capacitated Vehicle Routing Problem is approached. It comprises obtaining a set of routes, which must be covered by a fleet of homogeneous vehicles of the same capacity, thus meeting the demands of a group of customers. Their goal is to minimize the total cost of the routes, knowing that they must start and end in the central warehouse, and each customer can only be serviced once by a single vehicle. This problem is NP-difficult in nature and is commonly solved by means of heuristics. Another technique used is the integer linear programming, whose particularity corresponds to the confidence in the obtained solution, since by means of the returned final solution it is possible to prove this is the global optimum. As a disadvantage, combinatorial problems are computationally costly, making it unlikely to find an optimal solution at acceptable computational time. The purpose of this work is to develop a hybrid algorithm that combines the agile nature of heuristics with the precision of the solution methods by Linear Programming. The heuristic used was the Ant Colony Optimization (ACO), which will work in a hybrid way with CPLEX, software distributed by IBM. The best way of interacting between these two methods is analyzed, analyzing their possible modes of communication. These comprise two different forms of hybridization, one characterized by the absence of the feedback process, and the other making use of this feature. The results obtained by the hybridizations were compared with those produced by the methods performed individually, as well as with the solutions present in the literature.
dc.identifier.urihttps://repositorio.cefetmg.br//handle/123456789/1541
dc.language.isopt
dc.publisherCentro Federal de Educação Tecnológica de Minas Gerais
dc.publisher.countryBrasil
dc.publisher.initialsCEFET-MG
dc.publisher.programPrograma de Pós-Graduação em Modelagem Matemática e Computacional
dc.subjectSistemas multiagentes
dc.subjectProcessamento de dados
dc.subjectProgramação linear
dc.subjectAlgoritmos
dc.titleUm algoritmo híbrido baseado em colônia de formigas e programação linear aplicado ao problema de roteamento de veículos capacitados
dc.typeDissertação

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Um algoritmo híbrido baseado em colônia de formigas e programação linear aplicado ao problema de roteamento de veículos capacitados.pdf
Tamanho:
2.78 MB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.39 KB
Formato:
Item-specific license agreed to upon submission
Descrição:
Baixar

Coleções

Mestrado em Modelagem Matemática e Computacional