XXX ENCONTRO NACIONAL DE ENGENHARIA DE PRODUÇÃO
Maturidade e desafios da Engenharia de Produção: competitividade das empresas, condições de trabalho, meio ambiente.
São Carlos, SP, Brasil, 12 a15 de outubro de 2010.
APLICAÇÃO DAS METAHEURÍSTICAS
ALGORITMO GENÉTICO COM BUSCA
ADAPTATIVA E OTIMIZAÇÃO POR
SALTOS DE RÃS À SOLUÇÃO DO
PROBLEMA DAS P-MEDIANAS
Anderson Moreira de Vasconcelos (CEFET-MG)
[email protected]
Sérgio Ricardo de Souza (CEFET-MG)
[email protected]
Sinaide Nunes Bezerra (CEFET-MG)
[email protected]
Este trabalho propõe um estudo comparativo entre aplicações das
metaheurísticas Algoritmo Genético com Busca Local Adaptativo (AG)
e o Algoritmo de Otimização por Saltos de Rãs (JFO) para a solução
do Problema das p-Medianas. O problema de p-medianas consiste em
determinar p nós, denominado medianas, em um gráfico de n vértices,
minimizando a distância total a partir de outros nós do gráfico. A
metodologia utilizada consiste na apresentação do Algoritmo Genético,
juntamente com a busca local adaptativa para melhoria do
cromossomo gerado, e do Algoritmo de Otimização por Saltos de Rãs,
bem como de algoritmos de geração de clusters e de LocalizaçãoAlocação (HLA), métodos utilizados para criação de uma região de
atendimento destinada a ser coberta por uma facilidade. Testes
computacionais, realizados com instâncias da literatura, mostram que
as soluções encontradas através da metaheurística JFO são superiores
às encontradas pelo AG.
Palavras-chaves: Problema das p-Medianas, Algoritmos Genéticos,
Otimização por Saltos de Rãs; Metaheurística.
1. Introdução
De acordo com Tseng & Wu (2009), em várias aplicações do mundo real torna-se necessário
localizar um determinado objeto, denominado aqui como facilidade, dentro de uma região
estabelecida, mais adequada para se instalar um serviço específico.
O Problema das p-Medianas (PMP) é uma técnica clássica empregada na determinação dos
locais mais adequados para a instalação de serviços, dentro de uma região pré-estabelecida. O
objetivo do PMP é localizar p vértices (medianas) em um grafo contendo n vértices, de forma
a obter a menor soma das distâncias de cada vértice até a mediana mais próxima. Uma vez
localizadas as múltiplas medianas, são constituídos clusters (agrupamentos), nos quais cada
mediana é alocada a certo número de vértices de demanda.
Este problema vem sendo objeto de grande interesse por parte da comunidade científica. Em
Mladenovic et al. (2007) é apresentada uma revisão do estado da arte das propostas de
solução do PMP e de suas principais variantes. Steiner et al. (2004) apresentam um algoritmo
genético (AG) para a solução desse problema em que, além dos operadores convencionais,
utilizam também um novo operador, denominado hipermutação heurística. No trabalho de
Osman & Erhan (2003) é apresentada uma proposta de um algoritmo genético aplicado ao
problema de localização. O algoritmo proposto é relativamente simples e gera boas soluções
rapidamente, pois a evolução é facilitada por uma heurística gulosa. No trabalho de Beltran et
al. (2006) é utilizada à relaxação lagrangeana, aplicada a instâncias com até 1748 nós.
Senne & Lorena (2003) afirmam que os métodos exatos propostos para solucionar o PMP
encontram dificuldades em relação ao tempo computacional gasto na determinação da solução
ótima. Então, neste caso, muitas heurísticas e metaheurísticas têm sido propostas para resolvêlo, encontrando boas soluções em um tempo computacional aceitável. É nesse contexto que o
Algoritmo Genético (AG) e o Algoritmo de Otimização por Saltos de Rãs (JFO) são aplicados
neste trabalho. Encontramos também o AG ou o JFO aplicados ao problemas de localização
de facilidades em Correa et al. (2001), Osman & Erhan (2003), Chaudhry (2003), Correa
(2004), Tarcísio & Elias (2008) e Leonor et al. (2008). Cada um com suas devidas variações.
No presente trabalho, é feito uma comparação entre o Algoritmo Genético com Busca Local
Adaptativa e o Algoritmo JFO, todos os dois com suas devidas adaptações para a solução do
PMP.
2. Problema de Localização
O problema de p-Medianas (PMP) é um dos modelos clássicos baseados na teoria de
localização discreta como visto no trabalho de Mladenovic et al. (2007). Esse é um problema
de localização de facilidades que representam uma área relevante nos âmbitos acadêmicos e
prático (logístico), no qual o objetivo é encontrar técnicas capazes de solucionar tais
problemas de maneira mais eficiente e eficaz.
Senne & Lorena (2003), propõem um modelo de programação inteira binária para a solução
do problema da p-Mediana que é o seguinte:
2
Q( z )  Min
 d
xij
(1)
x
ij
 1; j  N
(2)
x
ii
p
(3)
xij  xii ; i, j  N
(4)
iN iN
s.a
iN
iN
ij
xij  0,1; i, j  N
(5)
em que:
N  1,  , N , cada elemento de N representa um vértice
d ij nxm é uma matriz simétrica de custo (ou distância), com dii  0, i  N ;
 
d 
ij nxn
é uma matriz de alocação, com xij = 1 se o nó j é alocado à mediana i, e xii = 0, caso
contrário.
p é o número de medianas;
n é o número de nós.
As restrições (2) e (4) garantem que cada nó j é alocado a apenas um nó i, o qual deve ser uma
mediana. A restrição (3) determina o número exato de medianas a ser localizado e a restrição
(5) corresponde às condições de integridade.
Segundo Senne & Lorena (2003), esta formulação do problema de p-medianas é de difícil
solução, mesmo com os avanços nos softwares dedicados à solução de problemas de
Programação Matemática. A formulação de 1 a 4 pode ser resolvida apenas para instâncias de
pequeno porte, porque esses métodos são conhecidos como "caros", por isso não podem ser
aplicados a problemas NP-Difíceis Jourdan et al. (2009) e Senne & Lorena (2003). Essas
limitações se devem ao fato de que o tempo de resolução aumenta exponencialmente à
medida que aumentam os dados de entrada. Segundo Woeginger (2003), para alguns
problemas, é possível projetar algoritmos que são significativamente mais rápido que busca
exaustiva, ainda assim, esses algoritmos continuam sendo não polinomiais.
No âmbito logístico, o problema de localização se justifica pelos seguintes fatos:
 Os problemas de localização têm aplicações práticas na produção de bens e serviços em
quaisquer setores e níveis da economia, servindo de ferramenta para as tomadas de
decisões;
 Problemas de localização são de grande importância econômica para planejamento
estratégico de setores produtivos, indústrias, prefeituras, comércio e outros. A otimização
destes modelos podem levar a grandes economias em seus investimentos, como descrito
por Lorena (2001);
 Os problemas de localização são aplicáveis a uma infinidade de situações, como:
localização de indústrias, centro de distribuição, antenas, escolas, postos de saúde, corpo
de bombeiros, universidades, entre outros.
O PMP é representado através de um grafo composto por um conjunto de vértices V, no qual
cada vértice é visto como um potencial local para se instalar uma facilidade ou simplesmente
3
medianas. Seja, então, um grafo não direcionado G(V,A), |V | = n, onde V são os vértices e A
as arestas. O PMP consiste em determinar um conjunto com p vértices, formando-se um
conjunto Vp, sendo Vp  V tal que |Vp| = p, logo Vp é a solução para o problema das pmedianas, agregando o máximo possível de arcos com a menor distância entre os pontos.
Logo, Vp contém os elementos (vértices) que indicam a localização de cada facilidade.
Figura 1 – p-Medianas
3. Algoritmo Genético
Os AG são algoritmos probabilísticos que fornecem um mecanismo de busca paralela e
adaptativa baseado no princípio Darwiniano de sobrevivência dos mais aptos e na reprodução
genética. De acordo com Goldberg (1989) o AG é um algoritmo robusto, eficiente e eficaz
para vários tipos de problemas.
Algoritmo (AG)
Inicie a população;
Avalie a população;
Enquanto (critério de parada não for atingido) faça
Selecione indivíduos para próxima população;
Aplique cruzamento e mutação;
Avalie a população;
Fim_Enquanto;
Fim_Algoritmo.
Figura 2 – Pseudocódigo Algoritmo AG Básico
O termo "genético" tem sua base na biologia e diz respeito a maneira como as possíveis
soluções para o problema tratado são codificadas em cromossomos, estrutura composta por
uma cadeia finita de elementos, os genes.
A população inicial de indivíduos pode ser gerada de várias maneiras, sendo, na maioria das
vezes, realizada de forma aleatória. Segundo Grefenstette (1986), o tamanho da população
afeta o desempenho global e a eficiência do algoritmo. Uma população grande fornece uma
cobertura representativa do problema, além de prevenir convergências prematuras para
soluções locais em vez de globais. Em contrapartida, são necessários mais recursos
computacionais.
A avaliação consiste em verificar o valor da aptidão de cada indivíduo da população. É
através do cálculo da aptidão que se mede quão próximo um indivíduo está da solução
desejada e determina quem poderá reproduzir.
4
A composição básica do algoritmo genético é inicializada a partir de verificada o valor da
aptidão de cada indivíduo. É através do cálculo da aptidão que se mede quão próximo um
indivíduo está da solução desejada ou quão boa é esta solução.
Após a avaliação de todos os indivíduos da população, tem-se o processo da seleção de
indivíduos para reprodução. Terminado a seleção, novos indivíduos são criados a partir dos
operadores genéticos de cruzamento (crossover) e mutação.
Há várias formas possíveis de se fazer o cruzamento. O cruzamento simples, chamado
cruzamento de um ponto. Este cruzamento prevê apenas um corte, escolhido com
probabilidade uniforme sobre o comprimento do cromossomo, Michaelewicz & Davis (1994).
A partir do ponto de corte, cada cromossomo pai é dividido em duas partes, assim os genes
dos dois pais são combinados de forma a gerar dois cromossomos filhos. Outro cruzamento é
o OrderCrossover (OX), que foi utilizado neste trabalho, este operador constrói seus
descendentes selecionando uma subsequência de um caminho de um pai, preservando a ordem
relativa da sequência do outro pai.
Terminada a recombinação por cruzamento, os cromossomos filhos podem sofrer mutação.
Este operador genético permite introduzir novos indivíduos na população, contribuindo para a
manutenção da diversidade da população. A mutação altera arbitrariamente um ou mais
genes, resultando em um novo cromossomo.
Quando ocorre o cruzamento entre dois cromossomos, pode ocorrer inconsistência em algum
dos cromossomos ou ambos, pois, genes repetidos podem ser atribuídos a um mesmo
indivíduo. Sejam ri={2,4,15,6,21} e rj={8, 12, 2, 5, 19}, ri e rj  V . Aplicado o operador OX,
tem-se rx={2, 12, 2, 5, 21} e rj={8, 4, 15, 6, 19}. Os genes 1 e 3 em rx são iguais, logo, rj não é
viável, e assim, não é uma solução candidata para o PMP.
Algoritmo AGPMP
Passo1 – Inicialização;
Construir a população inicial, gerar uma lista R={r1, r2, ... Rn};
Com m cromossomos viáveis de p genes cada, escolhidos aleatoriamente em V.
Calcular C1 = aptidão (ri)defina k=0, itmax e itsm
Ordenar R de modo que C1 ≤ C2≤ ... ≤ Cm;
Passo 2 – Teste
Testar se k≥ itmax ou k≥ itsm então PARE e apresente o cromossomo r1
Passo 3 – Seleção;
2


ri= Seleção(R) e rj = Seleção(R), ri ≠ rj ; Seleção ( R)  r j  R j    1  1  4.rnd n  n   
2

Passo 4 – Cruzamento

 


Fazer o cruzamento (ri, rj) = (rx, ry);
Passo 5 – Mutação
Escolher rx ou ry;
Aplicar mutação no cromossomo escolhido;
Passo 6 – Aptidão
Calcular a aptidão de rx e ry;
Se aptidão(rx) < aptidão(ry) então s = aptidão (rx);
Se aptidão(s) < Cm então
Cm = aptidão(s);
Rm = (s);
Senão
Busca_Local(s);
Passo 7 – Ordenação
Ordenar R, mantendo a ordem crescente de aptidões;
Fazer k=k+1 e voltar ao Passo 2;
Fim Algoritmo
5
Figura 3 – Pseudocódigo do Algoritmo Genético para o PMP
Quando um cromossomo C não é viável, o mesmo não pode ser considerado como um
descendente válido. Para solucionar este problema, deve-se verificar os elementos em C
repetidos e obter aleatoriamente em V um elemento que torne C viável, de modo que, C seja
viável e C _ V . Aplicando este procedimento no cromossomo de exemplo rx, temos: rx = {11,
12, 2, 5 21}. O gene 1 de rx foi escolhido de forma aleatório de V produzindo-se assim um
cromossomo viável. No algoritmo apresentado, a viabilidade dos cromossomos descendentes,
rx e ry, é verificada após cada cruzamento.
No algoritmo apresentado na Fig.2 no passo5, a probabilidade de escolha de rx ou ry é fixada
em 50% para cada cromossomo. Após a escolha de um cromossomo, a mutação ocorre
mediante uma probabilidade denominada probabilidade de mutação. Esta probabilidade é um
dos parâmetros que podem influenciar no funcionamento do AG.
O Algoritmo Genético apresentado neste trabalho realiza uma Busca Local Adaptativa
baseado no método GRASP, que são métodos iterativos proposto por Feo & Resende (1995).
Esse método consiste basicamente na construção de uma solução inicial aleatória onde são
gerados elemento a elemento. Outra fase é a busca local, que consiste em efetuar trocas dos
genes em um cromossomo com o intuito de melhorar sua aptidão. Daí é retornada a melhor
solução encontrada. O objetivo é refinar a solução encontrada pelo AG. Além disso, ele é
regulado pelo parâmetro perc-busca. O percentual de busca é ajustado conforme o número
máximo de iterações, desta forma, se o máximo de iterações (it-max) do algoritmo é 1000 e
perc-busca = 80%, então o procedimento Busca-Local será executado no máximo 800 vezes.
O procedimento de busca local pode acontecer quando o cruzamento efetuado no AG, gera
indivíduos com aptidões piores em relação a população existente. A condição para que a
busca local aconteça é então dependente do perc-busca. O valor máximo de troca é fixado em
1/3 da quantidade máxima de alelos disponíveis com o intuito de restringir a quantidade de
iterações do método, e assim, utilizar o método como forma auxiliadora proporcionando
melhores resultados e tempos computacionais.
Em testes empíricos foi avaliado que a busca local melhora os resultados encontrados pelo
AG.
4. Algoritmo de Otimização por Saltos de Rãs
O algoritmo JFO tem suas origens no movimento de um grupo de rãs que saltam de uma
pedra a outra em um determinado intervalo de tempo, sem ocupar posições intermediárias
conforme descrito no trabalho de García & Pérez (2007). Como as partículas podem ocupar
apenas um único conjunto de posições definido pelo domínio do problema, a idéia de
velocidade é substituída por saltos esporádicos e aleatórios no espaço de busca. Se o espaço
de busca do problema de otimização for discreto, torna-se necessário a utilização de métodos
como o JFO, que são mais adequados para esse tipo de situação.
Algoritmo JFO
Iniciar randomicamente a posição das N partículas da população;
Iniciar X, B e G;
Faça
Atualizar X;
Para i 1 até N faça;
Avaliar as aptidões das partículas em X através de f(Xi);
Atualizar B, segundo algoritmo Movimentos_JFO
Se f(Xi) < f (Bi), então f(Bi) = Xi;
Atualizar G. se Bi < f(G), então G=Bi;
Fim_Para;
Enquanto (critério de parada não atingido)
Fim_Algoritmo.
6
7
5. Geração de Clusters
O método que permite determinar a região atendida por cada facilidade (cluster) é
implementado pelo algoritmo de designação de Gillet e Johnson. Este método visa solucionar
problemas de múltiplas facilidades, relacionando cada ponto de demanda a facilidade mais
próxima. O algoritmo (G&J) é descrito na Fig.5.
O algoritmo será executado até que todos os nós estejam designados a uma determinada
mediana.
O algoritmo de G&J é descrito na figura 5, conforme Smiderle et al. (2004).
Após terminado o algoritmo de determinação, é aplicada a heurística de Localização (HLA),
proposta em Lorena, que busca melhorar, pelo uso de uma busca local, a instância_j dentro de
um cluster á formado alterando a mediana com um vértice a ela designado. A HLA é
empregada em trabalhos de Arakaki & Lorena (2006) e Hoffman & Gomez (2003).
A seguir, a Fig.6 apresenta o pseudo-código escrito em Arakaki & Lorena (2006) e adaptado
neste trabalho para o PMP não capacitado. Na busca por localizar as facilidades, em alguns
casos não é necessário a geração da região de atendimento, assim como o trabalho de Beasley
(1990), neste caso, os algoritmos G & J e HLA, não serão acionados.
Algoritmo Gillet & Johnson
Passo 1 – Calcula-se a distância entre cada nó ainda não designado até cada uma das
medianas;
Passo 2 – Para cada nó i(não designado) do passo anterior, obter
com distância
ti1
como sendo a mediana mais próxima de i,
ci1 e ci2 respectivamente;
Passo 3 – Para todos os nós i, calcular a razão ri =
ci1 / ci2 . Ordenar os nós i de acordo com os
valores de ri,
em ordem crescente;
Passo 4 – Designar os nós i para as medianas mais próximas, até sua capacidade de atendimento esgotar.
Voltar ao passo 1 até que todos os nós estejam designados.
O algoritmo será executado até que todos os nós estejam designados a uma determinada mediana.
Figura 5 – Pseudocódigo para determinação de cluster de Gillet & Johnson
Algoritmo HLA
Dados J conjuntos das medianas ={j1,...,jp}
Ck conjunto de vértices do agrupamento k={v1,...,v|ck|}
µkj soma das distâncias da mediana j aos vértices do agrupamento
|Ck| cardinalidade de Ck
Enquanto (solução-inicial melhora) faça
Para Ck =1, ..., p faça
Para i=1, ..., |Ck| faça
Troque mediana JK por um vértice vi;
Calcule novo µkj;
Se novo µkj for melhor que antigo µkj então
Atualiza µkj;
Guarda nova mediana;
Fim_Se;
Fim_Para;
Fim_Para;
Atualiza J;
Calcula o valor novasol que corresponde as realocações;
Se novasol for melhor que solução-inicial então
Faça solução-inicial novasol;
Fim_Se;
Fim_Enquanto;
Fim_Algoritmo.
Figura 6 – Pseudocódigo da HLA
8
6. Resultados Computacionais
Para a verificação da eficácia do AG-BL e o JFO utilizou-se as instâncias descritas a seguir:
• Instância 1 - Instâncias descritas em Beasley (1990) para o PMP não capacitado.
• Instância 2 - Instâncias descritas em Lorena (2001) com 324 e 818 nós para o PMP não
capacitado.
A Tabela 1, apresenta os resultados entre AG-BL e JFO para Instância 1, com 100, 200, 400,
600 e 900 nós para 5, 67, 133, 200 e 90 medianas respectivamente. Para comparação da
eficácia do AG-BL e o JFO, utilizou-se também em todos os testes os resultados do
Algoritmo Genético, descrito em Bezerra (2008).
O algoritmo foi implementado em linguagem de programação C++ Builder-6, e executado 10
vezes para cada mediana em um computador Intel Core 2 Duo com 3 GB de memória RAM e
sistema operacional Windows XP.
Os resultados obtidos para a Instância 1 são apresentados na Tabela 1. Nesta tabela, tem-se
que: n, quantidade total de pontos; p, quantidade de medianas; s, solução encontrada por
Lorena (2001); alg, algoritmo; pop, tamanho da população; σ, melhor solução encontrada;
mσ, solução média; tm, tempo médio em segundos das soluções.
Instâncias
n
p
s
pmed1
100
5
518
pmed10
200
67
1255
pmed20
400
133
1989
pmed30
600
200
1989
pmed40
900
90
5128
alg
AG
AG_BL
JFO
AG
AG_BL
JFO
AG
AG_BL
JFO
AG
AG_BL
JFO
AG
AG_BL
JFO
σ
5893
5819
5818
1474
1267
1258
2337
1831
1825
2686
2304
2047
6017
5246
5240
mσ
6175
5823
5820
1567
2161
1265
2433
1819
1832
2744
2044
2057
6141
5297,9
5823
tm(s)
2,43
2,95
2,67
15,96
161,1
2,75
26,18
4231
348,56
41,28
21378
161,9
26,03
3746
156
Tabela 1 – Valores encontrados para instância 1
A combinação dos métodos AG e busca local AG-BL permitem sair de ótimos locais mais
facilmente. Quando o AG converge para um ótimo local e não consegue escapar do mesmo
através do cruzamento ou mutação, este é auxiliado pela busca local, que, nesta situação
diversifica os cromossomos dos indivíduos da população, alterando de forma contundente a
combinação de genes dos cromossomos.
Nota-se, porém, que os resultados com o algoritmo JFO são melhores em comparação ao AG
e AG-BL.
A Tabela 2, apresenta os resultados entre AG, AG-BL e JFO para Instância 2, com 324 nós, 5,
10, 20 e 50 medianas. Os parâmetros de probabilidade de mutação, it_max, it_sm e
perc_busca são os mesmos utilizados para Instancia 1.
9
Instância
pmedian324
n
p
s
5
122518
10
79256,36
20
54533,11
50
32101,52
324
alg
AG
AG-BL
JFO
AG
AG-BL
JFO
AG
AG-BL
JFO
AG
AG-BL
JFO
σ
127920
127078
126721
828553
82447
80463
60109
55573
55428
38657
33496
33396
mσ
128554
129894
128556
85610
800976
80795
61954
54876
57967
39793
32764
33549
tm(s)
16,22
371,34
41,44
14,5
681
26,27
15,68
3104,43
581
19,6
7125
1756
Tabela 2 – Valores encontrados para instância 2
Nos testes com Instância 2 os resultados são melhores com JFO e AG-BL, mesmo assim, os
resultados encontrados pelo AG não são distantes quando encontrado na Instância 1 devido ao
fato da utilização dos algoritmos G&J e HLA. Os algoritmos para geração dos clusters
tornam- se métodos de refinamento da solução encontrada, principalmente a HLA, que
procura melhor a solução dentro de uma solução já encontrada.
Mesmos os algoritmos G&J e HLA atuarem para a melhoria dos valores encontrados pelo
AG, fica evidente que há grande dependência da solução gerada antes desses métodos. Diante
desta situação, o AG-BL vem contribuir na geração de melhores soluções em relação ao AG
que podem ser refinadas pelos algoritmos de G&J e HLA.
Para a Instância 2 com 818 nós, os resultados encontrados com AG-BL e JFO são
apresentados na Tabela 3. Para estes testes utilizou-se o AG-BL e JFO em comparação aos
resultados encontrados em Lorena (2001) e Bezerra(2008).
Instâncias
n
pmedian818
818
p
s
5
605856,1
10
251717,8
alg
AG
AG-BL
JFO
AG
AG-BL
JFO
σ
637874
628739
619745
310971
306954
288167
mσ
647937
635784
627694
329524
326465
637594
tm(s)
18,3
15353
8294
23,66
14941
212,55
Tabela 3 – Valores encontrados para instância 2
7. Considerações Finais
Este trabalho apresenta os resultados do desempenho das metatheurísticas Algoritmo
Genético (AG), Algoritmo Genético com Busca Local Adaptativo (AG − BL) e o algoritmo
Jump Frog Optimization (JFO), na busca por melhores soluções para o problema das
p−Medianas.
Os métodos são apresentados e aplicados às instâncias descritas em Beasley (1990) e Lorena
(2001), nomeadas neste trabalho como Instância1 e Instância2, respectivamente. No caso da
Instância1, não são gerados os clusters, ficando a geração dos cluster na Instância2.
10
Os resultados obtidos na Instância1 são comparados aos valores encontrado por Bezerra
(2008) e a os resultados encontrados para Instância 2, são comparados aos resultados descritos
em Bezerra (2008) e Lorena (2001).
As soluções da rotina AG-BL mantém, em todos os casos, superiores ao AG. Esse melhor
refinamento está diretamente relacionado com o maior tempo computacional necessário,
quando comparado com o tempo computacional despendido pelo AG. Já o Algoritmo JFO
apresentou melhores resultados em todos os testes que realizados em comparação ao AG e
AG-BL.
Quando são utilizadas instâncias que necessitam de geração da região de atendimento, o custo
computacional eleva-se pela própria necessidade de encontrar a região a ser coberta por uma
mediana, no caso do AG-BL este tempo é ainda maior.
Referências
ARAKAKI, R. G. I. & LORENA, L. A. N. Uma heurística de localização-alocação (HLA) para problemas de
localização de facilidades. Revista Produção Vol. 6, n. 2, p. 319-328, 2006.
BEASLEY, J. E. Or-library: distributing test problems by electronic mail, operational
research society, Vol. 41, n. 11 p. 1069-1072, 1990.
BELTRAN, C. & TADONKI, C. & J.-PH.VIAL. Solving the p-median problem with a semilagrangian
relaxation. Springer Science + Business Media, vol. 35, pp. 239 260. 2006.
BEZERRA, S. N. Algoritmos evolutivos paralelos aplicados ao problema das p-medianas. Dissertação de
Mestrado, Centro Federal de Educação Tecnológica de Minas Gerais. 2008.
CHAUDHRY, S. S. Solving a class of facility location problems using genetic algorithms. Expert Systems, vol.
20, n. 2, 86-91. 2003.
CORREA, E. & STEINER, M. & FREITAS, A, & CARNIERI, C. A genetic algorithm for the pmedianproblem. Genetic and Evolutionary Computation Conference, pp. 1268–1275. 2001
CORREA, E. S.. A genetic algorithm for solving a capacitated p-median problem. Numerical algorithms. 2004
FEO, T. A. & RESENDE, M. G. C.. Greedy randamized adaptative search procedures. Journal of Global
Optimization, vol. 6, pp. 109 133, 1995.
GARCÍA, F. J.M. & PÉREZ, J. A.M. Optimización por enjambre para la p-mediana continua y discreta.
Quinto Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados. 2007
GILLET, B. & JOHNSON. Multi-terminal vehicke-dispatch algorithm. 1976.
GOLDBERG, D. E. Genetic algorithms in search optimization e machine learning. 1989.
GREFENSTETTE, J. J. Optimization of control parameters for genetc algorithms. IEEE Transactions on
Systems, Man and Cybernetics, vol. 1086. 1986.
HOFFMAN, L. T. & GOMEZ, A. T.. Utilização da pesquisa tabu na geração de um sistema de informação
geográfica aplicado ao problema de localização de torres de rádio transmissão. XII Seminário de computação,
Blumenal. 2003.
JOURDAN, L. & BASSEUR, M. & TALBI, E.-G. Hybridizing Exact Methods and Metaheuristics: A
taxonomy. European Journal of Operational Research, vol. 199, pp. 620 629. 2009.
LEONOR, F. A. & DOUGLAS, H. & RAIMUNDO, R. L. R. & MIRIAN, B. G. & ANTONIO, S. C.
Localização de unidades de atendimento ao cidadão: Comparação e proposta para cidade de Manaus,
utilizando o algoritmo de teitz e bart e algoritmo genético. Engep, pp. 13. 2008.
LORENA, L. A. N. Integração de modelos de localização a sistemas de informações geográficas. Operations
Research. 2001.
11
MICHAELEWICZ, M. & DAVIS, L. D. Handbook of Genetic Algorithms. Artificial Intellegence. 1994.
MLADENOVIC, N. & HANSEN, P. & PEREZ, J. A. M. The p-median problem: A survey of metaheuristic
approaches. European Journal of Operational Research, vol. ., pp. 927–939. 2007.
OSMAN, A. & ERHAN, E. An Efficient Genetic Algorithm for the p-Median Problem. Annals of Operations
Research, vol. 122, pp. 21 42. 2003.
SENNE, E. L. F. & LORENA, L. A. N. Abordagens Complementares para Problemas de p-Medianas. Revista
Produção - SciELO Brasil, 2003..
SMIDERLE, A. A. S. M. T., & V. E, W. Técnicas da Pesquisa Operacional Aplicadas a um Problema de
Cobertura de Arcos. TEMA, Sociedade Brasileira de Matemática Aplicada e Computacional, vol. 5, pp. 347–
356. 2004.
STEINER, M. T. A. & CORREA, E. S. & FREITAS, A. A. A genetic algorithm for solving a capacitated pmedian problem. SpringerLink - Numerical Algorithms - Kluwer Academic Publishers. Printed in the
Netherlands. 2004.
TARCÍSIO, B. M. & ELIAS, A. C. J. Heurísticas para o problema de alocação/localização de facilidades.
2008.
TSENG, L. Y. & WU, C. The oa-based swap method for the p-median problem. IEEE International Conference
on Systems, 2009.
WOEGINGER, G. J. Exact algorithms for np-hard problems a survey. Springer, 2570, pp. 185 207. 2003.
12