Economia

Uma Heuristica GRASP com Reconexão por Caminhos para o Problema de Árvore de Steiner Euclidiana Tridimensional

Marcelo Lisboa Rocha
Curso de Ciência da Computação - Universidade Federal do Tocantins
Av. NS 15, S/N – ALCNO 14 - Bloco 02 – Sala 21, CEP: 77020-210, Palmas - TO [e-mail] Amit Bhaya
Programa de Engenharia Elétrica, Universidade Federal do Rio de Janeiro, COPPE/UFRJ
Caixa Postal 685-4. CEP: 21945-970. Rio de Janeiro, RJ - Brasil [e-mail] Flávio M. T. Montenegro
Instituto Brasileiro de Geografia e Estatística – COMEQ/DPE/IBGE
Av. República do Chile, 500, 10º andar, Rio de Janeiro, RJ – Brasil, CEP 20031-170 [e-mail] Nelson Maculan
Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro, UFRJ
CEP: 21941-972, Rio de Janeiro, RJ – Brasil [e-mail] RESUMO

Dado um conjunto de pontos no espaço 3D com métrica Euclideana, o Problema de Árvore de Steiner Tridimensional consiste em encontrar uma árvore de comprimento mínimo que conecta estes pontos usando, se necessário, pontos extras (pontos de Steiner). A obtenção de tal solução é um problema NP-difícil. O presente trabalho apresenta uma heurística híbrida baseada em GRASP e reconexão por caminhos para o problema em questão. Ao final, um experimento computacional compara o desempenho da heurística proposta com trabalhos anteriores da literatura.
PALAVARAS CHAVE. Árvore de Steiner Euclideano Tridimensional, GRASP, Reconexão por Caminhos.
Área Principal: Metaheurísticas.

ABSTRACT

Given a fixed set of points in a 3D space with Euclidean metric, the Tridimensional Euclidean Steiner Tree Problem consists of finding a minimum length tree that spans all these points using, if necessary, extra points (Steiner points). The finding of such solution is a NP-hard problem. This paper presents a hybrid heuristic based on GRASP and path relinking to the problem considered. Finally, a