Um estudo sobre abordagens para solução de
problemas de localização de dacilidades
M. G. Oliveira
Technical Report
-
February
RT-INF_001-12
-
2012
-
-
Relatório Técnico
Fevereiro
The contents of this document are the sole responsibility of the authors.
O conteúdo do presente documento é de única responsabilidade dos autores.
Instituto de Informática
Universidade Federal de Goiás
www.inf.ufg.br
Um estudo sobre abordagens para solução
de problemas Facility Location
Max Gontijo de Oliveira
∗
Cedric L. de Carvalho
[email protected]
†
[email protected]
Abstract. This paper is intended to propose a solution to the problem of resource
distribution in a predetermined geographic region. For this purpose, techniques
and data mining approaches have been studied in order to obtain patterns of
demand of the distribution problem you want solved. This type of problem is
known in literature as facility location problems, where we seek to find the best
locations for new facilities, considering the estimated demand.
Keywords: facility location, data mining, clustering algorithms, k-means.
Resumo. Este relatório tem o objetivo de apresentar um estudo sobre diversas abordagens que buscam solução para o problema de distribuição de recursos
em uma região geográfica pré-determinada. Nesse estudo, as informações de
demanda e de possı́veis localizações de uma facilidade terão respaldo de dados
históricos referentes ao problema. Assim, o uso de técnicas e abordagens de
mineração de dados para o aprendizado é fundamental. Esse tipo de problema
é conhecido na literatura como problemas de localização de facilidades (facility
location), onde busca-se encontrar as melhores localizações para a inserção facilidades, considerando a demanda existente.
Palavras-Chave: facility location, mineração de dados, algoritmos de cluster,
k-means.
1
Introdução
Decidir sobre como realizar a distribuição de facilidades1 em uma região geográfica
limitada (uma cidade, por exemplo), é uma atividade estratégica para muitas organizações.
Quando a disponibilização de um recurso envolve um custo muito alto ou o número de
recursos disponı́veis é limitado, esse problema fica ainda mais preocupante, pois uma
distribuição mal realizada pode acarretar em prejuı́zo certo para a organização.
∗
Mestrando em Ciência da Computação, INF-UFG
Orientador
1
Nesse contexto, uma facilidade é um recurso que provê algum tipo de serviço ou produto para atender
uma demanda medida ou estimada que, geralmente, está próxima a esse recurso. De modo geral, facilidade
e recurso terão o mesmo significado nesse trabalho.
†
1
Facility Location
2
Uma distribuição mal realizada de recursos disponı́veis pode ser responsável por uma
série de consequências indesejáveis pela organização, como interesse maior de clientes locais à concorrência, dificuldades de atingir metas de qualidade de serviço (prazo para
atendimento) e baixo uso do recurso (considerando sua capacidade). Somente para ilustrar, pode-se tomar como exemplo de organizações que se deparam com esse tipo de
decisão, redes de supermercados (que precisam decidir onde instalar uma nova filial), empresas que coordenam o serviço de divulgação por panfletagem (que precisam decidir como
alocar as pessoas que irão distribuir panfletos), empresas distribuidoras de energia elétrica
(que precisam decidir os melhores pontos em uma rede elétrica onde inserir chaves e transformadores), hospitais, postos de saúde, delegacias e semáforos em uma malha rodoviária
(que precisam ser distribuı́dos de forma que haja a maior cobertura possı́vel em uma
cidade, considerando a demanda e necessidade de cada unidade em uma cada região).
Esses problemas de realizar a distribuição de recursos (ou facilidades) em uma região
geográfica limitada é caracterizado na literatura como modelos do tipo facility location[?].
De modo geral, esses problemas lidam com recursos que, quando distribuı́dos, sempre permanecerão no local da distribuição. Isso é o caso das organizações que tem que
construir edificações para o fornecimento do serviço ou produto.
Entretanto, esse trabalho visa atacar problemas onde os recursos distribuı́dos irão
se locomover para atender as demandas. Cooperativas de taxi, por exemplo, poderiam
oferecer um atendimento mais rápido (e mais barato para a cooperativa) se realizasse
a distribuição dos taxistas de forma bem planejada, para que cada demanda recebida
pudesse ser mais facilmente atendida. Atendimentos médicos de emergência podem ser
realizados cada vez mais rápidos se as ambulâncias estiverem distribuı́das em locais estratégicos. É importante notar que nesse tipo de problema, a facilidade deverá estar
preparada para atender a uma demanda local, de modo que chegar a um consumidor não
afaste a facilidade demais dos outros consumidores.
Segundo Benati e Laporte[?], problemas de otimização modelados como facility location são NP-Difı́ceis, tornando inviável até mesmo a solução de instâncias relativamente
pequenas. Dessa forma, esse trabalho visa buscar uma abordagem inteligente embasadas
em propostas feitas ao longo do tempo na literatura, de modo que seja viável a geração
de boas sugestões de distribuição de recursos de um determinado problema de localização
de facilidades.
2
Caracterı́sticas de problemas facility location
Os problemas de localização de facilidades abrangem uma grande quantidade de
aspectos que podem determinar diversos tipos de modelos e abordagens.
Segundo Klose e Drexl[?], os modelos desse tipo de problema podem ser classificados
em diversas formas:
1. Organização da região geográfica. A região geográfica pode ser representada
como um plano ou o problema pode permitir que a região seja mapeada para um
modelo discreto. Uma exploração maior sobre modelos contı́nuos e descritos poderão
ser vistos na sessão 3.
2. Objetivos. Os objetivos podem incluir a minimização de uma variável (como a
soma do custo de instalação de uma facilidade ou a soma das distâncias entre pontos de demanda e a facilidade mais próxima) ou a maximização de outra (como a
cobertura de uma facilidade).
Facility Location
3
3. Capacidade da facilidade. Os modelos facility location podem ou não ter que considerar a restrição de capacidade. Essa restrição se refere à capacidade de demanda
que uma facilidade tem. De fato, de acordo com Melkote e Daskin[?], modelos que
não possuem a restrição de capacidade podem ser vistos como modelos que possuem tal restrição, desde que a capacidade de cada uma das facilidades seja maior
ou igual à soma de todas as demandas do problema. Assim, uma facilidade teria
capacidade para atender todos os pontos de demanda, podendo então, essa restrição,
ser desconsiderada, restando apenas as demais restrições do problema.
4. Quantidade de estágios. A logı́stica de atendimento de demanda pode ter um
único estágio ou pode ter vários estágios. Modelos com apenas um único estágio são
aqueles onde todas as facilidades atendem diretamente aos clientes da organização.
Modelos multi-estágios são aqueles em que, além das facilidades que atendem aos
clientes, tem-se ainda facilidades que atendem à outras facilidades, como por exemplo, pontos de abastecimento de estoque. A quantidade de estágios nessa estrutura
é determinada pelo problema.
5. Quantidade de produtos/serviços. Os modelos podem contemplar facilidades
que forneçam apenas um tipo de produto/serviço ou que forneçam mais de um tipo
de produto/serviço. São ainda considerados modelos de um único produto/serviço
aqueles modelos em que os diversos produtos/serviços podem ser condensados em
um único produto/serviço.
6. Influência da demanda. A maioria dos problemas do tipo facility location consideram que a demanda existe independente da localização das facilidades. Entretanto,
em alguns casos, a demanda pode ser influenciada pela existência ou não de uma
facilidade.
7. Dinamismo. Modelos podem ser estáticos ou dinâmicos. Modelos estáticos buscam
otimizações para perı́odos especı́ficos. Modelos dinâmicos consideram o tempo como
fator determinante a ser considerado na otimização.
Ainda analisando as classificações de modelos facility location, segundo Farahani,
SteadieSeifi e Asgari[?], esses modelos ainda podem ser distinguidos segundo a quantidade
de critérios a serem otimizados. Eles apresentam um grande estudo sobre o estado-da-arte
de problemas facility location com múltiplos critérios.
Assim, as seguintes classificações podem ainda ser acrescentadas à lista:
• Modelos com múltiplos objetivos;
• Modelos com múltiplos atributos.
3
Modelos contı́nuos e discretos
Quando se fala em distribuir facilidades em uma região geográfica, a primeira decisão
a ser tomada é de como essa região será organizada. A abordagem e algoritmos utilizados,
bem como fatores de performance e complexidade estão totalmente dependentes da forma
como essa organização é tratada no problema.
Assim, pode-se classificar os modelos do tipo facility location em pelo menos dois
grupos: modelos contı́nuos e modelos discretos.
4
Facility Location
3.1
Modelos contı́nuos e o problema de Weber
O meio mais natural de se enxergar a solução para a questão é tratar o plano de
forma contı́nua, de modo que cada ponto do plano seja uma localização potencial onde
pode-se instalar uma facilidade.
Partindo dessa premissa, em 1909 A. Weber[?] propôs o problema de encontrar o
melhor ponto para instalar uma facilidade, de modo que a soma das distâncias (euclidiana)
entre todos os pontos de demanda e a facilidade instalada fosse minimizada.
No problema de Weber simples (PWS), a quantidade de facilidades a serem distribuı́das era apenas uma. Dessa forma, dado que dk (x, y) é a distância do ponto de
demanda k à facilidade localizada na posição (x, y) e que pk é o peso de um ponto de
demanda (podendo ser obtido por uma função que considere diversos aspectos como prioridade, custo, frequência de uso da facilidade, etc.), o problema de otimização poderia
ser descrito conforme (1).
X
pk dk (x, y)
(1)
v(PWS ) = min(x,y)
k∈K
Se o plano for dividido em coordenadas discretas, a solução para o problema de
otimização (1) poderia ser facilmente implementada com o uso de um simples algoritmo
iterativo, como apresentado no Algoritmo 1.
Algoritmo 1: PWS (K)
Entrada: vetor K[(x1 , y1 ), (x2 , y2 )...] de coordenadas (k x , ky ) dos
pontos de demanda
Saı́da: coordenadas (x, y) do melhor posicionamento para a
facilidade
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
xMaior ← maior valor de coordenada x do vetor K
xMenor ← menor valor de coordenada x do vetor K
yMaior ← maior valor de coordenada y do vetor K
yMenor ← menor valor de coordenada y do vetor K
somaMenor ← ∞
para x ← xmenor até xMaior faça
para y ← ymenor até yMaior faça
soma ← 0
para cada k ∈ K faça
soma ← soma+ distância entre pontos (k x , ky ) e (x, y)
fim
se soma < somaMenor então
somaMenor ← soma
xS olucao ← x
yS olucao ← y
fim
fim
fim
retorna (xS olucao, yS olucao)
Percebe-se que a quantidade de operações necessárias para se encontrar a melhor
solução para o problema de Weber simples é O(x ∗ y ∗ k), onde x é a quantidade de colunas
5
Facility Location
do plano, y é a quantidade de linhas e k é a quantidade de pontos de demanda. Assim, o
problema de Weber simples possui uma solução iterativa eficiente.
Entretanto, é mais comum que problemas reais requeiram a distribuição de mais de
uma facilidade no plano. Dessa forma, uma extensão do problema de Weber simples é um
problema onde a quantidade de facilidades seja maior que 1. Essa extensão é chamada de
problema de Weber com múltiplas fontes (PWM).
O problema PWM consiste em distribuir n facilidades em uma determinada região
geográfica com os pontos de demanda K e alocar cada ponto de demanda à uma facilidade
especı́fica. Esse problema pode ser descrito conforme (2).
v(PW M) = min
p
XX
(2a)
pk dk (x, y)zk j
k∈K j=1
sujeito à
p
X
zk j = 1
∀k ∈ K,
(2b)
zk j ∈ {0, 1}
∀k ∈ K, j = 1, ..., p,
(2c)
j=1
onde zk j indica se o ponto de demanda k está sendo atendido pela facilidade j (zk j
assume valor 1) ou não (zk j assume valor 0), enquanto a restrição (2b) garante que somente
uma facilidade irá atender um ponto de demanda.
Dessa forma, avaliar todas as possibilidades de distribuição de uma facilidade em
um plano resultaria na execução de O((x ∗ y ∗ k)n ). Assim, analisando a quantidade de
facilidades n, pode-se perceber que a complexidade é exponencial.
3.2
Modelos discretos e modelos em rede
Uma grande parte dos problemas de localização podem ser modelados como problemas discretos, tendo em vista que um número limitado de pontos de localização é suficiente
para o espaço de busca da solução ótima. Os problemas de rede, por exemplo, constituem
de um tipo particular de problemas discreto.
Em problemas de localização de facilidades modelados em rede, as distâncias são
computadas como a menor distância em um grafo. De fato, muitos problemas de localização de facilidades podem considerar um número limitado de localizações como possı́veis
pontos de para a instalação de uma facilidade. Esses pontos são representados em um
grafo através dos vértices.
Segundo Klose e Drexl[?], um modelo de rede pode ser mapeado com um grafo,
onde os vértices representam os pontos de demanda e cada aresta que liga um vértice
representa uma ligação entre os dois pontos de demanda no problema real. Nesse contexto,
a distância entre um nó e outro é dada pela menor distância entre ambos no grafo. Um
subconjunto dos vértices desse grafo e mesmo pontos adicionais inseridos nas arestas do
grafo representam os possı́veis pontos de instalação de uma facilidade.
Em algumas abordagens, dependendo da função de distância adotada, como a de
[?], os pontos de localização de facilidades em potencial podem ser restritos ao próprio
conjunto de nós do grafo (pontos de demanda).
O problema de localização de facilidades modelado em rede correspondente ao problema de Weber com múltiplas fontes é conhecido como p-mediana. Nesse problema, buscase encontrar a localização de p medianas em um grafo, de modo que a soma das distâncias
6
Facility Location
entre todos os vértices (pontos de demanda) e a mediana mais próxima seja minimizada.
As medianas encontradas representarão, ao final, a localização das p facilidades que se
deseja distribuir.
O problema p-mediana pode ser formulado conforme apresentado em (3)
XX
v(PMed) = min
pk dk j zk j
(3a)
k∈K j∈J
sujeito à
X
zk j = 1
∀k ∈ K
(3b)
zk j − y j 6 0
X
yj = p
∀k ∈ K, j ∈ J
(3c)
j∈J
(3d)
j∈J
zk j , y j ∈ {0, 1}
∀k ∈ K, j ∈ J
(3e)
onde dk j representa a distância no grafo entre os vértices d e j, zk j indica se o ponto
de demanda k está sendo atendido pela facilidade j (zk j assume valor 1) ou caso contrário
(zk j assume valor 0) e y j indica se foi instalada uma facilidade no vértice j (y j assume
valor 1) ou não (y j assume valor 0).
Comumente, problemas de distribuição de facilidades em um plano (modelos contı́nuos) podem ser mapeados para um modelo de rede, de acordo com a conveniência em
se fazer essa conversão. Para isso, diversas abordagens podem ser utilizadas para a realização desse mapeamento, desde que os pontos de demanda resultem em vértices do grafo
e as arestas representem alguma ligação entre esses pontos de demanda.
Para problemas onde o negócio da organização pode enxergar os bairros de uma
cidade como unidades a serem tratadas individualmente, uma abordagem interessante
seria mapear cada bairro para um vértice do grafo e cada fronteira entre os bairros poderia
ser representado como uma aresta. O valor de cada aresta nessa abordagem, poderia ser,
por exemplo, a distância entre o ponto central de um um bairro ao ponto central do outro.
Em uma outra abordagem, o plano poderia ser discretizado em células que representariam os vértices. O problema de distribuição de facilidades em um plano poderia ser
mapeado para um problema de distribuição de facilidades em rede com alguns passos: a
discretização do mapa em células de tamanho igual; a identificação de células que contenham algum ponto de demanda; a ligação de células vizinhas; o grafo sairia das células
(vértices do grafo) e suas ligações com as células vizinhas (arestas do grafo). A Figura 1
mostra os passos dessa conversão.
Facility Location
7
Figura 1: Passos para um possı́vel mapeamento de pontos de demanda em um mapa
geográfico plotado em um plano cartesiano para uma representação em grafo. Em (a)
tem-se a configuração inicial do problema no plano, com a representação dos pontos de
demanda distribuı́dos pelo mapa de uma cidade (nesse caso, Goiânia); no passo (b) o
mapa é dividido em células de tamanhos iguais (nesse caso, optou-se por dividir em uma
grade de 8 x 8); em seguida, em (c), são identificadas as células que não possuem nenhum
ponto de demanda e as mesmas são excluı́das do espaço de solução; no passo seguinte (d),
cada célula que possui pelo menos um ponto de demanda recebe um vértice (ponto azul)
e os vértices gerados são ligados por arestas conforme alguma regra de fronteira entre as
células (nesse caso, optou-se como regra, considerar apenas fronteiras nos lados esquerdo,
direito, cima e baixo); o grafo gerado passa a ser o resultado da conversão (e), onde cada
aresta tem como valor, a distância euclidiana do centro de cada célula ao centro da célula
vizinha.
É importante notar que cada caso pode ser modelado de acordo com as caracterı́sticas do problema. A quantidade de células bem como a restrição de tamanhos serem iguais
podem ser alteradas conforme a necessidade. A polı́tica de atribuição das arestas também
pode ser adaptada, permitido, por exemplo, a criação de arestas diagonais ou proibindo
a criação de arestas que passem por células sem pontos de demanda.
Uma outra possı́vel abordagem poderia considerar identificar clusteres no mapa e
mapear cada centroide à um vértice. As arestas poderiam ser atribuı́das conforme alguma
regra estabelecida como, por exemplo, a parametrização de uma distância máxima entre
dois clusteres para a atribuição de uma aresta entre os mesmos.
Muitos problemas de localização de facilidades podem ser naturalmente mapeados
para um modelo de rede, sem exigir nenhuma conversão do plano para o grafo. O problema
de distribuição de transformadores em uma rede elétrica é um exemplo. Cada transformador deverá abastecer à uma quantidade determinada de pontos de consumo. Assim,
cada ponto de consumo representa um vértice em um grafo enquanto as arestas podem
ser representadas pelas ligações fı́sicas existentes entre esses pontos de consumo. Um
outro exemplo são as linhas de trânsito do transporte coletivo. Tomando como caso as
Facility Location
8
linhas de ônibus, o problema está em decidir onde inserir pontos de parada dos ônibus do
transporte coletivo de modo que os pontos de demanda (bairros contemplados pela linha)
sejam atendidos da maneira mais satisfatória possı́vel.
4
Critérios e objetivos
Os modelos de localização de facilidades buscam sempre otimizar algum critério
em sua função objetivo. A maioria dos modelos busca atingir um único objetivo. Em
geral, trata-se de minimizar uma variável, como a soma das distâncias entre os pontos de
demanda e a facilidade mais próxima, ou maximizar a cobertura de atendimento de uma
facilidade.
Entretanto, diversos problemas podem exigir uma abordagem que considere a
otimização de mais de um objetivo. Assim, de acordo com Farahani, SteadieSeifi e Nasrin
Asgari[?], os modelos podem ainda ser classificados quanto aos seus objetivos.
Antes de buscar uma solução para um problema multi-critério, alguns passos iniciais
são necessários:
• Verificar conflitos entre os objetivos. Geralmente modelos com mais de um objetivo tendem a ter conflitos em seus objetivos. Como exemplo, um problema pode
requerer minimizar a soma das distâncias entre pontos de demanda e a facilidade
mais próxima ao mesmo tempo em que pode requerer a minimização da maior distância entre um ponto de demanda e a facilidade mais próxima.
• A eficiência de uma solução. Esse ponto é referente ao fato de que uma abordagem
deve se preocupar com todos os objetivos, pois uma abordagem só será considerada eficiente se produzir soluções que otimize todos os objetivos, de modo que um
objetivo não serja superotimizado em detrimento de outro.
• A definição de uma solução preferida. Essa definição auxiliará no desenvolvimento
do modelo, de modo que as soluções geradas pela abordagem sejam capazes de
gerar aquele tipo de solução. Uma abordagem interessante é a de tentar converter
um problema multi-objetivo em um problema com apenas um objetivo.
Objetivos comuns para problemas de localização de facilidades, incluem: minimizar
o custo total; minimizar a maior distância de um ponto de demanda à facilidade mais
próxima; minimizar o custo fixo, que é o custo fixo de instalar uma facilidade em um ponto
especı́fico; maximizar a quantidade de serviço; minimizar a média de tempo ou distância
percorrida; minimizar o maior tempo ou distância percorrida; minimizar o número de
facilidades instaladas, diminuindo assim o custo de investimento; dentre outros objetivos.
Farahani[?] divide os problemas de localização com multi-critérios em problemas
multi-objetivos e problemas multi-atributos. Os problemas bi-objetivos são aqueles que
possuem sempre dois objetivos e, são um caso particular dos problemas multi-objetivos.
Os demais problemas dessa classe são chamados de problemas de localização k-objetivos.
Esse relatório não se aprofundará no assunto acerca de problemas com multicritérios. Para referências, a revisão da literatura feita por Farahani[?] é bastante vasta e
atualizada.
Facility Location
5
9
Algumas abordagens e algoritmos para solução de
problemas facility location
Os problemas de localização de facilidades tendem a abranger uma grande diversidade de possibilidades, podendo alcançar todo tipo de organização e seus vários contextos
para seus produtos providos e/ou serviços prestados.
Dessa forma, é improvável que exista um algoritmo que resolva todos os problemas
de um determinado modelo, sendo a solução, totalmente dependente do problema.
Entretanto, existem diversas abordagens que podem ser aplicadas à modelos especı́ficos, auxiliando assim na implementação de uma solução.
Essa sessão irá apresentar algumas propostas de abordagens para a solução de alguns
problemas de localização de facilidades.
5.1
Clusteres e o algoritmo k-means
A distribuição de K facilidades em um plano, como visto na sessão 3.1, é um problema de modelo contı́nuo. Em muitas abordagens para resolver esse tipo de problema,
um passo preliminar é encontrar os clusteres existentes no plano. Uma abordagem por
força bruta poderia ser definida por encontrar os clusteres por meio de um algoritmo iterativo, como o apresentado no Algoritmo 1. Entretanto, como já mencionado antes na
sessão 3.1, essa atividade que avalia todas as possibilidades e encontra os K clusteres seria
impraticável dado o número de comparações a serem realizadas.
Em 1967, MacQueen[?] introduziu o método k-means. O método k-means é, na
verdade, um algoritmo classificador. O seu propósito é o de encontrar clusteres nos dados,
onde cada cluster encontrado representa uma classe. Esse método é uma técnica de
mineração de dados do tipo não-supervisionada. Isso significa que o k-means não precisa
ser parametrizado e nem acompanhado. De modo geral, toda a informação necessária
como entrada para esse método restringe-se ao conjunto de dados amostral. A partir
desse conjunto, é possı́vel realizar a classificação.
Mahajan, Nimbhorkar e Varadarajan[?] apresentaram uma prova de que o problema
k-means no plano é NP-Difı́cil, realizando a redução através do problema 3-SAT2 .
Portanto, para resolver esse problema, é necessário o uso de boas meta-heurı́sticas
que sejam capazes de obter bons resultados em um tempo aceitável.
5.1.1
Abordagens para solução do problema k-means
O algoritmo k-means foi concebido inicialmente como uma abordagem não determinı́stica. Trata-se de um algoritmo bastante simples, rápido e eficiente que busca encontrar os centroides dos clusteres e pode ser resumido nos seguintes passos:
• Passo 1: Gerar valores iniciais para os centroides. Nesse passo, cada um dos k
centroides são distribuı́dos no espaço n-dimensional (geralmente de forma aleatória).
• Passo 2: Gerar uma matriz An×k , onde n é a quantidade de pontos de demanda e
Ai j tem o valor da distância (geralmente euclidiana) entre o ponto de demanda i e o
centroide j. Essa distância considera todos os atributos utilizados para determinar
um ponto. No caso do problema de distribuição de facilidades no plano, esses
atributos são apenas 2: as coordenadas x e y.
2
O 3-SAT é um problema da classe NP-Completo[?].
Facility Location
10
• Passo 3: Atribuir cada ponto de demanda ao centroide mais próximo. Nesse ponto,
o algoritmo termina se nenhum ponto de demanda mudar de centroide em relação ao
centroide a que estava atribuı́do anteriormente. Caso contrário, o algoritmo segue
para o próximo passo.
• Passo 4: Calcular os novos centroides. Cada um dos k centroides é movimentado
para o centro de cada cluster. Assim, cada atributo que define as coordenadas de
um centroide, assume como valor, a média de todos os valores desse mesmo atributo
dos pontos a ele atribuı́dos.
• Passo 5: Repetir até a convergência. O algoritmo volta ao Passo 2 a irá continuar
sua execução até que seja atingida a convergência.
Esse método converge bem rápido. Entretanto, nota-se que a qualidade o resultado está diretamente relacionada à distribuição inicial. Assim, o algoritmo k-means não
garante a convergência para a melhor configuração de localização dos centroides. Existem muitas abordagens para encontrar a solução desse problema por meio de artifı́cios
que busquem melhorar os resultados alcançados pelo algoritmo k-means. Kaveh, Zadeh
e Sahraeian[?], por exemplo, sugerem um algoritmo para resolução de um problema de
localização de facilidades que utiliza o k-means para gerar uma solução inicial e, para
melhorar os resultados obtidos nessa solução inicial, o algoritmo k-means é executado
várias vezes.
Contudo, mesmo rodando várias vezes, o k-meanscontinua gerando soluções que
convergem para um ótimo local, quando o desejado é um resultado que venha a convergir
para um ótimo global. Assim, existem diversas abordagens propostas para a busca de
uma convergência global. Somente para ilustrar, algumas serão apresentadas a seguir.
Em 1999, Krishna e Murty[?] propuseram uma versão do k-means utilizando algoritmos genéticos e que gera resultados que convergem para um ótimo global. Nesse
algoritmo, que foi batizado de GKA (Genetic K-Means Algorithm), a codificação do cromossomo utilizada foi um vetor C de tamanho n, onde n é a quantidade de pontos e cada
Ci assume um valor de 1 à k. Assim, cada cromossomo representa os pontos e a qual
centroide cada um está ligado. Essa codificação só é possı́vel porque cada ponto só pode
estar relacionado a um e somente um dos k centroides.
A população inicial é criada a partir de configurações aleatórias e execuções do kmeans clássico. A mutação ocorre selecionado alguns pontos de uma solução e somando
ao complemento de outra solução, tendo assim, uma nova solução. A partir daı́, os k
centroides são então recalculados novamente, baseando-se na sua nova configuração. A
convergência é atingida depois de um número parametrizado de iterações.
Yi Lu, Shiyong Lu, Fotouhi e DengBrown[?] criaram, em 2004, melhorias para o
GKA e batizaram o novo algoritmo de FGKA (Fast Genetic K-means Algorithm). Assim
como seu antecessor, o FGKA também converge para um ótimo global mas, segundo os
autores, o algoritmo faz isso muito mais rápido, graças às mudanças nos operadores de
mutação e seleção.
Likas, Vlassis e Verbeek[?] propuseram um algoritmo com convergência global que
possui um tempo de processamento consideravelmente mais longo que o k-means clássico,
mas ainda assim, com um bom desempenho. Trata-se de um algoritmo iterativo que
executará o k-means diversas vezes seguindo uma estratégia bem definida.
Primeiro, o k-means clássico é rodado com k = 1 para se encontrar a solução ótima
para k = 1. Em seguida, o k-means é rodado N vezes para k = 2, obedecendo a seguinte
Facility Location
11
regra: a posição inicial do primeiro centroide é sempre a posição ótima para k = 1 calculada
anteriormente. A posição inicial do segundo centroide é aleatória para a primeira rodada
do k-means e, a partir da segunda rodada, a posição inicial do segundo centroide passa a
ser a localização final do mesmo centroide na rodada anterior.
Assim, à medida em que vão sendo adicionados centroides para que o algoritmo
k-means execute N vezes com a nova quantidade de centroides, a estratégia de posicionamento inicial dos centroides continua a mesma: quando k = j, o algoritmo k-means irá ser
executado N vezes e, nessas N vezes, os primeiros j − 1 centroides assumem como posição
inicial, a posição ótima encontrada para k = j − 1, enquanto o j-ésimo centroide inicia em
uma posição aleatória na primeira rodada do k-means e, a partir da segunda rodada até
a última, a sua posição é a posição ótima encontrada na rodada anterior.
Esse algoritmo termina sua execução quando executa a última das N rodadas para
a quantidade de centroides k desejada.
Uma grande vantagem desse algoritmo é que, além de resolver o problema k-means ,
encontrando uma solução que converge para um ótimo global, ainda possibilita resolver
um outro problema: encontrar a quantidade de centroides necessárias para minimizar o
custo total. Ou seja, encontrar o valor de K. O mesmo algoritmo aqui descrito poderia
ser executado sem se limitar à quantidade K. Assim, o ponto de parada seria o valor do
custo desejado. O retorno seria o valor K e o posicionamento desses centroides.
5.2
Busca Tabu
Al-Sultan e Al-Fawzan[?] apresentaram uma abordagem baseada em uma Busca
Tabu para resolver o problema de localização de facilidades sem restrição de capacidade
e sugerir a quantidade de facilidades a serem instaladas. No problema atacado pelos
autores, o custo de instalação de uma facilidade é levado em consideração.
Nessa abordagem, além das informações atuais, um breve histórico de soluções encontradas é armazenado para evitar um recálculo desnecessário. Assim, essas soluções
armazenadas passam a compor os movimentos tabu4 .
Primeiramente, busca-se uma solução inicial para o problema. Para essa solução
inicial, cada ponto de demanda passa a ser atendido pela facilidade instalada mais próxima. Em seguida, começa a fase de remoção de facilidades. Nessa fase, cada facilidade
é analisada quanto à possibilidade de sua remoção. A remoção vai acontecer se o custo
total da solução (soma das distâncias de pontos de demanda à facilidade mais próxima e
soma dos custos de instalação das facilidades) diminuir com a remoção da mesma.
Após a criação dessa solução inicial, é iniciada a busca de soluções vizinhas melhores.
Essa abordagem não é amarrada e deixa aberta a forma como essa exploração é realizada.
Uma possibilidade é a de substituir algumas facilidades por outro ponto aleatório. Outra
maneira de formular a vizinhança é considerar que cada nova solução alcançada pelo
movimento de uma unidade de espaço de uma facilidade rumo à alguma direção faz parte
3
3
Busca Tabu (Tabu Search)[?] é um método meta-heurı́stico de busca de soluções para problemas
exponenciais que utiliza alguns artifı́cios para evitar que a busca convirja muito precocemente, dando
ao algoritmo, mais tempo para explorar novas soluções, seguindo caminhos de soluções piores do que a
melhor encontrada até o momento. A Busca Tabu utiliza uma lista de soluções visitadas (Lista Tabu)
que visa evitar que soluções recentes sejam recalculadas. O critério de parada é uma quantidade k de
passos dados sem encontrar nenhuma nova solução que seja melhor.
4
Em uma busca tabu, um movimento tabu é aquele que não pode ser realizado. Em outras palavras,
é uma solução que não pode ser considerada na busca, pois passar nessa solução novamente iria gerar um
ciclo e, consequentemente, a convergência.
12
Facility Location
da vizinhança atual.
Por fim, a abordagem assume que o algoritmo deve parar quando atingir algum
limite de iterações sem que haja melhoria nas soluções encontradas.
5.3
Aproximações para o problema das p-medianas
O problema das p-medianas, formulado em (3), é objeto de constante pesquisas
e existem diversos trabalhos que apresentam abordagens para a solução desse tipo de
problema. A seguir, algumas dessas abordagens serão apresentadas.
5.3.1
Algoritmo de Teitz e Bart
Dado um conjunto V de nós (vértices) em uma rede, Teitz e Bart[?] apresentaram
um algoritmo simples para o problema das p-medianas, onde espera-se encontrar um
subconjunto V 0 (onde |V 0 | = p) dos nós da rede de modo que a soma de todas as distâncias
entre os nós de V e o nó de V 0 mais próximo fosse minimizado.
Esse algoritmo, é inicializado com uma solução S aleatória tal que S ⊂ V e |S | = p.
A partir dessa solução inicial, é realizada uma varredura pelos demais vértices do conjunto
V, objetivando encontrar um vértice vi ∈ (V − S ) que possa substituir um vértice v j ∈ S
tal que a soma das distâncias entre todos os nós de V e o nó mais próximo em (S ∪ vi ) − v j
seja menor que a soma das distâncias entre todos os nós de V e o nó mais próximo em
S . O algoritmo termina quando não houver mais nenhuma substituição que produza uma
soma de distâncias menor que a atual.
É notório que esse algoritmo busca encontrar uma melhor solução, mas pode demorar muito para convergir. Assim, muitas outras meta-heurı́sticas surgiram para buscar
boas aproximações sem demandar muito tempo para a convergência. Uma alternativa é
relaxar o problema em alguma de suas restrições. A seguir, será apresentada a relaxação
lagrangeana/surrogate, que se mostra bastante conveniente para resolver o problema de
localização de facilidades.
5.3.2
O uso da relaxação lagrangeana/surrogate
Senne, Lorena e Pereira[?] propuseram um algoritmo branch-and-price 5 que faz uso
da relaxação lagrangeana/surrogate 6 para resolver o problema das p-medianas.
Nesse trabalho, o problema das p-medianas foi convertido em um problema de partição de conjuntos com uma restrição de cardinalidade. O problema então passa a ser
formulado como em (4).
v(S PPmed) = min
m
X
ck xk
(4a)
k=1
sujeito à
5
Branch-and-price é um método de geração de colunas em uma árvore de busca proposto por
Barnhart[?].
6
A relaxação lagrangeana/surrogate é um tipo de relaxação voltada para diversos problemas de
otimização de programação inteira, incluindo problemas de localização. Essa relaxação foi criada por
Greenberg e Pierskalla[?]
13
Facility Location
m
X
k=1
m
X
Aik xk = 1
∀i ∈ S ,
(4b)
xk = p,
(4c)
xk ∈ {0, 1},
(4d)
k=1
onde N é o conjunto de todos os nós da rede, S = {S 1 , ..., S m } é o conjunto de todos os
subconjuntos de N, A = [aik ]n×m é uma matriz que indica a qual subconjunto pertence cada
nó (aik = 1 se i ∈ S k e aik = 0 caso contrário), xk indica se o subconjunto k foi selecionado
P
como parte da solução e ck = min j∈S k ( i∈S k di j ). A relaxação utilizada pelos autores foi na
substituição da restrição (4d) pela restrição xk ∈ [0, 1].
5.4
Aproximações para o problema das p-medianas capacitado
Uma restrição bastante recorrente em muitos problemas de localização de facilidades
é a capacidade que uma facilidade tem para poder atender os pontos de demanda. Os
algoritmos clássicos para solução de problemas de localização geralmente não consideram a
capacidade de atendimento e, dessa forma, podem gerar soluções ótimas, porém, inviáveis.
Dessa forma, a restrição de capacidade deve ser sempre levada em consideração,
quando o problema do mundo real tem essa restrição. Exemplos clássicos de facilidades
que possuem essa caracterı́sticas são as redes de telefonia e redes elétricas, onde cada
facilidade (uma antena ou um transformador) tem uma capacidade que limita o tamanho
da demanda que pode atender.
Portanto, para resolver problemas dessa natureza, algoritmos mais elaborados se
fazem necessários.
Kaveh, Zadeh e Sahraeian[?] introduziram um algoritmo hı́brido, que mescla o uso
do algoritmo k-meanscom o algoritmo FNS (Fixed Neighborhood Search). Esse algoritmo
tem o objetivo de resolver o problema das p-medianas capacitado no qual cada ponto
de demanda pode ser alocado a somente uma facilidade. A formulação do problema é
apresentada em (5)
XX
v(CPMed) = min
ci j xi j
(5a)
i∈N j∈J
sujeito à
X
xi j = 1
∀i ∈ N,
(5b)
j∈J
X
y j = p,
(5c)
j∈J
X
ci j xi j 6 b j y j
∀ j ∈ J,
(5d)
∀i ∈ N, ∀ j ∈ J,
(5e)
i∈N
xi j ∈ {0, 1}, y j ∈ {0, 1}
onde xi j assume valor 1, se o ponto de demanda i está alocado à facilidade j e 0, caso
contrário; y j indica se no ponto j foi (assume valor 1) ou não (assume valor 0) instalada
uma facilidade; e b j representa a capacidade da facilidade j. A restrição (5d) é o que
Facility Location
14
garante que a capacidade da facilidade j jamais irá ser extrapolada pela demanda alocada
à ela.
O algoritmo proposto utiliza o algoritmo k-means para gerar uma solução inicial,
que irá servir de entrada para o algoritmo FNS. Como já mencionado antes, o k-means é
um algoritmo que não garante a solução ótima. Por essa razão, a abordagem utilizada
executa o k-means 20 vezes iniciando o mesmo em posições aleatórias. Evidentemente, a
quantidade de clusteres que se deseja encontrar é p (K = p). Para otimizar os resultados,
garantindo que será encontrada a mediana, o k-means executado aqui tem a função de
distância alterada. O valor utilizado para comparação é a distância elevada ao quadrado.
Assim, garante-se que a mediana será encontrada.
Depois de executar o k-means 20 vezes, o algoritmo seleciona a melhor solução.
Então, para cada um dos k clusteres identificados isoladamente, é executado um algoritmo
simples de solução do problema p-mediana (p = 1) com a finalidade de encontrar o melhor
nó para cada um dos k clusteres encontrados. Nesse ponto, o algoritmo tem a sua solução
inicial S .
No próximo passo, o algoritmo FNS é executado com a solução inicial S . Aqui, o
conceito de vizinhança é definido como: “a k0 -ésima vizinhança de uma solução são todas
as soluções que diferem da solução corrente em exatamente k0 facilidades.”
Dada uma função f (x) que retorna o valor do custo total de uma solução x, o
algoritmo FNS pode ser descrito conforme os passos do Algoritmo 2.
Algoritmo 2: FNS (k0 , maxiter, N)
Entrada: valor inteiro k0 que vai determinar o tamanho da
vizinhança; maxiter (que vai indicar quando o
algoritmo irá parar); o conjunto de pontos de demanda
N
Saı́da: solução S contendo os pontos de localização das
facilidades
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
S ← solução inicial do problema dada pelo algoritmo k-means
enquanto Não convergir faça
Vizk0 (S ) ← a k0 -ésima vizinhança de S
para cada S 0 ∈ Vizk0 (S ) faça
se f (S 0 ) < f (S ) então
S ← S0
r←1
sai do laço “para cada”
fim
se f (S 0 ) > f (S ) então
r ←r+1
se r > maxiter então
retorna S
fim
fim
fim
fim
Esse algoritmo foi então adaptado para o problema das p-medianas capacitado para
otimizar a escolha das novas soluções[?].
Facility Location
15
A primeira alteração foi na forma como os nós são selecionados no momento em
que a k0 -ésima vizinhança é gerada. No algoritmo FNS original (Algoritmo 2), todas as
possibilidades seriam geradas. A modificação realizada exclui alguns pontos do espaço de
busca. E isso pode ser feito de duas formas diferentes. Na primeira, k0 pontos são removidos da solução corrente e, a seleção dos novos k0 pontos irá considerar todos os demais
pontos que não possuem facilidade instalada, com exceção dos h nós mais próximos de
cada um dos k0 pontos selecionados. O valor de h deve ser parametrizado empiricamente,
por tentativa e erro.
A segunda alternativa é excluir os pontos mais periféricos, pois esses tendem a não
serem escolhidos para a solução final. Aqui, mais uma vez, os limites de periferia devem
ser parametrizados empiricamente.
A Figura 2 mostra o resultado dessas duas abordagens para a exclusão de pontos na
geração da vizinhança.
Figura 2: Identificação de nós candidatos à substituição na geração da vizinhança. Inicialmente, tem-se a solução corrente (a) onde os pontos azuis representam as facilidades
instaladas. Para k0 = 2, em (b), (c) e (d), são selecionadas duas facilidades para serem
removidas. Em (b), a vizinhança passa a ser gerada a partir de todos os demais pontos
(brancos). Em (c), para um h = 3, são selecionadas os três pontos mais próximos para
serem excluı́dos do espaço de solução (pretos). Em (d), as linhas pontilhadas delimitam
as margens periféricas, onde estarão os pontos excluı́dos.
A segunda alteração no algoritmo FNS foi o critério de parada. Antes, o critério
de parada era quando atingia a quantidade de iterações realizadas sem melhoria no custo
total. Agora, todas as k0 soluções da vizinhança deverão ser analisadas e o algoritmo só
para se nenhuma dessas soluções for melhor que a solução corrente.
Por fim, a última alteração realizada foi a adição de memória ao algoritmo, acrescentando uma lista tabu para armazenar soluções e evitar o recálculo de soluções já visitadas.
Facility Location
6
16
Aplicações
É notória a aplicação de modelos facility location a problemas de distribuição de
facilidades em uma região geográfica. Entretanto, de acordo Klose e Drexl[?], uma série
de ouras possı́veis aplicações podem fazer uso dos modelos de localização de facilidades.
A análise de clusteres para a identificação de classes distintas baseando-se em atributos diversos de uma grande quantidade de dados é uma atividade que já foi mapeada
como um problema das p-medianas.
A seleção de vendedores e a alocação dos mesmos aos produtos pode ser mapeado
para um modelo de localização. Identificar um conjunto de vendedores para vender um
determinado produto representa um problema de multi-critérios, onde devem ser levados
em conta a experiência do vendedor, o preço do produto que se deseja alocar, a qualidade
do mesmo, dentre outras.
Em alguns problemas, a organização não deseja oferecer um produto/serviço para
uma demanda especı́fica, mas explorar um produto/serviço de diversas fontes. Um exemplo de casos assim é o de encontrar a melhor localização para plataformas de exploração
de petróleo. Se o custo de instalação de uma plataforma fosse irrelevante, certamente
haveriam plataformas por toda a região que fosse rica em petróleo. Entretanto, esse custo
é muito relevante e, encontrar a melhor localização para a instalação de p plataformas,
bem como o tamanho de cada uma, pode ser facilmente mapeado para um problema de
localização de facilidades.
A localização de um servidor de banco de dados em uma rede de computadores pode
ser mapeada para um problema de p-medianas onde p = 1 em uma rede.
Assim, pode-se perceber que diversos problemas que, a princı́pio, não parecem se
enquadrar em algum modelo facility location, poderiam ser mapeados para um problema
de localização e ser resolvido com a ajuda de alguma das tantas abordagens que já foram
publicadas.
7
Conclusão
O problema de localização de facilidades em uma região geográfica é pertinente aos
mais diversos tipos de organizações: indústrias que buscam viabilizar o fornecimento de
produtos industrializados aos distribuidores, sem inviabilizar o recebimento de matéria
prima; grandes organizações comerciais, como redes de supermercado, que visam atender
o maior número de clientes; empresas de distribuição de energia elétrica; órgãos de saúde
e segurança pública; empresas de transporte; dentre outros tantos tipos de organizações,
cuja qualidade do serviço está diretamente ligada à uma distribuição ótima de facilidades.
Tais problemas de localização são conhecidos como NP-Difı́cil. Assim, uma grande
atenção tem sido voltada para essa área da Pesquisa Operacional. Não é uma necessidade
recente, sendo ela estudada desde o inı́cio do século XIX[?]. Entretanto, um grande salto,
no que diz respeito à quantidade de pesquisas realizadas e abordagens sendo criadas,
aconteceu nos últimos quinze anos, com um grande interesse sobre o assunto sendo cada
vez mais evidente.
Contudo, mesmo diante de tanto empenho por parte da comunidade de Pesquisa
Operacional, fica claro que os diversos modelos de localização de facilidades ainda deixam
muitas lacunas, abrindo espaço para novas abordagens. Percebeu-se que, mesmo com a
louvável iniciativa de separar os problemas em modelos bem definidos, diversas abordagens
poderiam ser bastante eficientes para um tipo especı́fico de problema, mas sendo inviáveis
Facility Location
17
para outros tipos. Dessa forma, conclui-se que, embora as abordagens existentes possam
ser utilizadas parcialmente, totalmente ou combinadas com outras, cada caso deve ser
analisado com suas particularidades.
Conclui-se também que existem muitas possibilidades de evolução das pesquisas
nessa área, tendo em vista que diversas boas novas abordagens foram propostas com a
simples junção de duas ou mais abordagens anteriormente publicadas ou com alguma
adaptação e/ou melhorias em cima de uma outra abordagem.
8
Agradecimento
À Profa. Dra. Telma Woerle de Lima Soares, pela avaliação do presente texto e
pelas sugestões feitas, as quais muito contribuı́ram para a melhoria do texto original.
Referências
[1] Al-Sultan, K.; Al-Fawzan, M. A tabu search approach to the uncapacitated facility location problem. Annals of Operations Research, 86:91–103, 1999.
10.1023/A:1018956213524.
[2] Barnhart, C.; Johnson, E. L.; Nemhauser, G. L.; Savelsbergh, M. W. P.; Vance, P. H.
Branch-and-price: Column generation for solving huge integer programs.
Operations Research, 46:316–329, 1996.
[3] Benati, S.; Laporte, G. Tabu search algorithms for the (r|xp)-medianoid and
(r|p)-centroid problems. Location Science 2, 1994.
[4] Cook, S. A. The complexity of theorem-proving procedures. In: Proceedings
of the third annual ACM symposium on Theory of computing, STOC ’71, p. 151–158,
New York, NY, USA, 1971. ACM.
[5] Farahani, R. Z.; SteadieSeifi, M.; Asgari, N. Multiple criteria facility location
problems: A survey. Applied Mathematical Modelling, 34(7):1689 – 1709, 2010.
[6] Glover, F.; Laguna, M. Tabu search, p. 70–150. John Wiley & Sons, Inc., New
York, NY, USA, 1993.
[7] Greenberg, H. J.; Pierskalla, W. P. Surrogate mathematical programming.
Operations Research, 18(5):924–939, September/October 1970.
[8] Hakimi, S. L. Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems. OPERATIONS
RESEARCH, p. 462–475, 1965.
[9] Klose, A.; Drexl, A. Facility location models for distribution system design.
European Journal of Operational Research, 162(1):4 – 29, 2005. Logistics: From
Theory to Application.
[10] Krishna, K.; Narasimha Murty, M. Genetic k-means algorithm. Systems, Man,
and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 29(3):433 –439, jun
1999.
Facility Location
18
[11] Likas, A.; Vlassis, N.; Verbeek, J. J. The global k-means clustering algorithm.
Pattern Recognition, 36(2):451 – 461, 2003.
[12] Lu, Y.; Lu, S.; Fotouhi, F.; Deng, Y.; Brown, S. J. Fgka: a fast genetic k-means
clustering algorithm. In: Proceedings of the 2004 ACM symposium on Applied
computing, SAC ’04, p. 622–623, New York, NY, USA, 2004. ACM.
[13] MacQueen, J. B. Some methods for classification and analysis of multivariate
observations. In: Cam, L. M. L.; Neyman, J., editors, Proceedings of the fifth
Berkeley Symposium on Mathematical Statistics and Probability, volume 1, p. 281–
297. University of California Press, 1967.
[14] Mahajan, M.; Nimbhorkar, P.; Varadarajan, K. The Planar k-Means Problem is
NP-Hard. In: Das, S.; Uehara, R., editors, WALCOM: Algorithms and Computation, volume 5431 de Lecture Notes in Computer Science, p. 274–285. Springer
Berlin / Heidelberg, 2009.
[15] Melkote, S.; Daskin, M. S. Capacitated facility location/network design problems. European Journal of Operational Research, 129(3):481 – 495, 2001.
[16] Melo, M.; Nickel, S.; da Gama, F. S. Facility location and supply chain management - A review. European Journal of Operational Research, 2009.
[17] Payman Kaveh, A. S. Z.; Sahraeian, R. Solving Capacitated P-median Problem
by Hybrid K-means Clustering and FNS Algorithm. International Journal
of Innovation, Management and Technology, 2010.
[18] Senne, E. L. F.; Lorena, L. A. N.; Pereira, M. A. A branch-and-price approach
to p-median location problems. Computers & Operations Research, 32(6):1655
– 1664, 2005.
[19] Teitz, M. B.; Bart, P. Heuristic methods for estimating the generalized vertex
median of a weighted graph. Operations Research, 16(5):955–961, September/October 1968.
[20] Weber, A.; Pick, G. Ueber den Standort der Industrien. Ueber den Standort
der Industrien. J.C.B. Mohr (Paul Siebeck), 1909.