Método de geração de colunas para o problema de agrupamento centrado capacitado


 
  
      !
"#$" %'&)(*&)+,.- /10.2*&4365879&4/1:.+58;.2*=?5.@A2*3B;.- C)D 5.,.5FE)5.G.+&4- (IHJ&?,.+/?=)5.KA:.+5MLN&OHJ5F&4E)2*EOHJ&)(IHJ/)G.- D - ;./);.& Foz do Iguaçu, PR, Brasil, 09 a 11 de outubro de 2007

MÉTODO DE GERAÇÃO DE COLUNAS PARA O PROBLEMA DE AGRUPAMENTO CENTRADO CAPACITADO Edson Luiz França Senne (UNESP/FEG) [email protected] Marcos Antonio Pereira (UNESP/FEG) [email protected]

O problema de agrupamento centrado capacitado (PACC) consiste em determinar, em uma rede de n nós, um conjunto de p agrupamentos (clusters) de nós de máxima similaridade. Cada nó da rede possui uma demanda a ser atendida e cada agrupamento possui uma capacidade limitada de atendimento, mas deve cobrir as demandas de todos seus nós. O problema é conhecido ser NP-difícil e aparece em diversas situações práticas. Neste trabalho, explora-se um método de geração de colunas, desenvolvido originalmente para o problema de pmedianas para a solução do PACC. O método proposto utiliza a relaxação lagrangeana/surrogate como técnica de estabilização do processo de geração de colunas. O trabalho apresenta resultados computacionais para problemas disponíveis na literatura, a fim de demonstrar a efetividade do método proposto. Palavras-chaves: Problemas de localização, problemas de agrupamento, problema de agrupamento centrado capacitado, problema de p-medianas, relaxação lagrangeana/surrogate, geração de colunas

P PQ RSRUT8V
W XYVAZ\[XVA]W RSXYVA]^F_Y`6`.aYbY`8aYcY% dYe %f_Y`6gUdhY_Yijk% h l'mMn?mIo p?q rsut9mvwJx*myrz9o w9{?t9|~}~w??t?v€{9q ~‚ w?p9wƒ~w9„?o myq nO…mMp9o r~|u}~w9†>z?o wO‡ˆm…NwmyƒIt?ƒN…mMnJ…rM„?q ‚ q {?r~{9m Foz do Iguaçu, PR, Brasil, 09 a 11 de outubro de 2007

1. Introdução Problemas de localização de facilidades permitem descrever situações envolvendo decisões sobre a distribuição espacial de serviços emergenciais, centros de distribuição, redes de telecomunicações, análise de mercado e planejamento urbano, dentre outros. Em algumas situações determina-se que as facilidades possuem capacidade de atendimento limitado. Neste caso, os problemas de localização mais utilizados são o problema de localização de facilidades capacitado (PLFC), o problema de p-medianas capacitado (PPMC), o problema de agrupamento capacitado (PAC) e o problema de agrupamento centrado capacitado (PACC). Os problemas PPMC, PAC e PACC são semelhantes no sentido que: (1) cada vértice deve ser atendido por apenas uma facilidade; (2) os custos de atendimento são baseados em alguma medida de dissimilaridade (no PPMC, os custos correspondem às distâncias entre cada par de vértices); e (3) não há custos fixos para a instalação de facilidades, característica presente no PLFC. O PACC consiste em determinar, em uma rede de n vértices, um conjunto de p agrupamentos (clusters) de vértices de máxima similaridade. Cada vértice da rede possui uma demanda a ser atendida. Cada agrupamento possui uma capacidade limitada de atendimento, que deve ser suficiente para cobrir as demandas de todos os seus vértices. Imaginando-se que a similaridade esteja relacionada à uma medida de distância, pode-se determinar o centro geométrico dos vértices que constituem um agrupamento. A seguinte formulação matemática para o PACC foi adaptada de Negreiros e Palhano (2006): (PACC)

v ( PACC ) = Min i∈N j∈P

sujeito a: j∈P

j∈P

i∈ N

xij = 1

vi − y j

2

i∈N

x jj = p

qi xij ≤ Q x jj

xij ∈{0, 1}

j∈P i ∈ N, j ∈ P

onde: •

N é o conjunto dos índices dos vértices da rede;

•

P é o conjunto dos índices dos agrupamentos, com |P| = p;

•

vi é a posição geométrica do vértice i;

•

yj é a posição geométrica do centróide do agrupamento j;

•

qi é a demanda do vértice i.

•

Q é a capacidade máxima de atendimento da demanda de um agrupamento;

•

xij = 1, se o vértice i pertence ao agrupamento j; xij = 0, caso contrário. xjj = 1 se o agrupamento j for não-vazio; xjj = 0, caso contrário.

Neste modelo busca-se minimizar a distância total entre cada vértice e o centróide do agrupamento a que for alocado. Note que a posição geométrica do centróide depende dos

2

P PQ RSRUT8V
W XYVAZ\[XVA]W RSXYVA]^F_Y`6`.aYbY`8aYcY% dYe %f_Y`6gUdhY_Yijk% h l'mMn?mIo p?q rsut9mvwJx*myrz9o w9{?t9|~}~w??t?v€{9q ~‚ w?p9wƒ~w9„?o myq nO…mMp9o r~|u}~w9†>z?o wO‡ˆm…NwmyƒIt?ƒN…mMnJ…rM„?q ‚ q {?r~{9m Foz do Iguaçu, PR, Brasil, 09 a 11 de outubro de 2007

vértices que compõem o agrupamento, ou seja, a posição do centróide não é um parâmetro conhecido a priori. O problema é conhecido ser NP-difícil. Além disso, a não linearidade da função-objetivo dificulta o emprego de métodos exatos para resolução do PACC. Por este motivo, as técnicas para tratamento do PACC baseiam-se principalmente em métodos desenvolvidos para o PAC. Dentre estes destacam-se algoritmos construtivos (BECK & MULVEY, 1992; AHMADI & OSMAN, 2004), heurísticas baseadas em otimização de subgradientes (MULVEY & BECK, 1984), meta-heurísticas híbridas que combinam simulated annealing e busca tabu (OSMAN & CHRISTOFIDES, 1994), busca tabu adaptativa (FRANÇA et al., 1999), e colônia de formigas (FRANÇA et al., 2004). Este artigo está organizado da forma descrita a seguir. A Seção 2 destaca as semelhanças entre o PACC e o PPMC. A Seção 3 apresenta uma heurística baseada no método de geração de colunas desenvolvido para o PPMC que pode ser empregado para obtenção de soluções viáveis para o PACC. A Seção 4 descreve o algoritmo empregado neste trabalho e na Seção 5 são apresentados os resultados computacionais obtidos com o emprego da metodologia descrita. As considerações finais são discutidas na Seção 6. 2. Problemas de localização e de agrupamento

O PACC se assemelha ao PPMC, pois em ambos o objetivo é definir p agrupamentos em uma rede de modo a minimizar a soma das distâncias de cada nó de demanda até o centro mais próximo. Cada vértice possui uma demanda a ser atendida e os centros possuem uma capacidade limitada de atendimento. A diferença entre os problemas é que no PPMC os centros serão instalados em vértices (medianas) existentes, enquanto que no PACC busca-se determinar o centro geométrico do agrupamento, que nem sempre corresponde a um vértice da rede. A Figura 1 ilustra a definição de uma solução de localização-alocação para esses dois problemas.

PPMC

PACC

centróide

mediana agrupamento

Figura 1 – Solução de localização-alocação dos problemas PACC e PPMC

O PPMC é um problema clássico de localização. As técnicas de solução propostas para o PPMC exploram métodos heurísticos, incluindo: busca tabu (FRANÇA et al., 1999), relaxação lagrangeana (LORENA & SENNE, 2003), algoritmos genéticos (CORREA et al., 2004), busca dispersa (DIAZ & FERNANDEZ, 2005), ou métodos exatos, que exploram técnicas de particionamento de conjuntos (BALDACCI et al., 2002), algoritmos branch-andprice (CESELLI & RIGHINI, 2005) e modelos de Programação Inteira (WU et al., 2006). O PPMC, no entanto, também pode ser classificado como um problema de agrupamento. Associado a cada mediana existe um conjunto de nós atendidos, o que caracteriza um

3

P PQ RSRUT8V
W XYVAZ\[XVA]W RSXYVA]^F_Y`6`.aYbY`8aYcY% dYe %f_Y`6gUdhY_Yijk% h l'mMn?mIo p?q rsut9mvwJx*myrz9o w9{?t9|~}~w??t?v€{9q ~‚ w?p9wƒ~w9„?o myq nO…mMp9o r~|u}~w9†>z?o wO‡ˆm…NwmyƒIt?ƒN…mMnJ…rM„?q ‚ q {?r~{9m Foz do Iguaçu, PR, Brasil, 09 a 11 de outubro de 2007

agrupamento. Considerando a mediana como apenas um dos nós do cluster, o centro geométrico do agrupamento pode ser determinado e seu custo recalculado. Dessa forma, uma solução viável para o PPMC pode ser vista também como uma solução viável para o PACC. Neste trabalho, explora-se um método de geração de colunas, desenvolvido originalmente para o PPMC (LORENA & SENNE, 2004), para a solução do PACC. O método de geração de colunas é uma ferramenta poderosa para a solução de grandes problemas de Programação Linear (PL). Esta técnica se aplica quando as colunas de um problema de PL não são conhecidas (ou não é factível enumerá-las completamente) ou quando o problema é formulado usando a decomposição de Dantzig-Wolfe (DANTZIG & WOLFE, 1960). O método de geração de colunas tem sido aplicado com sucesso na solução de vários outros problemas, tais como: problemas de escalonamento de tripulações (DESROCHERS & SOUMIS, 1989), problemas de corte (VANCE et al., 1999), problemas de roteamento de veículos (CHOI & TCHA, 2007), problemas de máxima cobertura (PEREIRA et al., 2007). Entretanto, em muitos casos, a aplicação direta do método de geração de colunas produz muitas colunas que não são relevantes para a solução final do problema, o que pode levar a dificuldades de convergência. Diferentes técnicas têm sido propostas para tratar estas dificuldades de convergência do método de geração de colunas (BRIANT et al., 2005; DESROSIERS & LÜBBECKE, 2005). Senne et al. (2007) aplicaram a relaxação lagrangeana/surrogate como técnica de estabilização do processo de geração de colunas. Para o problema de p-medianas, mostrou-se que esta técnica permite a geração de colunas mais produtivas, o que acelera o método de geração de colunas. 3. O método de geração de colunas proposto

O PACC pode ser modelado como o seguinte problema de particionamento de conjuntos: v ( PPC ) = Min

(PPC)

(1)

ck xk k ∈M

Ak xk = 1

(2)

xk = p

(3)

xk ∈ {0,1}

(4)

sujeito a: k ∈M

k ∈M

onde: •

S = {S1, S2, ..., Sm} é o conjunto de subconjuntos de N;

•

M = {1, ..., m} é o conjunto dos índices dos elementos de S;

•

A = [aik ] é uma matriz tal que aik = 1, se i ∈ Sk , satisfazendo

i∈ N

qi aik ≤ Q , e aik = 0, caso

contrário; • •

ck =

i∈S k

d ik , onde dik é a distância entre o vértice i e o centróide do cluster Sk;

[ xk ] é um vetor de variáveis de decisão tal que xk = 1 se o conjunto S k foi escolhido como parte da solução e xk = 0, caso contrário, ∀k ∈ M.

A função-objetivo (1) corresponde à soma dos custos dos clusters escolhidos, a qual deve ser minimizada. A restrição (2) impõe que cada nó esteja alocado a apenas um centro e que a

4

P PQ RSRUT8V
W XYVAZ\[XVA]W RSXYVA]^F_Y`6`.aYbY`8aYcY% dYe %f_Y`6gUdhY_Yijk% h l'mMn?mIo p?q rsut9mvwJx*myrz9o w9{?t9|~}~w??t?v€{9q ~‚ w?p9wƒ~w9„?o myq nO…mMp9o r~|u}~w9†>z?o wO‡ˆm…NwmyƒIt?ƒN…mMnJ…rM„?q ‚ q {?r~{9m Foz do Iguaçu, PR, Brasil, 09 a 11 de outubro de 2007

capacidade total de cada centro seja respeitada. A restrição (3) garante o número de centros a serem abertos. As restrições (4) fornecem as condições de integralidade. Essa mesma formulação foi usada por Minoux (1987) para o PPMC: (PPMC)

v ( PPMC ) = Min i ∈N j ∈ N

i∈N

xij = 1

sujeito a: j∈N

j∈ N

x jj = p

(6) (7)

qi xij ≤ Q x jj

i∈ N

(5)

d ij xij

xij ∈ {0, 1}

j∈N

(8)

i ∈ N, j ∈ N

(9)

onde d ij é a distância entre os vértices i e j, e [ xij ] é uma matriz de variáveis de decisão tal que xij = 1 se o vértice i está alocado à mediana j e xij = 0, caso contrário. Notar que x jj = 1, se j for uma mediana e x jj = 0, caso contrário. A formulação (1)-(4) fornece a solução ótima do PACC. No entanto, como o número de subconjuntos pode ser muito grande, por razões práticas é preciso considerar somente um conjunto parcial de colunas K ⊂ M. Dessa forma, o PPC é conhecido como problema-mestre restrito (PMR) no processo de geração de colunas. Assim, para o método de geração de colunas proposto, em vez de considerar o PPC, considera-se como PMR o seguinte problema de PL: v ( PCC ) = Min

(PCC)

k ∈K

sujeito a: k ∈K

k ∈K

ck x k

Ak xk ≥ 1 xk = p

xk ∈ [0, 1] . Após definir um conjunto inicial de colunas, o problema PCC é resolvido e os custos duais finais π i , i ∈ N, e µ são usados para gerar novas colunas, a partir da solução do seguinte subproblema: (SPπ)

v ( SPπ ) = Min {v ( PM π ) j } j∈ N

onde ( PM π ) j é um problema da mochila definido como: (PMπ)j

v ( PM π ) j = Min i∈N

( d ij − π i ) x ij

sujeito às restrições (8) e (9), ou seja, o método proposto considera o PPMC como subproblema gerador de colunas. Para a solução dos problemas da mochila foi utilizado o algoritmo de Horowitz e Sahni (MARTELLO e TOTH, 1990). Resolvido o problema SPπ, o custo reduzido associado será

5

P PQ RSRUT8V
W XYVAZ\[XVA]W RSXYVA]^F_Y`6`.aYbY`8aYcY% dYe %f_Y`6gUdhY_Yijk% h l'mMn?mIo p?q rsut9mvwJx*myrz9o w9{?t9|~}~w??t?v€{9q ~‚ w?p9wƒ~w9„?o myq nO…mMp9o r~|u}~w9†>z?o wO‡ˆm…NwmyƒIt?ƒN…mMnJ…rM„?q ‚ q {?r~{9m Foz do Iguaçu, PR, Brasil, 09 a 11 de outubro de 2007

ŒŽ xij

‹

Š ‰ poderá ser acrescentada ao PCC se v (SPπ ) < µ . Na realidade, 1 para j = 1, ..., n, todas as colunas correspondentes que satisfazem a condição:

v (SPπ ) − µ , e a coluna

i∈N

(d ij − π i ) xij < µ

(10)

podem ser acrescentadas ao PCC, acelerando o processo de geração de colunas. A relaxação lagrangeana/surrogate é integrada ao processo de geração de colunas transferindo-se os multiplicadores πi (i = 1, ..., n) do PCC para o seguinte problema dual:

v ( Dπ ) = Max v ( Lt Pπ )

(Dπ)

t ≥0

onde LtPπ é a relaxação lagrangeana/surrogate do PPMC, dada por: (LtPπ)

v ( Lt Pπ ) = Min

i∈N j∈N

( d ij − tπ i ) xij + t

i ∈N

πi

sujeito às restrições (7), (8) e (9). Deve-se observar que, para t = 1, LtPπ é a relaxação lagrangeana tradicional para os multiplicadores π i (i = 1, ..., n). Dois problemas duais podem ser identificados na relaxação lagrangeana/surrogate: um dual externo para a variável multidimensional π , usualmente otimizado por métodos de subgradientes (LORENA e SENNE, 1999) e, para um determinado multiplicador π , o dual interno Dπ, cuja solução corresponde ao melhor valor para o multiplicador (unidimensional) t. Para determinar o melhor valor de t, foi usado o procedimento de busca SH descrito em (SENNE e LORENA, 2000). 4. O algoritmo de geração de colunas

O parâmeto t difere a relaxação lagrangeana/surrogate da relaxação lagrangeana tradicional. Dependendo do valor de t, pode-se obter limitantes lagrangeanos tradicionais (quando t = 1), ou limitantes melhores, quando t é determinado como resultado do problema Dπ. A Figura 2 mostra o algoritmo de geração de colunas GC(t) proposto: 1) Enquanto as condições de parada não forem satisfeitas, fazer: 2) Resolver o PCC, obtendo as variáveis duais πi (i = 1, ..., n) e µ; 3) Resolver o problema dual Dπ para identificar o valor do parâmetro t; 4) Resolver o subproblema gerador de colunas SPλ, com λ = tπ, e identificar as colunas que podem ser acrescentadas ao PCC, ou seja, as colunas que satisfazem a condição (10); 5) Se nenhuma coluna for identificada no passo 4, parar.

6) Acrescentar ao PCC, as colunas

ŒŽ xij

1

‹

Š ‰ identificadas no passo 4.

Figura 2 – O algoritmo GC(t) proposto

A aplicação do algoritmo GC(t) requer que um conjunto inicial de colunas seja estabelecido para o PCC. Para estabelecer as colunas iniciais gera-se, aleatoriamente, p locais (vértices) da rede. Considerando-se esses p vértices como medianas, determina-se a primeira solução

6

P PQ RSRUT8V
W XYVAZ\[XVA]W RSXYVA]^F_Y`6`.aYbY`8aYcY% dYe %f_Y`6gUdhY_Yijk% h l'mMn?mIo p?q rsut9mvwJx*myrz9o w9{?t9|~}~w??t?v€{9q ~‚ w?p9wƒ~w9„?o myq nO…mMp9o r~|u}~w9†>z?o wO‡ˆm…NwmyƒIt?ƒN…mMnJ…rM„?q ‚ q {?r~{9m Foz do Iguaçu, PR, Brasil, 09 a 11 de outubro de 2007

inteira para o PPMC correspondente. Os clusters identificados por esta solução que satisfazem as restrições (8) são incluídos como colunas do PMR inicial. Repete-se esse procedimento até que o problema-mestre restrito inicial alcance mais de 1000 colunas. Com este procedimento de geração de colunas iniciais armazena-se a melhor solução viável obtida, que é mantida inalterada durante a aplicação do algoritmo GC(t). Ao término da execução do algoritmo GC(t), procura-se melhorar a solução viável obtida para o PACC, resolvendo o PMR final como um problema de Programação Inteira. Considera-se, neste caso, apenas a primeira solução inteira encontrada. 5. Resultados computacionais

Os algoritmos descritos na seção 4 foram codificados na linguagem C e executados em um microcomputador com processador Intel Core 2 Duo de 2 GHz e 2 GB de RAM. As soluções dos problemas-mestre restritos foram obtidas utilizando ILOG CPLEX 10.1. Os resultados computacionais foram obtidos para 13 problemas-teste considerados em (LORENA e SENNE, 2004) e (NEGREIROS e PALHANO, 2006). Os resultados obtidos estão mostrados nas Tabelas 1 e 2. A Tabela 1 compara os resultados computacionais obtidos pelos algoritmos GC(t) e GC(1). A Tabela 2 compara os resultados obtidos pelo algoritmo GC(t) com os resultados obtidos pelos algoritmos pCCCP e VNS, desenvolvidos especialmente para o PACC e reportados por Negreiros e Palhano (2006). Pr ta1 ta2 ta3 ta4 ta5 ta6 ta7 sjc1 sjc2 sja3a sjc3b sjc4a sjc4b

n 25 50 60 70 80 90 100 100 200 300 300 402 402

p 5 5 5 5 7 4 6 10 15 25 30 30 40

GC(t) vGC Iter Cols 1280,49 36 1472 4478,15 42 1995 5357,34 54 2837 6240,67 43 2453 5515,46 51 3242 8899,05 105 5094 8168,36 70 3760 17975,92 45 3290 33357,75 87 8734 45379,69 78 13542 41185,18 79 13364 61969,06 85 17338 52989,44 65 14563

T 0,05 0,09 0,37 0,28 0,45 2,66 1,45 0,56 6,25 16,03 10,08 44,48 16,41

vGC 1470,50 4474,52 5357,34 6240,67 6029,69 9040,69 8195,60 17375,36 34060,73 49032,97 42402,73 62729,15 53554,43

GC(1) Iter Cols 34 1481 42 1961 62 2943 47 2573 48 3126 110 5477 75 4090 49 3605 75 8581 69 12659 66 12637 77 17359 64 14759

T 0,05 0,14 0,39 0,3 0,33 3,41 1,33 0,50 7,12 13,80 8,41 46,83 18,66

Tabela 1 – Resultados obtidos pelos algoritmos GC(t) e GC(1) pCCCP Pr ta1 ta2 ta3 ta4 ta5 ta6 ta7 sjc1 sjc2 sja3a sjc3b sjc4a sjc4b

n 25 50 60 70 80 90 100 100 200 300 300 402 402

p 5 5 5 5 7 4 6 10 15 25 30 30 40

1528,64 4605,03 5475,96 6292,06 5918,44 9646,38 8270,26 19429,46 35322,48 50254,51 76352,45 -

VNS 1257,51 4485,44 5391,47 6275,99 5846,94 9134,69 8141,70 17696,53 33423,84 47985,29 66689,96 -

vGC 1280,49 4478,15 5357,34 6240,67 5515,46 8899,05 8168,36 17975,92 33357,75 45379,69 41185,18 61969,06 52989,44

GC(t) Iter 36 42 54 43 51 105 70 45 87 78 79 85 65

Cols 1472 1995 2837 2453 3242 5094 3760 3290 8734 13542 13364 17338 14563

T 0,05 0,09 0,37 0,28 0,45 2,66 1,45 0,56 6,25 16,03 10,08 44,48 16,41

dP -16,23 -2,76 -2,17 -0,82 -6,81 -7,75 -1,23 -7,48 -5,56 -9,70 -18,84 -

dV 1,83 -0,16 -0,63 -0,56 -5,67 -2,58 0,33 1,58 -0,20 -5,43 -7,08 -

7

P PQ RSRUT8V
W XYVAZ\[XVA]W RSXYVA]^F_Y`6`.aYbY`8aYcY% dYe %f_Y`6gUdhY_Yijk% h l'mMn?mIo p?q rsut9mvwJx*myrz9o w9{?t9|~}~w??t?v€{9q ~‚ w?p9wƒ~w9„?o myq nO…mMp9o r~|u}~w9†>z?o wO‡ˆm…NwmyƒIt?ƒN…mMnJ…rM„?q ‚ q {?r~{9m Foz do Iguaçu, PR, Brasil, 09 a 11 de outubro de 2007

Tabela 2 – Comparação de resultados obtidos por GC(t) com os obtidos por pCCCP e VNS

Estas tabelas contêm: • • • • • • • • • • •

Pr – nome do problema-teste; n – número de nós da rede; p – número de centros a serem abertos; vGC – melhor solução viável obtida pelo algoritmo GC(t)/GC(1); Iter – número de iterações realizadas pelo algoritmo GC(t)/GC(1); Cols – número total de colunas geradas pelo algoritmo GC(t)/GC(1); T – tempo de processamento (em segundos); pCCCP – solução obtida pelo algoritmo pCCCP, reportada por Negreiros e Palhano (2006); VNS – solução obtida pelo algoritmo VNS, reportada por Negreiros e Palhano (2006); dP – desvio percentual entre as soluções obtida pelos algoritmos GC(t) e pCCCP, ou seja, 100*(GC(t) – pCCCP)/pCCCP; dV – desvio percentual entre as soluções obtida pelos algoritmos GC(t) e VNS, ou seja, 100*(GC(t) – VNS)/VNS.

Deve-se observar que valores negativos para dP e dV indicam que o algoritmo GC(t) conseguiu obter soluções melhores do que os algoritmos pCCCP e VNS, respectivamente. A Tabela 3 compara o desempenho dos algoritmos GC(t) e GC(1) com relação aos valores médios de número de iterações, número total de colunas geradas, tempo de processamento e desvios percentuais em relação aos algoritmos pCCCP e VNS de Negreiros e Palhano (2006). Iter 53,54

GC(t) Cols T 4904,38 5,59

dP dV -6,10 -1,43

Iter 52,92

GC(1) Cols T 4911,92 5,71

dP -3,80

dV 1,12

Tabela 3 – Valores médios obtidos pelos algoritmos GC(t) e GC(1)

6. Conclusão

Neste artigo discutiu-se um método de geração de colunas para o PACC. O método proposto utiliza o problema de p-medianas capacitado como subproblema gerador de colunas e integra a relaxação lagrangeana/surrogate como método de estabilização do processo de geração de colunas. Os resultados computacionais mostram que com esta relaxação o método de geração de colunas é capaz de identificar colunas melhores do que as identificadas com o processo tradicional de relaxação lagrangeana. Assim, o método proposto consegue ser mais rápido e obter melhores resultados do que o método tradicional. Os resultados computacionais mostram também que o algoritmo GC(t) proposto consegue melhorar as soluções reportadas por Negreiros e Palhano (2006), para a maior parte dos problemas considerados. Deve-se observar que o algoritmo GC(t) melhora todos os resultados obtidos pelo algoritmo pCCCP e melhora 8 dos 11 resultados obtidos pelo algoritmo VNS. O método proposto pode ser útil para o desenvolvimento de algoritmos do tipo branch-andprice para a solução exata do PACC.

8

P PQ RSRUT8V
W XYVAZ\[XVA]W RSXYVA]^F_Y`6`.aYbY`8aYcY% dYe %f_Y`6gUdhY_Yijk% h l'mMn?mIo p?q rsut9mvwJx*myrz9o w9{?t9|~}~w??t?v€{9q ~‚ w?p9wƒ~w9„?o myq nO…mMp9o r~|u}~w9†>z?o wO‡ˆm…NwmyƒIt?ƒN…mMnJ…rM„?q ‚ q {?r~{9m Foz do Iguaçu, PR, Brasil, 09 a 11 de outubro de 2007

Referências AHMADI, S. & OSMAN, I.H. Density based problem space search for the capacitated clustering p-median problem. Annals of Operations Research, Vol. 131, p. 21-43, 2004. BALDACCI, R.; HADJICONSTANTINOU, E.; MANIEZZO, V. & MINGOZZI A. A new method for solving capacitated location problems based on a set partitioning approach. Computers and Operations Research, Vol. 29, n. 4, p. 365-386, April 2002. BECK, M.P. & J.M. MULVEY, J.M. Constructing optimal index funds. Princeton University Report No. EES82-1, 1982 BRIANT, O.; LEMARÉCHAL, C.; MEURDESOIF, P.H.; MICHEL, S.; PERROT, N. & VANDERBECK, F. Comparison of Bundle and Classical Column Generation, Rapport de recherche de l'INRIA 5453, Rhone-Alpes, France, 2005. CESELLI, A. & RIGHINI, G. A branch-and-price algorithm for the capacitated p-median problem. Networks, Vol. 45, n. 3, p. 125-142, 2005. CHOI, E. & TCHA, D. A column generation approach to the heterogeneous fleet vehicle routing problem. Computers and Operations Research, Vol. 34, n. 7, p. 2080-2095, Jul. 2007. CORREA, E.S.; STEINER, M.T.A.; FREITAS, A.A. & CARNIERI, C. A genetic algorithm for solving a capacitated p-median problem. Numerical Algorithms, Vol. 35, n. 2-4, p. 373-388, April 2004. DANTZIG, G.B. & WOLFE, P. Decomposition principle for linear programs. Operations Research, Vol. 8, n. 1, p. 101-111, 1960. DESROCHERS, M. & SOUMIS, F. A Column Generation Approach to the Urban Transit Crew Scheduling Problem, Transportation Science, Vol. 23, p. 1-13, 1989. DESROSIERS, J. & LÜBBECKE, M.E. A primer in column generation. In: G. Desaulniers, J. Desrosiers and M.M. Solomon (Eds.), Column Generation (GERAD 25th anniversary series), Springer Science+Business Media Inc., New York, p. 1-32, 2005. DIAZ, J.A. & FERNANDEZ, E. Hybrid Scatter Search and Path Relinking for the capacitated p-median problem. European Journal of Operational Research, Vol. 169, n. 2, p. 570-585, 2005. FRANÇA, P.M.; SOSA, N.M. & PUREZA, V. An adaptive tabu search algorithm for the capacitated p-median problem, International Transactions in Operational Research, Vol. 6, p. 665-678, 1999. FRANÇA, F.O.; VON ZUBEN, F.J. & CASTRO, L.N. A min-max ant system applied to the capacitated clustering problem. In: Proceedings of the IEEE Workshop on Machine Learning for Signal Processing, p. 755764, 2004. LORENA, L.A.N. & SENNE, E.L.F. A column generation approach to capacitated pmedian problems. Computers & Operations Research, Vol. 31, n. 6, p. 863-876, 2004. LORENA, L.A.N. & SENNE, E.L.F. Improving traditional subgradient scheme for Lagrangean relaxation: an application to location problems, International Journal of Mathematical Algorithms, Vol. 1, p. 133-151, 1999. LORENA, L.A.N. & SENNE, E.L.F. Local search heuristics for capacitated p-median problems. Networks and Spatial Economics, Vol. 3, n. 4, p. 407-419, 2003. MARTELLO, S. & TOTH, P. Knapsack problems: Algorithms and computer implementations, John Wiley & Sons, 1990. MINOUX, M. A Class of Combinatorial Problems with Polynomially Solvable Large Scale Set Covering/Set Partitioning Relaxations. RAIRO, Vol. 21, n. 2, p. 105–136, 1987. MULVEY, J.M. & BECK, M.P. Solving Capacitated Clustering Problems. European Journal of Operational Research, Vol. 18, 339–348, 1984. NEGREIROS, M. & PALHANO, A. The capacitated centred clustering problem. Computers & Operations Research, Vol. 33, n. 6, p. 1639-1663, 2006. OSMAN, I.H. & CHRISTOFIDES, N. Capacitated clustering problems by hybrid simulated annealing and tabu search. International Transactions in Operational Research, Vol. 1, n. 3, p. 317-336, 1994.

9

P PQ RSRUT8V
W XYVAZ\[XVA]W RSXYVA]^F_Y`6`.aYbY`8aYcY% dYe %f_Y`6gUdhY_Yijk% h l'mMn?mIo p?q rsut9mvwJx*myrz9o w9{?t9|~}~w??t?v€{9q ~‚ w?p9wƒ~w9„?o myq nO…mMp9o r~|u}~w9†>z?o wO‡ˆm…NwmyƒIt?ƒN…mMnJ…rM„?q ‚ q {?r~{9m Foz do Iguaçu, PR, Brasil, 09 a 11 de outubro de 2007

PEREIRA, M.A.; LORENA, L.A.N. & SENNE, E.L.F. A column generation approach for the maximal covering location problem. International Transactions in Operational Research, artigo aceito em 2007 para publicação, aguarda impressão. SENNE, E.L.F. & LORENA, L.A.N. Lagrangean/Surrogate Heuristics for p-Median Problems. In Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research, M. Laguna and J.L. Gonzalez-Velarde (Eds.), Kluwer Academic Publishers, p. 115-130, 2000. SENNE, E.L.F.; LORENA, L.A.N. & PEREIRA, M.A. A simple stabilizing method for column generation heuristics: an application to p-median location problems. International Journal of Operations Research, artigo aceito em 2007 para publicação, aguarda impressão. VANCE, P. Crew scheduling, cutting stock and column generation: solving huge integer programs. PhD thesis, Georgia Institute of Technology, 1993. WU, L.Y.; ZHANG, X.S. & ZHANG, J.L. Capacitated facility location problem with general setup cost, Computers and Operations Research, Vol. 33, n. 5, p. 1226-1241, May 2006.

Agradecimento: Este trabalho foi parcialmente financiado pelo CNPq – Conselho Nacional de Desenvolvimento Científico e Tecnológico (processos 306189/2006-2 e 010642/2006-4). Os autores agradecem o apoio financeiro recebido.

10