| dc.contributor.advisor | Martinotto, André Luis | |
| dc.contributor.author | Graeff, César Augusto | |
| dc.contributor.other | Dorneles, Ricardo Vargas | |
| dc.contributor.other | Ribeiro, Helena Graziottin | |
| dc.date.accessioned | 2022-03-21T17:34:07Z | |
| dc.date.available | 2022-03-21T17:34:07Z | |
| dc.date.issued | 2020-12-24 | |
| dc.date.submitted | 2020-12-16 | |
| dc.identifier.uri | https://repositorio.ucs.br/11338/9707 | |
| dc.description | Este trabalho tem por principal objetivo o estudo de heurísticas para a solução do Problema do Caixeiro Viajante, em especial para a resolução do Problema do Caixeiro Viajante com Janelas de Tempo. O problema do Caixeiro Viajante possui complexidade NP-Difícil, sendo inviável a utilização de força bruta para a solução de grafos que apresentam um grande número de vértices. Deste modo, são utilizadas heurísticas que procuram reduzir significativamente o tempo de execução, porém não garantindo a solução ótima para o problema. Para o desenvolvimento deste trabalho optou-se pela utilização da heurística GENIUS. A implementação foi desenvolvida utilizando a linguagem de programação C e a biblioteca de threads OpenMP, de forma a explorar o paralelismo em arquiteturas com múltiplos núcleos de processamento. Para os testes foi utilizado o pacote de grafos proposto por Dumas em 1995. Já para a avaliação do desempenho foram calculados o speedup e a eficiência do algoritmo implementado. Os resultados obtidos através deste trabalho apresentaram um speedup de até 2.48 e uma eficiência de até 62% ao utilizar 4 núcleos de processamento. [resumo fornecido pelo autor] | pt_BR |
| dc.language.iso | pt | pt_BR |
| dc.subject | Computação | pt_BR |
| dc.subject | Otimização combinatória | pt_BR |
| dc.subject | Programação heurística | pt_BR |
| dc.subject | Algorítmos genéticos | pt_BR |
| dc.title | Solução paralela para um sistema de roteirização utilizando o problema do caixeiro viajante | pt_BR |
| dc.type | Monografia | pt_BR |
| mtd2-br.advisor.instituation | Universidade de Caxias do Sul | pt_BR |
| mtd2-br.program.name | Bacharelado em Ciência da Computação | pt_BR |
| mtd2-br.campus | Campus Universitário de Caxias do Sul | pt_BR |
