IX SEPROSUL – Semana de Engenharia de Produção Sul-Americana
Novembro de 2009, Piriápolis, Uruguai
Problema das p-Medianas Capacitado: Estudo Sobre a
Resolução de Instâncias por Métodos Exatos
Fernando Stefanello (PPGI/UFSM)
Felipe Martins Müller (PPGI-PPGEP/UFSM)
Olinto César Bassi de Araújo (CTISM/UFSM)
Resumo
Este trabalho apresenta um estudo empírico sobre características determinantes na dificuldade de resolução de
instâncias do problema das p-medianas capacitado por métodos exatos. De modo geral, o objetivo deste
problema é obter agrupamentos de pontos distribuídos em um plano com auxílio de medidas de distância ou
similaridade, considerando restrições de capacidade, de modo a minimizar a distância entre uma mediana e
seus respectivos pontos. Alterações de parâmetros das instâncias propostas na literatura são utilizadas para
inferir a dificuldade de resolução por métodos exatos. Experimentos computacionais demonstram que, para as
instâncias consideradas, a distribuição geográfica dos pontos com maior demanda e a razão entre capacidade e
demanda total influenciam diretamente o desempenho de sistemas de otimização comerciais.
Palavras chave: Problemas de agrupamento capacitado. Problema das p-medianas capacitado. Conjunto de
instâncias de teste. Otimização Combinatória
1 Introdução
Problemas de agrupamento capacitado possuem diversas aplicações práticas, como a localização de fábricas,
hospitais, escolas e centros de coleta de lixo. Em todos esses casos, dado um conjunto de nós associado à
realidade que se deseja modelar, o objetivo é agrupá-los de forma a maximizar a dissimilaridade entre os
agrupamentos. Nesse contexto, ressalta-se o Problema das p-Medianas Capacitado (PPMC). Este problema
difere de problemas de alocação de facilidades basicamente em dois pontos: não existe custo para instalar uma
facilidade e existe um número definido de facilidades a serem instaladas.
O PPMC trata da alocação de p facilidades (medianas) para servir n pontos de demandas (nós). O objetivo é
minimizar a soma das distâncias entre os nós e as medianas, com a restrição de não exceder a capacidade de cada
mediana instalada. Para resolução, são observados os trabalhos que tratam heuristicamente o PPMC, reportandose às décadas de 80 e 90, com os estudos de Mulvey e Beck (1984), Osman e Christofides (1994) e Maniezzo et
al. (1998). Esse último propõe um método evolutivo, e o primeiro, algoritmos de simulated annealing e busca
tabu.
Mais recentemente, Baldacci et al. (2002) utilizam um novo método baseado na formulação de particionamento
de conjuntos. Lorena e Senne (2002) apresentam um método de geração de colunas. Ahmadi e Osman (2005)
propõem uma composição de meta-heurísticas em um framework denominado GRAMPS (Greedy Random
Adaptive Memory Search Method). Uma abordagem scatter search é utilizada por Scheuerer e Wendolsky
(2006) e Diaz e Fernandez (2006). Fleszar e Hindi (2008) resolvem o PPMC em duas etapas, a primeira usando
VNS para definir conjuntos de medianas e a segunda, o software CPLEX para o problema de atribuição. Boccia
et al. (2008) propuseram um algoritmo de planos de corte também resolvida pelo software CPLEX.
Nesse trabalho é apresentado um estudo mais aprofundado do tema delineado em Stefanello e Müller (2009)
sobre a resolução do PPMC com modelos matemáticos e sistemas de otimização comerciais. O objetivo é inferir
a dificuldade de resolução dos conjuntos de instâncias comumente utilizados na literatura científica assim como
avaliar alguns fatores que influenciam na dificuldade de resolução das mesmas. Na próxima seção, o PPMC é
definido formalmente e uma redução heurística de variáveis para lidar com as instâncias de grande porte é
proposta, de modo a possibilitar a obtenção de soluções de boa qualidade em tempos aceitáveis. Na seção 3, é
feito um estudo sobre os parâmetros que influenciam na dificuldade de resolução de uma instância. Os
experimentos computacionais são detalhados na seção 4. Por fim, na seção 5 e 6, são apresentadas conclusões
sobre o assunto e referências bibliográficas, respectivamente.
Problema das p-Medianas Capacitado:
Estudo Sobre a Resolução de Instâncias por Métodos Exatos
Stefanello & Müller & Araújo
1
IX SEPROSUL – Semana de Engenharia de Produção Sul-Americana
Novembro de 2009, Piriápolis, Uruguai
2 Problema das p-Medianas Capacitado
O PPMC é um problema de alocação de facilidades no qual dado um grafo G = (V,E), em que V representa o
conjunto de nós e E o conjunto de arcos com as distâncias entre os nós, deve-se encontrar um subconjunto de
vértices Vp
V tal que a soma das distâncias de cada vértice restante até a sua correspondente mediana em Vp
seja a menor possível e a restrição capacidade seja satisfeita. As primeiras formulações do problema foram
apresentadas em Hakimi (1964).
Esse problema é reconhecidamente NP-dificil (Garey & Johnson, 1979), o que sugere a inviabilidade do uso de
métodos exatos para a sua resolução. Diante disso, vários estudos utilizam métodos heurísticos para encontrar
soluções de boa qualidade em tempo computacional aceitável para uma tomada de decisão. No entanto, é
importante observar que a intratabilidade da questão não necessariamente ocorre em todas as instâncias do
problema, e uma escolha criteriosa do conjunto de instâncias deve ser feita para discriminar o desempenho dos
métodos heurísticos.
O PPMC pode ser formulado matematicamente conforme segue.
I : conjunto de índices dos nós
J : conjunto de índices dos nós candidatos a medianas
wij: variável binária para designar se o ponto i está associado ao agrupamento j;
dij: distância entre os nós i e j;
p: número de facilidades;
qi : demanda do ponto i;
n: número de pontos;
Qj: capacidade do agrupamento j.
Modelo P:
Min
d ij w ij
i I j
(P1)
J
Sujeito a:
w jj
j
p
(P2)
J
w ij
1
i
I
i
I,
j
J
i
I,
(P3)
j J
w ij
w jj
q i w ij
Q j w jj
j
J
(P5)
i I
w ij
{0,1}
(P4)
j
J
(P6)
A função objetivo é definida em (P1). As restrições (P2), (P3) e (P4) asseguram que cada nó é designado a
apenas uma mediana. A restrição (P5) determina que a capacidade das medianas deve ser respeitada, e a restrição
(P6) corresponde à condição de binariedade das variáveis.
As restrições (P4) e (P5) são redundantes, mas é conhecido que esta restrição (P4) melhora o desempenho do
resolvedor utilizado. Ainda que o uso dessas aumente o número de restrições avaliadas, observa-se que, dessa
maneira, o domínio do problema é reduzido, permitindo que sejam encontradas boas soluções num tempo
computacional menor do que sem o uso delas.
Para instâncias de maior porte, o uso de resolvedores torna-se inviável devido à grande quantidade de variáveis
envolvidas, e um arquivo em modo texto para instâncias com 3038 nós pode chegar a 800 MB de tamanho em
disco.
Diante disso, foi usada uma estratégia para eliminar heuristicamente variáveis com poucas chances de estarem
envolvidas na solução ótima. O modelo resultante é denominado Modelo Reduzido. Neste modelo, para todo nó
i, leva-se em conta apenas o k pontos mais próximos de i (desde que k possa ser associado a i), cujo somatório
das demandas seja inferior a uma dada capacidade atribuída ao nó, já subtraída de sua própria demanda,
conforme segue.
Problema das p-Medianas Capacitado:
Estudo Sobre a Resolução de Instâncias por Métodos Exatos
Stefanello & Müller & Araújo
2
IX SEPROSUL – Semana de Engenharia de Produção Sul-Americana
Novembro de 2009, Piriápolis, Uruguai
k
wj
αQ
j=1
em que α ≥ 1 é um fator de expansão da capacidade.
A aplicação dessa metodologia proporciona uma significativa redução do número de variáveis. Com tal redução,
apesar de não garantir a otimalidade, possibilita-se o tratamento de problemas de maior porte.
3 Parâmetros das instâncias que influenciam a dificuldade de resolução:
Conforme é demonstrado nos resultados computacionais, na sua maioria, é possível encontrar soluções ótimas
para as instâncias propostas na literatura com relativa facilidade por resolvedores comerciais. Dado esse fato,
vemos a necessidade de obter instâncias mais difíceis, pois estas sim poderão avaliar melhor as heurísticas que
são propostas para este problema (Silberholz e Golden, 2003).
Alterando parâmetros nas instâncias, foi possível observar que o tempo computacional gasto pelo resolvedor
para encontrar soluções ótimas ou reduzir o gap, quando não foi possível provar a otimalidade dentro de um
tempo pré-determinado, aumentou significativamente.
Dentre as modificações testadas, duas parecem ser críticas com relação ao aumento da dificuldade de resolução,
onde a primeira delas é a o aumento no Fator de ocupação (β) da instância e a segunda modificação é uma
alteração da designação das demandas para os pontos.
3.1 Sobre o Fator de Ocupação:
Definimos como Fator de Ocupação como β = ∑iєI qi / ∑ jєJ Qj, que indica quão restrito estão as demandas em
relação à capacidade das medianas.
Valores de β muito alto implicam em restrições menos folgadas, o que pode levar um gap maior entre a
relaxação do nó raiz e a solução ótima. Por outro lado, uma instância com valor de β pequeno, indica que as
restrições são folgadas.
Embora não seja uma regra, geralmente a resolução de instâncias com valor de β alto é mais difícil para
resolvedores comerciais. Assim, de acordo com nosso objetivo de gerar um conjunto de instâncias que sirva para
discriminar adequadamente métodos de resolução, estudamos o aumento a demanda em cada ponto e/ou a
redução da capacidade de cada mediana de modo a aumentar o valor de β.
O cálculo dos novos valores para um demanda i, denominado nqi , é dado da seguinte maneira: nqi = a*qi +b,
onde qi é a demanda atual do ponto i, a e b são coeficientes dados de acordo com o valor β desejado.
A segunda maneira de alterar a instância é alterar a capacidade das medianas. Supondo que a capacidade é igual
para todas as medianas, o novo valor é dado pela expressão nQ = ∑iєI qi /(β*p).
Um cuidado dever ser tomado durante as alterações tanto das demandas quanto da capacidade, que é a
manutenção da factibilidade do problema, pois pode ocorrer que a nova demanda do ponto seja superior à
capacidade das medianas.
3.2 Sobre a distribuição geográfica dos pontos com maior demanda
A segunda maneira estudada para gerar instâncias difíceis é modificar a designação demanda-ponto, ou seja,
fazer com que a demanda de um ponto passe a pertencer a outro, segundo uma determinada forma de realocação.
Esta realocação visa agrupar pontos de alta demanda numa determinada região, de forma que os agrupamentos
formados por pontos nessa região sofram grandes distorções.
Para realocar as demandas, foi usada a seguinte técnica:
1º - Encontrar um ponto extremo do grafo (no caso foi utilizado o ponto com menor soma das coordenas x e y);
2º - Classificar todos os pontos em ordem crescente de distância ao ponto encontrado no passo 1;
3º - Realocar as demandas em ordem decrescente de demanda, pela ordem crescente de distancias calculadas no
item 2.
Problema das p-Medianas Capacitado:
Estudo Sobre a Resolução de Instâncias por Métodos Exatos
Stefanello & Müller & Araújo
3
IX SEPROSUL – Semana de Engenharia de Produção Sul-Americana
Novembro de 2009, Piriápolis, Uruguai
Isso garante que os pontos com maior demanda sejam agrupados numa determinada região, como podemos
observar na Figura 1 (na qual a demanda do ponto é representada por círculos cujo centro é o próprio ponto e
raio é proporcional a demanda). Na maioria dos casos a realocação causa grande degeneração na distribuição
espacial da solução.
Este procedimento aplicado sozinho, não garante um acréscimo na dificuldade de resolução da instância, visto
que é dependente de alguns outros fatores discutidos na próxima seção, mas quando usado em conjunto com o
anterior é bastante significativo, de modo que para a maioria das instâncias o resolvedor encontra grande
dificuldade de reduzir o gap e provar a otimalidade.
Embora instâncias desse tipo possam não representar situações encontradas na vida real, elas são interessantes,
pois dão uma maior credibilidade as heurísticas e meta-heurística que são propostas para este problema.
3.3 Outras considerações:
Duas questões são importantes para aumentar a dificuldade das instâncias. A primeira é que haja pontos de
demanda que consumam boa parte da capacidade de uma mediana, pois quando esses pontos são agrupados, os
mesmos obrigatoriamente são associados a pontos de baixa demanda, que segundo a ordenação, vão estar
localizados a grandes distâncias, Figura 1.
Figura 1: Exemplo de nova instância e solução após modificações.
O segundo fator é a existência de demandas com desvio padrão relativamente alto, ou pelo menos diferente de
zero, pois caso contrário a realocação das medianas não surte efeito algum.
4. Resultados Computacionais
Três conjuntos de instâncias foram utilizados nos testes, o primeiro, um conjunto clássico introduzido por Osman
e Christofides (1994) contendo 20 instâncias nomeadas p1 a p20. O segundo conjunto contendo 6 instâncias,
proposto por Lorena e Senne (2004) com dados reais da cidade de São José dos Campos e o terceiro conjunto
por Lorena et al (2003), disponíveis em http://people.brunel.ac.uk/~mastjjb/jeb/info.html.
4.1 Resultados para PPMC
Para a realização dos testes computacionais foi utilizado o resolvedor CPLEX 9.01 com a configuração padrão e
um computador com processador Pentium IV 2,8 GHz com 2MB de memória RAM e sistema operacional
Linux.
A Tabela 1 apresenta os resultados comparativos para o PPMC, considerando o Modelo P e o Modelo Reduzido
para diferentes instâncias. Nessa tabela, a primeira coluna designa a instância analisada, os elementos das
colunas n e p correspondem ao número de pontos e medianas de cada instância. A coluna FO* traz a melhor
1
http://www.ilog.com/products/cplex/
Problema das p-Medianas Capacitado:
Estudo Sobre a Resolução de Instâncias por Métodos Exatos
Stefanello & Müller & Araújo
4
IX SEPROSUL – Semana de Engenharia de Produção Sul-Americana
Novembro de 2009, Piriápolis, Uruguai
solução encontrada para a instância na literatura (com exceção das instâncias p3038_1000 a p3038_600, neste
trabalho denominadas I1 a I5, cujos valores são referentes aos resultados obtidos por Lorena et al. (2003) com o
algoritmo CG(1)). As próximas duas colunas referem-se aos resultados do Modelo P, nas quais, respectivamente,
são apresentados os valores de função objetivos e o tempo computacional de obtenção da solução.
A coluna FOr traz os valores de função objetivo encontrados para o Modelo Reduzido. A coluna seguinte, gap,
com gap = (FOp- FOr)/ FOp), representa a diferença percentual da solução do Modelo Reduzido em relação ao
Modelo P, e, por último, a coluna Tempo(s) mostra o tempo de busca da solução de cada instância para o
Modelo Reduzido.
É possível observar que, para algumas instâncias, há uma diferença entre as soluções ótimas apresentadas e as
relatadas na literatura. Os autores atribuem essa diferença ao fato de que, ao gerar as restrições do modelo
matemático, as distâncias entre os nós foram arredondadas para duas casas decimais.
A resolução da instância Sjc4a necessitou um tempo computacional relativamente alto, se comparado a outras.
Entretanto, analisando-se o desempenho no decorrer do tempo, verifica-se que a solução obtida em menos de
260 segundos apresenta um gap menor que 1% e com 1777 segundos o resolvedor já encontra uma solução com
um gap inferior a 0,5%.
Em termos de tempo computacional, o Modelo Reduzido mostrou um bom desempenho quando comparado ao
Modelo P, visto que o tamanho do primeiro é menor, permitindo ao resolvedor encontrar boas soluções do
problema original (muitas vezes a ótima) em um tempo reduzido.
Os testes do Modelo Reduzido foram realizados com α = 2. Para as instâncias de grande porte (I1 a I5), houve
uma significativa redução no número de variáveis, com mais de 99,5% das variáveis eliminadas, o que levou a
arquivos, que inicialmente possuíam um tamanho aproximado de 800 MB, para menos de 3,5 MB.
Tabela 1: Resultados Computacionais – Modelo P e Modelo Reduzido.
Modelo P
Modelo Reduzido
Inst.
n
p
FO*
FOp
Tempo(s)
FOr
gap
Tempo(s)
Sjc1
100
10
17288,99
17288,55
57,40
17410,48
0,71%
21,54
Sjc2
200
15
33270,94
33270,08
96,80
33270,08
0,00%
45,99
Sjc3a
300
25
45335,16
45333,84
309,00
45333,84
0,00%
111,01
Sjc3b
300
30
40635,90
40634,66
97,90
40664,85
0,07%
22,27
Sjc4a
402
30
61925,51
61923,69
3337,60
61923,69
0,00%
307,51
Sjc4b
402
40
52458,00
52456,30
584,40
52456,30
0,00%
96,70
I1
3038
1000
82876,12
-
-
86030,82
3,81%
14389,09
I2
3038
900
89950,8
-
-
92471,17
2,80%
6983,99
I3
3038
800
98309,25
-
-
100344,10
2,07%
7430,28
I4
3038
700
108657,04
-
-
110051,15
1,28%
9332,60
I5
3038
600
121960,16
-
-
122966,22
0,82%
20078,52
Para as instâncias de grande porte, os resultados do CPLEX, usando o Modelo Reduzido, foram comparados aos
dados obtido em Lorena et al. (2003) com o algoritmo CG(1). O processamento foi interrompido sempre que o
valor da função objetivo não era atualizado por um determinado tempo limite. A Figura 2 mostra a evolução do
valor da função objetivo no decorrer do processamento (em vermelho) e o melhor valor obtido pelo algoritmo
CG(1) (em azul). O gráfico considera a instância com 3038 e 1000 medianas. Percebe-se que, num reduzido
tempo de processamento, já é possível encontrar uma solução de boa qualidade.
Problema das p-Medianas Capacitado:
Estudo Sobre a Resolução de Instâncias por Métodos Exatos
Stefanello & Müller & Araújo
5
IX SEPROSUL – Semana de Engenharia de Produção Sul-Americana
Novembro de 2009, Piriápolis, Uruguai
Figura 2: Valor da F.O. no decorrer do tempo para a instância I1
Mesmo que o Modelo Reduzido tenha sido idealizado para tratar instâncias de grande porte, verifica-se que esse
também pode ser aplicado a instâncias de pequeno e médio porte, pois o desempenho é comparável aos
resultados obtidos com o Modelo P.
4.2 Resultados das alterações nas instâncias
Neste caso, os testes foram executados em um computador provido com um processador Pentium IV 3,0 GHz
com 2MB de memória RAM, sistema operacional Windows e o resolvedor CPLEX 11.1 com a configuração
padrão.
Os resultados a seguir mostram que alterações em alguns parâmetros das instâncias podem influenciar
significativamente na dificuldade que um resolvedor tem em provar a otimalidade e/ou reduzir o gap destas
novas instâncias.
Testes realizados com diferentes valores do Fator de Ocupação mostram que a dificuldade de resolução da
instância por resolvedores comerciais aumenta significativamente para valores de β altos, como mostra a Figura
3.
Os dados desta figura se referem a testes realizados com um conjunto de 10 instâncias com n = 100 e p = 10
propostas por Osman e Christofides (1994) com alteração da capacidade das medianas. Valores de β são
representado no eixo das abscissas, enquanto o eixo das ordenadas representa o tempo médio gasto pelo
resolvedor para provar a otimalidade das instâncias.
Figura 3: Tempo médio de processamento para diferentes valores de β.
Para outros conjuntos de instâncias, a característica do gráfico é similar, embora possa sofrer leves alterações,
devido às características de cada instância, podendo ter uma acentuação ainda maior para valores menores de β,
Problema das p-Medianas Capacitado:
Estudo Sobre a Resolução de Instâncias por Métodos Exatos
Stefanello & Müller & Araújo
6
IX SEPROSUL – Semana de Engenharia de Produção Sul-Americana
Novembro de 2009, Piriápolis, Uruguai
além disso, alterações nas demandas ao invés da capacidade podem ter influências ainda mais significativas,
dependendo da instância.
A redistribuição das demandas também gerou um aumento na dificuldade da instância, mas para determinados
conjuntos, quando aplicado sem o aumento de β, não foi significativo. Já quando foi aplicado juntamente com o
aumento do fator de ocupação, a redistribuição se mostrou mais significativa e proporcionou uma maior
dificuldade, requerendo um tempo maior de processamento para a resolução.
A aplicação dos dois itens simultaneamente mostrou que o acréscimo de dificuldade foi substancial como pode
ser observado na Tabela 2, e nem mesmo fazendo uso do Modelo Reduzido foi possível resolver eficientemente
as instâncias.
As mudanças inferidas nas instâncias através dos fatores a e b foram definidas de forma experimental, pois ainda
não foi detectado um padrão comum para o aumento de dificuldade. Nota-se que o aumento do fator de ocupação
em geral implica numa dificuldade maior. Nos testes, as alterações, na maioria dos casos, correspondem a
multiplicação da demanda por um fator, de forma a obter um β próximo a 0,98 para o primeiro conjunto, entre
0,94 e 0,98 para o segundo conjunto, próximo a 0,90 para o terceiro conjunto, cuidando ainda para manter a
factibilidade do problema.
A Tabela 2 mostra os resultados de algumas instâncias após as modificações. A primeira coluna traz o nome da
instância modificada, com o número de pontos e medianas na segunda e terceira coluna, respectivamente. A
coluna TempoP(s) traz o tempo de resolução da instância original através do Modelo P. Já as colunas seguintes,
trazem tempo de processamento, o gap após o tempo de processamento e, por último, o fator de ocupação das
instâncias modificadas.
Os testes foram realizados com um tempo limite de processamento de 10.000,00 segundos. O resolvedor
comercial conseguiu solucionar satisfatoriamente o primeiro conjunto (p1 a p10), embora tenham mostrado um
grande aumento no tempo computacional se comparado com a instância original.
Tabela 2: Resultados Computacionais – Instâncias Modificadas.
Instância
p11
p12
p13
p14
p15
p16
p17
p18
p19
p20
sjc1
sjc2
sjc3a
sjc3b
sjc4a
sjc4b
n
100
100
100
100
100
100
100
100
100
100
100
200
300
300
402
402
p
10
10
10
10
10
10
10
10
10
10
10
15
25
30
30
40
TempoP(s)
23,88
25,58
6,95
75,92
50,06
14,58
80,69
33,83
24,14
1133,89
57,36
111,61
248,34
92,27
2582,22
230,33
TempoD(s)
10.000,00
10.000,00
8.536,94
10.000,00
8.926,97
10.000,00
10.000,00
5.219,28
10.000,00
3.898,84
3.533,83
10.000,00
10.000,00
10.000,00
10.000,00
10.000,00
gap
2,17%
1,71%
0%
0,78%
0%
2,77%
1,28%
0%
2,24%
0%
0%
6,07%
5,98%
6,27%
10,33%
7,98%
β(x100)
98,08
96,58
97,58
97,92
97,42
98,58
97,58
97,33
98,42
98,17
98,06
97,73
96,26
94,75
94,66
94,85
Para as instâncias p11 a p20, em 6 casos o resolvedor excedeu o tempo limite sem conseguir provar a
otimalidade das mesmas, mantendo um gap médio para estas instâncias de 1,83%. Para aquelas em que foi
possível resolver, o tempo gasto foi consideravelmente maior do que a instância original.
Para o segundo conjunto, apenas para a primeira instância o resolvedor conseguiu provar a otimalidade. Com
referência as demais, além de não provar a otimalidade, o gap se manteve bastante elevado, com uma média de
7,33%.
Problema das p-Medianas Capacitado:
Estudo Sobre a Resolução de Instâncias por Métodos Exatos
Stefanello & Müller & Araújo
7
IX SEPROSUL – Semana de Engenharia de Produção Sul-Americana
Novembro de 2009, Piriápolis, Uruguai
A redistribuição das demandas causa alguns efeitos negativos no Modelo Reduzido, que além de obter soluções
potencialmente piores, pode implicar inclusive na infactibilização do problema, pois em alguns casos pontos
com alta demanda devem estar associados a outros pontos com baixa demanda, mas a redistribuição os posiciona
mais distantes de tal forma que são ignorados pelo Modelo Reduzido. Isso faz com que determinadas medianas
tenham grande excedente de capacidade disponível, que seria destinado a pontos com baixa demanda, causando
assim a infactibilidade. Isso sugere uma melhor definição das regras para reduzir as variáveis heuristicamente.
Ainda considerando o Modelo Reduzido, para o conjunto de instâncias de larga escala, apenas a redistribuição
das demandas já as tornou-as mais difíceis na busca de uma solução. Com acréscimo nas demandas, algumas
delas se tornaram infactíveis ou então o resolvedor não conseguiu encontrar nenhuma solução dentro do tempo
estipulado, mesmo para valores maiores de α.
O Modelo Reduzido, de forma geral teve um comportamento instável, visto as grandes modificações aplicadas
nas instâncias. Em algumas situações foi possível encontrar boas soluções, embora num alto tempo de
processamento, mas em outras situações o modelo teve um comportamento muito inferior que ao próprio
Modelo P, como é o caso da instância Sjc4a, onde o gap se manteve acima de 20% no tempo limites estipulado.
5. Conclusão
Os experimentos realizados demonstram que as instâncias do tipo SJC podem ser tratadas diretamente a partir do
Modelo P. Para as instâncias de maior porte, I1 a I5, o Modelo Reduzido apresentou bom desempenho, pois em
tempo computacional relativamente baixo encontrou boas soluções. Para as instâncias de pequeno porte, na
maioria dos casos, encontrou os mesmos valores de função objetivo do Modelo P.
O fator de ocupação β tem grande influência no tempo gasto pelo resolvedor para provar a otimalidade da
solução, pois obriga que as restrições de demanda (P5) sejam mais apertadas, reduzindo a possibilidade de
encontrar soluções factíveis. Além disso, a realocação das demandas, provoca uma modificações na estrutura da
instância que, quando combinada ao alto fator de ocupação, gera situações de associação bem adversas.
Com as modificações, foi possível criar instâncias para as quais o resolvedor encontrou grande dificuldade em
encontrar boas soluções, reduzir o gap e provar a otimalidade, mesmo para o Modelo Reduzido proposto. Na
sequência da pesquisa, estas instâncias serão disponibilizadas para a comunidade científica.
Em trabalhos futuros, pretende-se estudar a influência da distribuição geográfica dos pontos, além da simetria da
matriz distância bem como a influência de outras métricas na resolução das instâncias. Ainda, verificar se os
métodos propostos atualmente são eficientes para resolver estas instâncias modificadas, de forma que se o
desempenho destas se mantiver satisfatório, significa que são robustas. Caso este fato seja confirmado, será
possível discriminar melhor a qualidade dos métodos heurísticas propostas para esse problema.
Agradecimento:
Os autores agradecem à CAPES pelo apoio financeiro recebido.
Referências Bibliográficas
AHMADI, S.; OSMAN, I.H. (2005). Greedy random adaptive memory programming search for the capacitated
clustering problem. European Journal of Operational Research 162 (1), 30–44.
BALDACCI, R. HADJICONSTANTINOU, E.; MANIEZZO, V.; MINGOZZI, A. (2002). A new method for
solving capacitated location problems based on a set partitioning approach. Computer and Operations Research,
29 (3): 365–386.
BOCCIA, M.; SFORZA, A.; STERLE, C.; VASILYEV, I.(2008) A cut and branch approach for the capacitated
p-median problem based on fenchel cutting planes. Journal of Mathematical Modelling and Algorithms, v.7, n.1,
p. 43-58.
DIAZ, J.A., FERNANDEZ, E. (2006). Hybrid scatter search and path relinking for the capacitated p-median
problem. European Journal of Operational Research 169, 570–585.
FLESZAR, K.; HINDI, D. S. (2008) An effective vns for the capacitated p-median problem. European Journal of
Operational Research, v. 191, n. 3, p.612-622
Problema das p-Medianas Capacitado:
Estudo Sobre a Resolução de Instâncias por Métodos Exatos
Stefanello & Müller & Araújo
8
IX SEPROSUL – Semana de Engenharia de Produção Sul-Americana
Novembro de 2009, Piriápolis, Uruguai
GAREY, M. R. ET JOHNSON, D. S. (1979). Computers and Intractability. A Guide to the Theory of NPCompleteness. W. H Freeman and Company.
HAKIMI, S.L. (1964), "Optimal locations of switching centers and the absolute centers and the medians of a
graph", Operations Research 12, 450-459.
LORENA, L.A.N., SENNE. E.L.F, (2002). Abordagens de Geração de Colunas para um Problema de pmedianas Capacitado XXXIV SBPO - Rio de Janeiro
LORENA L.A.N., SENNE E.L.F, (2004): A column generation approach to capacitated p-median problems.
Computers and Operational Research, Vol. 31 863–876.
LORENA, L.A.N., PEREIRA, M.A., SALOMÃO, S.N.A. (2003). A relaxação lagrangeana/surrogate e o método
de geração de colunas: novos limitantes e novas colunas. Revista Pesquisa Operacional, 23(1): 29-47.
MANIEZZO, V., MINGOZZI, A., BALDACCI, R. (1998) A bionomic approach to the capacitated p-median
problem. Journal of Heuristics 4: 263–80
MULVEY, J.M., BECK, M.P. (1984) Solving capacitated clustering problems. European Journal of Operational
Research 18, 339-348.
OSMAN, I.H., CHRISTOFIDES, N. (1994) Capacitated clustering problems by hybrid simulated annealing and
tabu search. International Transactions in Operational Research 1, 317-336.
SCHEUERER, S., WENDOLSKY, R.(2006) A scatter search heuristic for the capacitated clustering problem.
European Journal of Operational Research, v. 169, n. 2, p. 533-547
SILBERHOLZ, J., GOLDEN, B. (2003), Comparison of Metaheuristics, Handbook of Metaheuristics. 2003.
Kluwer Academic Publisher.
STEFANELLO, F., MÜLLER, F.M. (2009) Um Estudo Sobre Problemas de Agrupamento Capacitado. XLI
SBPO - Porto Seguro
Problema das p-Medianas Capacitado:
Estudo Sobre a Resolução de Instâncias por Métodos Exatos
Stefanello & Müller & Araújo
9