PROBLEMA DE LOCALIZAÇÃO DE MÁXIMA COBERTURA APLICADO À LOCALIZAÇÃO … · 2006-11-10 · O problema de localizar um ... A Floresta Amazônica ocupa 6,50 milhões de quilômetros

12 a 15/09/06 Goiânia, GOPesquisa Operacional na Sociedade: Educação, Meio Ambiente e DesenvolvimentoXXXVIII SIMPÓSIO BRASILEIRO PESQUISA OPERACIONALDE

PROBLEMA DE LOCALIZAÇÃO DE MÁXIMA COBERTURA APLICADO À LOCALIZAÇÃO DE ESQUADRÕES DE AERONAVES

DE INTERCEPTAÇÃO NA REGIÃO AMAZÔNICA

Rodrigo Prado dos Santos Carlos Müller

Instituto Tecnológico de Aeronáutica Praça. Marechal Eduardo Gomes, 50 São José dos Campos – SP – Brasil [email protected]; [email protected]

Resumo A área crítica para vigilância do espaço aéreo Brasileiro é a Floresta Amazônica, cobrindo uma área de aproximadamente 5,08 milhões de quilômetros quadrados. O problema de localizar um dado número de facilidades de vigilância ou localizar um dado número de esquadrões de interceptação para maximizar a área de cobertura em uma definida região geográfica, como a Amazônia, é conhecido na literatura como um Problema de Localização de Máxima Cobertura (MCLP). O objetivo deste artigo é apresentar o MCLP, sugerindo novas restrições para adaptá-lo à realidade do problema estudado. Os resultados obtidos mostraram que, sob determinadas circunstâncias, restrições adicionadas ao MCLP original conferem um maior realismo à formulação matemática utilizada. Palavras-chave: Problema de Localização de Máxima Cobertura (MCLP), Programação Linear Inteira Binária, Otimização. Área de classificação principal: LGT – Logística e Transportes.

Abstract The critical area for surveillance on the Brazilian airspace is the Amazonian Forest, covering an area of approximately 5.08 millions squared kilometers. The problem of to locate a given number of surveillance facilities or to locate a given number of interception squadrons to maximize the area of coverage in a specific geographic space, as the Amazônia, is known in the literature as a Maximum Covering Location Problem (MCLP). The objective of this paper is to present the MCLP, suggesting new restrictions to adapt him to the reality of the studied problem. The obtained results showed that, under certain circumstances, restrictions added original MCLP check a larger realism to the used mathematical formulation. Keywords: Maximum Covering Location Problem (MCLP), Linear Binary Programming Integer, Optimization. Main area: LGT – Logistics and Transportation.

XXXVIII SBPO [ 1042 ]


1. INTRODUÇÃO A Floresta Amazônica ocupa 6,50 milhões de quilômetros quadrados do continente sul americano, distribuída ao longo de nove países: Brasil, Bolívia, Colômbia, Equador, Guiana, Guiana Francesa, Peru, Suriname e Venezuela. Aproximadamente 85% dessa área situam-se no Brasil, representando 5,08 milhões de quilômetros quadrados, aproximadamente 61% do território brasileiro, conforme citado por Lorch (2000). Uma importante característica da Floresta Amazônica no Brasil é sua pequena densidade populacional, aproximadamente 3,2 habitantes por quilômetro quadrado, um número extremamente baixo quando comparado a alguns países do mundo, como Brasil (19/km2), Japão (332/km2), Inglaterra (239/km2), e Alemanha (229/km2). Ainda de acordo com Lorch (2000), essa característica, que por um lado pode ser benéfica no sentido de colaborar para a preservação de todo o potencial ainda inexplorado, por outro lado facilita a ação de grupos, com os interesses mais distintos, como o desmatamento para utilização de área para atividades pecuárias, o contrabando, o tráfico de drogas, a pirataria biológica. A vastidão da floresta oferece o benefício da impunidade a esses grupos, principalmente pela ampla facilidade de locomoção pela mata, rios e espaço aéreo, mostrando-se muitas vezes mais equipados que os organismos governamentais encarregados de fiscalizar e combater tais práticas. Se não bastasse, a região ainda está sujeita à invasão por parte de grupos guerrilheiros de países vizinhos, que, em acuados pelas forças armadas locais, buscam refúgio na floresta, trazendo problemas políticos de países vizinhos para o território brasileiro. No início da década de 90 iniciaram-se os estudos para suprir a necessidade de prover a região de um sistema de coordenação nacional. Assim nasceu o sistema SIVAM (acrônimo de SIstema de Vigilância da AMazônia), com a missão de coletar informação científica e também para assegurar a vigilância do tráfego aéreo na região. O sistema SIVAM consiste basicamente de:

• 25 Unidades de Vigilância – UV, responsáveis pela coleta de dados; • Três Centros Regionais de Vigilância – CRV, responsáveis pelo processamento e

repasse de informações aos órgãos regionais; e • Um Centro de Coordenação Geral – CCG, responsável por repassar as

informações coletadas aos principais órgãos federais. Além das estações citadas acima, o SIVAM também dispõe de inúmeras Unidades de Telecomunicação, dez radares meteorológicos, 13 radares de altitude, 70 estações de superfície, 200 plataformas de coletas de dados e informações de satélites (TIROS, GOES/METEOSAT, SCD-1, LANDSAT, SPOT, CBERS e ERS-1), cinco aeronaves de vigilância aérea (Embraer ERJ-145SA AEW&C – Early Warning and Control Aircraft – Alerta Aéreo Antecipado e Controle, designadas R-99A pela Força Aérea Brasileira), e três aeronaves de sensoriamento remoto (Embraer ERJ-145RS – Remote Sensing – Sensoriamento Remoto, designadas R-99B). Enquanto a malha de radares é responsável pela cobertura compacta da maior parte do espaço aéreo acima dos 10.000 pés de altitude, o R-99A realiza o trabalho complementar de cobrir o espaço aéreo abaixo dos 10.000 pés, com um raio de detecção de aproximadamente 350 quilômetros. A função do R-99B é gerar imagens em três dimensões e de poder localizar alvos móveis no solo com grande facilidade a até 100 quilômetros de distância, além de realizar o mapeamento do terreno com precisão muito superior à dos satélites comerciais atualmente utilizados, podendo prover informações detalhadas sobre as bases de apoio do narcotráfico no solo, ou ainda de queimadas, desmatamentos e outros fenômenos hoje monitorados pelo satélite, por exemplo.



Figura 01: O Sistema SIVAM.

Com a modernização do sistema de defesa aérea e controle do tráfego aéreo brasileiro, sendo o SIVAM uma grande expressão desse trabalho, comprovou-se que as principais rotas de entrada de drogas ilícitas em território brasileiro ocorrem por via aérea, em pequenas aeronaves, oriundas das regiões reconhecidamente produtoras dessas substâncias. Essas seguem para o interior do Brasil (consumo interno) ou para países vizinhos, a caminho da Europa e Estados Unidos, entre outros destinos da rota de exportação (http://www.fab.mil.br/imprensa/Noticias/lei-abate/3007_abate.htm). Quando uma aeronave suspeita sem plano de vôo é detectada, aeronaves militares (Embraer EMB-314 ALX – Super Tucano – designadas A-29) são acionadas para interceptar, e, se necessário, obrigar a mudança de rota e pouso. No caso de desobediência das instruções anteriores, a aeronave militar é autorizada a abater a aeronave suspeita, de acordo com o Decreto-Lei nº. 5.144, (publicado no Diário Oficial da União, de 19 de julho de 2004 – disponível em www.planalto.gov.br/ccivil_03/Leis/L9614.htm). Assim, levando-se em conta a grande extensão territorial da região amazônica, face aos recursos escassos disponíveis, os esquadrões responsáveis pela interceptação devem ser alocados em posições que possibilitem a máxima cobertura da região, podendo ter um tempo mínimo de deslocamento da base até o ponto de interceptação, diminuindo assim a probabilidade que essa aeronave suspeita fuja do alcance das autoridades. Atualmente, os esquadrões de A-29 estão localizados somente em três cidades: Campo Grande, Boa Vista e Porto Velho. O MCLP (Maximum Coverage Location Problem – Problema de Localização de Máxima Cobertura) pode ser aplicado ao problema descrito acima com a finalidade de encontrar a melhor localização de novas bases para os esquadrões de A-29, de modo a cobrir a Região Amazônica de maneira eficiente. O objetivo deste artigo é mostrar uma aplicação do MCLP ao problema identificado no Sistema SIVAM, utilizando para tal um conjunto de pontos “fictícios”, escolhidos de tal forma que ilustrem de uma maneira compreensível a aplicação. Na seção seguinte, será apresentado o MCLP, sua formulação matemática e suas aplicações. Na seção 3, será apresentada a formulação considerada para o problema em questão com suas devidas adaptações. Nas seções 4 e 5, serão



apresentados os pontos escolhidos, e mostrada a solução, utilizando a formulação original do MCLP e a formulação adaptada. Por fim, na seção 6 serão feitos comentários sobre as soluções encontradas e considerações sobre pesquisas futuras. 2. PROBLEMAS DE LOCALIZAÇÃO O Problema de Localização, conforme citado por Fuller (1997), tem por objetivo escolher um conjunto de pontos de facilidades que “cobrem” um dado conjunto de pontos de demanda. Um ponto de facilidade cobre um ponto de demanda se este ponto de demanda está dentro de uma dada métrica (usualmente distância ou tempo) de um ponto de facilidade. As duas versões do problema de localização e cobertura mais conhecidas e utilizadas são o Set Covering Problem (SCP) – Problema de Cobertura de Conjuntos e o MCLP. O SCP tem como objetivo encontrar o mínimo número de facilidades necessárias para cobrir um dado número de pontos de demanda. As restrições de cobertura são normalmente baseadas em alguma métrica determinada, como distância ou tempo de viagem. O MCLP direciona o problema para localizar um limitado número de facilidades para cobrir o máximo número de pontos de demanda, mas não necessariamente todos. Se todos os pontos de demanda são cobertos por um dado número de facilidades, o resultado do MCLP é equivalente ao do SCP. A Tabela 01 apresenta a relação entre o SCP e o MCLP.

Tabela 01: Relação entre SCP e MCLP (Başdemir, 2000). Problema Número de facilidades % Coberta dos pontos de

demanda Raio de cobertura

SCP Função objetivo (min.) 100% Exógeno

MCLP Exógeno Função objetivo (max.) Exógeno

Matematicamente, o SCP é descrito por Fuller (1997) da seguinte maneira:

Minimizar ∑∈

=Jj

jj xcz

Sujeito a: Iix

iNjj∑

∈

∈∀≥ ...,1 , e

{ } Jjx j ∈∀∈ 1,0 .

onde: m = número de pontos de demanda; n = número de possíveis locais de facilidades; I = conjunto de pontos de demanda; J = conjunto de pontos candidatos a locais de facilidades; S = máxima distância de cobertura (raio de cobertura); dij = distância (ou alguma outra métrica) de cada ponto de demanda i para cada

possível ponto de facilidade j; cj = custo de usar a localidade j, para j = 1, ..., n; xj = 1, se o ponto de facilidade j está ocupado, 0 caso contrário; e

Ni = o conjunto dos possíveis pontos de facilidade j que cobrem o ponto de demanda i.

{ } ⎟⎠⎞⎜

⎝⎛ =≤= miforSdjN iji ,...,1



O MCLP foi introduzido por Church e ReVelle (1974), e reformulado por Church e Toregas (1986). A formulação matemática do MCLP é:

Maximizar ∑∈

=Ii

ii yaz

Sujeito a: ∑

∈

∈∀≥iNj

ij Iiyx ,... ,

PxJj

j∑∈

≤ ,

{ } Jjx j ∈∀∈ 1,0 , e

{ } Iiyi ∈∀∈ 1,0 . onde:

{ } IiforSdJjN iji ∈∀≤∈=

xj = 1, se o ponto de facilidade j está ocupado, 0 caso contrário; yi = 1, se o ponto de demanda i está ocupado, 0 caso contrário; ai = a “bonificação” pela cobertura do ponto de demanda i, para i=1, …, m; P = o número máximo de locais de facilidades que podem ser ocupados; e todos os outros parâmetros definidos como no SCP acima.

Note que, se ai=1, i=1, ..., m, então o MCLP torna-se um problema de maximização de cobertura de pontos de demanda, e se todos os pontos de demanda são cobertos, o MCLP é equivalente ao SCP. Algumas aplicações do MCLP são mencionadas abaixo:

• Ótima localização de radares de vigilância (Santos et al, 2003); • Otimização de redes de telecomunicações (Costamagna et al, 1998); • Localização de estações de busca e salvamento (Başdemir, 2000); • Planejamento de rede de ambulâncias (Adenso-Diaz e Rodriguez, 1997); • Localização de sirenes de emergência (Current e O’Kelly, 1992); • Projeto de uma rede de monitores para controle da poluição do ar (Houglane e

Stephens, 1976); • Escolha e composição de listas para realizar uma campanha publicitária pelo

correio (Dwyear e Evans, 1981); • Seleção de áreas prioritárias para conservação (Woodhouse et al, 2000); e • Identificação de áreas que representam a máxima possível representação de

espécies específicas (Church et al., 1996). 3. FORMULAÇÃO DO PROBLEMA SIVAM Para formular o problema descrito na Região Amazônica, foram acrescentadas restrições ao MCLP como foi realizado por Başdemir (2000), modelando o problema de localização de unidades de busca e salvamento na região turca dos mares Egeu e Mediterrâneo. Na sua formulação, além de atribuir valores bônus para pontos de demanda de alta prioridade, ele também atribuiu bônus para algumas características das regiões candidatas a estações SAR – pontos de facilidade – como características logísticas, geográficas e climáticas. Isto efetivamente direcionou o modelo no sentido de se esforçar para cobrir tais pontos de demanda prioritários, com os pontos de facilidades considerados mais favoráveis. O modelo de Başdemir tem mais pontos candidatos (152 pontos) que pontos de demanda (100 pontos), e para a sua formulação foi elaborado um Problema de Programação Linear Inteiro Binário.



O problema SIVAM então, com suas devidas adaptações, pode ser representado pelo seguinte MCLP:

Maximizar ∑∈

=Ii

ii yaz (1)

Sujeito a: ∑

∈

∈∀≥iNj

ij Iiyx ,... , (2)

PxJj

j∑∈

≤ , (3)

JjNxL Ljj ∈≥∑ . , (4)

JjNxG Gjj ∈≥∑ . (5)

{ } Jjx j ∈∀∈ 1,0 , e

{ } Iiyi ∈∀∈ 1,0 , onde:

m = número de pontos de demanda; n = número de possíveis locais de facilidades candidatos (bases de esquadrões de A-29); I = conjunto de pontos de demanda (I = {1 … m}); J = conjunto de pontos de facilidades candidatos (J = {1 … n}); S = máxima distância de cobertura (alcance de missão do A-29); dij = distância de cada ponto de demanda i para cada possível ponto de facilidade j; xj =1, se a base de esquadrões de A-29 j é ocupada, 0 caso contrário; yi = 1, se o ponto de demanda é coberto, 0 caso contrário; Ni = o conjunto de possíveis bases de esquadrões de A-29 que cobrem o ponto de demanda i;

{ } ⎟⎠⎞⎜

⎝⎛ ∈∀≤∈= IiSdJjN iji ,

ai = bonificação resultante da cobertura do ponto de demanda i, para i=1, …, m; P = o número máximo de bases de esquadrões de A-29 que podem ser ocupadas; Lj = bônus referente à característica logística de cada ponto de facilidade j; Gj = bônus referente à característica geográfica de cada ponto de facilidade j; NL = valor mínimo de “bonificação logística” total; e NG = valor mínimo de “bonificação geográfica” total.

A bonificação ai na equação (1) representa a importância da cobertura de tal ponto no problema; quanto maior o seu valor, maior a possibilidade (ou necessidade) que o ponto yi esteja coberto na solução do problema. A restrição (2) é a restrição de cobertura. Os pontos candidatos a bases de esquadrões cobrem os pontos fixos de demanda. Cada ponto candidato possui um número de pontos de demanda que pode cobrir; da mesma maneira, cada ponto de demanda possui um conjunto de pontos candidatos que são capazes de cobri-lo (o conjunto Ni). A restrição (3) indica o limite máximo de pontos candidatos a bases de esquadrões de A-29 que podem ser escolhidos simultaneamente, normalmente determinados por restrições orçamentárias.



As restrições (4) e (5), para características logísticas e geográficas, são baseadas nas características de cada ponto candidato a base de esquadrão de A-29, e limitadas inferiormente por um valor (NL ou NG), indicando o padrão mínimo total de bonificação considerado para cada característica. 4. UMA APLICAÇÃO Uma aplicação foi desenvolvida considerando um mapa (sem escala, com objetivo ilustrativo) da Região Amazônica, e nele foram escolhidos dez pontos possíveis para localização de bases de esquadrões de A-29. Ainda foram escolhidos 15 pontos de demanda. Um conjunto de critérios para a seleção dos pontos de facilidade e para os pontos de demanda é sugerido abaixo. Tais critérios são úteis na quantificação dos valores bônus considerados para cada localidade: Critério de seleção para os pontos candidatos a bases de esquadrões de A-29:

- Unidade da Aeronáutica no local: Locais que já contam com a presença da Aeronáutica contribuem para a redução dos custos logísticos, com relação ao pessoal e material para manutenção das aeronaves;

- Agência da Polícia Federal no local: Quando é realizada a interceptação e o pouso forçado de uma aeronave suspeita sem plano de vôo, é necessária a presença da Polícia Federal em terra para ações adicionais;

- Fácil acesso de superfície: Vias de acesso em boas condições são necessárias para garantir um efetivo e permanente abastecimento dos esquadrões, permitindo um rápido acesso terrestre, para transporte de pessoal, suprimentos e material para manutenção;

- Disponibilidade das pistas de pouso: As condições do campo de pouso (tipo de pavimento, tamanho de pista) devem ser adequadas para a operação do A-29 e das aeronaves de suporte. A bonificação do item Logística pode ser atribuída a um bônus que indique a proximidade a Unidades da Aeronáutica e/ou Agências da Polícia Federal, e a um bônus referente à facilidade de acesso terrestre. A bonificação do item Geografia deve levar em conta o relevo local, atribuindo um bônus para o terreno com relevo mais favorável. Critério de seleção para os pontos de demanda:

- Pistas de pouso próximas a rodovias: Tal proximidade pode favorecer a rápida evasão de contrabandistas e traficantes após o pouso;

- Áreas com uso agrícola suspeito: Locais com imagens de satélite mostrando desmatamento, por exemplo, podem indicar locais utilizados para plantio de drogas;

- Rotas aéreas usadas pelos contrabandistas e traficantes: Locais com informação de grande fluxo aéreo suspeito utilizado por um grande número de aeronaves sem plano de vôo. Tais aeronaves podem ser somente fazendeiros movimentando-se entre as fazendas vizinhas, mas também podem ser aeronaves utilizadas por contrabandistas e traficantes. Existem registros de que cerca de 3000 movimentações sem plano de vôo ao longo da fronteira são detectadas diariamente. A pronta interceptação de uma aeronave sem plano de vôo é necessária tanto para aumentar a eficiência contra as atividades ilegais quanto para restringir a prática de não notificar o vôo, contribuindo assim para um tráfego aéreo mais seguro;

- Estações de telecomunicação e radares: Para garantir a segurança da rede existente; - Fronteira: A cobertura de pontos selecionados ao longo da fronteira com outros países

pode ser considerada como uma condição prioritária. Dessa maneira, é conveniente que pontos ao longo da fronteira sejam escolhidos para vigilância;

- Cidades populosas: Cidades populosas podem favorecer a rápida evasão após o pouso.



A localização aproximada e a bonificação sugerida para cada um dos pontos de facilidade e de demanda encontram-se a seguir. Foram ainda considerados, para a resolução do problema:

• P = 5 – número máximo de bases simultâneas a serem instaladas; • NL= 44 – padrão mínimo total de bonificação considerado para o somatório de

bônus logísticos dos pontos de facilidade escolhidos na solução; • NG= 47 – padrão mínimo total de bonificação considerado para o somatório de

bônus geográficos dos pontos de facilidade escolhidos na solução; e • S = alcance de missão do A-29 – indicado na figura seguinte. Para o caso

analisado, considerou-se que a aeronave seja capaz de realizar uma missão de interceptação saindo de Boa Vista, indo até Manaus e retornando até Boa Vista (distância entre Manaus e Boa Vista – 350 km aproximadamente).

Figura 02: Pontos Candidatos, Pontos de Demanda e Alcance de Missão do A-29.

(desenho sem escala)

Tabela 02: Identificação das localidades e valores das bonificações.

Bonificações Ponto de facilidade - xj Lj Gj Ponto de Demanda – yi

ai

1 – Campo Grande - MS 10 9 1 – Imperatriz - MA 8 2 – Cuiabá - MT 10 9 2 – Santarém - PA 6 3 – Cachimbo - PA 9 9 3 – Almeirim - PA 5 4 – Belém - PA 9 8 4 – Sinop - MT 5 5 – Macapá - AP 8 8 5 – Oriximiná - PA 6 6 – Porto Velho - RO 10 8 6 – Porto Esperidião - MT 9 7 – Manaus - AM 9 8 7 – Airão - AM 7 8 – Boa Vista - RR 10 7 8 – Manicoré - AM 7 9 – Rio Branco - AC 9 9 9 – Guajará - Mirim - AM 8 10 – São Gabriel da Cachoeira - AM 8 9 10 – Surucucu - RR 8

11 – Tefé - AM 9 12 – Japurá - AM 7 13 – Tabatinga - AM 9 14 – Jordão - AC 8

15 – Guajará - AM 10



5. RESULTADOS Desenvolvendo as formulações matemáticas descritas nas seções 3 e 4 e resolvendo o problemas utilizando o SOLVER do Excel, chegamos aos seguintes resultados:

Tabela 03: Resolução do MCLP original. Valor da função objetivo z = 104

Bases escolhidas 2 – Cuiabá – MT 5 – Macapá – AP 7 – Manaus - AM 9 – Rio Branco - AC 10 – São Gabriel da Cachoeira - AM

Pontos de demanda não cobertos 1 – Imperatriz - MA

Restrições adicionais (somente para comparação com o Problema SIVAM)

∑ ≡<= )47(44. Ljj NxL ∑ ≡<= )44(43. Gjj NxG

Figura 03: Cobertura resultante do MCLP original.

(desenho sem escala)



Tabela 04: Resolução do MCLP adaptado – Problema SIVAM. Valor da função objetivo Z = 80

Bases escolhidas 1 – Campo Grande – MS 2 – Cuiabá – MT 6 – Porto Velho – RO 9 – Rio Branco – AC 10 – São Gabriel da Cachoeira – AM

Pontos de demanda não cobertos 1 – Imperatriz – MA 2 – Santarém – PA 3 – Almeirim – PA 5 – Oriximiná – PA 7 – Airão – AM

Restrições adicionais

∑ ≡= )(47. Ljj NxL ∑ ≡= )(44. Gjj NxG

Figura 04: Cobertura resultante do Problema SIVAM.

(desenho sem escala) De posse dos resultados acima, observou-se o seguinte:

• Era esperado que o MCLP original obtivesse um valor da função objetivo z maior que o Problema SIVAM; quando se acrescentam restrições a um problema de otimização, o valor da solução, quando se mantém viável, é igual ou menor ao valor original sem o acréscimo de tal restrição (quando o problema é de maximização da função objetivo – quando o problema é de minimização, o novo valor ótimo, quando existe, é maior ou igual ao anterior, ou seja, nos dois casos, a solução somente pode “piorar”);



• Conseqüentemente, a cobertura gerada pela solução do MCLP original cobre um número maior de pontos, com as bases para os esquadrões de A-29 mais espalhadas ao longo da região;

• Podemos ver na Figura 04 que, com relação à cobertura, o ponto de facilidade 1 poderia ser retirado, sem prejuízo da solução do Problema SIVAM; entretanto, quando são considerados os mínimos requeridos em termos logísticos e geográficos, essa localidade deve ser mantida. Além disso, a base localizada em no ponto candidato 1 (Campo Grande – MS) tem como função não somente cobrir a área da Região Amazônica, mas também o Pantanal, região esta não considerada nesta análise;

• Os mínimos requeridos em termos logísticos e geográficos são respeitados na solução do Problema SIVAM, enquanto que no MCLP original esses mínimos não foram alcançados. Uma outra interpretação desses mínimos poderia ser o grau de facilidade de instalação do conjunto de bases escolhido – quanto maior o grau de facilidade, menor o custo de implantação;

• Na solução do Problema SIVAM, a escolha das bases privilegiou as candidatas que apresentavam melhores características logísticas e geográficas. Ainda mais, os pontos de demanda que apresentam maior bonificação estão, em sua maioria, cobertos por mais de uma base.

Na aplicação prática mostrada acima, a bonificação atribuída aos pontos candidatos a bases de esquadrões de A-29 teve como prioridade a proteção da fronteira Oeste da Região Amazônica, nas fronteiras com a Colômbia, o Peru e a Bolívia, região sabidamente mais afetada pelo tráfico de drogas. 6. CONCLUSÕES Este artigo estudou o problema de localização de bases de aeronaves de interceptação na Região Amazônica brasileira para cobrir a área de uma maneira eficiente. Este problema é classificado como um tipo de Problema de Localização de Máxima Cobertura – MCLP. Foi apresentada a formulação matemática do MCLP original, e também foram realizadas algumas adaptações, sugerindo uma formulação matemática para tratar o Problema SIVAM, considerando o uso de bonificações pelas características logísticas e geográficas das localidades candidatas a pontos de facilidades, e acrescentando restrições com relação ao padrão mínimo que o conjunto de bases escolhidas deveria obedecer. Cabe ressaltar que os valores considerados na aplicação prática têm finalidade didática, não correspondendo totalmente com a realidade da região. Os resultados mostraram que se não forem consideradas tais restrições, a solução apresentada pelo MCLP original mostra-se melhor que o Problema SIVAM, cobrindo um número maior de pontos; entretanto, algumas situações, como por exemplo, existência de orçamento reduzido, pode indicar que o problema seria tratado com mais realismo, dando prioridade para pontos com valor de bonificação maior, se for adotada a formulação proposta no Problema SIVAM. A completa formulação do problema, com ênfase na seleção dos pontos de demanda e de facilidade, com a respectiva quantificação dos valores para os bônus para os locais escolhidos, bem como o estudo da análise de sensibilidade estão previstos para trabalhos futuros. REFERÊNCIAS

Força Aérea Brasileira, www.fab.mil.br/imprensa/Noticias/lei-abate/3007_abate.htm.

Acesso em 20 de março de 2006. Projeto SIVAM, www.sivam.gov.br/PROJETO/INDEX.HTM. Acesso em 20 de março

de 2006.



Embraer – Empresa Brasileira de Aeronáutica S.A., www.embraer.com.br/english/content/aeronaves/. Acesso em 20 de março de 2006.

Adenso-Diaz, B.; Rodriguez, F. (1997) “A Simple search Heuristic for the MCLP: Application to the location of ambulance bases in a Rural region”, Omega-International Journal of Management Science, v. 25, n. 2, (Abril 1997), p. 181 – 187.

Arakaki, R. G. I. (2003) “Heurística de localização-alocação para problemas de localização de facilidades”, Tese (Doutorado em Computação Aplicada) – São José dos Campos: INPE, 2002.

Başdemir, M. M. (2000) “Locating Search and Rescue Stations in the Aegean and Western Mediterranean Regions of Turkey”, Tese (Mestrado em Pesquisa Operacional) – Ohio: Air Force Institute of Technology, 2000.

Church, R.; Revelle, C. (1974) “The Maximal Covering Location Problem”, Papers of the Regional Science Association, v. 32, (Dezembro 1974), p. 101 – 118.

Church, R.; Stoms, D.; Davis, F. W. (1996) “Reserve Selection as a Maximal Covering Location Problem”, Biological Conservation, v. 76, n. 2, p. 105 – 112.

Costamagna, E.; Fanni, A.; Giacinto, G., (1998) “A Tabu Search algorithm for the optimization of telecommunication networks”, European Journal of Operational Research, v. 106, (1998), p. 357 – 372.

Current, J.; O’Kelly, M. (1992) “Locating emergency warnings sirens”, Decision Sciences, v. 23, n. 1, (Jan/Fev 1992), p. 221 – 234.

Dwyear, F.; Evans, J. (1981) “A branch and Bound Algorithm for the list selection problem in direct mail advertising”, Management Science, v. 27, n. 6, (Junho 1981), p. 658 – 667.

Fuller, D. E. (1997) “Optimizing Airborne Area Surveillance Asset Placement”, Tese (Mestrado em Análise Operacional) – Ohio: Air Force Institute of Technology, 1997.

Goldbarg, M.C.; Luna, H. P. L. (2000) “Otimização Combinatória e Programação Linear: Modelos e Algoritmos” – Rio de Janeiro: Elsevier, 2000, 649p.

Hougland, E. S.; Stephens, N. T. (1976) “Air Pollutant Monitor Sitting by analytical techniques”, Journal of Air Pollution Control Association, v. 26, n. 1, p. 51 – 53.

Köksalan, M.; Süral, H.; Kirca, Ö. (1995) “A Location-Distribution Application for a Beer Company”, European Journal of Operational Research, n.80 (1995), p. 16 – 24.

Lorch, C. (2000) “Do CAN ao SIVAM: a FAB na Amazônia” – Rio de Janeiro: Aerospace, 2000, 144p.

Santos, O.J.S. (2005) “Problema de Localização de Cobertura de Conjuntos”, Spectrum (Revista do Comando Geral de Operações Aéreas – COMGAR), n. 9, (Dezembro 2005), p. 26 – 28.

ReVelle, C.; Laporte, G. (1996) “The Plant Location Problem: News Models and Research Prospects”, Operations Research, v. 44, n. 6 (1996), p. 864 – 873.

Santos, C. L. R.; Brito, F. M. Jr.; Heinzelmann, L. S. (2003) “Otimização de Cobertura Radar Via Algoritmo Genético”, VII SPOLM, p 71 – 78.

Woodhouse, S.; Lovett, A.; Dolman, P.; Fuller, R. (2000) “Using a GIS to select priority areas for conservation”, Computers, Environment and Urban Systems, v. 24, n. 3, p. 79 – 93.


Documents

PROBLEMA DE LOCALIZAÇÃO DE MÁXIMA COBERTURA APLICADO À LOCALIZAÇÃO … · 2006-11-10 · O problema de localizar um ... A Floresta Amazônica ocupa 6,50 milhões de quilômetros