Upload
others
View
3
Download
0
Embed Size (px)
Citation preview
Alexandre B. Gonçalves
Instituto Superior Técnico, Univ. de Lisboa
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Os Sistemas de Informação
Geográfica e a Otimização
Espacial no Apoio à Decisão: Problemas, Modelos e Soluções
SIG
• Processam informação geográfica
• Possibilitam análise espacial:
cruzam conjuntos de dados
geográficos com base na localização
– Encontrar locais que verificam
determinadas condições ou critérios
– Problemas com uma só solução
Obter a área agrícola a menos de 1000 m das
estradas nacionais no concelho de Alcoutim.
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Exemplo
• Alcoutim
12/7/2014 Instituto Superior Técnico
12/7/2014 Instituto Superior Técnico
12/7/2014 Instituto Superior Técnico
5235 ha
• Ramo da Matemática Aplicada – baseada nos trabalhos de matemáticos dos séculos
XVII a XX (Newton, Leibnitz, Bernoulli, Lagrange, Fourier, Babbage, Monge, von Neumann, Kantorovich, Stigler,...)
– apoio à decisão (sobre recursos)
– modelos matemáticos • formalização da teoria da decisão
• análise da estrutura de problemas
– métodos analíticos quantitativos • simulação
• otimização matemática
• métodos econométricos
• ...
Investigação Operacional
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
I.O.
Ciência da localização (location science)
• Ramo da investigação operacional
• Weber (1909): onde localizar uma indústria tendo em conta custos de matéria prima, trabalho e transporte e economias de escala
C.L.
Matemática
Aplicada
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Ciência da localização (location science)
• Lida com os problemas de localização
– Encontrar locais que melhor verificam determinadas condições ou critérios
– Subjacente: medida de qualidade das soluções deseja-se a melhor solução
– Problemas com várias (muitas) soluções
Qual o melhor rearranjo do
mapa judiciário português?
Que rotas de recolha de lixo
são as que mais poupam?
Como distribuir torres de
vigia de incêndios de
modo a observar a maior
área possível de floresta?
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Problema de localização
Onde? O quê? Quanto?
Porquê?
Espaço de
localização Oferta Procura Função-objetivo
Restrições Funções de
parametrização Restrições
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Problemas de localização
• Espaço de localização
– contínuo
– discreto
• Elementos de oferta
– número
– tipo
– capacidade
– custo
– geometria
• Elementos de procura
– distribuição
– nível de procura
– associação à oferta
• Funções de parametrização
– de interação
– de validação
• Função-objetivo
– objetivo
– restrições
• espaciais
• de validação
• de configuração
• de domínio
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
(...) distribuir torres de vigia de incêndios de modo a observar a
maior área possível de floresta
Problemas de localização (PL)
• Os PL interessantes apresentam em
geral um número muito grande de
soluções para analisar
• Para o problema de máxima cobertura
com 50 locais candidatos e 5 torres há
2118760 combinações
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Ciência da localização (location science)
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Modelos matemáticos
Representam
formalmente o problema
Permitem enquadrar o
problema segundo as
suas características
Ciência da localização (location science)
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Técnicas de otimização
Codificam e avaliam
soluções
Permitem determinar
a(s) melhor(es)
solução(ões)
Ciência da localização (location science)
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Modelos: formulação de um problema
(...) distribuir P torres de vigia de incêndios de modo a observar
a maior área possível de floresta
Ii,Z
Jj ,X
PX
IiXaZ
Zh
i
j
Jj
j
Jj
jiji
Ii
ii
10
10
suj.a
max maximizar a “cobertura”
local i só é coberto se houver
alguma torre que o observe
localizar P torres
condições de integralidade
das variáveis de decisão torres
cobertura
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Modelos: enquadramento de problemas
• Muitos modelos:
– Cobertura de conjuntos
– Máxima cobertura
– Mediana
– Centragem
– ...
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Não se localizam só pontos
• Localização de linhas
– Rotas, percursos, redes
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Rotas e percursos
• Caminho mais curto (LCP)
• Passagem por locais pré-determinados
(encontrar a melhor ordem):
– Caixeiro-viajante (TSP)
– Rotas de veículos (VRP)
– Carteiro chinês (CPP)
– …
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Localização de linhas - LCP
Fonte
:esri.c
om
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Localização de linhas - LCP
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Localização de linhas - TSP
Localização de linhas - VRP
• Passagem por locais pré-determinados
(encontrar a melhor ordem):
– Caixeiro-viajante
– VRP
– Carteiro chinês
– …
12/7/2014 Instituto Superior Técnico Fonte:esri.com
Localização de linhas - CPP
Fo
nte
:we
b.m
it.e
du
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Localização de redes
• Ou equipamentos lineares
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Localização de redes
• Ou equipamentos lineares
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Localização de áreas
• site search
• multi-site land-use allocation
• redistricting
• facility layout
• …
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Site search
• Dada uma distribuição da
aptidão e/ou custo, obter a
melhor solução, que é parte
do espaço
– máx. aptidão
– mín. custo
– critérios de forma
– …
J.V
.Sousa
(IS
T)
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Multi-site land-use allocation
• Classificar o
espaço com base
em condições de
vizinhança,
distância, fronteira,
dimensão, (…)
aplicadas às
classes
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Multi-site land-use allocation
• Classificar o
espaço com base
em condições de
vizinhança,
distância, fronteira,
dimensão, (…)
aplicadas às
classes
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Redistricting
• Redistribuição/reagrupamento de
unidades territoriais
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
C. G
igante
(IS
T)
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Facility layout
• Classificação do espaço em função de
restrições de adjacência ou proximidade
entre classes
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Resolução
• A escolha do método de resolução depende:
– Da estrutura ou tipo do problema
• Há problemas para os quais se conhecem algoritmos
eficientes em termos de espaço de memória e tempo de
execução
• Há outros para os quais não se conhecem
– Da dimensão do problema
• Número de elementos de oferta/procura no problema
– Da capacidade de transformar o problema em
outro problema já conhecido
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Exatos
Encontram o valor ótimo
Tiram partido da
estrutura do problema
Servem para problemas
“tratáveis”
Heurísticos
Não garantem a
descoberta do ótimo
Permitem determinar
a(s) melhor(es)
solução(ões) face aos
recursos disponíveis
Métodos de resolução
Meta-heurísticas são métodos
heurísticos que podem lidar com
qualquer problema de otimização
por não estarem dependentes de
um problema específico. II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Análise de algoritmos
• Espaço
– Espaço de armazenamento, número de variáveis
• Tempo
– Número de operações necessárias
A análise de um algoritmo visa determinar o tempo
expectável para a sua execução e o espaço de
armazenamento de variáveis necessário
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Ordens de
complexidade
1 0,0 1,0 1,0 2,0
25 3,1 5,0 625 3,3 X107
50 3,9 7,1 2500 1,1 X1015
75 4,3 8,6 5625 3,8 X1022
100 4,6 10,0 10000 1,3 X1030
O(1) Constante “Ultrarrápido”
O(logn) Logarítmico “Rápido”
O(n) Linear “Moderado”
O(n logn) Sublinear “Moderado”
O(nk) Polinomial “Lento”
O(kn) Exponencial “Intratável”
Recursos de cálculo
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Tempo de cálculo
Comple-
xidade
n=10 n=20 n=40
O(n) 0,00001 s 0,00002 s 0,00004 s
O(n2) 0,0001 s 0,0004 s 0,0016 s
O(n3) 0,0001 s 0,008 s 0,0064 s
O(2n) 0,0001 s 1,05 s 12,7 dias
O(en) 0,022 s 8,08 minutos 74,6 séculos
1 milhão de operações por segundo
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Com recurso a “supermáquinas”
comple-
xidade
veloc.
atual
10x mais
rápido
100x mais
rápido
1000x
+ rápido
O(n) N1 10xN1 100xN1 1000xN1
O(n2) N2 3,16xN2 10xN2 31,6xN2
O(n3) N3 2,15N3 4,64xN3 10xN3
O(2n) N4 N4+3,32 N4+6,64 N4+9,97
O(en) N5 N5+2,3 N5+4,61 N5+6,91
quanto poderá crescer o input em função do aumento da velocidade
de processamento, mantendo o tempo de execução
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Heurísticas
• Construtivas
• De simplificação
• De combinação
• De melhoramento
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Heurísticas
• Construtivas
INÍCIO
Determinar o candidato que cobre a maior quantidade de procura
ainda não satisfeita
Ativar equipamentonesse local e remover a procura
coberta por este
Não
FIM
Sim
Já foram localizados P
elementos, ou já toda a procura é satisfeita?
INÍCIO
Selecionar aleatoriamente um equipamento ainda não escolhido
Não
FIM
Sim
Já foram localizados P
elementos, ou já toda a procura é satisfeita?
Ativar equipamentonesse local e remover a procura
coberta por este
Sim
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Meta-heurísticas
• Codificam e exploram o espaço de
soluções:
– Algoritmos genéticos
– Colónia de formigas
– Arrefecimento simulado
– ...
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Algoritmos genéticos
• Fraser & Burnell (1970); Crosby (1973); Holland (1975)
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Algoritmos genéticos
Colónia de formigas
• Dorigo, 1992
• Inspirada pelo comportamento das formigas e pelo
rasto de feromonas: mais feromonas = melhor
solução
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Arrefecimento simulado
• Kirkpatrick, Gelatt, Vecchi (1983); Černý (1985)
• Inspirada por processo metalúrgico
Fonte
:wik
ipedia
.org
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
“Papel” dos SIG
• Input e output
• Localização em espaços não homogéneos
• Parametrização: há muitas funções além da distância
• Heurísticas “espaciais” (redução de candidatos, produção de soluções: p.ex., localização de observadores)
• Análise de sensibilidade (relacionado com o MAUP)
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Exemplos de heurísticas espaciais
• Localizar antenas no concelho de Sintra de modo a
maximizar a população “coberta”
• Duas estratégias: reduzir candidatos / generalizar
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
(90 m)
0
500
1000
1500
2000
2500
3000
3500
4000
Pit Valley Pass Ridge Peak Planar
nu
mb
er
of
vis
ible
cell
s
Exemplos de heurísticas espaciais
Pits 0,12%
Channels 22,84%
Passes 0,68%
Ridges 26,76%
Peaks 0,21%
Planar 49,39%
• Classificação morfológica
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Exemplos de heurísticas espaciais
• Calcular o índice de visibilidade e
escolher os melhores 5%
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Exemplos de heurísticas espaciais
• Generalização
90 m
150 m
300 m
Conclusão
• É enorme a variedade de problemas de localização que se podem equacionar
• Há um conjunto de modelos e técnicas que se adaptam a estes problemas
• Os SIG permitem quantificar e qualificar relações espaciais que interessam em vários PL, bem como induzir várias heurísticas espaciais
• A investigação nesta área é um campo que ainda agora começou a ser explorado!
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
DISSERTAÇÕES DE MESTRADO
• DIOGO M. MORGADO: Modelo de otimização para a gestão de resíduos hospitalares perigosos em Portugal com integração de SIG. Mestr. Engª e Gestão Industrial, IST (2015)
• FILIPE F. GOMES: Otimização de circuitos de inspeção aos pavimentos de uma rede rodoviária nacional. Mestr. Engª e Gestão Industrial, IST (2015)
• ISABEL BATISTA: “Módulo para Resolução de Problemas de Localização de Pontos em Ambiente SIG”, Mestr. Engª do Território, IST (2010)
• ALEXANDRE SANTOS: “Definição do Traçado de Infra-estruturas Lineares Usando SIG: O Caso da Infra-estrutura Ferroviária de Alta Velocidade”, Mestr. SIG, IST (2009)
• JOSÉ V. SOUSA: “Localização por Site Search”, Mestr. SIG, IST (2008)
ARTIGOS
• AMORIM, A.; GONÇALVES, A.B.; NUNES, L.M.; SOUSA, A.J. (2012): “Optimizing the location of weather monitoring stations using estimation uncertainty”, International Journal of Climatology, V. 32, n.º 6, pp. 941-952.
• GONÇALVES, A.B. (2010): "An extension of GIS-based least-cost path modelling to the location of wide paths", International Journal of Geographical Information Science, V. 24, n.º7, pp. 983-996.
• BRAVO, J.M.; COLLISCHONN, W.; PILAR, J. V.; GONÇALVES, A. (2008): “Avaliação do Desempenho de um Algoritmo Baseado no Comportamento de Formigas em Problemas de Caminho de Mínimo Custo em Ambientes Raster”, Revista Brasileira de Cartografia, v. 60, pp. 31-41.
• LEITÃO, J.P.; MATOS, J.S.; GONÇALVES, A.; MATOS, J.L. (2005): "Contribution of Geographic Information Systems and Location Models to Planning of Wastewater Systems", Water Science and Technology, V. 52, nº 3, pp. 1-8.
CONFERÊNCIAS
• RODRIGUES, M.S.; GOMES, M.C.; GONÇALVES, A.B.; SHRUBSALL, S. (2015): “Hazardous materials transportation using bi-level linear programming: a case-study of liquid fuel distribution”, International Conference on Operations Research and Enterprise Systems.
• AMORIM, A.; GONÇALVES, A.B.; NUNES, L.M.; SOUSA, A.J. (2011): “Optimização da localização de estações meteorológicas”. 15.º Congresso da Associação Portuguesa de Investigação Operacional (APDIO).
• SOUSA, J. ; GONÇALVES, A. (2009): “Localização por Site Search”, VI Conferência Nacional de Cartografia e Geodesia.
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa
Alexandre B. Gonçalves
Instituto Superior Técnico, Univ. de Lisboa
Os Sistemas de Informação
Geográfica e a Otimização
Espacial no Apoio à Decisão: Problemas, Modelos e Soluções
II Colóquio de Sistemas de Informação Geográfica – Sociedade de Geografia de Lisboa