Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/37399| Título: | Otimização de rotas interestelares: simulação e comparação de algoritmos |
| Título(s) alternativo(s): | Interstellar routes optimization: simulation and comparison of algorithms |
| Autor(es): | Getaruck, Yuri Constantino |
| Orientador(es): | Godoi, Muriel de Souza |
| Palavras-chave: | Caixeiros-viajantes Heurística Otimização combinatória Traveling sales personnel Heuristic Combinatorial optimization |
| Data do documento: | 12-Fev-2025 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Apucarana |
| Citação: | GETARUCK, Pedro Mian. Otimização de rotas interestelares: simulação e comparação de algoritmos. 2025. Trabalho de Conclusão de Curso (Engenharia de Computação) – Universidade Tecnológica Federal do Paraná, Apucarana, 2025. |
| Resumo: | Problemas de otimização são fundamentais em diversas áreas, especialmente na busca por soluções eficientes para tarefas complexas. Neste trabalho, abordou-se o problema Star Tours, uma variação do problema do caixeiro viajante, cujo o objetivo é encontrar o caminho mais curto para visitar um conjunto de estrelas no cosmos. Com o aumento do número de estrelas, o problema se torna exponencialmente mais complexo, exigindo estratégias eficientes para sua resolução. Neste estudo, comparou-se o desempenho de quatro algoritmos de otimização: vizinho mais próximo, procedimento de busca adaptativa randomizada gananciosa, genético e colônia de formigas, aplicados a conjuntos de dados de diferentes escalas, contendo 100, 1.000, 10.000, 37.859 e 109.399 estrelas. Para facilitar a análise e a experimentação, desenvolveu-se um simulador com interface gráfica que permite a definição de hiperparâmetros, a execução dos algoritmos e a visualização da melhor rota retornada. Foram analisadas métricas como número de iterações, taxa de melhoria por iteração, taxa de convergência, tempo de execução e proximidade do caminho ótimo. Os resultados demonstraram que, para todas as instâncias, o algoritmo busca adaptativa apresentou o melhor desempenho, sendo consistentemente superior aos demais. Para as instâncias menores (100 e 1.000 estrelas), os algoritmos genético e colônia de formigas também obtiveram resultados satisfatórios, entretanto, com o aumento do tamanho do conjunto de dados, seu desempenho decaiu, ficando atrás até mesmo do algoritmo de vizinho mais próximo que, embora seja o mais simples, mostrou-se mais eficaz em cenários de maior complexidade. Concluiu-se que o algoritmo de busca adaptativa randomizada gananciosa é a estratégia mais adequada para resolver instâncias do problema Star Tours em diferentes escalas, enquanto o algoritmo de vizinho mais próximo pode ser uma alternativa viável para instâncias maiores, devido à sua simplicidade e eficiência relativa. |
| Abstract: | Optimization problems are fundamental in various fields, particularly in the search for efficient solutions to complex tasks. This study addresses the Star Tours problem, a variation of the traveling salesman problem, which aims to find the shortest path to visit a set of stars in the cosmos. As the number of stars increases, the problem becomes exponentially more complex, requiring efficient strategies for its resolution. In this research, the performance of four optimization algorithms was compared: nearest neighbor, greedy randomized adaptive search procedure, genetic algorithm, and ant colony optimization, applied to datasets of varying scales containing 100, 1,000, 10,000, 37,859, and 109,399 stars. To facilitate analysis and experimentation, a simulator with a graphical interface was developed, allowing the definition of hyperparameters, execution of the algorithms, and visualization of the best route returned. Metrics such as the number of iterations, improvement rate per iteration, convergence rate, execution time, and proximity to the optimal path were analyzed. The results showed that, for all instances, the adaptive search algorithm performed the best, consistently outperforming the others. For smaller instances (100 and 1,000 stars), the genetic and ant colony algorithms also achieved satisfactory results; however, as the dataset size increased, their performance declined, falling behind even the nearest neighbor algorithm, which, despite being the simplest, proved more effective in more complex scenarios. It was concluded that the greedy randomized adaptive search procedure is the most suitable strategy for solving Star Tours problem instances at different scales, while the nearest neighbor algorithm can be a viable alternative for larger instances due to its simplicity and relative efficiency |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/37399 |
| Aparece nas coleções: | AP - Engenharia de Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| otimizacaorotas.pdf | 4,01 MB | Adobe PDF |  Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons
