Voip

XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento

12 a 15/09/06 Goiânia, GO

HEURÍSTICA GRASP APLICADO AO PROBLEMA DE ALOCAÇÃO DE
ANTENAS DE TRANSMISSÃO

José Elias Cláudio Arroyo
Universidade Candido Mendes, Campos – UCAM-Campos
Departamento de Computação e Sistemas
Rua Anita Peçanha, 100, Campos, RJ [e-mail] Tarcísio Barroso Marques
Universidade Candido Mendes, Campos – UCAM-Campos
Departamento de Computação e Sistemas
Rua Anita Peçanha, 100, Campos, RJ [e-mail] RESUMO
Este artigo aborda o problema de posicionamento de antenas de telecomunicações (por exemplo, antenas de transmissão de sinais de rádio-difusão, sinais de TV, Internet via rádio, etc) em pontos específicos de uma região (cidade). O objetivo é atender ou cobrir a maior quantidade de pontos de demanda usando um número mínimo de antenas. São consideradas restrições de alcance de transmissão e presença de obstáculos interferentes. Para resolver o problema é desenvolvida uma heurística GRASP (Greedy Randomized Adaptive Search Procedure) que usa um método guloso chamado ADD e uma estratégia de cruzamento de soluções para melhorar a qualidade das soluções obtidas pela fase da busca local. O bom desempenho da heurística desenvolvida é testado em problemas de grande porte gerados manualmente (cujas soluções são conhecidas) e aleatoriamente.
PALAVRAS CHAVE. Heurísticas, Localização de facilidades, GRASP, Metaheurísticas

ABSTRACT
This article approaches the positioning problem of telecommunication antennas in specific point of a city (e.g., transmission antennas of broadcasting signs, TV sings, Internet through radio, etc.). The goal is to attain the large amount of demanding points using a minimum number of antennas. We consider restrictions such as, transmission reach of the equipments and interfering obstacles. To solve the problem, we propose a GRASP (Greedy