Um Algoritmo Evolucionário para o Problema Dinâmico de

UNIVERSIDADE DO RIO GRANDE DO NORTEFEDERAL

UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE

CENTRO DE TECNOLOGIA

PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E

DE COMPUTAÇÃO

Um Algoritmo Evolucionário para o ProblemaDinâmico de Localização de Facilidades com

Capacidades Modulares

Allyson Fernandes da Costa Silva

Orientador: Prof. Dr. Daniel Aloise

Dissertação de Mestrado apresentada aoPrograma de Pós-Graduação em EngenhariaElétrica e de Computação da UFRN (área deconcentração: Engenharia de Computação)como parte dos requisitos para obteção do tí-tulo de Mestre em Ciências

.

Número de ordem PPgEE: M495Julho 2016, Natal, Brasil

Silva, Allyson Fernandes da Costa. Um algoritmo evolucionário para o problema dinâmico delocalização de facilidades com capacidades modulares / AllysonFernandes da Costa Silva. - 2017. 105 f.: il.

Dissertação (mestrado) - Universidade Federal do Rio Grandedo Norte, Centro de Tecnologia, Programa de Pós-Graduação emEngenharia Elétrica e de Computação. Natal, RN, 2017. Orientador: Prof. Dr. Daniel Aloise.

1. Localização dinâmica de facilidades - Dissertação. 2.Capacidade modular - Dissertação. 3. Metaheurística híbrida -Dissertação. 4. Algoritmo Genético - Dissertação. 5. VariableNeighborhood Search - Dissertação. I. Aloise, Daniel. II.Título.

RN/UF/BCZM CDU 004

Universidade Federal do Rio Grande do Norte - UFRNSistema de Bibliotecas - SISBI

Catalogação de Publicação na Fonte. UFRN - Biblioteca Central Zila Mamede

Resumo

Problemas de localização buscam determinar as melhores posições onde devem serinstaladas facilidades de modo a atender demandas existentes. Pela vasta aplicabilidadeda área, diversas características já foram importadas aos modelos para melhor represen-tar situações práticas. Uma delas generaliza os modelos clássicos para situações em quedecisões de localização devem ser tomadas periodicamente. Outra, permite que modelostratem do dimensionamento das capacidades como uma variável do problema. O Pro-blema Dinâmico de Localização de Facilidades com Capacidades Modulares unifica estase outras características presentes em problemas de localização num único e generalizadomodelo. Este problema foi recentemente formulado na literatura, onde uma abordagemexata foi introduzida e aplicada a instâncias derivadas de um estudo de caso no contexto daexploração de recursos florestais. Neste trabalho será apresentado um método alternativopara resolver o mesmo problema. O método escolhido utiliza a estrutura da metaheurís-tica Algoritmo Genético e a hibridiza com uma rotina de Descida em Vizinhança Variávelcom três vizinhanças de busca adaptadas de vizinhanças aplicadas a outros problemas delocalização. Experimentos atestaram a efetividade da metaheurística híbrida desenvolvidaem comparação à aplicação dos métodos puros. Na comparação com o método exato, aheurística se mostrou competente ao chegar a soluções até 0,02% de distância do ótimona maioria das instâncias testadas.

Palavras-chave: localização dinâmica de facilidades, capacidade modular, metaheu-rística híbrida, Algoritmo Genético, Variable Neighborhood Search

Abstract

Location problems aim to determine the best positions where facilities should be ins-talled in order to meet existing demands. Due to its wide applicability, several characte-ristics have already been appended to the models to better represent real situations. Oneof them generalizes classical models to the case that location decisions should be takenperiodically. Another allows models to deal with capacity sizing as a problem variable.The Dynamic Facility Location Problem with Modular Capacities unifies these and othercharacteristics present in location problems in a single and generalized model. This pro-blem was recently formulated in literature where an exact approach was introduced andapplied to instances of a case study in the context of the forestry sector. We present analternative method to solve the same problem. The method chosen uses a Genetic Algo-rithm metaheuristic framework and hybridizes it with a Variable Neighborhood Descentroutine with three neighborhoods adapted from others applied to location problems. Ex-periments attested the effectiveness of the hybrid metaheuristic developed in comparisonto the use of those methods purely. Compared to the exact approach, the heuristic provedto be competent by finding solutions up to a gap of 0,02% to the global optimum in themajority of the instances tested.

Keywords: dynamic facility location, modular capacity, hybrid metaheuristic, Gene-tic Algorithm, Variable Neighborhood Search

Sumário

Lista de Figuras iii

Lista de Tabelas v

Lista de Algoritmos vii

Lista de Nomenclaturas e Símbolos ix

1 Introdução 1

2 Revisão da Literatura 72.1 A localização de facilidades na teoria de localização . . . . . . . . . . . . 7

2.1.1 Classificações dos modelos de FLP . . . . . . . . . . . . . . . . 82.1.2 CFLP e a classe de modelos capacitados . . . . . . . . . . . . . . 92.1.3 DFLP e a classe de modelos dinâmicos . . . . . . . . . . . . . . 112.1.4 Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2 Apresentação do DFLPG . . . . . . . . . . . . . . . . . . . . . . . . . . 152.2.1 Classificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.2.2 Modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3 Métodos de solução dos FLPs . . . . . . . . . . . . . . . . . . . . . . . 192.3.1 Métodos heurísticos . . . . . . . . . . . . . . . . . . . . . . . . 202.3.2 Busca em vizinhança . . . . . . . . . . . . . . . . . . . . . . . . 212.3.3 Metaheurísticas . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.4 Discussão da literatura . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3 Descrição do algoritmo 253.1 Visão geral sobre o Algoritmo Genético . . . . . . . . . . . . . . . . . . 253.2 Estruturas do AG+VNDi . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.2.1 Estrutura do indivíduo . . . . . . . . . . . . . . . . . . . . . . . 273.2.2 Avaliação do indivíduo . . . . . . . . . . . . . . . . . . . . . . . 283.2.3 População inicial . . . . . . . . . . . . . . . . . . . . . . . . . . 293.2.4 Operadores do Algoritmo Genético . . . . . . . . . . . . . . . . 303.2.5 Vizinhanças . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.2.6 Elitismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433.2.7 Reinício da população . . . . . . . . . . . . . . . . . . . . . . . 44

3.3 Pseudo-código do AG+VNDi . . . . . . . . . . . . . . . . . . . . . . . . 44

i

3.4 Outras considerações sobre o AG+VNDi . . . . . . . . . . . . . . . . . . 45

4 Experimentos computacionais 494.1 Ordem de exploração das vizinhanças . . . . . . . . . . . . . . . . . . . 504.2 Configuração dos parâmetros . . . . . . . . . . . . . . . . . . . . . . . . 524.3 Análise de convergência . . . . . . . . . . . . . . . . . . . . . . . . . . 544.4 Análise de impacto de outras estruturas do algoritmo . . . . . . . . . . . 55

4.4.1 Tabela hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554.4.2 Critérios de aceitação de indivíduos . . . . . . . . . . . . . . . . 564.4.3 Listas de soluções do VND . . . . . . . . . . . . . . . . . . . . . 58

4.5 Comparação com um método exato . . . . . . . . . . . . . . . . . . . . 594.6 Análise de complexidade do algoritmo . . . . . . . . . . . . . . . . . . . 63

5 Considerações Finais 67

Referências bibliográficas 69

A Resultados dos experimentos 77

Lista de Figuras

1.1 Problema de Weber . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Função escada do custo de instalação de módulos . . . . . . . . . . . . . 4

2.1 Representação de módulos (a) horizontais e (b) verticais . . . . . . . . . 14

3.1 Representação do indivíduo . . . . . . . . . . . . . . . . . . . . . . . . . 273.2 Exemplo de grafo gerado para o FCM . . . . . . . . . . . . . . . . . . . 283.3 Operador de seleção de indivíduos para nova geração . . . . . . . . . . . 313.4 Operador de cruzamento . . . . . . . . . . . . . . . . . . . . . . . . . . 323.5 Operador de mutação . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.6 Operação 3: Corte vertical de segmentos de genes . . . . . . . . . . . . . 353.7 Operações 4 e 5: Corte vertical e horizontal de facilidades . . . . . . . . 353.8 Iterações da BL1 - adição de um segmento a facilidade . . . . . . . . . . 373.9 Iterações de troca de segmentos da BL2 . . . . . . . . . . . . . . . . . . 383.10 Operações da BL3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.1 Convergência da melhor solução por tempo de execução do AG e doAG+VNDi nas instâncias (a) 10/20, (b) 10/50 e (c) 50/50 . . . . . . . . . 55

4.2 Crescimento do tamanho da tabela hash . . . . . . . . . . . . . . . . . . 644.3 Quantidade de novas chaves adicionadas a THASH em cada geração . . . . 654.4 Variação em P da quantidade de chaves em THASH . . . . . . . . . . . . . 66

iii

Lista de Tabelas

3.1 Atributos dos arcos no grafo do FCM . . . . . . . . . . . . . . . . . . . 293.2 Operações de vizinhança realizadas nas buscas locais . . . . . . . . . . . 36

4.1 Resultados computacionais da aplicação de vizinhanças isoladas no VND 504.2 Resultados computacionais da aplicação de pares de vizinhanças no VND 514.3 Resultados computacionais da aplicação das três vizinhanças no VND . . 514.4 Resultados computacionais da configuração dos parâmetros . . . . . . . . 524.5 Combinação de parâmetros dominantes . . . . . . . . . . . . . . . . . . 534.6 Resultados computacionais de ajuste da taxa de mutação . . . . . . . . . 534.7 Comparação do AG+VNDi com e sem uso de THASH . . . . . . . . . . . 564.8 Comparação do AG+VNDi com e sem critério de aceitação de indivíduos

diferentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574.9 Comparação do AG+VNDi com diferentes parâmetros como critério de

aceitação de indivíduos em termos de seus custos de localização . . . . . 584.10 Comparação do AG+VNDi com e sem uso de listas de soluções encon-

tradas nas vizinhanças exploradas . . . . . . . . . . . . . . . . . . . . . 594.11 Resultados do AG+VNDi comparados às instâncias resolvidas a otimali-

dade pelo método exato de Jena et al. (2015a) . . . . . . . . . . . . . . . 614.12 Comparação entre o AG+VNDi e o método de Jena et al. (2015a) nas

instância não-resolvidas a otimalidade pelo método exato . . . . . . . . . 624.13 Tamanho da tabela hash ao final da execução do AG+VNDi . . . . . . . . 63

A.1 Resultados dos experimentos para L = 3 . . . . . . . . . . . . . . . . . . 77A.2 Resultados dos experimentos para L = 5 . . . . . . . . . . . . . . . . . . 80A.3 Resultados dos experimentos para L = 10 . . . . . . . . . . . . . . . . . 83

v

Lista de Algoritmos

1 Estrutura básica do VND . . . . . . . . . . . . . . . . . . . . . . . . . . 232 Estrutura básica do AG . . . . . . . . . . . . . . . . . . . . . . . . . . . 263 Mutação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334 Deslocamento de módulos na BL3 . . . . . . . . . . . . . . . . . . . . . 425 Elitismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456 Pseudocódigo do AG+VNDi . . . . . . . . . . . . . . . . . . . . . . . . 48

vii

Lista de Nomenclaturas e Símbolos

NomenclaturasAG Algoritmo Genético

AG+VNDi Algoritmo Genético com Descida em Vizinhança Variável iterada

BL Heurística de busca local

BL1 Busca Local 1

BL2 Busca Local 2

BL3 Busca Local 3

CFLP Problema de Localização de Facilidades Capacitadas

DFLP Problema Dinâmico de Localização de Facilidades

DFLPG Problema Dinâmico de Localização de Facilidades com Capacidades Modu-lares

FCM Fluxo a Custo Mínimo

FLP Problema de Localização de Facilidades

GMC Generalized Modular Capacities

HC1 Heurística Construtiva 1

HC2 Heurística Construtiva 2

MCFLP Problema de Localização de Facilidades com Capacidades Modulares

MIP Programação inteira mista

PO Pesquisa Operacional

UFLP Problema de Localização de Facilidades Não-capacitadas

VND Descida em Vizinhança Variável

WP Problema de Weber

ix

Símbolos%mut Parâmetro de probabilidade do operador de mutação ser executado num in-

divíduo gerado no cruzamento

α Porcentagem do total de indivíduos que compõe a classe A da geração

β Porcentagem do total de indivíduos que compõe a classe B da geração

I Conjunto de clientes

J Conjunto de potenciais locais para instalação de facilidades

L Conjunto de módulos potenciais de uma facilidade

Nn(•) n-ésima vizinhança de uma solução •

Pg Conjunto de indivíduos (população) vivos na geração g

T Conjunto de períodos de tempo no horizonte de planejamento

ρ Distância máxima da pior solução que pode ser encontrada pelo algoritmoaproximativo

C Comprimento de um segmento de módulos

cti jl Custo unitário de transporte da facilidade j operando com l módulos para o

cliente i no período t

dti Demanda do cliente i no período t

etjl1l2

Custo da decisão de mudança do módulo l1 para l2 numa facilidade j noperíodo t

f (•) Custo (aptidão) da solução •

GR Parâmetro da quantidade de gerações para realizar um reinício da população

G jt Gene do indivíduo que representa o módulo aberto na facilidade j no períodot

gajt Custo fixo de abertura de facilidade no DFLP

g fjt Custo fixo de fechamento de facilidade no DFLP

GV ND Parâmetro de quantidade de gerações para se realizar um elitismo

H j Altura da facilidade j representada pelo seu maior módulo aberto no hori-zonte de planejamento

hCut(l) Corte horizontal no módulo l

l j Módulo instalado na facilidade antes do início do horizonte de planejamento

Ln Lista contendo soluções resultantes após a execução da busca local n

N Quantidade de vizinhanças definidas de uma solução

P Parâmetro de tamanho da população

R Parâmetro da quantidade de reinícios da população em cada execução doAG+VNDi

S jtit f Segmento de genes do indivíduo que representa se um módulo em j perma-

nece aberto entre os períodos ti e t f

THASH Tabela hash que armazena as soluções encontradas pelo algoritmo de FCM

tmax Parâmetro de tempo máximo de execução do AG+VNDi

u jl Capacidade total instalada na facilidade j quando aberto o módulo l

vCut(t) Corte vertical no período t

xti jl Variável de decisão das alocações

ytjl1l2

Variável de decisão das decisões de localização

Capítulo 1

Introdução

Em uma rede logística, a decisão de localização de facilidades consiste em determinarposições ideais onde serão instalados os recursos que darão suporte ao funcionamento darede. É uma importante decisão gerencial a nível estratégico no planejamento da redede distribuição em organizações de todos os setores econômicos, tanto públicas (escolas,hospitais, etc.) quanto privadas (bancos, fábricas, escritórios, etc.) [Owen & Daskin1998].

Para escolher adequadamente o local onde as facilidades serão instaladas, os decisoresdevem levar em consideração as características da rede na qual as facilidades servirão desuporte. As características mais comuns são relacionadas às exigências dos clientes queserão servidos pela empresa, como distância ou tempo para entrega. Dependendo do sis-tema, também pode ser relevante considerar atributos relacionados aos fornecedores dasmatérias-primas, aos bens ou serviços ofertados, à infraestrutura existente, às empresasconcorrentes, aos aspectos ambientais, entre outros.

O Problema de Localização de Facilidades (FLP, Facility Location Problem) é umproblema bem estabelecido com uma vasta literatura de livros e artigos escritos sobreo tema que faz parte da área de otimização de sistemas na Pesquisa Operacional (PO).Drezner & Hamacher (2001) e Farahani & Hekmatfar (2009) são alguns dos livros queabordam o tema no contexto da PO apresentando uma coletânea de modelos e aplicaçõesjá publicados. A terminologia adotada neste trabalho será voltada a aplicações na logísticade distribuição de cargas e gerenciamento de cadeias de suprimentos. Porém, pode serconvertida a outras aplicações como Drezner & Hamacher (2001) apresentam, como narobótica e nas telecomunicações.

A PO busca aplicar métodos analíticos para ajudar os decisores a tomarem uma de-cisão que atenda às necessidades da companhia. Um dos métodos é a otimização ma-temática do problema formulado através de um modelo matemático que represente ascaracterísticas mais relevantes do sistema em questão. Um modelo matemático na PO éconstituído por elementos relacionados às decisões a serem tomadas pelo decisor (variá-veis de decisão), ao objetivo do problema (funções objetivo) e às suas restrições. Especi-ficamente na literatura dos FLPs, as variáveis de decisão são relacionadas às localizaçõesdas facilidades e aos fluxos da rede. Já a função objetivo busca otimizar o sistema deacordo com a estratégia de negócios da empresa, sendo o mais comum a minimizaçãode custos do sistema. Uma infinidade de restrições podem ser consideradas no modelo,

2 CAPÍTULO 1. INTRODUÇÃO

sendo a mais trivial o atendimento às exigências dos clientes.Além do desafio de formular modelos de FLPs bem representativos para cada caso em

estudo, um fator que motiva o desenvolvimento das pesquisas na área é a dificuldade deresolver otimamente estes problemas. Em aplicações reais, é normal encontrar problemasde tamanho absurdamente gigante com relação ao número de variáveis - especificamentede variáveis inteiras [Revelle et al. 2008] - e restrições. Em certas situações, encon-trar manualmente uma solução viável num FLP requer recursos (financeiro, mão-de-obra,temporal, etc.) que não estão prontamente disponíveis aos decisores. Nestes casos, não háalternativa senão recorrer ao auxílio da automatização para a tomada da decisão. A esco-lha do método mais adequado é definida pelo balanceamento entre a qualidade da soluçãocapaz de ser encontrada e a quantidade de recursos necessários para obtê-la. De maneirageral, o melhor método é aquele que encontra as melhores soluções dada as restrições derecursos disponíveis do decisor.

O estudo analítico de decisão da localização de facilidades vem sendo tratado for-malmente na literatura pelo menos desde meados do século XX, quando Alfred Weber[Weber 1929] popularizou o clássico problema geométrico da mediana espacial. O Pro-blema de Weber (WP) é um problema de localização de facilidades simples que consisteem determinar o ponto ótimo em um espaço Euclideano para instalar uma única facilidadede modo a minimizar custos de transporte proporcionais às distâncias entre a facilidadee os pontos de demanda (clientes). Este ponto ótimo é chamado de mediana espacial, oumediana geométrica, por estar localizada na mediana dos pontos de demanda. Em relaçãoaos vértices de um quadrado, como na Figura 1.1, a mediana espacial está localizada exa-tamente no centro quando os pesos dos vértices são iguais. Desde então, novos modelostem extendido o WP ao tentar incorporar as diversas características das situações reaisdos FLPs.

Figura 1.1: Problema de Weber

Localizar uma facilidade o mais próximo possível dos clientes tem o atrativo de redu-zir os custos de alocação proporcionais à distância percorrida para ou pelos clientes. Estaé uma boa estratégia, por exemplo, na localização de escolas primárias que atendam a umpúblico restrito ao bairro em que ela está localizada. Neste caso, minimizar a distância,e, possivelmente, o tempo, que seus alunos têm de percorrer para chegar até ela é um

3

fator relevante para o seu sucesso. Porém, nem sempre esta estratégia é economicamentemelhor. Uma extensão popular do WP nos FLPs é a consideração de custos relacionadosdiretamente ao local onde poderá ser construída uma nova facilidade. Um exemplo se-ria localizar um aeroporto em meio a um centro urbano, o que geraria incômodo sonoronos locais residenciais próximos, maior risco de colisões das aeronaves com os edifícios,dentre outros problemas. Embora os potenciais clientes do aeroporto possam morar nes-tas zonas residenciais, localizar a facilidade muito próxima deles geraria uma penalidademaior que o benefício da redução do deslocamento dos passageiros até lá. Nestes ca-sos, uma penalidade em forma de custo de localização é atribuída a um potencial localindesejado, ou menos desejado, no modelo.

Melo et al. (2009) apresentam características que geralmente são consideradas numproblema de localização de facilidades no contexto da gestão de cadeias de suprimentos.São conhecidos os conjuntos de clientes distribuídos num espaço e de potenciais locaisonde facilidades podem ser instaladas para servir suas demandas. Distâncias, tempos oucustos entre clientes e facilidades são medidos por uma dada métrica. O modelo deveser capaz de responder pelo menos às seguintes questões: "Quais facilidades devem serabertas e quais clientes devem ser servidos por estas de modo a minimizar o custo total dosistema?". Variações destas questões, ou mesmo novas questões, devem ser respondidaspelo modelo quando novas configurações são acrescentadas.

Antes de apresentar ao leitor o problema tratado neste estudo é preciso introduzirduas das classes de FLPs mais conhecidas em que o problema se enquadra: os FLPscapacitados e os FLPs dinâmicos.

Os Problemas de Localização de Facilidades Capacitadas (CFLP) consideram queas facilidades a serem localizadas possuem um limite de capacidade de atendimento dasdemandas. Estes limites são representados nos modelos como restrições de capacidade.Modelos mais elaborados flexibilizam estas restrições, permitindo, por exemplo, que ascapacidades das facilidades sejam dimensionáveis. Nestes casos, além de decidir ondeuma facilidade será localizada, o modelo responde também qual a capacidade a ser insta-lada nela.

Ao localizar uma facilidade deve ser levado em consideração seus custos de constru-ção e produção. Economias de escala ocorrem em facilidades que o custo de produçãounitário reduz a medida em que a facilidade expande. Jena et al. (2015a) explicam queeste conceito é importante na representação de estruturas de custos de ajuste de capacida-des na prática, especialmente em aplicações de grande escala, onde adicionar capacidadea uma facilidade se torna mais barato até o limite máximo de capacidade possível.

A configuração de capacidades pode ser representada por variáveis contínuas (qual-quer tamanho é possível) ou discretas (através de uma função escada). Neste caso, umadas formas de representar nos modelos as possibilidades de ajuste de capacidade nas fa-cilidades é através de estruturas modulares. Um módulo é representado por um índiceatrelado às variáveis de decisão de localização e possui um custo de instalação e umacapacidade incremental. Uma função escada representando o custo total de instalação demódulos numa facilidade é mostrada na Figura 1.2. A função de custo de instalação, as-sim como a de capacidade incrementada, não necessariamente cresce de forma linear emrelação ao número de módulos instalados, o que permite a representação de módulos com


diferentes parâmetros nos modelos.

Figura 1.2: Função escada do custo de instalação de módulos

A representação em matrizes das estruturas dos módulos permite a criação de modelosmais flexíveis. Deste modo, uma facilidade pode ter sua capacidade expandida ou redu-zida apenas alterando a variável que representa o número de módulos instalados. Estecaso especial dos CFLPs torna muito mais abrangente a aplicação de modelos de locali-zação.

Os Problemas Dinâmicos de Localização de Facilidades (DFLP), ou multiperíodos,consideram a passagem do tempo como uma característica relevante para a configuraçãoda rede. Nesta classe, são levadas em conta variações nos parâmetros do problema, comocustos e demandas, ao longo do horizonte de planejamento, permitindo que decisões se-jam tomadas a cada período de tempo de modo a readequar a rede aos novos parâmetros.Um DFLP deve ser capaz de responder não apenas onde localizar as facilidades mas tam-bém quando as abrir, mover ou fechar.

Existem outras diversas classes de FLPs na literatura (hierarquia, hubs, concorrentes,estocásticas, etc.), porém a discussão detalhada de cada uma delas foge do escopo destetrabalho. Há ainda modelos de localização de facilidades que não são relacionados aoProblema de Weber, como os problemas de cobertura, de centro, dentre outros. Descriçõesdos diversos tipos de FLPs são mostradas nos livros de Farahani & Hekmatfar (2009) ede Arabani & Farahani (2012).

Este estudo lidará com o Problema Dinâmico de Localização de Facilidades com Ca-pacidades Modulares (DFLPG, Dynamic Facility Location Problem with Generalized Mo-dular Capacities). Este problema foi introduzido por Jena et al. (2015b) e foi formuladocomo um problema de programação inteira mista (MIP), sendo uma generalização demodelos existentes na literatura do CFLP num contexto dinâmico.

A modelagem do DFLPG foi inspirada num projeto industrial de uma madeireira quedeveria decidir a localização de campos de exploração para acolher trabalhadores envol-vidos em atividades de coleta de madeira, otimizando os custos logísticos de localizaçãoe de transporte. A descrição detalhada do problema é encontrada no referido trabalho em

5

que foi introduzido.Em resumo das características consideradas, o DFLPG trata de um problema em que

facilidades com estrutura modular devem ser localizadas de modo a atender demandasconhecidas minimizando os custos de instalação dos módulos e de distribuição das mer-cadorias. Tudo isto num contexto dinâmico que permita que as decisões de localização(construção, ampliação, redução ou fechamento de facilidades) e de alocação (facilidade-cliente) sejam tomadas periodicamente. Adicionalmente, o modelo é flexível o bastantepara considerar estruturas de custo de instalação de módulos complexas, sendo definidaspara cada par de níveis de capacidade em uma matriz de custos, como na função escadamostrada na Figura 1.2. Em uma extensão à primeira pesquisa sobre o DFLPG, Jenaet al. (2015a) desenvolvem um modelo robusto de MIP e provam a sua dominância sobremodelos existentes adaptados ao problema. Instâncias com até 100 locais potenciais parainstalação das facilidades servindo a até 1000 clientes foram utilizadas em seus testes eserão usadas neste trabalho como benchmarking para avaliação do método aqui desenvol-vido.

A maioria dos FLPs, incluindo os CFLPs, estão na classe dos problemas NP-difíceis,que, na teoria da complexidade computacional, são problemas que nenhum algoritmoconhecido consegue resolver otimamente em um tempo computacional de ordem polino-mial. Entretanto, graças ao avanço da PO, problemas complexos como estes estão cadavez mais tratáveis devido ao melhor entendimento da estrutura dos problemas de oti-mização combinatória, bem como o desenvolvimento de algoritmos especializados pararesolução. Tanto técnicas para encontrar resultados ótimos quanto métodos aproximati-vos tem sido vastamente pesquisados na literatura. Farahani & Hekmatfar (2009) revisamdiversos métodos já publicados para resolver problemas nas diferentes classes de FLPs.

Como mostrado anteriormente, a escolha do método mais adequado depende da na-tureza da aplicação. Métodos exatos, ou seja, que garantidamente encontram a solu-ção ótima do problema, costumam ser atrativos para aplicações de menor escala (poucasrestrições e variáveis de decisão) ou para instâncias pequenas de aplicações complexas.Quando o problema se torna complexo demais, recorre-se aos métodos heurísticos. Estesbuscam encontrar soluções de forma mais rápida que satisfaçam as necessidades do deci-sor sem a garantia de otimalidade. Na ciência da computação, as heurísticas são técnicasdesenvolvidas para serem rápidas em suas execuções de modo a encontrar soluções pró-ximas à ótima. Heurísticas são especialmente atrativas em problemas dinâmicos devidoà incerteza de parâmetros futuros, como mudanças nas demandas. Nestes casos, obteruma solução ótima para o problema não tem valor prático maior que uma solução apro-ximativa. Um algoritmo de execução mais rápida permite que o decisor teste diferentessimulações de cenários numa situação em que os dados sejam imprecisos ou desconheci-dos.

No estudo feito por Jena et al. (2015b) foi desenvolvido um método exato para resolvero DFLPG. O MIP apresentado mostrou-se dominante e bastante eficiente quando compa-rado com outros dois métodos exatos. Porém, o modelo teve dificuldade para resolverparte das instâncias testadas dentro de um limite de tempo de seis horas de execução.

A principal contribuição deste trabalho é apresentar um método heurístico alternativoao modelo exato capaz de tratar o DFLPG de forma rápida e eficaz. Para isto foi escolhido


o Algoritmo Genético (AG), uma metaheurística inspirada no processo de seleção natu-ral pertencente à classe dos algoritmos evolucionários e com várias aplicações nas maisvariantes classes de FLPs. Para melhorar a qualidades das soluções o AG periodicamentepassa por uma fase de Descida em Vizinhança Variável (VND, Variable NeighborhoodDescent), quando são aplicadas sequencialmente diversas heurísticas de busca local (BL)desenvolvidas a partir de adaptações de BLs eficazes em outros problemas de localiza-ção. Algoritmos evolucionários híbridos como este já foram aplicados com sucesso paraoutros FLPs, como em Wollenweber (2008) e Fernandes et al. (2014).

O restante do trabalho está organizado como descrito a seguir. No capítulo 2 serámostrada uma revisão da literatura de localização de facilidades e a descrição do pro-blema tratado. Métodos heurísticos relacionados ao desenvolvido serão apresentados aofim do capítulo. No capítulo 3 será feita uma breve apresentação da estrutura básica deAlgoritmos Genéticos para, a partir dela, serem descritos e analisados os operadores cri-ados para o DFLPG, incluindo as buscas locais utilizadas no VND iterado. No capítulo 4serão mostrados os resultados dos experimentos computacionais feitos. Os experimentosdefinem a ordem de exploração das vizinhanças no VND e a configuração dos parâmetrosdo algoritmo. Eles ainda atestam a qualidade de algumas das estruturas implementadasno algoritmo e da hibridização com o VND. Por fim a comparação com o método exato érealizada e a complexidade do algoritmo é analisada. O capítulo 5 encerra este trabalhocom as considerações finais sobre o estudo.

Capítulo 2

Revisão da Literatura

Este capítulo inicia apresentando como os problemas de localização de facilidadessão abordados na Pesquisa Operacional para situar melhor o leitor quanto à maturidadeda área. As classes de FLPs mais relevantes relacionadas ao problema trabalhado nestadissertação são brevemente discutidas, bem como exemplos de aplicações destes méto-dos. Em seguida, o DFLPG é classificado e seu modelo matemático é mostrado conformeapresentado na literatura. Por fim, métodos de solução dos FLPs serão debatidos conver-gindo até o método heurístico escolhido para resolver o problema desta dissertação.

2.1 A localização de facilidades na teoria de localização

Na teoria de localização quando se fala em "localização de facilidades"estamos nosreferindo a modelagem, formulação e resolução de uma classe de problemas que podemser resumidos a localizar facilidades em um dado espaço [Farahani & Hekmatfar 2009].

O objetivo dos problemas de localização é determinar a melhor posição onde devemser instaladas facilidades de modo a atender um conjunto de requerimentos desejados,geralmente demandas de clientes espalhados numa área. Pelo menos dois agentes comdiferentes interesses são identificados neste problema. Empresas buscam localizar faci-lidades de forma a maximizar seus lucros enquanto que clientes escolhem localizaçõesque lhes ofereçam o melhor nível de serviço. Na visão da firma, maximização de lucropode significar aumento de market share em mercados competitivos ou redução de custostornando as operações mais eficientes. Na visão do cliente, o nível de serviço é atribuídoa algum valor que for adicionado ao serviço baseado na localização da facilidade. O valormais comumente considerado é relacionado à distância entre a facilidade e o cliente.

Outros aspectos também podem ser considerados dependendo do tipo de serviço ofer-tado, como o tempo de deslocamento necessário para o produto chegar ao cliente, ou oestado da rota a ser percorrida neste deslocamento. Estes fatores podem ainda ser trans-formados em uma função de custo utilizada como medida da eficiência da rede.

A decisão de localização é um elemento crucial no planejamento estratégico das em-presas. Os seus impactos afetam diretamente decisões futuras a níveis tático e operacio-nal. Os altos custos associados à construção de facilidades e aquisição de propriedadesfazem com que projetos de localização e realocação de facilidades sejam investimentos delongo prazo. Desta forma, tomadores de decisão devem ser cautelosos quanto às decisões

8 CAPÍTULO 2. REVISÃO DA LITERATURA

tomadas para garantir o sucesso duradouro dos negócios.O estudo analítico da localização de facilidades iniciou-se formalmente em 1909

quando o economista alemão Alfred Weber, em seu estudo Über den Standort der In-dustrien (Sobre a Localização de Indústrias, em tradução livre), considerou um problemaem que uma única facilidade deveria ser posicionada de modo a minimizar a distânciaponderada total entre ela e os pontos de demanda. O Problema de Weber [Weber 1929],como ficou popularizado, é uma generalização do problema geométrico da mediana es-pacial e do problema do Ponto de Fermat formulados no século XVII. O WP deu ori-gem a um extraordinário número de generalizações, extensões e modificações [Drezner &Hamacher 2001]. Revisões deste clássico podem ser encontradas em Wesolowsky (1993)e Drezner et al. (2002). Uma extensão bem conhecida do WP que requer a localização dep facilidades numa área contínua é o problema de localização das p-medianas, introdu-zido por Hakimi (1964). Kariv & Hakimi (1979) provam que o problema das p-medianasé NP-difícil. Mladenovic et al. (2007) fazem uma revisão do problema e das instânciasmais usadas na literatura até então, e apresentam uma série de estudos com heurísticas emetaheurísticas para resolvê-lo.

Uma abordagem mais próxima ao contexto de localização de facilidades foi introdu-zida por Balinski (1965) a partir do problema das p-medianas. Nela, são consideradoscustos de construção das facilidades, bem como eliminada a exigência da existência de pfacilidades, tornando o número de facilidades a serem localizadas endógeno, ou seja, umavariável do problema.

O problema descrito é amplamente conhecido como Problema de Localização de Faci-lidades Simples, ou Não-capacitadas (UFLP, Uncapacitated Facility Location Problem).Bons levantamentos da literatura deste problema são relatados em Cornuéjols et al. (1983)e Krarup & Pruzan (1983).

O UFLP é provavelmente o mais simples na literatura dos FLPs que considera a na-tureza real e os desafios da localização de facilidades. À medida em que versões maiscomplexas foram sendo apresentadas foi surgindo a necessidade de organizar a área atra-vés de classificações dos modelos e revisões da literatura. A seguir mostraremos duas dasclassificações propostas e indicaremos ao leitor algumas das revisões mais recentes.

2.1.1 Classificações dos modelos de FLPDevido à vastidão de problemas apresentados na área, diversos pesquisadores busca-

ram formas de classificar os modelos de localização de facilidades. Uma delas é apresen-tada por Daskin (2008) e Revelle et al. (2008). Eles dividem os modelos de localizaçãode facilidades em quatro tipos de acordo com a topologia dos agentes de interesse. Sãoeles:

• Modelos analíticos - são os modelos de localização mais simples em que deman-das são distribuídas de forma contínua em uma área e facilidades são localizadasem qualquer lugar nesta área. Estes modelos são tipicamente resolvidos usandotécnicas de cálculo ou outras técnicas mais simples;• Modelos contínuos - diferenciam-se dos analíticos por assumirem que as demandas

existem apenas em pontos discretos. O Problema de Weber é um exemplo de um

2.1. A LOCALIZAÇÃO DE FACILIDADES NA TEORIA DE LOCALIZAÇÃO 9

modelo contínuo;• Modelos em rede - assumem que demandas existem e facilidades podem ser locali-

zadas apenas em uma rede composta por nós e arcos. Geralmente demandas estãonos nós enquanto facilidades podem ser localizadas tanto nos nós quanto nos vér-tices. O principal foco da literatura deste grupo é encontrar algoritmos com tempopolinomial capazes de resolver o problema em tipos específicos de redes (e.g., ár-vores);• Modelos discretos - diferenciam-se dos em rede por as facilidades poderem ser

localizadas apenas em um conjunto discreto de pontos na rede, chamados de nóscandidatos.

Uma outra forma interessante e mais abrangente de classificar os modelos de localiza-ção é apresentada por Klose & Drexl (2005). Eles classificam os modelos de localizaçãode facilidades em nove categorias. São elas: a topografia da rede, o objetivo do problema,a presença de restrições de alocação e de capacidade, a hierarquia dos fluxos, o númerode mercadorias, a elasticidade da demanda, o tamanho do horizonte de planejamento, asincertezas dos dados e o roteamento dos fluxos.

Outras classificações podem ainda ser encontradas nos diversos livros e revisões deliteratura já escritos sobre os FLPs como em Owen & Daskin (1998), Drezner & Ha-macher (2001), Revelle & Eiselt (2005), Daskin (2008), Melo et al. (2009), Farahani &Hekmatfar (2009), Smith et al. (2009), Arabani & Farahani (2012), Farahani et al. (2012)e Laporte et al. (2015).

A partir deste ponto do trabalho aprofundaremos nas classes de modelos mais relevan-tes em que o problema tratado nesta dissertação se enquadra, a dos modelos capacitados edinâmicos. Ao final desta seção serão mostradas algumas aplicações encontradas duranteo estudo que se utilizaram destes modelos para resolver problemas reais.

2.1.2 CFLP e a classe de modelos capacitados

Uma extensão natural do UFLP é introduzida adicionando restrições de capacidade deserviço às facilidades. No Problema de Localização de Facilidades Capacitadas (CFLP)valores exógenos, predeterminados, são considerados para o número máximo de merca-dorias que facilidades podem suportar. O CFLP é um problema que vem sendo estudadohá mais de 50 anos [Sá 1969, Davis & Ray 1969] e é um problema fortemente NP-difícil[Cornuéjols et al. 1991].

Dado um grafo (V ,A), sejam I ⊂ V o conjunto de nós representando os clientesa serem atendidos e J ⊂ V o conjunto de nós candidatos a receberem uma facilidade.Sejam os parâmetros ci j o custo de transportar uma unidade de produto para um clientelocalizado em i ∈ I a partir de uma facilidade em j ∈ J , di a demanda do cliente i e e j eu j, respectivamente, o custo de construir e a capacidade ao se instalar uma facilidade emj. Por fim, sejam xi j as variáveis de decisão de transporte e y j as variáveis de localização.A formulação clássica do CFLP pode ser representada, como em Sridharan (1995), por


(CFLP)

min ∑i∈I

∑j∈J

ci jxi j + ∑j∈J

e jy j (2.1)

sujeito a

∑j∈J

xi j = di, ∀i ∈ I (2.2)

∑i∈I

xi j ≤ u jy j, ∀ j ∈ J (2.3)

xi j ≥ 0, ∀i ∈ I , j ∈ J (2.4)y j ∈ B, ∀ j ∈ J . (2.5)

A função objetivo (2.1) busca minimizar o custo total da rede composto pelos custosde transporte de mercadorias e os custos de construção das facilidades. As restrições (2.2)garantem que todas as demandas sejam atendidas. As restrições (2.3) são as restrições decapacidade. Por fim, as restrições (2.4) e (2.5) definem o domínio das variáveis de decisão.

A literatura do CFLP é extremamente vasta e detalhar todas as suas variantes seriaconteúdo suficiente para um trabalho inteiro. Entre estudos publicados mais recentementeque lidam com este problema em sua versão mais clássica estão Klose & Görtz (2007) eRahmani & MirHassani (2014). Focaremos neste momento em uma das variantes em queos modelos permitem que as capacidades das facilidades sejam configuráveis.

Dimensionamento da capacidade e estrutura de custos

Na configuração da cadeia de suprimentos uma empresa pode optar por diferentespolíticas de localização e dimensionamento de facilidades. É melhor construir várioscentros de distribuição pequenos com atuação regional ou poucas instalações maiorescom atuação mais abrangente?

O tamanho da facilidade, expresso em unidades relacionadas a capacidade de pro-dução, de armazenamento ou de serviço, e o seu custo de instalação são grandezas di-retamente proporcionais mas não necessariamente linearmente proporcionais. De fato,quando o crescimento marginal do custo é menor que o da capacidade dizemos que houveuma economia de escala [Feldman et al. 1966, Correia & Captivo 2003]. Do contrário,ou seja, quando o custo unitário passa a aumentar com o incremento de mais capacidade,chamamos de deseconomia de escala [Harkness & ReVelle 2003, Lu et al. 2014].

Para representar estes conceitos em modelos, pesquisadores adicionaram o dimensi-onamento da capacidade como uma variável dos FLPs. O domínio do dimensionamentoda capacidade de uma facilidade pode ser definido num contínuo [Verter & Dincer 1995],quando qualquer quantidade de capacidade é válida, ou em pontos discretos [Shulman1991]. Este segundo caso levou à criação de uma subclasse de problemas capacitadoschamada de Problema de Localização de Facilidades com Capacidades Modulares (MC-FLP).

Nas telecomunicações um módulo pode ser um dispositivo qualquer instalado em


um nó EDGE [Addis et al. 2012], nos serviços de saúde pode ser uma estrutura físicacomposta por salas de consulta e de espera com enfermeiros, médicos, etc. [Correia &Captivo 2003], já na aviação um módulo pode ser uma aeronave que faz uma ponte aéreaentre dois aeroportos [Jaillet et al. 1996]. De maneira geral, podemos definir um módulocomo sendo uma parte de uma facilidade que possui como parâmetros uma capacidadeincremental e um custo de instalação.

O k-CFLP, conhecido problema da literatura de FLPs em que até k cópias da facili-dade original podem ser abertas no mesmo local [Arya et al. 2004], é um caso especial doMCFLP quando todos os módulos possuem custo e capacidade iguais. Além de dimen-sionamento da capacidade nos nós há também modelos capacitados nos arcos [Yaman &Carello 2005].

O modelo do CFLP apresentado anteriormente pode ser facilmente adaptado a umMCFLP genérico adicionando um segundo índice às variáveis de localização y jl e umterceiro às de alocação xi jl e, similarmente, aos parâmetros e jl e ci jl . Sendo que l ∈ L ={0, . . . ,L} define o módulo instalado e L representa o conjunto de módulos que podemser instalados em um local potencial. Feitas as devidas modificações basta adicionar aomodelo as restrições

∑l∈L

y jl = 1, ∀ j ∈ J , (2.6)

garantindo a escolha de um módulo em todas as facilidades, inclusive quando l =0. Outras formas de representar módulos nos modelos de localização de facilidades édiscutida em Jena et al. (2015a).

Assumindo u jl < u j(l+1), i.e., módulos maiores representam capacidades maiores,economias de escala são representadas quando

e jl− e j(l−1)

u jl−u j(l−1)>

e j(l+1)− e jl

u j(l+1)−u jl, (2.7)

ou seja, quando o custo unitário de produção decresce ao expandir a capacidade da facili-dade.

O MCFLP pode ser abordado em contextos estáticos [Agar & Salhi 1998, Correia &Captivo 2003, Gouveia & Saldanha-da Gama 2006] ou dinâmicos. Antes de apresentar osestudos já publicados neste segundo caso primeiro será feita uma revisão geral da classede modelos dinâmicos.

2.1.3 DFLP e a classe de modelos dinâmicosDecisões de localização tem um efeito duradouro para a empresa. Ao construir uma

facilidade, a companhia deve levar em consideração não só a configuração presente, mastambém previsões futuras. Mudanças nos custos de instalação e nas demandas acontecemao longo do tempo de forma que uma configuração ótima para a situação atual não sejanecessariamente a melhor num médio ou longo prazo. Na prática, um projeto de uma


rede logística começa com a identificação de potenciais locais para a instalação de umanova facilidade e a capacidade requerida. Então, uma grande quantidade de capital éinvestida nesta nova facilidade. Devido ao alto nível de investimento inicial é esperadoque a nova facilidade opere por um longo período de tempo até que as mudanças ocorridasnos parâmetros do sistema tornem esta localização custosa demais para ser mantida emrelação a uma nova instalação melhor localizada [Melo et al. 2009].

Problemas Dinâmicos de Localização de Facilidades (DFLP) são bastante utilizadosna configuração de cadeias de suprimentos devido a sua maior capacidade de simular arealidade. Ballou (1968) foi um dos primeiros trabalhos a levar em consideração o tempona análise de localização de armazéns numa rede em hierarquia. Wesolowsky (1973),Wesolowsky & Truscott (1975) e Sweeney & Tatham (1976) são outros estudos pioneiroscom DFLPs. Modelos dinâmicos também são conhecidos na literatura como multiperío-dos [Nickel & da Gama 2015]. Alguns autores [Arabani & Farahani 2012] usam o termodinâmico num sentido mais amplo, englobando também aspectos estocásticos. Todos osproblemas de localização estáticos podem ser transformados de algum modo em proble-mas dinâmicos [Arabani & Farahani 2012]. Os autores ainda classificam os modelos di-nâmicos em duas categorias. Os modelos dinâmicos explícitos permitem que facilidadessejam abertas, fechadas, realocadas, etc. em tempos e localizações específicos. Já os mo-delos dinâmicos implícitos supõem que facilidades sejam abertas no início do horizontede planejamento e permeneçam abertas durante todo o período.

Matematicamente, o aspecto temporal nos modelos é representado pela adição doíndice t às variáveis. Sejam T períodos de tempo e T = {0,1, . . . ,T} o conjunto dosperíodos em que decisões devem ser tomadas, custos fixos ga

jt e g fjt de abertura e fecha-

mento das facilidades são adicionados e custos de operação etj também são considerados.

A abertura de uma facilidade y no tempo t é representada quando ocorre a sequênciayt−1

j = 0 e ytj = 1. No caso inverso, yt−1

j = 1 e ytj = 0, a facilidade foi fechada. A configu-

ração inicial da rede é dada pelas variáveis y0j . Se y0

j = 0 ∀ j ∈ J , significa que nenhumafacilidade está aberta antes do horizonte de tempo considerado. Um modelo dinâmicogenérico, capacitado, baseado no apresentado em Klose & Drexl (2005), é dado por

(DFLP)

min ∑j∈J

T

∑t=1

(∑i∈I

cti jx

ti j + et

jytj +g f

jtyt−1j (1− yt

j)+gajt(1− yt−1

j )ytj

)(2.8)

sujeito a

∑j∈J

xti j = dt

i , ∀i ∈ I , t ∈ T (2.9)

∑i∈I

xti j ≤ u jyt

j, ∀ j ∈ J , t ∈ T (2.10)

xti j ≥ 0, ∀i ∈ I , j ∈ J , t ∈ T (2.11)

ytj ∈ B, ∀ j ∈ J, t ∈ T . (2.12)

A função objetivo (2.8) minimiza o custo total da rede. O primeiro termo está relacio-


nado aos custos de transporte, o segundo aos custos de operação das facilidades e os doisúltimos aos custos de fechamento e abertura. Vamos analisar as quatro possíveis decisõesque podem ser tomadas para cada facilidade em cada período com relação aos últimostrês termos da função objetivo.

• Facilidade fechada permanece fechada (yt−1j = 0 e yt

j = 0): todos os três termos sãodesativados, portanto nenhum custo incorrerá relacionado à facilidade;• Facilidade fechada é aberta (yt−1

j = 0 e ytj = 1): os primeiro e terceiro termos são

ativados, então ocorrerão apenas os custos de operação e abertura da facilidade;• Facilidade aberta permanece aberta (yt−1

j = 1 e ytj = 1): apenas o primeiro termo é

ativado, ou seja, apenas o custo de operação da facilidade será considerado;• Facilidade aberta é fechada (yt−1

j = 1 e ytj = 0): apenas o segundo termo é ativado,

o que significa que apenas o custo de fechamento será contabilizado.

As restrições são equivalentes às do CFLP, sendo (2.9) restrições de atendimento dedemandas, (2.10) restrições de capacidade, com (2.11) e (2.12) correspondendo ao domí-nio das variáveis.

Klose & Drexl (2005) apontam algumas das dificuldades ao considerar o uso de mo-delos dinâmicos. A primeira é que não existe um tamanho certo de horizonte de plane-jamento em aplicações reais, cabendo ao decisor escolher o tamanho que lhe for conve-niente. Outra é que a quantidade de dados requerida nestes modelos é enorme e certasvezes inestimáveis. Eles também mostram que modelos desagregados são mais sensíveisa ajustes de parâmetros que modelos dinâmicos. A complexidade destes modelos é bemmaior que a de modelos estáticos quanto mais integrados forem as decisões em função dotempo dificultando a resolução do problema com métodos exatos.

Realocações de facilidades e redimensionamento da capacidade

Devido à necessidade de grandes investimentos para construção de facilidades, há cer-tas situações em que ajustar capacidades das facilidades existentes seja mais favorável queconstruir novas facilidades do zero [Owen & Daskin 1998]. Melo et al. (2006) conside-ram realocações unitárias de capacidade entre facilidades abertas em seu modelo. Umaoutra abordagem para expansão de capacidade é utilizando módulos com capacidades ecustos predefinidos, assim como apresentado nos modelos capacitados estáticos.

Blocos de capacidade podem ser representados em modelos como sendo múltiplasfacilidades localizadas num mesmo local. A Figura 2.1 mostra duas representações extre-mas de módulos, sendo (a) a representação horizontal e (b) a vertical. Na representaçãohorizontal expansões são representadas empilhando módulos de forma que a capacidadetotal instalada numa facilidade é dada pela soma das capacidades dos módulos empilha-dos. Na representação vertical, os módulos não são empilhados. Assim, uma expansão deuma facilidade é representada pela retirada do módulo atual seguida do acréscimo de umnovo módulo com capacidade maior. Outras representações intermediárias também sãopossíveis.

Modelos com estas representações não permitem que os parâmetros dos blocos sejammodificados ao longo do horizonte de planejamento. Entretanto, eles permitem múlti-plas facilidades de diferentes tamanhos no mesmo local, o que é equivalente a ajustes de


Figura 2.1: Representação de módulos (a) horizontais e (b) verticais. Fonte: Adaptado deJena et al. (2015a)

capacidade total instalada ao longo do tempo [Jena et al. 2015a]. Troncoso & Garrido(2005) modelam um problema como no caso (a) e Jena et al. (2015a) como no (b). Diaset al. (2007) mostram uma modelagem em que variáveis binárias do tipo y jl1l2 indicam seuma facilidade j mudou sua capacidade de um módulo l1 para um módulo l2 em que l1 el2 ∈ L .

Jena et al. (2015a) aponta diferentes maneiras de ajustar capacidades dentro de umhorizonte de tempo planejado:

• Construção ou fechamento de uma facilidade num certo período de tempo;• Expansão ou redução de capacidade de uma facilidade existente;• Fechamento temporário de uma facilidade e reabertura em um período de tempo

futuro;• Realocação de capacidade de um local a outro.

Em situações reais, quando demandas perenes surgem em regiões distantes da áreade atuação da infraestrutura existente da empresa, a opção de construção de novas faci-lidades é desejável. Similarmente, quando demandas acabam a empresa deve optar pelofechamento das facilidades que as serviam. Expansões e reduções são desejáveis quandotendências de mudança das demandas são observadas na região atendida pela facilidade.O desafio nestes casos é determinar o momento certo de redimensionar a capacidade dafacilidade.

A opção de fechar temporariamente uma facilidade tem a vantagem de evitar os custosde operação durante um período. Pode ser vantajoso quando a facilidade lida com deman-das cíclicas ou sazonais, em que a utilização da facilidade é economicamente inviável de-vido aos custos de operação demasiadamente altos nas estações de baixa demanda. Outraalternativa para lidar com demandas cíclicas é a realocação de facilidades. Neste caso,além de baixas demandas temporárias, também é necessário que haja uma demanda não-atendida num outro local para onde a facilidade, ou parte dela, será realocada. Modeloscom realocações possuem custos específicos para estes ajustes associados ao transporteda estrutura de um local a outro e a economia de possuir previamente a estrutura.

A quantidade de mudanças de capacidade também é uma característica importantedos modelos dinâmicos. Estudos como Van Roy & Erlenkotter (1982) e Hinojosa et al.(2008) permitem que facilidades sejam abertas e fechadas apenas uma vez, enquanto queChardaire et al. (1996), Canel et al. (2001), dentre outros, não restringem a quantidade

2.2. APRESENTAÇÃO DO DFLPG 15

de mudanças. Apesar destes serem mais genéricos, eles aumentam a quantidade de va-riáveis no modelo exponencialmente, tornando-o muito mais complexo de ser resolvidootimamente em um período razoável de tempo.

2.1.4 Aplicações

A aplicação de modelos dinâmicos e/ou modulares é ampla. Num contexto do setorpúblico, Antunes & Peeters (2001) apresentam uma aplicação para localização de esco-las em que os módulos seriam uma ou um grupo de salas de aula. Já Brotcorne et al.(2003) tratam da localização de ambulâncias como um problema de cobertura em que arealocação das ambulâncias tem um papel fundamental quando ocorre incidentes e pontosestratégicos ficam temporariamente sem ambulâncias disponíveis.

O contexto mais comum da aplicação destes modelos no setor privado é no projetode redes de cadeias de suprimento. Ulstein et al. (2006) mostram um modelo aplicadonuma grande empresa de distribuição de silício e ferrosilício onde decisões sobre dimen-sionamento de capacidade das suas fábricas são tomadas em cenários estocásticos, sendopossível fechar, adquirir novas fábricas e aumentar o investimento em equipamentos deprodução. Van Ommeren et al. (2006) projetam a cadeia de suprimentos de lojas de reparode forma a minimizar os níveis de estoque de peças nas lojas através do gerenciamento daquantidade de servidores instalados no local.

A aplicação que inspirou o modelo deste trabalho, em Jena et al. (2015b), trata derealocação de capacidade num contexto de exploração de recursos florestais. Trailers quehospedam trabalhadores nos acampamentos onde os recursos coletados são depositadossão deslocados periodicamente de acordo com novos locais de exploração. O objetivo édeterminar a posição e a quantidade ótima de trailers nos pontos de exploração de modo aminimizar custos relacionados à construção e funcionamento dos acampamentos e deslo-camento dos recursos coletados. A seção a seguir apresentará a classificação na literaturae o modelo deste problema.

2.2 Apresentação do DFLPG

O complexo modelo apresentado por Jena et al. (2015b) em seu estudo de caso foisimplificado em Jena et al. (2015a) de modo a representar a estrutura de custo de mu-dança do nível de capacidade l1 para l2 em um nível mais detalhado usando uma matrizde custo de mudança de módulos. Este problema foi denominado então Problema de Lo-calização Dinâmica de Facilidades com Capacidades Modulares, ou DFLPG, pois retratauma generalização de vários problemas de localização encontrados na literatura.

2.2.1 Classificação

Com base no que foi apresentado, o DFLPG pode ser classificado na literatura deFLPs nas seguintes categorias:


• Discreto: Como na classificação em Daskin (2008) e Revelle et al. (2008), as facili-dades podem ser localizadas em um conjunto de pontos discretos predeterminados;• Objetivo MinSoma: O objetivo do problema é minimizar a somatória dos custos de

transporte de mercadorias e de localização das facilidades;• Capacidade modular: As facilidades são representadas por módulos, que são estru-

turas com um custo de instalação e uma capacidade atribuídos a cada uma, permi-tindo ao modelo considerar cenários com diversas estruturas de custo representandode forma mais realista problemas práticos;• Camada única: Decisões de localização são tomadas num único nível da rede e

esta camada representa os pontos de suprimento (facilidades) a partir de onde asmercadorias serão transportadas;• Alocação múltipla: Não há restrições de alocação, de forma que cada cliente pode

ser servido por qualquer facilidade, desde que abertas;• Dinâmico: O modelo permite a representação de variações nas demandas e nos

custos do problema ao longo de um período de tempo finito e também possibilitaque decisões de ajuste nas localizações sejam feitas em cada período do horizontede planejamento sem restrições na quantidade de ajustes feitos;• Determinístico: Os parâmetros de entrada do modelo são todos conhecidos previa-

mente.

2.2.2 ModeloO DFLPG foi formulado em Jena et al. (2015a) como um modelo de programação

inteira mista referido como Generalized Modular Capacities (GMC).

Parâmetros

Dado um grafo (V ,A), em que I ⊂ V é o conjunto de clientes e J ⊂ V é o conjuntode potenciais locais onde podem ser instaladas as facilidades. Os conjuntos I e J não sãonecessariamente iguais. Os arcos direcionados A representam as conexões entre nós faci-lidades a nós clientes. L é a quantidade máxima de módulos que podem ser instalados emj ∈ J e L = {0, . . . ,L} representa o conjunto destes módulos. T = {1, . . . ,T} representaos períodos de tempo no horizonte de planejamento de tamanho T em que as decisões delocalização serão tomadas.

Cada cliente em i ∈ I possui uma demanda a ser atendida dti no período t ∈ T dada

em unidades da mercadoria. cti jl são os custos unitário de alocação de uma unidade de

mercadoria no período t de uma facilidade em j operando com o módulo l instalado paraservir um cliente em i. A dependência do tamanho da facilidade neste parâmetro permiteuma representação de custos mais complexa. Os custos de alocação c podem englobarcustos de diferentes naturezas, como custos oriundos do transporte das mercadorias aosclientes e custos de produção das mercadorias nas facilidades. Os custos de produçãogeralmente estão associados à capacidade da facilidade. Quando os custos unitários deprodução decrescem com o aumento da capacidade das facilidades, dizemos que há umaeconomia de escala, ou seja, uma economia nos custos proporcionada pela produção emmaior escala. Economias de escala são representadas no modelo quando ct

i jl > cti j(l+1) ∀

2.2. APRESENTAÇÃO DO DFLPG 17

l ∈ L . Vale destacar que operar com um módulo em l é o mesmo que dizer que todos osmódulos até l estão instalados na facilidade de acordo com a representação horizontal demódulos mostrada na Figura 2.1 (a).

Uma facilidade em j operando com um módulo l tem capacidade u jl . Os parâmetroset

jl1l2representam o custo de uma facilidade em j que operava com o módulo l1 no período

t− 1 passar a operar com o módulo l2 no período t. l j representa o módulo instalado nafacilidade em j no início do horizonte de planejamento, portanto l1 = l j no período 1. Osparâmetros e podem ainda representar estruturas de custo mais detalhadas. Em Jena et al.(2015a) custos de operação e fechamento e abertura de módulos são imbutidos nestes pa-râmetros no modelo ER-GMC. Quando custos de fechamento temporário e reabertura defacilidades são também considerados o modelo é chamado de CR-GMC. A representaçãode realocações só é possível nesta estrutura matricial dos custos quando houver realoca-ções completas de facilidades. Das quatro maneiras de ajustar capacidades num problemadinâmico apresentadas na seção 2.1.3, apenas as realocações parciais exigiria uma refor-mulação no modelo de forma que ele fosse capaz de rastrear os módulos existentes narede.

De acordo com os parâmetros descritos, quando uma facilidade estiver equipada com omódulo zero, ou seja, quando estiver fechada, os custos de transporte ct

i j0 e as capacidadesu j0 necessariamente serão iguais a zero.

Variáveis de decisão

Dois tipos de decisões devem ser tomadas pelo modelo: decisões de localização e dealocação. As decisões de localização são representadas pelas variáveis de decisão bináriasy. yt

jl1l2é igual a 1 se a facilidade em j muda seu módulo de l1 para l2 e opera em l2 durante

o período t, e 0 caso contrário. É importante ressaltar que mesmo quando l1 = l2, ytjl1l2

pode ser igual a 1. Se isto acontecer, o módulo em j não foi alterado entre os períodost − 1 e t, e o único custo incorrido será, se houver, o custo de operação de j com estemódulo neste período.

Já as alocações são representadas pelas variáveis xti jl , em que x representa a fração da

demanda do cliente i no período t servida pela facilidade j equipada com o módulo l.

Modelagem matemática

Definidos os parâmetros e as variáveis, o problema foi modeladopor Jena et al. (2015a)como

(GMC)

min ∑i∈I

∑j∈J

∑l∈L

∑t∈T

cti jld

ti x

ti jl + ∑

j∈J∑

l1∈L∑

l2∈L∑

t∈Tet

jl1l2ytjl1l2 (2.13)


sujeito a

∑j∈J

∑l∈L

xti jl = 1, ∀i ∈ I , t ∈ T (2.14)

∑i∈I

dti x

ti jl ≤ ∑

l1∈Lu jlyt

jl1l, ∀ j ∈ J , l ∈ L , t ∈ T (2.15)

∑l1∈L

yt−1jl1l = ∑

l2∈Lyt

jll2, ∀ j ∈ J , l ∈ L , t ∈ T \{1} (2.16)

∑l2∈L

y1jl jl2

= 1, ∀ j ∈ J (2.17)

xti jl ≥ 0, ∀i ∈ I , j ∈ J , l ∈ L , t ∈ T (2.18)

ytjl1l2 ∈ B, ∀ j ∈ J , l1 ∈ L , l2 ∈ L , t ∈ T (2.19)

A função objetivo (2.13) minimiza o custo total da rede composto pelos custos detransporte e de mudança de módulos. Restrições (2.14) garantem o atendimento das de-mandas dos clientes. Restrições (2.15) são de capacidade das facilidades em cada períodode tempo. Restrições (2.16) ligam as variáveis de mudança de módulos em períodos detempo consecutivos, garantindo que em cada período de tempo seja tomada alguma deci-são sobre o próximo estado da facilidade. Restrições (2.17) garantem que algum móduloseja escolhido no início do horizonte de planejamento, mesmo que seja o próprio mó-dulo l j. Restrições (2.18) definem o domínio das variáveis de transporte e (2.19) o dasvariáveis de mudança de módulos.

Uma observação sobre as restrições (2.16) é que para cada facilidade j e tempo t, ytjl1l2

é representada por uma matriz de dimensões (L+1)×(L+1), sendo L o número máximode módulos que é somado ao módulo zero. Nesta matriz apenas um dos elementos seráigual a um, sendo este o da linha do módulo aberto em t− 1 e coluna do módulo atual.Todos os outros elementos da matriz deverão ser necessariamente iguais a zero. Destaforma, graças às restrições (2.17), cada lado da equação sempre terá soma igual a um.

Dois conjuntos de desigualdades válidas tradicionais na literatura dos FLPs foramadicionadas por Jena et al. (2015a) ao modelo a priori para facilitar a solução do GMC.As inequeções fortes

xti jl ≤ ∑

l1∈Lyt

jl1l, ∀ j ∈ J , l ∈ L , t ∈ T (2.20)

apertam os limitantes superiores das variáveis de alocação de demanda. Já as restriçõesde demanda agregada

∑j∈J

∑l1∈L

∑l2∈L

u jl2ytjl1l2 ≥∑

i∈Idt

i , ∀t ∈ T (2.21)

permitem que resolvedores de MIP gerem cortes para fortalecer a formulação [Jena et al.2015a]. O termo "corte"na otimização refere-se ao refinamento do conjunto de soluções

2.3. MÉTODOS DE SOLUÇÃO DOS FLPS 19

viáveis através do uso de desigualdades lineares. Em problemas capacitados, cortes asso-ciados aos parâmetros das capacidades são chamados de cortes de cobertura (cover cuts).

Por ser uma generalização de diversos modelos de FLP, o GMC pode ser adaptadoa outros problemas menos complexos da literatura como os de Van Roy & Erlenkotter(1982), Shulman (1991), Sridharan (1995), Chardaire et al. (1996) e Correia & Captivo(2003).

2.3 Métodos de solução dos FLPs

Até então este capítulo focou em como algumas características dos problemas de lo-calização de facilidades podem ser representadas na Pesquisa Operacional até chegar noproblema que foi escolhido na literatura a ser abordado. Nesta parte do trabalho serãomostrados diferentes métodos bem sucedidos de como resolver FLPs.

De maneira geral, métodos de solução de problemas de otimização podem ser dividi-dos em duas classes, a dos métodos exatos e das heurísticas. Métodos exatos são usadospara encontrar a solução ótima do problema, i.e. o ponto extremo (mínimo ou máximo) dafunção objetivo do modelo que seja viável em relação a todas as restrições. Na otimiza-ção combinatória existem problemas que resolvê-los até a otimalidade é inviável, seja porquestões de tempo disponível ou de memória da máquina. Mesmo nestes casos, métodosexatos são capazes de prover limitantes do valor da solução ótima. Com isto, é possívelter uma ideia aproximada do valor extremo da função.

Uma das práticas mais comuns para resolver um FLP é modelar matematicamenteo problema como um MIP, e, então, recorrer a softwares de otimização genéricos pararesolvê-los. Um resolvedor comercial vastamente utilizado na literatura é o IBM CPLEX,como utilizado em Jena et al. (2015a) para resolver o DFLPG. Resolvedores comerciaiscomo o CPLEX usam métodos exatos bem elaborados para resolver os mais variadostipos de problemas de otimização.

Métodos exatos são excelentes ferramentas para resolver modelos de menor escala.Porém, a necessidade de resolver problemas reais cada vez maiores e mais complexosfaz com que nem sempre seja possível resolvê-los com esta abordagem. Nestes casos,decisores e pesquisadores recorrem aos métodos heurísticos. O objetivo das heurísticas éencontrar rapidamente soluções de qualidade, sendo especialmente atrativas na resoluçãode problemas complexos. Por serem rápidas, as heurísticas também são muito utilizadaspara simular cenários quando os dados são incertos ou imprecisos no problema.

No âmbito das pesquisas dos FLPs, houve grandes avanços tanto no sentido de melho-rar o desempenho dos resolvedores tradicionais quando usados nesta classe de problemas,quanto no desenvolvimento de métodos heurísticos para cada configuração específica doproblema. As próximas subseções serão dedicadas a apresentar algumas classes de méto-dos heurísticos comumente utilizados para resolver problemas de localização na literatura.O leitor interessado em conhecer mais sobre os métodos exatos pode encontrar referênciasem Arabani & Farahani (2012) e Melo et al. (2009).


2.3.1 Métodos heurísticosUm método heurístico deve ser capaz de prover limitantes viáveis ao problema em

um tempo razoável. Alguns métodos exploram a estrutura do modelo matemático paraobter limitantes da solução ótima, transformando o problema original em subproblemasmenores. Na Decomposição de Benders [Wentges 1996], os limitantes são encontradosresolvendo duais e relaxações do problema, técnicas bastante utilizadas na PO. Tambémé possível encontrar limitantes usando Relaxações Lagrangeanas. Jena et al. (2014) utili-zam este método para resolver uma variante do DFLPG onde múltiplas mercadorias sãoconsideradas. Alguns estudos [Lee & Dong 2008] combinam os dois métodos para criaruma decomposição cruzada.

Uma outra abordagem heurística comum em FLPs é o uso de algoritmos aproxima-tivos. Neles, o objetivo é encontrar métodos capazes de prover soluções que, no piorcaso, estejam à menor distância possível da solução ótima. A aproximação da otimali-dade é medida através de um fator constante. Um algoritmo é dito ser de aproximação-ρse no pior caso é provado que o custo da solução aproximativa f (x) está no intervalof (x∗)≤ f (x)≤ ρ f (x∗), sendo f (x∗) o custo da solução ótima.

Shmoys et al. (1997) desenvolvem um algoritmo aproximativo para o UFLP baseadona relaxação linear das variáveis binárias y do problema original. Como problemas deprogramação linear são muito mais rápidos de serem resolvidos que MIPs, estas rela-xações provêem resultados ótimos rápidamente. Entretanto, estes resultados podem serinviáveis no problema original, servindo apenas como limitantes inferiores (em proble-mas de minimização) para o custo ótimo do problema. Para transformar a solução doproblema relaxado em uma solução viável, o método arredonda iterativamente as variá-veis de localização fracionadas aumentando o custo por um fator constante relativamentepequeno a cada iteração.

É importante observar que, no UFLP, se o conjunto de facilidades abertas é conhecido,para encontrar o conjunto ótimo das alocações basta atribuir cada cliente à facilidadeaberta mais próxima, resolvendo o problema em tempo linear em relação à quantidade declientes. No CFLP esta abordagem não é possível. Entretanto, se o problema permitiralocações múltiplas de facilidades a clientes, a parte das alocações é uma instância doproblema de Fluxo a Custo Mínimo (FCM).

O objetivo do FCM é encontrar a maneira mais barata de se transportar o fluxo demercadorias através de uma rede de fluxo. A rede é definida como um grafo direcionadocomposto pelos nós representando as facilidades abertas e os clientes com demandas. Osarcos direcionados conectam as facilidades aos clientes. Cada arco possui como atributosas quantidades mínima e máxima de mercadorias que podem ser transportadas entre osnós ao qual eles estão ligados, e o custo de transporte unitário. Uma vez montado o grafo,o problema é resolvido utilizando algoritmos combinatórios. Dentre alguns dos algorit-mos utilizados para resolver o FCM estão o Ciclo de Cancelamento, o Custo de Escala ea Rede Simplex. A estrutura destes e de outros algoritmos de FCM são encontrados emAhuja et al. (1993). Uma observação importante sobre os algoritmos de FCM é que elessão polinomiais, ou seja, encontram a solução ótima do problema em tempo polinomialem relação ao tamanho da rede.

Voltando às decisões de localização, o método de relaxação-arredondamento de Sh-


moys et al. (1997) também pode ser aplicado ao CFLP. Eles mostram que se a facili-dade parcialmente aberta for escolhida aleatoriamente a cada iteração, a heurística de-senvolvida leva a um algoritmo aproximativo com fator 3,16 no UFLP e 5,69 no CFLPcom múltiplas alocações. An et al. (2017) mostram o atual melhor método baseado emrelaxação-arredondamento e nas teorias de fluxos de múltiplas mercadorias para o CFLP.

Para o UFLP, Guha & Khuller (1999) apresentam uma heurística gulosa que ao seraplicada com o método de Shmoys et al. (1997) leva a uma solução de custo no máximo2,41 vezes o ótimo. A heurística consiste em adicionar facilidades não utilizadas a soluçãooriginal quando sua adição diminuir os custos de alocação em um valor maior que oseu custo de construção. Eles também provam que é impossível existir um algoritmoaproximativo em tempo polinomial com fator menor que 1,463, exceto se P = NP. Atéonde sabemos, o melhor fator aproximativo encontrado para o UFLP é de 1,5 [Byrka &Aardal 2010]. Mais informações sobre algoritmos aproximativos e problemas abertos naárea podem ser encontradas no livro de Williamson & Shmoys (2011).

Uma outra classe de heurísticas em destaque para resolver FLPs é a das heurísticas debusca local utilizadas para realizar buscas em vizinhança, como apresentadas a seguir.

2.3.2 Busca em vizinhança

Uma busca local consiste em encontrar soluções aprimorantes contidas na vizinhançade uma solução existente. Antes de apresentar heurísticas de busca em vizinhança efetivasque resolveram FLPs na literatura serão apresentadas algumas definições relacionadas àsbuscas locais.

Seja um problema de otimização combinatória com uma instância S e o conjunto desoluções viáveis X para esta instância, X (S) é a representação da conexão entre a instânciae o conjunto de soluções e f : X →R é a função que obtém o custo da solução. Assumindoque X é um conjunto finito, mas extremamente grande, num problema de otimização deminimização o objetivo é encontrar uma solução x∗ de modo que f (x∗)≤ f (x), ∀x ∈ X .

Uma vizinhança de uma solução x ∈ X é representada por N(x)⊂ X , em que N é umafunção que mapeia uma solução a um conjunto de soluções. Uma solução x é dita serum ótimo local em uma vizinhança N se f (x) ≤ f (x′) ∀ x′ ∈ N(x). Uma heurística debusca em vizinhança parte de uma solução inicial x e calcula x′ = argminx′′∈N(x){ f (x′′)},isto é, encontra a solução mais barata x′ na vizinhança de x. Se f (x′) < f (x) então oalgoritmo atualiza x = x′. A vizinhança da nova solução x é varrida em busca de umanova solução aprimorante repetidamente até não ser mais possível encontrar uma soluçãomelhor na vizinhança. A solução x final encontrada é o ótimo local. O algoritmo des-crito utiliza a estratégia de melhor aprimorante (best descent) pois a cada iteração toma adireção da melhor solução existente, ou seja, o ótimo local, na vizinhança varrida. Umaoutra abordagem nas buscas locais seria mover a solução para a primeira solução aprimo-rante encontrada na varredura da vizinhança. Este método é conhecido como método doprimeiro aprimorante (first descent) e possui como vantagem sobre o melhor aprimorantemovimentar mais rapidamente uma solução para outra melhor na busca.

No contexto dos FLPs, algumas heurísticas de busca local foram desenvolvidas e tes-tadas nos problemas clássicos e posteriormente adaptadas às variantes. As mais estudadas


foram as que definiram as vizinhanças de uma solução das seguintes formas:

• Abrir facilidades;• Fechar facilidades;• Substituir facilidades abertas por facilidades fechadas.

As primeiras heurísticas de busca local com estas vizinhanças desenvolvidas para umFLP datam de mais de 50 anos atrás [Kuehn & Hamburger 1963]. Recentemente Koru-polu et al. (2000) adaptaram estas heurísticas para uma série de variações do problemadas p-medianas, UFLP e CFLP. Apesar destas técnicas obterem fatores aproximativos ra-zoáveis, a ordem de complexidade da execução destes métodos era demasiadamente alto,mesmo sendo polinomial. Outros estudos [Chudak & Williamson 1999, Arya et al. 2004]apresentaram melhorias ao método e as análises de Korupolu et al. (2000), obtendo fa-tores aproximativos melhores que os originais. Charikar & Guha (1999) combinam asbuscas locais com algoritmos primal-dual para desenvolver um método de O(n3), melhorque o de Korupolu et al. (2000) de O(n6 log n/ε), sendo ε > 0 uma constante qualquer,para o UFLP.

Estes estudos tratam apenas de substituição de no máximo uma facilidade fechada poruma aberta. Mahdian & Pál (2003) e Zhang et al. (2005) são alguns dos trabalhos que con-sideraram a substituição de mais de uma facilidade simultaneamente obtendo resultadoscom boa aproximação, porém com alta ordem de complexidade.

Expandir demasiadamente a vizinhança de uma busca levará a resultados melhores,porém a um custo computacional que pode tornar impraticável o seu uso. Mesmo umatroca simples entre m facilidades, requereria um algoritmo de, no mínimo, O(nm) tornandoo método custoso demais para resolver instâncias suficientemente grandes de problemasmais complexos, como os problemas dinâmicos. Para lidar com instâncias assim é maisprudente aplicar diversas buscas locais em vizinhanças menores sequencialmente. Feliz-mente, ótimos locais em uma vizinhança não necessariamente são ótimos locais em outra[Hansen & Mladenovic 2001], de modo que o uso de várias heurísticas de busca local,mesmo que com vizinhanças simples, podem levar a soluções de alta qualidade.

A Descida em Vizinhança Variável (VND) é um procedimento de exploração de váriasvizinhanças diferentes através do uso de diferentes algoritmos de busca local. A suaestrutura básica é mostrada no Algoritmo 1.

A ordem das vizinhanças são definidas previamente, o que significa que o VND é umprocesso de busca local determinístico. As linhas 5-7 mostram a descida da solução dentrode uma mesma vizinhança conhecida como busca em exaustão. O método de descidautilizado pode ser tanto o do melhor aprimorante quanto o do primeiro aprimorante. Sehouve pelo menos uma mudança de solução na vizinhança após a exploração exaustiva, oVND retorna a busca na primeira vizinhança desta nova solução (linha 9). Caso contrário,segue para a vizinhança seguinte (linha 11). A abordagem apresentada foi a escolhida paraser utilizada neste trabalho. Entretanto, esta não é a única e nem necessariamente a maiseficiente para outras variantes do FLP.

Métodos heurísticos tem se mostrado poderosos pela eficiência e simplicidade de im-plementação. Porém, a maioria das heurísticas mais clássicas são determinísticas, sendoincapazes de gerar diferentes soluções ou diferentes ótimos locais. O desenvolvimento da


Algoritmo 1 Estrutura básica do VND1: Solução inicial: x;2: Conjunto de vizinhanças Nn(x), n = {1, . . . ,N};3: for n = 1 to N do4: xi← x;5: while Houver um x′ ∈Nn(x)| f (x′)< f (x) do6: x← x′

7: end while8: if f (x′)< f (xi) then9: n = 1;

10: else11: n = n+1;12: end if13: end for

pesquisa de heurísticas levou a criação de algoritmos mais sofisticados. Uma classe po-pular é a das metaheurísticas. A seguir, serão apresentadas algumas das metaheurísticasmais utilizadas na literatura dos FLPs.

2.3.3 MetaheurísticasO prefixo meta tem aqui um significado de "além"ou "alto nível". Isto porque ge-

ralmente metaheurísticas tem desempenho melhor que heurísticas simples [Yang 2010].As metaheurísticas são procedimentos que utilizam heurísticas iterativamente através dautilização de algum mecanismo estocástico. O procedimento alterna entre fases de diver-sificação e de intensificação da busca. A diversificação permite ao algoritmo buscar novassoluções em vizinhanças não-alcançáveis a partir de soluções criadas pelas heurísticas deintensificação, como as buscas locais, dando maior robustez a qualidade do método emescala global. O objetivo é balancear diversificação com intensificação de modo que ametaheurística seja capaz de fugir de soluções ótimas locais sem perder a característicade rapidez na busca das heurísticas mais simples.

Diversas estruturas para metaheurísticas já foram propostas. Gendreau & Potvin(2005) classificam as metaheurísticas de acordo com a quantidade de soluções trabalha-das por vez. As metaheurísticas de solução única, como Simulated Annealing, BuscaTabu e VNS, são aquelas que partem de uma única solução e tem uma única trajetóriade busca. Já as baseadas em uma população, como os Algoritmos Evolucionários (den-tre os quais estão os Algoritmos Genéticos), possuem múltiplas soluções que evoluemconcorrentemente. Osman & Laporte (1996), Blum & Roli (2003) e Gendreau & Potvin(2005) apresentam boas revisões da literatura das metaheurísticas usadas em otimizaçãocombinatória.

Na área dos FLPs, Arostegui et al. (2006) fazem um levantamento das três metaheu-rísticas mais aplicadas a estes problemas: Busca Tabu, Simulated Annealing e AlgoritmoGenético. Uma comparação empírica é mostrada onde as heurísticas foram aplicadas a al-gumas variantes, como os modelos capacitados, dinâmicos e com múltiplas mercadorias.


Um levantamento semelhante foi feito em Basu et al. (2015) incluindo ainda as metaheu-rísticas de Busca Dispersa e de Enxame de Partículas. GRASP [Delmaire et al. 1999] eVNS [Wollenweber 2008] também são encontrados na literatura. A vastidão de métodospublicados é um indício de que o desempenho do algoritmo é situacional, portanto a es-colha do mais adequado depende das características do problema [Arostegui et al. 2006].

Quando um só procedimento não é suficiente para gerar soluções satisfatórias paraproblemas específicos, podemos recorrer a hibridização de métodos de diferentes áreasda otimização, criando uma estrutura mais complexa que possa se beneficiar das van-tagens dos métodos empregados. As metaheurísticas híbridas combinam metaheurísti-cas clássicas com relaxações do problema original, programação dinâmica ou até outras(meta)heurísticas. Talbi (2002) apresenta uma taxonomia para as metaheurísticas híbri-das baseada nos métodos hibridizados e Blum et al. (2011) mostram diversas categoriasde métodos que podem ser hibridizados com metaheurísticas.

Vários métodos híbridos já foram aplicados a FLPs. Wollenweber (2008) mostra umametaheurística híbrida que parte de uma solução construída a partir da relaxação lineardo problema seguida da fase de diversificação num algoritmo VNS e intensificação numVND com buscas locais de abertura, fechamento e substituição de facilidades. Fernandeset al. (2014) utilizam uma estrutura semelhante mas com um AG sendo utilizado comodiversificação. Ambos foram aplicados em problemas no contexto de projeto de cadeiasde suprimento (múltiplos niveis de facilidades). Os resultados computacionais mostraramque tais estruturas são capazes de melhorar os limitantes encontrados pelo resolvedor domodelo MIP em instâncias de grande porte gastando menos tempo de solução.

2.4 Discussão da literaturaEste capítulo mostrou uma parte da vasta literatura existente sobre os problemas de

localização de facilidades no âmbito da Pesquisa Operacional. Como pode ser lido, aquantidade de características trazidas de aplicações reais ao problema gerou um númerode variantes imenso de modelos. Tão grande quanto é a quantidade de ferramentas dispo-níveis para resolvê-los. Se por um lado é um desafio encontrar o método de solução idealpara cada característica incorporada ao problema, por outro isto traz diversas oportunida-des de trabalhos futuros a serem realizados sobre o tema.

Modelos que tratam de dimensionamento das capacidades das facilidades num ho-rizonte de planejamento ainda são incomuns. Na série de estudos de Jena, Cordeau eGendron [Jena et al. 2014, Jena et al. 2015b, Jena et al. 2015a, Jena et al. 2016], eles bus-caram juntar o que já fora trabalhado separadamente sobre estes problemas e unificaramnum novo modelo até então inexplorado. O modelo resultante, apresentado em Jena et al.(2015a) como DFLPG, é resolvido apenas usando um método exato. Porém, as pesquisasmostram repetidamente que o desenvolvimento de métodos especializados para proble-mas específicos pode ser mais eficaz que resolvê-los com métodos generalistas. Destaforma, resolvemos experimentar uma abordagem heurística para resolver o DFLPG apre-sentado usando um Algoritmo Genético como metaheurística e um VND iterado comvizinhanças adaptadas ao problema dentre as mostradas neste capítulo. O AG+VNDi serádescrito no próximo capítulo deste trabalho.

Capítulo 3

Descrição do algoritmo

No capítulo 2 foi apresentado o problema de localização de facilidades que será abor-dado neste trabalho. O DFLPG possibilita a representação de estruturas de custo maiscomplexas e consiste em localizar facilidades, dimensionar suas capacidades e alocaras facilidades aos clientes num contexto dinâmico visando minimizar os custos da rede.Apesar destas características não serem novas na literatura dos FLPs, o problema que en-globa todas simultâneamente é relativamente novo. Entretanto, o DFLPG mantém muitascaracterísticas de seus subproblemas de modo que seja razoável inferir que métodos deresolução eficazes destes subproblemas também possam ser para o DFLPG.

Como o DFLPG é uma generalização de outros problemas combinatórios difíceis deserem resolvidos, uma abordagem exata pode não ser a mais adequada em situações comoquando a instância for grande demais. Por mais eficientes que sejam a técnica e o resol-vedor utilizados para resolver o problema, o tempo computacional requerido seria dema-siadamente alto, o que muitas vezes decisores não tem a sua disposição. Uma alternativaa estes casos é resolver o problema utilizando heurísticas que sejam capazes de encontrarboas soluções através de métodos computacionalmente menos complexos.

A escolha do método heurístico mais adequado deve levar em conta as característicasdo problema. Para um problema generalizado como o DFLPG, a exploração de diferentesespaços de busca possibilita uma flexibilidade maior para resolver as diversas aplicaçõesque possam ser tratadas com este modelo. Para reforçar ainda mais o poder destas buscaspodemos recorrer a metaheurísticas que possibilitem a exploração de soluções em dife-rentes espaços, diminuindo as chances de que o método fique preso em soluções ótimaslocais.

A metaheurística Algoritmo Genético é uma das mais aplicadas em problemas delocalização e possui um histórico de sucesso em muitas de suas variantes. Mostraremos aseguir a estrutura básica deste método e, em seguida, uma adaptação híbrida com o VND(AG+VNDi) para resolver o DFLPG.

3.1 Visão geral sobre o Algoritmo GenéticoO conceito de Algoritmo Genético foi introduzido por Holland (1975) e posterior-

mente descrito por Goldberg & Holland (1988). AGs são técnicas de busca estocásticasbaseadas no mecanismo de seleção natural e evolução. Nelas, indivíduos representando

26 CAPÍTULO 3. DESCRIÇÃO DO ALGORITMO

soluções do problema formam uma população. A aptidão de cada indivíduo é avaliada deacordo com a qualidade da solução, geralmente medida pelo valor da sua função objetivo.Os indivíduos evoluem através de iterações sucessivas chamadas de gerações. Em cadageração os indivíduos na população geram descendentes. Um descendente (filho) é umnovo indivíduo formado a partir do cruzamento entre dois indivíduos (pais) selecionadospor um operador de seleção na população. Um filho deve conter características, ou genes,herdadas dos pais. Além disto, um filho pode ter seus genes modificados através de umoperador de mutação. Uma nova geração é formada selecionando através de um operadorde aceitação indivíduos entre os da geração atual e os formados pelo operador de cruza-mento. Geralmente, indivíduos mais adaptados possuem maior probabilidade de seremselecionados. Após sucessivas gerações, as soluções convergem para resultados melhores.O algoritmo termina quando algum critério de parada é atendido, como uma quantidademáxima de gerações ou de tempo de busca. O Algoritmo 2 mostra o passo-a-passo de umAG básico.

Algoritmo 2 Estrutura básica do AG1: P0 - Indivíduos gerados através de uma heurística construtiva;2: Avaliação - Calcula a aptidão dos indivíduos em P0;3: while Critério de parada não for atendido do4: Seleção - Seleciona pais na população;5: Cruzamento - Gera filhos a partir dos pais selecionados em Pg;6: if Critério para mutação for aceito then7: Mutação - Modifica filhos gerados;8: end if9: Avaliação - Calcula a aptidão dos filhos gerados;

10: Aceitação - Seleciona indivíduos que irão compor a geração seguinte Pg+1;11: g = g+1;12: end while13: return Melhor indivíduo encontrado.

O AG foi utilizado como base para desenvolver o AG+VNDi usado na resolução doDFLPG. A seguir serão descritas as estruturas que compõem o algoritmo.

3.2 Estruturas do AG+VNDi

Como o DFLPG apresentado permite alocações múltiplas resolver as alocações oti-mamente é computacionalmente simples desde que as localizações e capacidades das fa-cilidades sejam conhecidas, assim como no CFLP. Desta forma, a função do AG+VNDi édeterminar as localizações e capacidades das facilidades para a partir disto a solução seravaliada pelo algoritmo de fluxo a custo mínimo.

3.2. ESTRUTURAS DO AG+VNDI 27

3.2.1 Estrutura do indivíduo

Uma solução x formada pelo algoritmo pode ser representada por uma matriz J×T ,em que J é a quantidade de elementos em J e T o tamanho do horizonte de planejamento.Cada posição da matriz indica o módulo aberto na facilidade j ∈ J no período t ∈ T .Cada célula desta matriz é um gene da solução. Um gene é representado por G jt = l, emque l corresponde ao módulo aberto na posição j x t como na matriz:

x =

G11 G12 . . . G1TG21 G22 . . . G2T

...... . . . ...

GJ1 GJ2 . . . GJT

Devido à natureza do problema, é comum que numa solução um módulo permaneça

aberto numa mesma facilidade durante longos períodos de tempo. Um módulo presentena sequência de genes {G jti, . . . ,G jt f }, onde ti e t f são, respectivamente, os períodos emque o módulo foi aberto e fechado, será representado por um segmento de genes. Umsegmento de genes é equivalente a um módulo horizontal como mostrado na Figura 2.1(a).Dizemos que uma facilidade j possui um segmento de genes S j

tit f ativo se um módulopermanece aberto durante o intervalo do período ti ao t f . A representação da solução emuma matriz em vez de num vetor, como em Ko & Evans (2007), é mais prática do pontode vista das operações do algoritmo e visualização de segmentos.

O conjunto de todos os segmentos de genes ativos de uma solução forma um indiví-duo. Na Figura 3.1 temos um exemplo de um indivíduo com cinco segmentos de genesativos. São eles S2

13, S334, S4

15, S415 e S4

34. Como segmentos representam um único módulo,nota-se que a facilidade 4 é constituída de dois segmentos semelhantes representando osmódulos 1 e 2, e um terceiro segmento para o módulo 3.

Figura 3.1: Representação do indivíduo

Definiremos ainda como um indivíduo viável um indivíduo que represente uma solu-ção viável do DFLPG. Uma solução é dita viável quando não há violação de restrição doproblema original. No algoritmo desenvolvido a viabilidade de uma solução é garantidaquando

∑j∈J

u jG jt ≥∑i∈I

dit , ∀t ∈ T . (3.1)


Em outras palavras, uma solução é viável quando há capacidade disponível suficiente paraatender a todas as demandas em cada período. Isto é verdadeiro pois é suficiente garantira viabilidade da solução na fase de localização das facilidades para que a execução doFCM obtenha um resultado viável na fase de alocação das demandas.

3.2.2 Avaliação do indivíduo

A avaliação da aptidão de um indivíduo é feita como mostrado no início da seção3.2. Uma vez determinadas as localizações basta a execução de um algoritmo de FCMpara encontrar o conjunto ótimo de alocações. O valor de f (•) representa a aptidão doindivíduo através do valor da sua função objetivo. Um indivíduo x1 é mais apto que outrox2 se f (x1)< f (x2).

O cálculo dos custos de localização é feito de forma direta quando um indivíduo écriado utilizando apenas os valores dos seus genes e os custos de decisão de localizaçãorepresentados pelo parâmetro e. Já o custo total de alocação é obtido pela somatória doscustos de alocação em cada um dos T períodos de tempo. Como as alocações de umperíodo independem das alocações em outro é necessário executar T vezes o FCM paraisto.

O cálculo do FCM em cada período de tempo é feito a partir de um grafo direcionadomontado como na Figura 3.2. Os nós nível 1 e 4 representam a origem e o destino dosfluxos, em que o 1 possui um suprimento inicial negativo igual a soma de todas as deman-das do período e o 4 um positivo de valor igual. Os nós brancos no nível 2 representam asfacilidades abertas e no nível 3 os clientes com demandas. Facilidades fechadas e clientessem demandas no período (nós pretos) não são incluídos no grafo.

Figura 3.2: Exemplo de grafo gerado para o FCM


Os arcos são construídos levando em consideração apenas facilidades abertas e cli-entes com demandas, o que reduz consideravelmente o tamanho da rede e, consequen-temente, acelera a execução do FCM. A cada arco são associados cinco atributos: nóorigem, nó destino, fluxo mínimo, máximo (capacidade) e custo de transportar uma uni-dade de mercadoria. A Tabela 3.1 mostra os valores dos atributos dos arcos sendo O o nóorigem e D o nó destino.

Tabela 3.1: Atributos dos arcos no grafo do FCM

Arco Origem DestinoFluxo Fluxo

CustoMínimo Máximo

Nível 1 O j 0 utjl 0

Nível 2 j i 0 min{utjl,d

ti} ct

i jlNível 3 i D dt

i dti 0

A cada execução do FCM seu resultado é armazenado numa tabela hash, uma estruturade dados capaz de associar chaves a valores. Na tabela criada, THASH , a chave indica aconfiguração das facilidades no período de tempo executado, i.e. quantos módulos estãoabertos em cada facilidade. Já o valor é o custo das alocações. Desta forma, quandouma configuração de localizações se repetir para um mesmo período, o algoritmo poderecuperar o estado ótimo das alocações sem precisar resolver novamente o problema. Emtermos computacionais a busca por um elemento numa tabela hash é mais eficiente que aresolução do FCM, sendo de complexidade O(log n), onde n é a quantidade de elementosarmazenados na tabela, enquanto que os algoritmos de FCM mais eficientes são O(nm logn(m+n log n)), em que n é a quantidade de nós e m a de arcos na rede.

3.2.3 População inicialA população em cada geração do AG tem tamanho fixo de P indivíduos. Os primeiros

P indivíduos criados compõem a população inicial do problema e são construídos pormétodos heurísticos. Uma heurística construtiva (HC) é um método projetado para criarindivíduos viáveis a partir de uma solução vazia. Duas HCs simples foram desenvolvidasneste trabalho.

A Heurística Construtiva 1 (HC1) seleciona aleatoriamente uma facilidade para abrirum módulo em todos os períodos de tempo até um indivíduo viável ser formado. Emoutras palavras, a HC1 repete a operação de ativação do segmento de genes Si

1T parafacilidades aleatórias até as desigualdades (3.1) serem verdadeiras.

A Heurística Construtiva 2 (HC2) seleciona aleatoriamente uma facilidade para abrirum módulo entre um intervalo de tempo selecionado também aleatoriamente até um in-divíduo viável ser formado. Diferentemente da HC1, na HC2 os três parâmetros do seg-mento de genes ativado são escolhidos aleatoriamente. A HC2 também termina assim queuma solução viável é obtida.

Um fenômeno comum na HC2 é a mudança de representação dos segmentos de ge-nes quando segmentos gerados em uma mesma facilidade são sobrepostos. Por exemplo,se os segmentos S j

24 e S j35 são os únicos ativados numa mesma facilidade, j é composto


pelos genes {0,1,2,2,1}. Um remapeamento dos segmentos mostrará que os segmentosinseridos foram modificados para S j

25 e S j34. Este fenômeno, também presente em outros

mecanismos do AG+VNDi, diversifica a busca por novas soluções na exploração de vizi-nhanças que lidam com a movimentação de segmentos, como é o caso de uma das buscaslocais que será apresentada mais adiante.

É fácil observar que a HC1 é um caso especial da HC2 para quando ti = 1 e t f = Tsão fixos. Portanto, o domínio das soluções possíveis de serem geradas pela HC1 é umsubconjunto do domínio da HC2. Entretanto, a HC1 gera soluções em média melhoresque a HC2 devido a menor variação de mudanças de módulos nas facilidades. Já a HC2consegue gerar soluções mais diversificadas, que podem ser úteis nos cruzamentos doAG. Por oferecer esta diversificação, a HC2 é utilizada em outras partes do algoritmodesenvolvido quando gerar novas soluções for necessário.

3.2.4 Operadores do Algoritmo GenéticoComo um algoritmo evolucionário, o AG+VNDi realiza cruzamentos entre indivíduos

de uma mesma geração para gerar novas soluções que farão parte da geração seguinte.Este processo evolucionário realiza operações em quatro etapas: seleção, cruzamento,mutação e aceitação.

Seleção

O operador de seleção usado no AG+VNDi combina os métodos de seleção de fa-mília e seleção de indivíduo dentre os apresentados em Hollstien (1971). A populaçãoé dividida em classes A (alta), B (média) e C (baixa). O primeiro indivíduo usado nocruzamento é selecionado aleatoriamente dentre os que compõem a classe A. O outro éselecionado dentre qualquer uma das três classes. A quantidade de indivíduos que com-põem cada classe é controlada pelos parâmetros α e β. Como em Ericsson et al. (2002),a próxima geração será composta pela promoção automática dos indivíduos da classe Aatual, pelos indivíduos formados pelo operador de cruzamento e por novos indivíduos ge-rados pela HC2 que substituirão os da classe C nas proporções mostradas na Figura 3.3.O ao final da execução dos operadores do AG, os indivíduos são reordenados em funçãoda aptidão. Portanto, a composição das classes em cada geração é dinâmica.

Cruzamento

Selecionados os dois indivíduos pais é realizado o cruzamento. Como em Fernandeset al. (2014), o operador decide aleatoriamente para cada facilidade dos pais qual a confi-guração será repassada para o filho. A Figura 3.4 mostra o processo de escolha dos genesdo filho.

Computacionalmente, o operador de cruzamento consiste em gerar um vetor binárioem que cada bit corresponde a uma facilidade e seu valor ao pai escolhido. Isto significaque até 2J diferentes configurações de filhos podem ser geradas. Porém, se a configuraçãode facilidades iguais for igual entre os pais, a diversidade do operador cai a um fator tam-bém exponencial. Isto significa que há uma tendência de aceleração da homogeneização


Figura 3.3: Operador de seleção de indivíduos para nova geração

da população à medida em que se passam gerações. Por um lado isto reduz o tempo gastona avaliação dos novos indivíduos, uma vez que comumente aparecerão combinações degenes já avaliadas pelo FCM, o que torna o processo de avaliação a uma simples recupera-ção de dados em THASH . Por outro, uma população muito homogênea dificilmente geraráfilhos com configurações distantes das existentes, reduzindo as chances de melhoria emótimos locais. O AG+VNDi possui diversas ferramentas de diversificação para manter umbom nível de heterogeneidade na população. Uma delas, já apresentada, é permitir quenovas soluções sejam geradas pela HC2 a cada geração substituindo a classe C. Outras,como a mutação e a aceitação, serão mostradas na sequência.

Mutação

Na biologia, a mutação é um processo de modificação aleatória dos genes de um indi-víduo. No AG+VNDi o operador de mutação unifica algumas das vizinhanças exploradaspelas buscas locais (explicadas mais adiante na seção 3.2.5) para modificar o indivíduoformado no cruzamento. O operador foi projetado de modo que uma parte dos genes doindivíduo seja deslocada para uma outra posição na matriz de solução. O processo é di-vidido em duas etapas: seleção e deslocamento. Na seleção são escolhidos os módulosque serão alterados. Já no deslocamento estes são movidos para uma outra facilidade. OAlgoritmo 3 mostra os passos do operador criado.

O operador inicia recebendo o indivíduo gerado no cruzamento (linha 1). A muta-ção só ocorrerá se o filho for sorteado com probabilidade definida pelo parâmetro %mut(linha 2). O método seleciona uma facilidade jo que possua algum módulo aberto (li-nha 3) e em seguida determina os módulos que serão retirados (linha 4). Os pontos doscortes horizontais hCut(a) para cima e hCut(b) para baixo são valores entre zero e a al-tura da facilidade H j representada pelo seu maior módulo aberto. As linhas 5-8 mostramum operador de corte que oferece a possibilidade de mover apenas parte dos módulosselecionados com probabilidade de 50% de execução. vCut(c) é o corte no horizonte de


Figura 3.4: Operador de cruzamento

planejamento e, se existir, fará com que apenas os módulos até ou a partir deste períodoselecionado sejam movidos (linha 7). Os módulos entre hCut(a) e hCut(b) são retiradosda origem respeitando o limite mínimo de zero módulos caso haja menos módulos abertosque a quantidade selecionada (linhas 9-11). A partir da linha 12 começa a fase de deslo-camento dos módulos. Selecionamos uma facilidade destino jd qualquer e movemos osmódulos retirados para ela também respeitando o limite de módulos máximo L em cadafacilidade (linhas 13-15). As linhas 16-18 oferecem um operador de mudança tambémcom probabilidade de 50% de ser usado. Quatro possibilidades de mudanças com iguaisprobabilidades podem ocorrer: abertura mais cedo de um módulo, abertura mais tardede um módulo, fechamento mais cedo de um módulo ou fechamento mais tarde de ummódulo (linha 17). Ao final, o filho mutado é retornado.

A Figura 3.5 mostra um exemplo de indivíduo modificado pela mutação. As três pri-meiras etapas são referentes à retirada dos módulos da facilidade origem e as duas últimasà reinserção na facilidade destino. As quatro possibilidades de mudança dos módulos re-tirados são mostradas em 5.1 a 5.4 na figura, mas apenas uma delas é escolhida. Noexemplo foi escolhida a opção sublinhada em 5.2 resultando no indivíduo mostrado nocanto superior direito.

Aceitação

O operador de aceitação determina quais os filhos gerados que permanecerão vivos nageração seguinte. Para isto, eles devem passar pelos seguintes critérios:

1. ser um indivíduo viável;

2. ter custos fixos de no máximo 10% maiores que os custos fixos do pior indivíduoda classe A;


Algoritmo 3 Mutação1: Seja x o filho gerado no cruzamento;2: if %mut then3: Seleciona uma facilidade origem jo ∈ J que tenha algum módulo instalado;4: Seleciona pontos dos cortes horizontais para cima hCut(a) ∈ [0,H j − 1] e para

baixo hCut(b) ∈ [a+1,H j];5: if Corte then6: Seleciona ponto do corte vertical vCut(c) ∈ [ti +1, t f ];7: Realiza corte vertical à direita (ti = vCut(c)) ou à esquerda (t f = vCut(c));8: end if9: for t = ti to t f do

10: G jot = MAX{G jot− (hCut(a)−hCut(b)),0};11: end for12: Seleciona facilidade destino jd ∈ J ;13: for t = ti to t f do14: G jdt = MIN{G jdt +(hCut(a)−hCut(b)),L};15: end for16: if Muda then17: G jd(ti−1) = G jd(ti−1)+1 or G jdti = G jdti−1 or G jdt f

= G jdt f−1 or G jd(t f+1) =

G jd(t f+1)+1;18: end if19: return Filho x mutado;20: end if

3. ser diferente de qualquer outro indivíduo na população atual ou aceito para a popu-lação posterior;

4. e ser diferente de qualquer indivíduo processado no histórico do VND.

O primeiro critério evita que soluções inviáveis participem do processo evolucionário.O segundo busca descartar soluções que potencialmente serão ruins antes de executar oprocesso de avaliação. O terceiro impede que indivíduos idênticos façam parte da mesmapopulação, o que reduziria a diversidade da geração. Por fim, o quarto evita que indiví-duos que já passaram pelo VND tenham influência sobre futuras gerações, aumentandoas chances dos indivíduos vivos serem pontos de início da busca melhores. Experimentoscomprovando a eficiência do uso destes critérios serão mostrados no próximo capítulo.

Se o filho gerado não for aceito, os processos de seleção, cruzamento e mutação sãorepetidos até que indivíduos sejam aceitos. Ao final, os indivíduos gerados na classe Bsão avaliados e ordenados junto aos indivíduos da classe A para a próxima geração. Paraeconomia de tempo, os da classe C não são avaliados, já que é pouco provável que a HC2gere soluções que possam entrar diretamente na classe A.


Figura 3.5: Operador de mutação

3.2.5 VizinhançasComparada a outras metaheurísticas, a velocidade de evolução das soluções em Algo-

ritmos Genéticos simples é lenta [Arostegui et al. 2006]. Uma estratégia de intensificaçãocomum é a hibridização do AG com heurísticas de busca local (BL) aplicadas nas soluçõesda população.

Na revisão da literatura foi mostrado que existem diversas buscas locais de sucessopara resolver problemas de localização de facilidades. Entretanto, buscas mais sofisti-cadas, como a substituição de múltiplas facilidades, apesar de serem efetivas podem setornar demasiadamente custosas computacionalmente. As vizinhanças de busca devemser definidas de modo que a varredura seja eficiente em termos de tempo de execução.

Uma busca local pode ser criada para o DFLPG a partir de operações derivadas dasvizinhanças clássicas usadas nos FLPs. Levando em consideração o contexto dinâmico emodular do problema, foram definidas cinco operações básicas que podem ser combina-das para formar a vizinhança de uma busca local. São elas:

Op 1. Adicionar um segmento de genes;Op 2. Retirar um segmento de genes;Op 3. Cortar na vertical e mover um segmento de genes;Op 4. Cortar na horizontal e mover uma facilidade;Op 5. Cortar na vertical e mover uma facilidade.

Nas operações de corte e movimento também deve ser definida uma direção indicando


qual lado do corte terá seus módulos movidos. Na descrição do operador de mutaçãoforam utilizadas as notações vCut e hCut para indicar os cortes vertical e horizontal,respectivamente, realizados no processo de mutação. Agora, será adicionada uma seta aofinal da notação para indicar para qual direção o corte será direcionado. Por exemplo,vCut(2)→ representa um corte vertical no período 2 realizado à direita e hCut(3) ↑ umcorte horizontal no módulo 3 realizado para cima. A Figura 3.6 mostra diferentes formasde extrair uma parte do segmento cortado utilizando as operações de corte de segmentos(Op 3). A primeira etapa consiste no mapeamento dos segmentos de genes da facilidadeorigem. Selecionado o segmento a ser cortado, cortes verticais são realizados à direita, àesquerda ou mesmo as duas operações simultaneamente, de modo a mover um bloco demódulos intermediário do segmento.

Figura 3.6: Operação 3: Corte vertical de segmentos de genes

As operações de corte de facilidades funcionam de modo semelhante. A Figura 3.7mostra um exemplo com as quatro possibilidades de cortes de facilidades.

Figura 3.7: Operações 4 e 5: Corte vertical e horizontal de facilidades

As Op 4 e Op 5 já foram mostradas anteriormente neste trabalho na Figura 3.5 querepresenta o operador de mutação na fase de retirada de módulos da facilidade origem.Ainda sobre a mutação, operações de adição e retirada de segmentos (Op 1 e 2, respec-tivamente) são feitas no operador de mudança apresentado na mesma figura para o casoespecial em que o tamanho do segmento adicionado/retirado é limitado a somente umperíodo. O operador de mutação utiliza explicitamente quatro das cinco operações de vi-zinhança definidas. A Op 3 é usada de forma implícita quando o piso e o teto selecionadosseparem um único módulo e a mutação passar pelo operador de corte.

As buscas locais criadas para o problema aqui tratado também consistem em efetuaruma ou múltiplas operações para gerar uma nova solução em sua vizinhança. A Tabela


3.2 resume quais tipos de operações são efetuadas explicitamente em cada busca localcriada.

Tabela 3.2: Operações de vizinhança realizadas nas buscas locais

Busca LocalOperação

1 2 3 4 51 X X2 X X X3 X X

A seguir serão descritas as vizinhanças das BLs criadas, resumidas às etapas maisimportantes do algoritmo. Em seguida, é feita uma análise de complexidade de cada umadelas.

Busca Local 1: Soluções a um segmento de distância

A Busca Local 1 (BL1) realiza todos os movimentos possíveis de acrescentar e reti-rar um segmento de genes da solução atual. Ela inicia a busca numa facilidade aleatóriadeterminada antes do seu início. Como a descida é pelo primeiro aprimorante, inicia-mos as buscas por diferentes facilidades para que não seja tendenciosa a favor de algumafacilidade.

Pré-processamento. Antes de iniciar a busca, os custos de alocação de cada períodode tempo da solução original são armazenados num vetor de tamanho T . Desta forma,quando for necessário avaliar uma solução modificada na busca, o tempo gasto para avali-ação dos períodos não alterados é de O(1), mais eficiente que a busca em THASH . Um outrovetor armazena os custos modificados durante a busca por facilidade, também reduzindoa complexidade da avaliação da solução.

Adição de segmento. A primeira vizinhança explorada é a de adição de um segmentode módulos. Todas as combinações de adição são testadas, como mostra a Figura 3.8, ex-ceto se em algum período de tempo a facilidade estiver equipada com o L-ésimo módulo.Neste caso, a iteração é passada para a seguinte.

Retirada de segmento. Se nenhuma solução aprimorante for encontrada na fase deadição, a busca varre a vizinhança de retirada de um segmento de genes. Assim como naadição, se na retirada uma facilidade estiver fechada, a iteração vai para a próxima. Alémdisto, como a retirada de capacidade da rede pode resultar em inviabilidade, a quantidadede iterações que resultam em soluções viáveis nesta vizinhança poderá ser significativa-mente menor que na vizinhança de adição.

Análise de complexidade. No pior caso, a BL1 faráT∑

i=1(−i2+Ti+ i) modificações de

módulos eT 2 +T

2iterações de adição de segmentos em cada facilidade em J (igualmente

para retirada de segmentos). Portanto, a vizinhança de uma solução explorada por estaBL contém até J(T 2 + T ) soluções, sendo J a quantidade de locais em J . A Figura3.8 mostrou um exemplo para T = 5 onde são realizadas 35 modificações de módulos(quantidade de números "1"na figura) e 15 iterações de adição. Como originalmente todos


Figura 3.8: Iterações da BL1 - adição de um segmento a facilidade

os módulos na facilidade mostrada estavam fechados, não é possível fazer mudanças deretirada de módulos. Portanto, a vizinhança desta facilidade possui apenas 15 soluções.

A avaliação de cada solução vizinha é feita através da atualização dos custos de locali-zação nos períodos modificados somando-se aos novos custos de alocação. Nos períodosnão modificados, estes custos são obtidos através da recuperação dos valores armazena-dos no vetor descrito no pré-processamento em O(1). Nos demais períodos, poderá sernecessário executar o algoritmo de FCM ou não. A maioria das modificações resultará emconfigurações já exploradas pela BL, não sendo necessário executar novamente o FCM.De fato, no pior caso, apenas 5 execuções do algoritmo seriam necessárias para avaliaras 35 modificações do exemplo anterior. Portanto, a quantidade máxima de execuções doFCM em uma passagem da BL1 será de 2JT , ou seja, O(JT ), em que a constante vem dasoma das operações de adição e retirada. Para mover a solução atual para uma nova me-lhor solução encontrada na vizinhança, basta atualizar os valores do vetor correspondenteà facilidade modificada e os novos custos do indivíduo, todas operações feitas em O(1).

Busca Local 2: Substitui e altera partes de um segmento de uma facilidade a uma outra

A Busca Local 2 (BL2) realiza movimentos de mudança de segmentos de módulosexistentes na solução para outras facilidades. Os movimentos são graduais, ou seja, corta-se o segmento em cada período e move o corte para a outra facilidade. Além disto,ao adicionar o segmento na nova facilidade, pequenas mudanças no período em que osegmento inicia e termina também são testadas.


Mapeamento de segmentos. A BL2 tem uma fase de pré-processamento semelhantea BL1 com uma etapa a mais. Esta etapa consiste no mapeamento dos segmentos degenes do indivíduo. O mapeamento é feito conforme a definição de segmento de genes(seção 3.2.1) usando um algoritmo de busca que percorre a matriz de genes procurandopor genes maiores que zero.

Troca de segmentos. A troca de segmentos explora uma vizinhança similar a detroca de facilidades nos FLPs estáticos. Para cada segmento mapeado de comprimentoC = t f − ti +1 serão feitas 2C−1 operações de troca, sendo C−1 cortes a direita, C−1cortes a esquerda e uma troca completa (Figura 3.9).

Figura 3.9: Iterações de troca de segmentos da BL2

Assim como na BL1, haverão casos em que a troca de módulos pode resultar em solu-ções inviáveis caso o mesmo módulo tenha capacidade menor em outras facilidades, o quepoderá resultar numa diminuição de capacidade das instalações da rede. Um módulo tam-bém não poderá ser movido para uma facilidade que esteja operando em sua capacidademáxima.

Nem todos os segmentos precisam ser testados por todas as iterações. Para segmentosiguais de uma mesma facilidade apenas um é movido. Segmentos com inícios iguais, cor-tes à direita do menor deles resultam em configurações testadas pelo maior. Igualmente,


segmentos com finais iguais, o menor não passa pela fase de cortes à esquerda.Modificação do segmento trocado. Cada iteração da BL2 tem a vizinhança expan-

dida de modo a permitir que pequenas mudanças no período de abertura e/ou de fecha-mento de módulos sejam testadas. Seja Stit f o módulo modificado, no total cada iteraçãofaz nove testes de mudança de módulos:

1. Stit f - Move o corte original;

2. S(ti−1)t f - Abre o segmento um período mais cedo;

3. S(ti+1)t f - Abre o segmento um período mais tarde;

4. Sti(t f−1) - Fecha o segmento um período mais cedo;

5. Sti(t f+1) - Fecha o segmento um período mais tarde;

6. S(ti−1)(t f−1) - Operação 2 + 4;

7. S(ti−1)(t f+1) - Operação 2 + 5;

8. S(ti+1)(t f−1) - Operação 3 + 4;

9. S(ti+1)(t f+1) - Operação 3 + 5.

Análise de complexidade. Quando o tamanho do segmento movido for igual aotamanho máximo do horizonte de planejamento T , a BL2 realiza 2T − 1 iterações entrecada par de facilidades para cada segmento na fase de troca. O exemplo da Figura 3.9mostra as nove iterações que são realizadas para um T = 5.

A fase de modificação do segmento expande a vizinhança de uma solução adicionandovizinhos resultantes das operações de modificação aos cortes da fase de troca de segmen-tos, desde que sejam viáveis. Um corte de segmento com C = T , por exemplo, terá trêssoluções vizinhas testadas resultante das operações de diminuição do comprimento dosegmento na modificação (operações 3, 4 e 8). Se todas as oito operações de mudançapuderem ser feitas, até oito novas soluções são alcançadas na busca.

O tamanho de uma vizinhança da modificação de um segmento qualquer do indivíduoé dado pela soma da quantidade de iterações de corte que podem ser feitas (mostradaantes como sendo igual a 2C−1) com a quantidade de operações viáveis de modificaçãodo segmento trocado. No segmento S j

15, numa instância com T = 5 (como no exemploda Figura 3.9), nove soluções vizinhas serão alcançadas no movimento de troca e cortes,e cada iteração possuirá diferentes quantidade de operações viáveis de modificação. Aiteração 1 possui apenas três movimentos possíveis. As iterações 2 e 6, que possuem C =1, também possuem três movimentos. Nas demais iterações, cinco diferentes movimentospodem ser realizados em cada. No total, 39 configurações são alcançáveis na fase demodificação do exemplo que, somadas às 9 iterações da fase de troca, resulta em umavizinhança com 48 soluções alcançáveis em cada movimento de segmento da BL.

Um segmento com ti = 1 e t f = T , possuirá 10C−11 soluções vizinhas resultantes dafase de modificação, além das 2C−1 soluções da fase de troca. Mesmo com diferentes ti e


t f a ordem da quantidade de vizinhos formados por um segmento é O(C). Se uma soluçãopossui um único segmento ativado, então haverão J− 1 destinos para este segmento eo tamanho da vizinhança da BL2 será de O(JC). Porém, num indivíduo com múltiplossegmentos, a análise do tamanho da vizinhança da BL é mais complexa.

Segmentos iguais de módulos diferentes da facilidade origem geram vizinhanças iguais.Por exemplo, uma facilidade origem o que possui os genes {2, 2, 2, 2, 2} tem dois seg-mentos semelhantes So

15 ativados. Neste caso, a fase de troca de segmentos da BL resul-tará exatamente nas mesmas configurações para qualquer um dos segmentos. Entretanto,numa facilidade {1, 2, 3, 2, 1} a troca dos três segmentos disponíveis resultarão em con-figurações diferentes. No segmento do primeiro módulo, a BL2 realizará nove iterações,como mostrado anteriormente. No do segundo módulo serão feitas cinco iterações. Porfim, no segmento do terceiro módulo, mais uma iteração. Neste exemplo, a busca nos trêssegmentos gera 15 novas soluções vizinhas na troca de cada facilidade origem com cadadestino.

Para cada segmento diferente numa facilidade origem, a fase de modificação dos seg-mentos expande a vizinhança da busca em O(C). No pior caso, cada facilidade J possuiaté O(LT ) segmentos distintos (i.e., facilidade {L, 0, L, . . . , 0, L , 0 possui LT/2 segmen-tos). Sendo J−1 destinos e C = 1 como no exemplo citado, a complexidade de pior casodo tamanho da vizinhança de busca é O(J2LT ).

Apesar da enorme vizinhança, para a avaliação das soluções vizinhas uma quanti-dade de FCMs muito menor que a quantidade de vizinhos precisará ser resolvida. Nafase de troca de segmentos, os movimentos de corte à direita e à esquerda resultam emconfigurações de facilidades iguais às testadas na troca completa. Na Figura 3.9 isto ébem evidenciado. Na iteração 1, cinco novas configurações são geradas, sendo uma emcada período, o que requer a execução de cinco FCMs. Na iteração 2, a configuraçãodo primeiro período já foi explorada na iteração anterior e as demais são semelhantes àsoriginais, não havendo necessidade de executar novos FCMs para avaliação da solução. Omesmo acontece nas demais iterações. Desta forma, apesar das 2T −1 iterações de trocade segmentos, apenas T execuções do FCM serão feitas.

Na fase de modificação do segmento, apenas as operações 2, 3, 4 e 5 podem necessi-tar de uma execução do FCM, pois podem gerar configurações inexploradas nos períodosmodificados. Entretanto, as modificações feitas por estas operações são equivalentes aadicionar um segmento de módulos de comprimento C = 1 a um período anterior (opera-ção 2) e posterior (operação 5) ao segmento modificado ou retirar um segmento de mesmocomprimento do primeiro período do segmento (operação 3) e do último (operação 4).Todas estas operações de inserção e retirada de segmentos resultam em configuraçõestambém possíveis de ser geradas pela BL1. Consequentemente, a repetição de configura-ções de facilidades nos períodos modificados não exigirá novas execuções de FCMs. Oresultado disto é que a fase de modificação do segmento expande enormemente a vizi-nhança de busca da BL2 sem afetar a ordem de complexidade do algoritmo relacionada aquantidade de execuções de FCMs.

Se cada troca de segmentos entre um par de facilidades resulta em até T execuçõesde FCM, então a quantidade máxima de FCMs realizadas pela BL2 será de (J2− J)T , ouseja, a complexidade de pior caso desta busca local é O(J2T ). Como a BL2 se trata de


uma busca local que procura em vizinhanças onde trocas de módulos são efetivadas e suacomplexidade não é influenciada por L - quantidade máxima de módulos por facilidade- esta é uma boa busca local para resolver instâncias onde potencialmente uma grandequantidade de módulos podem ser construídos nas facilidades.

Busca Local 3: Substitui múltiplos segmentos de uma mesma facilidade para outra

A Busca Local 3 (BL3) realiza movimentos de mudança de segmentos pertencentes auma mesma facilidade simultaneamente. Em termos de operações de vizinhanças, a BL3realiza uma Op 4 direcionada acima seguida por duas Op 5 sendo o corte mais a esquerdadirecionado à direita e o corte mais a direita direcionado à esquerda (Figura 3.10). Osmódulos retirados (em verde na figura) são então deslocados e testados em cada uma dasdemais facilidades da instância.

Figura 3.10: Operações da BL3

Mapeamento das facilidades. A BL3 possui a mesma fase de pré-processamento daBL2, exceto que o mapeamento não é feito no nível de segmentos, mas de facilidades. Omapeamento consiste em determinar as alturas H j das facilidades j. A altura é igual aomaior nível de capacidade aberto, portanto H j = max{G jt}, ∀t ∈ T .

Deslocamento dos módulos. A mudança dos módulos é feita em todas as combina-ções de cortes horizontais para cima e verticais. O pseudo-código do Algoritmo 4 mostratodas as iterações testadas de deslocamento dos módulos, onde jo é a facilidade origem,jd o destino, a o ponto do corte horizontal hCut(a) ↑ que deve ir até a altura H jo , e b e cos pontos dos cortes verticais vCut(b)→ e vCut(c)←.

Ao contrário da BL2 que trabalha com um único corte vertical no segmento, a BL3usa dois cortes (linhas 8 e 9 do Algoritmo 4), o que permite testar todas as combinaçõesde períodos possíveis de mudanças. Entretanto, para evitar uma expansão muito grandeda vizinhança acarretando em um custo computacional elevado, apenas um corte é feitona horizontal (linha 6).

Análise de complexidade. A quantidade de iterações feitas em cada conjunto desegmentos movidos na BL3 depende dos comprimentos C dos segmentos de genes e daaltura H da facilidade. Um conjunto "retangular", ou seja, todos os genes da facilidadesão iguais a G jt = H, ∀ j ∈ J, t ∈ T , e C = T , representa a situação no pior caso. Para

cada nível de capacidade neste caso,(T 2 +T )

2trocas seriam realizadas.

Na fase de retirada dos módulos, o indivíduo com pior entrada possível seria aqueleque possui todos os genes da matriz de solução iguais a bL/2c, portanto H = bL/2c,


Algoritmo 4 Deslocamento de módulos na BL31: Seja um indíviduo x;2: for jo = 1 to J do3: if H jo > 0 then4: Calcula ti e t f ;5: for a = 1 to H jo do6: for jd = 1 to J do7: for b = ti to t f do8: for c = b to t f do9: if jo 6= jd then

10: Desloca θc = MAX{G joc − a,0} módulos de G joc para G jdc for-mando um novo indivíduo x∗ com custo f (x∗);

11: if f (x∗)< f (x) then12: return x∗;13: end if14: end if15: end for16: for c = b to t f do17: Retorna θc módulos de G jdc para G joc;18: end for19: end for20: end for21: end for22: end if23: end for24: return x;

uma vez que um gene acima da metade da quantidade máxima de módulos não poderáser movido a uma facilidade que também possua um gene acima da metade (e.g., moverseis módulos para uma facilidade que já possui seis módulos abertos quando o númeromáximo de módulos é 10).

O tamanho de uma vizinhança N na BL3 é determinada de forma exata através doscomprimentos dos segmentos da solução. Desconsiderando módulos numa mesma facili-dade com mais de um segmento ativo no horizonte de planejamento, seja um indivíduo xcom M módulos com segmentos ativos, cada módulo tem comprimento Cm. Então, paraum L grande o suficiente para que todas as facilidades possam receber os módulos daorigem,

N(x) =(J−1)

2

M

∑m=1

(C2m +Cm), (3.2)

onde J− 1 representa a quantidade de facilidades destino e o outro fator é a quantidadede iterações que geram novos indivíduos para cada segmento. No indivíduo de pior caso,como descrito anteriormente, Cm = T , ∀m= {1, . . . ,M}, e M = bL/2cJ. A sua vizinhança


conterá bL/2c(J2− J)T 2 +T

2indivíduos.

Como já foi mostrado nas outras BLs, o simples movimento de módulos entre facili-dades não é custoso computacionalmente. Se em cada nível de capacidade até T FCMssão realizados em cada deslocamento de módulos entre a facilidade origem e destino, acomplexidade de pior caso da quantidade de execuções de FCMs na BL3 é de O(J2T L). Épossível ainda determinar a quantidade exata de FCMs calculados numa passagem da BL3por (J− 1) ∑

j∈J∑

t∈TG jt , sendo o segundo fator do produto a quantidade total de módulos

abertos em todos os períodos do horizonte de planejamento.Um ponto importante para justificar o uso da BL3 é que ela possui uma vizinhança

que intercede grande parte da vizinhança da BL2. Com isto, estas duas buscas sendo exe-cutadas de forma complementar não serão tão mais custosas que a execução única de cadauma delas. Assim, grandes vizinhanças poderão ser exploradas a um custo computacionalrazoável.

3.2.6 ElitismoA aplicação das buscas locais apresentadas é feita através de um operador de elitismo

no AG+VNDi. De maneira geral, o elitismo consiste em selecionar indivíduos na popula-ção para serem melhorados, geralmente até atingirem ótimos locais. O critério de seleçãodos indivíduos que passarão pelo processo de elitismo deve ser escolhido com base nanatureza do problema e nos recursos disponíveis. Um extremo é aplicar o elitismo emtodas as soluções geradas pelo Algoritmo Genético. Neste caso, o algoritmo evolucio-nário resultante é chamado de Algoritmo Memético [Moscato & Norman 1992]. Porém,quando o processo de elitismo for demasiadamente custoso para ser executado, o que écomum em FLPs complexos, uma abordagem memética pode não ser a mais ideal.

No AG+VNDi foi definido que o elitismo deve ser efetuado periodicamente em umúnico indivíduo da população. Em quatro situações o elitismo é executado:

• Logo após a criação da população inicial executa para o melhor indivíduo criado;• Quando um novo melhor indivíduo é encontrado nos operadores do AG executa

para este indivíduo;• A cada GV ND iterações executa para um indivíduo selecionado aleatoriamente entre

os indivíduos das classes A e B;• Após a execução do operador de reinício da população (mostrado mais adiante na

seção 3.2.7) executa para um indivíduo recriado aleatório.

O operador de elitismo foi projetado para ser executado usando a estrutura de umVND com as três vizinhanças definidas anteriormente. A estrutura utilizada no VND ésemelhante a apresentada no Algoritmo 1 no capítulo da revisão de literatura.

Um cuidado a se tomar ao aplicar o VND é determinar bons pontos de início da busca.No operador de seleção mostramos que soluções iguais ou que já passaram pelo VND sãodescartadas a priori da busca se geradas no AG. O VND também possui um mecanismode descarte, porém a posteriori. Nele, as soluções que já foram exploradas em cadauma das três buscas são armazenadas separadamente. Se durante a busca o indivíduo em


processamento se tornar igual a uma destas soluções na mesma heurística em que estasolução foi encontrada no passado, o VND é abortado e a solução é descartada. Isto éfeito porque haverá uma alta probabilidade de que esta busca termine no mesmo ótimolocal encontrado num VND passado. Também é descartado o indivíduo gerado pelo VNDque seja igual a um outro existente na população pela mesma justificativa do operador deseleção de eliminar soluções iguais. Com estes operadores diminui a probabilidade de quesoluções sem potencial de melhoria pelo VND tenham influência nas futuras gerações.Para manter a quantidade de indivíduos estável na população, um novo indivíduo é geradopela HC2 substituindo o indivíduo descartado.

O operador de elitismo resultante é mostrado no Algoritmo 5. O primeiro passo é de-finir a ordem de exploração das três vizinhanças criadas (linha 1). Em seguida, o valor daaptidão do indivíduo a ser elitizado xp

g é armazenado na lista de soluções que já passarampelo VND referente à primeira vizinhança explorada (linha 3). As BLs são executadas se-quencialmente até que não seja possível encontrar uma solução aprimorante em nenhumadas vizinhanças (linhas 4-19). Todas as BLs usam o método de descida do primeiro apri-morante e são executadas em exaustão (linhas 5-13). A exploração da k-ésima vizinhançaé feita na linha 7. Se a solução encontrada já foi explorada por esta vizinhança anteri-ormente, o indivíduo é descartado e um novo criado pela HC2 é inserido na populaçãoem seu lugar (linha 9). Caso contrário, o valor da aptidão é inserido na lista referente avizinhança explorada (linha 11). Quando soluções forem aprimoradas numa vizinhança,após a busca em exaustão, o VND retorna a busca para a primeira vizinhança (linhas 14-18). Se a solução final for semelhante a alguma solução existente na população atual P ,o indivíduo também é descartado e recriado (linha 21). Ao final, se a solução encontradanão tiver sido descartada na linha 9 ou 21, ela substituirá a solução inicial (linha 23).

3.2.7 Reinício da populaçãoUma outra estratégia de diversificação implementada no AG+VNDi é o reinício pe-

riódico da população. Nela, todos os indivíduos vivos, exceto o melhor, são substituídospor novos indivíduos gerados pela HC2 a cada GR gerações depois que a melhor soluçãonão tenha sido alterada. O objetivo é criar uma nova população com uma diversidadediferente da anterior. A quantidade de reinícios R feitos no algoritmo é um dos critériosde parada do AG+VNDi.

3.3 Pseudo-código do AG+VNDiAs estruturas do AG+VNDi apresentadas são executadas como mostrado no pseudo-

código do Algoritmo 6. Os parâmetros de tamanho da população (P), tamanho das classesA (α) e B (β), quantidade de reinícios (R), probabilidade de mutação (%mut), geraçõespara realização do VND (GV ND), gerações para reinício (GR) e tempo máximo de exe-cução (tMAX ) são iniciados (linha 1). Também são criadas na linha 2 as estruturas res-ponsáveis por armazenar os resultados passados pelas buscas locais (Ln) e os resultadosdas execuções do FCM (THASH). A leitura da instância (linha 3) e o inicio da população(linha 4) são feitos em seguida. Cada indivíduo p na geração g é representado por xp

g .

3.4. OUTRAS CONSIDERAÇÕES SOBRE O AG+VNDI 45

Algoritmo 5 Elitismo1: Define a ordem das BLs em N ;2: x

′←xpg ;

3: Insere f (x′) em L1;

4: for n = 1 to 3 do5: repeat6: fi = f (x

′);7: Executa BLn(x

′);8: if f (x

′)∈Ln then9: return Substitui xp

g por novo indivíduo criado pela HC2;10: else11: Insere f (x

′) em Ln;12: end if13: until f (x

′)6= fi

14: if f (x′) mudou na BLn and n 6= 1 then

15: n = 1;16: else17: n = n+1;18: end if19: end for20: if f (x

′)= f (xpg ) para algum p ∈ P then

21: return Substitui xpg por novo indivíduo criado usando HC2;

22: end if23: return xp

g ← x′;

A população inicial é criada (linhas 5-11), sendo metade dos indivíduos pela HC1 e orestante pela HC2. Os indivíduos criados são avaliados e ordenados pela função objetivoem ordem crescente de custo (linha 12). Antes de iniciar as iterações, o algoritmo elitizacom o VND a melhor solução gerada pelas HCs (linha 13). Pelo menos GR geraçõesserão avaliadas a menos que o clock atinja o tempo máximo de execução do algoritmo(linha 15). Em cada geração os operadores de seleção, cruzamento, mutação e aceitaçãodo AG são executados (linha 16). O elitismo é feito quando um novo melhor indivíduoé encontrado ou passaram-se GR gerações sem melhoria no indivíduo (linhas 18-21). Ocontador de gerações g é reiniciado sempre que uma nova melhor solução for encontradapelos operadores (linhas 22-24). Após GR gerações sem melhoria, o reinício é aplicado(linha 26-30) e um elisitsmo é executado em uma das soluções novas (linha 29). A melhorsolução encontrada é retornada ao final do algoritmo (linha 32).

3.4 Outras considerações sobre o AG+VNDiEm termos de complexidade, as buscas locais são os mecanismos mais custosos do

AG+VNDi. Isto porque estas heurísticas exigem um processamento enorme de soluçõesvizinhas para encontrar uma solução aprimorante. Em um nível mais baixo, podemos de-


terminar a complexidade do algoritmo pela quantidade de execuções do FCM. Nos casosem que o FCM já foi executado a avaliação da solução pode ser feita rapidamente atravésda busca na tabela hash que guarda as soluções das configurações de facilidades já explo-radas. Isto significa que efetuar buscas locais em soluções muito próximas é muito menoscustoso que em soluções de uma população muito heterogênea, o que justifica o uso dooperador de cruzamento convergente no AG+VNDi. Entretanto, soluções parecidas ten-dem a levar a ótimos locais semelhantes.

Uma outra maneira de acelerar as buscas é feita reaproveitando os grafos construí-dos na execução do algoritmo para facilitar as inicializações avançadas (warm starts) naresolução do fluxo a custo mínimo. O último grafo utilizado num FCM é mantido peloAG+VNDi. Quando houver demanda para uma nova execução do FCM, o grafo é refor-mulado atualizando os nós e arcos ativos. Com isto, o FCM utiliza parte da estrutura dasolução anterior como solução inicial da nova configuração evitando recomeçar a buscapelo fluxo ótimo do zero.

A complexidade de cada BL é subjetiva e depende da estrutura da solução a ser ava-liada. Na BL1, por exemplo, cada gene igual a zero ou L impede o teste de retirada ouadição de um módulo, respectivamente, reduzindo a quantidade de execuções do FCM.Da mesma forma, soluções apertadas - quando há pouca capacidade ociosa - terão poucosmovimentos viáveis de redução de módulos.

Nas instâncias com custos de localização relativamente altos, comuns em problemasde localização, a média de execuções do FCM na BL1 tenderá a um valor próximo a JT(quantidade máxima de execuções do FCM para operações de adição de um módulo),uma vez que haverá poucas opções de redução de capacidade gerando soluções viáveis.O número de chamadas poderá ser ainda menor se houver facilidades sendo utilizadas emseu máximo nível de capacidade, evitando operações de adição de segmentos.

Supor instâncias com custos de localização altos é bastante razoável em aplicaçõeslogísticas, uma vez que construir facilidades são projetos que exigem vultuosos investi-mentos. Assim, é esperado que uma facilidade instalada agregue uma quantidade relati-vamente elevada de capacidade ao sistema, de modo que a quantidade de facilidades queserão abertas não seja tão grande quando comparada à quantidade de locais potenciais.Nas instâncias com estas características, a quantidade de segmentos de módulos será re-duzida, diminuindo consideravelmente a quantidade de execuções do FCM em relação aodescrito nas análises de pior caso.

Considerando as BL2 e BL3, uma outra implicação do cenário descrito é que comosão heurísticas que majoritariamente não criam novos segmentos na solução, ao assumirque a quantidade de segmentos das boas soluções é próximo de um valor constante baixo,é prudente realizar estas BLs apenas em indivíduos que possuam aproximadamente estaquantidade constante. Como a BL1 deve ser capaz de lapidar soluções ruins em termosde quantidade de segmentos ativos, uma boa estratégia é utilizar esta BL antes das outrasno VND para melhorar a configuração de entrada delas. Testes para verificação da melhorordem de exploração das vizinhanças criadas serão mostrados mais adiante no trabalhono Capítulo 4.

Uma exceção para a análise anterior é quando os custos de expansão de facilidadessão de magnitude menor que os de construção do primeiro módulo, ou seja, se o efeito

3.4. OUTRAS CONSIDERAÇÕES SOBRE O AG+VNDI 47

da economia de escala for significativo na instância. Se isto for verdadeiro, e os custosde alocação não forem tão altos, as soluções tenderão a ter uma concentração de módulosem poucos locais da rede, o que aumenta a quantidade de segmentos na solução.

Todas as análises de complexidade feitas até aqui foram relacionadas a execução dasBLs separadamente. Na prática do algoritmo criado, quando uma busca local explorauma vizinhança ela deixa seu rastro na tabela hash de soluções já calculadas pelo FCM.A repetição de execuções do VND o torna mais rápido à medida em que o mapeamentodas vizinhanças vai sendo feito. No algoritmo evolucionário criado, graças ao operadorde cruzamento convergente, isto fica ainda mais evidente. Comumente serão escolhidasna rotina do VND soluções muito próximas às já exploradas, reduzindo a complexidadeda avaliação a simples recuperações de dados na tabela hash. A implicação disto é quenormalmente a primeira descida será a mais longa em termos de tempo computacional ea maior parte das demais passarão por poucas ou mesmo nenhuma execução do FCM. Osresultados dos experimentos computacionais que serão mostrados no próximo capítuloatestam estas afirmações.


Algoritmo 6 Pseudocódigo do AG+VNDi1: Inicializa parâmetros: P, α, β, R, %mut , GV ND, GR, tMAX ;2: Inicializa estruturas para armazenamento de informações: Ln(n = {1,2,3}), THASH ;3: Ler instância;4: Inicializa população: xp

0 , p = {1, . . . ,P};5: for i = 0 to P do6: if i < P/2 then7: Cria xi

0 usando HC1;8: else9: Cria xi

0 usando HC2;10: end if11: end for12: Ordena indivíduos x pela função objetivo;13: Elitismo em x0

0;14: for r = 0 to R do15: for g = 1 to GR and clock ≤ tMAX do16: Operadores do AG;17: Ordena x;18: if g % GV ND = 0∨ x0

g 6= x0g−1 then

19: p = RAND{0,α+β}∨ p = 0;20: Elitismo em xp

g ;21: end if22: if f (x0

g)< f (x0(g−1)) then

23: g = 0;24: end if25: end for26: for i = 1 to P and r < R do27: Reinício;28: p = RAND{1,P−1}29: Elitismo em xp

g ;30: end for31: end for32: return x0

Capítulo 4

Experimentos computacionais

Neste capítulo serão mostrados os experimentos realizados para demonstrar a efetivi-dade do método proposto. Para isto, foram usadas as instâncias de Jena et al. (2015a).Os experimentos foram realizados nas instâncias do problema ER-GMC do artigo ori-ginal, mas podem ser facilmente replicados ao problema CR-GMC criando as variáveisreferentes ao fechamento parcial das facilidades.

As instâncias são agrupadas pelos seus tamanhos em relação às combinações faci-lidades/clientes (10/20, 10/50, 50/50, 50/100, 50/250, 100/250, 100/500 e 100/1000) equantidade máxima de módulos por facilidade (3, 5 e 10).

Cada uma destas 24 categorias reunem 12 combinações de instâncias a partir dosparâmetros:

• Topologia da rede: três cenários onde nós são localizados em áreas quadradas detamanhos 300 x 300, 380 x 380 e 450 x 450 km;• Distribuição das demandas: dois cenários, um com a soma das demanda estável em

cada período de tempo e outro com demandas instáveis e aleatórias;• Proporção dos custos: dois cenários, um com os custos originais do problema do

estudo de caso e outro com os custos de alocação aumentados em 500%.

No total, 288 instâncias foram testadas com grafos variando de um máximo de 30 nóse 200 arestas nas menores (10/20) até 1100 nós e 100.000 arestas nas maiores (100/1000)em cada período do horizonte de planejamento.

Devido ao tamanho das instâncias, o algoritmo de fluxo a custo mínimo escolhido pararesolver o problema das alocações foi a Rede Simplex, incluso na biblioteca de otimizaçãode redes LEMON [Dezso et al. 2011, Lemon 2017]. Kovács (2015) mostrou que estemétodo desempenha melhor que os outros métodos da própria biblioteca, e até outrossolvers, em instâncias com até alguns milhares de nós.

Os experimentos foram rodados em um Intel Core i5-3337U com quatro núcleos e1,8 GHz com 8 GB de memória RAM e cada execução usou um único processador. OAG+VNDi foi implementado em C++ e compilado pelo gcc 4.8.4. Todos os testes deajustes do algoritmo foram executados nas instâncias menores (10/20, 10/50 e 50/50) eL = 10, exceto quando explicitado, sendo replicados 10 vezes cada. O tempo de execuçãofoi medido usando o tempo da CPU obtido na biblioteca time da linguagem C.

50 CAPÍTULO 4. EXPERIMENTOS COMPUTACIONAIS

4.1 Ordem de exploração das vizinhançasO primeiro conjunto de experimentos busca determinar a melhor forma de aplicar as

vizinhanças criadas para o VND. Cada teste consistiu em executar as HCs e em seguida oVND com diferentes combinações das buscas locais na melhor solução criada. A Tabela4.1 mostra os resultados das execuções de cada busca local isolada. A primeira coluna serefere a instância e as demais às BLs. O intervalo de integralidade (GAP) foi calculadocomo

GAP(x) =f (x)− f (x∗)

f (x∗). (4.1)

sendo f (x) a média das soluções obtidas ao final da busca local e f (x∗) a melhor soluçãoencontrada pelo método exato no problema.

Tabela 4.1: Resultados computacionais da aplicação de vizinhanças isoladas no VND

InstânciaBL1 BL2 BL3

GAP Tempo GAP Tempo GAP Tempo10/20 4,34% 0,03s 1,07% 0,15s 6,93% 0,13s10/50 2,01% 0,10s 0,65% 0,38s 4,14% 0,30s50/50 5,19% 1,08s 1,97% 15,42s 11,40% 7,56sMédia 3,85% 0,40s 1,23% 5,31s 7,49% 2,66s

Nota-se da Tabela 4.1 que a BL1 é a mais rápida e a BL2 a mais efetiva quando apli-cadas sozinhas. Já a BL3 é superada por ambas na qualidade da solução. Este resultado éexplicado pelas características das buscas locais e das instâncias.

A BL1 tem menor complexidade de tempo mas não executa operações de troca de mó-dulos entre facilidades de modo que quando a solução chega próxima à quantidade ótimade módulos se torna difícil efetuar operações que resultem em melhoria. Uma adição demódulos geralmente leva a um aumento de custo de localização que não seria compensadopela redução dos custos de alocação. Já uma retirada é (quase sempre) impossível devidoa pouca capacidade ociosa na solução. Isto foi evidente principalmente nas instânciascom menor custo de alocação.

O outro extremo é a BL3, onde não são feitas operações de mudanças na quantidade demódulos, apenas alterações nas localizações dos existentes. Como a HC1, mais eficaz quea HC2, gera soluções com muitos módulos abertos, a BL3 sozinha é incapaz de melhoraro resultado a partir de uma entrada ruim.

A BL2 envolve operações dos dois tipos, mudanças na quantidade e nas localizaçõesdos módulos. Isto faz com que ela seja eficaz mesmo quando aplicada sozinha. Entre-tanto, a um custo computacional mais alto que as outras.

A Tabela 4.2 mostra os resultados das execuções das BLs em pares para determinarqual é a primeira vizinhança a ser explorada mais efetiva no VND. Cada coluna mostra aexecução do VND com as duas vizinhanças na ordem apresentada.

Os resultados confirmam as justificativas dadas para os testes anteriores. A BL1 tornaa solução inicial apertada de modo que a sua execução antes das outras BLs é mais eficaz

4.1. ORDEM DE EXPLORAÇÃO DAS VIZINHANÇAS 51

Tabela 4.2: Resultados computacionais da aplicação de pares de vizinhanças no VND

InstânciaBL1→ BL2 BL1→ BL3 BL2→ BL1


InstânciaBL2→ BL3 BL3→ BL1 BL3→ BL2


que o inverso. A execução de BL2→ BL1 obtém um resultado semelhante, porém aum tempo computacional quase três vezes maior que a aplicação inversa. Portanto, avizinhança da BL1 deve ser sempre explorada antes das demais para um resultado efetivo.

Resta identificar se o impacto da exploração das três vizinhanças é mais eficaz que asimples aplicação de duas delas. A Tabela 4.3 mostra o resultado das aplicações do VNDcom as três vizinhanças, começando pela BL1.

Tabela 4.3: Resultados computacionais da aplicação das três vizinhanças no VND

InstânciaBL1→ BL2→ BL3 BL1→ BL3→ BL2GAP Tempo GAP Tempo

10/20 0,19% 0,11s 0,20% 0,12s10/50 0,05% 0,26s 0,05% 0,24s50/50 0,25% 6,88s 0,26% 6,03sMédia 0,16% 2,42s 0,17% 2,13s

Comparando os resultados nas Tabelas 4.2 e 4.3 vemos uma redução do GAP dasaplicações da BL1 seguida das BL2 e BL3 de 0,20% e 0,33%, respectivamente, para0,16% e 0,17% quando aplicadas as três buscas locais. Na comparação com a execuçãodas BLs sozinhas na Tabela 4.1 percebe-se que a exploração de múltiplas vizinhanças ébastante vantajosa para aumentar a qualidade da solução.

Com relação ao tempo de execução, pouco foi alterado mesmo acrescentando umaterceira vizinhança ao VND. A explicação para isto está no espaço de busca das duas BLsmaiores que são em grande parte semelhantes, o que torna o processo de avaliação dassoluções pouco custoso, uma vez que configurações de facilidades se repetirão frequente-mente e a avaliação pode ser feita recuperando os valores armazenados na tabela hash doFCM.

A BL2 se mostrou mais eficaz em todas os testes, mas como a BL3 é mais rápida,alternar momentos de prioridade de execução entre as duas parece ser uma estratégia


razoável para o VND no AG+VNDi. Nos testes a seguir optou-se por usar esta estratégiapara determinar a ordem de exploração das vizinhanças no VND.

4.2 Configuração dos parâmetrosDiversos parâmetros precisam ser definidos para o AG+VNDi. A quantidade de in-

divíduos em cada classe da população foi escolhida como sendo os mesmos valores deBuriol et al. (2005), sendo α = 20% e β = 75%. Resta então definir os parâmetros dequantidade de reinícios da população (R), quantidade de gerações para reinício (GR),quantidade de gerações para VND (GV ND), tamanho da população (P), e probabilidade demutação (%mut).

Os testes foram conduzidos para as seguintes combinações de valores: (i) nenhumou um reinícios da população; (ii) 100, 200 ou 300 gerações para reinício; (iii) 5, 10 ou20 gerações para executar o VND; e (iv) população com 50 ou 100 indivíduos em cadageração. A taxa de mutação foi fixada em 20%. A Tabela 4.4 mostra os resultados obtidospara as 10 execuções nas instâncias pequenas (10/20, 10/50 e 50/50). As primeiras quatrocolunas referem-se às respectivas variáveis (i), (ii), (iii) e (iv). O GAP na quinta coluna foicalculado como anteriormente, sendo comparados às soluções exatas obtidas pelo métodoexato e arredondados para duas casas decimais. O tempo na sexta coluna é a média dasmédias de tempo de execução de cada grupo de instâncias.

Tabela 4.4: Resultados computacionais da configuração dos parâmetrosR GR GV ND P GAP Tempo R GR GV ND P GAP Tempo

0

100

550 0,03% 7,15s

1

100

550 0,00% 14,57s

100 0,06% 8,68s 100 0,01% 17,39s

1050 0,07% 4,50s

1050 0,03% 9,38s

100 0,08% 5,78s 100 0,02% 11,77s

2050 0,10% 3,52s

2050 0,04% 7,13s

100 0,10% 4,34s 100 0,03% 8,79s

200

550 0,02% 9,90s

200

550 0,01% 18,81s

100 0,05% 11,82s 100 0,01% 23,31s

1050 0,04% 6,32s

1050 0,02% 12,59s

100 0,06% 7,75s 100 0,01% 15,57s

2050 0,07% 4,59s

2050 0,03% 9,34s

100 0,08% 5,83s 100 0,02% 11,74s

300

550 0,02% 12,20s

300

550 0,00% 23,52s

100 0,04% 14,82s 100 0,00% 28,31s

1050 0,03% 8,15s

1050 0,01% 15,85s

100 0,05% 9,72s 100 0,01% 18,83s

2050 0,06% 5,71s

2050 0,02% 11,20s

100 0,07% 7,17s 100 0,01% 14,00s

Na Tabela 4.4 nota-se que as configurações que geram resultados mais próximos do

4.2. CONFIGURAÇÃO DOS PARÂMETROS 53

ótimo são as que mais aplicam o VND (GV ND = 5). Entretanto, estas são as mais custosasem termos de tempo computacional. Uma forma justa de selecionar os parâmetros seriaequilibrar qualidade das soluções com tempo de execução. Na Tabela 4.5 foram separa-das as configurações dominantes, ou seja, aquelas que possuem pelo menos um dos doiscritérios melhores que as demais configurações quando comparados simultaneamente. Asconfigurações estão ordenadas pelos seus resultados.

Tabela 4.5: Combinação de parâmetros dominantesR GR GV ND P GAP Tempo1 100 5 50 0,00% 14,57s1 300 20 100 0,01% 14,00s0 200 5 50 0,02% 9,90s0 100 5 50 0,03% 7,15s0 200 10 50 0,04% 6,32s0 300 20 50 0,06% 5,71s0 100 10 50 0,07% 4,50s0 100 20 50 0,10% 3,52s

A Tabela 4.5 sugere oito combinações que podem ser utilizadas no algoritmo. A esco-lha da mais adequada depende do interesse do decisor em priorizar a obtenção de melhoressoluções ou execuções mais rápidas. No AG+VNDi, além da quantidade de reinícios e ge-rações, há um critério de parada de limite de tempo tMAX . Deste modo, podemos escolheruma configuração que priorize mais a qualidade, e quando a instância estiver demorandomais que o tempo disponível, ela seja limitada por este parâmetro. Sendo assim, os pa-râmetros utilizados daqui em diante nos experimentos serão os representados na primeiralinha da tabela.

O último parâmetro a ser ajustado é a taxa de mutação. Testes com o melhor conjuntode parâmetros definidos anteriormente foram executados para diferentes taxas de 0%, 5%e 50%. A Tabela 4.6 compara os resultados obtidos, além dos mostrados antes para umataxa de 20%.

Tabela 4.6: Resultados computacionais de ajuste da taxa de mutaçãoR GR GV ND P %mut GAP Tempo

1 100 5 50

0 0,01% 12,72s5 0,01% 13,41s

20 0,00% 14,57s50 0,01% 16,68s

A proximidade entre os resultados obtidos no ajuste da taxa de mutação leva a umaconclusão de que este parâmetro tem pouca influência na qualidade final da solução. Se-guindo o mesmo critério do ajuste anterior, manteremos a taxa de 20% uma vez que estalevou a soluções ligeiramente melhores que as demais. Em resumo, definimos os parâme-tros do AG+VNDi da seguinte forma:


• α = 0,20P e β = 0,75P;• R = 1;• GR = 100;• GV ND = 5;• P = 50;• %mut = 20.

4.3 Análise de convergência

Nas seções anteriores foram testadas as ordens de exploração das vizinhanças no VNDe definidos os parâmetros do AG+VNDi. Mas será que a metaheurística híbrida é maiseficiente que uma abordagem pura do Algoritmo Genético?

Na análise das buscas locais mostramos que a ordem de complexidade das heurísticasapresentadas, apesar de ser polinomial, pode chegar a um fator elevado. Para testar se aconvergência das soluções é mais rápida no AG com o VND, experimentos foram feitosnas instâncias menores para medir a velocidade de descendência do melhor indivíduo napopulação.

Nas sessões de testes o AG+VNDi foi executado com as configurações definidas an-teriormente para ser comparado com uma segunda configuração em que o VND é de-sativado do algoritmo original, mantendo todo o resto do algoritmo. Nesta versão, osexperimentos foram feitos com o parâmetro de quantidade de reinícios do AG definidocomo "ilimitado"e o critério de parada foi modificado para ser o tempo de execução dasinstâncias no AG+VNDi.

Na primeira sessão foi testada a convergência do melhor indivíduo das duas configu-rações em relação ao número de gerações. Como o operador de elitismo é executado logoapós a criação da população inicial, a solução no melhor indivíduo converge ainda na ge-ração 0 para GAPs relativamente baixos (abaixo de 1%). Nas execuções sem o elitismo, aconvergência por geração é lenta e, ao final das 200 gerações testadas, não alcança sequera solução encontrada pelo VND na geração 0.

Uma forma mais justa de comparar as duas configurações é através da análise de con-vergência pelo tempo de execução. A Figura 4.1 mostra a convergência da melhor solu-ção entre as duas versões da metaheurística em relação ao tempo de execução nas classes10/20, 10/50 e 50/50 de instâncias em teste, respectivamente. Os resultados mostradossão a média das médias de 10 execuções das 12 instâncias que compõem cada classe.

Na Figura 4.1 nota-se que a convergência do melhor indivíduo é mais rápida na me-taheurística híbrida desenvolvida do que no AG puro. Nas classes 10/20 e 10/50, o AGaparenta ainda não ter convergido para uma solução ótima local, ao contrário do que acon-tece na 50/50 em que o AG estabiliza a um GAP de 2,13% após 31 segundos. Este mesmoGAP é alcançado pelo AG+VNDi em média com 2,5 segundos de execução apenas.

De maneira geral, há indícios de que a busca em vizinhança proposta acelera a conver-gência da solução em relação ao ótimo global em uma magnitude de aproximadamente10 vezes.

4.4. ANÁLISE DE IMPACTO DE OUTRAS ESTRUTURAS DO ALGORITMO 55

Figura 4.1: Convergência da melhor solução por tempo de execução do AG e doAG+VNDi nas instâncias (a) 10/20, (b) 10/50 e (c) 50/50

4.4 Análise de impacto de outras estruturas do algoritmo

Ferramentas e estruturas não-convencionais foram apresentadas na descrição do algo-ritmo. Nesta seção iremos analisar algumas delas e testar seu impacto no AG+VNDi emtermos da influência na qualidade da solução final, do tempo de execução do algoritmo e,quando houver, na memória exigida pelo programa.

4.4.1 Tabela hash

A primeira das estruturas a ser analisada será a tabela hash implementada para arma-zenar as soluções obtidas pelo algoritmo de FCM ao longo da execução do algoritmo.THASH , como é aqui chamada, é uma estrutura de dados que associa uma chave, que con-tém a configuração das facilidades em um dado período de tempo, ao valor obtido peloFCM do custo ótimo das alocações. A sua utilização é possível no DFLPG graças aofato de que a determinação das alocações em cada período de tempo neste problema éindependente entre os períodos, de modo que configurações iguais num mesmo períodosempre gerarão a mesma rede de fluxo ótima.

A tabela não tem impacto algum sobre a qualidade das soluções. Ela serve como umamera recuperação de dados partindo do princípio de que esta tarefa é computacionalmente


menos custosa que a resolução de FCMs. THASH acelera a execução do algoritmo ao custode armazenamento temporário de dados na memória da máquina.

A Tabela 4.7 mostra o impacto do uso da tabela hash em relação ao tempo de execuçãototal do AG+VNDi nas três menores classes de instâncias de testes para L = 10. Os testesforam executados com as configurações do algoritmo definidas até este ponto do trabalho,mudando-se apenas a presença da tabela hash.

Tabela 4.7: Comparação do AG+VNDi com e sem uso de THASH

Instâncias Tempo c/ THASH Tempo s/ THASH10/20 0,9s 4,5s10/50 1,6s 12,1s50/50 43,2s 244,7s

Como esperado, THASH reduz consideravelmente o tempo de execução do algoritmo aum custo zero de qualidade da solução. Veremos mais adiante, na análise de complexidadedo algoritmo (Seção 4.6), que o custo de memória é muito baixo comparado ao benefícioda redução de tempo apresentado. Com isto, conclui-se que a presença da tabela hash éfundamental para melhorar a qualidade do algoritmo desenvolvido.

4.4.2 Critérios de aceitação de indivíduosNa descrição do operador de aceitação do AG+VNDi foram mostrados os quatro cri-

térios aos quais um novo indivíduo gerado deve atender para ser aceito e passado à novageração. Por questões estruturais do algoritmo, não analisaremos o primeiro deles - seruma solução viável - nesta seção, pois o AG desenvolvido depende que os indivíduospossuam um valor objetivo de aptidão para determinar a sua classe. Então, é fundamentalque todos os indivíduos criados sejam viáveis. Entretanto, os demais critérios podem seranalisados e alterados facilmente no algoritmo.

O primeiro critério analisado é o de que novos indivíduos devem ser diferentes dosvivos ou já aceitos. O objetivo principal dele é garantir uma maior diversidade de genesna população. No DFLPG, a densidade de bons indivíduos em torno de uma boa soluçãoé muito alta. De fato, a modificação de um único dentre os JT genes é suficiente para criarum indivíduo diferente do atual sem modificar tanto seu custo. Experimentos mostraramque os indivíduos que compõem a classe A de uma geração são muito parecidos entresi. Sem uma restrição que impeça indivíduos iguais de seguirem adiante nas gerações, atendência mostrada é que toda a população da classe A se torne igual à melhor solução oua poucas soluções próximas dela em poucas gerações.

A situação descrita leva às seguintes implicações. Em termos de recursos, indivíduosmuito parecidos ajudam a reduzir o tempo de execução do algoritmo, uma vez que au-mentam as chances de formarem filhos com configurações já exploradas pelo FCM. Emcompensação, considerando o operador de cruzamento implementado, uma populaçãodemasiadamente homogênea tende a gerar filhos muito parecidos, ou até iguais, aos paisem excesso, tornando mais difícil a tarefa de sair de soluções ótimas locais. Um mínimode heterogeneidade deve ser garantida para evitar isto. A Tabela 4.8 mostra os resultados

4.4. ANÁLISE DE IMPACTO DE OUTRAS ESTRUTURAS DO ALGORITMO 57

de testes feitos nas menores instâncias em termos de tempo e qualidade da solução doAG+VNDi aplicado com e sem este critério na aceitação.

Tabela 4.8: Comparação do AG+VNDi com e sem critério de aceitação de indivíduosdiferentes

InstânciasCom critério Sem critérioGAP Tempo GAP Tempo

10/20 0,01% 0,9s 0,01% 0,8s10/50 0,00% 1,6s 0,01% 1,4s50/50 0,01% 43,2s 0,02% 44,9s

Os resultados mostram uma ligeira piora na qualidade da solução quando o critério deaceitação descrito é retirado. A diferença na qualidade não é tão grande porque em ambosos testes o impacto do elitismo na qualidade é mais significante que o dos operadores doAG, sendo estes responsáveis no AG+VNDi apenas por gerar novas soluções que possamcair em novos ótimos locais no elitismo. Como a população heterogênea oferece opçõesde entrada mais diversa para o elitismo, aumenta-se a chance de geração de ótimos locaisdistantes dos conhecidos. Já em termos de tempo, não há mudança significativa nos doismétodos. Isto porque apesar de criar populações diversas, os indivíduos ainda assim sãomuito parecidos uns com os outros, o que não anula o efeito de ganho de tempo de umapopulação homogênea descrito anteriormente.

O segundo critério de aceitação a ser analisado é o de que indivíduos formados devemter custo fixo no máximo 10% maiores que os do pior indivíduo da classe A. Antes defocar no valor do parâmetro, serão descritas as vantagens e desvantagens de utilizar estabarreira na formação da população.

A principal vantagem deste critério é em termos de redução de tempo de execução.O cálculo do custo fixo de um indivíduo é feito de maneira direta apenas sabendo-seos módulos abertos nas facilidades. Assim, é possível comparar dois indivíduos pelosseus custos de localização antes mesmo de executar FCMs para determinar as alocações.Em instâncias em que os custos fixos são preponderantes, eliminar soluções que apre-sentem estes valores muito altos em relação aos das soluções já conhecidas, evita queFCMs sejam realizados em indivíduos com pouca probabilidade de terem uma boa apti-dão. Consequentemente, ao utilizar esta barreira, apenas as potencialmente boas soluçõessão passadas a fase de avaliação. O real ganho de tempo vem do fato de que soluções comcusto fixo próximo umas das outras tendem a ser soluções com configurações de facili-dades mais parecidas, e suas implicações são as mesmas de uma população homogênea.Então, em vez do algoritmo gastar tempo explorando soluções distantes das melhoresexistentes, com baixo potencial de melhoria global, ele vai direto para próximo delas.

Por outro lado, a homogeneidade aumenta a probabilidade das soluções ficarem presasem ótimos locais. Por um lado, este critério pode aumentar as chances de que ótimoslocais não tão distantes dos atuais sejam encontrados, porém os mais distantes são maisdifíceis de serem alcançados. Para avaliar se o uso do critério é mais vantajoso que a suaausência, testes foram executados nas menores instâncias e são reportados na Tabela 4.9.Nela, um cenário onde não há a aplicação deste critério é testada e comparada a outros


três cenários para um limite de aceitação de indivíduos com custos fixos de até 5%, 10%e 50% maiores que os do pior indivíduo da classe A.

Tabela 4.9: Comparação do AG+VNDi com diferentes parâmetros como critério de acei-tação de indivíduos em termos de seus custos de localização

10/20 10/50 50/50GAP Tempo GAP Tempo GAP Tempo

Até 5% 0,03% 0,9s 0,00% 1,7s 0,03% 62,2sAté 10% 0,01% 0,9s 0,00% 1,6s 0,01% 43,2sAté 50% 0,03% 1,0s 0,00% 2,0s 0,02% 45,4s

Sem critério 0,00% 1,6s 0,00% 2,8s 0,02% 58,6s

Da tabela, observa-se que não restringir as soluções nas instâncias testadas pode levara resultados de maior qualidade, mas a um custo computacional considerável. Da mesmaforma, restringir demais, como em até 5% na classe 50/50, pode fazer com que o potencialganho de tempo se perca com a dificuldade de gerar novas soluções que atendam aos cri-térios de aceitação por causa da restrição de que as soluções geradas devem ser diferentesdas existentes.

Para definir o melhor limite deve-se levar em consideração o peso dos custos de loca-lização em comparação aos de alocação na instância. Naquelas em que o primeiro é maisimportante, a tendência é que as melhores soluções sejam aquelas em que o custo fixo érelativamente baixo e, portanto, um limite mais restritivo é desejável. No segundo caso,o valor dos custos fixos tende a ser menos relevante para a aptidão do indivíduo e, então,uma restrição mais relaxada pode ser a melhor opção. No AG+VNDi testado deixaremoso limite em 10% como definido na descrição do algoritmo no capítulo anterior.

O último dos critérios de aceitação diz respeito a descartar indivíduos já processadosno histórico do VND. O objetivo deste critério é aumentar as chances de que os indivíduosescolhidos para o processo de elitismo resultem em ótimos locais desconhecidos. Assim,evita-se a perda de uma execução do elitismo que resultaria em uma solução conhecidae, possivelmente, viva na população que acabaria sendo descartada no VND. A análisedeste critério será feita a seguir em conjunto com a dos demais usos das listas que contémas soluções do VND.

4.4.3 Listas de soluções do VNDNa descrição do operador de elitismo do AG+VNDi no capítulo anterior desta disser-

tação foram apresentadas listas onde são armazenadas as soluções após cada busca emvizinhança do VND. A função destas listas é descartar soluções que já foram encontradasnuma outra busca na mesma vizinhança ao assumir que o caminho que seria percorrido apartir dela tem uma grande probabilidade de levar ao mesmo ótimo local da outra execu-ção. Com isto, o elitismo é parado imediatamente e o tempo que seria gasto percorrendoeste caminho é economizado.

Cada vizinhança possui uma lista própria indicando as soluções obtidas pelas buscasanteriormente feitas nelas. As listas foram implementadas na estrutura de dados homô-

4.5. COMPARAÇÃO COM UM MÉTODO EXATO 59

nima, e armazenam o valor da aptidão do indivíduo encontrado na busca. O seu tamanhocresce a um nível muito lento, pois apenas valores de ótimos locais são armazenados,não oferecendo ameaça alguma em condições normais de exigir uma memória elevada damáquina na atual tecnologia disponível.

Já a qualidade das soluções pode ser afetada ou não por esta estratégia. Se por umlado descartar soluções que iriam gerar ótimos locais conhecidos e substituir por novassoluções aleatórias ajuda a diversificar a população, por outro, não fazer a busca até ofinal pode fazer com que novos caminhos não percorridos não sejam encontrados, apesardesta situação ser atípica na busca (i.e. se a ordem das vizinhanças a ser exploradas fordiferente).

Foram feitos testes em que as listas foram totalmente retiradas do AG+VNDi - inclu-sive retirando o último critério do operador de aceitação do AG - para que o impacto daslistas fosse avaliado quando comparado ao seu uso. A Tabela 4.10 apresenta os resultadosem termos de qualidade e tempo das execuções do AG+VNDi com e sem as listas, e tam-bém mostra a soma da quantidade de elementos contidos nas listas das três vizinhanças

Tabela 4.10: Comparação do AG+VNDi com e sem uso de listas de soluções encontradasnas vizinhanças exploradas

InstânciasSem listas Com listas

GAP Tempo GAP Tempo Elementos em L10/20 1,0s 0,01% 0,9s 0,01% 62810/50 1,8s 0,00% 1,6s 0,00% 76150/50 45,0s 0,02% 43,2s 0,01% 1426

Os resultados dos testes mostram que o uso das listas tem um impacto aparentementepouco significativo nos resultados mas positivo. Nas três classes houve uma redução detempo pequena e em uma delas o GAP diminuiu com as listas. O baixo impacto é esperadoporque as listas apenas impedem que caminhos já percorridos os sejam novamente. Naprática, elas não evitam que FCMs sejam resolvidos, apenas interferem na execução deoutros passos no algoritmo, que, como será mostrado mais adiante no trabalho, tem poucoimpacto na ordem de complexidade do tempo de execução do AG+VNDi. Apesar disto,decidimos manter a estratégia no algoritmo final pois o custo da memória ocupada peloselementos das listas é muito baixo.

4.5 Comparação com um método exato

O objetivo desses experimentos é comparar a eficiência do método metaheurísticoAG+VNDi desenvolvido com o método exato estado da arte de Jena et al. (2015a) pararesolver o DFLPG e, assim, determinar as vantagens da heurística sobre a abordagemexata. Os resultados são mostrados para as mesmas instâncias usadas pelos autores naversão do modelo ER-GMC. Um limite de tempo de uma hora foi definida para a execuçãoda heurística.


Foi-nos dado acesso pelos autores aos resultados de cada instância dos testes originaispara uma comparação precisa entre os métodos. A comparação é feita em duas partes,sendo a primeira com os resultados que o método exato encontra o ótimo dentro de umlimite de execução de seis horas, e a outra com as instâncias que não foram resolvidasneste mesmo período. Desta forma, os resultados mostrados não são distorcidos pelo altotempo de execução das instâncias não resolvidas.

A Tabela 4.11 faz uma comparação entre o AG+VNDi e o método exato nas instânciasresolvidas até o critério de parada de aproximação da otimalidade usado em Jena et al.(2015a). Este critério consiste em considerar uma instância resolvida se o GAP entre amelhor solução viável e o melhor limitante inferior encontrados pelo CPLEX fosse de até0,01%. A primeira coluna refere-se ao número máximo de módulos L e a segunda a classedas instâncias. Em ER-GMC, a coluna #Inst mostra a quantidade de instâncias resolvidasa otimalidade em cada classe e Tempo mostra o tempo médio para a solução exata. Porfim, em AG+VNDi, a coluna GAP médio mostra o GAP médio relativo entre as soluçõesda heurística e do método exato, GAP máx o maior GAP médio entre as execuções, Tempoa média dos tempos para resolver cada instância, e +1h a quantidade de instâncias quetiveram o processo pausado no limite de uma hora de tempo definido para a heurística jáque a quantidade de reinícios da população R não está sendo atingida dentro deste limite.

Como o relógio é verificado no nível mais superior do algoritmo, em certas situações,como quando o VND está em execução, o algoritmo espera terminar a busca para poderparar o AG+VNDi, resultando em tempos maiores que os 3600s como visto nas maioresinstâncias da Tabela 4.11.

Os experimentos mostraram a estabilidade do AG+VNDi na resolução dos problemas,independentemente da quantidade máxima de módulos da instância. O tempo médio deexecução variou pouco para os três Ls testados em uma mesma classe de instâncias. Istoreforça a discussão da complexidade das buscas locais 2 e 3, mais custosas computacio-nalmente, que são pouco afetadas por esta variável nas instâncias testadas que verificama característica de que poucas facilidades são abertas apesar da grande quantidade deopções de localidades disponíveis, como é o caso destas.

O tempo gasto pelo método exato é fortemente influenciado pelo L de modo que nasinstâncias para L = 3 o método heurístico jamais é mais eficiente. No L = 5 a heurísticaé mais rápida nas instâncias até 50/50. Já para L = 10, o AG+VNDi é competitivo emtermos de tempo de execução pelo menos até as instâncias 50/250. Em relação a qualidadeda solução, a heurística chega a um GAP médio abaixo de 0,02% em 16 dos 24 conjuntosde instâncias testados, com destaque para o conjunto 10/50 que chega ao ótimo em todasas instâncias. Os únicos conjuntos em que o GAP médio reportado fica acima deste limitesão aqueles em que há parada de execução do algoritmo pelo limite de tempo de umahora, o que nos leva a pensar que para um limite de tempo maior o GAP nestas execuçõespode convergir para valores melhores.

O resultado detalhado de cada execução da Tabela 4.11 é reportado nas tabelas doApêndice A. Nelas, as instâncias são apresentadas pelos seus parâmetros. Do métodoexato são reportados o valor da melhor solução encontrada, o GAP para o limitante infe-rior quando o método foi terminado e o tempo de execução. Vale relembrar que em Jenaet al. (2015a), o método é terminado quando o limitante inferior é de no máximo 0,01%.

4.5. COMPARAÇÃO COM UM MÉTODO EXATO 61

Tabela 4.11: Resultados do AG+VNDi comparados às instâncias resolvidas a otimalidadepelo método exato de Jena et al. (2015a)

L InstânciasER-GMC AG+VNDi

#Inst Tempo GAP médio GAP máx Tempo +1h

3

10/20 12 0,3s 0,00% 0,04% 0,5s 010/50 12 0,6s 0,00% 0,00% 0,9s 050/50 12 4,3s 0,02% 0,13% 25,8s 0

50/100 12 2,6s 0,00% 0,04% 108,1s 050/250 12 6,4s 0,00% 0,03% 777,1s 0100/250 12 23,1s 0,05% 0,15% 2840,7s 6100/500 12 68,6s 0,11% 0,22% 3657,0s 12

100/1000 12 82,0s 0,70% 2,04% 3780,6s 12

5

10/20 12 1,4s 0,00% 0,01% 0,5s 010/50 12 2,5s 0,00% 0,00% 1,0s 050/50 12 611,3s 0,01% 0,07% 28,9s 0

50/100 12 13,5s 0,00% 0,05% 115,5s 050/250 12 19,4s 0,00% 0,01% 687,1s 0100/250 12 58,9s 0,04% 0,11% 2790,7s 6100/500 12 158,4s 0,09% 0,25% 3661,0s 12

100/1000 12 197,8s 0,90% 3,05% 3745,0s 12

10

10/20 12 1337,3s 0,01% 0,07% 0,9s 010/50 9 1939,3s 0,00% 0,00% 1,6s 050/50 10 1251,8s 0,01% 0,03% 43,2s 0

50/100 10 260,2s 0,02% 0,07% 112,0s 050/250 12 2924,9s 0,00% 0,03% 528,1s 0100/250 11 512,7s 0,03% 0,08% 2881,4s 5100/500 11 3214,1s 0,08% 0,20% 3592,7s 9

100/1000 12 670,3s 0,67% 3,41% 3769,2s 12

Desta forma, nas instâncias com GAP maior que zero podem haver soluções melhores queas reportadas que sejam viáveis para o problema, como na instância 50/100, nw2, RND,500 para L = 5, em que as 10 execuções encontraram uma solução melhor que o métodoexato, resultando num gap negativo no AG+VNDi. Por fim, são reportados o GAP médiodas melhores soluções encontradas pelo AG+VNDi nas 10 execuções em relação a solu-ção do GMC, o tempo total médio de execução da heurística e a quantidade de execuçõesem que a instância encontrou uma solução igual ou melhor que a do GMC.

Das tabelas no apêndice, nota-se a rapidez do AG+VNDi nas instâncias com maiorproporção de custos de localização sobre custos de alocação. Para L = 3 e 5, a partir dasinstâncias 50/50 a diferença entre os tempos de execução nas instâncias com os custos dealocação quintuplicadas chega a ser quase cinco vezes maior que com os custos originais.Quando L = 10, a diferença de tempo diminui uma vez que nas instâncias testadas as ca-pacidades dos módulos diminuem de tamanho consideravelmente nestas instâncias, o queincentiva o modelo a construir mais módulos para atender as demandas. Já foi mostrado


que nos casos onde há mais módulos construídos a complexidade das buscas é maior.A Tabela 4.12 apresenta os resultados do AG+VNDi nas instâncias não resolvidas até

a otimalidade pelo algoritmo exato de Jena et al. (2015a). O tempo máximo de execuçãonestas instâncias foi ajustado para coincidir com o utilizado no trabalho original de seishoras. Os resultados são mostrados para cada instância separadamente.

A tabela mostra que seis das nove instâncias testadas não puderam ser resolvidas atéo limite de tempo de 21600 segundos devido à limitação de memória da máquina detestes. Isto acontece devido a quantidade de informações que são armazenadas na tabelahash com os resultados do FCM. Por isto, na Tabela 4.12 também é reportado o tamanhofinal médio da tabela hash ao fim das execuções, em milhões de chaves armazenadas.Objetivamente, o critério de parada foi definido como sendo quando a memória livredisponível atinge 0,02% da memória total da máquina.

Tabela 4.12: Comparação entre o AG+VNDi e o método de Jena et al. (2015a) nas ins-tância não-resolvidas a otimalidade pelo método exato

InstânciaAG+VNDi

GAP Tempo Tamanho THASH10,10/50,nw2,CONS,100 0,00% 21600s 13,7 mi10,10/50,nw2,CONS,500 0,00% 8186s 20,4 mi10,10/50,nw2,RND,100 0,00% 4849s 25,4 mi

10,50/50,nw1,CONS,100 -0,03% 2156s 17,1 mi10,50/50,nw1,RND,100 0,00% 2425s 17,0 mi

10,50/100,nw1,CONS,100 0,00% 4333s 16,9 mi10,50/100,nw1,RND,100 0,00% 4856s 16,3 mi

10,100/250,nw3,RND,100 0,00% 21600s 14,4 mi10,100/500,nw3,CONS,100 0,00% 21600s 4,9 mi

Da tabela anterior, nota-se que o estouro da memória de 8 GB disponível na máquinade testes acontece quando o tamanho da tabela hash está aproximadamente entre 20 e 25milhões de chaves nas instâncias testadas de tamanho 10/50 e entre 16 e 17 milhões nasinstâncias 50/50 e 50/100. A diferença entre estes valores se dá pelo tamanho da chaveguardada na tabela que é representada por um vetor de tamanho diretamente proporcionala quantidade de potenciais locais J para instalação das facilidades.

De acordo com os testes executados nesta seção, vimos que o AG+VNDi pode exi-gir uma quantidade de recursos computacionais (tempo e memória) que nem sempre osdecisores tem a sua disposição. A próxima seção será dedicada a realizar uma análisedetalhada sobre como estes recursos são utilizados pelo algoritmo através da definição dacomplexidade geral do algoritmo.

4.6 Análise de complexidade do algoritmoComo mostrado anteriormente, o uso da tabela hash acelera significativamente o tempo

de execução do algoritmo ao evitar que o FCM seja executado novamente para configu-

4.6. ANÁLISE DE COMPLEXIDADE DO ALGORITMO 63

rações de soluções que já tenham sido exploradas. Consequentemente, pode-se inferirque a quantidade de execuções do FCM é o fator que define a ordem de complexidade dotempo total de execução do algoritmo, além, é claro, da própria complexidade do FCM.Na descrição das buscas locais foram feitas análises indivíduais das complexidades dasbuscas, que são as estruturas do AG+VNDi que mais requerem o cálculo de FCMs nostestes realizados. A análise de complexidade geral do algoritmo foi deixada de lado paraque esta pudesse ser avaliada através dos experimentos computacionais, uma vez que ainfluência da tabela hash torna demasiadamente complexa a sua análise teórica.

Além do tempo de execução, um outro recurso que pode haver uma limitação de dis-ponibilidade para o decisor é a memória da máquina onde o algoritmo é executado. Naseção anterior foram mostrados alguns casos onde o espaço disponível não foi suficientepara atender os requisitos dos testes. Então, assim como é necessário discutir sobre a com-plexidade de tempo do AG+VNDi, também será feita uma breve análise de complexidadede espaço.

Das execuções da seção anterior (Tabela 4.11) foram coletados dados para avaliarobjetivamente qual o impacto do FCM na complexidade geral do AG+VNDi. Aqui serãoconsiderados apenas as execuções referentes ao L = 10, uma vez que a complexidadeé independente do tamanho de L, e nas classes de instâncias que não tiveram nenhumainstância limitada pelo tMAX . A Tabela 4.13 mostra os tempos médio de execução de cadaclasse como já mostrado anteriormente, e apresenta dois novos dados das respectivasclasses. Na coluna Tamanho THASH é mostrado o tamanho médio da tabela hash ao finalda execução do algoritmo em quantidade de chaves armazenadas, e em % tempo FCM aporcentagem de tempo, em média, que o algoritmo gasta montando o grafo e resolvendoos FCMs em relação ao tempo total mostrado na coluna Tempo.

Tabela 4.13: Tamanho da tabela hash ao final da execução do AG+VNDiL Instâncias Tamanho THASH Tempo % tempo FCM

10

10/20 19360 0,9s 56,8%10/50 20666 1,6s 75,1%50/50 308981 43,2s 84,2%

50/100 314648 112,0s 92,7%50/250 397206 528,1s 97,5%

Os dados da Tabela 4.13 mostram como a influência do FCM aumenta a medida emque o tamanho das instâncias aumenta. Nas instâncias menores, o tempo gasto nas demaisestruturas do AG+VNDi ainda tem uma certa influência no total. Porém, o tempo dasoperações destas estruturas cresce numa proporção muito menor que o tempo do FCM,chegando ao ponto de terem uma participação abaixo dos 3% do tempo total nas instâncias50/250. Portanto, para instâncias maiores, uma melhoria significativa de tempo só seriaalcançada através de mudanças estruturais do método, de modo a encontrar boas soluções,como as que já estão sendo encontradas, executando menos vezes o algoritmo de FCM.

Confirmado, então, que a complexidade de tempo do AG+VNDi é influenciada pelaordem da quantidade de execuções do FCM, resta saber como que os parâmetros dasinstâncias influenciam nisto. Na descrição do FCM foi mostrado que a complexidade


dos algoritmos para resolver este problema é dependente do tamanho da rede, ou seja,a quantidade de nós e arcos. De fato, na Tabela 4.13 vemos que as instâncias 50/100utilizaram o algoritmo de FCM (representado pelo tamanho da tabela hash) menos de 2%de vezes a mais que as 50/50, mas o tempo de execução é 160% maior. Similarmente, asinstâncias 50/250 realizaram 26% mais FCMs que as 50/100 e o tempo foi 370% maior.A diferença entre estas classes de instâncias é apenas a quantidade I de clientes, que é100% maior no primeiro caso e 150% no segundo.

Já um aumento na quantidade J de possíveis locais para instalação das facilidadestem um impacto significativamente maior que I no tempo. Isto porque um aumento deJ influencia tanto na complexidade do FCM (aumentando o número de nós e arcos narede) quanto da quantidade de execuções do FCM (aumentando as vizinhanças das buscaslocais). Na comparação com a classe 10/50, a 50/50 realiza quase 14 vezes mais FCMs egasta um tempo total 26 vezes maior. Voltando à tabela de comparação do AG+VNDi como método exato (Tabela 4.11), ao dobrar J entre as instâncias 50/250 e 100/250, vemosque o tempo aumenta a uma taxa bem maior, mesmo considerando que várias das últimasinstâncias foram limitadas pelo tMAX .

Um outro ponto importante para compreender melhor a complexidade do algoritmo éverificar a taxa de evolução do tamanho da tabela hash ao longo da execução do AG+VNDi.Para isto, informações referentes ao tamanho de THAHS foram extraídas das execuções dasclasses 10/20, 10/50 e 50/50. Os gráficos da Figura 4.2 mostram a relação do tamanhomédio da tabela e a quantidade de elitismos executados nas instâncias das três classes.Dois cenários diferentes foram testados. O primeiro (linha azul) mostra os resultados doalgoritmo original, enquanto o segundo (linha vermelha) mostra os do algoritmo com aestratégia de reinício da população desativada. Em todos os testes, a quantidade máximade gerações foi limitada a 200 gerações.

Figura 4.2: Crescimento do tamanho da tabela hash

Em todas as execuções, o comportamento do crescimento da tabela hash mostrado naFigura 4.2 é semelhante. Há um crescimento exponencial nos primeiros elitismos, quandoo algoritmo precisa varrer vizinhanças completamente desconhecidas, que passa a serlinear a medida em que o algoritmo avança. Um salto é dado no meio da execução quandoo reinício da população é feito, justamente porque os elitismos realizados após o reinícioexploram vizinhanças de soluções novas e, normalmente, distantes das já exploradas.

4.6. ANÁLISE DE COMPLEXIDADE DO ALGORITMO 65

Mas, mesmo quando há reinício, o comportamento da curva não é alterado - crescimentoexponencial no início e linear com o passar das gerações.

A linearidade da segunda parte da curva é explicada pelo critério de aceitação de indi-víduos no Algoritmo Genético desenvolvido que força para que haja uma quantidade deindivíduos novos gerados igual ao tamanho da população P. Este critério faz cada geraçãocriar uma quantidade pequena e aproximadamente semelhante de novas configurações defacilidades que ainda não foram exploradas. Então, a linearidade se sobressai em relaçãoàs novas execuções do elitismo porque como após algumas gerações a população se tornabastante homogênea, as buscas locais varrem poucas, ou até nenhuma, nova configuraçãode facilidades. O gráfico da Figura 4.3 confirma esta análise. Nele, são mostradas a quan-tidade de novas chaves que são adicionadas à tabela hash em cada geração das instâncias10/20. A maioria dos picos acontecem nas gerações onde houve um elitismo. Porém,estes tendem a ficar menores com o passar das gerações.

Figura 4.3: Quantidade de novas chaves adicionadas a THASH em cada geração

Se o tamanho da tabela hash cresce linearmente com o passar das gerações graças aooperador de aceitação sempre gerar P novos indivíduos, então pode-se inferir que o tama-nho da população também tenha influência na complexidade de espaço do algoritmo. AFigura 4.4 mostra um gráfico similar ao da Figura 4.2 para comprovar a influência de P nataxa de crescimento da tabela hash mostrando as curvas de quatro diferentes configuraçõestestadas também nas instâncias 10/20. Repare que o crescimento do tamanho da tabelahash é acentuado apenas aumentando P logo nas primeiras gerações após a execução doprimeiro elitismo.

Conclui-se desta seção que a complexidade de tempo do AG+VNDi é resultante dacombinação da complexidade do método utilizado para resolver os problemas de fluxo acusto mínimo com a complexidade de espaço do algoritmo. No primeiro caso, os princi-pais fatores são I e J, que influenciam na quantidade de nós e arcos da rede. No segundo,os mais influentes são os parâmetros P, R e GR, sendo os dois últimos os parâmetros que


Figura 4.4: Variação em P da quantidade de chaves em THASH

definirão a quantidade total de gerações na busca. O tamanho T do horizonte de plane-jamento também tem influência na complexidade de espaço já que as configurações sãoarmazenadas na tabela hash para cada período de tempo. Curiosamente, o tamanho dasvizinhanças das buscas locais, fortemente influenciadas por J, só deve ser considerado nacomplexidade de espaço do algoritmo se atrelado à quantidade R de reinícios da popula-ção. Se GR for grande o suficiente em relação a R, como nos testes em que houve estourode memória da Tabela 4.12, a influência de P é maior que a das buscas locais no tamanhototal da tabela hash. Nos demais testes, quando GR não é tão grande, as buscas locais pos-suem uma influência maior que P, dando a falsa impressão de que as vizinhanças definema complexidade do algoritmo.

Os experimentos mostraram resultados que ilustram a competitividade do AG+VNDiperante um método exato estado da arte para o DFLPG. Em resumo, a aplicação das trêsbuscas locais propostas numa rotina de VND é uma ferramenta poderosa para a resoluçãodo problema. Além disto, o VND no algoritmo permite uma convergência mais rápida emelhor para soluções próximas do ótimo que o AG puro. As Tabelas 4.11 e 4.12 mos-traram que na média o AG+VNDi alcança resultados muito próximos da melhor soluçãoencontrada pelo método exato em todas as classes de instâncias de tamanho até 50/250.Nas instâncias maiores, o GAP cresce devido a interrupção do método pelo limite detempo de uma hora.

Assim como ocorre nas vizinhanças semelhantes às propostas quando aplicadas a ou-tros FLPs, a complexidade das buscas locais pode ser grande demais em certas situaçõescomo, por exemplo, quando a quantidade de módulos máximo por facilidade seja pe-quena. Os testes mostraram que quanto maior o L, menor a quantidade de facilidades eclientes e maior o peso dos custos de localização na instância, maior a chance da heurísticaproposta ser mais eficiente para resolver o DFLPG que o método exato.

Capítulo 5

Considerações Finais

Esta dissertação propôs uma metaheurística híbrida de um Algoritmo Genético comuma Descida em Vizinhança Variável para o Problema Dinâmico de Localização de Faci-lidades com Capacidade Modulares apresentado por Jena et al. (2015a).

O problema consiste em localizar facilidades e dimensionar suas capacidades de formaa atender demandas previamente conhecidas em um horizonte de tempo finito. Decisõesde localização são tomadas periodicamente, onde são possíveis a abertura ou fechamentoda facilidade e expansão ou redução de sua capacidade. Além disto, o problema per-mite a representação de estruturas de custos complexas, o que torna possível uma melhormodelagem de problemas reais.

O DFLPG é uma generalização de vários problemas da literatura de FLPs. É um pro-blema da classe NP-difícil e, consequentemente, pode ter uma abordagem exata inviávelem certas condições, como quando o tamanho da instância seja grande. Um outro desafioé saber lidar com os dados do problema. Como se trata de um problema dinâmico, elelida com previsões futuras de demandas e custos muitas vezes difíceis de serem estima-dos precisamente, de modo que uma solução aproximada tenha o mesmo valor práticoque soluções ótimas.

A resolução do problema pelo algoritmo proposto foi dividida em duas partes, se-guindo a lógica utilizada em problemas capacitados e com alocações múltiplas. Inicial-mente são determinadas as facilidades e os modulos abertos na rede através dos operado-res do algoritmo. Somente após conhecidas as localizações é que são feitas as alocaçõesatravés de um algoritmo de fluxo a custo mínimo.

A rotina de VND do método desenvolvido, chamado de AG+VNDi, adapta operadorese vizinhanças existentes para outros problemas de localização para determinar as localiza-ções e dimensões das facilidades em cada período de tempo. Dentre diversas operações debusca possíveis, três vizinhanças foram criadas de forma a mesclar as vantagens de cadauma das características destas operações. Uma das vizinhanças faz buscas por soluçõesapenas com decisões de abertura e fechamento de módulos e outra apenas com desloca-mento de módulos. A terceira mistura parte das duas vizinhanças ao efetuar operaçõesdos dois tipos simultaneamente.

Apesar de efetivo, o VND é determinístico. Uma estrutura do AG foi utilizada paraescapar dos ótimos locais encontrados pela busca em vizinhança. O AG apresentado pos-sui os operadores clássicos de seleção, cruzamento, mutação e aceitação de indivíduos

68 CAPÍTULO 5. CONSIDERAÇÕES FINAIS

que formam uma população com soluções viáveis para o problema. O VND é executadocomo rotina do AG melhorando soluções que fazem parte das classes alta e média dapopulação. Um último operador ainda foi desenvolvido de modo a reiniciar a popula-ção existente após uma quantidade de iterações que torne a população demasiadamenteheterogênea.

Os experimentos mostraram a eficiência do algoritmo híbrido frente a abordagens pu-ras dos métodos heurísticos. A convergência do AG+VNDi é cerca de 10 vezes maisrápida que o uso do AG sem busca em vizinhança e estabiliza em um resultado melhorque o AG puro. Além disto, o uso das três vizinhanças de forma conjunta gerou resulta-dos melhores que a aplicação das buscas locais isoladas ou em pares. Outras ferramentasusadas na heurística foram postas a prova e tiveram suas eficiências mensuradas, comouma tabela hash para armazenar soluções do FCM, os critérios de aceitação dos indiví-duos formados no AG e listas que armazenam as soluções aprimorantes obtidas em cadavizinhança do VND.

Na comparação com o método exato usado no trabalho que apresentou o problema,o AG+VNDi se mostrou competitivo nas instâncias em que a quantidade de módulosque podem ser localizados em cada facilidade é maior. A distância entre as soluçõesheurísticas e exatas ficou até 0,02% na média em mais de 60% das classes de instânciastestadas, chegando a uma solução pelo menos igual à melhor solução do método exato namaioria delas dentro do intervalo de tempo de uma hora de testes para cada instância. Nasclasses de instâncias maiores, o método foi interrompido quase sempre pela barreira detempo máximo de execução, mas, devido à convergência rápida do VND, o GAP fica namédia abaixo de 1% em todas elas.

Os resultados comprovaram que em instâncias com dados reais a complexidade dasbuscas pode ser bem menor que no pior caso devido à baixa quantidade relativa de mó-dulos abertos nos casos em que os custos de localização são mais altos. O tempo deexecução do AG+VNDi nas instâncias com os custos de alocação originais foi até cincovezes menor que nas instâncias com os custos de alocação quintuplicados.

Vizinhanças parecidas com as exploradas no DFLPG já haviam se mostrado serem efi-cazes em vários problemas de localização de facilidades e neste não foi diferente. Apesarda alta ordem de complexidade como algoritmo aproximativo, estas buscas locais podemser bem aproveitadas em certas ocasiões, principalmente em aplicações logísticas reaisonde custos de localização são relativamente altos. O método é flexível o suficiente paraser aplicado em vários outros problemas das classes dinâmica e modular dos FLPs. Emúltima instância, podem ainda ser adaptados a estruturas especializadas na exploração devizinhanças, como o VNS, para que possam melhorar ainda mais a eficiência da busca.

Referências Bibliográficas

Addis, Bernardetta, Giuliana Carello & Alberto Ceselli (2012), ‘Exactly solving a two-level location problem with modular node capacities’, Networks 59(1), 161–180.

Agar, MC & Said Salhi (1998), ‘Lagrangean heuristics applied to a variety of large ca-pacitated plant location problems’, Journal of the Operational Research Societypp. 1072–1084.

Ahuja, Ravindra K, Thomas L Magnanti & James B Orlin (1993), Network flows: theory,algorithms, and applications, Prentice Hall.

An, Hyung-Chan, Mohit Singh & Ola Svensson (2017), ‘Lp-based algorithms for capaci-tated facility location’, SIAM Journal on Computing 46(1), 272–306.

Antunes, António & Dominique Peeters (2001), ‘On solving complex multi-period loca-tion models using simulated annealing’, European Journal of Operational Research130(1), 190–201.

Arabani, Alireza Boloori & Reza Zanjirani Farahani (2012), ‘Facility location dynamics:An overview of classifications and applications’, Computers & Industrial Enginee-ring 62(1), 408–420.

Arostegui, Marvin A, Sukran N Kadipasaoglu & Basheer M Khumawala (2006), ‘Anempirical comparison of tabu search, simulated annealing, and genetic algorithmsfor facilities location problems’, International Journal of Production Economics103(2), 742–754.

Arya, Vijay, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala &Vinayaka Pandit (2004), ‘Local search heuristics for k-median and facility locationproblems’, SIAM Journal on computing 33(3), 544–562.

Balinski, Michel Louis (1965), ‘Integer programming: methods, uses, computations’,Management Science 12(3), 253–313.

Ballou, Ronald H (1968), ‘Dynamic warehouse location analysis’, Journal of MarketingResearch pp. 271–276.

Basu, Sumanta, Megha Sharma & Partha Sarathi Ghosh (2015), ‘Metaheuristic applicati-ons on discrete facility location problems: a survey’, Opsearch 52(3), 530–561.

69

70 REFERÊNCIAS BIBLIOGRÁFICAS

Blum, Christian & Andrea Roli (2003), ‘Metaheuristics in combinatorial optimiza-tion: Overview and conceptual comparison’, ACM Computing Surveys (CSUR)35(3), 268–308.

Blum, Christian, Jakob Puchinger, Günther R Raidl & Andrea Roli (2011), ‘Hybridmetaheuristics in combinatorial optimization: A survey’, Applied Soft Computing11(6), 4135–4151.

Brotcorne, Luce, Gilbert Laporte & Frederic Semet (2003), ‘Ambulance location andrelocation models’, European journal of operational research 147(3), 451–463.

Buriol, Luciana S, Mauricio GC Resende, Celso C Ribeiro & Mikkel Thorup (2005),‘A hybrid genetic algorithm for the weight setting problem in ospf/is-is routing’,Networks 46(1), 36–56.

Byrka, Jaroslaw & Karen Aardal (2010), ‘An optimal bifactor approximation algorithmfor the metric uncapacitated facility location problem’, SIAM Journal on Computing39(6), 2212–2231.

Canel, Cem, Basheer M Khumawala, Japhett Law & Anthony Loh (2001), ‘An algorithmfor the capacitated, multi-commodity multi-period facility location problem’, Com-puters & Operations Research 28(5), 411–427.

Chardaire, Pierre, Alain Sutter & Marie-Christine Costa (1996), ‘Solving the dynamicfacility location problem’, Networks 28(2), 117–124.

Charikar, Moses & Sudipto Guha (1999), Improved combinatorial algorithms for the faci-lity location and k-median problems, em ‘Foundations of Computer Science, 1999.40th Annual Symposium on’, IEEE, pp. 378–388.

Chudak, Fabián A & David P Williamson (1999), Improved approximation algorithmsfor capacitated facility location problems, em ‘International Conference on IntegerProgramming and Combinatorial Optimization’, Springer, pp. 99–113.

Cornuéjols, Gérard, George L Nemhauser & Lairemce A Wolsey (1983), The uncapaci-tated facility location problem, Relat tico, DTIC Document.

Cornuéjols, Gérard, Ranjani Sridharan & Jean-Michel Thizy (1991), ‘A comparison ofheuristics and relaxations for the capacitated plant location problem’, Europeanjournal of operational research 50(3), 280–297.

Correia, Isabel & M Eugénia Captivo (2003), ‘A lagrangean heuristic for a modular capa-citated location problem’, Annals of operations research 122(1-4), 141–161.

Daskin, Mark S (2008), ‘What you should know about location modeling’, Naval Rese-arch Logistics (NRL) 55(4), 283–294.

Davis, PS & TL Ray (1969), ‘A branch-bound algorithm for the capacitated facilitieslocation problem’, Naval Research Logistics (NRL) 16(3), 331–344.

REFERÊNCIAS BIBLIOGRÁFICAS 71

Delmaire, Hugues, Juan A Díaz, Elena Fernández & Maruja Ortega (1999), ‘Reactivegrasp and tabu search based heuristics for the single source capacitated plant locationproblem’, INFOR: Information Systems and Operational Research 37(3), 194–225.

Dezso, Balázs, Alpár Jüttner & Péter Kovács (2011), ‘Lemon–an open source c++ graphtemplate library’, Electronic Notes in Theoretical Computer Science 264(5), 23–45.

Dias, Joana, M Eugénia Captivo & João Clímaco (2007), ‘Dynamic location problemswith discrete expansion and reduction sizes of available capacities’, InvestigaçãoOperacional 27(2), 107–130.

Drezner, Zvi & Horst W Hamacher (2001), Facility location: applications and theory,Springer Science & Business Media.

Drezner, Zvi, Kathrin Klamroth, Anita Schöbel & George O Wesolowsky (2002), ‘1 theweber problem’.

Ericsson, M, Mauricio GC Resende & Panos M Pardalos (2002), ‘A genetic algorithm forthe weight setting problem in ospf routing’, Journal of combinatorial optimization6(3), 299–333.

Farahani, Reza Zanjirani & Masoud Hekmatfar (2009), Facility Location: Concepts, Mo-dels, Algorithms and Case Studies, Physica-Verlag Heidelberg.

Farahani, Reza Zanjirani, Nasrin Asgari, Nooshin Heidari, Mahtab Hosseininia & MarkGoh (2012), ‘Covering problems in facility location: A review’, Computers & In-dustrial Engineering 62(1), 368–407.

Feldman, EFATL, FA Lehrer & TL Ray (1966), ‘Warehouse location under continuouseconomies of scale’, Management Science 12(9), 670–684.

Fernandes, Diogo RM, Caroline Rocha, Daniel Aloise, Glaydston M Ribeiro, Enilson MSantos & Allyson Silva (2014), ‘A simple and effective genetic algorithm for thetwo-stage capacitated facility location problem’, Computers & Industrial Enginee-ring 75, 200–208.

Gendreau, Michel & Jean-Yves Potvin (2005), ‘Metaheuristics in combinatorial optimi-zation’, Annals of Operations Research 140(1), 189–213.

Goldberg, David E & John H Holland (1988), ‘Genetic algorithms and machine learning’,Machine learning 3(2), 95–99.

Gouveia, Luís & Francisco Saldanha-da Gama (2006), ‘On the capacitated concentra-tor location problem: a reformulation by discretization’, Computers & operationsresearch 33(5), 1242–1258.

Guha, Sudipto & Samir Khuller (1999), ‘Greedy strikes back: Improved facility locationalgorithms’, Journal of algorithms 31(1), 228–248.


Hakimi, S Louis (1964), ‘Optimum locations of switching centers and the absolute centersand medians of a graph’, Operations research 12(3), 450–459.

Hansen, Pierre & Nenad Mladenovic (2001), ‘Variable neighborhood search: Principlesand applications’, European journal of operational research 130(3), 449–467.

Harkness, Joseph & Charles ReVelle (2003), ‘Facility location with increasing productioncosts’, European Journal of Operational Research 145(1), 1–13.

Hinojosa, Yolanda, Jörg Kalcsics, Stefan Nickel, Justo Puerto & Sebastian Velten (2008),‘Dynamic supply chain design with inventory’, Computers & Operations Research35(2), 373–391.

Holland, John H (1975), ‘Adaptation in natural and artificial systems: An introductoryanalysis with applications to biology, control, and artificial intelligence.’.

Hollstien, Roy Bruce (1971), Artificial genetic adaptation in computer control systems,Tese de doutorado, PhD thesis, University of Michigan.

Jaillet, Patrick, Gao Song & Gang Yu (1996), ‘Airline network design and hub locationproblems’, Location science 4(3), 195–212.

Jena, Sanjay Dominik, Jean-François Cordeau & Bernard Gendron (2014), Lagrangianheuristics for large-scale dynamic facility location with generalized modular capa-cities, Relat tico, CIRRELT-2014-21, Centre interuniversitaire de recherche sur lesreseaux dentreprise, la logistique et le transport.

Jena, Sanjay Dominik, Jean-François Cordeau & Bernard Gendron (2015a), ‘Dyna-mic facility location with generalized modular capacities’, Transportation Science49(3), 484–499.

Jena, Sanjay Dominik, Jean-François Cordeau & Bernard Gendron (2015b), ‘Modelingand solving a logging camp location problem’, Annals of Operations Research232(1), 151–177.

Jena, Sanjay Dominik, Jean-François Cordeau & Bernard Gendron (2016), ‘Solving adynamic facility location problem with partial closing and reopening’, Computers& Operations Research 67, 143–154.

Kariv, Oded & S Louis Hakimi (1979), ‘An algorithmic approach to network locationproblems. ii: The p-medians’, SIAM Journal on Applied Mathematics 37(3), 539–560.

Klose, Andreas & Andreas Drexl (2005), ‘Facility location models for distribution systemdesign’, European Journal of Operational Research 162(1), 4–29.

Klose, Andreas & Simon Görtz (2007), ‘A branch-and-price algorithm for the capacitatedfacility location problem’, European Journal of Operational Research 179(3), 1109–1125.


Ko, Hyun Jeung & Gerald W Evans (2007), ‘A genetic algorithm-based heuristic forthe dynamic integrated forward/reverse logistics network for 3pls’, Computers &Operations Research 34(2), 346–366.

Korupolu, Madhukar R, C Greg Plaxton & Rajmohan Rajaraman (2000), ‘Analysis of a lo-cal search heuristic for facility location problems’, Journal of algorithms 37(1), 146–188.

Kovács, Péter (2015), ‘Minimum-cost flow algorithms: an experimental evaluation’, Op-timization Methods and Software 30(1), 94–127.

Krarup, Jakob & Peter Mark Pruzan (1983), ‘The simple plant location problem: surveyand synthesis’, European Journal of Operational Research 12(1), 36–81.

Kuehn, Alfred A & Michael J Hamburger (1963), ‘A heuristic program for locating wa-rehouses’, Management science 9(4), 643–666.

Laporte, Gilbert, Stefan Nickel & F Saldanha da Gama (2015), Location science, Vol.145, Springer.

Lee, Der-Horng & Meng Dong (2008), ‘A heuristic approach to logistics network de-sign for end-of-lease computer products recovery’, Transportation Research Part E:Logistics and Transportation Review 44(3), 455–474.

Lemon (2017), ‘Lemon - library for efficient modeling and optimization networks’.URL: http://lemon.cs.elte.hu/trac/lemon

Lu, Da, Fatma Gzara & Samir Elhedhli (2014), ‘Facility location with economies anddiseconomies of scale: models and column generation heuristics’, IIE Transactions46(6), 585–600.

Mahdian, Mohammad & Martin Pál (2003), Universal facility location, em ‘EuropeanSymposium on Algorithms’, Springer, pp. 409–421.

Melo, M Teresa, Stefan Nickel & F Saldanha Da Gama (2006), ‘Dynamic multi-commodity capacitated facility location: a mathematical modeling framework forstrategic supply chain planning’, Computers & Operations Research 33(1), 181–208.

Melo, M Teresa, Stefan Nickel & Francisco Saldanha-Da-Gama (2009), ‘Facility locationand supply chain management–a review’, European journal of operational research196(2), 401–412.

Mladenovic, Nenad, Jack Brimberg, Pierre Hansen & José A Moreno-Pérez (2007), ‘Thep-median problem: A survey of metaheuristic approaches’, European Journal ofOperational Research 179(3), 927–939.


Moscato, Pablo & Michael G Norman (1992), ‘A memetic approach for the traveling sa-lesman problem implementation of a computational ecology for combinatorial opti-mization on message-passing systems’, Parallel computing and transputer applica-tions 1, 177–186.

Nickel, Stefan & Francisco Saldanha da Gama (2015), Multi-period facility location, em‘Location Science’, Springer, pp. 289–310.

Osman, Ibrahim H & Gilbert Laporte (1996), ‘Metaheuristics: A bibliography’, Annalsof Operations Research 63, 513–628.

Owen, Susan Hesse & Mark S Daskin (1998), ‘Strategic facility location: A review’,European Journal of Operational Research 111(3), 423–447.

Rahmani, A & SA MirHassani (2014), ‘A hybrid firefly-genetic algorithm for the capaci-tated facility location problem’, Information Sciences 283, 70–78.

Revelle, Charles S & Horst A Eiselt (2005), ‘Location analysis: A synthesis and survey’,European Journal of Operational Research 165(1), 1–19.

Revelle, Charles S, Horst A Eiselt & Mark S Daskin (2008), ‘A bibliography for somefundamental problem categories in discrete location science’, European Journal ofOperational Research 184(3), 817–848.

Sá, Graciano (1969), ‘Branch-and-bound and approximate solutions to the capacitatedplant-location problem’, Operations Research 17(6), 1005–1016.

Shmoys, David B, Éva Tardos & Karen Aardal (1997), Approximation algorithms forfacility location problems, em ‘Proceedings of the twenty-ninth annual ACM sym-posium on Theory of computing’, ACM, pp. 265–274.

Shulman, Alexander (1991), ‘An algorithm for solving dynamic capacitated plant locationproblems with discrete expansion sizes’, Operations research 39(3), 423–436.

Smith, Honora K, Gilbert Laporte & Paul Robert Harper (2009), ‘Locational analysis:highlights of growth to maturity’, Journal of the Operational Research Societypp. s140–s148.

Sridharan, Ramaswami (1995), ‘The capacitated plant location problem’, European Jour-nal of Operational Research 87(2), 203–213.

Sweeney, Dennis J & Ronad L Tatham (1976), ‘An improved long-run model for multiplewarehouse location’, Management Science 22(7), 748–758.

Talbi, E-G (2002), ‘A taxonomy of hybrid metaheuristics’, Journal of heuristics8(5), 541–564.

Troncoso, Juan J & Rodrigo A Garrido (2005), ‘Forestry production and logistics plan-ning: an analysis using mixed-integer programming’, Forest Policy and Economics7(4), 625–633.


Ulstein, Nina Linn, Marielle Christiansen, Roar Grønhaug, Nick Magnussen & Marius MSolomon (2006), ‘Elkem uses optimization in redesigning its supply chain’, Interfa-ces 36(4), 314–325.

Van Ommeren, JCW, Adriana Felicia Bumb & AV Sleptchenko (2006), ‘Locating repairshops in a stochastic environment’, Computers & Operations Research 33(6), 1575–1594.

Van Roy, Tony J & Donald Erlenkotter (1982), ‘A dual-based procedure for dynamicfacility location’, Management Science 28(10), 1091–1105.

Verter, Vedat & M Cemal Dincer (1995), ‘Facility location and capacity acquisition: anintegrated approach’, Naval Research Logistics 42(8), 1141–1160.

Weber, Alfred (1929), ‘Alfred weber’s theory of the location of industries (translation of"Über den standort der industrien")’.

Wentges, Paul (1996), ‘Accelerating benders’ decomposition for the capacitated facilitylocation problem’, Mathematical Methods of Operations Research 44(2), 267–290.

Wesolowsky, George O (1973), ‘Dynamic facility location’, Management Science19(11), 1241–1248.

Wesolowsky, George O (1993), ‘The weber problem: History and perspectives.’, Compu-ters & Operations Research .

Wesolowsky, George O & William G Truscott (1975), ‘The multiperiod location-allocation problem with relocation of facilities’, Management Science 22(1), 57–65.

Williamson, David P & David B Shmoys (2011), The design of approximation algorithms,Cambridge university press.

Wollenweber, Jens (2008), ‘A multi-stage facility location problem with staircase costsand splitting of commodities: model, heuristic approach and application’, OR Spec-trum 30(4), 655–673.

Yaman, Hande & Giuliana Carello (2005), ‘Solving the hub location problem with modu-lar link capacities’, Computers & operations research 32(12), 3227–3245.

Yang, Xin-She (2010), Nature-inspired metaheuristic algorithms, Luniver press.

Zhang, Jiawei, Bo Chen & Yinyu Ye (2005), ‘A multiexchange local search algorithmfor the capacitated facility location problem’, Mathematics of Operations Research30(2), 389–403.


Apêndice A

Resultados dos experimentos

As Tabelas A.1, A.2 e A.3 mostram os resultados em detalhe dos experimentos re-alizados na Seção 4.4 para L = 3, 5 e 10, respectivamente. A coluna Inst1 se refere ainstância de acordo com seu tamanho, topologia da rede, distribuição das demandas eproporção dos custos. GMC mostra os resultados obtidos pelo método exato, onde Solu-ção é o valor da função objetivo encontrada, GAPLB é a distância para o limitante inferiorao terminar a execução e Tempo o tempo para parada da execução. AG+VNDi são os re-sultados da metaheurística, onde GAP é o GAP médio relativo das execuções comparadoa melhor solução encontrada pelo método exato, Tempo é o tempo médio de execução e#Exato a quantidade de execuções que encontraram uma solução igual ou melhor que amelhor solução do método exato.

Tabela A.1: Resultados dos experimentos para L = 3

InstGMC AG+VNDi

Solução GAPLB Tempo GAP Tempo #Exato10/20, nw1, CONS, 100 4401495 0,00% 1s 0,00% 0,48s 1010/20, nw1, CONS, 500 9855435 0,01% 0s 0,00% 0,51s 1010/20, nw1, RND, 100 4475922 0,00% 0s 0,00% 0,44s 1010/20, nw1, RND, 500 9780963 0,00% 0s 0,00% 0,50s 10

10/20, nw2, CONS, 100 5240672 0,00% 0s 0,00% 0,80s 1010/20, nw2, CONS, 500 12735690 0,01% 0s 0,04% 0,59s 710/20, nw2, RND, 100 5075685 0,00% 1s 0,00% 0,42s 1010/20, nw2, RND, 500 12269854 0,00% 0s 0,00% 0,51s 10



1Tamanho (10/20 a 100/1000), topologia (nw1: 300 x 300; nw2: 380 x 380; e nw3: 450 x 450),demandas (CONS: constante; RND: aleatória), custos (100: original; 500: alteradas em 500%)

77

78 APÊNDICE A. RESULTADOS DOS EXPERIMENTOS












79












InstGMC AG+VNDi











81

50/100, nw2, CONS, 100 14936647 0,00% 7s 0,00% 34,90s 1050/100, nw2, CONS, 500 37232592 0,00% 3s 0,00% 228,44s 1050/100, nw2, RND, 100 14760106 0,00% 20s 0,05% 49,33s 550/100, nw2, RND, 500 35577698 0,01% 4s -0,01% 185,49s 10















83


InstGMC AG+VNDi





10/50, nw2, CONS, 100 12755690 0,93% +21600s 0,00% 1,48s 1010/50, nw2, CONS, 500 32853969 0,26% +21600s 0,00% 1,57s 1010/50, nw2, RND, 100 13242553 3,55% +21600s 0,00% 2,26s 1010/50, nw2, RND, 500 33112669 0,01% 5947s 0,00% 1,51s 10


50/50, nw1, CONS, 100 9676307 0,44% +21600s -0,03% 35,72s 1050/50, nw1, CONS, 500 15826261 0,01% 186s 0,00% 40,56s 950/50, nw1, RND, 100 10310940 1,36% +21600s 0,03% 29,85s 350/50, nw1, RND, 500 15873676 0,00% 36s 0,02% 30,27s 7



50/100, nw1, CONS, 100 13259704 0,43% +21600s 0,03% 96,32s 650/100, nw1, CONS, 500 28211804 0,01% 67s 0,07% 106,83s 150/100, nw1, RND, 100 13531208 0,40% +21600s 0,02% 87,03s 850/100, nw1, RND, 500 27994228 0,00% 385s 0,00% 102,83s 10









100/250, nw3, CONS, 100 32548373 0,00% 802s 0,02% 2878,26s 7100/250, nw3, CONS, 500 81940817 0,00% 87s 0,03% 3611,48s 1100/250, nw3, RND, 100 32428523 0,24% +21600s 0,00% 2236,36s 9100/250, nw3, RND, 500 80262608 0,01% 74s 0,00% 3643,91s 4


100/500, nw2, CONS, 100 44786585 0,01% 126s 0,05% 3629,94s 5100/500, nw2, CONS, 500 116300588 0,01% 4s 0,06% 3686,92s 0100/500, nw2, RND, 100 44667649 0,01% s 285 0,10% 3612,52s 3100/500, nw2, RND, 500 114983244 0,00% 4s 0,10% 3661,98s 0

100/500, nw3, CONS, 100 54142844 0,41% +21600s 0,07% 3633,92s 3100/500, nw3, CONS, 500 150477964 0,00% 17s 0,08% 3726,35s 0100/500, nw3, RND, 100 54053690 0,00% 33s 0,20% 3647,61s 0100/500, nw3, RND, 500 149278644 0,01% 9s 0,07% 3626,99s 1

85




Documents

Um Algoritmo Evolucionário para o Problema Dinâmico de