Please use this identifier to cite or link to this item:
https://repositorio.ufu.br/handle/123456789/38564| ORCID: |  http://orcid.org/0009-0001-6960-1694 |
| Document type: | Trabalho de Conclusão de Curso |
| Access type: | Acesso Aberto |
| Title: | Avaliação de desempenho do algoritmo de Clarke-Wright para a construção de rotas e de seu aprimoramento utilizando busca local |
| Alternate title (s): | Performance evaluation of the Clarke-Wright algorithm for route construction and its improvement using local search |
| Author: | Santos, Gabriel Dal Belo Gomes |
| First Advisor: | Gabriel, Paulo Henrique Ribeiro |
| First member of the Committee: | Brasil, Christiane Regina Soares |
| Second member of the Committee: | Melo, Wendel Alexandre Xavier de |
| Summary: | 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. |
| Keywords: | Roteamento de veículos Algoritmo de Clarke-Wright Heurística Heuristics Busca local Local search Vehicle routing Clarke-Wright algorithm |
| Area (s) of CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Language: | por |
| Country: | Brasil |
| Publisher: | Universidade Federal de Uberlândia |
| Quote: | 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 |
| Date of defense: | 21-Jun-2023 |
| Appears in Collections: | TCC - Sistemas de Informação (Uberlândia) |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| AvaliaçãoDesempenhoAlgoritmo.pdf | TCC | 2.44 MB | Adobe PDF |  View/Open |
This item is licensed under a Creative Commons License
