Integração de modelos de localização a sistemas de informações geográficas
Open Access
- 1 August 2001
- journal article
- Published by FapUNIFESP (SciELO) in Gestão & Produção
- Vol. 8 (2) , 180-195
Abstract
O problema de p-medianas consiste em decidir onde localizar p centros em uma rede composta por vértices e arestas, de forma a minimizar a soma de todas as distâncias de cada vértice ao centro mais próximo. Em alguns casos, quando uma demanda estiver associada a cada vértice, pode haver restrições na capacidade de atendimento dos centros (problema de pmedianas com restrições de capacidade). Modelos de localização de facilidades têm sido propostos como ferramentas de auxílio à decisão, principalmente quando é possível usar Sistemas de Informações Geográficas (SIGs) na coleta e análise dos dados dos problemas. Apresentamos neste trabalho um relato da integração de modelos de p-medianas aos SIGs ArcView, da ESRI, e SPRING, um sistema desenvolvido no INPE. O código que foi integrado a estes SIGs implementa uma abordagem recente da heurística Lagrangiana/ surrogate, onde a viabilização da solução dual é feita através de uma heurística de localização-alocação alternada. O trabalho apresenta alguns testes computacionais usando dados do município de São José dos Campos, com tamanhos variando até o máximo de 3280 vértices e 1141 centros, para o caso sem restrições de capacidade.Keywords
This publication has 18 references indexed in Scilit:
- Lagrangean/surrogate relaxation for generalized assignment problemsEuropean Journal of Operational Research, 1999
- Relaxation heuristics for a generalized assignment problemEuropean Journal of Operational Research, 1996
- A surrogate heuristic for set covering problemsEuropean Journal of Operational Research, 1994
- Lagrangean heuristics for location problemsEuropean Journal of Operational Research, 1993
- A method for solving to optimality uncapacitated location problemsAnnals of Operations Research, 1989
- A tree search algorithm for the p-median problemEuropean Journal of Operational Research, 1982
- Calculating surrogate constraintsMathematical Programming, 1980
- A dual algorithm for the constrained shortest path problemNetworks, 1980
- Some relationships between lagrangian and surrogate duality in integer programmingMathematical Programming, 1979
- The traveling-salesman problem and minimum spanning trees: Part IIMathematical Programming, 1971