HEURÍSTICAS PARA O PROBLEMA DE ALOCAÇÃO DE ANTENAS DE TRANSMISSÃO

1Tarcísio Barroso Marques, 2José Elias Claudio Arroyo, 3Dalessandro Soares Vianna

1,3Universidade Candido Mendes, Campos – UCAM-Campos

Departamento de Computação e Sistemas Rua Anita Peçanha, 100, Campos - RJ

tarcisiob@gmail.com, dalessandro@ucam-campos.br

2Universidade Federal de Viçosa – UFV Departamento de Informática

Av. P.H. Rolfs, s/n, Campus Universitário, Viçosa - MG jarroyo@dpi.ufv.br

RESUMO Este artigo aborda o problema de posicionamento de antenas de telecomunicações em locais específicos de uma região. O objetivo é atender a uma maior quantidade de pontos de demanda usando um número mínimo de antenas e minimizando a distancia dos pontos de demanda às antenas mais próximas. São consideradas restrições tais como, alcance de transmissão das antenas e obstáculos interferentes. Para resolver o problema foram desenvolvidos dois algoritmos baseados nas metaheurísticas GRASP e Algoritmo Genético. O objetivo deste trabalho é analisar o comportamento e desempenho de dois métodos diferentes na solução do problema abordado. O algoritmo GRASP usa uma adaptação da heurística gulosa Add na construção de soluções. Na fase da busca local são usadas diferentes estruturas de vizinhança e, além disso, as soluções obtidas são melhoradas fazendo o cruzamento com a melhor solução obtida até o momento. O Algoritmo Genético usa uma população de soluções iniciais geradas através de uma heurística construtiva gulosa-aleatorizada. O operador de cruzamento consiste na união de soluções seguida de uma técnica gulosa Drop que remove elementos enquanto é melhorado o valor da função objetivo. O desempenho das heurísticas propostas é testado em diversos problemas de médio e grande porte. Os resultados computacionais mostram que as heurísticas são capazes de gerar boas soluções aproximadas. Palavras chave: GRASP, Algoritmo genético, Problemas de localização de facilidades.

ABSTRACT This paper approaches the positioning problem of telecommunication antennas in specific points of an area. The goal is to reduce the large amount of demanding points using a minimum number of antennas, and minimizing the distances of the demand points to the closest antennas. We considered restrictions such as transmission range of the equipments and interfering obstacles. To solve the problem two algorithms based on the metaheuristics GRASP and Genetic Algorithm were developed. The objective of this work is to analyze the behavior and performance of two different methods in the solution of the approached problem. The algorithm GRASP uses an adaptation of the greedy heuristic ADD in the construction of solutions. In the local search phase, different neighborhood structures are used and besides the obtained solutions are improved making the crossing with the best solution obtained until the moment. The Genetic Algorithm uses the population of initial solutions created by a greedy constructive heuristic. The crossing of solutions is based on the union of solutions followed by a greedy DROP method that removes elements while it is improving the value of the function objective. The performance of developed heuristics is tested on medium and larger-sized problems. Computational results show that the heuristics are capable of yield good approximated solutions. Key-words: GRASP, Genetic algorithm, Locations facilities problems.

XXXIX SBPO [1566]

1. INTRODUÇÃO Problemas de localização de facilidades tratam de decisões sobre onde alocar ou instalar

facilidades, considerando clientes ou usuários que devem ser atendidos de forma a otimizar um ou mais critérios. O termo “facilidades” é utilizado para designar postos de saúde, depósitos, escolas, fábricas, antenas de telecomunicação etc., enquanto “clientes” refere-se a bairros, unidades de vendas, estudantes etc.

Na literatura, existem várias formulações ou modelos de problemas de localização (Drezner, 1995). A diferença entre estes problemas de localização está na maneira como as demandas e a localização das facilidades são representadas.

A distância cliente-facilidade é um diferencial importante entre os modelos de localização. Em alguns problemas de localização conhecidos como problemas de máxima distancia, por exemplo, uma distância máxima (distância de recobrimento) é dada a priori (Toregas et. al., 1971). Dentro deste contexto estão os problemas de recobrimento de conjuntos (set covering) (Lorena & Lopes, 1997), máxima cobertura (maximum covering) (Schilling et al., 1993; Galvão & Revelle, 1996; Galvão et al. 2000) e máximo recobrimento esperado (maximum expected covering) (Church & Revelle, 1974).

No contexto dos modelos de distância total ou média estão os problemas das p-medianas e os problemas de custo fixo (Hakimi, 1964, 1965; Schilling et al., 2000). O problema das p-medianas consiste em encontrar a localização de p facilidades em uma rede tal que o custo total (soma dos custos de atendimento dos clientes) seja minimizado.

A aplicação de métodos heurísticos para problemas de localização de facilidades, recentemente, tem recebido considerável atenção por muitos pesquisadores. Foram propostas heurísticas baseadas em: simulated annealing, algoritmos genéticos, busca tabu, GRASP, VNS (Variable Neighborhood Search) e relaxação lagrangeana (Murray & Church, 1996; Lorena e Lopes, 1997; Abdinnour-Helm, 1998; Chiyoshi & Galvão, 2000; Senne & Lorena, 2000; Alp et al. 2003; Lorena & Senne, 2003; Resende & Werneck, 2004; Crainic et al., 2004).

Na literatura, o problema de alocação de antenas tem sido abordado através do modelo das p-medianas na qual é fixado o número de antenas a serem instaladas e não são considerados obstáculos interferentes no raio de ação das antenas (Hoffmann & Gómez, 2003; Lorena, 2003).

Neste artigo são propostos dois algoritmos baseados nas metaheurísticas GRASP (Feo & Resende, 1995) e Algoritmo Genético (Michalewicz, 1996) para o problema de localização/alocação de antenas de transmissão onde é procurado atender à maior quantidade possível de clientes (pontos de demanda) usando uma quantidade mínima de facilidades (locais candidatos). No problema são consideradas restrições de alcance de transmissão e presença de obstáculos interferentes. Na fase da busca local da heurística GRASP são utilizadas três vizinhas distintas. Logo após da busca local, inicia uma terceira fase que consiste em unir ou combinar a solução Y obtida com a melhor solução X* encontrada até o momento (solução de elite). Em seguida são excluídas (ou fechadas), de forma gulosa, algumas facilidades enquanto é melhorado o valor da função objetivo. Nesta terceira fase é obtida uma nova solução melhorada que possui características das soluções Y e X*.

O Algoritmo Genético (AG) proposto é relativamente simples e gera soluções de boa qualidade rapidamente. A população inicial de soluções é construída usando um algoritmo guloso com estratégias de aleatoriedade, similar a um algoritmo construtivo usado na heurística GRASP. Novas soluções filhos são geradas unindo duas soluções “pais” escolhidas aleatoriamente da população. A soluções geradas (filhos) são melhoradas excluindo, de forma gulosa, algumas facilidades enquanto é melhorado o valor da função objetivo. Na seqüência a população é atualizada.

O artigo é organizado da seguinte maneira. Na Seção 2 é apresentada a definição do problema abordado neste trabalho. Na Seção 3 são descritas as fases da heurística GRASP desenvolvida. As etapas do algoritmo genético proposto são apresentadas na Seção 4. A Seção 5 apresenta os resultados obtidos pelos dois métodos e as conclusões estão na Seção 6.

XXXIX SBPO [1567]

2. DEFINIÇÃO DO PROBLEMA DE ALOCAÇÃO DE ANTENAS DE TRANSMISSÃO O objetivo do problema de localização de antenas é determinar os locais para a instalação

de um número mínimo de antenas (facilidades) em uma rede de n locais candidatos, de modo a atender a um conjunto de pontos de demanda, procurando minimizar a distância entre cada ponto de demanda e a antena mais próxima. Para modelar matematicamente o problema, são consideradas as seguintes notações: • B = {1,...,n}, um conjunto de pontos de demanda (um ponto de demanda pode ser um bairro,

uma quadra ou quarteirão de um bairro); • bi = 1 se o ponto de demanda i∈B é atendido por pelo menos uma antena, caso contrário, bi =

0; • A = {1,...,m}, um conjunto de locais candidatos para instalação de facilidades; • aj = 1 se no local j∈A é instalada uma facilidade (antena) para atender à pelo menos um

ponto de demanda, caso contrário aj = 0; • Cj : representa o custo de instalação da facilidade j (antena j); • dij : é a distância entre um ponto de demanda i e a facilidade j. • D: é o alcance (raio de ação) de uma facilidade (se dij ≤ D, o ponto i é atendido pela antena j). • Ni = { j | dij ≤ D} é o conjunto de facilidades instaladas (nos locais j) que cobrem ou atendem

o ponto de demanda i.

O problema pode ser modelado da seguinte maneira:

Minimizar f = ∑∑==

=∈+n

ijij

m

jjj aAjdaC

11}1 , |min{ (1)

Sujeito a: ∑∈ iNj

ja ≥ bi, i = 1, ..., n (2)

11

≥∑=

m

jja (3)

bi ∈{0,1}, i = 1,...,n aj ∈{0,1}, j = 1,...,m

A função objetivo f é definida como a soma dos custos das antenas utilizadas e a soma

das distâncias mínimas entre cada ponto de demanda e a antena instalada. Note que uma solução melhora à medida que menos facilidades são empregadas estando estas, o mais próximo possível dos pontos de demanda.

As restrições (2) indicam que os pontos de demanda serão considerados como cobertos (ou atendidos), se existir ao menos uma antena que possa atendê-lo. Na Figura 1 mostra-se um exemplo na qual um ponto 1 de demanda está dentro do raio de cobertura de 3 facilidades, ou seja N1 = {1,2,3}. A restrição (3) garante que no mínimo deve ser usada uma antena. Na prática isto é muito comum, quando é desconhecida a quantidade de facilidades a serem alocadas.

Note que um ponto de demanda é considerado atendido, se existir pelo menos uma linha de visada direta entre ele e alguma facilidade instalada, com distância menor ou igual ao máximo alcance do sistema. Para uma dada solução factível, o conjunto A de todos os locais candidatos é dividido em dois subconjuntos A1 e A0. A1 contem os índices dos locais abertos (escolhidos para instalar facilidades) e A0 os locais fechados (não escolhidos), ou seja, A1 = {j | aj = 1} e A0 = {j | aj = 0}. O objetivo do problema é determinar os locais que serão abertos (elementos do conjunto A1).

Para uma melhor qualidade de sinal (maior densidade de potência), um ponto de demanda deverá estar o mais próximo possível de uma antena transmissora instalada. As freqüências utilizadas devem estar situadas na faixa alta do espectro (a partir de 30 MHz) como ondas VHF, UHF e SHF. Segundo Smit (1988, 1997), nesta faixa de freqüência, apenas objetos densos como montanhas são considerados interferentes, embora alguns possam ser contornados

XXXIX SBPO [1568]

devido a fenômenos como difração, refração, espalhamento, vinculação, não abordados neste trabalho.

Figura 1. Exemplo da formação do Conjunto N em relação a um ponto de demanda. Neste trabalho um obstáculo é geometricamente representado por um paralelepípedo. Na

Figura 2 mostra-se uma aproximação de um obstáculo por um paralelepípedo com dimensões a, b e c. Existe interferência entre uma facilidade j e um ponto de demanda i se, a reta que une os pontos j e i intercepta (ou corta) um determinado obstáculo.

Figura 2. Representação gráfica de um obstáculo interferente.

3. HEURÍSTICA GRASP PARA O PROBLEMA DE ALOCAÇÃO DE ATENAS

GRASP – Greedy Randomized Adaptive Search Procedure (Feo & Resende, 1995) é uma heurística de múltiplas partidas, na qual cada iteração consiste de duas fases: construção e busca local. A primeira fase constrói uma solução X viável utilizando um algoritmo guloso randomizado. Na segunda fase a solução construída X é melhorada através de um método de busca local ou busca em vizinhança. GRASP é considerada uma metaheurística de busca e tem sido aplicado com muito sucesso para resolver diversos problemas de otimização combinatória (Festa & Resende, 2004).

A Figura 3 apresenta o pseudocódigo da heurística GRASP implementada neste trabalho. O procedimento recebe como entrada o número máximo de iterações a serem executadas (N_iter) e o parâmetro que controla a percentagem de aleatorização na fase de construção (α∈[0,1]). A cada iteração ite, o procedimento Construção constrói uma solução X, e em seguida esta solução é submetida a um procedimento de Busca Local obtendo uma solução melhorada Y (Passos 03 e 04). A partir da segunda iteração, a solução Y é unida com a melhor solução X* encontrada até o momento, obtendo uma solução Z (procedimento Union-Drop). Após fazer a união é aplicada um procedimento de redução (Drop) na nova solução Z, que consiste em excluir ou fechar facilidades, de forma gulosa, enquanto o valor da função objetivo seja melhorado (Passo 06). A cada iteração, é armazenada a melhor solução encontrada (Passo 07). Ao término de todas as

b a

c

XXXIX SBPO [1569]

iterações, aplica-se uma outra busca local, denominada fixa, à melhor solução encontrada (Passo 09).

Procedimento GRASP (N_iter, α) 01 f(X*) = ∞; 02 For ite = 1 to N_iter do 03 X = Construção(α ); 04 Y = Busca-Local(X); 05 If ite >1 then 06 Z = Union-Drop(Y, X*); 07 If f(Z) < f(X*) then X* = Z; 08 End for; 09 X’’ ← Busca-Local-Fixa (X*); 10 Return X’’ End GRASP.

Figura 3. Pseudocódigo da heurística GRASP proposta.

3.1. Fase de Construção

Para determinar uma solução (i.e. determinar um conjunto de facilidades abertas) do problema de alocação de antenas, é usada a heurística gulosa ADD, proposta inicialmente por Kuehn e Hamburger (1963) para problemas de localização de facilidades.

Esta heurística é inicia com todas as facilidades fechadas (A0 =A, A1 = ∅) e a função objetivo f = ∞ (um valor positivo muito grade). A heurística é então repetida de acordo com a seguinte iteração. Procure pela facilidade j∈A0 cuja adição em A1 produza o menor valor da função objetivo f. Se existe decremento no valor de f, adicione j em A1. Caso contrário finalize o procedimento.

Para gerar soluções diferentes, a cada iteração da GRASP, o método ADD ordena o conjunto A0 de facilidades fechadas em ordem crescente da função objetivo. Suponha que o conjunto ordenado seja A0 = {1,...,m}. A cada iteração da fase construtiva, uma facilidade j é selecionada aleatoriamente do subconjunto {1,..., p}⊆ A0 e adicionada no conjunto A1: A0 = A0 – {j}, A1 = A1 ∪ {j}. O conjunto {1,..., p} é denominado conjunto de candidatos restritos e seu tamanho é definido como p = max(1, α×|A0|), onde α ∈[0,1] é o parâmetro de aleatorização e |A0| é o número de facilidades fechadas. Note que, se α = 0, a facilidade a ser escolhida é j =1 (escolha gulosa). Se α = 1, tem-se p = m e a escolha da facilidade é de forma completamente aleatória. A fase de construção finaliza quando não seja mais possível melhorar a função objetivo f ao inserir facilidades no conjunto A1. 3.2. Busca Local

A cada iteração da heurística GRASP é executado o procedimento de Busca-Local que inicia a partir da solução construída pelo procedimento Construção. Nesta busca local são usados dois tipos de movimentos para gerar soluções vizinhas (estrutura de vizinhanças): • Vizinhança 1: uma solução vizinha é determinada adicionando na solução corrente duas

novas facilidades e removendo uma. • Vizinhança 2: uma solução vizinha é determinada adicionando na solução corrente uma nova

facilidade e removendo duas. A cada iteração da GRASP, a escolha da vizinhança é feito de forma aleatória. As

vizinhanças usadas permitem que, numa solução, o número de facilidades abertas não seja fixo. No procedimento Busca-Local-Fixa é usada uma outra estrutura de vizinhança:

• Vizinhança 3: uma solução vizinha é determinada adicionando na solução corrente uma nova facilidade e removendo outra (troca de facilidades). Esta ultima vizinhança permite que o número de facilidades na solução seja fixo.

XXXIX SBPO [1570]

3.3. Procedimento Union-Drop

A cada iteração da heurística GRASP, a solução Y obtida pela Busca Local é melhorada aplicando um procedimento de “cruzamento” de soluções seguida da remoção de algumas facilidades. A idéia deste procedimento é, inserir na solução Y facilidades importantes presentes na atual melhor solução X* e remover facilidades desnecessárias enquanto melhore o valor da função objetivo. Na Figura 4 é mostrado o procedimento de Union-Drop que recebe com entrada duas soluções, a solução Y obtida após da Busca Local e a melhor solução X* encontrada até o momento. No Passo 01 é construído uma nova solução Z fazendo a união de Y e X*. A partir do Passo 05 é aplicado a Z um procedimento de remoção de facilidades. Este procedimento exclui, de maneira gulosa, facilidades que não pertencem a Y ∩ X* (i.e. facilidades que estão em ambas soluções não são removidas). O processo de remoção de facilidade continua enquanto é possível melhorar o valor da função objetivo (Passos 05-09). O procedimento Union-Drop retorna a solução melhorada Z que possui características das soluções Y e X* (passo 10).

Procedure Union-Drop(Y, X*) 01 Gere uma solução Z unindo as facilidades abertas de Y e X* (Z = Y∪X*); 02 Calcule o valor da função objetivo da solução da nova solução Z: f(Z); 03 Defina o seguinte conjunto de facilidades: F = Y∪X* – Y∩X*. 04 Melhora = true; 05 While Melhora = true do 06 Determine a facilidade j∈F que produza o maior decremento da função

objetivo quando j é removida da solução Z. 07 If existe a facilidade j then faça Z = Z – {j}; 08 Else Melhora = false; 09 End while; 10 Return Z; End Union-Drop;

Figura 4. Pseudocódigo do procedimento de intensificação Union-Drop.

4. ALGORITMO GENÉTICO (AG) PARA O PROBLEMA DE ALOCAÇÃO DE ATENAS

Nesta seção são apresentadas as etapas da implementação de um algoritmo genético para o Problema de Alocação de Atenas.

4.1. Codificação de soluções e geração da população inicial de soluções

Uma solução (cromossomo) do problema de alocação de antenas é representada por um vetor de tamanho p (1 ≤ p ≤ m) que armazena os locais candidatos abertos, ou seja, pontos onde serão instaladas as antenas (m é número total de locais candidatos). Por exemplo, o vetor A1 = [8, 4, 3, 25] é uma solução na qual nos pontos 8, 4, 3 e 25 foram escolhidos para a instalação de facilidades (antenas).

Para gerar uma população inicial é usada uma técnica denominada sample greedy proposta por Resende e Werneck (2004), na fase construtiva de uma heurística GRASP proposta para o problema das p-medianas. Os autores propuseram e compararam vários algoritmos construtivos sendo que o método sample greedy apresentou bom desempenho em termos de qualidade de soluções obtidas e tempo computacional.

O método sample greedy é uma heurística gulosa que usa estratégias de escolha aleatória. A escolha do local candidato a ser inserido em A1 é feita da seguinte maneira. Inicialmente é formado um conjunto (amostra) Q de q locais candidatos selecionados aleatoriamente de A0 (conjunto de locais fechados). Em seguida escolhe-se, do conjunto Q, o “melhor” local candidato para ser inserido na solução corrente A1. Para determinar o melhor local, avalia-se a função objetivo após da adição de cada elemento de Q em A1. O número de elementos de Q é definido

XXXIX SBPO [1571]

como )/(log2 estimfmq = , onde m é o número de locais candidatos à instalação das facilidades e festim o número estimado de locais candidatos numa solução. A Figura 5 exibe o pseudocódigo do procedimento População_Construtiva usado para determinar a população inicial de soluções.

Procedure População_construtiva(Pzize) 01 For (i ← 1,2,3,..., Pzize) do 02 A0 ← A; A1 ← ∅; f ← infinito; 03 Escolha aleatoriamente q locais candidatos de A0 formando o subconjunto Q; 04 Para cada local candidato de Q, teste sua adição de em A1 e selecione o melhor local k; 05 Se ao inserir o local k em A1 é melhorado o valor da função objetivo then 06 Insira o local k em A1 e repita os passo 03, 04 e 05; 07 Cromossomo i da população ← A1; 08 End_For End População_construtiva;

Figura 5. Pseudocódigo do algoritmo construtivo para gerar população inicial do AG.

4.2. Cruzamento de Soluções

Após a geração da população inicial, duas soluções Y e X são escolhidas aleatoriamente para cruzamento, gerando uma nova solução Z. O procedimento de cruzamento usado no algoritmo genético é igual ao procedimento Union-Drop apresentado na Figura 6. Inicialmente é feito Z = X∪Y em seguida a solução Z é melhorada de forma gulosa removendo alguns locais candidatos. A renovação da população é feito substituindo a pior solução da população pela solução Z obtida no cruzamento de X e Y.

4.3. Estrutura do algoritmo genético

Procedure AG(Pzize) 01 P ←População_construtiva(Pzize); 02 Determine a pior solução S da população P; 03 While (critério de parada não satisfeito) do 04 Escolha aleatoriamente duas soluções X e Y da população; 05 Z ← Union-DropY, X); 06 If f(Z) < f(S) e Z∉P then 07 P = P – {S}; P = P ∪{Z}; 08 Atualize S ; 09 End-If ; 10 Atualize a melhor solução S* de P; 11 End-While; 12 Return S*; Fim AG;

Figura 6. Pseudocódigo do Algoritmo Genético

O AG implementado neste trabalho usa um operador de cruzamento híbrido denominado Union-Drop que consiste em cruzar (unir) soluções e em seguida melhorar a solução através de uma técnica gulosa (Drop). A população de soluções evolui de acordo com substituição da pior solução pela nova solução encontrada. Desta maneira, a cada iteração, busca-se melhorar a “qualidade” das soluções contidas na população. O pseudocódigo exibido na Figura 6 sintetiza as etapas do algoritmo genético. No Passo 01 é construída P, a população inicial de soluções. No Passo 03 é feita a seleção aleatória de duas soluções pais para serem cruzadas no Passo 05. Se a solução gerada Z é melhor que a pior solução de P e Z∉P, então a pior solução é substituída por Z (Passos 06 e 07). Note que não é permitida a inserção (em P) de soluções Z que já estejam presentes na população. Isto evita a convergência da população para

XXXIX SBPO [1572]

um ótimo local. O critério de parada usado no AG é o “mesmo” usado na heurística GRASP apresentada na Seção 3. Os resultados das heurísticas AG e GRASP são comparados na Seção 5.

No AG foi testado um operador de mutação que consiste em inserir, com probabilidade pm%, um local candidato não encontrado na união das soluções pais X e Y, e não permitindo a remoção deste local no procedimento Drop. O uso do operador mutação não melhorou o desempenho do AG e por este motivo não foi usado este operador.

5. TESTES COMPUTACIONAIS

Nesta seção são comparados os resultados computacionais das heurísticas GRASP e Algoritmo Genético. As heurísticas foram implementadas na linguagem Object Pascal do Delphi 7.0 e os teste computacionais foram realizados em um computador Semprom 3.4 Ghz com 1G Mb de memória RAM.

5.1. Geração dos problemas testes

Para testar as heurísticas, foram gerados dois conjuntos de problemas: • Conjunto 1: composta de 21 problemas gerados de forma manual inserindo estrategicamente

obstáculos, pontos de demanda e locais candidatos com o objetivo de tornar difícil a busca por uma boa solução.

• Conjunto 2: Formado por problemas na qual os obstáculos, pontos de demanda e locais candidatos foram gerados de forma aleatória.

Para cada conjunto de problemas o número de pontos de demanda (n) varia de 100 a 1000. O número de pontos candidatos à instalação de facilidades (m) é igual ao número n. As coordenadas (x, y) dos pontos são gerados de forma dispersa numa área retangular de 33000 metros de comprimento por 30000 metros de largura (0 ≤ x ≤ 33000, 0 ≤ y ≤ 30000). As dimensões a, b e c dos obstáculos interferentes pertencentes ao intervalo [20, 500]. Foram considerados custos constantes de instalação das antenas (Cj = 7000,∀j). A altura das antenas e o alcance de transmissão (máximo raio de cobertura) foram fixados em 30 metros e 10000 metros, respectivamente.

5.2. Parâmetros usados nas heurísticas

Heurística GRASP: • Parâmetro α: Mede o nível de aleatoriedade e gulosidade da GRASP. Foram testados os

seguintes valores de α: 0,0; 0,1; 0,2; 0,3; 0,5; 0,75 e 1,0. Os melhores resultados foram obtidos com α = 0,3.

• Número de iterações GRASP (N_iter): Para cada problema testado a heurística executa 200 iterações.

Algoritmo Genético: • Tamanho da população (Pzize): Resultados satisfatórios foram obtidos com Pzize = (n +

m)/4, onde m representa o número total de locais candidatos para instalação de facilidades e n o número total de pontos de demanda.

• Número estimado de locais candidatos numa solução ( festim ): Este parâmetro é usado na definição do número q de locais candidatos na lista Q para a construção da população inicial. Foram testados diferentes valores para festim: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20. Observou-se que festim = 4 apresentou melhores resultados. Vale ressaltar que para o problema das p-medianas festim = p (Resende e Werneck, 2003).

• Critério de parada: O critério de parada usado no AG foi um número de soluções avaliadas. Para cada problema testado, este número é igual ao número de soluções avaliadas pela GRASP, nas 200 iterações. A Tabela 1 apresenta o número médio de soluções avaliadas, pelos dois métodos, para cada tamanho de problemas.

XXXIX SBPO [1573]

Tabela 1. Número médio de soluções avaliadas para cada tamanho de problema. 100_100 200_200 300_300 400_400 500_500 800_800 1000_1000 Conjunto1 50488 94491 274976 235363 325308 754232 918093 Conjunto2 37252 131329 229101 455657 524632 843572 1004017

5.3. Resultados computacionais Na Tabela 2, mostram-se, para cada um dos 21 problemas dos Conjuntos 1 e 2, os pontos de demanda atendidos PA, o total de facilidades utilizadas TF, os valores da função objetivo f e os tempos computacionais (t), em minutos:segundos, gastos por cada método. Na Tabela 2, os valores em negrito correspondem aos melhores valores da função objetivo. Para o Conjunto 1 de problemas, a heurística GRASP foi melhor que o AG em 8 problemas, o AG foi melhor que a GRASP em 10 problemas e ambos métodos encontraram a mesma solução em 3 problemas. Para o Conjunto 2 de problemas, a heurística GRASP foi melhor que o AG em 7 problemas, o AG foi melhor que a GRASP em 13 problemas e ambos métodos encontraram a mesma solução em 1 problema.

Tabela 2. Comparação dos resultados obtidos pelos métodos GRASP e AG Conjunto 1 Conjunto 2

GRASP AG GRASP AG Prob. n_m PA TF t f PA TF t f PA TF t f PA TF t f

1 99 6 00:01 28771 99 6 00:01 28771 91 5 00:01 56159 91 5 00:01 56159

2 100 8 00:01 20144 100 8 00:01 20039 85 5 00:01 57775 94 6 00:01 56118

3

100_ 100

95 7 00:01 38249 98 8 00:01 38948 88 5 00:01 49981 94 6 00:01 49398

4 187 7 00:03 96113 187 7 00:03 96113 191 7 00:05 68072 192 7 00:05 67695

5 195 13 00:05 63287 197 13 00:05 61365 185 6 00:05 70113 192 7 00:04 68877

6

200_ 200

198 5 00:02 50346 197 5 00:02 50472 187 7 00:05 75802 193 8 00:05 74792

7 285 8 00:13 91736 298 9 00:12 86655 289 9 00:15 93425 296 10 00:15 92930

8 296 11 00:15 105786 282 9 00:15 104020 281 8 00:21 106155 291 10 00:20 103587

9

300_ 300

276 28 00:44 157062 268 27 00:48 160232 282 14 00:20 117319 277 13 00:20 118206

10 372 4 00:24 123700 395 5 00:22 116458 391 17 01:09 125112 391 17 01:20 124532

11 382 8 00:31 101217 391 9 00:29 98349 381 15 01:05 120085 378 15 01:05 123855

12

400_ 400

396 11 00:39 120355 388 10 00:40 120166 370 15 01:02 129857 385 16 01:09 123437

13 500 8 00:51 122737 500 8 00:46 121520 488 17 01:51 133725 488 17 01:51 135031

14 484 7 01:16 121083 492 8 01:03 124052 441 12 01:35 188857 454 14 01:32 192809

15

500_ 500

493 9 01:10 147341 490 9 01:10 150176 474 16 02:16 168750 461 14 02:04 166655

16 800 8 04:20 142856 800 8 03:23 143099 733 16 09:06 277111 765 19 08:34 273613

17 800 14 09:30 111149 800 14 08:23 111582 782 15 06:40 216605 774 15 06:34 223413

18

800_ 800

800 7 04:57 129120 800 7 03:54 129120 754 9 05:48 229142 772 10 05:15 224796

19 1000 16 15:18 225764 1000 16 13:44 226457 952 14 11:28 309418 953 14 10:54 309867

20 1000 9 08:25 163554 1000 8 07:29 152545 977 13 13:43 262064 983 14 12:22 262057

21

1000_ 1000 1000 10 11:20 147384 1000 9 12:08 139856 980 13 13:49 266591 976 14 14:16 268535

Nos 15 problemas onde a heurística GRASP foi melhor que o AG, o percentual médio de

melhoria da GRASP com relação ao AG foi de 1,33%. E, nos 23 problemas onde o AG foi melhor que a GRASP, o percentual médio de melhoria do AG com relação à GRASP foi de 2,30%. Os resultados obtidos mostraram que o AG obteve desempenho um pouco melhor que a heurística GRASP.

A Figura 7 ilustra-se as soluções obtidas pela GRASP e pelo AG no problema 7 (300-300) do Conjunto 1. Nesta Figura observa-se que a solução da GRASP não atende alguns pontos de demanda e a adição de mais uma facilidade na solução do AG, permite o atendimento desses pontos de demanda.

XXXIX SBPO [1574]

Na Figura 8 mostra-se que as heurísticas implementadas também procuram aproximar as facilidades dos pontos de demanda. Nesta Figura observa-se que ambas as heurísticas alocaram 8 facilidades, porém o melhor resultado foi obtido pelo AG, que encurtou a distância de atendimento para vários pontos de demanda.

Figura 7. Gráfico comparativo para a instância 7 do Conjunto 1 de problemas.

Figura 8. Gráfico comparativo para a instância 13 do Conjunto 1 de problemas. As heurísticas também procuram reduzir o número de facilidades utilizadas. Isto pode ser

observado pela Figura 9, que compara as soluções para o problema 20 (1000-1000) do Conjunto 1. As soluções obtidas atenderam a todos os pontos de demanda, porém o AG foi melhor pois utiliza uma facilidade a menos.

XXXIX SBPO [1575]

Figura 9. Gráfico comparativo para a instância 20 do Conjunto 1 de problemas.

6. CONCLUSÕES

O objetivo deste artigo foi desenvolver duas heurísticas diferentes para a solução do problema de localização de antenas de transmissão. Na abordagem do problema procurou-se aproximar mais a situações reais onde em muitos casos é desconhecido o número de facilidades a serem instaladas e tem-se a presença de obstáculos interferentes. A heurística GRASP usa um procedimento construtivo que consiste em abrir locais candidatos à medida que a solução melhora. Na busca local, novas soluções vizinhas são determinadas através do uso de três estruturas de vizinhanças baseadas na inserção e remoção de locais candidatos. O Algoritmo Genético desenvolvido é bastante simples. As soluções iniciais da população são geradas usando uma heurística construtiva gulosa aleatorizada e a evolução da população depende fortemente da substituição da pior solução pela nova solução gerada através do cruzamento.

Os dois métodos propostos foram testados e comparados em 42 problemas de tamanhos diferentes. Analisando os resultados computacionais, é possível observar que a heurística GRASP e o Algoritmo Genético geraram as melhores soluções em 15 e 23 problemas, respectivamente. A melhoria média obtida pelo Algoritmo Genético com relação à heurística GRASP, nos 42 problemas, foi de 0.62%.

Como trabalho futuro pretende-se gerar limites inferiores do problema abordado. Uma relaxação do problema pode ser definida fixando o número de facilidades (como no problema das p-medianas) e não considerando obstáculos interferentes. As soluções das heurísticas propostas poderão ser comparadas com os limites inferiores gerados.

REFERÊNCIAS 1. ABDINNOUR-HELM, S., (1998). A hybrid heuristic for the uncapacitated hub location

problem European Journal of Operational Research, vol. 106, Issues 2-3, 489-499 2. ALP, O., ERKUT, E. & DREZNER, Z., (2003). An Efficient Genetic Algorithm for the p-

Median Problem. Annals and Operations Research, 122, 21-42. 3. CHIYOSHI, F. & GALVÃO, R.D., (2000). A statistical analysis of simulated annealing

applied to the p-median problem. Annals and Operations Research, 96, 61-74. 4. CHURCH, R.L. & REVELLE, C., (1974). The Maximal Covering Location Problem,

Papers of the Regional Science Association, Vol. 32, pp. 101-118.

XXXIX SBPO [1576]

5. CRAINIC, T.G., GENDREAU, M., HANSEN, P. & MLADENOVIC, N., (2004). Cooperative Parallel Variable Neighborhood Search for the p-Median. Journal of Heuristics, vol. 10, pp. 293-314.

6. DREZNER, Z. (1995). “Facility Location: A Survey of Applications and Methods” Springer-Verlag, 1995.

7. FEO, T.A. & RESENDE, M.G.C., (1995), Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109-133, 1995.

8. FESTA, P. & RESENDE, M.G.C., (2004). An annotated bibliography of GRASP. Submitted for the European Journal of Operational Research.

9. GALVÃO, R.D. & REVELLE, C.S., (1996). A Lagrangean Heuristic for the Maximal Covering Location Problem. European Journal of Operational Research, 88: 114-123.

10. GALVÃO, R.D., ESPEJO, L. G.A. & BOFFEY, B., (2000). A Comparison of Lagrangean and Surrogate Relaxations for the Maximal Covering Location Problem. European Journal of Operational Research, 377-389.

11. HAKIMI, I.S., (1964). Optimum location of switching centers and the absolute centers and medians of a graph, Operations Research, Vol. 12, pp. 450-459.

12. HAKIMI, I.S., (1965). Optimum location of switching centers in a communications network and some related graph theoretic problems, Operations Research, Vol. 13, pp. 462-475.

13. HOFFMANN, L.T & GÓMEZ, A.T., (2003). Uma Abordagem do Problema de Localização de Torres de Rádio Transmissão Auxiliado por um Sistema de Informação Geográfica. XXXV SBPO, Natal.

14. KUEHN A.A., HAMBURGER M.J., (1963). A heuristic program for locating warehouses, Management Science, Vol. 9, pp. 643-666.

15. LORENA, L.A. N., (2003). Análise Espacial de Redes com Aplicações em sistemas de Informações Geográficas. Revista Produção (on-line), vol. 3 (2).

16. LORENA, L.A.N. & SENNE, E. L. F., (2003). Local search heuristics for capacitated p-median problems. Networks and Spatial Economics 3: 407-419.

17. LORENA, L.A.N. & LOPES, L.S., (1997). Genetic Algorithms Applied to Computationally Difficult Set Covering Problems. Journal of the Operational Research Society, 48, 440-445.

18. MICHALEWICZ Z. (1996) “Genetic Algorithms + Data Structures = Evolution Programs”, Thir Edition, Springer-Verlag Berlin Heidelberg New York.

19. MURRAY, A.T. & CHURCH R. L. (1996). Applying simulated annealing to location-planning models. Journal of Heuristics, 2:31-53.

20. RESENDE, M.G.C. & WERNECK, R.F., (2004). A Hybrid Heuristic for p-Median Problem. Journal of Heuristics, vol. 10, pp. 59-88.

21. SCHILLING, D., JAYARAMAN, V. & BARKHI, R. (1993). A review of covering problems in facility location. Location Science, 1:25–55, 1993.

22. SCHILLING, D. A., ROSING, K. E. & REVELLE, C. S. (2000). Network Distance Characteristics that Affect Computational Effort in p-Median Location Problems. European Journal of Operational Research, 525-536.

23. SENNE, E.L.F. & LORENA, L.A.N., (2000). Lagrangean/surrogate heuristics for p-median problems. In Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research, M. Laguna and J. L. Gonzalez-Velarde (eds.), Kluwer Academic Publishers, pp. 115-130.

24. SMIT, J. (1988). “Ondas e Antenas”, Editora Érica, 2ª edição. 25. SMIT, J. (1997). “Rádio Propagação”, Editora Érica, 4ª edição. 26. TOREGAS, C., SWAIN, R., REVELLE, C., & BERGM, L., (1971). The Location of

emergency service facilities, Operations Research, Vol. 19, pp. 1363-1373.

XXXIX SBPO [1577]