[pt] Seja G= (V, E) um grafo não-orientado com custos não- negativos em suas arestas e D um conjunto de pares origem - destino. Um 2-caminho entre nós (s,t)é um caminho de s a t formado por , no máximo, 2 arestas. O problema de síntese de redes com 2-caminhos (2PNDP) consiste em encontrar um subconjunto de arestas com custo mínimo que contenha um 2- caminho entre as extremidades dea cada para origem- destino pertencente a D. Apicações deste problema encontram-se no projeto de redes de comunicação, onde caminhos com poucas arestas são desejáveis para garantir alta confiabilidade e pequenos atrasos. A metaheurística GRASP é um processo multipartida para resolver problemas combinatórios, cujas iterações consistem de duas fases, uma fase de construção e outra de busca local. O algoritmo retorna a melhor solução encontrada depois de um número determinado de iterações.Aplica-se a técnica de reconexão por caminhos ao final de cada iteração GRASP para melhorar a qualidade das soluções. Implementações paralelas de metaheurística são muito robustas. A maior parte das implementações paralelas da metaheurística GRASP segue uma estratégia do tipo independente , baseada na distribuição balanceada das iterações pelos processadores. No caso de estratégias colaboradtivas, os processadores trocam e compartilham informações coletadas ao longo da trajetória que cada um deles investiga. Neta tese são desenvolvidas heurísticas seqüenciais e paralelas para 2PNDP. São analisadas variantes e combinações de GRASP e reconexão por caminhos , comparando-se os resultados obtidos pelos algoritmos descritos na literatura. Heurísticas GRASP paralelas com reconexão por caminhos são avaliadas e comparadas para verificar qual o papel que a colaboração entre os processadores desempenha na qualidade das soluções e nos tempos de processamento. Procura-se também estudar a melhor maneira de desenvolver implementações paralelas , para se utilizar da melhor forma possível os recursos computacionais e reduzir conflitos de memória e comunicação. / [en] Let G = ( V, E) be a connected undirected graph , where V is the set of nodes and E denotes the set of edges. A 2- path between nodes (s,t)is a sequence of a most two edges connecting them. Given a non-negative weight function associated with edges of G and a set D of origin- destination pairs of nodes, the 2-path network design problem (2PNDP) consists in finding a minimum weighted subset of edges containing a 2-path between the extremities of every origin-destination pair in D. Applications can be found in the design of communication networks , in which paths with few edges are sought to enforce high reliability and small delays. The GRASP metaheuristic is a multistart process , in which each iteration consists of two phases : construction and local search. The best solution found after a fixed number of iterations is returned. Path- relinking is applied as an attempt to improve the solutions found at the of each GRASP iteration. Parallel implementations of metaheuistics ara very robust. Typical parallelizations of GRASP correspond to multiple-walk independent-thread strategies, based on the balanced distribuiton of the iterations over the processors. In the case of multiple-walk cooperative-thread strategies, the processors exchange and share information collected along the trajectories that they investigate. In this thesis, sequential and parallel heuristics are developed for 2PNDP. Variants and combinations of GRASP with path-relinking are analysed by comparing the results of the proposed algorithms with those obtained by others algoritms described in the literature. Parallel GRASP with pathrelinking heuristcs are compared to investigate the influence of the cooperation among processors in terms of solution quality and processing time. We also explore different strategies to optimize the parallel implementations, to make better use of the computational resources and to reduce communication and memory conflicts.