Publicação: Avaliação de desempenho do algoritmo de Clarke-Wright para a construção de rotas e de seu aprimoramento utilizando busca local
Carregando...
Tipo do documento
Data
Direito de acesso
Programa
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Título da Revista
ISSN da Revista
Título de Volume
Orientador
Coorientador
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
Citação
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.
DOI
Avaliação
Revisão
Suplementado Por
Referenciado Por
Licença Creative Commons
Exceto quando indicado de outra forma, a licença deste item é descrita como Acesso Aberto