DESAFIOS APLICADOS EM
LOCALIZAÇÃO
Pontifícia Universidade Católica do Rio de Janeiro
Departamento de Engenharia Industrial
Nélio D. Pizzolato
Sumário
1.
2.
3.
4.
5.
Introdução
Tipologias metodológicas
Localização
Overview de modelos de localização
Resolução de um PLI
Introdução
Weber (1909)
Introdução
• Enfoques
– Prático
– Aplicado
– Acadêmico
Introdução
• Enfoque prático
– Localização dos materiais de produção
(insumos);
– Disponibilidade de mão de obra;
– Terrenos disponíveis, clima, fatores
topográficos;
– Distância da fonte de combustível industrial.
– Facilidades de transporte;
Introdução
• Enfoque prático
– Distância e dimensão do mercado e
facilidades de distribuição;
– Disponibilidade de energia, água, telefones,
redes de esgoto;
– Condições de vida, leis e regulamentos,
incentivos;
– Estrutura tributária.
Introdução
• Enfoque aplicado
– Proposta de Modelos;
– Aplicação de Metodologias;
– Validação de Resultados;
– Implementação de Soluções.
Introdução
• Enfoque acadêmico
– Proposta de Modelos;
– Desenvolvimento de Heurísticas;
– Desenvolvimento de Meta-heurísticas;
– Desenvolvimento de Métodos Exatos.
Tipologias metodológicas
• Diagrama de Voronoi
– Tipo de partição do espaço métrico
– Resulta em polígonos convexos
Tipologias metodológicas
• Diagrama de Voronoi (Definição)
– Seja um conjunto de
instalações,
– Seja
a localização da instalação .
– Suponha cada instalação espacialmente
distinta
– Seja
uma localização arbitrária de um
ponto no plano.
Tipologias metodológicas
• Diagrama de Voronoi (Definição)
– A distância euclidiana entre
e
é
– A região
para
é chamada de polígono ordinário de Voronoi
da instalação .
Tipologias metodológicas
• O problema da p-mediana
Min
Sujeito a:
Localização
• Localização no plano
• Localização em redes
Localização no plano
Localização
• Localização no plano
Sejam os pontos e , a distância entre eles
é dada por:
– Métrica euclidiana
– Métrica metropolitana
Localização
• Localização no plano
– Centro de gravidade
Seja
o peso total de todos os pontos, as
coordenadas
do ponto
podem ser
calculadas pelas expressões:
• Localização de Sirenes (Illinois).
O’Kelly e Murray (2004)
• Localização de heliportos (RJ).
Martins e Pizzolato (2004)
• Plataformas de petróleo no mar.
Estrella (2010)
• Localização de Hubs
Figueiredo (2010)
• Localização de hospitais
Töreyen (2007)
Localização
• Localização em redes
Hakimi(1966)
• Rede com vértices e arcos
• Localização de escolas (RJ)
Pizzolato et al. (2004)
• Localização de escolas (RJ)
Pizzolato et al. (2004)
• Localização de escolas (RJ) usando GIS.
Menezes(2010)
• Localização de unidades de educação
infantil
Lobo (2003)
• Localização de unidades de educação
infantil
Lobo (2003)
• Localização de Shopping Centers
Rozental e Pizzolato (2009)
• Localização de Shopping Centers
Rozental e Pizzolato (2009)
• Localização de maternidades
Galvão et al.(2002)
Métodos de Solução para a pmediana
• Métodos Heurísticos
–
–
–
–
Método guloso
Método de Maranzana
Método de Teitz e Bart
Outros.
• Métodos Exatos
– Programação Linear
inteira.
– Métodos
Lagrangeanos.
Overview dos modelos de
localização
1. Modelo p-mediana com custos fixos
2. Modelo p-mediana capacitado
3. Problema de localização de uma planta
simples
4. Problema da localização com cobertura
completa
5. Problema da localização com máxima
cobertura
6. Localização de Hubs
1. Modelo p-mediana com custos fixos
Min
Sujeito a:
2. Modelo p-mediana capacitado
Min
Sujeito a:
3. Problema de localização de uma planta
simples
Min
Sujeito a:
4. Problema da localização com
cobertura completa
Min
Sujeito a:
5. Problema da localização com
cobertura máxima
Max
Sujeito a:
6. Localização de Hubs
Min
Sujeito a:
Resolução de um PLI
•
•
•
•
•
Branch-and-bound
Métodos dos planos de corte
Método lagrangeano
GRASP
Etc.
Referências
•
•
•
•
•
•
Boots, B. e South, R. Modeling Retail Trade Areas Using Higher-Order,
Multiplicatively Weighted Voronoi Diagrams. Journal of Retailing, 73 (4), 1997, pp
519-536.
Brandeau, M.L. e Chiu, S.S. An Overview of Representative Problems in
Location Research. Management Science, 35, 1989, pp. 645-674.
Buarque, Cristovam. Avaliação Econômica de Projetos. Campus 2ed., Rio de
Janeiro, 1986, 266 p.
Current J., M. Daskin e D. Schilling. Discrete Network Location Models em
Drezner Zvi e Hamacher H. W. Facility Location: Applications and Theory,
Springer Verlag, 2002, pp. 81-121.
Drezner, Z.; Klamroth, K.; Schöbel, A. e Wesolowsky, G.O. The Weber Problem, em
Drezner, Z. e Hamacher, H.W. Facility Location: Applications and Theory.
Springer, New York, 2002, pp. 1-36.
Estrella, Eduardo, Localização de Plataformas Marítimas. Dissertação de
Mestrado, PUC/Rio, 2010.
Referências
•
•
•
•
•
•
Farahani, R. Z. e Hekmatfar (eds), Facility Location: Concepts, Models,
Algorithms and Case Studies: Contributions to Management Science, PhysicaVerlag Heidelberg, 2009.
Feo, T.A. e Resende, M.G.C. Greedy Randomized Adaptive Search Procedures.
Journal of Global Optimization, Vol. 6, 1995, pp. 109–133.
Figueiredo, R.M.A de. Estratégia Hub-and-Spoke em Redes de Transporte Aéreo:
Uma Contribuição para Modelar Casos na América do Sul e no Brasil. Tese de
Doutorado. PUC/Rio, 2010.
Galvão, Roberto D.; Acosta, L.G.E. e Boffey, B. A Hierarchical Model for the
Location of Perinatal Facilities in Municipality of Rio de Janeiro. European
Journal of Operational Research, 138, 2002, pp. 495-517.
Hakimi S. Optimum Locations of Switching Centers and the Absolute Centers
an Median of a Graph. Operation Research, 12, 1964, pp. 450-459.
Iannoni, A.P. e Morabito, R. Otimização da localização das bases de ambulâncias
e do dimensionamento das suas regiões de cobertura em rodovias. Produção
Vol. 18, N. 1, 2008, pp. 47-63.
Referências
•
•
•
•
•
•
•
Kershner, R. The Number of Circles Covering a Set. American Journal of
Mathematics, 61, 1939, pp. 665-671.
Lobo, Debora da Silva. Dimensionamento e Otimização Locacional de Unidades
de Educação Infantil. Tese de Doutorado, UFSC, 2003.
Martins, Isnard e Pizzolato, N. D. Utilização da p-mediana para Simulação de
Bases Táticas de Helicópteros Policiais. XII SIMPEP, Bauru – SP, 2004.
Menezes, Rafael C. O uso do SIG – Sistema de Informação Geográfico – para o
apoio à decisão no planejamento da localização das Escolas Municipais em
Guaratiba, Rio de Janeiro. Dissertação de Mestrado, PUC/Rio, 2010.
O’Kelly, M.E. e A.T. Murray. A Lattice Covering Model for Evaluating Existing
Service Facilities. Regional Science, 83, 2004, pp 565-580.
Okabe, A. e Suzuki, A. Locational Optimization Problems Solved through
Voronoi Diagrams. European Journal of Operational Research, 98, 1997, pp. 445456.
Pizzolato, N. D. A Heuristic for Large-Size p-median Location Problems with
Application to School Location, Annals of Operations Research, 50, 1994, pp. 473485.
Referências
•
•
•
•
•
•
•
Pizzolato, N. D.; Barros, A G; Barcelos, F. B. e Canen, A.G. Localização de Escolas
Públicas: Síntese de Algumas Linhas de Experiências. Pesquisa Operacional,
Vol. 24, No 1, 2004, pp. 111-131.
Reese, J. Methods for Solving the p-Median Problem: An Annotated
Bibliography. Department of Mathematics, Trinity University, San Antonio, Texas,
EUA, 2005.
Resende, M.G.C. e Werneck, R. F. A Hybrid Heuristic for the p-Median Problem.
Journal of Heuristics 10, vol.1, pp. 59-88, 2004.
ReVelle, C.; D. Marks e J.C. Liebman. An Analysis of Private and Public Sector
Location Models. Management Science, 16, 1970, pp. 692-707.
ReVelle, C.S. e Eiselt, H. A. Location Analysis: A Synthesis and Survey.
European Journal of Operational Research, 165, 2005, pp. 1-19.
Reese, J. Methods for Solving the p-Median Problem: An Annotated
Bibliography. Department of Mathematics, Trinity University, San Antonio, Texas,
EUA, 2005.
Resende, M.G.C. e Werneck, R. F. A Hybrid Heuristic for the p-Median Problem.
Journal of Heuristics 10, vol.1, pp. 59-88, 2004.
Referências
•
•
•
•
•
•
ReVelle, C.; D. Marks e J.C. Liebman. An Analysis of Private and Public Sector
Location Models. Management Science, 16, 1970, pp. 692-707.
ReVelle, C.S. e Eiselt, H. A. Location Analysis: A Synthesis and Survey.
European Journal of Operational Research, 165, 2005, pp. 1-19.
Rosa, Vinicius, e Ferreira Filho V.J. Otimização da Localização de Plataformas de
Produção, em Rio Oil&Gás Expo and Conference, Vol. 1, Rio de Janeiro, 1114/09/2006, pp. 1-8.
Rozental, M. e Pizzolato, N.D.Localização de Shopping Center de Vizinhança
Estudo de Caso: Barra da Tijuca, Rio de Janeiro. Podes, Pesquisa Operacional
para o Desenvolvimento, Vol 1 (3), 2009.
Teitz, M e Bart, P. Heuristic Methods for Estimated Generalized Vertex Median of
a Weighted Graph. Operations Research, 16, 1968, pp. 955-961.
Teixeira, João C. e Antunes, António P. A Hierachical Location Model for Public
Facility Planning. European Journal of Operational Research, 185, 2008, pp. 92104.
Referências
•
•
•
Töreyen, Özgün. Hierarchical Maximal Covering Location Problem with Referral
in the presence of Partial Coverage. These M.Sc., Middle East Technical
University, Turkish, 2007.
Weber, A., Über den Standort der Industrien, Tübingen, Germany, 1909. English
Translation: Friederich, C.J., Theory of the Location of Industries. The University
of Chicago Press, Chicago, 1929.
Wolsey, L.A. Integer Programming. Editora John Wiley & Sons, 1998.
Perguntas ?
?