“Tese apresentada ao Centro de Ciência e Tecnologia, da ... · UM ALGORITMO GENÉTICO PARA SOLUÇÃO DO PROBLEMA DE LOCALIZAÇÃO DE ATIVIDADES ECONÔMICAS ... desenvolvido resultou

UM ALGORITMO GENÉTICO PARA SOLUÇÃO DO PROBLEMA DE

LOCALIZAÇÃO DE ATIVIDADES ECONÔMICAS

JACQUELINE MAGALHÃES RANGEL CORTES

“Tese apresentada ao Centro de Ciência e

Tecnologia, da Universidade Estadual do

Norte Fluminense, como parte das

exigências para obtenção do título de

Doutor em Ciências de Engenharia”.

Orientador: Prof. Geraldo Galdino de Paula Junior, D.Sc.

Campos dos Goytacazes – RJ

Agosto de 2003

UM ALGORITMO GENÉTICO PARA SOLUÇÃO DO PROBLEMA DE

LOCALIZAÇÃO DE ATIVIDADES ECONÔMICAS

JACQUELINE MAGALHÃES RANGEL CORTES

“Tese apresentada ao Centro de Ciência e

Tecnologia, da Universidade Estadual do

Norte Fluminense, como parte das

exigências para obtenção do título de

Doutor em Ciências de Engenharia.”

Aprovada em 28 de agosto de 2003.

Comissão Examinadora:

Prof. Geraldo Galdino de Paula Junior, D.Sc. UENF

Presidente

Profa. Gudelia G. Morales, D.Sc., UENF

Prof. José Ramón Arica Chávez, D.Sc., UENF

Prof. Rodrigo Tavares Nogueira, D.Sc., UES

ii

DEDICATÓRIA

A Deus, sempre presente.

A minha vó Elvira, uma doce lembrança.

iii

AGRADECIMENTOS

Ao professor Geraldo Galdino de Paula Junior, pelo precioso conhecimento

transmitido.

Aos professores Arica, Gudélia e Rodrigo, pelas observações e sugestões.

A Décio, companheiro de todos os momentos.

A meus pais Maria Luiza e Cretom e a minha irmã Sheila pelo incentivo, amor e

carinho.

A Alcimar e Roberto, pela colaboração.

Aos colegas do Laboratório de Engenharia de Produção.

A UENF, pela oportunidade.

A Fenorte, pelo apoio financeiro.

A todos os que de alguma forma contribuíram para a realização deste trabalho.

iv

Resumo da Tese apresentada ao CCT/UENF, como parte dos requisitos

necessários à obtenção do grau de Doutor em Ciências de Engenharia (D.Sc.)

Um Algoritmo Genético para Solução do Problema de

Localização de Atividades Econômicas

Jacqueline Magalhães Rangel Cortes

Orientador: Geraldo Galdino de Paula Junior, D.Sc.

Curso: Doutorado em Ciências de Engenharia

Área de Concentração: Engenharia de Produção

O problema de localização de atividades econômicas de base tecnológica é

representado nesta tese por um modelo linear, multiobjetivo e dinâmico 0-1. Os

objetivos aqui atingidos estão contidos em resultados que se basearam em

fatores locacionais dominantes, de natureza qualitativa e quantitativa. A

formulação apresentada como resultado da pesquisa se propõe a minimizar os

custos de implantação das atividades econômicas, minimizar o tempo de acesso

dessas atividades aos seus clientes e maximizar a obtenção de benefícios

agregados às instalações e suas conexões, durante o horizonte de planejamento.

Além disso, o processo de localização atende a um conjunto de restrições

operacionais, de orçamento, bem como à exigência de interligação dos períodos

de tempo associados ao aspecto dinâmico do problema. O esforço aqui

desenvolvido resultou na formulação de um algoritmo genético e de sua

adaptação à abordagem multiobjetivo do problema tratado nesta tese. Tal

contribuição incorpora o uso de operadores de correção, apropriados e

particulares, assim como inclui a penalização das soluções inviáveis através de

uma verificação seqüencial das restrições. Ao final do processo evolutivo, as

soluções não-dominadas, extraídas do conjunto das melhores soluções, são

fornecidas à avaliação do decisor. Experimentos computacionais extensos foram

realizados e seus resultados mostraram-se promissores, tanto em relação a

aproximações de uma solução do problema em si, quanto com vistas à vantagem

de se utilizar, via metáfora biológica, a inteligência da natureza em favor do

cálculo de uma solução de problemas de modelagem computacional.

v

Abstract of Thesis presented to CCT/UENF as a partial fulfillment of the

requirements for the degree of Doctor in Engineering Sciences (D.Sc.).

A Genetic Algorithm for Solving the Economic Activity Location Problem

Jacqueline Magalhães Rangel Cortes

Advisor: Geraldo Galdino de Paula Junior, D.Sc.

Subject: Doctor in Engineering Science

Major Subject: Production Engineering

A linear, multiobjective and dynamic 0-1 model is used in this thesis to

describe and solve, by a genetic algorithm, the location problem of economic

activities having technological basis. The objectives achieved are contained in the

results based on location dominant factors of qualitative and quantitative nature.

The formulation presented aims to minimize investment costs of economic

activities, minimize the access time of those activities to their customers and

maximize the benefits joined to the facilities and their connections, during the

planning horizon. Besides, the location process assists a group of operational

restrictions, of budget, as well as the demand of interlinked periods of time,

associated to the dynamic side of the problem. The effort developed results in the

formulation of a genetic algorithm and its adaptation to the multiobjetive approach

of the problem treated in this thesis. Such contribution incorporates the use of

correction operators, appropriate and private, as well as includes the penalization

of the infeasible solutions through a sequential verification of the restrictions. At

the end of the evolutionary process, the non dominated solutions, extracted from

the group of the best solutions, are supplied to the decisor maker’s evaluation.

Extensive computational experiments were accomplished and their results were

shown promising, so much in relation to the solution of the problem in itself, as

with views to the advantage of using, through biological metaphor, the intelligence

of the nature in solution of computational modeling problems.

vi

SUMÁRIO

Lista de Figuras...........................................................................................ix

Lista de Tabelas.......................................................................................... x

Lista de Quadros.........................................................................................xi

CAPÍTULO 1 INTRODUÇÃO..............................................................................1

1.1 Considerações gerais....................................................................... 1

1.2 Objeto de estudo...............................................................................6

1.3 Objetivos da pesquisa.......................................................................6

1.3.1 Objetivo geral.......................................................................... 6

1.3.2 Objetivo específico.................................................................. 6

1.4 Importância do trabalho.................................................................... 7

1.5 Estrutura do texto..............................................................................7

CAPÍTULO 2 PROGRAMAÇÃO MULTIOBJETIVO................................................. 9

2.1 Principais formas de análise multiobjetivo........................................ 9

2.2 Conceitos fundamentais da programação multiobjetivo................... 12

2.3 Procedimentos para resolução de problemas PMO......................... 16

2.4 Alguns métodos de resolução de problemas PMO-01..................... 19

CAPÍTULO 3 PROBLEMAS DE LOCALIZAÇÃO.................................................... 22

3.1 Teoria de localização........................................................................22

3.2 Base histórica dos problemas de localização descritivos................. 23

3.3 Base histórica dos problemas de localização normativos................ 24

3.3.1 Redes, centros e medianas .....................................................25

3.3.2 Modelos de localização........................................................... 26

3.3.3 Relaxação do problema de localização linear e estrutura

facial do politopo......................................................................30

3.3.4 Base histórica dos algoritmos para o problema de localização

de atividades.......................................................................... 32

3.3.4.1 Relaxação lagrangeana............................................. 33

3.3.4.2 Decomposição de Benders........................................ 36

vii

3.3.4.3 Um algoritmo de decomposição baseado na

relaxação lagrangeana convexa do problema

mestre de Benders..................................................... 38

3.4 Problemas de localização dinâmica..................................................41

3.4.1 Um problema específico de localização dinâmica................... 42

3.4.2 Outros problemas de localização dinâmica............................. 44

3.5 Problemas de localização multiobjetivo............................................ 46

3.6 Problemas de localização dinâmica multiobjetivo.............................47

CAPÍTULO 4 FATORES LOCACIONAIS.............................................................. 50

4.1 Considerações iniciais...................................................................... 50

4.2 Importância dos fatores locacionais..................................................50

4.3 Classificação dos fatores locacionais............................................... 52

4.4 Fatores mais relevantes....................................................................55

4.4.1 Custo....................................................................................... 55

4.4.2 Proximidade da matéria-prima................................................ 55

4.4.3 Proximidade dos mercados consumidores..............................56

4.4.4 Economias de aglomeração.................................................... 57

4.4.5 Características da localidade.................................................. 58

4.4.5.1 Disponibilidade de mão-de-obra.................................. 58

4.4.5.2 Infra-estrutura local...................................................... 58

4.4.5.3 Tributação e incentivos fiscais..................................... 59

4.4.5.4 Qualidade de vida........................................................ 59

CAPÍTULO 5 ALGORITMO GENÉTICO............................................................... 61

5.1 Algoritmo genético tradicional...........................................................61

5.1.1 O diferencial dos algoritmos genéticos....................................61

5.1.2 Conceituação básica . ............................................................. 62

5.1.3 Funcionamento dos algoritmos genéticos............................... 64

5.1.4 Operadores genéticos............................................................. 65

5.1.4.1 Seleção........................................................................ 65

5.1.4.2 Cruzamento..................................................................66

5.1.4.3 Mutação....................................................................... 67

5.1.4.4 Elitismo.........................................................................67

viii

5.1.5 Parâmetros genéticos..............................................................68

5.2 Algoritmo genético para problemas com restrições.......................... 69

5.3 Algoritmo genético para problemas multiobjetivo............................. 71

CAPÍTULO 6 UM MODELO DE LOCALIZAÇÃO DINÂMICA MULTIOBJETIVO............ 74

6.1 Introdução.........................................................................................74

6.2 Especificação do modelo.................................................................. 75

6.3 Funções objetivo...............................................................................76

6.4 O modelo dinâmico multiobjetivo...................................................... 78

CAPÍTULO 7 O ALGORITMO GENÉTICO PROPOSTO.......................................... 81

7.1 Introdução.........................................................................................81

7.2 Codificação do cromossomo.............................................................82

7.3 População inicial...............................................................................83

7.3.1 Geração aleatória de valores para y .................................... 83 it

7.3.2 Garantia de instalação.............................................................84

7.3.3 Garantia de viabilidade orçamentária...................................... 84

7.3.4 Geração aleatória de valores para x ................................... 84 ijt

7.3.5 Garantia de associação...........................................................84

7.4 Avaliação da aptidão.........................................................................85

7.5 Ordenação........................................................................................ 86

7.6 Seleção.............................................................................................86

7.7 Cruzamento...................................................................................... 86

7.8 Mutação............................................................................................87

7.9 Correção........................................................................................... 87

7.10 Penalização.................................................................................... 89

7.11 Elitismo........................................................................................... 90

7.12 Critério de término.......................................................................... 91

7.13 Não-dominância..............................................................................91

7.14 O algoritmo..................................................................................... 92

CAPÍTULO 8 EXPERIMENTOS COMPUTACIONAIS...............................................95

8.1 Características de hardware e software........................................... 95

ix

8.2 Inicialização dos parâmetros............................................................ 95

8.3 Problemas teste................................................................................95

8.4 Resultados........................................................................................98

CAPÍTULO 9 CONCLUSÕES E PESQUISAS FUTURAS......................................... 103

9.1 Conclusões....................................................................................... 103

9.2 Pesquisas futuras............................................................................. 104

REFERÊNCIAS ...............................................................................................106

x

LISTA DE FIGURAS Capítulo 2 Figura 2.1 Espaço de decisão.....................................................................14

Figura 2.1 Espaço de critérios.................................................................... 14

Capítulo 5 Figura 5.1 Exemplo de cruzamento de um ponto...................................... 66

Figura 5.2 Exemplo de cruzamento de multipontos................................... 66

Figura 5.3 Exemplo de cruzamento uniforme............................................ 67

Figura 5.4 Exemplo de mutação................................................................ 67

Capítulo 7 Figura 7.1 Sentido da comparação entre a população gerada e a elite.... 91

xi

LISTA DE TABELAS

Capítulo 8 Tabela 8.1 Resultados de P1 para pc = 1................................................... 98

Tabela 8.2 Resultados de P1 para pc = 0,8................................................ 98


Tabela 8.4 Resultados de P2 para pc = 1................................................... 99


Tabela 8.6 Resultados de P2 para pc = 0,5............................................... 100

Tabela 8.7 Resultados de P3 para pc = 1.................................................. 100



xii

LISTA DE QUADROS

Capítulo 2 Quadro 2.1 Comparação entre as abordagens PMO e MADM................. 11

Capítulo 8 Quadro 8.1 Dimensões dos problemas teste............................................. 96

Quadro 8.2 Combinações de parâmetros genéticos utilizados.................. 97

Quadro 8.3 Valores ótimos dos problemas P1 e P2.................................. 97

xiii

CAPÍTULO 1

INTRODUÇÃO 1.1 Considerações gerais

As empresas têm dado cada vez mais importância ao seu planejamento locacional

motivadas pela obtenção de maior competitividade. As decisões relativas a este tipo de

planejamento podem ser tomadas considerando uma mistura de feeling pessoal do decisor e

métodos científicos de auxílio à tomada de decisão. Contudo, a utilização destes métodos

não garante uma decisão fácil, pois o planejamento locacional é, por natureza, de longo

prazo, intensivo em uso de dados e de complexidade elevada. Nesse sentido, a análise

locacional é um tema de interesse de pesquisadores de áreas como Economia, Engenharia,

Geografia, Pesquisa Operacional, Marketing, Matemática, Planejamento, Ciência

Regional, entre outros.

O problema de localização de atividades pode ser visto como uma subárea de um

contexto mais amplo conhecido como Logística, que trata do planejamento, organização e

controle das tarefas associadas a armazenagem, transporte e distribuição de bens e

serviços, ou ainda definido pela seleção adequada de configurações em redes, tais como,

redes de transporte, de distribuição e de comunicação. Em muitas situações, e quando for

apropriada, a análise locacional é considerada, do ponto de vista econômico, como a busca

do equilíbrio entre custos fixos de implantação de atividades e custos variáveis de

transporte entre as atividades e os clientes atendidos por elas. Isto pode ocorrer com ou

sem a consideração de restrições sobre o número de atividades a serem instaladas no

cenário que é objeto de estudo.

CAPÍTULO 1 – INTRODUÇÃO

2

De forma geral, a localização de atividades econômicas1 consiste em escolher um

ou mais locais entre um conjunto de potenciais alternativas, respeitando um conjunto de

restrições2 e considerando uma medida de avaliação3 (objetivo) das possíveis alternativas

de instalação.

O planejamento da localização pode existir em muitos contextos, desde a

localização de indústrias, aeroportos ou hospitais até de máquinas ou equipamentos. Em

relação ao espaço geográfico, a localização pode apresentar-se em dois principais níveis:

Nível macro: Na localização macrogeográfica consideram-se as características inter-

regionais na escolha da região ou cidade para a instalação da atividade econômica; e,

Nível micro: Na localização microgeográfica consideram-se as características em um

nível mais local para a determinação da localização. Escolhe-se, por exemplo, o terreno

dentro de um determinado bairro.

A importância da decisão locacional é freqüentemente relacionada aos altos

investimentos e ao impacto que tais decisões têm sobre os custos. Dessa forma, a

localização representa um elemento fundamental para a vantagem competitiva das

empresas. Porter (1999a) apresenta uma das razões que reforçam a necessidade da decisão

locacional ser parte da estratégia global da empresa: “[...] a localização afeta a vantagem

competitiva através da influência sobre a produtividade e, em especial, sobre o crescimento

da produtividade”. Uma empresa de qualquer setor (agricultura, vestuário, educação, etc)

pode tornar-se mais produtiva se forem incorporados métodos sofisticados, adotadas

tecnologias avançadas e oferecidos produtos e serviços únicos. Potencialmente, todos os

setores dispõem de condições para utilizar alta tecnologia4 e podem ser intensivos em

conhecimento.

1 Atividade econômica é considerada aquela socialmente organizada para produção de bens e/ou serviços e que apresenta resultado econômico. 2 Por exemplo, restrições de orçamento, de tempo, de atendimento a todos os clientes, entre outros. 3 Por exemplo, menor custo, menor contaminação, maior satisfação, entre outros. 4 O termo “alta tecnologia” se refere a um processo de produção cujo insumo principal é o conhecimento e a informação (CASTELLS, 1986). De acordo com Malecki (1997), dois indicadores principais podem ser utilizados para definir alta tecnologia: a participação dos gastos com Pesquisa & Desenvolvimento (P&D) no total das vendas e a percentagem de trabalho profissional (cientistas, engenheiros e técnicos) no total da força de trabalho.


3

Uma atividade econômica de base tecnológica se caracteriza pelo uso de

tecnologias inovadoras, exigindo investimentos em Pesquisa & Desenvolvimento (P&D) e

com o emprego intensivo de conhecimento técnico-científico. As áreas de informática,

microeletrônica, química fina, biotecnologia, aeroespacial, mecânica de precisão,

tecnologia da informação, automação industrial, entre outras, são exemplos típicos de

destaque.

Embora P&D represente um elemento crítico de uma atividade de base tecnológica,

poucas empresas são inteiramente de alta tecnologia, no sentido de serem

predominantemente engajadas na produção não rotineira, essência das atividades de P&D

(MALECKI, 1987).

Segundo Carvalho et al. (2000), as empresas brasileiras de base tecnológica podem

ser caracterizadas como micro e pequenas empresas de capital próprio, formadas a partir de

tecnologia gerada pelas transações informais entre empresário e Universidade, e por terem

poucos sócios de elevado nível de escolaridade.

De acordo com Porter (1990), existem várias formas da localização afetar o custo

de uma empresa, seja de base tecnológica ou não, uma vez que as localidades possuem

diferentes custos de logística, de mão-de-obra, de administração, de matérias-primas, de

energia, entre outros. Assim, a preferência por um local em potencial geralmente depende

do custo associado ou do lucro esperado. No entanto, nas decisões locacionais raramente as

avaliações são baseadas exclusivamente no valor monetário, envolvendo assim mais de um

objetivo (ver NIJKAMP & SPRONK, 1979). Adicionalmente, segundo Nijkamp & Spronk

(1981), muitos aspectos das decisões de investimento não podem ser representados por um

denominador monetário comum (por exemplo, risco e segurança). Além disso, tais

decisões geralmente causam efeitos que dificilmente poderiam ser incorporados ao custo

tradicional (por exemplo, danos ambientais).

A decisão que envolve múltiplos objetivos é caracterizada como um problema

multiobjetivo5. Em algumas situações, as medidas de avaliação consideradas, quantitativas

ou qualitativas, podem ser conflitantes. Como, por exemplo, uma situação na qual se busca

a minimização dos custos totais e a maximização da qualidade, mas a redução dos custos

implica na redução de qualidade – o que não satisfaz um dos objetivos. Para lidar com este

5 Neste trabalho, as palavras “critério” e “objetivo” são utilizadas com significado semelhante.


4

dilema, são necessárias ferramentas de auxílio à decisão que considerem o tradeoff 6 entre

os fatores relevantes que afetam a decisão a ser tomada (MELACHRINOUDIS & MIN,

2000). Alguns fatores que podem influenciar a escolha final da localização da atividade

econômica podem ser destacados: proximidade dos mercados e dos fornecedores, infra-

estrutura local, localização dos competidores, impacto econômico, impacto na saúde,

barreiras governamentais, qualidade de vida, competências locais e danos ambientais.

Outros fatores podem ser encontrados em Blair (1995).

A empresa que decidir por uma análise multicritério poderá melhorar sua vantagem

competitiva, pois ao incorporar à análise locacional uma grande variedade de aspectos de

decisão relevantes obtém-se uma representação mais próxima da situação real. No entanto,

como as decisões locacionais são inerentemente de longo prazo7, uma localização pode

tornar-se um erro de investimento no futuro devido às mudanças ambientais, mesmo

considerando uma abordagem de múltiplos critérios. Para tornar tal empreendimento

lucrativo, é conveniente selecionar locais que não apenas tenham boa representação de

acordo com o momento atual, mas que continuarão sendo lucrativos pelo período em que a

atividade estiver em operação ou pelo menos durante o horizonte de tempo considerado no

planejamento, mesmo em situações de mudanças ambientais, migrações populacionais e

evolução das tendências de mercado. Nesse contexto, determinar as melhores localizações

em um horizonte de planejamento é um importante desafio para a manutenção da

competitividade da empresa, representando um dos mais importantes determinantes para o

sucesso.

Uma boa localização pode fornecer vantagens estratégicas difíceis de serem

superadas pela concorrência. Uma outra questão importante é que a localização representa

um investimento de longo prazo que freqüentemente está associada a um custo

significativo no caso de relocalização, ao contrário das estratégias de marketing, por

exemplo, que podem ser facilmente modificadas em resposta a uma mudança ambiental

(GHOSH & CRAIG, 1983). Dessa forma, a decisão locacional é um dos elementos críticos

em um planejamento estratégico. Segundo Revelle et al. (1970), essa questão é de interesse

para empresas tanto do setor privado quanto público.

6 Tradeoff é a “negociação” ou compensação realizada entre os fatores a fim de se obter o equilíbrio. Isto significa que a melhoria de um fator só é obtida se algum outro fator piorar (GORE, 1984). 7 Os altos custos associados a aquisição de propriedades e instalação fazem dos projetos de localização e relocalização um investimento de longo prazo (OWEN & DASKIN, 1998).


5

Segundo Iakovou et al. (1997), Psaraftis et al. (1986) e Psaraftis & Ziogas (1985), a

tomada de decisão sobre a localização de equipamentos específicos é estruturada em três

níveis hierárquicos: estratégico, tático e operacional. Para o caso da localização de

atividades econômicas, pode-se ter a seguinte caracterização:

1) Nível estratégico: As questões de investimento e de planejamento de longo prazo são

consideradas. Incluem-se, portanto, as decisões de localização, número, tamanho e tipo

de atividades a serem instaladas;

2) Nível tático: Determinam-se ações de agregação/associação das atividades aos clientes

e os níveis de capacidade apropriados;

3) Nível operacional: A performance da atividade é examinada.

De acordo com Rees & Stafford (1986), as decisões locacionais são estratégicas.

Owen & Daskin (1998) destacam que, devido a sua natureza estratégica, os problemas de

localização necessitam também que características dinâmicas e/ou estocásticas sejam

consideradas. A formulação dinâmica trata a questão do horizonte de tempo envolvido na

localização. A formulação estocástica tenta captar as incertezas nos parâmetros de entrada

do problema, podendo ser tratada de duas formas: através da abordagem probabilística e da

abordagem de cenários. Este trabalho não aborda as questões estocásticas dos problemas

de localização. Para estudos sobre este tema, ver Mulvey et al. (1995), Bean et al. (1992),

Daskin et al. (1992) e Schilling (1982).

Um problema de localização multiobjetivo de característica dinâmica pode ser

representado por um modelo de programação matemática. No entanto, como geralmente

tal modelo possui natureza combinatorial e complexidade elevada, o custo computacional

para sua resolução é alto, pois a obtenção de soluções exatas em tempo determinístico não

é possível. Nesse caso, um método heurístico de resolução pode ser o mais apropriado para

resolver tal modelo. O método heurístico chamado Algoritmo Genético (AG) tem obtido

sucesso na resolução de problemas combinatórios complexos, o que o torna um forte

candidato para resolver o problema de localização considerado.

AG é um algoritmo heurístico8 de busca estocástica baseado no processo de

evolução biológica e que favorece o alcance do ótimo global. Sua utilização é adequada

8 Os AGs, assim como as técnicas Simulated Annealing e Busca Tabu, são chamados de metaheurísticas.


6

para resolver problemas complexos – tais como, otimização combinatória, aprendizado de

máquina, processamento de imagem, robótica, etc – fornecendo soluções de boa qualidade

em tempos computacionais aceitáveis a partir de fácil implementação em computadores

(GOLDBERG, 1989).

Além da simplicidade, uma outra característica marcante dos AGs é que eles

trabalham com um conjunto de soluções ao invés de uma única solução, assim, em cada

rodada do algoritmo um conjunto de soluções pode ser oferecido ao decisor. Essa última,

em especial, é a característica principal que distingue e torna os AGs apropriados a

resolução de problemas multiobjetivo, pois supre a necessidade que tais problemas têm de

obtenção de um conjunto de soluções que sejam melhores em pelo menos um objetivo.

1.2 Objeto de estudo

Neste trabalho, consideraram-se os seguintes objetos de estudo:

A localização de atividades econômicas de base tecnológica do setor privado

considerando um conjunto de restrições.

O tratamento de soluções inviáveis através de algoritmos genéticos.

1.3 Objetivos da pesquisa

Os objetivos da pesquisa são classificados em dois tipos: geral e específico.

1.3.1. Objetivo geral

Propor uma abordagem para auxiliar o planejamento da localização de atividades

econômicas de base tecnológica.

1.3.2. Objetivos específicos

Os objetivos específicos deste trabalho são:

Formular um modelo dinâmico multiobjetivo para representar o problema de

localização de atividades econômicas de base tecnológica. Esse modelo deve

considerar um conjunto de restrições, como também objetivos que estejam relacionados

a fatores qualitativos e quantitativos potencialmente dominantes na decisão locacional

de tais atividades.


7

Desenvolver um algoritmo genético para resolver, de forma interativa com o decisor, o

modelo proposto para o problema de localização de atividades econômicas de base

tecnológica. Tal algoritmo deve incorporar procedimentos apropriados para lidar com

as soluções inviáveis do problema.

1.4 Importância do trabalho

Devido a importância das decisões locacionais, modelagens mais aprofundadas

devem ser desenvolvidas a fim de expressar melhor a complexidade inerente a este tipo de

decisão. Em particular, as abordagens multiobjetivo e dinâmica são de natureza estratégica

e tratam o problema de localização de forma mais realista. Conseqüentemente, espera-se

contribuir para que a escolha locacional seja bem sucedida, no momento da decisão e nas

condições futuras, do ponto de vista das considerações econômicas do empresário.

Também se espera contribuir para a identificação e compreensão dos fatores, sejam

qualitativos ou quantitativos, que influenciam as decisões locacionais.

Um outro ponto a ser destacado é que existem relativamente poucas técnicas para a

resolução de problemas complexos de decisão locacional, tal como o abordado neste

trabalho. O desenvolvimento de novos métodos que forneçam boas soluções em tempo

computacional aceitável ainda é um desafio.

Além disso, o tratamento das soluções inviáveis dos problemas de otimização

representa uma nova área de atuação dos AGs. Assim, esta tese contribui ao propor formas

apropriadas de correção e penalização baseadas em restrições específicas do modelo

considerado.

1.5 Estrutura do texto

Este trabalho possui nove capítulos, incluindo este primeiro, onde são apresentados

as considerações gerais, os objetivos e a importância desta pesquisa.

No capítulo 2 tem-se uma revisão sobre as principais formas de se realizar uma

análise multiobjetivo e os conceitos básicos da programação multiobjetivo, sendo

particularizado para o problema linear 0-1 (PMOL-01). Por fim, os procedimentos para

resolução dos problemas de programação matemática são tratados.


8

O capítulo 3 trata dos problemas de localização. Inicialmente, são apresentadas as

duas principais formas de se abordar um problema de localização. Em seguida é

apresentada uma revisão da base histórica referente a problemas de localização

considerando essas duas correntes, com destaque para as pesquisas realizadas no âmbito da

programação matemática.

No capítulo 4, discutem-se os fatores que influenciam as decisões locacionais,

sendo apresentados ao final do capítulo os que atualmente têm maior relevância.

No capítulo 5 são apresentados os conceitos básicos relacionados aos algoritmos

genéticos tradicionais. Ao final, dá-se atenção aos algoritmos genéticos específicos para os

problemas com restrições como também os algoritmos para os problemas multiobjetivo.

No capítulo 6 é apresentado o modelo sugerido para o problema de localização de

atividades econômicas de base tecnológica. Tal modelo é multiobjetivo linear 0-1 que

incorpora características dinâmicas.

No capítulo 7 descrevem-se as etapas de um algoritmo genético que contém

operadores de correção e penalização propostos para o tratamento de soluções inviáveis de

um problema de localização específico. Além desses operadores, o algoritmo considera um

processo aleatório orientado para a geração de soluções viáveis iniciais e um operador que

preservar as melhores soluções obtidas em cada iteração do algoritmo.

O capítulo 8 fixa-se nas implementações e testes computacionais realizados durante

a implementação do algoritmo genético proposto para resolver o problema de localização

de atividades de base econômica. Este algoritmo é comparado com um algoritmo genético

que trabalha com uma elite, porém, utiliza apenas os operadores genéticos tradicionais.

O capítulo 9 apresenta as conclusões deste trabalho, além de sugestões de temas

para futuras pesquisas.

CAPÍTULO 2

PROGRAMAÇÃO MULTIOBJETIVO 2.1 Principais formas de análise multiobjetivo

A área de Auxílio Multicritério à Decisão (AMD), também conhecida como

Tomada de Decisão com Múltiplos Critérios, está relacionada aos métodos e

procedimentos pelos quais múltiplos critérios podem ser formalmente incorporados ao

processo analítico. O propósito é dar ao decisor ferramentas que possam capacitá-lo a

resolver um problema de decisão, onde diversos interesses, freqüentemente conflitantes,

devem ser considerados. A abordagem do problema de decisão sob o enfoque do AMD

visa apoiar o processo decisório através da recomendação de ações ou cursos de ações.

Siskos & Spyridakos (1999) consideram que são quatro as tendências teóricas de

abordagem de AMD, a saber: abordagem de sistema de valor (ou teoria de utilidade

multiatributo), abordagem de relação de hierarquia, abordagem de desagregação-agregação

e abordagem de otimização multiobjetivo.

A abordagem de sistema de valor1 visa a construção de uma função utilidade (ou

sistema de valor) que agrega as preferências do decisor em um critério baseado em

suposições rigorosas (relações de preferência transitiva e completa). O sistema de valor

estimado por esta abordagem fornece uma forma quantitativa que conduz o decisor em sua

decisão final (ver ZOPOUNIDIS, 1999; KEENEY, 1992; KEENEY & RAIFFA, 1976).

A abordagem de relação de hierarquia2 surgiu a partir da elaboração dos métodos

ELECTRE (ELimination Et Choix Traduisant la REalité). O conceito de hierarquia nos

métodos ELECTRE é devido a Bernard Roy, que foi o pioneiro nesses métodos. Tal

1 Escola Americana. 2 Escola Francesa.

CAPÍTULO 2 – PROGRAMAÇÃO MULTIOBJETIVO

10

abordagem visa a construção de uma relação de hierarquia das alternativas de ação que

permita a comparação entre elas, porém, não é limitada a um modelo matemático.

Adicionalmente, um processo de exploração e dedução é realizado para ajudar o decisor a

verificar se uma solução é satisfatória (ver SISKOS & SPYRIDAKOS, 1999;

ZOPOUNIDIS, 1999; ROY, 1990).

A abordagem de desagregação-agregação é freqüentemente utilizada como uma

forma de modelar as preferências de um decisor (ou de um grupo de decisores) através de

análise de seu comportamento e seu estilo cognitivo. Procedimentos interativos e iterativos

especiais são usados de forma que os componentes do problema e a forma de julgamento

das alternativas de ação sejam analisados e seqüencialmente agregados em um sistema de

valor. O objetivo desta abordagem é auxiliar o decisor a melhorar sua compreensão sobre o

estado do problema e sua forma de julgar, a fim de que se consiga uma decisão consistente

(SISKOS & SPYRIDAKOS, 1999; ZOPOUNIDIS, 1999).

A abordagem de otimização multiobjetivo é representada por um problema de

programação matemática que considera mais de um objetivo para satisfazer e um conjunto

de alternativas de ação relativamente grande (MALCZEWSKI, 1999; SISKOS &

SPYRIDAKOS, 1999).

Uma outra forma de categorização considera basicamente a existência de dois

campos distintos de atuação (DELGADILLO, 1997; CLÍMACO et al., 1996):

1) Método de análise de decisão multiatributo (MADM): refere-se a problemas de

seleção, ordenação ou categorização de um número finito de alternativas explicitamente

conhecidas, em um ambiente de incerteza. Nesse sentido, tal método é chamado de

discreto;

2) Programação matemática multiobjetivo (PMO) ou método de otimização multiobjetivo:

é mais freqüentemente aplicada a problemas determinísticos, nos quais o número de

alternativas viáveis é grande e implicitamente conhecido. Nesse sentido, tal campo de

atuação é chamado de contínuo.

Malczewski (1999) fornece uma comparação dessas duas abordagens. Os

problemas de PMO lidam explicitamente com objetivos primários do decisor e projetam as

alternativas e a busca pela melhor decisão dentre um conjunto infinito ou muito grande de

alternativas viáveis. O papel de PMO na tomada de decisão é fornecer uma estrutura para


11

projetar um conjunto de alternativas. Cada alternativa é definida implicitamente em termos

das variáveis de decisão e avaliadas por meio de funções objetivo. Os problemas de PMO

consideram que atributos de alternativas freqüentemente são meios para se alcançar o

resultado essencial, os objetivos do decisor, enquanto que os MADM obtêm preferências,

geralmente na forma de funções e ponderações, diretamente pelos níveis de atributos. A

resolução pelo MADM é um processo de escolha, em oposição a um processo de projeto.

O quadro 2.1 ilustra esta e outras comparações.

Quadro 2.1 Comparação entre as abordagens PMO e MADM

PMO MADM

Critérios definidos por Objetivos Atributos Objetivos3 definidos Explicitamente Implicitamente

Atributos4 definidos Implicitamente Explicitamente

Restrições definidas Explicitamente Implicitamente

Alternativas definidas Implicitamente Explicitamente

Número de alternativas Infinito (grande) Finito (pequeno)

Controle do decisor Significativo Limitado

Paradigma da

modelagem Orientado ao processo Orientado ao resultado

Relevante a Projeto/Busca Avaliação/Escolha Fonte: Malczewiski (1999, Tabela 3.1)

Considerando que o problema de localização tratado neste trabalho envolve a

escolha de locais e formas de associações dentre um grande número de alternativas viáveis

implicitamente conhecidas, optou-se pela abordagem de programação multiobjetivo.

3 Um objetivo é uma variável mais abstrata que possui uma especificação desejada de seus níveis, máximo ou mínimo (MALCZEWSKI, 1999). 4 Um atributo é uma variável descritiva concreta que representa uma medida de quantidade ou qualidade e é utilizada para medir a performance em relação a um objetivo (MALCZEWSKI, 1999).


12

2.2 Conceitos fundamentais da programação multiobjetivo

Um problema de programação monobjetivo pode ser definido da seguinte forma:

( )Minimize Z f xSujeitoa x S

=∈

onde é a função objetivo ou critério, é o conjunto de variáveis de decisão e S é a

região viável no espaço das variáveis de decisão. Em geral, S é definido por um conjunto

de equações (e/ou desigualdades) de funções de restrição,

, onde A é a matriz de coeficientes tecnológicos

(dimensão m ) e b é o vetor de termos independentes. O propósito deste problema de

otimização é encontrar um ponto x que apresente o mínimo valor da função objetivo.

( )f x

S x∈

x

( ){ : ,n g x b b= = ∈

n×

}m

S∈

De acordo com Steuer (1986), dependendo do tipo das funções do problema

monobjetivo, pode-se ter uma das seguintes classes de problemas:

Problema de programação linear monobjetivo: se for linear e S for definido

também por funções lineares;

( )f x

Problema de programação linear inteiro monobjetivo: se for linear e S for

definido também por funções lineares e pela condição adicional que as coordenadas de

cada ponto em sejam inteiras;

( )f x

S

Problema de programação não-linear monobjetivo: se ou qualquer uma das

restrições que definem S for não-linear.

( )f x

Muitos problemas reais envolvem diversos objetivos a serem satisfeitos

simultaneamente. Este fato faz com que o problema de otimização monobjetivo seja uma

abordagem inadequada e a abordagem multiobjetivo seja mais apropriada para representar

tais problemas reais.

Uma classe de problemas de programação multiobjetivo (PMO) é o problema de

programação multiobjetivo linear (PMOL) apresentado a seguir.


13

( )

( )

( )

{ }

1

2

1 1

2 2

( )

: ,

kk k

n m

PMOL x

S x Ax b b

Minimize Z f x cMinimize Z f x c x

Minimize Z f x c x

Sujeito a x = ∈ = ∈

= == =

= =

∈

De acordo com Steuer (1986), tal problema tem a característica de ser um problema

PMO que possui todos os objetivos e restrições como funções lineares. Uma representação

adicional é dada a seguir.

{ }:Minimize Z C x x S= ∈

onde S x { }0: , ,n mAx b b x= ∈ = ∈

Outras representações possíveis são:

Minimize ( ) ( ) ( ){ }1 2, ,..., kZ f x f x f x=

Sujeito a x S∈

Minimize Z c { }1 2, ,..., kx c x c x=

Sujeito a x S∈

onde é uma matriz dos objetivos (dimensão k ), cujas linhas c são

formadas pelos objetivos individuais, z e Z é o vetor

objetivo.

C n×

ic x

( )1,...,i i k=

k∈( )1,...,i i k==

Enquanto que na programação monobjetivo o conjunto de soluções viáveis S é um

subconjunto no espaço de decisão, na programação multiobjetivo, o conjunto linear


14

{ }: ,kZ Z Z C x x S= ∈ = ∈

x

inimize

2=

de todas os vetores objetivo, correspondentes aos

vetores de soluções viáveis , define o espaço dos critérios (ARBEL &

KORHONEN, 1998).

S∈

A solução viável que otimiza simultaneamente todas as k funções objetivo é

chamada de solução ideal e seu correspondente vetor critério é chamado de ponto ideal.

Pelo fato da solução ideal geralmente não existir, do ponto de vista operacional,

“M ” representa a operação de tradeoff para determinar soluções de compromisso.

Assim, no contexto multiobjetivo, o conceito de solução ótima dá lugar ao de solução

eficiente5 ou não-dominada, dependendo do espaço onde as alternativas são consideradas.

Geralmente, o termo não-dominado é usado no espaço de critérios, e eficiente, no espaço

de decisão (KORHONEN, 1998).

Uma solução que se refere aos piores valores para todas as soluções não-dominadas

é chamado de solução antiideal ou ponto Nadir.

A Figura 2.1 ilustra o espaço de decisão de um problema com duas variáveis de

decisão (n ) e dois objetivos de minimização ( ), enquanto que a Figura 2.2

ilustra seu espaço de critérios destacando o conjunto não-dominado (CND) e as soluções

ideal (I) e antiideal (AI).

2k =

Z CND

AI

z2

z1

S

x2

x1 I

Figura 2.1 Espaço de decisão Figura 2.2 Espaço de critérios

5 Uma solução eficiente também pode ser chamada de Pareto-ótima, não-inferior ou admissível.


15

Uma solução é chamada de eficiente, se, e somente se, não existir outra solução

viável que melhore o valor de uma função objetivo sem piorar o valor de, pelo menos, uma

outra função objetivo. Desta forma, as soluções do conjunto não-dominado são

incomparáveis entre si; em outras palavras, não existe uma solução que seja melhor que as

outras em todos os critérios.

Considerando o problema PMOL, uma definição de vetor objetivo não-dominado e

uma de solução eficiente para o caso de objetivos de minimização são apresentadas a

seguir (CORTES, 1998):

Definição 2.1.: O vetor objetivo ( 1 2, , ..., kkz z z= ∈

( 1 2, , ...,k

kz z z= ∈

))

Z é chamado de não-dominado,

se, e somente se, não existe outro Z tal que Z e Z≤ ii <z z

para pelo menos um . { }i k1 2, , ...,∈

Definição 2.2.: x é uma solução eficiente, se, e somente se, não existir y S

tal que C y e c y para pelo menos um i k .

0 ∈

0C x

S

n

{ }0\ x∈

≤ 0i ic x< { }1 2, , ...,∈

Quando as variáveis de decisão do problema PMOL são todas inteiras, tem-se o

problema multiobjetivo linear inteiro (PMOLI). No caso das variáveis de decisão serem

0-1, tem-se a classe multiobjetivo 0-1 (PMOL-01). Uma formulação para o PMOL-01 é

dada a seguir:

{ }01( ) :PMOL Minimize Z C x x S− = ∈

onde { }: , ,n mS x Ax b b x Β= ∈ = ∈ ∈


16

2.3 Procedimentos para resolução de problemas PMO

A solução de um problema PMO pode ser estimada através de procedimentos

iterativos que conduzem a (SISKOS & SPYRIDAKOS, 1999):

alcançar níveis de satisfação do decisor sobre cada objetivo; ou,

construir um modelo de utilidade do decisor que é usado para a seleção das soluções

viáveis para serem avaliadas segundo um procedimento de maximização da utilidade;

ou,

uma combinação dos dois métodos descritos acima.

Considerando a não existência de um ponto ideal, Steuer (1986) propõe uma forma

de se resolver um problema multiobjetivo a partir da definição da função utilidade

para o decisor. Dessa forma, deve-se resolver o seguinte problema: U : k →

( ){ }( )

1 2U

1

( )

,

, , ..., k

i i

PMU Maximize

Sujeitoa z f x i kx S

z z z

=∈

Um ponto x é ótimo se for eficiente e maximizar a função utilidade do

decisor do problema PMU.

S∈ U

Desconsiderando o fato da função utilidade ser não-linear, uma das maiores

dificuldades é que em muitos problemas não é possível obter uma representação

matemática da função utilidade e, apesar disso, os problemas devem ser resolvidos. U

Sem o conhecimento explícito da função utilidade do decisor, não se tem outra

escolha a não ser a de buscar, no espaço de soluções eficientes, a solução de melhor

compromisso para o decisor através de tradeoffs entre os objetivos do problema PMO,

usando apenas informações implícitas e de uma forma econômica e convencional para o

usuário. Como geralmente o espaço de soluções eficientes é grande, a busca não é fácil de


17

ser feita. Segundo Korhonen & Karaivanova (1998), a questão chave nos métodos de apoio

à decisão multiobjetivo é gerar soluções não-dominadas para a avaliação do decisor de

forma que suas preferências sejam levadas em consideração.

De acordo com Korhonen (1998), apesar de existirem muitas variações entre os

diferentes métodos de geração das soluções eficientes, um procedimento freqüentemente é

adotado: um problema de otimização monobjetivo substituto é resolvido para gerar as

novas soluções. A função objetivo deste problema substituto, chamada de função escalar

substituta, é um escalar que representa o problema multiobjetivo (CLÍMACO &

ANTUNES, 2000; HENIG & RITZ, 1986). Tipicamente, essa função escalar agrega em

uma única dimensão os diferentes objetivos e inclui parâmetros sobre as preferências do

decisor, cuja solução ótima é uma solução eficiente do problema multiobjetivo. Korhonen

(1998) apresenta três classes de parâmetros possíveis para a utilização em programação

multiobjetivo:

1) Coeficientes de ponderação: representam a importância relativa de cada objetivo;

2) Níveis de reserva: correspondem aos requerimentos mínimos sobre cada objetivo;

3) Níveis de aspiração/referência: representam níveis de aspiração desejáveis (ou

indesejáveis) sobre cada objetivo.

Baseadas nesses parâmetros, várias maneiras podem ser adotadas para especificar a

função escalar citada. Uma orientação que deve ser seguida é que essa função caracterize

completamente o conjunto das soluções eficientes.

Segundo Clímaco et al. (1996), tradicionalmente, os métodos de programação

linear multicritério classificam-se em categorias de acordo com o processo utilizado para

agregar as preferências do decisor, com vista a selecionar a “melhor” solução de

compromisso. Esta categorização é apresentada abaixo:

1) Métodos em que não há articulação de preferências do decisor ou métodos geradores

Esses métodos dão pouca responsabilidade ao decisor e podem ser aplicados onde

há decisores inacessíveis ou não identificados. Várias técnicas podem ser utilizadas para a


18

geração de soluções eficientes, entre elas, tem-se o método ponderado e o método de ε-

restrição (ou restritivo). Uma característica comum dessas técnicas é que elas transformam

o problema de decisão multiobjetivo em um problema de um único objetivo para gerar uma

solução eficiente, e então geram o conjunto completo ou um subconjunto de soluções

eficientes por variação paramétrica. As soluções eficientes geradas pelas sucessivas etapas

de cálculo são apresentadas ao decisor para a escolha da solução de maior aceitação.

A diferença básica entre estes dois métodos está na forma como é feita a

transformação de um problema multiobjetivo em um problema monobjetivo. O método

ponderado envolve a designação de pesos para cada uma das funções objetivo e então as

múltiplas funções são convertidas em uma forma monobjetivo através da combinação

linear dos objetivos e seus correspondentes pesos. Um subconjunto de soluções não-

dominadas pode ser gerado pela variação paramétrica dos pesos. O método de ε-restrição

maximiza apenas uma das funções objetivo, enquanto que as outras são convertidas em

restrições de desigualdades com limites ε para cada nova restrição. Um subconjunto de

soluções não-dominadas pode ser gerado pela variação paramétrica dos limites. Ambos os

problemas podem ser resolvidos por técnicas convencionais de programação linear

(MALCZEWSKI, 1999).

2) Métodos em que há articulação de preferências do decisor

2.1) a-priori

Esses métodos requerem a intervenção do decisor no início do processo através da

informação de suas preferências e/ou pesos. Uma função utilidade é construída a partir

dessas preferências. Assim, o problema multiobjetivo é reduzido a um problema

monobjetivo. Alguns métodos que podem ser considerados são: programação por metas e

teoria de utilidade multiatributo, além do método ponderado e do método de ε restrição.

Uma das críticas é baseada em estudos empíricos que demonstraram que os decisores não

são sempre coerentes com as funções destinadas a agregar os critérios e representar as suas

preferências, agindo geralmente mais de acordo com a sua própria maneira de ver o

problema do que procurando conciliar esta com os axiomas que são a justificativa teórica


19

da existência da função de valor (BELL & FARQUHAR, 1986, apud CLÍMACO &

ANTUNES, 2000).

2.2) progressivamente ou métodos interativos

Nesses métodos existe uma articulação progressiva das preferências do decisor ao

longo do processo interativo, podendo considerar uma estrutura de preferências

preexistente. Nos métodos interativos, a existência de uma função de utilidade do decisor

pode ser assumida implicitamente. Todos os procedimentos interativos consistem de duas

fases que se alternam, uma fase de cálculo e uma fase julgamento. Na fase de cálculo, uma

solução, ou um conjunto de soluções, é gerada, e então fornecida ao decisor. Na fase de

julgamento, o decisor avalia a informação recebida e articula suas preferências com

respeito aos valores dos critérios. Esta troca de informação continua até que uma solução

eficiente seja satisfatória para o decisor. Alguns métodos que podem se utilizados de forma

interativa são: ponderado, ε-restrição, STEM (step method), programação por metas

interativa, procedimento Tchebychef (aumentado e lexicográfico), Pareto Race

(CLÍMACO,1986). Os métodos interativos mostram-se mais eficientes para lidar com os

problemas multiobjetivo do que os métodos geradores citados no item 1, pois estão

habilitados a reduzir o esforço computacional, especialmente no caso de problemas de

grande porte (ALVES & CLÍMACO, 2000).

2.4 Alguns métodos de resolução de problemas PMOL-01

Existe um número relativamente pequeno de métodos eficientes para a resolução

dos problemas PMOL-01. A seguir são descritos alguns métodos que podem ser utilizados.

O método de enumeração implícita de Bitran (1977, 1979) é um método não

interativo de enumeração. O autor propõe um problema auxiliar sem restrições, da forma

PMOL-01 e mostra que as soluções deste problema são também eficientes para o problema

original. Inicialmente, o método exclui as soluções não-eficientes viáveis do problema

auxiliar. Então são utilizados vetores de direção (definidos pelo cone polar inverso ao cone

definido pelas filas da matriz de função objetivo) e um ponto a ser mapeado para encontrar

as soluções eficientes. Para encontrar o resto das soluções eficientes, são determinadas e

examinadas as soluções não-eficientes do problema auxiliar. Bitran também propõe um


20

método que trabalha com grafos direcionados. Estes métodos apresentam alto custo

computacional para resolver problemas de médio e grande porte.

Korhonen & Laakso (1986) desenvolveram o método interativo visual apropriado

para problemas multiobjetivo lineares ou não. O propósito desse método é projetar um

segmento ilimitado no espaço critério sobre a superfície não-dominada da região viável. A

projeção sobre a superfície não-dominada é obtida pelo uso de uma função escalar e de um

programa paramétrico. A função escalar considerada é aquela que projeta um ponto de

referência, viável ou inviável, sobre o conjunto de vetores critério não-dominado. Essa

função foi introduzida por Wierzbicki (1983, 1982). A projeção sobre o conjunto não-

dominado de um segmento ilimitado é feita pela resolução de um programa paramétrico

escalarizado.

O método ponderado Tchebychef é um método interativo para resolução do espaço

vetorial ponderado, sendo também apropriado para resolver problemas multiobjetivo

lineares, não-lineares e inteiros. Tal método é baseado na norma generalizada de

Tchebychef λ z , que é da forma 1

λ,...max i ii k

zzλ ==

λ

, onde z e

com sendo constantes positivas, e a exigência que ∑ . Tem-

se o problema chamado de métrica ponderada de Tchebychef. Inicialmente, é obtido um

conjunto representativo maximamente disperso de vetores de ponderação que são

gerados aleatoriamente. O problema é resolvido para estes ’s e os vetores eficientes são

fornecidos ao decisor. Uma nova área em torno dos pesos do vetor selecionado é calculada

com a seleção de um vetor eficiente, dando origem a novos vetores de ponderação e é

encontrado um conjunto representativo maximal disperso dos pesos a partir dessa área. Os

vetores eficientes calculados são fornecidos ao decisor, e assim sucessivamente. A cada

interação um conjunto de problemas de programação inteira é resolvido, fornecendo

apenas uma solução para cada parâmetro (STEUER & CHOO, 1983).

( )1,..., kkz z= ∈

1λ = 1i

k

i=

λ

( 1λ = λ ,...,λk ) λi

λ

O método de enumeração implícita apresentado por Delgadillo (1997) é um método

interativo de enumeração implícita, de forma que em cada interação, um conjunto de

soluções eficientes é calculado através da resolução de um único problema de programação

inteira. Inicialmente, um problema auxiliar monobjetivo é construído, baseado na métrica

ponderada de Tchebychef, de forma que uma solução ótima desse problema é uma solução


21

eficiente para o problema original. Em seguida, o problema auxiliar é resolvido por um

algoritmo de enumeração implícita para gerar um conjunto de soluções eficientes para o

problema original, que é apresentado ao decisor. Caso as soluções sejam satisfatórias, o

procedimento é finalizado, caso contrário, o decisor introduz novos parâmetros e um novo

problema auxiliar é construído, repetindo as etapas anteriores até que o decisor encontre

alguma solução eficiente que seja satisfatória.

CAPÍTULO 3

PROBLEMAS DE LOCALIZAÇÃO 3.1 Teoria de localização

A teoria de localização foi formalmente iniciada por von Thünen (1866) através da

consideração de atividades agrícolas. Porém, deve-se a Weber (1909) a primeira tentativa

de obtenção de uma teoria geral para a localização (apud ZOOK, 2000). De acordo com

Seppälä (1997), a partir deste ponto, as teorias de localização seguiram dois caminhos

distintos. Em um caminho, os economistas seguem von Thünen e se concentram na

explicação do comportamento das atividades econômicas. No outro caminho, estudiosos da

pesquisa operacional seguem Weber. Estes dois caminhos podem ser considerados,

respectivamente, como abordagens descritiva e normativa da teoria de localização. Os dois

tipos principais de modelos resultantes destas abordagens são:

Modelos descritivos: explicam o comportamento espacial das atividades, ou seja, sua

distribuição no espaço geográfico;

Modelos normativos1: fornecem orientações para as decisões locacionais.

Beckmann (1968) afirma que os métodos de Pesquisa Operacional (PO) para o

problema de localização de atividades são baseados na abordagem de equilíbrio da

atividade econômica que é derivada da teoria econômica neoclássica2, embora, como já

visto, o desenvolvimento das técnicas de PO tenha seguido independentemente das teorias

econômicas. Desta forma, os modelos de PO são baseados na busca por um equilíbrio, por

1 De acordo com Galvão et al. (1999), os modelos normativos são chamados assim pelo fato de se caracterizarem pela otimização de uma norma (medida de eficiência), sujeita a restrições operacionais relevantes. 2 A teoria econômica neoclássica considera hipóteses de informação perfeita, existência de equilíbrio, racionalidade, alocação ótima dos recursos, maximização do lucro e desconsideração do tempo (CÁRIO & PEREIRA, 2002).

CAPÍTULO 3 – PROBLEMAS DE LOCALIZAÇÃO

23

exemplo, a maximização do lucro de uma firma. Muitos desses modelos são estáticos

(consideram um único período de tempo) e assumem um equilíbrio estático. Os modelos

dinâmicos de localização (consideram mais de um período de tempo) seguem as dinâmicas

criadas fora do sistema (por exemplo, a consideração de uma mudança de demanda),

enquanto o próprio sistema permanece em equilíbrio (apud SEPPÄLÄ, 1997).

3.2 Base histórica dos problemas de localização descritivos

O modelo de Weber (1909) utiliza os seguintes pressupostos básicos: a distribuição

não-uniforme das matérias-primas, uniformidade dos custos de transporte, homogeneidade

do preço das mercadorias e mercados consumidores puntiformes. Nesse modelo, a

localização de uma indústria será aquela que minimizar o custo total de transporte, tanto da

matéria-prima quanto do produto final. Além do custo de transporte, os fatores locacionais

de custo do trabalho e de aglomeração também, afetam a localização da atividade

(SOUZA, 2002).

Insumos como trabalho e informação foram considerados como ubiqüidades3, o que

revela a pouca importância dada a estes insumos (MALECKI, 1991). A tecnologia é outro

elemento que não recebe destaque, e por causa disso, há um consenso de que a teoria de

Weber possui pouco poder de explicação para as indústrias de base tecnológica

(GONÇALVES, 1999).

O modelo de von Thünen (1866) sugere que a acessibilidade ao mercado urbano

pode criar um sistema completo de uso da área rural. Esse modelo foi desenvolvido para a

agricultura e supõe que um único produto é utilizado para abastecer um único centro

urbano. O fator determinante no aluguel da terra é o custo de transporte. Quando tal custo é

baixo, o aluguel da terra será alto, e vice-versa (SOUZA, 2002).

O modelo de Losch (1954) aborda a localização da indústria e considera que as

matérias-primas e insumos necessários no processo de produção são ubíquos, a população

é distribuída uniformemente e acrescenta as economias de escala como fator importante na

determinação da localização conjuntamente com o fator transporte (em condições

uniformes). A inter-relação deste último item com a idéia de curva de demanda espacial

3 Ubiqüidade é a característica de estar presente ao mesmo tempo em todos os locais, ou seja, ser onipresente.


24

(influenciada pelo custo de transporte) permite a delimitação do que se chama área de

mercado de um determinado centro produtor (SOUZA, 2002).

3.3 Base histórica dos problemas de localização normativos

O problema de localização de atividades4 recebeu grande atenção de pesquisadores

nas quatro décadas recentes, o que estimulou o aparecimento de inúmeras aplicações

práticas no cenário tecnológico, ver Balakrishnan et al. (1991), Mirzaian (1985),

Cornuejols et al. (1977) e Hakimi (1964). Por sua vez, essas aplicações realimentaram a

pesquisa teórica. De fato, soluções conhecidas de diversos problemas de localização

permitiram expandir o uso eficiente de alguns instrumentos de programação matemática

para apoiar o gerenciamento de operações em setores representativos da economia.

A preocupação e o desafio de instalar atividades em locais escolhidos com base em

critérios científicos decorreram, dentre várias causas, do surgimento da crise energética. A

partir deste momento, torna-se necessária a procura por locais ótimos que estejam

associados ao consumo racional de combustível no transporte em estruturas viárias

relacionadas ao problema.

De acordo com Hansen et al. (1985) e Tansel et al. (1983), Jordan (1869) analisa

automorfismos de formas quadráticas, obtendo-se a caracterização do conjunto mediano de

uma árvore. Entretanto, só a partir de 1960, os matemáticos aplicados se motivaram a

pesquisar tais problemas, modelos e algoritmos de localização. A referência para este

início é o trabalho de Hakimi (1964), sobre localização ótima de centros de permutação e

os conceitos de centros e medianas de um grafo. Alguns trabalhos nestas áreas podem ser

encontrados em Hansen et al. (1985), Francis et al. (1983), Tansel et al. (1983), Krarup &

Pruzan (1983) e Cornuejols et al. (1977).

Os problemas de localização de atividades podem ser classificados em estáticos,

dinâmicos, determinísticos, probabilísticos, capacitados, não-capacitados, discretos,

4 Nesta revisão, a expressão “localização de atividades” refere-se, genericamente, a localização de instalações onde ocorrerá algum tipo de atividade de atendimento a população: hospitais, escolas, centros de apoio, etc; a localização de instalações de caráter econômico (atividades econômicas): indústrias, armazéns e centrais de distribuição, plataformas de produção de petróleo, universidades particulares, etc; e a localização de instalações indesejáveis: depósitos de lixo, instalações nucleares, presídios e centros de correção, etc.


25

contínuos e de múltiplos critérios, bem como um problema de p-medianas e de p-centros,

ver Hansen et al. (1985).

A quantidade registrada de artigos científicos sobre localização é grande, ver

Melkote & Daskin (2001), Berman & Drezner (2000), Fernández et al. (2000), Rahman &

Smith (2000), Drezner & Drezner (1998), Revelle & Laporte (1996), Brandeau & Chiu

(1989), Tansel et al. (1983), Krarup & Pruzan (1983), Francis et al. (1983).

3.3.1. Redes, centros e medianas

Uma rede é um conjunto de pontos, nós ou vértices, ligados por um conjunto de

arestas ou arcos. Um centro de uma rede é qualquer um de seus nós em relação ao qual o

nó mais afastado da rede é o mais próximo possível. Uma mediana de uma rede é qualquer

um de seus nós em relação ao qual a soma das distâncias aos demais nós da rede é mínima.

Portanto, o problema de encontrar o centro de uma rede consiste em minimizar a distância

máxima, e encontrar a mediana consiste em minimizar a soma das distâncias dos demais

nós a ela. O centro de uma rede é ideal para instalar atividades do tipo “atendimento de

emergência”, como uma estação do corpo de bombeiros, por exemplo. Dessa forma,

garante-se o atendimento ao cliente mais distante com o mínimo trajeto possível. A

mediana de uma rede é ideal para instalar atividades do tipo “atendimento a população”,

como escolas e hospitais. Assim, garante-se o atendimento aos clientes com o menor custo

possível.

O problema das -medianas, que é o maior grupo de problemas de localização de

atividades, restringe o número de atividades a serem abertas numa rede a um número , ao

mesmo tempo em que se procura minimizar a soma das distâncias (ou custo) entre a

atividade e os vértices da rede considerada, sendo, portanto, do tipo min-sum. O problema

mais simples das p -medianas também é conhecido como “problema de Weber”, que

assume uma simples atividade para se localizar otimamente de acordo com pontos de

demanda discretos. O problema de Weber generalizado – também conhecido como

“problema de localização de depósitos” ou “problema de alocação-localização” – consiste

em localizar atividades em uma área com n pontos de demanda e determinar áreas de

serviços para cada uma das atividades.

p

p

p


26

No problema dos p -centros procura-se minimizar a distância (ou custo) entre a

atividade e o vértice mais distante dentro da rede. Em outras palavras, minimiza-se as

distâncias máximas, ou os tempos ou custos máximos. Enquanto que no problema das -

medianas a solução identifica as medianas da rede, no problema dos -centros, que é do

tipo min-max, a solução localiza os centros da rede.

p

p

3.3.2. Modelos de localização

O problema de localização não-capacitado de atividades é representado pelo

seguinte modelo.

{ }

1 1

1, 1 2

0, , 1 3

0, , 1 4

0 1 , 1 5

( . )

( . )

( . )

( . )

, (

ij ij j ji j j

ijj

j ij

ij

j

Minimize Z c x f y

Sujeito a x i I

y x i I j J

x i I j J

y j J

= +

= ∈

− ∈ ∈

∈ ∈

∈ ∈

∑∑ ∑

∑

. )

}m

}n

onde é o conjunto de clientes que demandam algum tipo de bem e/ou

serviço produzido ou oferecido pelas atividades; J é o conjunto de atividades

em potencial, isto é, conjunto de locais potenciais, para instalação de atividades, visando

atender os clientes; c

{1, ,I = …

{1, ,= …

ij é o custo de atendimento do cliente i pela atividade ; e j jf é o

custo fixo de instalação da atividade . O modelo 1.1 a 1.5 é do problema de localização

não-capacitado, estático, discreto e determinístico. O termo não-capacitado pode ser

interpretado como uma referência a capacidade das atividades atenderem uma quantidade

pseudo-infinita de clientes.

j

Pode-se partir do problema conhecido como capacitado e através de transformações

adequadas chegar-se ao modelo 1.1 a 1.5.

Considera-se o seguinte modelo:


27

( )

{ }

2 1

, 2

0, 2 3

0, , 2 4

0 1 , 2 5

( . )

( . )

( . )

( . )

, (

j ij ij j ji j j

ij ij

j j iji

ij

j

Minimize Z p t f y

Sujeito a d i I

a y j J

i I j J

y j J

= + +

= ∈

− ∈

∈ ∈

∈ ∈

∑∑ ∑

∑

∑

ϖ

ϖ

ϖ

ϖ

2

. )

onde e têm os mesmos significados do modelo 1.1 a 1.5; I J jp é o custo unitário de

operação da atividade incluindo aí os custos variáveis de produção e administração; t é

o custo unitário de transporte da atividade ao cliente i ;

,j ij

j jf é o custo fixo de instalação

da atividade ; j ja é uma constante positiva que atua como limite superior para o fluxo

máximo que sai da atividade ; e d é o número de unidades do bem e/ou serviço que

corresponde à demanda do cliente i .

j i

Com esta formulação procura-se essencialmente minimizar a relação “custo de

produção”/“eficiência logística” para um conjunto de atividades que produzem e fornecem

um determinado item de consumo.

Na solução, o estado da atividade é designado por aberto ou fechado.

1jy se a atividade é aberta (instalada e colocada em operação); e = j

0,jy caso contrário. =

Se 1,jy = o valor de ijϖ é o número de unidades produzidas na atividade e

fornecidas ao cliente i , e se

j

0,jy tem-se = 0.ijϖ = Assim, tem-se n m variáveis

do problema, sendo que a n variáveis

n+ ×

jy são chamadas de estratégicas e as m n

variáveis

×

ijϖ são as variáveis táticas. Um custo fixo de abertura de atividade é considerado

sempre que uma quantidade do item de consumo é enviada a partir de uma atividade. No

modelo 2.1 a 2.5, as n restrições 2.3 asseguram que os clientes serão atendidos somente a

partir de atividades abertas.


28

Considera-se a hipótese de que 0jp e t isto é, 0,ij 0,j ij+p t i

Com isso, nenhuma atividade fornece uma quantidade além da demandada, o que permite

substituir

,I∈ .j J∈

ja da restrição 2.3 por Além disso, a restrição 2.2 pode ser trocada por

igualdade. Na ocorrência de algum

.iid∑

j ijt+p negativo, é possível transformar os dados

adequadamente a fim de manter a hipótese de não-negatividade acima. Substituindo-se

j ijp t+ por j ij ip t α+ + para todo i onde as constantes são escolhidas de acordo com a

seguinte relação

, j

{ :ij p t+ +

,ii

}0 .ij<maxαi j jp t O único efeito desta transformação

será o de aumentar a função objetivo de α∑ sem, contudo, alterar a solução ótima.

Para se determinar um conjunto ótimo de ,ijϖ a partir de qualquer vetor binário

( )jy y= dado, procede-se da seguinte forma:

Seja e X i A relação

ótima “custo de produção”/“eficiência do plano de transporte” fica determinada em relação

ao vetor

{ }1: jX j y= =

( )

( ) {{ }.: minj ij s iss Jj X p t p t

∈= ∈ + = + }

jy dado, se, e para algum for feito y= i∀ ∈I ( ),j X i∈ ij idϖ = e, para os

outros , ,j s 0.ijϖ =

.m

Com isso, a quantidade de soluções distintas possíveis, em termos de

variáveis estratégicas, é dada por ou seja, . Se cada cliente é servido por

uma única atividade, o número total de atribuições distintas possíveis, de clientes a

atividades, é n Do primeiro ao último dos m clientes, cada um tem n formas de ser

atendido.

1,( )

n

k

nk

=∑ 2 1n−

Se é a fração da demanda do cliente i , atendida a partir da atividade , isto é,

se

ijx j

( )1i

,dij ijx = ϖ tem-se que ( ) ( )i j ij ij j ij ijt x p td p ϖ+ = +

j

e c d é o custo

total de atendimento do cliente i a partir da atividade . As m restrições

(ij i j ijp t= +

j

),ij idϖ =∑

passam a i e trocando ,Ii∈ 1,ijjx =∑ ,I∈ ja por nas n restrições 2.3 obtêm-se i

id∑


29

( ) 0.i j ijid y x−∑

m ij

Estas podem ser desagregadas nas m restrições 1.3. Com isso,

chega-se ao modelo 1.1 a 1.5.

n×

i I∀ ∈

{ , ,I J i n= = … } ,

De acordo com Efroymson & Ray (1966), apesar da restrição no modelo

1.1 a 1.5 não obrigar, necessariamente, que x , , na solução ótima,

dos x são iguais a 1 e todos os outros iguais a zero. Isto ocorre porque para qualquer

especificação inteira dos

0ijx

J{ }0 1,ij ∈ , j∈

jy ’s, os x ’s ótimos podem ser determinados diretamente,

permitindo que cada cliente seja atendido pela atividade aberta mais próxima.

ij

O custo total de uma solução ótima em relação a um dado subconjunto X de

atividades abertas, é, portanto, Assim, a solução do problema é

reduzida à identificação de um subconjunto X que minimiza o custo total.

,J⊂

min .ij jj Xi I j Xc

∈∈ ∈+∑

J⊂

f∑

∈

Uma alternativa para as m restrições 1.3, consiste em agregá-las em n

restrições da forma n y , onde

n×

0, jj j iji

x J−∑ jn é o número de clientes que podem

ser supridos a partir da atividade .j

Os algoritmos considerados mais eficientes para o problema de localização não-

capacitado são os de Erlenkotter (1978) e Bilde & Krarup (1977), baseados num

procedimento dual ascendente5. A solução dual viável obtida gera um limite inferior para o

ótimo do problema. As condições das folgas complementares e a solução dual são usadas

também para construir uma solução viável do problema que produz um limite superior para

o ótimo. O procedimento dual ascendente é, então, combinado com um algoritmo do tipo

Branch and Bound, de modo que a solução ótima é sempre encontrada. As rotinas do tipo

dual ascendente geralmente fornecem limites muito justos, que asseguram uma pequena

expansão da árvore de busca do algoritmo de Branch and Bound.

O modelo do problema puro das -medianas de uma rede pode ser obtido fazendo

acrescentando ao modelo 1.1 a 1.5 do problema de localização a

relação que restringe a p o número de atividades a serem instaladas na rede, e eliminando

os custos fixos na função objetivo.

p


30

{ }

3 1

1, 3 2

, 3

0, , 3 4

0 1 , , 3 5

( . )

( . )

( . )

( . )

, (

ij iji j

ijj

jjj

jj ij

ij

Minimize Z d x

Sujeito a x i I J

x p

x x i I j J

x i I j J

=

= ∈ =

=

− ∈ ∈

∈ ∈ ∈

∑∑

∑

∑ 3

. )

onde d é uma matriz quadrada de ordem n em que cada d i é a distância (não-

negativa) entre os vértices i e da rede, e

ij ,ij ,j≠

j 0.jj =

ijx =

d é a matriz de alocação, tal que

se o vértice i é alocado à mediana , e caso contrário.

ijx

0,1ijx = j

No problema generalizado de -medianas com custos fixos, além de acrescentar à

função objetivo a parcela referente aos custos fixos, troca-se a restrição 3.3 por

O problema das p -medianas é tratado por Narula et al. (1977), Galvão

(1980), Christofides & Beasley (1982), Coelho & Capitivo (1984), Mirzaian (1985), entre

outros. O problema dos p -centros é estudado por Hakimi (1964), Minieka (1977), entre

outros.

p

1 .jjjx p∑

3.3.3. Relaxação do problema de localização linear e estrutura facial do politopo

Um conjunto do tipo é chamado de poliedro, onde

é um sistema de m desigualdades com n variáveis. Um politopo é um poliedro

limitado, isto é, tal que

{, :nm nX x Ax= ∈ }b

Ax b

j jb≤ ,j = …ja , para todo x≤ 1 ., ,j n

De acordo com Rockafellar (1970), uma coleção de pontos x x

é dita afim independente se, e somente se, os vetores (

0 1 2 3, , , , nx x ∈…

) ( ) ( )1 0x x 2 0 3 0, ,x x x x− − − …,

forem linearmente independentes.

5 O procedimento dual ascendente é uma heurística para a solução da relaxação de programação linear do problema de localização


31

Um poliedro X com, no máximo, k pontos afim independentes, tem

dimensão k

,m n 1+

.

j ij

a x b∑

, .m n

é uma desigualdade válida para se ela é satisfeita para todo

,m nX

x X∈

Uma face de X é um subconjunto de soluções viáveis para Ax que satisfaz

algumas das restrições como igualdades; ou seja, é um conjunto

,m n

j

,b

, :m n ij

f X x b = ∩

∑a x= .

Se j ij

a x b∑ é uma desigualdade válida para e se ,m nX ,j ij

a x b=∑

,X n

para k

pontos afim independentes, ( ) a igualdade ,,m nx X∈ ( )0 1 ,m nk− dim

j ibj

a x∑ = descreve uma face de X de dimensão k ,m n 1.−

Um ponto extremo ou vértice de X é qualquer face sua de dimensão 0 (zero) e

uma aresta de é qualquer face deX de dimensão 1. Se a dimensão deX é k ,

qualquer face de dimensão k de é uma faceta de

,m n

,m n,m nX ,m n

1− ,m nX , .m nX

Guignard (1980) constrói uma família de vértices fracionários do politopo da

relaxação do problema de localização, e gera vários cortes válidos para eliminá-los,

provando que esses cortes são facetas. Além disso, estudam-se famílias de problemas de

localização com grandes gaps de dualidade e apresenta as facetas específicas que zeram o

gap dual. Cho et al. (1981) e Cornuejols & Thizy (1982) também estudam outras

propriedades da estrutura facial do politopo da relaxação do problema de localização.

Muitos testes computacionais indicam que no caso do problema das -medianas

freqüentemente as relaxações de programação linear fornecem boas aproximações para os

correspondentes modelos de programação inteira. Segundo Erlenkotter (1978), Schrage

(1975) e Toregas et al. (1971), as relaxações de programação linear para estes problemas

de localização freqüentemente alcançam as soluções ótimas. O procedimento dual

ascendente fornece uma maneira de utilizar as relaxações do problema de localização. Uma

outra forma consiste em resolver diretamente as relaxações de programação linear

p


32

utilizando o método simplex. Schrage (1975) obteve bons resultados com uma versão

especial do algoritmo simplex na solução de relaxações de programação linear do

problema de localização. Uma dificuldade na solução destes problemas surge do fato de

que os problemas lineares com restrições de limites superiores variáveis, do tipo x y ,

freqüentemente são muito degeneradas. Todd (1982) apresenta uma especialização

alternativa do método simplex que contorna o problema da degeneração.

ij j

3.3.4. Base histórica dos algoritmos para o problema de localização de atividades

Os algoritmos construídos para resolver os problemas de localização de atividades

apresentam eficiência variada. Certos algoritmos exatos, quando atuam sobre instâncias de

tamanho considerável, exigem um tempo de execução proibitivo, o que inviabiliza a sua

utilização prática na solução de problemas de grande porte. Nessas situações, uma

alternativa viável é a construção de heurísticas que produzem soluções aproximadas e,

algumas vezes, até soluções ótimas. A avaliação dessas heurísticas geralmente é feita pela

análise da qualidade das soluções que elas produzem, como também pelo exame das

condições sob as quais elas atingem o ótimo.

Se a heurística tem um bom desempenho para muitas instâncias do problema, ou

seja, mantêm a margem de erro dentro de limites de tolerância, há uma excelente razão

para dar preferência a tais métodos em lugar de algoritmos exatos de alto custo

computacional.

Muitos algoritmos procuram pela solução através de uma seqüência de ações

locais ótimas. Em algumas circunstâncias, isto leva a bom termo, em outras não.

A heurística gulosa, que procura pela solução global através de escolhas locais e

criteriosas na vizinhança dos pontos, foi usada para resolver problemas de localização sob

duas grandes motivações:

1) No caso de problemas de porte muito grande, cujas soluções não podem ser obtidas por

outro processo mais elaborado (relaxação, decomposição, Branch and Bound, etc.)

2) Mesmo quando esses problemas podem ser resolvidos por procedimentos bem

elaborados, a solução inicial precisa ser produzida por outro algoritmo. Nesse caso, a


33

heurística gulosa é uma opção excelente para prover a solução inicial, limite superior

para a solução ótima.

3.3.4.1 Relaxação lagrangeana

A metodologia da relaxação lagrangeana baseia-se na substituição do problema

original por outro com mais variáveis e uma quantidade menor de restrições, de solução

mais fácil. Em muitos casos, as soluções produzidas são aproximações para o ótimo, ou

então, são limites inferiores, no caso de problema de minimização, para a solução ótima.

Tal método constitui uma alternativa para as relaxações de programação linear, de

problemas discretos, que geram limites para os algoritmos do tipo Branch and Bound.

Definição 3.2: Um problemaPβ é uma relaxação do problema Pα , se V P( ) ( ),V Pα β⊂

onde V P é o conjunto de soluções viáveis do problema , e ( ) P

( )( )

( )( ),P P

x V P x V PMínimo f x Mínimo f x

β αβ α∈ ∈

ñ

onde ( )Pf x é a função objetivo do problema P .

A idéia geral da relaxação lagrangeana aplicada a modelos de programação linear

discreta, consiste em decompor o conjunto de restrições Ax do problema dado por bú

( )

0,

( )

j

P Minimize f x cxSujeito a Ax b

xx j

=

∈ ∈

ú

J

2

em dois subconjuntos de restrições Ax e , da seguinte forma 1 1bú 2Ax bú


34

( )

1 1

2 2

,

0,

( )

j

P Minimize f x cxSujeito a Ax b

A x bxx j

=

∈ ∈

úú

úJ

)

J

em seguida, o problema relaxado é obtido

1 1

2 2

0,

( ) (

j

RL Minimize cx b AxSujeito a Ax b

xx j

+ −

∈ ∈

λ λú

ú

ondeλ é um vetor não negativo adequado. O problema RLλ é a relaxação lagrangeana de

em relação ao conjunto de restrições Ax e P 1 1bú 0.λ ú

1 1,bú

A decomposição das restrições

de P em dois grupos, Ax e A x é feita a partir da suposição de que A x

tem uma estrutura especial e que as restriçõesAx eventualmente, complicam a

solução do problema. Observa-se que toda solução viável de P é também viável para

1 1bú 2 ú 2,b 2 2,bú

RLλ , e, já que b A chega-se a 1 1− 0,x

( ) ( )T1 1cx b Ax c x f x+ − =λ ñ

para todo 0,λú o que mostra os valores objetivos deRLλ como limites inferiores para os

valores correspondentes de P .

Alguns resultados de dualidade são decisivos no contexto da relaxação

lagrangeana, já que a escolha do melhor 0,λú ou seja, aquele que produz o limite inferior

mais forte para a solução ótima, é apresentada através da solução do problema dual a

seguir.

Considerando inicialmente o problema primal

( )

( ) 0( )P Minimize f x

Sujeito a g xx X∈

ñ


35

ondeX ,n⊂ ( ) ( ) ( )( )T1 , , mg x g x g x= … , :f X→ e g X , 1, ,: .i i m→ = …

é não-vazio e convexo e as funções nele definidas são convexas. O dual de P

é definido por

X

( ) ( ){ }0( ) inf

x XD Maximize f x g x

∈+

λλ

ú

onde mλ∈ . Geoffrion (1971) mostra a equivalência entre esta definição de dual e o dual

da programação linear. A função a ser maximizada em D , ( ) ( ) ( ){ }infx Xf x g xψ λ λ

∈= + , é

uma função côncava.

Os problemas P e D sempre têm valores objetivos ótimos, que podem até

mesmo ser ± Certamente, se eles não têm soluções viáveis, seus valores objetivos não

serão finitos, a partir da convenção usual de que se então e o

.∞

.−∞

,X =∅ infX=+∞

supX =

Um par ( ),* *x ,λ com e*x X∈ 0,*λ ú satisfaz as condições de otimalidade

para P , se

1) x minimiza * ( ) ( )*f x g xλ+ em ; X

2) ( ) 0* *g xλ = ;

3) 0*λ ú ;

4) . ( ) 0*g x ñ

As condições de otimalidade são suficientes para que x seja ótimo em P . *

Definição 3.3: Um vetor nγ ∈ é um subgradiente da função convexa ,: nf → no

ponto ,n∈x se ( ) ( ) ( )f x f x x xγ+ −ú .nx∀ ∈


36

Geralmente f não é diferenciável. Isto provoca a necessidade de um conceito que

generalize o gradiente de uma função diferenciável. O subgradiente realiza essa função. O

conjunto dos subgradientes de qualquer função ,f em ,x que é representado por ( ),f x∂ é o

subdiferencial de f em .x Trata-se de um conjunto convexo e fechado.

Os algoritmos baseados na relaxação lagrangeana podem ser usados na solução de

problemas de localização como alternativa aos procedimentos do tipo dual-ascendente,

como o de Erlenkotter (1978).

3.3.4.2 Decomposição de Benders

A técnica de Benders consiste em utilizar a teoria da dualidade para resolver um

problema de programação mista através da solução de seu correspondente problema

inteiro. A dificuldade inicial com esta estratégia surge da impossibilidade prática de se

obter todas as restrições do problema inteiro, uma vez que cada restrição requer a

especificação do valor numérico de um ponto extremo ou raio extremo do poliedro

convexo associado ao problema. A infinidade de pontos e raios extremos corresponderia a

uma infinidade de restrições, resultando, portanto, em uma dificuldade computacional até

então intransponível. O algoritmo de Benders contorna o obstáculo, resolvendo o problema

inteiro após a geração de somente parte das restrições. O método resolve sucessivamente

um problema linear e um inteiro. A solução do programa linear produz um ponto ou raio

extremo e, portanto, uma única restrição para o problema de programação inteira; seu valor

objetivo ótimo fornece um limite superior para o ótimo do problema misto. Por sua vez, o

programa inteiro fornece um limite inferior não decrescente para o ótimo do problema

misto. A solução ótima do problema misto é obtida quando os dois limites coincidem. O

problema inteiro coincide com o problema misto, se nele estiverem presentes

simultaneamente todas as restrições.

Seja o problema misto dado por

inteiro0, 0

Minimize cx fySujeito a Ax By b

x yy

++ ú

ú ú


37

Para ,y que é um dado y o problema acima é escrito como um programa linear

dado por

,

0

( )P Minimize cxSujeito a Ax b By

x−ú

ú

onde a constante f y deve ser adicionada ao valor objetivo após a solução do problema

acima. O dual do problema P é:

0

( ) ( )D Maximize u b BySujeito a uA c

u

−ñú

Pode-se observar que o poliedro convexo V u independe de { 0:uA c= ú ñ } .y

Com isso, o máximo de ,( )By−u b comu ocorre em um ponto extremo de V ou

cresce ilimitadamente ao longo de um dos raios extremos deV qualquer que seja o valor

de

,V∈

,

.y Representando por u k os pontos extremos e por v q os

raios extremos do poliedroV temos que o máximo da função objetivo u b é

ilimitado, se para algum

, 1, ,k = …

,

,K , 1, ,= …

B−

,Q

,( )y

q

, ,y existir um q tal que, 0( )q By− >v b

Também, se o máximo de ,( )By−u b cresce ilimitadamente, pois para

algum existe um q para o qual a direção v satisfaz

,u V∈

,y , 0( )q By− > .v b Com isso,

são as condições necessárias e suficientes para a

existência de soluções do problema misto, uma vez que, pela teoria da dualidade, as

soluções viáveis do problema primal são dependentes de que o dual seja um problema

limitado. Assim, o dual pode ser escrito como

0, , ,( )qv b y q Q− …1=B

1, ,

0, 1, ,

( )

( )

k

q

k KMaximizeu b By

Sujeitoa v b By q Q=

−

− =…

…

O problema misto torna-se


38

1, ,

inteiro

0, 1, ,

0

{[ ( )] }

( )

,

k

k K

q

Minimize Máximou b By fy

Sujeitoa v b By q Q

y y

=− +

− =…

…

Fazendo Z M tem-se Z u k K 1, ,

,( )k

k Káximou b By fy=

= − +…

,( )k b By fy− + 1, , .= …

Assim, o problema misto é equivalente ao problema inteiro dado por

e inteiro

, 1, ,

0 , 1,

0

( )

( )

k

q

yMinimize Z

Sujeitoa Z u b By fy k K

v b By q Q

y

− + =

− =

…

…,

O problema acima é conhecido como problema mestre de Benders. Se V é vazio, o

dual não tem solução viável, e, portanto, o problema misto não tem solução ótima finita.

3.3.4.3 Um algoritmo de decomposição baseado na relaxação lagrangeana convexa do

problema mestre de Benders

O termo convexo indica que a relaxação lagrangeana é feita a partir de uma

combinação linear convexa de restrições do problema. Ou seja, os coeficientes

kλ utilizados como multiplicadores são tais que ∑ e 1kkλ = 0, 1, , .k k Kλ = … Ou

ainda, os coeficientes utilizados em cada iteração são os componentes de um vetor ,λ

projetado no simplex do dado por { } . ,K 1, , λ 1, 0, 1, ,k k Kλ= =… …( ):k kk

λ λ ∑

Além disso, observa-se o caráter dinâmico da própria relaxação lagrangeana, uma vez que,

no decorrer das iterações, o problema é relaxado iterativamente em relação às restrições ou

cortes de Benders gerados nas iterações sucessivas. Os vetores λ ’s de coeficientes ou

multiplicadores são projeções de vetores, sucessivamente, em subespaços do

paraK 1, ,K K+ …, 0.>

Dado o problema


39

{ }

1, ,

1 ,

0 0 1 , ,

( )

,

ij ij j ji I j J j J

ijj J

jj J

ij j

P Minimize Z c x f y

Sujeito a x i I

y p

x y i I j J

∈ ∈ ∈

∈

∈

= +

∈

∈ ∈

∑∑ ∑

∑

∑ ñ

ñ ñ ∈

temos que para um vetor y fixo, que satisfaça a restrição 1 de P se

transforma no problema de programação linear dado por

jj J

y∈∑ ñ p

1, ,

, ,

0, ,

( )L iji I j J j J

ijj J

ij j

ij

P Minimize c x f y

Sujeito a x i I

x y i I j

x i I

∈ ∈ ∈

∈

+

∈

− − ∈ ∈

∈ ∈

∑∑ ∑

∑ij j j

J

j J

O dual de P é o seguinte problema L

, ,

0,

0, ,

( )D ii I i I j J j J

i ij ij

i

ij

P Maximize u y v f y

Sujeito a u v c i I j J

u i I

v i I j J

∈ ∈ ∈ ∈− +

− ∈

∈

∈ ∈

∑ ∑∑ ∑j ij j j

∈

Sejam { 1:jy= = }A j o conjunto dos pontos potenciais abertos e { }0:

jy= =F j

o conjunto dos pontos potenciais fechados. De acordo com Magnanti & Wong (1981) e

Lasdon (1970), a solução de é dada por DP

( ) { }

{ }, ,

0, ,0, , ,

min :

max

i i j i ij

ij

ij i ij

u c c j A i Iv j A i Iv u c j F

= = ∈ ∈= ∈ ∈= − ∈ i I∈

f

Fornecendo um limite superior dado por Z c ( ),sup i j i ji I j A∈ ∈

= +∑ ∑


40

O problema mestre do algoritmo de Benders, onde foi omitida a restrição relativa

aos raios extremos – o problema é finito desde que se garanta pelo menos um 0,jy pois

o problema sendo não-capacitado, uma única atividade aberta poderá atender a todos os

clientes – é dado por:

≠

{ }

, 1, ,

1

0 1 ,

( )

,

M

k ki ij j j j

i I i I j J j J

jj J

j

P Minimize Z

Sujeito a Z u v y f y k K

p y

y j J

∈ ∈ ∈ ∈

∈

− + =

∈ ∈

∑ ∑∑ ∑

∑

…

Para produzir a relaxação lagrangeana de P , considera-se o seguinte

procedimento.

M

Dado 11, ,(K)λ λ λ= …

11, ,(K

, sua projeção é obtida em algum subespaço do tal

que o vetor

K

)λ λ λ= … resultante, esteja a uma distância mínima de λ e seja tal

que 1

1k

k

Kλ

=∑ 1,= 0, 1,k k 1, .Kλ = … Utilizando esse vetor λ , relaxa-se a primeira

restrição de e obtêm-se: MP

{ }

1

1

1

0 1 ,

( ) (

,

M

Kk k

M RLP k i j ij j jk i I i I j J j J

jj J

j

RLP Z Min Z u y v f y Z

Sujeito a y p

y j J

= ∈ ∈ ∈ ∈

∈

= + − + −

∈ ∈

∑ ∑ ∑∑ ∑

∑

λ )

Desenvolvendo chega-se ao problema

{ }

1 1 1 1

1 1

1 1 1 1

1 1

1 , 0 1 ,

( ) ( )

( )

,

M

K K K Kk k

RLP k i k ij j k j j ky i I k i I j J k k j J k

K Kk k

j k ij j k iy j J i I k i I k

j jj J

Z MinZ u v y f y Z

Min f v y u

Sujeitoa y p y j J

∈ = ∈ ∈ = = ∈ =

∈ ∈ = ∈ =

∈

= + − + − =

= − +

∈ ∈

∑∑ ∑∑∑ ∑ ∑ ∑

∑ ∑∑ ∑∑

∑

λ λ λ

λ λ

λ


41

A solução do problema acima é construída criando-se a função e o problema

seguintes

1

1( ) ,

Kk

j j k iji I k

f v j Jρ λ λ∈ =

= − ∈∑∑

{ }

1

0 1 ,

( )

,

j jj J

jj J

j

Minimize y

Sujeito a y p

y j

∈

∈

∈ ∈

∑

∑

ρ λ

J

Assim, o problema RL pode ser resolvido dado MP 0.λ Além disso, tem-se

que , MRLPz z 0λ . Ou seja, z é um limite inferior para o valor objetivo deP .

Quer-se agora escolher o

MRLP M

0λ que, depois de projetado no vetor 0,λ tal que

produza o melhor limite inferior para P . Ou seja, quer-se resolver o

problema dual lagrangeano

1,kλ =k∑ M

0

( ) ( )M MD RLPD z Max

Sujeitoa

= z λ

λ

onde

{ }

1

0 1 ,

( ) ( )

,

MRLP j j i ij jj J i I i I j J

jj J

j

yz Min f y u v

Sujeito a y p

y j J

∈ ∈ ∈ ∈

∈

= + −

∈ ∈

∑ ∑ ∑∑

∑

λ λ y

3.4. Problemas de localização dinâmica

Na localização de atividades em rede, é freqüente o caso em que, no decorrer do

tempo, não há modificação de posição das atividades instaladas em pontos escolhidos

como solução prévia do problema. Estes são os problemas estáticos de localização. Muitos

trabalhos focam as formulações estáticas, tais como Plastria (2001), Boffey & Narula


42

(1997), Hansen et al. (1994), Durrer & Slater (1977), Church & ReVelle (1976), entre

outros

O problema de localização em que a posição dos pontos utilizados para instalação

de atividades varia discretamente com o tempo é denominado problema dinâmico de

localização.

No problema estático de localização puro, procura-se regionalizar a rede em função

dos pontos eleitos, definindo um plano ótimo de transporte associado ao processo de oferta

e demanda de bens e serviços (atividades) existentes nos nós da rede.

No problema estático de localização de p -medianas em rede, o objetivo é o

mesmo, só que se procura atingi-lo mantendo controle sobre o número de atividades (não

mais quep ) a serem instaladas na rede. É um problema mais restrito.

Um problema dinâmico de localização de -medianas em rede é proposto em

Paula Junior (1986). Neste trabalho, além da restrição acima, mantém-se um certo controle

sobre a regionalização da rede, com características alternativas, seguindo a orientação das

peculiaridades do processo produtivo, ou do sistema de consumo, ou de ambos, existentes

na região para a qual a rede é uma conveniente abstração. Em alguns casos existe uma pré-

regionalização da rede que não pode ser destruída pelo algoritmo.

p

3.4.1. Um problema específico de localização dinâmica

Em Paula Junior (1986) é definido, resolvido e aplicado um tipo específico de

problema de localização dinâmica de atividades. Neste trabalho, a abstração da região para

a qual é conduzida a otimização de instalação de atividades é chamada de rede essencial.

Os nós ou vértices da rede essencial são os pontos de demanda e/ou oferta de bens e

serviços (atividades) da região.

O conjunto de nós da rede essencial é representado por I e o conjunto de nós

potenciais (candidatos em potencial para instalação de atividades) por J

,

( )J I⊆ .

O conjunto I de nós da rede essencial, é particionado, para fins de execução do

processo produtivo, em, no máximo, T subconjuntos. A escolha dos subconjuntos que

formam uma partição de I é feita dinamicamente através de um processo de tomada de

decisões seqüenciais.


43

é o conjunto de estágios do sistema dinâmico de decisões seqüenciais

referido. Cada estágio é uma coleção de pontos alternativos de eventual reinício do

processo produtivo.

{1, ,S = … }T

}K t

}

S é o conjunto dos estados do estágio t . Cada estado de um estágio

corresponde a um ponto particular da coleção de pontos alternativos que formam o estágio.

{1, , ( )t = …

é um estado genérico k do estágio t , e d k é uma decisão associada ao estado

genérico k do estágio t .

tk ( )t

é um conjunto de decisões admissíveis que podem

ser tomadas no estado k do estágio t . Em cada estado é tomada uma decisão sobre a

duração (ou extensão) do processo produtivo a partir daquele ponto (estado).

( ){ ,:t t ttkD d k k S t S∈= ∈

Cada decisão está associada a um retorno que corresponde ao custo mínimo de

execução do processo produtivo com a duração (ou extensão) proveniente da decisão

tomada.

O custo total quando se vai de um estágio a outro é dado por uma função de

transição aditiva que fornece a soma dos custos de execução do processo produtivo nos

estágios considerados.

Um mesmo estado e uma mesma decisão podem ocorrer em mais de um estágio.

Entretanto, o estado poderá ser atingido e a decisão poderá ser tomada uma única vez no

decorrer de todo o processo. Em cada estado toma-se uma única decisão.

Definidos o estágio inicial e o estado inicial, com as correspondentes decisões

associadas, diz-se que um estágio, a partir do segundo, foi alcançado quando algum de seus

estados foi atingido através de uma decisão tomada no estágio anterior. Nesse processo de

tomada de decisões seqüenciais, nem todos os estágios na solução necessariamente são

alcançados. Um estado é dito terminal quando nele não é tomada nenhuma decisão e,

portanto, cessa aí o processo decisório.

O problema dinâmico de decisões seqüenciais que é definido consiste em

determinar, dentro de cada estágio alcançado, o estado mais indicado, e dentro do estado

escolhido, se ele não é terminal, determinar a melhor decisão a ser tomada. Em um estado


44

não terminal de um estágio considerado, toma-se uma decisão que vai conduzir a um outro

estado de um estágio seguinte, que não é necessariamente o estágio imediatamente

seguinte. O processo continua até que se atinja, em algum estágio, o estado terminal.

3.4.2 Outros problemas de localização dinâmica

Inicialmente, Ballou (1968) reconhece a limitada aplicação de modelos estáticos.

Nessa abordagem, tenta-se localizar um único depósito de forma que os lucros sejam

maximizados ao longo de um horizonte finito de planejamento. A programação dinâmica é

utilizada para determinar o melhor programa para abrir algumas atividades como uma

estratégia quase ótima de localização e relocalização no período de tempo.

Wesolowsky (1973) considera o problema de localização de uma única atividade

sem restrições sobre um horizonte finito de planejamento com custos explícitos de

relocalização. Uma formulação de programação inteira binária da função objetivo é

apresentada e procedimentos de enumeração são sugeridos para resolvê-lo.

Sweeney & Tatham (1976) ampliam o conjunto de locais para localizações

potenciais. As melhores soluções em cada período são encontradas através de um

procedimento iterativo de resolução de programas inteiros com decomposição de Benders’.

O conjunto expandido de locais para localização potenciais em cada período é usado em

um programa dinâmico para determinar uma estratégia ótima de localização e

relocalização.

Com o objetivo de avaliar os procedimentos heurísticos de busca por soluções

próximas ao ótimo, Erlenkotter (1981) compara a performance de várias heurísticas sobre

um determinado problema de localização dinâmica. Em seguida, examina-se um problema

capacitado de minimização de custos, com intervalos de tempos discretos.

Van Roy & Erlenkotter (1982) formulam um problema de localização dinâmica de

atividades não-capacitadas, no qual se deseja selecionar o momento de estabelecer

atividades em diferentes localizações, de forma a minimizar os custos descontados totais,

que incluem os custos de localização e operação das atividades e também os custos totais

de produção e distribuição. A formulação apresentada permite a abertura de novas

atividades e o fechamento de atividades existentes. Um procedimento Branch and Bound é


45

proposto com a utilização de limites inferiores obtidos através da resolução de problemas

relaxados (PL) com um método heurístico dual ascendente.

Gunawardane (1982) considera o problema de localização aplicado ao setor

público. O autor estuda vários problemas de cobertura nos quais as atividades são

localizadas (e relocalizadas, se necessário) sobre um horizonte de planejamento. O autor

apresenta modelos expandidos, para o problema de cobertura máxima e para o problema de

cobertura de um conjunto de localizações, em um horizonte de planejamento de T

períodos.

Wesolowsky & Truscott (1975) examinam extensões dinâmicas de problemas de

localização/alocação. Nessa abordagem, permite-se que atividades sejam relocalizadas em

resposta às mudanças previstas na demanda. Um modelo de programação inteira e um

dinâmico são apresentados.

Drezner & Wesolowsky (1991) examinam a localização de uma única atividade em

uma cidade em crescimento com mudança de demanda ao longo do tempo, porém, de

forma determinística. O objetivo é encontrar uma localização para a única atividade que

minimize o custo esperado sobre o horizonte dado.

Shulman (1991) busca achar uma programação de tempo e a capacidade das

atividades de forma que o custo de capital descontado sobre o horizonte de tempo seja

minimizado. A classe do problema de localização dinâmica de atividade capacitada

considerada é aquela na qual as atividades disponíveis têm capacidades finitas, e o número

de tipos destas atividades é relativamente pequeno, de forma que uma expansão de

tamanho não possa ser modelada por variáveis contínuas. O autor formula o problema

como um problema de otimização combinatória que permite a consideração de mais do que

um tipo de atividade e achar o mix ótimo de atividades em cada localização. Também é

apresentado um algoritmo baseado na técnica de relaxação lagrangeana para resolver tal

problema.

Hinojosa et al. (2000) tratam de um problema de localização multiperíodo onde se

deseja estabelecer dois diferentes níveis de distribuição. O modelo proposto minimiza o

tempo de atendimento das demandas de todos os clientes ao longo do horizonte de

planejamento enquanto satisfaz os requerimentos de capacidade das plantas de produção e

depósitos intermediários. Uma relaxação lagrangeana é proposta para resolver o problema,


46

juntamente com um procedimento heurístico que constrói soluções viáveis a partir de

problemas relaxados.

3.5 Problemas de localização multiobjetivo

Até poucas décadas atrás, os problemas de tomada de decisões abordados através

de programação matemática eram modelados principalmente com apenas um único

objetivo. Lin (1980) diz que o objetivo único de maximizar lucros tem sido seriamente

questionado e que existem evidências de que na prática não se tem como objetivo apenas

maximizar lucros. Muitos problemas reais nas indústrias, negócios, organizações

governamentais e não-governamentais incluem uma variedade de metas e objetivos

conflitantes. Atualmente, grande atenção tem sido dada aos problemas de múltiplos

objetivos, como também há um reconhecimento crescente de que muitos problemas de

localização são inerentemente multiobjetivo (CURRENT et al., 1990; PELEGRIN &

FERNANDEZ, 1988; NIJKAMP & SPRONK, 1979).

Segundo Delgadillo (1997), ReVelle et al. (1981) foi um dos primeiros trabalhos a

analisar a necessidade de uma abordagem multiobjetivo para o problema de localização de

atividades usando otimização combinatória. O problema multiobjetivo é formulado como

um problema de min-sum, ou seja, como um problema de p-mediana.

Nijkamp & Spronk (1981) desenvolvem modelos baseados na análise tradicional de

Weber6, com o objetivo de trabalhar com algumas das limitações desta abordagem, tais

como os problemas de mais de uma atividade. Uma abordagem interativa é sugerida para

ser aplicada ao problema multiobjetivo de Weber modificado.

Ross & Soland (1980) tratam das questões multiobjetivo através de um modelo para

selecionar os locais para a instalação de atividades públicas, a fim de servir a um grupo de

clientes localizados em pontos distintos. Para algumas combinações de objetivos

específicos encontram-se todas as soluções eficientes. Em muitos outros casos, as soluções

eficientes podem ser encontradas através de solução paramétrica de um problema de

designação com restrições adicionais que podem ser incorporadas em um algoritmo

existente para problema de designação.

6 Weber (1909) considera o problema de localização de uma única atividade, de forma a minimizar a distância total entre esta atividade e um conjunto de clientes distribuídos espacialmente.


47

As importantes questões e variáveis do mundo real que são relacionadas aos

problemas de localização de atividades foram investigadas por ReVelle & Laporte (1996).

Novos problemas e modelos são sugeridos, todos possuindo relevância prática. Entre as

sugestões, está o problema de múltiplos objetivos.

O problema de localização de plataformas de produção de petróleo, como também

dos poços produtores, é tratado por Cortes (1998). Um modelo multiobjetivo é proposto

para abordar de forma mais realista o problema, cujos objetivos são: minimizar os custos

de construção/instalação das plataformas e os custos de conexão do poço à plataforma;

maximizar a produção de petróleo de um dado campo petrolífero; e, minimizar o impacto

de possíveis danos ambientais. Um problema monobjetivo auxiliar é construído

considerando a função escalarizada ponderada aumentada de Tchebychef para definir o

objetivo, tem-se o seguinte problema:

( ){ } ( )1 1

ρ,...

min max :i i i i ii k i k

c x Z c x Z x Sλ=

− + − ∈∑

onde ( )1,.., kkZ Z Z= ∈ é um ponto de referência e são parâmetros

fixos.

1 κλ , ..., λ ,ρ > 0

Para auxiliar a resolução de tal problema é apresentado um algoritmo interativo,

baseado no método de enumeração implícita, que determina um conjunto de soluções

eficientes para serem avaliadas pelo decisor.

3.6. Problemas de localização dinâmica multiobjetivo

A literatura disponível sobre decisões de localização é grande, mas existem

relativamente poucos artigos que tratam simultaneamente das abordagens dinâmica e

multiobjetivo7.

Um dos primeiros trabalhos foi publicado por Bitran & Lawrence (1980), no qual

considera-se a localização de escritórios para serviços regionais. Esses escritórios

7 A técnica chamada de Programação Dinâmica Multiobjetivo que significa a aplicação da Programação Dinâmica a problemas apenas multiobjetivo, tal como em Li & Haimes (1980) e Tauxe et al. (1979), não corresponde à abordagem dinâmica multiobjetivo tratada no presente trabalho.


48

funcionam como centros administrativos que dão suporte às vendas e ao processamento

das reclamações. A localização é determinada através de um modelo de programação

multiobjetivo linear 0-1. Os critérios são relacionados à distância entre o escritório e seus

clientes e o custo de operação e investimento. As restrições tratam de considerações

econômicas e operacionais. Esse problema é resolvido a partir do procedimento descrito

em Bitran (1979).

Schilling (1980) considera uma abordagem alternativa para resolver problemas de

localização dinâmica de atividades, inspirado pela necessidade dos setores públicos instalar

atividades. Em tal trabalho, considera-se especialmente uma formulação de problema

multiobjetivo de cobertura máxima, e busca-se um conjunto de boas soluções, da qual o

decisor poderá selecionar alguma destas para implementar. O modelo apresentado combina

T problemas de cobertura máxima, um para cada período em um horizonte de tempo. O

autor sugere abordagens multiobjetivo para gerar um conjunto de soluções eficientes para o

decisor, tais como os métodos ponderado, de restrição e simplex multiobjetivo.

A abordagem multiobjetivo para o problema de localização dinâmica também é

utilizada por Min (1988), que considera a expansão e a relocalização de bibliotecas em

uma área metropolitana. O critério considerado na escolha das localizações das bibliotecas

inclui a cobertura da população, a proximidade de cada comunidade e a acessibilidade das

rotas de transporte ou áreas de estacionamento. É formulado um modelo de localização de

variáveis discretas baseado na programação por metas nebulosas (fuzzy).

Abo-Sinna & Hussein (1994) desenvolvem uma técnica para resolver problemas

que envolvam objetivos conflitantes de características dinâmicas através de uma

decomposição paramétrica que usa a abordagem de norma ponderada. Os autores

consideram o caso particular de um problema convexo, separável e monótono. Uma

abordagem de programação dinâmica associada a abordagem de norma ponderada é

aplicada para caracterizar as soluções eficientes daquele problema. Pelo uso de

determinadas relações ponderadas entre as funções objetivo, pode-se encontrar um

conjunto de soluções eficientes do problema.

Abo-Sinna & Hussein (1995) complementam o trabalho desenvolvido por Abo-

Sinna & Hussein (1994) através da consideração de uma relaxação da suposição de

convexidade. Os autores apresentam um algoritmo para geração de soluções eficientes de

problemas multiobjetivo, baseado no princípio de otimalidade em programação dinâmica.


49

Assumindo a separabilidade e monotonicidade do problema, uma equação funcional geral

de programação dinâmica é derivada pelo uso da técnica de ε restrição. Essa abordagem

consiste na manutenção de um objetivo como principal e no tratamento dos objetivos

restantes como restrição, tendo cada uma destas restrições um limite superior ε, cuja

escolha de valores interferirá na geração do conjunto de todas as soluções eficientes.

Melacharinoudis & Min (2000) consideram a desativação e a relocalização de

fábricas/depósitos em um ambiente de mudanças. É formulado um modelo multiobjetivo

dinâmico inteiro misto, cujos objetivos, que foram estabelecidos a partir de potenciais

fatores locacionais, são os seguintes: maximizar o lucro total, minimizar o tempo total de

acesso entre a fábrica/depósito e seus fornecedores e seus clientes, e maximizar o

recebimento de incentivos. Os autores utilizam o método de ponderação de objetivos e um

caso real é resolvido através do software LINGO.

CAPÍTULO 4

FATORES LOCACIONAIS 4.1 Considerações iniciais

Os objetivos de um problema de localização dinâmico multiobjetivo podem ser

estabelecidos a partir de fatores locacionais (MIN & MELACHARINOUDIS, 1999). Tais

fatores podem ser definidos como variáveis que influenciam a decisão locacional do

empresário (MALECKI, 1997), como também afetar a habilidade de uma localidade em

atrair e reter atividades econômicas (BLAIR, 1995). Listas de fatores locacionais podem

ser encontradas em Kowalska & Funck (2000), Rees & Stafford (1986) e Lee et al. (1981).

4.2 Importância dos fatores locacionais

Cada decisão pode ser influenciada por uma variedade de fatores locacionais,

inclusive com diferentes níveis de intensidade. A importância desses fatores pode depender

do tipo e do porte da atividade econômica, da abrangência do estudo (macrolocalização ou

microlocalização), do período de tempo considerado na análise (presente ou futuro) e do

setor interessado (investidor público ou privado), entre outros.

De acordo com Hoover & Giarratani (1999), o meio mais comum de se medir o

grau de importância relativa dos fatores locacionais é o método mais direto, ou seja,

através de consulta ao decisor. Podem ser utilizados questionários contendo uma lista de

fatores que devem receber uma avaliação com relação à importância relativa através de

adjetivos (por exemplo, “excepcionalmente importante”, “muito importante”,

“indiferente”, “pouco importante”, “sem importância”, e assim por diante) ou por algum

tipo de sistema de pontuação simples que utilize uma escala de preferências.

CAPÍTULO 4 – FATORES LOCACIONAIS

51

Os fatores locacionais similares dentro de grandes regiões, tais como clima e custos

de energia, são chamados de macrolocacionais. Os fatores que variam em um nível

microgeográfico de detalhes são chamados de microlocacionais, e geralmente são menos

importantes em um estágio inicial de análise, por exemplo, acomodações satisfatórias

podem ser obtidas em qualquer lugar dentro de quase todas as regiões. Tais fatores são

mais representativos na seleção de uma comunidade específica dentro de uma região

(BLAIR, 1995).

Na análise locacional devem ser considerados tanto os fatores que afetam as

operações no momento atual, como também os que podem se tornar importantes no futuro.

De acordo com Blair (1995), a velocidade com que os fatores locacionais se tornam

expressivos pode ser compreendida pela análise das mudanças no fim do século passado.

Durante este período, qualidade de vida e questões ambientais tornaram-se foco de

interesse. Mudanças tecnológicas, tais como comunicação global de satélite e tecnologias

de transporte de massa, também passaram a influenciar as escolhas locacionais. De forma

similar, mudanças da importância dos fatores podem ser antecipadas. Contudo, antecipar

quais as mudanças que podem afetar uma escolha locacional é uma questão mais

complexa. Por causa da natureza de longo prazo dos problemas de localização, o decisor

deve estar orientado para o futuro e avaliar tendências.

A escolha locacional dependerá da natureza do setor interessado. No setor privado

o principal interesse é o de obter o menor custo ou o maior lucro para os proprietários,

enquanto que no setor público o interesse é o maior benefício ou o menor custo para a

sociedade (GALVÃO et al., 1999; REVELLE et al., 1970). Portanto, a definição do tipo de

decisor poderá indicar a tendência da localização. Quando o decisor é uma empresa

privada, as decisões locacionais são orientadas à instalação de atividades econômicas em

locais que proporcionam maior viabilidade econômica e rentabilidade. Por outro lado,

quando o decisor é o poder público, normalmente as decisões locacionais são direcionadas

às localizações que fornecem a melhor utilização dos recursos locais visando a satisfação

de objetivos de desenvolvimento regional, de desenvolvimento urbano e de diminuição dos

desequilíbrios regionais. Segundo Clemente (1998), as decisões locacionais são

fundamentais tanto para as empresas, que procuram as maiores vantagens em termos de

custos e receitas, quanto para o poder público, cujos objetivos de desenvolvimento

regional, de desenvolvimento urbano e de diminuição dos desequilíbrios regionais e inter-


52

regionais estão sempre em destaque. Nesse sentido, tais decisões têm muita influência

sobre os lucros das empresas e podem exercer influências positivas ou negativas sobre o

desenvolvimento de uma área ou região específica.

Considerando a natureza estratégica dos problemas de localização, é necessário

também examinar os objetivos relacionados ao planejamento urbano e regional, de forma a

levá-los em conta na decisão de investimento da empresa. Dessa forma, os seguintes

objetivos podem ser destacados: aumento do valor agregado empresarial, elevação do nível

de emprego e redistribuição na população, utilização dos recursos locais, criação de uma

estrutura empresarial diversificada e com capacidade de crescimento auto-sustentado e

aumento da competitividade (CLEMENTE, 1998).

Neste contexto, uma empresa tem que decidir se investe em uma região pouco

desenvolvida, levando em consideração que locais de salários baixos e impostos reduzidos

geralmente são carentes em infra-estrutura eficiente (PORTER, 1999a). Por outro lado, o

poder público tem que decidir quanto recurso destinar para uma região pouco

desenvolvida. Dessa forma, uma decisão está vinculada à outra, pois para a empresa

interessa saber se o governo pretende investir na localidade; enquanto que para o poder

público é importante saber se as empresas aproveitarão os resultados do investimento na

localidade, e, assim, proporcionar, por exemplo, o aumento de postos de trabalho. Nesse

caso, a satisfação dos interesses tanto do poder público quanto da empresa só poderá ser

alcançada com a contribuição de ambos.

4.3 Classificação dos fatores locacionais

Tradicionalmente, podem-se ter dois tipos de situações com relação aos fatores de

localização. A primeira é uma demanda de fatores pela atividade econômica, na qual

inclui-se a rapidez de acesso aos clientes, a qualificação da mão-de-obra, adequação do

local e imagem da empresa. A segunda situação é a oferta de fatores pela localidade, entre

os quais podem-se citar, o custo da mão-de-obra, do terreno, de transporte, de energia e as

competências locais. O confronto entre demanda e oferta de fatores locacionais orientará a

escolha da localização para a instalação da atividade econômica.

Uma outra classificação, proposta por Krajewski & Ritzman (1999), separa os

fatores de localização em dominantes e secundários. Os fatores dominantes são aqueles


53

derivados de prioridades competitivas (custo, qualidade, tempo e flexibilidade) e têm forte

impacto sobre as vendas ou custos. Os fatores secundários possuem pequena importância e

até podem ser ignorados caso existam outros muito mais importantes. Esta categorização

dependerá do tipo de empresa tratada e da importância dos fatores envolvidos na decisão.

Assim, fatores que são dominantes para uma empresa podem ser secundários para alguma

outra.

As escolhas locacionais podem ser orientadas tanto por fatores econômicos ou

técnicos (por exemplo, energia) quanto por fatores qualitativos relacionados ao julgamento

do decisor (por exemplo, qualidade do ambiente). MacCormack et al. (1994) classificam

os fatores locacionais em: quantitativos e qualitativos. De acordo com Krajewski &

Ritzman (1999), os fatores quantitativos são aqueles que podem ser medidos em unidades

monetárias, como, por exemplo, custo, distância; os fatores qualitativos são aqueles que

não podem ser avaliados em termos monetários, como, por exemplo, qualidade de vida,

qualificação dos trabalhadores, infra-estrutura local. Malizia & Feser (1999) destacam os

seguintes fatores qualitativos: a habitabilidade do local (qualidade de vida para os

empregados e especialmente para a gerência), o clima de negócios (freqüentemente

enfatizado pela postura do governo local e o grau de sindicalização da atividade) e

questões ambientais (o interesse pela qualidade ambiental razoável e a ameaça das

regulamentações ambientais de alto valor).

Segundo Kowalska & Funck (2000), nas escolhas locacionais da sociedade pós-

industrial, alguns fatores locacionais tradicionais dominantes, tais como custo de transporte

e custo de matéria-prima, têm sido substituídos por outros fatores, tal como acesso a fontes

de informação especializada. Em particular, para as instituições de pesquisa tecnológica,

pode-se desejar a presença de um ambiente criativo e a disponibilidade de fornecimento de

pessoal altamente qualificado. Em resumo, uma série de fatores soft ou quase-soft pode

tornar-se muito relevante.

Kowalska & Funck (2000) sugerem uma classificação dos fatores locacionais a

partir dos efeitos diretos e indiretos sobre a lucratividade. Os fatores que influenciam as

condições específicas de uma região por uma certa atividade produtiva através do impacto

direto sobre o lucro ou através de intervenção direta no mercado são tratados como fatores

locacionais hard. Todos os outros fatores que exercem apenas uma influência indireta e

não possuem impacto “visível” sobre o resultado econômico são denominados como


54

fatores soft. Em contraste aos fatores hard, que podem ser quantificados com certa

facilidade, os fatores soft são mais difíceis de serem medidos e avaliados.

Ensslin (1995) ressalta que todos os fatores considerados importantes para a tomada

de decisão, sejam eles tangíveis ou intangíveis, devem ser incorporados na análise.

Também devem ser consideradas as divergências de opiniões entre os diversos decisores

envolvidos, bem como os possíveis imprevistos que possam ocorrer na vida real.

Em Meyer-Stamer (2000) encontra-se uma diferenciação entre os fatores de

localização objetivos e os subjetivos, sendo que estes últimos são subdivididos em fatores

empresariais e pessoais. Alguns exemplos desses fatores são apresentados a seguir.

Fatores objetivos:

Posição geográfica em relação aos mercados de compra e venda;

Ligação à rede de transportes (em estrada, em ferrovia em água, no ar);

Ofertas e pedidos de empregos (nível salarial, disponibilidade de mão-de-obra

qualificada);

Disponibilidade de terrenos;

Custos de energia e meio ambiente;

Encargos municipais;

Ofertas promocionais (incentivos fiscais, subvenções, etc.).

Fatores subjetivos para a localização de empresas:

Clima econômico da cidade da região;

Imagem da cidade/região;

Contatos setoriais;

Universidades, instituições de pesquisa e tecnologia;

Ambiente inovativo da região;

Desempenho de associações comerciais e industriais.

Fatores subjetivos para a localização de empresas com relação às pessoas:

A qualidade residencial e seu ambiente;


55

A qualidade do meio ambiente;

A qualidade de escolas e outras instituições de formação;

A qualidade da infra-estrutura;

Valor recreativo;

4.4 Fatores mais relevantes

Alguns dos fatores de localização mais considerados nos trabalhos pesquisados são

tratados a seguir com maior detalhadamento.

4.4.1 Custo

Este é um dos mais tradicionais fatores de localização e é um dos mais importantes

para empresas do setor privado. Contudo, uma vantagem de custo pode não definir uma

escolha se outros fatores de maior importância estiverem envolvidos na decisão.

Os custos podem ser estimados, tanto para o período atual quanto para períodos

futuros, e podem se apresentar de duas formas, tangíveis e intangíveis. Os custos tangíveis

são aqueles que são rapidamente identificados e precisamente medidos. Custos desse tipo

podem incluir produção, trabalho, utilidade, material, taxas, depreciação, transporte (seja

de insumos ou de produtos), instalação, relocalização, entre outros. Os custos intangíveis

não são facilmente quantificáveis, podendo incluir qualidade da educação, transporte

público, atitudes da comunidade em relação à empresa, atitudes dos potenciais empregados

(HEIZER & RENDER, 2001). Um outro exemplo de custo intangível é o relativo aos

custos psicológicos de uma relocalização.

4.4.2 Proximidade da matéria-prima

Se a atividade econômica for uma indústria manufatureira que realiza uma ou mais

operações em relação a um suprimento de matérias-primas, existirá a preocupação da

indústria estar localizada em uma área próxima às fontes de suprimento. Uma das razões é

que o custo de aquisição das matérias-primas dependerá da localização da empresa. Dessa


56

forma, o grau de atração exercido pela matéria-prima dependerá do tipo e quantidade dos

recursos que assumem maior importância para a empresa.

As seguintes questões devem ser consideradas na avaliação: problemas de

transporte da matéria-prima, como a perda de peso ou volume; grau de perecibilidade da

matéria-prima; o valor da matéria-prima; custo de transporte; ou alguma razão estratégica

com o intuito de favorecer a região fornecedora de matéria-prima (HEIZER & RENDER,

2001).

4.4.3 Proximidade dos mercados consumidores

A influência da proximidade das fontes de matéria-prima para as empresas

modernas tem sido minorada, principalmente para as empresas baseadas em tecnologia.

Estall & Buchanan (1976) relatam que para o caso específico de uma refinaria de petróleo,

não há a exigência de instalação próxima ao local produtor de petróleo. Esta situação pode

ser justificada pelo fato de os derivados do petróleo representarem uma percentagem

relativamente elevada dos custos totais em comparação ao petróleo, a perda de peso no

beneficiamento ser relativamente pequena e a matéria-prima ser fluida. Assim, é mais

barato levar o petróleo até o ponto de refino do que distribuir os diversos derivados até os

vários centros de consumo. Nesse contexto, outros fatores, tais como proximidade de um

porto ou de mercados consumidores, teriam maior importância. A instalação próxima ao

local produtor de petróleo só poderia permanecer como uma opção válida no caso desta

localidade oferecer fatores que também são de grande importância (como, por exemplo,

isenção fiscal, impacto ambiental e competências locais), e assim haja a compensação das

avaliações negativas obtidas quando se consideram outros fatores.

Para algumas empresas é extremamente importante se localizar próximo aos

mercados consumidores, principalmente para prestadoras de serviços. No caso de

manufaturas, este fator é considerável quando o transporte do produto acabado é caro ou

difícil por causa do volume, peso ou fragilidade.

A localização próxima ao mercado também é conveniente quando o contato e a

interação com o cliente são essenciais. Podem ser citadas, as empresas que regularmente

fornecem produtos sob medida, as empresas que prestam serviços ligados ao processo

produtivo dos clientes e as empresas de manutenção.


57

4.4.4 Economias de aglomeração

O direcionamento para locais próximos aos concorrentes recebe diversas

denominações, entre elas, aglomeração, concentração e clustering. Esta tendência ocorre

freqüentemente quando recursos naturais, informação, capital e talento são encontrados em

determinada região. Por exemplo, o talento atrai empresas de software a se concentrar no

Vale do Silício e em Boston, locais que apresentam um grande fornecimento de jovens

graduados em Berkeley e Stanford na Califórnia e em Harvard e no MIT em Massachusetts

(HEIZER & RENDER, 2001).

Segundo Porter (1999b), clusters1 (grupos, agrupamentos ou aglomerados) são

concentrações geográficas de empresas de determinado setor de atividade e organizações

correlatas, fornecedores de insumos, instituições de ensino e clientes. Sendo que as

fronteiras de um cluster são definidas pelos elos e pela interdependência entre os diferentes

setores e instituições.

Uma característica marcante presente nos clusters é a existência tanto de

concorrência quanto de cooperação. Os concorrentes competem intensamente para vencer

e reter seus clientes. Mas a cooperação também está presente, em grande parte

verticalizada, envolvendo empresas de setores afins e instituições locais. A concorrência

convive com a cooperação, pois as duas ocorrem em dimensões diferentes e entre

participantes distintos (PORTER, 1999b). Uma rede de relacionamentos entre companhias,

agências governamentais e Universidades concentradas geograficamente, e atuando em um

campo específico, é possível de ser identificada nos clusters. Esta rede inclui fornecedores

de matérias-primas, equipamentos e serviços, bem como infra-estrutura adequada e acesso

aos canais de distribuição e aos consumidores (PORTER, 1999a).

De acordo com Ballau (1992), o fator aglomeração não possui natureza totalmente

econômica, pois indústrias e instituições tendem a se concentrarem e a se expandirem para

locais onde compartilham clientes, fornecedores, serviços públicos, atrativos sociais,

recursos comuns e interesses políticos. Estes benefícios, agregados aos de natureza mais

econômica, como proximidade de mercados ou fontes de suprimento, são o resultado de

1 Uma revisão de algumas explicações de como os clusters se formam pode ser encontrada em Meijboom & Rongen (1995).


58

forças de aglomeração. Tais forças são aquelas que incentivam a instalação da atividade

econômica em uma mesma região.

Os benefícios advindos da concentração (chamados de economia de aglomeração),

têm gerado vantagens competitivas sustentáveis que são compartilhadas pelas empresas

inseridas no cluster.

Uma contribuição para auxiliar a empresa a decidir sobre sua instalação em um

cluster é apresentada em Porter (1999a). Nesse trabalho, é feita a análise da vantagem

competitiva localizada através do chamado modelo de “diamante”, no qual os seguintes

determinantes interagem: i) estratégia, estrutura e rivalidade da empresa; ii) condições dos

fatores; iii) setores de apoio; iv) condições da demanda.

4.4.5 Características da localidade

A escolha locacional também pode ser influenciada pelas características do

potencial local de instalação. As seguintes características podem ser destacadas:

4.4.5.1. Disponibilidade de mão-de-obra

O suprimento de mão-de-obra é um fator de grande importância para as atividades

de base tecnológica. Demandam primordialmente por uma mão-de-obra qualificada e

especializada que esteja disponível na região, tais como, técnicos e operários

especializados, funcionários bilíngües, engenheiros e outros graduados, entre outros.

Mesmo se a localidade não possuir oferta deste tipo de mão-de-obra, deve ser considerada

a possibilidade de migração destes tipos de profissionais de regiões vizinhas para a

localidade considerada a fim de compensar sua deficiência.

4.4.5.2. Infra-estrutura local

Verifica-se, neste caso, se o potencial local para a instalação possui adequada rede

de transporte, abastecimento de água, disponibilidade de fornecimento de energia elétrica

em quantidade necessária, disponibilidade de conhecimento proveniente de Universidades

e de Centros de Pesquisa, entre outros. Nesta análise, também deve ser considerado o custo

para a obtenção destes serviços.


59

4.4.5.3. Tributação e incentivos fiscais

Atualmente, a tributação tem tido grande importância nas decisões locacionais. De

acordo com Estall & Buchanan (1976), as variações tributárias dentro de fronteiras

nacionais ou regionais podem definir a escolha locacional.

Doações de terrenos, subsídios e concessões relativas a impostos podem ser

adotadas com o intuito de atrair as atividades econômicas. Tais benefícios seriam o

resultado da parceria entre Estado e Município e podem variar ao longo de um período de

tempo. O propósito da concessão destes benefícios é evitar acentuados desequilíbrios

regionais e inter-regionais, além de incentivar investimentos privados em determinados

locais que estejam fora das áreas de alta concentração econômica e demográfica e que

possuem potencial para se tornarem centros de desenvolvimento. Espera-se também que

ocorra o efeito multiplicador de desenvolvimento pelas áreas vizinhas (ESTALL &

BUCHANAN, 1976).

Deve-se destacar que a concessão de incentivos por si só não é suficiente para

manter uma política de atração local que se sustente por longo período, pois seus efeitos

são questionáveis. Podem ser necessários, por exemplo, investimentos públicos em infra-

estrutura, capacitação da mão-de-obra, entre outros.

4.4.5.4. Qualidade de vida

A qualidade de vida proporcionada aos habitantes de determinado local também é

um fator locacional. É desejável que no local escolhido para a instalação da atividade

econômica se possa trabalhar e viver bem.

De acordo com Massan (2002), a qualidade de vida percebida por um lado pode ser

vista como um indicador ou causa de atração de um local, por outro lado pode ser tratada

como a conseqüência das condições observadas e uma medida que reúne os desejos e

expectativas dos indivíduos. Conseqüentemente, a qualidade de vida pode ser considerada

como uma composição de benefícios privados e públicos que é um

“meio”/“causa”/“entrada” e/ou “fim”/“efeito”/“saída”. Desta forma, uma definição

precisa de qualidade de vida é extremamente complexa. Apesar disto, é de aceitação quase

que absoluta que boas escolas, opções atrativas de recreação, eventos culturais e taxa

reduzida de criminalidade contribuem para a qualidade de vida de um determinado local.


60

A princípio, o fator qualidade de vida pode ser considerado secundário, porém, em

algumas situações, representa um fator diferencial de atração de atividades econômicas

(KRAJEWSKI & RITZMAN, 1999). Por exemplo, quando se quer escolher entre dois

locais economicamente viáveis, a preferência será por aquele com a melhor qualidade de

vida.

CAPÍTULO 5

ALGORITMO GENÉTICO 5.1 Algoritmo genético tradicional

Algoritmo Genético (AG) é um método heurístico1 de busca estocástica baseado no

processo de evolução biológica que favorece o alcance do ótimo global. Sua utilização é

adequada para resolver problemas complexos – tais como, otimização de funções

numéricas em geral, otimização combinatória, aprendizado de máquina, processamento de

imagem, robótica, etc – fornecendo soluções de boa qualidade em tempos computacionais

aceitáveis a partir de fácil implementação em computadores (GOLDBERG, 1989). Por esta

razão, os AGs têm apresentado grande popularidade no campo científico, entre os quais,

Moon et al. (2002), Sexton et al. (1999), Reeves (1996), Shaffer & Eshelman (1996), Wren

& Wren (1995), Mathias & Whitley (1992), Tam (1992), Davis (1991), Ulder et al. (1991).

No entanto, existe certa carência de estudos comparativos entre os AGs e outras técnicas

(REEVES, 1997); uma dessas poucas comparações é apresentada em Houck et al. (1996).

Para o caso dos problemas de localização podem ser citados: Aytug & Saydam (2002),

Jaramillo et al. (2002), Gong et al. (1999), Houck et al. (1996), Conway &

Venkataramanan (1994), Hosage & Goodchild (1986).

5.1.1 O diferencial dos algoritmos genéticos

De modo geral, algumas características que distinguem os AGs de outras técnicas

clássicas de busca e otimização são as seguintes (GOLDBERG, 1989):

1 Os AGs, assim como as técnicas Simulated Annealing e Busca Tabu, são chamados de metaheurísticas.

CAPÍTULO 5 – ALGORITMO GENÉTICO

62

Manipulam paralelamente um conjunto de soluções potenciais, chamado de população,

em vez de uma única solução;

Trabalham com uma codificação de um conjunto de parâmetros e não com os próprios

parâmetros;

Usam transições probabilísticas em vez de regras determinísticas;

Necessitam apenas de informação sobre o valor de uma função objetivo para cada

integrante da população de indivíduos, não utilizando derivadas.

A consideração de um conjunto de soluções potenciais em um mecanismo de

evolução induz a busca em diferentes áreas do espaço de solução, o que faz com que o

algoritmo não se prenda a extremos locais e favoreça a busca do ótimo global. No entanto,

a utilização dos AGs pode acarretar certa lentidão pelo fato de trabalharem com uma

população de soluções, além de haver a necessidade de ajuste de seus parâmetros para se

obter eficácia.

Os AGs pertencem a uma classe metodológica maior, a Computação Evolutiva ou

Evolucionária que considera que uma população de indivíduos pode evoluir de forma a

melhorar sua adequação ao ambiente. Tal classe engloba outras técnicas, tais como, a

programação evolutiva, as estratégias evolutivas e a programação genética (GOLDBERG,

1989).

5.1.2 Conceituação básica

O conceito de AG foi inicialmente tratado por Holland (1975) e popularizado por

Goldberg (1989), tendo sido inspirado no princípio de seleção natural de Charles Darwin

(1809-1882). Darwin, em seu livro “Sobre a origem das espécies por meio da seleção

natural”, faz uma das maiores contribuições à teoria da evolução, através da consideração

de que as espécies evoluem pelo princípio da seleção natural e sobrevivência do mais apto.

O mecanismo de evolução proposto por Darwin pode ser resumido nos itens descritos a

seguir:

Os indivíduos de uma mesma espécie mostram muitas variações na forma e na

fisiologia;


63

Boa parte dessas variações é transmitida aos descendentes;

Se todos os indivíduos de uma espécie se reproduzissem, as populações cresceriam

exponencialmente;

Como os recursos naturais são limitados, os indivíduos de uma população lutam por

sua sobrevivência e de sua prole;

Portanto, somente alguns, os mais aptos, sobrevivem e deixam descendentes. A

sobrevivência e a reprodução dependem das características desses indivíduos que, por

serem hereditárias, serão transmitidas aos seus filhos;

Através dessa seleção natural, as espécies serão representadas por indivíduos cada vez

mais aptos.

Outras definições básicas relacionadas aos AGs são:

Genótipo: cromossomo, a estrutura codificada;

Fenótipo: solução do problema real, estrutura decodificada;

Gene: conjunto de valores que expressam uma variável de decisão;

Alelos: possíveis valores que um determinado gene pode assumir;

Lócus: posição dos alelos no cromossomo.

Cada indivíduo da população é chamado de cromossomo (string de valores) e

representa uma solução para o problema, sendo o comprimento do cromossomo (lchrom)

definido pela quantidade de valores que o compõe. Essa representação, chamada de

codificação, dependerá da classe do problema que se deseja resolver e é uma das etapas

mais críticas na definição de um algoritmo genético. Atualmente, existem três tipos

principais de representações para os cromossomos: binária, inteira ou real, sendo que a

forma binária é a mais utilizada.

A habilidade de adaptação de um cromossomo a um determinado ambiente é

representada por uma medida de avaliação/aptidão (fitness). A aptidão pode ser definida

através do valor da função objetivo, do seu escalonamento ou pelo ranqueamento do

indivíduo na população.


64

Apesar da simplicidade, os AGs são suficientemente complexos para fornecer

poderosos e robustos mecanismos de busca adaptativa. Contudo, o resultado do uso desses

algoritmos dependerá da realização de dois procedimentos importantes:

1) Representação adequada das soluções possíveis do problema em forma de cromossomo

(codificação);

2) Determinação de uma função de avaliação de aptidão que possa fornecer para o

problema uma medida de importância de cada cromossomo gerado.

Deve-se destacar que estas são, justamente, as partes que relacionam um AG ao

problema a ser resolvido.

5.1.3 Funcionamento dos algoritmos genéticos

Existem diversas variações entre os AGs, porém, a estrutura geral é sempre a

mesma, podendo ser descrita da seguinte forma (ver JARAMILLO et al., 2002):

Etapa 0: Geração da população inicial de cromossomos;

Etapa 1: Avaliação da aptidão de cada cromossomo da população;

Etapa 2: Seleção dos cromossomos que produzirão descendentes;

Etapa 3: Geração de descendentes através de cruzamento e mutação;

Etapa 4: Repetir as etapas 1, 2 e 3 até que alguma condição de parada seja satisfeita.

O pseudocódigo a seguir descreve esta estrutura.

PPrroocceeddiimmeennttoo eevvoolluuttiivvoo ggeerraall::

IInníícciioo

gg ←← 00

iinniicciiaalliizzee PP((gg))

aavvaalliiee PP((gg))


65

eennqquuaannttoo ((nnããoo ccoonnddiiççããoo ddee ppaarraaddaa)) ffaaççaa

gg ←← gg ++ 11

sseelleecciioonnee PP((gg)) aa ppaarrttiirr ddee PP((gg--11))

aapplliiqquuee ooss ooppeerraaddoorreess ggeennééttiiccooss:: ccrruuzzaammeennttoo ee mmuuttaaççããoo

aavvaalliiee PP((gg))

ffiimm ddoo eennqquuaannttoo

ffiimm

onde P(g) é a população da geração g.

A população inicial dos AGs tanto pode ser gerada aleatoriamente como também

pode ser obtida através de algum processo heurístico. O importante é que a população

inicial seja distribuída dentro do espaço de soluções de forma abrangente.

O cromossomo, que é uma cadeia de símbolos, evolui através de sucessivas

iterações. Em cada iteração, que representa uma geração, é feita a avaliação dos

cromossomos usando alguma medida de avaliação/aptidão.

Para obter a geração seguinte, novos cromossomos, chamados de descendentes ou

filhos, são formados através dos operadores genéticos: seleção, cruzamento e mutação.

5.1.4 Operadores genéticos

5.1.4.1 Seleção

Seleção é o processo de escolha dos melhores indivíduos da população, sendo feito

geralmente a partir das medidas de aptidão. Os membros selecionados são utilizados para a

reprodução. Dessa forma, os indivíduos com maior aptidão têm maiores chances de se

reproduzirem e os menos aptos de serem descartados. Após várias gerações, a melhor

solução converge, e espera-se que seja o ótimo ou alguma solução próxima ao ótimo

(REEVES, 1997; GOLDBERG, 1989).

As estratégias de seleção mais utilizadas são: o método da roleta, os métodos de

ordenação linear e exponencial e o método de torneio. No método da roleta, cada indivíduo


66

da população recebe uma porção da roleta proporcional à sua medida de aptidão. O

lançamento da roleta é repetido lchrom vezes (comprimento do cromossomo), e, então, os

indivíduos sorteados são os selecionados para a reprodução. Nos métodos de ordenação

linear e exponencial, os indivíduos são ordenados decrescentemente pelas suas aptidões. A

cada indivíduo é atribuída uma probabilidade de seleção tomada de uma dada distribuição

que pode ser linear ou exponencial. O método de torneio realiza um torneio entre um grupo

de indivíduos escolhidos aleatoriamente. Aquele indivíduo que possuir maior aptidão é

selecionado (CASTRO, 2001; REEVES, 1997).

Feito o processo de seleção, os cromossomos escolhidos são combinados em pares

para realizar o processo de cruzamento e mutação. Em cada combinação, a partir de 2

cromossomos pais originam-se 2 cromossomos filhos.

5.1.4.2 Cruzamento

Cruzamento é o operador de troca de genes entre cromossomos da geração atual

que gera cromossomos filhos com características semelhantes às dos cromossomos pais. O

operador cruzamento é aplicado com uma probabilidade dada pela taxa de cruzamento pc;

no caso de não haver cruzamento, os cromossomos filhos serão cópias exatas dos pais. As

formas mais utilizadas de cruzamento são:

Um ponto: um ponto de cruzamento é escolhido aleatoriamente entre 1 e e a

partir deste ponto material as informações genéticas dos cromossomos pais são trocadas. A

Figura abaixo apresenta um exemplo deste tipo de cruzamento.

1lchrom −

Pai 1: 11110011 110000110011 Filho 1: 11110011 111111001100

Pai 2: 11001111 111111001100 Filho 2: 11001111 110000110011

Figura 5.1 Exemplo de cruzamento de um ponto.

Multipontos: é a generalização da troca de material genético dos pais, onde muitos pontos

de cruzamento são utilizados de forma que haja a troca de segmentos de informações

genéticas;


67

Pai 1: 1111 001111 00001100 11001111 11 Filho 1: 1111 111111 00001100 00111100 11

Pai 2: 1100 111111 11110011 00111100 11 Filho 2: 1100 001111 11110011 11001111 11

Figura 5.2 Exemplo de cruzamento de multipontos.

Uniforme: não utiliza pontos de cruzamento, mas através da probabilidade de cada bit ser

trocado entre os pais.

Pai 1: 11 11 0011 11 00001100 1100 1111 00 Filho 1: 11 00 0011 11 00001100 0011 1111 11

Pai 2: 11 00 1111 11 11110011 0011 1100 11 Filho 2: 11 11 1111 11 11110011 1100 1100 00

Figura 5.3 Exemplo de cruzamento uniforme.

5.1.4.3 Mutação

Mutação é o operador de modificação arbitrária de um ou mais genes dos

indivíduos escolhidos, sendo responsável pela introdução ou manutenção da diversidade

genética da população, visto que permite que o algoritmo manipule uma outra solução do

espaço de soluções. Este operador será aplicado em cada um dos bits com uma

probabilidade dada pela taxa de cruzamento pm de forma que os valores dos bits sejam

invertidos, ou seja, há a alteração de 0 para 1 ou de 1 para 0.

Antes: 11 0011001111 11 11 00 11

Depois: 00 0011001111 00 11 11 11

Figura 5.4 Exemplo de mutação.

5.1.4.4 Elitismo

Um outro operador genético, chamado de Elitismo, é uma variação do operador de

seleção, versão artificial da seleção natural, que permite a preservação das melhores

soluções. Uma elite genética pode guardar uma mesma quantidade (entre 1 a npop) de

melhores indivíduos ao longo das gerações para que não sejam destruídos pelos operadores

de Cruzamento e Mutação, ou perdidos se não forem selecionados para a reprodução. Esse


68

artifício é necessário, pois apesar do algoritmo genético ser considerado evolutivo no

sentido de melhoria a cada iteração, uma boa solução pode ser descartada em uma geração

e não reaparecer nas futuras gerações.

5.1.5 Parâmetros genéticos

Segundo Castro (2001), a eficiência e o funcionamento de um AG é altamente

dependente dos seus parâmetros de controle. A calibração destes algoritmos é fundamental

no equilíbrio entre intensificação da busca e diversificação de soluções para evitar a

convergência prematura do algoritmo. Alguns parâmetros necessários para a

implementação do AG são:

Tamanho da população;

Número máximo de gerações;

Probabilidade de ocorrência de cruzamento;

Probabilidade de ocorrência de mutação.

O tamanho da população define a quantidade de cromossomos presentes em cada

população e deve ser determinada experimentalmente, pois afeta o desempenho global e a

eficiência dos AGs. A manipulação de uma população de grande número de indivíduos

fornecerá uma maior diversidade de soluções, visto que apresentará uma grande cobertura

do espaço de soluções e, conseqüentemente, soluções globais, ao invés das locais, são

favorecidas. No entanto, o custo computacional será alto. Por outro lado, a manipulação de

uma população pequena geralmente não possui este tipo de problema, contudo, poderá

pecar por uma pequena cobertura do espaço de soluções.

O número de gerações define o tamanho do espaço de busca a ser coberto e também

deve ser determinado experimentalmente. Este número irá influenciar a quantidade de

indivíduos substituídos em cada geração. Uma grande quantidade de gerações substituirá a

maior parte da população, favorecendo a busca, mas, com possível perda dos indivíduos

mais aptos. Por outro lado, um valor baixo pode tornar mais lenta a convergência.

A taxa de cruzamento irá definir qual a probabilidade de haver cruzamento entre os

indivíduos selecionados na população. Quanto maior for esta taxa, mais rapidamente novos

cromossomos serão introduzidos na população substituindo a maior parte da população, o


69

que pode descartar indivíduos de alta aptidão. No entanto, a consideração de um valor

baixo poderá tornar a convergência muito lenta.

A taxa de mutação indicará a probabilidade de haver mutações das estruturas

selecionadas na população. Com uma taxa muito alta a busca se torna essencialmente

aleatória. Com uma taxa de mutação muito pequena se previne que uma dada posição

continue apresentando o mesmo valor ao longo da evolução, além de favorecer a busca no

espaço de soluções.

A influência de cada parâmetro no desempenho do AG dependerá da classe do

problema a ser resolvido. Segundo Coello (1999a), não existe uma regra determinística

para se estipular o tamanho da população e a probabilidade de utilização dos operadores

genéticos de modo a se obter uma adequada relação quanto aos tópicos de diversidade na

população e a capacidade de convergência dos AGs. Geralmente, em configurações

binárias considera-se o tamanho da população entre 30 e 200, probabilidade de cruzamento

entre 0,5 e 1,0 e probabilidade de mutação entre 0,001 e 0,05 (SRINIVAS & PATNAIK,

1994).

Segundo Lenive (1997), outras questões também devem ser consideradas ao se

optar pelo uso de AG. A convergência prematura é uma delas. Esta ocorre quando muitos

indivíduos na população possuem valores de alelos similares, o que resulta em um outro

indivíduo similar após o cruzamento. Algumas formas para melhorar seu desempenho

podem ser utilizadas, tais como, métodos de seleção alternativa e taxas de mutação

adaptativa.

O desconhecimento do quanto a solução fornecida pelo AG está próxima da

solução ótima é uma questão que deve ser trabalhada. O que tem sido feito é a escolha de

um apropriado critério de parada. Os critérios de parada podem envolver limites de

gerações, medidas de similaridade da população ou até mesmo a observação de nenhuma

mudança na função após um determinado número de gerações (LENIVE, 1997).

5.2 Algoritmo genético para problemas com restrições

A utilização de AGs tradicionais para a resolução de problemas com restrições pode

ser insatisfatório, principalmente pelo fato de não se ter certeza da viabilidade após os

processos de cruzamento e mutação (LENIVE, 1997). A questão principal é tratar as


70

soluções inviáveis. O tratamento das restrições é uma recente área de estudo e proporciona

uma ampla área de pesquisa a ser desenvolvida. Neste trabalho, considera-se um problema

de localização pertencente à classe de problemas restritos.

Alguns procedimentos podem ser adotados para tratar dos problemas com

restrições. De acordo com Reeves (1997), as seguintes abordagens podem ser utilizadas:

técnicas de penalização, correção de soluções que não respeitam as restrições, múltiplos

objetivos, operadores modificados e modificação da formulação do problema. Tais técnicas

são detalhadas a seguir.

As técnicas de penalização penalizam a função objetivo no caso da solução ser

inviável. Entretanto, esta tentativa isolada geralmente falha. Isto porque, se a penalidade

for muito suave, muitas soluções inviáveis são permitidas na propagação. Por outro lado,

se a penalidade for muito severa, o cromossomo não participa mais do processo de

evolução, ou seja, a busca ficará confinada ao interior do espaço de busca, longe dos

extremos da região viável (ver CASTRO, 2001; BEASLEY & CHU, 1996; BEASLEY,

1993; GLOVER & LAGUNA, 1993; SMITH & TATE, 1993; FAIRLEY, 1991). Uma

característica dessas técnicas é a necessidade de se escolher “penas” apropriadas para cada

problema.

A reparação de soluções inviáveis aceita uma solução inviável, mas a corrige antes

de devolvê-la à população, representando uma forma de mutação (ZHOU et al., 2002).

Alguma justificativa biológica é freqüentemente usada para sustentar esta abordagem.

Seguindo esta linha, a solução inviável poderia ser tratada como um cromossomo imaturo.

Embora inicialmente demonstrado inadequado para sua finalidade, no entanto, pode ao

longo do tempo levar a uma solução razoável (ver HÖHN & REEVES, 1995; ORVOSH &

DAVIS, 1993; FALKENAUER & DELCHAMBRE, 1992; GORGES-SCHLEUTER,

1989).

A abordagem multiobjetivo das restrições sugere que seja usada a inviabilidade

como um objetivo adicional ao problema, e, assim, evita-se a introdução de penalidades

(CHU & BEASLEY, 1994).

A modificação de operadores também pode ser utilizada para tratamento das

restrições e, assim, torná-los apropriados para resolver o problema (ver RADCLIFFE &

GEORGE, 1993; RADCLIFFE, 1991).


71

Uma outra abordagem é a modificação da formulação do problema restrito, a fim de

se obter uma relaxação das restrições (ver REEVES, 1996; STARKWEATHER et al.,

1991).

5.3 Algoritmo genético para problemas multiobjetivo

De acordo com van Veldhuizen & Lamont (2000), o estudo precursor sobre

tratamento de problemas multiobjetivo pelos AGs é apresentado em Schaffer (1985).

Contudo, somente a partir de Goldberg (1989) é que a utilização dos AGs para a resolução

destes problemas difundiu-se (ver SARKER et al., 2002 ,COELLO, 1999a; COELLO,

1999b; HANNE, 1999; FONSECA & FLEMING, 1995).

A principal razão dos AGs serem particularmente apropriados para resolver

problemas multiobjetivo é o fato de lidarem simultaneamente com um conjunto de

possíveis soluções eficientes em uma única execução do algoritmo, ao invés de ter que

realizar uma série de execuções das técnicas tradicionais de programação matemática

(COELLO, 1999a).

De acordo com Castro (2001), a utilização dos AGs em problemas multiobjetivo

tem as seguintes finalidades:

guiar a busca na direção do conjunto não-dominado;

manter a diversidade da população eficiente.

Atualmente, existem inúmeros procedimentos genéticos para a otimização

multiobjetivo (vide Van VELDHUIZEN & LAMONT, 2000). Os mais importantes

procedimentos são apresentados a seguir.

Schaffer (1985) apresenta o Vector Evaluated Genetic Algorithm (VEGA). Esse

algoritmo consiste em uma extensão do software GENESIS, desenvolvido por Grefenstette

(1984), através da incorporação de uma modificação do procedimento de seleção. O novo

procedimento combina a seleção proporcional à aptidão dos cromossomos com uma

seleção aleatória repetida para cada objetivo individualmente até se obter uma determinada

quantidade de cromossomos.

Fonseca & Fleming (1993) apresentam um procedimento de ordenação não-

dominado, para realizar a seleção, o chamado Multi-objective Optimization Genetic

Algorithm (MOGA). Esse algoritmo verifica todos os cromossomos, e, então, os indivíduos


72

não-dominados são designados à posição 1, e os dominados são penalizados através do

posicionamento de acordo com a quantidade de indivíduos que os dominam.

Srinivas & Déb (1993) propõem o método Nondominated Sorting Genetic

Algorithm (NSGA) que classifica os cromossomos em vários níveis. Antes de se realizar a

seleção, a população é ordenada de acordo com o nível de não-dominância. Todos os

indivíduos não-dominados são classificados em uma categoria, recebendo um valor de

aptidão fantasma que é proporcional ao tamanho da população a fim de fornecer o mesmo

potencial reprodutivo. Para manter a diversidade da população, as soluções não-dominadas

compartilham os seus valores de aptidão. Então, esses indivíduos são ignorados e um outro

nível de indivíduos não-dominados é considerado. Este procedimento é repetido até que

toda a população seja classificada, sendo que gradativamente em cada nível é associado um

valor menor de aptidão compartilhada. Durante a reprodução, os indivíduos do primeiro

nível participam de mais cruzamentos do que os de outros níveis, visto que eles apresentam

a maior aptidão.

Horn & Nafpliotis (1993) apresentam o Niched Pareto Genetic Algorithm (NPGA)

que possui um esquema de seleção por torneio baseado na dominância de Pareto. Ao invés

de limitar a comparação a dois indivíduos, uma outra quantidade de indivíduos é usada

para verificar a dominância.

Deve-se destacar que os procedimentos descritos acima originalmente não lidam

com a inviabilidade as soluções não-dominadas dos problemas multiobjetivos. No entanto,

tais procedimentos poderiam se tornar apropriados a problemas restritos através da

incorporação de operadores adequados.

Segundo Coello (1999a), o método de soma ponderada ainda é um dos mais

utilizados nos problemas multiobjetivos, podendo ser aplicado a problemas com restrições.

Consiste na soma dos produtos entre os objetivos e seus correspondentes pesos para o

cálculo da aptidão Z , onde são os coeficientes ponderados que

representam a importância relativa dos objetivos e assume-se que ∑ . No entanto,

para que os correspondam de fato a importância dos objetivos, todas as funções devem

ser expressas em unidades de valores numéricos aproximadamente iguais. Normalmente, o

vetor critério é escalarizado. Pelo fato dos resultados da resolução de um modelo de

( )λi ii K

f∈

=∑ x λ 0i

λ 1ii K∈

=

λi


73

otimização variarem significativamente de acordo com a alteração dos coeficientes de

ponderação e por geralmente poucas pessoas saberem como escolher esses coeficientes,

um procedimento necessário é resolver o mesmo problema com novos valores de .

Então, o decisor escolhe a mais apropriada solução baseada em sua intuição.

λ

CAPÍTULO 6

UM MODELO DE LOCALIZAÇÃO DINÂMICA MULTIOBJETIVO 6.1 Introdução

A localização dinâmica multiobjetivo se refere ao problema de localização no qual

múltiplos objetivos devem ser considerados em um horizonte de planejamento, sendo que a

parte dinâmica está relacionada aos múltiplos períodos de tempo considerados no

planejamento. O problema de localização dinâmica multiobjetivo considerado é o de

determinar os locais para a instalação de atividades econômicas e determinar as

associações entre estas atividades e os centros consumidores de demanda unitária1 de

forma a satisfazer os objetivos e as restrições. Considera-se um único tipo de atividade

econômica que pode ser instalada em vários locais diferentes. Conseqüentemente, podem-

se ter várias atividades econômicas idênticas em uma região produzindo os mesmos bens

e/ou serviços. Além disso, cada atividade instalada representa a concentração das

atividades administrativa, de P&D e de produção/serviço.

Uma classe de problemas de localização que não é contemplada por este trabalho é

aquela que considera múltiplos níveis hierárquicos de atividades para serem instaladas.

Este tipo de problema pode ter como propósito: determinar o número e a localização de

atividades em cada nível, o fluxo de produtos entre as atividades dos diferentes níveis e a

associação entre clientes e atividades no último nível. Para estudos mais detalhados sobre

este tema, ver Tragantalerngsak et al. (2000).

O modelo de planejamento de localização proposto é um problema de programação

multiobjetivo linear 0-1. Para o desenvolvimento deste modelo, assume-se que a

1 O centro consumidor demanda apenas por um vínculo com uma atividade instalada para suprir suas necessidades de bens e/ou serviços.

CAPÍTULO 6 – UM MODELO DE LOCALIZAÇÃO DINÂMICA MULTIOBJETIVO

75

localização da atividade econômica é realizada em nível macrogeográfico e que, uma vez

instalada, a localização não poderá mudar durante o horizonte de tempo em estudo, dessa

forma, não é aceita uma relocalização. Assume-se, também, que as condições futuras – tais

como custos, incentivos, vantagens, tempo, investimentos públicos, entre outros – sejam os

mais prováveis de ocorrer e que as funções objetivo podem ser estabelecidas a partir de

determinados fatores locacionais.

6.2 Especificação do modelo

O modelo proposto assume a hipótese de que o problema pode alocar n atividades

econômicas de um mesmo tipo ao conjunto I de possíveis locais para a

instalação ao longo de um horizonte de planejamento

1 2{ , , ..., }=

{ ,

n

1 2, ..., }fT . Cada local deve

receber apenas uma atividade econômica. Considera-se que m centros consumidores ou

clientes devem ser associados às atividades instaladas, sendo J o conjunto

dos centros consumidores. Os conjuntos de potenciais locais e de clientes são considerados

fixos e conhecidos previamente. O modelo fundamenta-se em dois fatores locacionais

quantitativos e um fator locacional qualitativo resultante da agregação de subfatores

para estabelecer seus objetivos.

t

m

=

1 2{ , ,= ..., }

1 2 3 4 5{ , , , , }P =

Os parâmetros utilizados são os seguintes:

itf

∈

, custo de investimento/instalação/operação de uma atividade no local i no período

;

I∈

t T

ijtd

i ∈

, tempo de acesso/conexão/atendimento médio entre a atividade instalada no local

e o centro consumidor no período t T ; I j J∈ ∈

itq , avaliação total do benefício agregado ao local i no período t T ; I∈ ∈

ijtq , avaliação total do benefício agregado ao acesso/conexão/atendimento entre a

atividade instalada no local i e o centro consumidor no período t T ; I∈ j J∈ ∈

pitF

p P∈

, julgamento do benefício agregado ao local i no período t segundo o subfator

;

I∈ T∈


76

pijtF , julgamento do benefício agregado ao acesso/conexão/atendimento entre a atividade

instalada no local i e o centro consumidor no período t segundo o

subfator ;

I∈ j J∈ T∈

p P∈

tR , orçamento disponível no período t T ; ∈

b , capacidade de associação da atividade instalada.

As variáveis de decisão do modelo são booleanas e definidas da seguinte forma:

1ity = , se a atividade for instalada no local i no período t , ou 0, caso contrário; I∈ T∈

1ijtx = , se o centro consumidor for associado a atividade instalada no local i I

no período t , ou 0, caso contrário.

j J∈ ∈

T∈

6.3 Funções objetivo

Três funções objetivo lineares foram estabelecidas a partir dos fatores que mais

influenciam a decisão locacional de atividades econômicas de base tecnológica. Os fatores

considerados são os seguintes: custo, proximidade dos mercados consumidores e

benefícios agregados. Sendo este último o resultado da agregação de cinco outros fatores:

economias de aglomeração, disponibilidade de mão-de-obra qualificada, infra-estrutura

local, tributação e incentivos fiscais e qualidade de vida. Os fatores custo e proximidade

dos mercados são quantitativos, os demais fatores são qualitativos. Detalhes sobre os

fatores considerados são apresentados no capítulo 4.

A primeira função objetivo está relacionada ao fator custo e consiste na soma dos

custos de instalação/operação das atividades econômicas durante o horizonte de tempo:

( )1t Ti I

Z y itf yit∈∈=∑∑

O tempo de acesso/conexão/atendimento médio entre a atividade instalada e seu

centro consumidor relacionado é representado pela segunda função objetivo:


77

( )2t Ti I j J

iZ x jt ijtd x∈∈ ∈

=∑∑∑

Os benefícios esperados através das instalações e conexões durante o horizonte de

tempo são representados pela última função objetivo:

( )3 ,t T t Ti I j J i I

Z x y ijt ijt it itq x q y∈ ∈∈ ∈ ∈

= +∑∑∑ ∑∑

ijtp P

pijtq F∈

= ∑

itp P

q pitF∈

= ∑

onde 1 2 3 4 5{ , , , , }, , , ,pijt p P i I j J t TF ∀ ∀ ∀ ∀= ∈ ∈ ∈ ∈

1 2 3 4 5{ , , , , }, , ,pit p P i I t TF ∀ ∀ ∀= ∈ ∈ ∈

A escolha locacional deverá proporcionar vantagem competitiva para a empresa e

satisfação para os funcionários. Para tanto, o benefício agregado ao local, q , e o benefício

agregado ao atendimento aos clientes pelas atividades instaladas, q , devem refletir o

julgamento subjetivo dos benefícios das localizações e das possíveis conexões à luz de 5

subfatores:

it

ijt

p : economias de aglomeração; 1=

p : mão-de-obra qualificada; 2=

p : infra-estrutura local; 3=

p : tributação e incentivos fiscais; 4=

p : qualidade de vida. 5=


78

O decisor deverá fazer o julgamento dos benefícios de cada local e de cada conexão

considerando uma escala de notas que varia de 1 a 5:

F : benefício extremamente baixo; 1=

F : benefício baixo 2=

F : benefício razoável; 3=

F : benefício alto; 4=

F : benefício extremamente alto. 5=

O benefício total de cada local e de cada conexão é obtido pela soma das

pontuações associadas aos 5 subfatores.

6.4 O Modelo dinâmico multiobjetivo

O problema dinâmico multiobjetivo pode ser representado pelo seguinte modelo de

programação multiobjetivo linear 0-1:

{ }

{ }{ }

1 2 3

, 1

(PDML-01) , ,

, 6

= 1, 6 2

, ,

, ,

, ,

0 1 , , 6

( ) ( ) ( , )

( . )

, (

( . )

( . )

\ (

, (

it it ti I

ijti I

ijt itj J

ijt itj J

it i t f

it

Minimize Z y Z x Z x y

Sujeito a f y R t T

x j J t T

x by i I t T

x y i I t T

y y i I t T t

y i I t T

∈

∈

∈

∈

+

−

∀ ∈

∀ ∈ ∀ ∈

∀ ∈ ∀ ∈

∀ ∈ ∀ ∈

∀ ∈ ∀ ∈

∈ ∀ ∈ ∀ ∈

∑

∑

∑

∑

{ }

6

0 1 , , , 6 7

)

, (ijtx i I j J t T∈ ∀ ∈ ∀ ∈ ∀ ∈

1

6 3

6 4

6 5

. )

. )

.

. )


79

O modelo multiobjetivo acima possui restrições

principais lineares e

(2 1f f f ft m t n t n t+ + + − )

f ft n t+nm variáveis de decisão binárias 0-1, sendo as fn t variáveis

as variáveis estratégicas, e as ity fnm variáveis x , as táticas. t ijt

Nessa formulação, os seguintes objetivos no horizonte de planejamento estão

presentes: minimizar os custos de instalação/operação da atividade { , minimizar o

tempo de acesso/conexão/atendimento da atividade ao seu centro de consumo { } e

maximizar obtenção dos benefícios agregados ao local e às associações { } .

Assumindo a forma de problema de minimização para o último objetivo, tem-se a seguinte

equivalência:

( )1Z y }( )2Z x

( )3 ,Z x y

( ) ( ){ }3 3, ,Max Z x y Min Z x y⇔ − −

As restrições principais do problema são lineares e podem ser agrupadas em cinco

tipos. As exigências de cada uma delas são apresentadas a seguir:

(6.1) A soma dos gastos em cada período t não deve ultrapassar o orçamento disponível

do período;

(6.2) Em cada período t , cada centro consumidor deve ser associado a apenas uma

atividade econômica instalada no local i . Em outras palavras, deve ter apenas uma

conexão;

j

(6.3) Em cada período t , se nenhuma atividade for instalada no local i , então nenhum

centro consumidor pode estar associado a este local. Além disso, no caso de uma

atividade instalada, o número de centros consumidores associados a ela não deve

ser superior à sua capacidade. Uma situação indesejada que é permitida por esta

restrição é a do local i receber uma atividade e não atender a nenhum cliente.

(6.4) Em cada período t , se uma atividade for instalada no local i , então essa atividade

deverá atender a pelo menos um cliente. Com isto evita-se a situação indesejada

que é permitida pela restrição anterior.


80

(6.5) A atividade que for instalada no local i não poderá ser removida durante o

horizonte de tempo considerado. Assim, não se considera a possibilidade de haver

uma relocalização.

(6.6) Se a atividade for instalada no local i no período t T , é igual a 1; caso

contrário, y é igual a 0.

I∈ ∈ ity

it

(6.7) Se o centro consumidor for associado a atividade instalada no local i no

período t T , x é igual a 1; caso contrário, x é igual a 0.

j J∈ I∈

∈ ijt ijt

Pode-se esperar que os parâmetros do modelo apresentem ordem de grandeza muito

diferentes, neste caso, deve-se realizar o procedimento de escalarização do mesmo (ver

STEUER, 1986).

A solução do modelo PDML-01 informará os locais para a instalação das atividades

econômica e as associações entre centros consumidores e atividades instaladas ao longo do

horizonte de planejamento.

Os problemas de localização podem tornar-se bastante difíceis, visto que envolvem

a análise de uma grande quantidade de variáveis relacionadas a decisão locacional e de

escolhas viáveis que necessitam ser consideradas para a implantação. Além disso, sua

natureza combinatorial faz com que o custo computacional de sua resolução seja alto.

Dessa forma, a principal dificuldade para a resolução do problema PDML-01 é sua

complexidade, pois a obtenção de soluções exatas em tempo polinomial não é possível.

Isto porque, sendo um problema simplificado da classe NP-árduo, o problema de

localização considerado também será da mesma classe (KRARUP & PRUZAN, 1983;

GAREY & JOHSON, 1979). Portanto, um método heurístico pode ser o procedimento

mais apropriado para resolver o modelo proposto. O sucesso dos algoritmos genéticos na

resolução de problemas combinatórios os torna fortes candidatos para resolver o problema

PDML-01.

CAPÍTULO 7

O ALGORITMO GENÉTICO PROPOSTO 7.1 Introdução

O algoritmo proposto resolve um modelo auxiliar de único objetivo que é

construído a partir do modelo PDML-01 apresentado no capítulo 6. O modelo auxiliar

possui uma função escalar resultante da agregação ponderada (método ponderado) dos três

objetivos presentes no PDML-01.

As seguintes restrições são assumidas como sendo as novas restrições do tipo 1 e 3

do modelo auxiliar:

Restrição 1 : t Ti Iit it Rf y

∈∈≤∑∑

Restrição 3: , ,j J

ijt it i I t Tx my∈

≤ ∀ ∈ ∀∑ ∈

onde R é o orçamento disponível para todo o horizonte do planejamento.

Estas novas restrições informam que:

Restrição 1 : A soma dos gastos de todos os períodos t não deve ultrapassar o orçamento

total disponível R ;

Restrição 3: Em cada período t , cada atividade instalada no local i , possui capacidade

para se associar a todos os clientes, ou seja, b m . =

CAPÍTULO 7 – O ALGORITMO GENÉTICO PROPOSTO

82

O modelo multiobjetivo resultante possui 1 2 restrições

principais lineares, permanecendo com as

(f f fm t n t n t+ + + − )1

f fn tnm variáveis de decisão binárias 0-1. t +

O algoritmo genético proposto incorpora operadores de correção e de penalização

adequados para tratar as soluções inviáveis do modelo considerado. Ao final da execução

do algoritmo, é fornecido um conjunto de soluções não-dominadas da elite para a

apreciação do decisor. Decisor, neste trabalho, é considerado uma única pessoa ou um

grupo em que haja consenso em suas decisões. A decisão será a escolha de uma solução

não-dominada que seja a mais aceitável.

7.2 Codificação do cromossomo

Devido ao problema considerado ser do tipo 0-1, uma codificação binária para os

cromossomos é adotada. Cada componente do cromossomo corresponde a uma variável da

solução binária e respeita a seguinte seqüência.

wX , , ,ijt it i I j J t Tx y ∀ ∀ ∀ = ∈ ∈ ∈

( ) ( ) (( ) ( ) (

( ) ( ) (( ) ( )

w111 121 1 1 211 221 2 1 11 21 1

112 122 1 2 212 222 2 2 12 22 2

11 12 1 21 22 2 1 2

11 21 1 12 22 2 1 2

X ... ... ... ...

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

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

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

ff f f f f f f f

f f

m m n n

m m n n

nmtt t mt t t mt n t n t

n n t t

x x x x x x x x x

x x x x x x x x x

x x x x x x x x x

y y y y y y y y

=

( )fnty

))

)

nm

nm

A quantidade de genes que cada cromossomo possui, ou seja, a quantidade de

variáveis de cada solução, é chamada de lchrom e é definido por nm . f ft n t+

Uma representação de seqüenciamento de variáveis de um cromossomo é mostrada

a seguir para o caso de n , e t . Nesta situação, cada cromossomo será

constituído por 30 genes/variáveis.

3= 4m = 2f =


83

111 121 131 141 211 221 231 241 311 321 331 341

112 122 132 142 212 222 232 242 312 322 332 342

11 21 31 12 22 32

X x x x x x x x x x x x xx x x x x x x x x x x x

y y y y y y

=

Deve-se notar que a variável y (local 1 no tempo 1) está relacionada às variáveis

, x , x e x , ou seja, o local 1 no período 1 poderia atender aos 4 clientes. As

outras correlações são:

11

111x 121 131 141

21 211 221 231 241e , ,y x x x x→

31 311 321 331 341e , ,y x x x x→

12 112 122 132 142e , ,y x x x x→

22 212 222 232 242e , ,y x x x x→

32 312 322 332 342e , ,y x x x x→

7.3 População inicial

A geração da população inicial de npop indivíduos é feita de forma parcialmente

aleatória dentro do espaço de soluções viáveis para agilizar a geração, o que representa um

processo de geração orientada para o caso particular do modelo considerado. Este processo

é detalhado a seguir:

7.3.1 Geração aleatória de valores para yit

.

A partir de cada local i referente a cada período t , escolhe-se aleatoriamente entre

0 ou 1 para as variáveis y . it

Ex.1: 11 12 21 22 31 32e e e ; ;y y y y y y

Deve-se respeitar a condição de que, se um local receber uma atividade em um

período, esta atividade deve permanecer no local pelos períodos seguintes. Essa exigência

diz respeito à satisfação da restrição do tipo 5 do modelo proposto.

1 Todos os exemplos deste capítulo estão relacionados ao caso n = 3, m = 4 e tf = 2.


84

7.3.2 Garantia de instalação

Segundo a restrição do tipo 2 no modelo proposto, em cada período, cada centro

consumidor deverá ter conexão com alguma atividade econômica, portanto, é necessário

que pelo menos um local receba uma atividade para atender os centros consumidores.

Ex.: 11 21 31 12 22 321 1; ;y y y y y y+ + + +

Caso isto não ocorra, é necessário, outra vez, gerar aleatoriamente valores para y . it

7.3.3 Garantia de viabilidade orçamentária

Deve-se verificar se a restrição do tipo 1 é respeitada.

Ex.: 11 11 21 21 31 31 12 12 22 22 32 32f y f y f y f y f y f y R+ + + + +

Caso isto não ocorra, é necessário gerar aleatoriamente novos valores para y . it

7.3.4 Geração aleatória de valores para x ijt

Escolhe-se aleatoriamente entre 0 ou 1 para as variáveis x referentes a cada

período t , da seguinte forma:

ijt

1) De acordo com a restrição do tipo 3, se determinado local i não receber atividade em

um período t ( ), este local não terá associação com nenhum cliente. 0ity =

Ex.: Para o local 2 no período 1: se , então x x x . 21 0y = 211 221 231 241 0x+ + + =

2) De acordo com a restrição do tipo 4, se determinado local i receber atividade em um

período t ( 1y ), este local terá associação com pelo menos um cliente. it =

Ex.: Para o local 2 no período 2: se y , então x x x . 22 1= 212 222 232 242 1x+ + +

7.3.5 Garantia de associação

Em cada período, cada cliente deverá ter conexão com apenas uma atividade

econômica instalada (restrição do tipo 2).

Ex.: Para o cliente 4 no período 2: x x . 142 242 342 1x+ + =


85

Caso isto não se verifique, é necessário gerar aleatoriamente novos valores para

. ijtx

Eventualmente poderá existir mais de uma cópia de algum indivíduo na geração

inicial.

Algumas representações de soluções viáveis do ponto de vista das restrições2 do

tipo 2, 3, 4 e 5 são dadas a seguir.

X1 = [ 1110 0001 0000 : 1010 0001 0100 : 110:111 ]

X2 = [ 1000 0101 0010 : 0010 1001 0100 : 111:111 ]

X3 = [ 0000 0000 1111 : 0110 0000 1001 : 001:101 ]

X4 = [ 0110 0000 1001 : 1010 0001 0100 : 101:111 ]

X5 = [ 0100 0011 1000 : 0100 1001 0100 : 111:111 ]

X6 = [ 0000 0000 1111 : 0100 0010 1001 : 001:111 ]

X7 = [ 0000 1111 0000 : 0000 1100 0011 : 010:011 ]

7.4 Avaliação da aptidão

A função objetivo pode fornecer um bom indicador do quanto cada indivíduo está

adaptado ao ambiente. Portanto, a função objetivo do problema auxiliar descrito na seção

7.1, ou seja, a função escalar, é considerada como sendo a medida de aptidão/desempenho

dos indivíduos/soluções. Tal função é montada pela soma ponderada dos três objetivos do

PDML-01 na forma de minimização. Assim, a melhor aptidão, isto é, o melhor

desempenho, será o da solução que possuir o menor valor da função escalar abaixo.

( ) ( ) ( ) ( )1 1 2 2 3 3λ λ λ, ,Minimize Ze x y Z y Z x Z x y= + −

onde é o peso ou importância da função objetivo k K e considerando

que e . Observa-se que os valores de

λk

λi K∈∑

{1 2 3, ,∈ =

(

}1i = λ 0i ),x yZe podem ser positivos ou

negativos.

2 A viabilidade em relação a restrição do tipo 1 dependerá da especificação dos custos e do orçamento.


86

7.5 Ordenação

Consiste na distribuição de rótulos para os indivíduos, chamados de ordem no caso

da população gerada e de ordemelite para a elite. Tal distribuição é feita em ordem

decrescente de valor da adaptação, ou seja, ordem crescente do valor de ( ),x yZe .

Portanto, à cada indivíduo corresponderá uma ordem/ordemelite que vai de 1 até npop, de

forma que o indivíduo de melhor aptidão, ou seja, o de menor valor de ( ),x yZe , receba a

ordem/ordemelite 1, e o indivíduo de pior aptidão, ou seja, o de maior valor de ( ),Ze x y , a

ordem/ordemelite npop. Em caso de empate de aptidão, a distribuição dos rótulos é feita

aleatoriamente entre os indivíduos empatados.

7.6 Seleção

É adotada a seleção por torneio de dois para escolher os cromossomos que devem

participar do processo reprodutivo e assim gerar descendentes. Neste critério de seleção,

sorteiam-se dois indivíduos da população e então é realizado um torneio entre eles. Vence

aquele indivíduo que possuir maior aptidão, o que é representado pelo menor valor da

função ( ),Ze x y ; em caso de empate, a escolhe é feita aleatoriamente entre os dois. Esse

procedimento é realizado lchrom vezes em cada geração.

7.7 Cruzamento

Após a operação de seleção ser realizada, os cromossomos selecionados são

agrupados aleatoriamente em pares e a uma probabilidade pc ocorre o cruzamento entre tais

pares. O operador de cruzamento considerado utiliza apenas um ponto. Este ponto,

escolhido aleatoriamente entre 1 e lchrom , indica a posição onde é feito um corte no

cromossomo. Em seguida, as informações genéticas que estiverem à direita deste ponto são

trocadas entre os pares de cromossomos pais, resultando nos cromossomos filhos. Caso

não haja cruzamento, os filhos serão cópias idênticas dos pais.

1−

Uma característica desse procedimento é que, ao final do cruzamento, não se

garante que os descendentes apresentem viabilidade. A questão do tratamento da

inviabilidade das soluções é abordada mais adiante.


87

7.8 Mutação

Cada elemento do cromossomo (bit) é considerado para sofrer uma mutação a uma

determinada probabilidade pm. Em caso de mutação, o gene do cromossomo terá seu valor

trocado.

7.9 Correção

Uma vez que os cromossomos filhos tenham sido gerados, é feita uma verificação

de sua viabilidade em relação às restrições do tipo 2, 3 e 4. Em caso de violação destas

restrições, realiza-se uma modificação na estrutura do cromossomo a fim de que tais

restrições sejam respeitadas. De certa forma, este operador representa um tipo de mutação

nos cromossomos filhos.

A correção é realizada primeiro nas variáveis do tipo x e, em seguida, nas

variáveis do tipoy .

ijt

it

Inicialmente, a viabilidade pela restrição do tipo 2 é verificada. O não atendimento

dessa restrição significa que se tem, em algum período, algum cliente que está associado a

mais de uma atividade instalada ou a um local que não recebeu a instalação de alguma

atividade. Uma ilustração desta situação é dada a seguir.

X = [ 0010 0000 0101 : 0110 1000 0011 : 101:111 ]

Na solução apresentada, há 3 conexões no período 1 e 5 conexões no período 2. Os

pontos de inviabilidade são citados abaixo.

1) Para o cliente 1 no período 1: x x , ou seja, não houve

associação deste cliente a nenhum local.

111 211 311 0 0 0x+ + = + + = 0

22) Para o cliente 3 no período 2: x x , ou seja, o cliente 3

recebeu duas associações, uma com o local 1 e a outra com o local 3.

132 232 332 1 0 1x+ + = + + =

Nesta situação de inviabilidade, para cada cliente , escolhe-se o local i de menor

valor de função para associação, não formando conexão com as demais posições.

Eventualmente, algum local que não havia recebido a instalação de uma atividade poderá

j


88

ter uma instalação. Como resultado desse procedimento, tem-se um número total de

associações em cada período igual ao número de clientes.

Após a correção, o exemplo apresentado acima fica da seguinte forma:

X = [ 0010 0000 1101 : 0110 1000 0001 : 101:111 ]

Neste caso, há 4 conexões no período 1 e 4 conexões no período 2, o que

corresponde a uma situação de viabilidade. Os pontos que sofreram correção são

mostrados a seguir.

1) Para o cliente 1 no período 1: x x , ou seja, o cliente 1

foi associado ao local 3.

111 211 311 0 0 1x+ + = + + = 1

12) Para o cliente 3 no período 2: , ou seja, o cliente 3

foi associado ao local 1.

132 232 332 1 0 0x x x+ + = + + =

Finalizada a correção das variáveis do tipo x , inicia-se a correção das variáveis

do tipo y , tal procedimento diz respeito a satisfação das restrições do tipo 3 e 4. Os

valores de y são ajustados de acordo com os valores das variáveis do tipo x

considerando as seguintes orientações:

ijt

it

it ijt

1) Se o número de associações de cada atividade em cada períodot for maior ou igual a 1,

significa que o local i recebeu a atividade no período t . Em outras palavras, para i e

conhecidos, se t 1ijtj J∈x∑ , então y . 1it =

2) Se o número de associações for nulo, significa que o local i não recebeu nenhuma

atividade no período t . Em outras palavras, para i e t conhecidos, se 0ijtj Jx

∈=∑ ,

então . 0ity =

Tais orientações são respeitadas na representação abaixo, sendo detalhadas para

cada para i e t logo em seguida.


89

X = [ 1111 0000 0000 : 1010 0000 0101 : 100:101 ]

Para o local 1 no período 1: 111 121 131 141 111 1 1 1 4 1x x x x y+ + + = + + + = ⇒ = 1

0

0

1

0

1

Para o local 2 no período 1: 211 221 231 241 210 0 0 0 0x x x x y+ + + = + + + = ⇒ =


Para o local 1 no período 2: 112 122 132 142 121 0 1 0 2 1x x x x y+ + + = + + + = ⇒ =


Para o local 3 no período 2: 312 322 332 342 320 1 0 1 2 1x x x x y+ + + = + + + = ⇒ =

7.10 Penalização

Este operador está relacionado às restrições do tipo 1 e 5. A restrição do tipo 1 diz

respeito a uma limitação orçamentária. Já a restrição do tipo 5 está relacionada a uma

situação em que, se algum local receber uma atividade econômica em algum período,

deverá haver a permanência desta atividade no mesmo local pelos períodos subseqüentes;

em outras palavras, não se deseja uma relocalização.

Para a inviabilidade pelas restrições 1 ou 5, penaliza-se a função de avaliação

( ),Ze x y com um alto valor (Penalidade) para cada restrição violada, desta forma a aptidão

do indivíduo inviável será reduzida. Esse procedimento é representado da seguinte forma:

( ) ( ) =

, ,Ze x y Ze x y Penalidade nrviol

Penalidade lchromµ

← + ×

×

onde nrviol é o número de restrições violadas e é o mais alto coeficiente, em módulo, da

função

µ

( ),Ze x y

( ijtx +

de um determinado problema. A Penalidade é representada por uma

função cujos coeficientes das lchrom variáveis ( são iguais a e todas essas

variáveis são iguais a 1. Dessa forma, a Penalidade será um valor superior ao

maior valor possível para

))

ijt itx y+ µ

ity

( ),x yZe e o valor de qualquer função penalizada será maior do

que o valor de qualquer função não-penalizada.


90

Como o operador de penalização não corrige a inviabilidade das soluções, apenas

as penaliza, indivíduos inviáveis poderão permanecer na população, ser selecionados e

gerar descendentes. No entanto, uma solução inviável não poderá pertencer a um conjunto

das melhores soluções, como será apresentado na próxima seção.

Depois de realizar a penalização, podem-se ter duas novas situações no momento

da seleção por torneio de dois.

1) Se um indivíduo é viável e o outro inviável, ganha aquele que é viável, pois a função

de avaliação do indivíduo inviável já está penalizada, sendo, portanto, um valor muito

grande;

2) Se os dois indivíduos são inviáveis, ganha aquele que possuir o menor número de

restrições violadas, pois sua função de avaliação é a menos penalizada. Em caso de

empate, a escolha é feita aleatoriamente entre os dois.

7.11 Elitismo

O operador elitismo é incorporado ao algoritmo de forma que uma elite seja

montada para receber uma quantidade de indivíduos igual a npop. Inicialmente, a elite

apresenta os mesmos elementos que a geração inicial e, portanto, a mesma ordenação

(ordem decrescente de adaptação, ordemelite = ordem). Pelo fato desses indivíduos serem

viáveis, a elite inicial também será viável, e deverá permanecer assim ao longo de todo o

processo evolutivo.

Ao final de cada geração, a elite poderá ser atualizada, o que significa a troca de

alguns indivíduos da elite por novos indivíduos viáveis, chamados de candidatos, presentes

na população. No entanto, deve ser realizada previamente a comparação dos cromossomos

gerados, que são os candidatos a entrar na elite, com os cromossomos da elite. Esse

procedimento começa com a comparação da ordem 1 (o melhor da população gerada) com

a ordemelite npop (o pior da elite), em seguida, a ordem 2 com a ordemelite , e,

assim, sucessivamente. Dessa forma, a comparação dos cromossomos gerados começa a

partir do indivíduo de ordem 1, indo progressivamente até o indivíduo de ordem npop;

enquanto que a comparação da elite ocorre em sentido oposto, ou seja, começa do

indivíduo de ordemelite npop, indo na direção de ordemelite 1. Este processo é

apresentado na Figura 7.1.

1npop −


91

População gerada: [ ordem 1 ordem npop]

Elite: [ ordemelite 1 ordemelite npop]

Figura 7.1 Sentido da comparação entre a população gerada e a elite.

Para que de fato a troca ocorra, o indivíduo candidato não poderá ter cópia na elite

e deve ter aptidão melhor do que a aptidão do indivíduo da elite que está sendo comparado.

Dessa forma, os seguintes procedimentos devem ser considerados:

1) Se algum indivíduo for inviável, ele não é candidato a substituir a elite. A comparação

com a elite não chegará a ser realizada, pois, sabe-se que como a formação inicial da

elite é de indivíduos viáveis, qualquer solução ainda inviável possui aptidão pior do

que qualquer um indivíduo da elite, visto que sofreu penalização. Então, finaliza-se a

operação de atualização e o indivíduo inviável não entra na elite.

2) Caso haja alguma cópia do indivíduo candidato na elite, passa-se para a ordem

seguinte, ou seja, avalia-se um outro indivíduo candidato, permanecendo fixa a mesma

ordemelite para a comparação.

3) Se em algum momento o indivíduo candidato for pior do que o indivíduo da elite, o

processo de atualização da elite é encerrado.

7.12 Critério de término

O algoritmo é finalizado depois de se alcançar o número máximo de gerações.

7.13 Não-dominância

Após a finalização do processo evolutivo, os indivíduos não repetidos presentes na

elite passam por uma avaliação de não-dominância, segundo a definição 2.1 que é

reapresentada a seguir.


92

Definição: O vetor objetivo ( 1 2, , ..., kkz z z= ∈

( 1 2, , ...,k

kz z z= ∈

))

Z é chamado de não-dominado, se, e

somente se, não existe outro Z tal que Z e Z≤ ii z<z para

pelo menos um i k . { }1 2, , ...,∈

O indivíduo de maior aptidão, que é o de ordemelite 1, domina os outros indivíduos

da elite, assim, o teste de não dominância é realizado para os demais indivíduos não

repetidos da elite.

Em seguida, um conjunto de indivíduos/soluções não-dominados é fornecido ao

decisor para a avaliação. Caso estas soluções não sejam satisfatórias, inicia-se um processo

interativo onde novos valores de parâmetros são introduzidos no processo de evolução. Em

caso contrário, o processo é finalizado. A quantidade de indivíduos do conjunto não-

dominado dependerá da qualidade das soluções presentes na elite na última geração.

7.14 O algoritmo

O AG implementado poder ser descrito pelos seguintes passos:

0) Leitura dos parâmetros.

1) Inicialização da população viável inicial, Geração := 0.

2) Inicialização da elite.

3) Cálculo da aptidão da população gerada e da elite.

4) Ordenação da população gerada e da elite.

5) Geração := Geração + 1.

6) Seleção.

7) Cruzamento e Mutação.

8) Correção, em caso de inviabilidade das restrições do tipo 2, 3 e 4.

9) Cálculo da aptidão da população gerada.

10) Penalização, em caso de inviabilidade das restrições do tipo 1 e 5.


93

11) Ordena nova população gerada.

12) Atualiza elite.

13) Ordena elite.

14) Se Geração > (número máximo de gerações), então vá para o passo 15. Caso

contrário, retorne ao passo 5.

15) Avalia não-dominância da elite.

16) Se elite não-dominada for satisfatória, então pare. Caso contrário, faça leitura dos

novos ’s e retorne ao passo 3. λ

Esta estrutura é representada pelo pseudocódigo abaixo.

PPrroocceeddiimmeennttoo eevvoolluuttiivvoo pprrooppoossttoo

iinníícciioo

gg ←← 00

iinniicciiaalliizzee ( )P g ee ( )E g

eennqquuaannttoo ssoolluuççããoo )(maxgenE nnããoo--ddoommiinnaaddaa nnããoo ffoorr ssaattiissffaattóórriiaa,, ffaaççaa

aavvaalliiee ee oorrddeennee ( )P g ee ( )E g

eennqquuaannttoo g maxgen ,, ffaaççaa

gg ←← gg ++ 11

sseelleecciioonnee ( )P g aa ppaarrttiirr ddee 1 ( )P g −

ccrruuzzaammeennttoo ee mmuuttaaççããoo ( )P g

ccoorrrreeççããoo ( )P g

aavvaalliiee ( )P g

ppeennaalliizzaaççããoo ( )P g

oorrddeennee ( )P g

aattuuaalliizzee ee oorrddeennee ( )E g


94


aavvaalliiee nnããoo--ddoommiinnâânncciiaa ( )E maxgen


ffiimm

onde é a população da geração g , ( )P g ( )E g é a população da elite na geração g e

é o número máximo de gerações. maxgen

CAPÍTULO 8

EXPERIMENTOS COMPUTACIONAIS 8.1 Características de hardware e software

A implementação do Algoritmo Genético de Correção e Penalização proposto

(AGCP) foi realizada em Delphi 5.0 e os testes computacionais foram executados em

microprocessador Pentium 933 MHz, com 512 MB de RAM.

8.2 Inicialização dos parâmetros

Para efeito de testes computacionais, os parâmetros do modelo multiobjetivo

dinâmico 0-1 foram gerados aleatoriamente, sendo distribuídos dentro dos limites dados

abaixo, e considerou-se um orçamento disponível R de 75% do somatório de todos os

coeficientes de custo gerados.

[ ]0 10,...,itf =

[ ]0 10,...,ijtd =

1 1,...,itq = − − 0 0 e q (forma de minimização) 1 1,...,ijt= − −

0 75,t Ti I

R fit∈∈= ∑∑

8.3 Problemas teste

Três problemas teste de dimensões diferentes, P1, P2 e P3, foram gerados

aleatoriamente respeitando os limites apresentados na seção anterior. As dimensões de tais

problemas são apresentadas no quadro 8.1.

CAPÍTULO 8 – EXPERIMENTOS COMPUTACIONAIS

96

Quadro 8.1 Dimensões dos problemas teste

Problema n m ft No. de restrições No. de variáveis lchrom

P1 3 4 2 24 30 P2 5 5 3 56 90 P3 10 10 5 191 550

Os seguintes valores foram considerados como constantes em todas as instâncias:

λ , , , representando a importância dos fatores do ponto de

vista de uma empresa privada;

1 0 6,= 2λ 0 1,= 3λ 0 3,=

p , uma probabilidade de mutação de valor pequeno, pois a necessidade de

introdução ou manutenção da diversidade genética da população já é parcialmente

suprida pelo operador de correção.

0 001,m =

Cada uma das combinações dos parâmetros genéticos (npop, maxgen e )

apresentadas no quadro 8.2 foi rodada cinco vezes para o mesmo tipo de problema teste,

em cada uma dessas vezes foi gerada uma população inicial diferente.

cp

O AGCP foi comparado com um algoritmo genético que incorpora apenas os

operadores genéticos tradicionais, que é chamado de Algoritmo Genético Tradicional

(AGT). A comparação é feita considerando que uma mesma população inicial é utilizada

por AGCP e AGT.

O AGT preserva a estrutura básica do AGCP e também trabalha com uma elite

viável de comprimento lchrom, mas não realiza nenhum tipo de tratamento das soluções

inviáveis. No entanto, para que haja a atualização da elite, é necessário realizar o teste de

viabilidade das soluções geradas antes de compará-las com as soluções da elite em cada

geração.

Para efeito de avaliação das soluções de melhor aptidão fornecidas pelos algoritmos

AGCP e AGT, os problemas auxiliares monobjetivo dos problemas teste P1 e P2 foram

construídos de acordo com as orientações apresentadas no capítulo 7, salvos em arquivos

de extensão .ltx e resolvidos pelo software Lindo, obtendo-se, então, os valores ótimos de

P1 e P2. Tais valores são apresentados no quadro 8.3.


97

Quadro 8.2 Combinações de parâmetros genéticos utilizados

Problemas Tamanho da população

npop

No. máximo de gerações maxgen

Probabilidade de cruzamento

cp

P1 P2 P3

50

50

1 0,8 0,5

P1 P2 P3

100

50

1 0,8 0,5

P3 200 50 1 P3 400 50 1 P1 P2 P3

50

100

1 0,8 0,5

P1 P2 P3

100

100

1 0,8 0,5

P3 200 100 1 P3 400 100 1 P1 P2 P3

50

200

1 0,8 0,5

P1 P2 P3

100

200

1 0,8 0,5

P3 200 200 1 P3 400 200 1 P3 50 400 1 P3 100 400 1 P3 200 400 1 P3 400 400 1

Quadro 8.3 Valores ótimos dos problemas P1 e P2

Problema (* ,Ze x y) mono P1 - 0,20 P2 - 8,90


98

8.4 Resultados

Os resultados apresentados nesta seção são referentes às médias obtidas nas cinco

rodadas de cada combinação, exceto os valores ↑ e ↓ que se referem,

respectivamente, ao maior valor e ao menor valor de

Ze

(

Ze

),x yZe obtido nas cinco rodadas. O

termo ND significa a média de soluções não-dominadas na elite (considerou-se o valor

aproximado por truncamento), t(s) é o tempo médio, em segundos, gasto nas gerações, Ze

é a média dos ( ),x yZe obtidos nas cinco rodadas, Ze↓ é a média dos ↓ obtidos. Ze

Problema P1

Tabela 8.1 Resultados de P1 para pc = 1

AGCP AGT

npop maxgen ND t(s) Ze↑ Ze Ze↓ Ze↓ ND t(s) Ze↑ Ze Ze↓ Ze↓

50 50 37 9 13,7 5,0 -0,2 -0,16 21 12 14 6,92 -0,2 -0,04

100 50 54 18 13,6 5,46 -0,2 -0,16 44 21 14,6 6,65 -0,2 -0,08

50 100 30 18 12,8 4,92 -0,2 -0,12 20 23 12,8 5,03 -0,2 -0,04

100 100 65 36 14,2 5,31 -0,2 -0,16 59 48 14,8 6,37 -0,2 -0,04

50 200 34 37 12,5 4,7 -0,2 -0,16 26 48 12,5 5,70 -0,2 -0,04

100 200 73 71 13,5 5,8 -0,2 -0,16 49 96 13,5 6,01 -0,2 -0,08

Tabela 8.2 Resultados de P1 para pc = 0,8

AGCP AGT


50 50 19 9 12,2 5,02 -0,2 -0,12 14 10 12,2 5,82 -0,2 -0,04

100 50 77 18 15,4 5,65 -0,2 0,2 78 23 15,4 6,1 -0,2 -0,02

50 100 35 19 13,4 4,67 -0,2 -0,16 14 25 13,4 5,72 ≅ 0 ≅ 0

100 100 73 34 12,9 5,81 -0,2 -0,16 41 47 12,9 6,18 -0,2 -0,08

50 200 33 36 12,1 5,33 -0,2 -0,16 25 49 12,9 5,7 -0,2 -0,08

100 200 75 74 13,5 5,64 -0,2 -0,2 48 97 13,5 6,27 -0,2 -0,12


99


AGCP AGT


50 50 24 9 12,6 5,17 -0,2 -0,08 22 12 12,6 5,69 ≅ 0 ≅ 0

100 50 58 15 13,4 5,79 -0,2 -0,12 57 25 13,6 6,3 -0,2 -0,8

50 100 31 18 13,3 5,2 -0,2 -0,12 30 25 13,4 5,69 -0,2 -0,12

100 100 77 36 13,4 5,66 -0,2 -0,12 76 49 14,4 6,39 -0,2 -0,12

50 200 20 36 14,8 5,74 ≅ 0 ≅ 0 20 50 14,8 6,4 ≅ 0 0,22

100 200 69 72 14,8 6,5 -0,2 -0,16 66 93 14,8 7,02 -0,2 -0,12

Problema P2


AGCP AGT


50 50 32 10 11 3,14 -5,8 -3,9 28 13 27,2 11,38 -5,8 -2,64

100 50 47 19 23,1 2,58 -8,9 -5,28 52 26 30,5 11,32 -8,5 -3,5

50 100 27 19 15,2 5,12 -5, -4,3 32 26 28,7 12,75 -2,4 -1,28

100 100 71 38 11 2,26 -6,2 -4,2 80 52 27,7 12,11 -6,2 -2,52

50 200 30 38 10,6 1,57 -5,6 -4,66 37 53 27,5 13,56 -4,5 -2,54

100 200 58 76 12,5 2,2 -6,2 -5,02 69 104 28,2 11,81 -2,6 -2,0


AGCP AGT


50 50 32 10 17 6,06 -8,9 -5,06 40 13 25,1 12,00 -3,7 -1,28

100 50 60 19 20 4,00 -8,3 -5,50 73 27 30,3 11,21 -4,4 -3,68

50 100 31 20 17,3 3,08 -8,9 -6,22 32 28 33,7 11,67 -7,7 -4,96

100 100 62 39 20 2,64 -8,3 -6,54 64 54 27,9 11,31 -6,1 -4,0

50 200 29 40 19,6 2,79 -8,3 -4,94 33 54 31,4 10,41 -3,9 -1,18

100 200 50 78 22,9 4,64 -8,9 -6,26 67 108 27,4 10,69 -8,9 -5,9


100


AGCP AGT


50 50 37 10 28,8 5,09 -6,8 -5,34 40 14 31,3 11,09 -6,8 -3,44

100 50 74 19 23,4 4,91 -8,9 -6,54 64 27 28,2 11,06 -8,9 -4,98

50 100 32 20 25,3 4,76 -8,9 -5,62 28 27 25,8 9,52 -8,9 -4,42

100 100 59 39 33,3 6,00 -8,9 -6,48 57 54 29,6 11,0 -8,9 -5,2

50 200 41 40 60,1 9,92 -5,8 -3,82 41 54 91,1 18,01 -4 2,08

100 200 63 79 22,0 5,35 -8,9 -5,86 61 108 30,8 1,77 -4,8 -3,92

Problema P3


AGCP AGT


50 50 36 13 71,2 34,74 -10,9 1,08 39 18 83,9 44,97 -7,49 6,96

100 50 72 26 68,8 28,98 -3,50 0,94 75 35 88,3 41,82 4,9 8,42

200 50 110 55 60,3 19,86 -5,10 -1,12 95 76 100,7 40,09 -4,8 0,12

400 50 160 106 71,1 17,94 -17,9 -12,7 189 141 108,0 42,53 -17,9 -10,34

50 100 21 26 59,4 10,4 -2,3 1,22 17 35 84,5 44,17 0,99 8,2

100 100 76 56 49,5 9,55 -27,7 -8,32 53 72 96,9 37,82 -4,5 1,52

200 100 143 111 60,3 16,92 -12,6 -6,04 100 151 91,5 38,51 -5,7 -1,58

400 100 257 210 53,0 6,36 -16,3 -13,72 180 233 93,6 43,26 -14,9 -7,84

50 200 34 57 85,2 33,23 -8,9 3,8 30 61 92,5 34,0 3 8,4

100 200 83 111 60,7 22,26 5,8 1,92 75 145 91,2 42,42 -2,2 7,22

200 200 114 244 68,8 21,06 -8,2 -3,86 104 303 101,4 4,11 -8,2 3,16

400 200 272 414 91,5 4,04 -12,2 -5,82 207 568 94,5 44,34 -4,7 -1,08

50

100

200

400

400

400

400

400

31

47

155

304

107

214

431

864

74

77,8

67,9

34,0

29,95

28,22

14,6

14,19

0,09

-8,6

-11,5

-27,9

3,30

-1,28

-6,84

-7,44

35

49

73

240

144

285

598

1154

83,5

102,2

94,8

97,5

38,56

38,06

35,25

43,07

5,4

-1,2

-6,3

-5,6

8,62

3,56

-2,56

-1,66


101


AGCP AGT


50 50 32 14 64,4 38,44 5,2 12,50 32 19 97,3 43,07 5,2 12,50

100 50 61 26 76,9 20,69 -8,8 -2,22 51 35 98,4 45,37 -8,8 2,94

50 100 38 27 75,7 34,28 -3,0 5,94 31 37 86,5 45,60 1,5 9,18

100 100 90 54 68,4 30,04 -9,9 3,68 51 74 108,1 43,04 -2,5 8,26

50 200 20 53 73,3 28,41 -2,0 3,82 23 72 84,2 42,30 -0,3 4,86

100 200 52 103 66,4 66,73 -7,0 1,34 45 140 90,8 46,43 -6,2 5,28


AGCP AGT


50 50 36 13 70,3 33,79 -5,89 1,02 28 17 84,6 70,06 2,1 7,54

100 50 61 27 81,3 32,16 -4,2 0,54 68 36 95,4 44,65 -2,7 2,32

50 100 36 27 72,7 34,67 -14,1 -3,08 21 37 90,4 39,42 -7,3 3,32

100 100 51 53 80,7 31,54 -1,4 4,88 43 72 96,5 40,26 -1,4 6,58

50 200 30 55 77,2 28,86 -6,9 -1,4 21 77 88,6 37,52 -1,89 1,64

100 200 68 103 83,1 35,94 -2,4 4,16 66 140 92,9 43,56 3,6 7,0

A partir dos resultados pode-se observar que:

O AGCP forneceu soluções com os menores de valores de Ze↓ , e geralmente os

menores valores de Ze ;

Os tempos de geração dos AGPC mostraram-se inferiores aos do AGT;

Mantendo-se fixos npop e pc, ao se dobrar a quantidade de gerações (maxgen), o tempo

de geração aproximadamente dobra.

Para P1, o AGCP geralmente forneceu uma quantidade maior de soluções não-

dominadas do que o AGT. Para P2 e P3, o AGT freqüentemente fornece as maiores

quantidades de tais soluções.

O pior desempenho do AGCP nos 3 problemas é observado quando pc = 0,5, o que é

evidenciado por valores Ze maiores do que os obtidos com as outras probabilidades.

O desempenho do AGCP em P1 e P2 foi melhor com pc = 1 e pc = 0,8, o que é

evidenciado por menores valores de Ze , e ↓ ; e em P3 quando pc = 1; Ze↓ Ze


102

O AGCP geralmente tem desempenho pior ou igual ao AGT quando se trabalha com

uma população pequena (npop = 50);

No problema P1, tanto o AGCP quanto o AGT alcançaram o valor ótimo do problema

auxiliar monobjetivo diversas vezes (Z* = -0,2). Contudo, a freqüência foi maior no

AGCP.

No problema P2, o AGCP algumas vezes alcançou o valor ótimo do problema auxiliar

monobjetivo (Z* = -8,9).

CAPÍTULO 9

CONCLUSÕES E PESQUISAS FUTURAS 9.1 Conclusões

Neste trabalho, considerou-se o problema restrito de localização de atividades

econômicas de base tecnológica através de uma abordagem normativa baseada na

programação matemática multiobjetivo.

Sugere-se um modelo linear multiobjetivo dinâmico 0-1 para este problema, cujas

restrições tratam questões de orçamento, operacionais e da interligação dos períodos de

tempo do horizonte de planejamento locacional. A abordagem multiobjetivo relaciona os

fatores locacionais dominantes, dois quantitativos e um qualitativo, aos objetivos do

problema, a saber, minimizar os custos de instalação/operação da atividade, minimizar o

tempo de acesso/conexão/atendimento da atividade ao seu centro de consumo e maximizar

obtenção dos benefícios agregados à localização. Sendo que a função do último objetivo é

o resultado da agregação de cinco outros fatores: economias de aglomeração,

disponibilidade de mão-de-obra qualificada, infra-estrutura local, tributação e incentivos

fiscais e qualidade de vida.

Este trabalho apresenta uma proposta de algoritmo genético, o chamado Algoritmo

Genético de Correção e Penalização (AGCP), para auxiliar a resolução do modelo

multiobjetivo dinâmico restrito sugerido. Nesse caso, o modelo substituto, referente a um

problema auxiliar monobjetivo, considera uma função escalar construída pela soma

ponderada dos três objetivos originais.

O AGCP resolve o problema, de forma interativa com o decisor, ao incorporar

procedimentos apropriados para lidar com as soluções inviáveis do problema tratado e um

teste de não-dominância nas melhores soluções viáveis obtidas. Esses procedimentos são

relativos aos operadores de correção e penalização propostos. O operador de correção

CAPÍTULO 9 – CONCLUSÕES E PESQUISAS FUTURAS

104

modifica as variáveis da solução para que algumas restrições sejam respeitadas, enquanto

que o operador de penalização impõe uma pena caso as demais restrições (de orçamento e

de não-relocalização) não sejam satisfeitas.

Além desses operadores, o AGCP considera um processo de geração aleatória

orientada para a obtenção de soluções viáveis iniciais e um operador de elitismo para

preservar as npop melhores soluções obtidas durante todo processo evolutivo.

Ao contrário do operador de correção que atua das variáveis x para as y , o

processo de geração da população inicial adotado, que é um processo aleatório orientado,

atua das variáveis y para as x .

ijt it

it ijt

Ao final da execução do AGCP, um conjunto de soluções não-dominadas da elite é

fornecido para a apreciação do decisor. Caso estas soluções não sejam satisfatórias, ou não

exista a certeza da importância dos fatores, inicia-se um processo interativo onde novos

valores de parâmetros são introduzidos no processo de evolução. Caso contrário, o

processo é finalizado.

O AGCP foi comparado com um Algoritmo Genético Tradicional (AGT). Sob as

mesmas condições, em média, o AGCP alcança uma melhor qualidade de soluções não-

dominadas da elite do que do AGT, chegando até a alcançar a solução ótima do problema

auxiliar monobjetivo em menos tempo. Apesar da qualidade dessas soluções se mostrarem

satisfatórias, constata-se a necessidade de explorar mais o tratamento de problemas

restritos em problemas de grandes dimensões, que ainda apresenta alto custo

computacional quando resolvidos pelo AGCP.

9.2 Pesquisas futuras

A pesquisa desenvolvida neste trabalho abre perspectivas para uma série de

pesquisas futuras:

Desenvolvimento de algoritmos genéticos com operadores de correção e penalização

das soluções inviáveis para auxiliar a resolução de outros tipos de modelos de

localização;

Gerar a população inicial do AGCP através de métodos heurísticos;

Considerar uma função escalar ponderada aumentada de Tchebychef (ver CORTES,

1998) como a função de avaliação da aptidão das soluções/cromossomos. Com a

CAPÍTULO 9 – CONCLUSÕES E PESQUISAS FUTURAS

105

incorporação do parâmetro ponto de referência na função de aptidão espera-se obter

soluções não-dominadas mais satisfatórias para o decisor e direcionar a busca no

espaço de critérios.

Realizar o teste de não-dominância das soluções da elite ao final de cada geração e não

somente ao final do processo evolutivo. Com isso, a elite será atualizada com novos

indivíduos viáveis e não-dominados.

Incorporar características estocásticas ao modelo multiobjetivo dinâmico, como por

exemplo, uma análise de cenários, com o intuito de explorar completamente as

características estratégicas dos problemas de localização;

Considerar a questão orçamentária em cada período ao invés de um orçamento único

para todo o horizonte. Dessa forma, o AGCP deverá sofrer uma alteração no

procedimento de geração da população inicial e outra alteração no operador de

penalização. O novos procedimentos devem considerar t restrições orçamentárias ao

invés de uma única.

Integrar o modelo multiobjetivo dinâmico e o algoritmo genético sugerido a um

Sistema de Informação Geográfica (SIG) e assim criar um sistema de apoio à decisão

multiobjetivo espacial (ver MALCZEWSKI, 1999);

Desenvolver um sistema de apoio à decisão que integre a abordagem de relação de

hierarquia com a programação multiobjetivo sugerida, a fim de auxiliar o decisor a

escolher uma das soluções não-dominadas fornecidas pelo algoritmo genético.

Considerar o caso de múltiplos níveis hierárquicos de atividades, como, por exemplo, o

problema de localização de estrutura organizacional descentralizada, onde em um nível

de atividade, tem-se uma única atividade que representa a matriz administrativa e a

unidade de P&D; e, em outro nível, várias atividades que representam as unidades

produtivas e que devem ser associadas a um conjunto de centros consumidores. Em

função das atividades relacionadas a esse problema possuírem naturezas distintas, a

importância dos fatores locacionais para cada nível será diferente, e, assim, os objetivos

não serão os mesmos para os dois níveis.

REFERÊNCIAS

ABO-SINNA, M.A.; HUSSEIN, M.L. (1995) An algorithm for generating solutions of multiobjective dynamic programming problems, European Journal of Operational Research, vol. 80, no. 1, pp. 156-165.

ABO-SINNA, M.A.; HUSSEIN, M.L. (1994) An algorithm for decomposing the parametric space in multiobjective dynamic programming problems, European Journal of Operational Research, vol. 73, no. 3, pp. 532-538.

ALVES, M.J; CLÍMACO, J. (2000) An interactive reference point approach for multiobjetive mixed-integer programming using branch-and-bound, European Journal of Operational Research, vol. 124, no. 3, pp. 478-494.

ARBEL, A.; KORHONEN, P. (1998) Using objective values to start multiple objective linear programming algorithms, International Institute for Applied Systems Analysis - IIASA, Interim Report IR-98-066/August, 17p.

AYTUG, H.; SAYDAM, C. (2002) Solving large-scale maximum expected covering location problems by genetic algorithms: a comparative study, European Journal of Operational Research, vol. 141, no. 3, pp. 480-494.

BALAKRISHNAN, A.; MAGNANTI, T.L.; SHULMAN, A.; WONG, R.T. (1991) Models for planning capacity expansion in local access telecommunication networks, Operations Research, vol. 33, pp. 239-284.

BALLOU, R. (1968) Dynamic warehouse location analysis, Journal of Marketing Research, vol. 5, pp. 271-276.

BEAN, J.C.; HIGLE, J.L.; SMITH, R.L. (1992) Capacity expansion under stochastic demands, Operations Research, vol. 40, pp. S210-S216.

BEASLEY, J. (1993) Lagrangean relaxation. In C.R. Reeves (ed.), Modern heuristic techniques for combinatorial problems, Blackwell Scientific Publications, Oxford, UK, pp. 243-303.

BEASLEY, J.; CHU, P.C. (1996) A genetic algorithm for the set covering problem, European Journal of Operational Research, vol. 94, pp. 392-404.

BERMAN, O.; DREZNER, Z. (2000) A note on the location of an obnoxious facility on a network, European Journal of Operational Research, vol. 120, no. 1, pp. 215-217.

BECKMANN, M. (1968) Location theory. Random House, Massachussets, USA.

BELL, D.; FARQUHAR, P. (1986) Perspectives on utility theory, Operations Research, vol. 34, no. 1, pp. 179-183.

REFERÊNCIAS

107

BERMAN, O.; DREZNER, Z. (2000) A note on the location of an obnoxious facility on a network, European Journal of Operational Research, vol. 120, no. 1, pp. 215-217.

BILDE, O.; KRARUP, J. (1977) Sharp lower bounds and efficient algorithms for the plant location problems, Annals of Discrete Mathematics, vol. 1, pp. 79-97.

BITRAN, G.R. (1979) Theory and algorithms for linear multiple objective programs with zero-one variables, Mathematical Programming, vol. 17, pp. 362-390.

BITRAN, G.R. (1977) Linear multiple objective programs with zero-one variables, Mathematical Programming, vol. 13, pp. 121-139.

BITRAN, G.R.; LAWRENCE, K.D. (1980) Locating service offices: a multicriteria approach, OMEGA, vol. 8, no. 2, pp. 201-206.

BLAIR, J.P. (1995) Local economic development: analysis and practice, Sage Publications, New Delhi, pp. 41-65.

BOFFEY B.; NARULA, S.C. (1997) Multiobjective covering and routing problems, Pesquisa Operacional, vol. 17, no. 1, pp. 1-28.

BRANDEAU, M.L.; CHIU, S.S. (1989) An overview of representative problems in location research, Management Science, vol. 35, no. 6, pp. 645-674.

CÁRIO, S.A.F.C.; PEREIRA, F.C.B. (2002) Inovação e desenvolvimento capitalista: referências histórica e conceitual de Schumpeter e dos neo-shumpeteriana para uma teoria econômica dinâmica, VII Encontro Nacional de Economia Política, Universidade Federal do Paraná, Curitiba, pp. 28-31.

CARVALHO, M.M.; MACHADO, S.A.; RABECHINI JR, R. (2000) Fatores críticos de sucesso em empresas de base tecnológica. Revista Produto & Produção, vol. 4, pp. 47-59.

CASTELLS, M. (1986) Mudança tecnológica, reestruturação econômica e a nova divisão espacial do trabalho. Espaço e Debates, vol. 17, pp. 5-23.

CASTRO, R.E. (2001) Otimização de estruturas com multi-objetivos via algoritmos genéticos. Tese de Doutorado em Ciências em Engenharia Civil, Rio de Janeiro, UFRJ.

CHO, D.C.; PADBERG, M. W.; RAO, M. R. (1981) On the uncapacitated plant location problem ii: facets and lifting theorems, Rapport de Recherche, IRIA, nº 87.

CHU, P.C.; BEASLEY, J.E. (1994) A genetic algorithm for the set partitioning problem, Technical Report, The Management School, Imperial College, London.

CHURCH, R.L.; REVELLE, C.S. (1976) Theoretical and computational links between the p-median, location set-covering, and the maximal covering location problem, Geographical Analysis, vol. 3, pp. 406-415.

CLEMENTE, A. (1998) Projetos empresariais e públicos, Editora Atlas, São Paulo, SP.

REFERÊNCIAS

108

CLÍMACO, J.C.N.; ANTUNES, C.H. (2000) Programação linear multiobjetivo: uma perspectiva interativa. In M.P.E. Lins and L.A. Meza (eds.), Análise envoltória de dados e perspectivas de integração no ambiente de apoio à decisão, COPPE/UFRJ, pp. 125-159.

CLÍMACO, J.C.N.; ANTUNES, C.H.; ALVES, M.J.G. (1996) Programação linear multiobjectivo: métodos interactivos, “software” e aplicações. Apostila. Faculdade de Economia da Universidade de Coimbra, Portugal, 258 p.

COELHO, J.D.; CAPITIVO, M. E. (1984) A lagrangean decomposition algorithm for the p-median problem, Tenth Triennial Conference on Operations Research, IFORS’84, Washington D. C., USA

COELLO, C.A.C. (1999a) A comprehensive survey of evolutionary-based multiobjective optimization techniques, Knowledge and Information Systems, vol.1, no.3, pp. 269-308.

COELLO, C.A.C. (1999b) List of references on evolutionary multiobjective optimization. Disponível em: <http://www.lania.mx/~ccoello/EMOO/EMOObib.html>. Acesso em: 23/MAI/02.

CONWAY, D.G.; VENKATARAMANAN, M.A. (1994) Genetic search and the dynamic facility layout problem, Computers & Operations Research, vol. 21, pp. 955-960.

CORNUEJOLS, G.; FISHER, M.L.; NEMHAUSER, G.L. (1977) Location of bank account to optimize float: an analytic study of exact and approximate algorithms, Management Science, vol. 23, pp. 789-810.

CORNUEJOLS, G.; THIZY, J.M. (1982) Some facets of the simple plant location polytope, Mathematical Programming, vol. 23, pp. 50-74.

CORTES, J.M.R. (1998) Uma contribuição para a resolução do problema de alocação multiobjetivo de plataformas de produção de petróleo. Dissertação de Mestrado em Ciências de Engenharia - Produção, Campos dos Goytacazes, UENF.

CHRISTOFIDES, N.; BEASLEY, J. E. (1982) A tree search algorithm for the p-median problem, European Journal of Operational Research, vol. 10, pp. 196-204.

CURRENT, J.; MIN, H.; SCHILLING, D. (1990) Multiobjective analysis of facility location decisions, European Journal of Operational Research, vol. 49, pp. 295-307.

DASKIN, M.S.; HOPP, W.J.; MEDINA, B. (1992) Forecast horizons and dynamic facility location planning, Annals of Operations Research, vol. 40, pp. 125-151.

DAVIS, L. (1991) Handbook of genetic algorithms, van Nostrand Reinhold, New York, USA.

DELGADILLO, R.S. (1997) Contribuições na resolução do problema multiobjetivo 0-1. Tese de Doutorado em Engenharia Industrial, Rio de Janeiro, PUC.

REFERÊNCIAS

109

DREZNER, T.; DREZNER, Z. (1998) Facility location in anticipation of future competition, Location Science, vol. 6, pp. 155-173.

DREZNER, Z.; WESOLOWSKY, G.O. (1991) Facility location when demand is time dependent, Naval Research Logistics, vol. 38, pp. 763-777.

DURRER, E.J.; SLATER, G.E. (1977) Optimization of petroleum and natural gas production: a survey, Management Science, vol. 24, no. 1, pp. 35-43.

EFROYMSON, M.A.; RAY, T.L. (1966) A branch and bound algorithm for plant location, Operations Research, vol. 14, pp. 361-368.

ENSSLIN, S.R. (1995) A estruturação no processo decisório de problemas multicritério complexos. Dissertação de Mestrado em Engenharia de Produção, UFSC.

ERLENKOTTER, D. (1981) A comparative study of approaches to dynamic location problems, European Journal of Operational Research, vol. 6, no. 2, pp. 133-143.

ERLENKOTTER, D. (1978) A dual based procedure for uncapacitated facility location. Operations Research, vol. 26, pp. 992-1009.

ESTALL, R.C.; BUCHANAN, R.O. (1976) Atividade industrial e geografia econômica. Zahar: Rio de Janeiro.

FALKENAUER, E.; DELCHAMBRE, A. (1992) A genetic algorithm for bin packing and line balancing, in Proceedings of the IEEE International Conference on Robotics and Automation.

FAIRLEY, A. (1991) Comparison of methods of choosing the crossover point in the genetic crossover operation, Technical Report, Department of Computer Science, University of Liverpool, Liverpool, UK.

FERNÁNDEZ, J.; FERNÁNDEZ, P.; PELEGRÍN, B. (2000) A continuous location model for siting a non-noxious undesirable facility within a geographical region, European Journal of Operational Research, vol. 121, no. 2, pp. 259-274.

FONSECA, C.M.; FLEMING, P.J. (1995) An overview of evolutionary algorithms in multiobjective optimization, Evolutionary Computation, vol. 3, no.1, pp. 1-16.

FONSECA, C.M.; FLEMING, P.J. (1993) Genetic algorithms for multiobjective optimization: formulation, discussion and generation. In S. Forrest (ed.), Proceedings of the Fifth International Conference Algorithms, San Mateo, California, pp. 416-423.

FRANCIS, R.L.; MCGINNIS, L.F.; WHITE, J.A. (1983) Locational analysis, European Journal of Operational Research, vol. 12, pp. 220-252.

GALVÃO, R.D. (1980) A dual bounded algorithm for the p-median problem, Operations Research, vol. 28, no. 5, pp. 1112-1121.

REFERÊNCIAS

110

GALVÃO, R.D.; NOBRE, F.F.; VASCONCELLOS, M.M. (1999) Modelos matemáticos de localização à organização espacial de unidades de saúde, Rev. Saúde Pública, vol. 33, no. 4, pp. 422-434.

GAREY, M.R.; JOHNSON, D.S. (1979) Computers and intractability: a guide to the theory of np-completeness. Freeman, New York.

GEOFFRION, A.M. (1971) Duality in nonlinear programming: a simplified applications oriented development, Siam Review, vol. 13, no. 1, pp. 137.

GHOSH, A.; CRAIG, S. (1983) Formulating retail location strategy in a changing environment, Journal of Marketing, vol. 47, pp. 56-68.

GLOVER, F.; LAGUNA, M. (1993) Tabu search, in Modern heuristic techniques for combinatorial problems, C.R. Reeves (ed.), Blackwell Scientific Publications, Oxford, UK, pp. 70-150.

GOLDBERG, D.E. (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley Publising Company, Reading, Massachussets.

GONÇALVES, E. (1999) Inserção de Juiz de Fora na indústria de tecnologia avançada: uma introdução sobre as possibilidades de regiões periféricas. Texto para Discussão no. 7, Núcleo de Pesquisas Econômicas, Faculdade de Economia e Administração, Universidade Federal de Juiz de Fora.

GONG, D.; YAMAZAKI, G.; GEN, M.; XU, W. (1999) A genetic algorithm method for one-dimensional machine location problems, International Journal Production Economics, vol. 1, no. 3, pp. 337-342.

GORE, C. (1984) Regions in question: space, development theory and regional policy. Methuen & Co, Chaucer Press, London.

GORGES-SCHLEUTER, M. (1989) ASPARAGOS: an asynchronous parallel genetic optimization strategy, in Proceeding of Third International Conference on Genetic Algorithms, J.D. Shaffer (ed.), Morgan Kaufmann, Los Altos, CA, pp. 422-427.

GREFENSTETTE, J.J. (1984) GENESIS: a system for using genetic search procedures . In Proceedings of the 1984 Conference on Intelligent Systems and Machines, pp. 161-165.

GUIGNARD, M. (1980) Fractional vertices, cuts, and facets of the simple plant location problem, Mathematical Programming, vol. 12, pp. 150-162.

GUNAWARDANE, G. (1982) Dynamic versions of set covering type public facility location problems, European Journal of Operational Research, vol. 10, pp. 190-195.

HAKIMI, S.L. (1964) Optimal locations of switching centers and medians of a graph, Operations Research, vol. 12, pp. 450-459.

HANNE, T. (1999) On the convergence of multiobjective evolutionary algorithms, European Journal of Operational Research, vol. 117, no. 3, pp. 553-564.

REFERÊNCIAS

111

HANSEN, P.; LABRE, M.; PEETERS, D.; THISSE, J. F. (1985) Single facility location on network, School on Combinatorial Optimization, Rio de Janeiro, vol. 819, July, 37 p.

HANSEN, P.; PEDROSA, E.; RIBEIRO, C. (1994) Modeling location and sizing of offshore platforms, European Journal of Operational Research, vol. 72, no. 3, pp. 602-606.

HEIZER, J.; RENDER, B. (2001) Operations management. 6 ed. Prentice-Hall, New Jersey.

HENIG, M.; RITZ, Z. (1986) Multiplicative decision rules for multiobjective decision problems, European Journal of Operational Research, vol. 26, pp. 134-141.

HINOJOSA, Y.; PUERTO J.; FERNÁNDEZ, F.R. (2000) A multiperiod two-echelon multicommodity capacitated plant location problem, European Journal of Operational Research, vol. 123, no. 2, pp. 271-291.

HOLLAND, J.H. (1975) Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control and artificial intelligence. MIT Press, Cambridge, Masssachussets.

HÖHN, C.; REEVES, C.R. (1995) Embedding local search operators in a genetic algorithm, Technical Report, School of Mathematical and Information Sciences, Coventry University, Coventry, UK.

HOOVER, E.M.; GIARRATANI, F. (1999) An introduction to regional economics. Disponível em: <http://rri.wvu.edu/WebBook/Giarratani/preface.htm>. Acesso em: 27/ABR/01.

HORN, J.; NAFPLIOTIS, N. (1993) Multiobjective optimization using the Niched Pareto Genetic Algorithm. Technical Report IlliGAl Report 93005, University of Illinois, Urbana-Champaign.

HOSAGE, C.M.; GOODCHILD, M.F. (1986) Discrete space location-allocation solutions from genetic algorithm, Operations Research, vol. 6, pp. 35-46.

HOUCK, C.R.; JOINES, J.A.; KAY, M.G. (1996) Comparison of genetic algorithms, random restart and two-opt switching for solving large location-allocation problems, Computers & Operations Research, vol. 23, pp. 587-596.

IAKOVOU, E.; IP, C.M.; DOULIGERIS, C.; KORDE, A. (1997) Optimal location and capacity of emergency cleanup equipment for oil spill response, European Journal of Operational Research, vol. 96, no. 1, pp. 72-80.

JARAMILLO, J.H.; BHADURY, J.; BATTA, R. (2002) On the use of genetic algorithms to solve location problems, Computers & Operations Research, vol. 29, no. 6, pp. 761-779.

JORDAN, C. (1869) Sur les assemblages de lignes, J. Reine Angew Math 70, pp. 185-190.

http://rri.wvu.edu/WebBook/Giarratani/preface.htm

REFERÊNCIAS

112

KEENEY, R. (1992) Value-focused thinking: a path to creative decision making. Harvard University Press, London.

KEENEY, R.; RAIFFA, H. (1976) Decisions with multiple objectives: preferences and value trade-offs. Wiley, New York.

KORHONEN, P. (1998) Multiple objective programming support, international institute for applied systems analysis - IIASA, Interim Report IR-98-010/March, 16p.

KORHONEN, P.; KARAIVANOVA, J. (1998) An algorithm for projecting a reference direction onto the nondominated set of given points, International Institute for Applied Systems Analysis - IIASA, Interim Report IR-98-011/March, 18p.

KORHONEN, P.; LAAKSO, J. (1986) A visual interactive method for solving the multiple criteria problem, European Journal of Operational Research, vol. 24, pp. 277-287.

KOWALSKA, J.D.; FUNCK, R.H. (2000) Cultural activities as a location factor in european competition between regions: concepts and some evidence, Regional Science, vol. 34, no. 1, pp. 1-12.

KRAJEWSKI, J.; RITZMAN, B. (1999) Operations management: strategy and analysis. 5 ed. Addison-Wesley Publishing, New York.

KRARUP, J.; PRUZAN, P.M. (1983) The simple plant location problem: survey and synthesis, European Journal of Operational Research, vol. 12, pp. 36-81.

LASDON, L.S. (1970) Optimization theory for large systems, Macmillan P. Co.

LEE. S.M.; GREEN, G.I.; KIM, C.S. (1981) A multiple criteria model for the location-allocation problem, Computers and Operations Research, vol. 8, pp. 1-8.

LENIVE, D. (1997) Genetic algorithms: a practitioner’s view, Journal on Computing, vol. 9, no. 3, pp. 256-259.

LI, D.; HAIMES, Y.Y. (1989) Multiobjective dynamic programming: the state of the art, Control-Theory and Advanced Technology, vol. 5, no. 4, pp. 471-483.

LIN, W.T. (1980) An accounting control system structured on multiple objective planning models, OMEGA, vol. 8, no. 3, pp. 375-382.

LOSCH, A. (1954) The economics of location, Yale U.P., New Haven.

MALCZEWSKI, J. (1999) GIS and multicriteria decision analysis. John Willey and Sons, New York.

MALECKI, E.J. (1997) Technology & economic development: the dynamics of local, regional and national competitiveness, Longman, England, Second Edition, pp. 112-156.

MALECKI, E.J. (1987) The R&D location decision of the firm and “creative” regions – a survey, Technovation, vol. 6, pp. 205-222.

REFERÊNCIAS

113

MALIZIA, E.E.; FESER, E.J. (1999) Understanding local economic development. Center for Urban Policy Research, New Jersey, 298 p.

MACCORMAK, A.D.; NEWMANN, L.I.; ROSENFELD, D.B. (1994) The new dynamics of global manufacturing site location, Sloan Management Review, vol. 35, no.4, pp. 69-80.

MAGNANTI, T.L.; WONG, R.T. (1981) Accelerated Benders decomposition: algorithmic enhancement and model selection criteria, Operations Research, vol. 29, pp. 464-484.

MASSAN, B.H. (2002) Quality of life: public planning and private living. Progress in Planning, vol. 58, no. 3, pp. 141-227.

MATHIAS, K.; WHITLEY, D. (1992) Genetic operators, the fitness landscape and the traveling salesman problem, in Parallel Problem-Solving from Nature 2, R. Männer and B. Manderick (eds.), Elsevier Science Publishers, Amsterdam, pp. 219-228.

MEIJBOOM, B.R.; RONGEN, J.M.J. (1995) Clustering, logistics and spatial economies. Disponível em: <http://www.citeseer.nj.nec.com/434054.html>.Acesso em: 11/MAI/01.

MELACHRINOUDIS, E.; MIN, H. (2000) The dynamic relocation and phase-out of a hybrid, two-echelon plant/warehousing facility: a multiple objective approach, European Journal of Operational Research, vol. 123, no. 1, pp. 1-15.

MELKOTE, S.; DANSKIN, M.S. (2001) Capacitated facility location/network design problems, European Journal of Operational Research, vol. 129, no. 3, pp. 481-495.

MEYER-STAMER, J. (2000) Estratégias de desenvolvimento local e regional: clusters, política de localização e competitividade sistêmica. Fundação Empreender, SC. Disponível em: <http://www.desarrollolocal.org/documentos/deslocal.pdf>. Acesso em: 05/OUT/00.

MIN, H. (1988) Dynamic expansion and relocation of capacitated public facilities: a multi-objective approach, Computers and Operations Research, vol. 15, no. 3, pp. 243-252.

MIN, H.; MELACHRINOUDIS, E. (1999) The relocation of a hybrid manufacturing/ distribution facility from supply perspectives: a case study, Omega, vol. 27, no.1, pp. 75-85.

MINIEKA, E. (1977) The centers and medians of a graph, Operations Research, vol. 25, pp. 641-650.

MIRZAIAN, A. (1985) Lagrangian relaxation for the star-star concentrator location problem: approximation algorithm and bounds, Networks, vol. 15, pp. 1-20.

MOON, C.; KIM; J., CHOI, G.; SEO, Y. (2002) An efficient genetic algorithm for the traveling salesman problem with precedence constraints, European Journal of Operational Research, vol. 140, no. 3, pp. 606-617.

http://www.desarrollolocal.org/documentos/deslocal.pdf

REFERÊNCIAS

114

MULVEY, J.M.; VANDERBEI, R.J.; ZENIOS, S.A. (1995) Robust optimization of large-scale systems. Operations Research, vol. 43, no. 2, pp. 264-281.

NARULA, S.C.; OGBU, U.L.; SAMUELSSON, H.M. (1977) An algorithm for the p-median problem, Operations Research, vol. 25, pp.709-713.

NEMHAUSER, G.L.; WOLSEY, L.A. (1978a) An analysis of approximations for maximizing submodular set functions I, Mathematical Programming, vol. 14, pp. 265-294.

NEMHAUSER, G.L.; WOLSEY, L.A. (1978b) An analysis of approximations for maximizing submodular set functions II, Mathematical Programming Study, vol. 8, pp. 73-87.

NIJKAMP, P.; SPRONK, J. (1981) Interactive multidimensional programming models for locational decisions, European Journal of Operational Research, vol. 6, pp. 220-223.

NIJKAMP, P.; SPRONK, J. (1979) Analysis of production and location decisions by means of multicriteria analysis, Engineering and Process Economics, vol. 4, pp. 285-302.

ORVOSH, D.; DAVIS, L. (1993) Shall we repair? Genetic algorithms, combinatorial optimization and feasibility constraints, in Proceedings of Fifth International Conference on Genetic Algorithms, S. Forrest (ed.), Morgan Kaufmann, San Mateo, CA, pp. 650.

OWEN, S.H.; DASKIN, M.S. (1998) Strategic facility location: a review, European Journal of Operation Research, vol. 111, no. 3, pp. 423-447.

PAULA JUNIOR, G. G. (1986) Um algoritmo de decomposição primal para solução de um problema dinâmico de localização de p-medianas e sua aplicação na produção industrial de carvão vegetal. Tese de Doutorado, Rio de Janeiro, COPPE/UFRJ.

PELEGRIN, P.; FERNANDEZ, F.R. (1988) Determination of efficient points in multiple-objective location problems, Naval Research Logistics, vol. 35, pp. 697-705.

PLASTRIA, F. (2001) Static competitive facility location: an overview of optimization approaches, European Journal of Operation Research, vol. 129, no. 3, pp. 461-470.

PORTER, M.E. (1999a) On competition: competição, estratégias competitivas essenciais, 4 ed. Ed. Campus, Rio de Janeiro.

PORTER, M.E. (1999b) Clusters e competitividade, HSM Management, no. 15, pp. 100.

PORTER, M.E. (1990) Vantagem competitiva: criando e sustentando um desempenho superior, Ed. Campus: Rio de Janeiro.

PSARAFTIS, H.N.; THARAKAN, G.G.; CEDER, A. (1986) Optimal response to oil spills: the strategic decision case, Operations Research, vol. 34, no. 2, pp. 203-217.

REFERÊNCIAS

115

PSARAFTIS, H.N.; ZIOGAS, B.O. (1985) A tactical decision algorithm for optimal dispatching of oil spill cleanup equipment, Management Science, vol. 31, pp. 1475-1491.

RADCLIFFE, N.J. (1991) Equivalence class analysis of genetic algorithms, Complex Systems, vol. 5, pp.183-205.

RADCLIFFE, N.J.; GEORGE, F.A.W. (1993) A study in set recombination, in Proceedings of Fifth International Conference on Genetic Algorithms, S. Forrest (ed.), Morgan Kaufmann, San Mateo, CA, pp. 23-30.

RAHMAN, S.; SMITH, D.K. (2000) Use of location-allocation models in health service development planning in developing nations, European Journal of Operational Research, vol. 123, no. 3, pp. 437-452.

REES, J.; STAFFORD, H.A. (1986) Technology, regions and policy. Rowan & Littlefield Publishers, New Jersey, 322 p.

REEVES, C.R. (1997) Genetic algorithms for the operations researcher, Journal on Computing, vol. 9, no. 3, pp. 231-250.

REEVES, C.R. (1996) Hybrid genetic algorithms for bin-packing and related problems, Operations Research, vol. 63, pp. 371-396

REVELLE, C.S.; COHON, J.L.; SHOBYS, D. (1981) Multiple objectives in facility location: a review. In M. Beckmann and A.P. Kunzi (eds.), Lecture Notes in Economics and Mathematical Systems, vol. 190, pp. 321-337.

REVELLE, C.S.; LAPORTE, G. (1996) The plant location problem: new models and research prospects, Operations Research, vol. 44, no. 6, pp. 864-874.

REVELLE, C.; MARKS, D.; LIEBMAN, J.C. (1970) An analysis of private and public sector location models, Management Science, vol. 16, no. 11, pp. 692-707.

ROCKAFELLAR, R.T. (1970) Convex Analysis, Princeton University Press.

ROSS, G.T.; SOLAND, R.M. (1980) A multicriteria approach to the location of public facilities, European Journal of Operational Research, vol. 4, pp. 307-321.

ROY, B. (1990) Decision aid and decision making. European Journal of Operational Research, vol. 45, pp. 324-331.

SARKER, R.; LIANG, K-H.; NEWTON, C. (2002) A new multiobjetctive evolutionary algorithm, European Journal of Operational Research, vol. 140, no. 1, pp. 12-23.

SCHAFFER, J.D. (1985) Multiple objective optimization with vector evaluated genetic algorithms. In J.J. Grefenstette (ed.), Proceedings of the first international conference on genetic algorithm and their applications, pp. 93-100, Lawrence Erlbaum, Hillsdale, New Jersey.

REFERÊNCIAS

116

SCHILLING, D.A. (1982) Strategic facility planning: the analysis of options, Decision Sciences, vol. 13, pp. 1-14.

SCHILLING, D.A. (1980) Dynamic location modeling for public-sector facilities: a multicriteria approach, Decision Sciences, vol. 11, pp. 714-724.

SCHRAGE, L. (1975) Implicit representation of variable upper bounds in linear programming, Mathematical Programming Study, vol. 4, pp. 118-132.

SEPPÄLÄ, U. (1997) An evolutionary model for spatial location of economic facilities, International Institute for Applied Systems Analysis - IIASA, Interim Report IR-97-003/February, 30p.

SEXTON, R.S.; DORSEY, R.E.; JOHNSON, J.D. (1999) Optimization of neural networks: a comparative analysis of the genetic algorithm and simulated anneling, European Journal of Operational Research, vol. 114, no. 3, pp. 589-601.

SHAFFER, J.D.; ESHELMAN, L.J. (1996) Combinatorial optimization by genetic algorithms: the value of the genotype/phenotype distinction, in Modern Heuristic Search Methods, V.J. Rayward-Smith, L.H. Osman, C.R. Reeves and G.D. Smith (eds.), John Wiley & Sons, New York, pp. 85-97.

SHULMAN, A. (1991) An algorithm for solving dynamic capacitated plant location problem with discrete expansion sizes, Operations Research, vol. 39, no. 3, pp. 423-436.

SISKOS, Y.; SPYRIDALKOS, A. (1999) Intelligent multicriteria decision support: overview and perspectives, European Journal of Operational Research, vol. 113, no. 2, pp. 236-246.

SMITH, A.E.; TATE, D.M. (1993) Genetic optimization using a penalty function, in Proceedings of Fifth International Conference on Genetic Algorithms, S. Forrest (ed.), Morgan Kaufmann, San Mateo, CA, pp. 499-505.

SOUZA, C.C.A. (2002) Área metropolitana de Belo Horizonte versus área metropolitana de Curitiba: um estudo comparativo dos fatores de atração. Dissertação de Mestrado em Ciências Econômicas, Faculdade de Ciências Econômicas, UFMG.

SRINIVAS, M.; DEB, K. (1993) Multiobjective using Nondominated Sorting in Genetic Algorithms. Technical Report, Department of Mechanical Engineering, Indian Institute of Technology.

SRINIVAS, M.; PATNAIK, L.M. (1994) Genetic algorithms: a survey, IEEE Computer, vol. 27, no. 6, pp. 37-47.

STARKWEATHER, T.; MCDANIEL, S.; MATHIAS, K.; WHITLEY, D.; WHITLEY, C. (1991) A comparison of genetic sequencing operators, in Proceedings of Fourth International Conference on Genetic Algorithms, R.K. Belew and L.B. Booker (eds.), Morgan Kaufmann, San Mateo, CA, pp. 69-76.

REFERÊNCIAS

117

STEUER, R.E. (1986) Multiple criteria optimization: theory, computation and application. John Wiley & Sons, New York.

STEUER, R.E.; CHOO, E.U. (1983) An interactive weighted Tchebychef procedure for multiple objective programming. Mathematical Programming, vol. 26, pp. 326-344.

SWEENEY, D.J.; TATHAM, R.L. (1976) An improved long-run model for multiple warehouse location, Management Sciences, vol. 22, no. 7, pp. 748-758.

TAM, K.Y. (1992) Genetic algorithms, function optimization and layout design, European Journal of Operational Research, vol. 63, pp. 322-346.

TANSEL, B.C.; FRANCIS, R.L.; LOWE, T.J. (1983) Location on networks: a survey. Part i: the p-center and p median problems, Management Science, vol. 29, no. 4, pp. 482-497.

TAUXE, G.W.; INMAN, R.R.; MADES, D.M. (1979) Multiobjective dynamic programming: a classic problem redressed, Water Resources Research, vol. 15, no. 6, pp. 1398-1402.

TEITZ, M.B.; BART, P. (1968) Heuristic methods for estimating the generalized vertex median of a weighted graph, Operations Research, vol. 16, pp. 955-961.

TODD, M.J. (1982) An implementation of the simplex method for linear programming problems with variable upper bounds, Mathematical Programming, vol. 23, pp. 34-49.

TOREGAS, C.; SWAIN, R.; REVELLE, C.; BERGMAN, L. (1971) Location of emergency service facilities, Operations Research, vol. 19, pp. 1366-1373,

TRAGANTALERNGSAK, S.; HOLT, J.; RÖNNQVIST, M. (2000) An exact method for the two-echelon, single-source, capacitated facility location problem, European Journal of Operational Research, vol. 123, pp. 473-489.

ULDER, N.L.J.; AARTS, E.H.L.; BANDELT, H.J.; LAARHOVEN, P.J.M.; PESCH, E. (1991) Genetic local search algorithms for the traveling salesman problem, in Parallel Problem-Solving from Nature, H.P. Shwefel and R. Männer (eds), Springer-Verlag, Berlin, pp. 109-116.

Van ROY, T.J.; ERLENKOTTER, D. (1982) A dual-based procedure for dynamic facility location, Management Science, vol. 28, no. 10, pp. 1091-1105.

Von THÜNEN, J.H. (1866) Isolated state an English edition of der isolierte staat. Trans. C.M. Watengerg. Oxford: Pergamon.

Van VELDHUIZEN, D.A.V.; LAMONT, G.B. (2000) Multiobjective evolutionary algorithms: analyzing the state-of-the-art, Evolutionary Computation, vol. 8, no. 2, pp. 125-147.

WEBER, A. (1909) Theory of the location of industries. Trans. C.J. Freidrich. Chicago: University of Chicago Press.

REFERÊNCIAS

118

WESOLOWSKY, G.O. (1973) Dynamic facility location, Management Science, vol. 19, no. 11, pp. 1241-1248.

WESOLOWSKY, G.O.; TRUSCOTT, W.G. (1975) The multiperiod location-allocation problem with relocation of facilities, Management Science, vol. 22, no. 1, pp. 57-65.

WIERZBICKI, A.P. (1983) Critical essay on the methodology of multiobjective analysis, Regional Science and Urban Economics, vol. 13, pp. 5-29.

WIERZBICKI, A.P. (1982) A mathematical basis for satisfacting decision making, Mathematical Modelling, vol. 3, pp. 391-408.

WONG, R.T. (1984) Recent advances in location and network design models for transportation planning, Working paper, Krannert Graduate School of Management, Purdue University,

WONG, R.T. (1983) Recent research on location and network design problems: an annotated bibliography, Proceedings of the Summer School on Combinatorial Optimization, Dublin.

WREN, A.; WREN, D.O. (1995) A genetic algorithm for public transport scheduling, Computers & Operations Research, vol. 22, pp. 101-110.

ZHOU, G.; MIN, H.; GEN, M. (2002) The balanced allocation of customers to multiple distribution centers in the supply chain network: a genetic algorithm approach, Computers & Industrial Engineering, vol. 43, no. 1, pp. 251-261.

ZOPOUNIDIS, C. (1999) Multicriteria decision aid in financial management, European Journal of Operational Research, vol. 119, no. 2, pp. 404-415.

ZOOK, M.A. (2000) Technological innovation and theories of regional development. Disponível em: <http://garnet.berkeley.edu/~zook/pubs/Inside_Field.html>. Acesso em: 05/OUT/00.

http://garnet.berkeley.edu/~zook/pubs/Inside_Field.html

Documents

“Tese apresentada ao Centro de Ciência e Tecnologia, da ... · UM ALGORITMO GENÉTICO PARA SOLUÇÃO DO PROBLEMA DE LOCALIZAÇÃO DE ATIVIDADES ECONÔMICAS ... desenvolvido resultou