Metaheurísticas para o problema de roteamento de veículos capacitados: o algoritmo híbrido de otimização por colônia de formigas e a busca híbrida em grande vizinhança

Bernardes, Lucas Correia

Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/22214

Document type:	Trabalho de Conclusão de Curso
Access type:	Acesso Aberto
Title:	Metaheurísticas para o problema de roteamento de veículos capacitados: o algoritmo híbrido de otimização por colônia de formigas e a busca híbrida em grande vizinhança
Alternate title (s):	Metaheuristics for the capacitated vehicle routing problem: the hybrid ant colony optimization and hybrid large neighborhood search
Author:	Bernardes, Lucas Correia
First Advisor:	Soares, Alexsandro Santos
First member of the Committee:	Fernandes, Márcia Aparecida
Second member of the Committee:	Melo, Wendel Alexandre Xavier de
Summary:	Este trabalho apresenta a comparação de duas técnicas de metaheurísticas para o Problema de Roteamento de Veículos Capacitados (PRVC) - o Algoritmo Híbrido de Otimização por Colônia de Formigas (AHOCF) e a Busca Híbrida em Grande Vizinhança (BHGV). Além disso, é mostrada uma visão geral das técnicas mais recentes e das variações mais utilizadas do problema. Será descrita a implementação dos métodos na linguagem de programação Clojure, e a performance dos algoritmos será testada em um conjunto das instâncias mais utilizadas do repositório CVRPlib. Os resultados obtidos serão então contrastados com os resultados apresentados pelos autores e entre si, para, por fim, verificar que o método AHOCF obteve um desempenho superior nos resultados, em comparação com os alcançados pela BHGV.
Abstract:	This paper presents a comparison between two metaheuristics techniques to the Capacitated Vehicle Routing Problem (CVRP) - the Hybrid Ant Colony Optimization (HACO) and Hybrid Large Neighborhood Search (HLNS). Futhermore, an overview of the most recent techniques and most used problem variants is shown. The implementation of both methods using the Clojure programming language is described, and the algorithms performance tested against the most used set of instances from the CVRPlib repository. The results obtained are then contrasted with the results presented by the authors and with each other, to finally verify that the HACO metaheuristic obtained a superior performance in the results, in comparison with those achieved by the HLNS.
Notes:	Contém códigos fontes no apêndice e também em https://github.com/lucascb/hybrid-lns e https://github.com/lucascb/hybrid_aco
Keywords:	Problema de Roteamento de Veículos Capacitados Metaheurística Problema de Otimização Busca em Grande Vizinhança Otimização por Colônia de Formigas Recozimento Simulado Capacitated Vehicle Routing Problem Metaheuristics Optimization Problems Large Neighborhood Search Ant Colony Optimization Simulated Annealing
Area (s) of CNPq:	CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Language:	por
Country:	Brasil
Publisher:	Universidade Federal de Uberlândia
Quote:	BERNARDES, Lucas Correa. Metaheurísticas para o problema de roteamento de veículos capacitados: o algoritmo híbrido de otimização por colônia de formigas e a busca híbrida em grande vizinhança. 2018. 127f. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação) - Universidade Federal de Uberlândia, Uberlândia, 2018.
URI:	https://repositorio.ufu.br/handle/123456789/22214
Date of defense:	13-Jul-2018
Appears in Collections:	TCC - Sistemas de Informação (Uberlândia)

Files in This Item:

File	Description	Size	Format
MetaheuristicasProblemaRoteamento.pdf		1.26 MB	Adobe PDF	View/Open

Show full item record