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]