Use este identificador para citar ou linkar para este item: https://repositorio.ufu.br/handle/123456789/38564
ORCID:  http://orcid.org/0009-0001-6960-1694
Tipo do documento: Trabalho de Conclusão de Curso
Tipo de acesso: Acesso Aberto
Título: Avaliação de desempenho do algoritmo de Clarke-Wright para a construção de rotas e de seu aprimoramento utilizando busca local
Título(s) alternativo(s): Performance evaluation of the Clarke-Wright algorithm for route construction and its improvement using local search
Autor(es): Santos, Gabriel Dal Belo Gomes
Primeiro orientador: Gabriel, Paulo Henrique Ribeiro
Primeiro membro da banca: Brasil, Christiane Regina Soares
Segundo membro da banca: Melo, Wendel Alexandre Xavier de
Resumo: O Problema de Roteamento de Veículos (PRV) representa, ainda nos dias atuais, um grande desafio devido à sua complexidade computacional. Não há um método eficiente capaz de resolver todos os possíveis casos, que variam desde pequenas instâncias até instâncias enormes contendo dezenas de milhares de pontos a serem considerados. Neste trabalho, retrocedemos um pouco no tempo ao analisar e comparar em termos de eficiência e desempenho duas das primeiras soluções mais abrangentes para este problema, sendo a primeira o algoritmo de Clarke e Wright, proposto em 1964, e a aplicação do método 2-opt, proposto alguns anos antes em 1958, em cima do resultado gerado pelo algoritmo anterior. A aplicação desse método de melhoria em cima de uma heurística construtiva aprimora o resultado ainda mais e o aproxima da solução ótima a um baixo custo computacional. Ambos os algoritmos foram implementados manualmente utilizando a linguagem de programação Python, permitindo execuções nas quais podemos observar de maneira direta o custo das soluções resultantes.
Abstract: The Vehicle Routing Problem (VRP) still represents a significant challenge in modern days due to its computational complexity. There is no efficient method capable of solving all possible cases, which range from small instances to massive instances containing tens of thousands of points to be considered. In this work, we take a step back in time to analyze and compare two of the earliest comprehensive solutions to this problem in terms of efficiency and performance. The first one is the Clarke and Wright algorithm proposed in 1964, and the second is the application of the 2-opt method, proposed a few years earlier in 1958, on the result generated by the previous algorithm. Applying this improvement method on top of a constructive heuristic further enhances the result. It brings it closer to the optimal solution at a low computational cost. Both algorithms were manually implemented using the Python programming language, enabling direct executions where we can directly observe the cost of the resulting solutions.
Palavras-chave: Roteamento de veículos
Algoritmo de Clarke-Wright
Heurística
Heuristics
Busca local
Local search
Vehicle routing
Clarke-Wright algorithm
Área(s) do CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Idioma: por
País: Brasil
Editora: Universidade Federal de Uberlândia
Referência: SANTOS, Gabriel Dal Belo Gomes. Avaliação de desempenho do algoritmo de Clarke-Wright para a construção de rotas e de seu aprimoramento utilizando busca local. 2023. 37 f. Trabalho de Conclusão de Curso (Graduação em Sistemas de Informação) – Universidade Federal de Uberlândia, Uberlândia, 2023.
URI: https://repositorio.ufu.br/handle/123456789/38564
Data de defesa: 21-Jun-2023
Aparece nas coleções:TCC - Sistemas de Informação (Uberlândia)

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
AvaliaçãoDesempenhoAlgoritmo.pdfTCC2.44 MBAdobe PDFThumbnail
Visualizar/Abrir


Este item está licenciada sob uma Licença Creative Commons Creative Commons