[pt] ESTRATÉGIAS SEQÜENCIAIS  E PARALELAS  DE GRASP  COM RECONEXÃO  POR CAMINHOS  PARA O PROBLEMA  DE SÍNTESE  DE REDES  A  2-CAMINHOS

ISABEL CRISTINA MELLO ROSSETI

[en] SEQUENTIAL AND PARALLEL STRATEGIES OF GRASP WITH PATH-RELINKING FOR THE 2-PATH NETWORK DESIGN PROBLEM

dc.contributor	CELSO DA CRUZ CARNEIRO RIBEIRO
dc.contributor	CELSO DA CRUZ CARNEIRO RIBEIRO
dc.creator	ISABEL CRISTINA MELLO ROSSETI
dc.date	2004-01-09
dc.date.accessioned	2022-09-21T21:42:12Z
dc.date.available	2022-09-21T21:42:12Z
dc.identifier	https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=4365@1
dc.identifier	https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=4365@2
dc.identifier	http://doi.org/10.17771/PUCRio.acad.4365
dc.identifier.uri	https://hdl.handle.net/20.500.12032/42465
dc.description	[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.
dc.description	[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.
dc.language	pt
dc.publisher	MAXWELL
dc.subject	[pt] GRASP
dc.subject	[pt] SINTESE DE REDES A 2-CAMINHOS
dc.subject	[pt] RECONEXAO POR CAMINHOS
dc.subject	[pt] PARALELISMO
dc.subject	[pt] METAHEURISTICAS
dc.subject	[en] GRASP
dc.subject	[en] 2-PATH NETWORK DESIGN PROBLEM
dc.subject	[en] PARALLELISM
dc.subject	[en] METAHEURISTICS
dc.title	[pt] ESTRATÉGIAS SEQÜENCIAIS E PARALELAS DE GRASP COM RECONEXÃO POR CAMINHOS PARA O PROBLEMA DE SÍNTESE DE REDES A 2-CAMINHOS
dc.title	[en] SEQUENTIAL AND PARALLEL STRATEGIES OF GRASP WITH PATH-RELINKING FOR THE 2-PATH NETWORK DESIGN PROBLEM
dc.type	TEXTO

Files in this item

Files	Size	Format	View
There are no files associated with this item.

This item appears in the following Collection(s)

Documentos - PUC-RIO

Show simple item record