ORIGEMEstão freqüentemente no nosso cotidiano.Tratam de decisões sobre onde encontrar

facilidades em uma rede, considerando a demanda, visando otimizar determinado critério.

Esse problema começou a ser estudado por Alfred Weber em 1909.

Weber seguiu a linha de pesquisa sobre a seleção de locais de facilidade tendo como objetivo minimizar os custos sobre transporte e a distância.

APLICAÇÕESEsses problemas tratam da questão de onde

localizar uma facilidade e podem ser aplicados para tomar decisões em situações como:

Onde construir escolas, hospitais, fábricas. Como posicionar policiais nas ruas, de modo

que atenda à maioria da população.Também é usado na hora de instalar uma

antena de telefonia celular.

TRABALHOS RELACIONADOS

Geomarketing: Modelos e Sistemas, com Aplicações em Telefonia. Paulo Sérgio Sampaio de Aragão - Tese de Mestrado Universidade Estadual de Campinas.

Distribuição de gás natural no Brasil: Um enfoque crítico de minimização de custos. Eduardo Rocha Praça – Tese de Mestrado Universidade Federal do Ceará.

MODELOS MATEMÁTICOS

Formulação matemática do problema de máxima cobertura:

Church e Revelle (1974) apresentaram a formulação matemática deste problema.A fomulação é a que se segue:

Problema de localização de máxima coberturaConsiste em escolher locais para instalar

facilidades de forma que o maior número de clientes (pontos de demanda) sejam cobertos, e saber qual cliente será atendido por qual facilidade.

O PLMC procura cobrir áreas de demanda.Não faz restrição de capacidade.Não exige que todas as áreas de demanda

sejam cobertas.

Problema de localização de máxima cobertura

Problema de localização de máxima cobertura

v(PLMC) = Max∑ Di yi (1)

i

E

N

sujeito a ∑ xj ≥ yi para todo i E N (2)

jENi

∑ xj = p (3)j EM

xj E {0, 1}, para todo j E M, (4)yi E {0, 1}, para todo i E N (5)

Problema de localização de máxima cobertura

Onde:S : distância de serviço - a área de demanda é coberta se

está dentro desta distância;N = {1, 2, ..., n} : conjunto de pontos de demanda;M = {1, 2, ..., n} : conjunto de poss´ıveis facilidades;Di : a demanda de população da área i;p : número de facilidades a serem localizadas;dij= a menor distância do nó i ao nó j;Ni = {j E J | dij ≤ S};yi recebe 1 se a área de demanda é coberta, caso

contrário recebe 0xj recebe 1 se a facilidade deve ser localizada em j, caso

contrário recebe 0

Problema de localização de máxima cobertura

Nesse Modelo acima descrito, a função objetivo (1) procura maximizar a população coberta.

A restrição(2) diz que a área de demanda j E J é coberta e se há pelo menos uma facilidade dentro da distância S. A restrição (3) limita o número de facilidades a p. E as

restrições (4) e (5) definem as variáveis de decisão a {0,1}.

Algoritmo HLA p/ PLMCHeurística aplicada ao PLMC (HLA)

Algoritmo HLA p/ PLMCDados J conjunto dos vértices facilidades = {j1,..., jp} eCk conjunto de vértices do agrupamento k = {v1, ...v|Ck|}| Ck | cardinalidade de CkEnquanto (solução-inicial melhora) faça

Para k = 1, ..., pPara i = 1, ..., | Ck |

Troque facilidade jk por um vértice vi;Calcule o valor sol correspondente ao novo valor de cobertura;Se sol é melhor que solução inicial então ¸ Faça melhor vértice← vi; Faça solução-inicial← sol;Fim Se;

Fim Para;Se houver melhor vértice então;Atualize J;Fim Se;

Fim Para;Fim Enquanto;

Algoritmo HLA p/ PLMC

Algoritmo HLA p/ PLMC

Algoritmo HLA p/ PLMC

Modelo matemático para o Problema das P-medianas

O problema das p-medianas pode ser formulado como um problema de programação inteira binária. Dado um grafo descrevendo uma dada instância, obtida através da aplicação do algoritmo de Floyd (Beasley, 1993) e um conjunto resultante de vértices. N = {1, ..., n} podemos descrevê-lo da seguinte maneira:

Modelo matemático para o Problema das P-medianas v(PM) = Min∑ ∑ dijXij (1)

iEN jEN

sujeito a ∑ Xij = 1; i E N (2)

jEN

∑ Xjj = p (3)

jEN

  Xij ≤ Xii i, j E N (4) Xij E {0, 1}, i E N, j E N (5)

Modelo matemático para o Problema das P-medianas

Onde:N = {1,...,n} é o índice dos objetos a serem

alocados;p : número de medianas;[dij ] é a matriz de distâncias;Xij recebe 1 se o vértice i é atribuído ao vértice

j, caso contrato yij recebe 0.

Modelo matemático para o Problema das P-medianas

Nesse modelo as restrições 2 e 4 vértice j seja atribuído somente a um vértice i, que deve ser uma mediana. A restrição 3 assegura o número exato de medianas a

serem localizadas e a restrição 5 indica a condição binária de atribuições.

Trabalho Prático - 1Função Objetiva: Minimizar a distância entre

os vértices e as Medianas.

Escolha da Mediana.

Modelo matemático para o Problema das P-medianas