Upload
enzo-lobato
View
217
Download
0
Embed Size (px)
Citation preview
Geologia, Geofísica &Informática no Setor dePetróleo & Gás na UFRNANP-MME-MCT
anpAgênciaNacional doPetróleoURNF
UMA ABORDAGEM PARA O PROJETO DE REDES URBANAS DE
DISTRIBUIÇÃO DE GÁS POR OTIMIZAÇÃO COMBINATÓRIA E
SISTEMAS DE INFORMAÇÃO GEOGRÁFICAS
Cezar Miranda Paula de SouzaBolsista Mestrado – DIMApOrientação:Marco César GoldbargElizabeth Gouvêa Goldbarg
Geologia, Geofísica &Informática no Setor dePetróleo & Gás na UFRNANP-MME-MCT
anpAgênciaNacional doPetróleoURNF
Objetivos
• Apresentar uma abordagem para o projeto de redes urbanas de serviços com topologia em árvore (em especial, redes urbanas de gás)– que seja de custo mínimo– que gere o menor impacto sócio-
ecológico possível. • Uso de SIG e técnicas de otimização
combinatória
Geologia, Geofísica &Informática no Setor dePetróleo & Gás na UFRNANP-MME-MCT
anpAgênciaNacional doPetróleoURNF
Motivação• Cenário nacional propício para o crescimento de
redes de gás natural– Grandes reservas de gás natural– Demanda crescente
• Indústrias siderúrgica, química, petroquímica e de fertilizantes – fornece calor, gera eletricidade e força motriz
• transportes urbanos – pode substituir o óleo diesel, a gasolina e o álcool
– “Combustível limpo”, sem restrições ambientais• Projeto e implantação de redes urbanas de serviço
– tarefas árduas– grande importância econômico-social– envolve custos elevados
Geologia, Geofísica &Informática no Setor dePetróleo & Gás na UFRNANP-MME-MCT
anpAgênciaNacional doPetróleoURNF
Desafios• Necessidades do projeto variam
– Características do terreno e do ambiente– Fatores urbanos e ecológicos
• intervenção física – Diversos tipos e modelos de dutos e tubos– Valores limites máximos e mínimos
• pressão • Vazão do gás • variam de segmento a segmento
– Atender a todos os pontos de demanda minimizando os custos
• distâncias, custos de instalação
Geologia, Geofísica &Informática no Setor dePetróleo & Gás na UFRNANP-MME-MCT
anpAgênciaNacional doPetróleoURNF
Desafios• Projetos envolvem uma série de variáveis de decisão
– Problema complexo (NP Árduo)– Difícil solução computacional
• Soluções Enumerativas (Inviabilidade Temporal)• Otimização combinatória / Soluções Aproximativas (qualidade de
solução x tempo de execução)– Neste contexto, os SIGs surgem como ferramentas que, aliadas
às técnicas de Otimização Combinatória, possibilitam o apoio à tomada de decisão no processo de projeto das redes a serem implantadas e/ou expandidas.
• Integração de plataforma SIG com módulos de otimização (traçado e diâmetro) e Bancos de Dados de alto nível
• Mapeamento no problema de árvores de Steiner– formulação com bottleneck Min-Max-Min-Sum. – Formulação Bottleneck para árvores de Steiner ausente na
literatura
Geologia, Geofísica &Informática no Setor dePetróleo & Gás na UFRNANP-MME-MCT
anpAgênciaNacional doPetróleoURNF
Aplicabilidade
• Metodologia pode ser aplicada ao projeto de redes urbanas de serviços em geral (em topologia árvore e em outras topologias)– Rede Elétrica– Saneamento– Telecomunicações– Etc.
Geologia, Geofísica &Informática no Setor dePetróleo & Gás na UFRNANP-MME-MCT
anpAgênciaNacional doPetróleoURNF
Resultados• Desenvolvimento de algoritmos aproximativos
– SPH (Shortest Path Heuristic)– GRASP Híbrido com perturbações– Algoritmo Genético– Comparações para obtenção de estatísticas de
desempenho• Desenvolvimento de SIG para integração em
Software• SIG
– pré-processamento– Grafo representativo do problema – exibição da solução
Geologia, Geofísica &Informática no Setor dePetróleo & Gás na UFRNANP-MME-MCT
anpAgênciaNacional doPetróleoURNF
Resultados – Algoritmos
• Testes de desempenho para os algoritmos– 20 instâncias da Steinlib – Execução:
• Pentium 4 3GHz 512 MB RAM• Instâncias não possuem referência geográfica
– resultados não permitem exibição– estatísticas de desempenho / validação dos algoritmos
• Testes com instâncias reais – PotiGás: Natal / RN
• base geográfica da cidade• resultados podem ser exibidos
Geologia, Geofísica &Informática no Setor dePetróleo & Gás na UFRNANP-MME-MCT
anpAgênciaNacional doPetróleoURNF
Resultados – Algoritmos
e x e c u ç ã oInstância 1 2 3 4 5 6 7 8 9 10 Média Vertices Arestas Terminais Ótimo Desvioc1 85 85 85 85 85 87 87 86 87 85 85,7 500 625 5 85,00 0,82%c2 144 144 144 144 144 144 144 144 144 144 144 500 625 10 144,00 0,00%c3 756 757 756 756 756 757 756 756 756 756 756,2 500 625 83 754,00 0,29%c4 1093 1095 1093 1097 1097 1094 1097 1094 1094 1097 1095,1 500 625 125 1079,00 1,49%c5 1582 1582 1583 1581 1582 1582 1582 1581 1582 1581 1581,8 500 625 250 1579,00 0,18%c6 55 55 55 55 55 55 55 55 55 55 55 500 1000 5 55,00 0,00%c7 107 109 109 106 109 103 108 108 107 109 107,5 500 1000 10 102,00 5,39%c8 513 513 512 512 514 512 513 512 513 513 512,7 500 1000 83 509,00 0,73%c9 710 710 712 713 712 712 712 713 713 712 711,9 500 1000 125 707,00 0,69%c10 1093 1093 1093 1093 1093 1093 1093 1093 1093 1093 1093 500 1000 250 1093,00 0,00%d1 106 106 106 106 106 106 106 106 106 106 106 1000 1250 5 106,00 0,00%d2 224 224 224 224 224 224 224 224 224 224 224 1000 1250 10 220,00 1,82%d3 1582 1577 1580 1582 1583 1579 1583 1579 1582 1580 1580,7 1000 1250 167 1565,00 1,00%d4 1947 1945 1945 1949 1944 1950 1949 1949 1948 1946 1947,2 1000 1250 250 1935,00 0,63%d5 3255 3255 3255 3254 3253 3254 3253 3255 3256 3253 3254,3 1000 1250 500 3250,00 0,13%d6 71 71 70 70 70 70 70 71 70 70 70,3 1000 2000 5 67,00 4,93%d7 103 103 103 103 103 103 103 103 103 103 103 1000 2000 10 103,00 0,00%d8 1098 1102 1101 1099 1102 1098 1100 1095 1102 1098 1099,5 1000 2000 167 1072,00 2,57%d9 1460 1462 1461 1459 1461 1459 1461 1459 1461 1459 1460,2 1000 2000 250 1448,00 0,84%d10 2112 2111 2112 2113 2111 2111 2112 2113 2112 2113 2112 1000 2000 500 2110,00 0,09%
e x e c u ç ã oInstância 1 2 3 4 5 6 7 8 9 10 Média Vertices Arestas Terminais Ótimo Desvioc1 85 85 85 85 85 85 85 85 85 85 85 500 625 5 85,00 0,00%c2 184 179 183 183 179 179 179 178 183 184 181,1 500 625 10 144,00 25,76%c3 850 847 852 848 849 855 860 844 848 854 850,7 500 625 83 754,00 12,82%c4 1159 1159 1159 1159 1159 1159 1159 1159 1159 1159 1159 500 625 125 1079,00 7,41%c5 1639 1637 1638 1643 1642 1640 1637 1639 1638 1643 1639,6 500 625 250 1579,00 3,84%c6 69 69 69 64 69 64 69 69 69 69 68 500 1000 5 55,00 23,64%c7 117 117 117 117 117 112 117 117 117 117 116,5 500 1000 10 102,00 14,22%c8 625 628 620 625 625 625 625 625 625 624 624,7 500 1000 83 509,00 22,73%c9 802 806 809 811 806 799 806 803 820 814 807,6 500 1000 125 707,00 14,23%c10 1150 1155 1147 1152 1150 1148 1152 1151 1151 1148 1150,4 500 1000 250 1093,00 5,25%d1 108 108 108 108 108 108 108 108 108 108 108 1000 1250 5 106,00 1,89%d2 251 251 251 251 251 251 251 251 251 251 251 1000 1250 10 220,00 14,09%d3 1791 1770 1768 1782 1757 1784 1784 1779 1801 1767 1778,3 1000 1250 167 1565,00 13,63%d4 2126 2136 2140 2142 2129 2134 2131 2126 2135 2138 2133,7 1000 1250 250 1935,00 10,27%d5 3364 3363 3368 3366 3361 3363 3362 3368 3361 3367 3364,3 1000 1250 500 3250,00 3,52%d6 79 79 79 79 79 79 79 79 79 79 79 1000 2000 5 67,00 17,91%d7 156 156 156 156 156 156 156 156 156 156 156 1000 2000 10 103,00 51,46%d8 1256 1266 1265 1261 1267 1263 1262 1264 1257 1257 1261,8 1000 2000 167 1072,00 17,71%d9 1652 1640 1649 1644 1643 1643 1636 1645 1648 1647 1644,7 1000 2000 250 1448,00 13,58%d10 2236 2233 2243 2246 2239 2246 2232 2230 2231 2233 2236,9 1000 2000 500 2110,00 6,01%
Geologia, Geofísica &Informática no Setor dePetróleo & Gás na UFRNANP-MME-MCT
anpAgênciaNacional doPetróleoURNF
Resultados - SIG• Tratamento de bases geográficas (ArcGIS /
Network Analyst)– Geocodificação de endereços– Análises de rede
• Caminho mais curto• Árvore Geradora Mínima• Caixeiro Viajante
• SIG embarcado (MapObjects / NetEngine )– Simbolização– Visualização (Zoom / Pan)– Rotulação– Análise / Edição de bases– Visualização / Seleção de camadas– Análises de rede
Geologia, Geofísica &Informática no Setor dePetróleo & Gás na UFRNANP-MME-MCT
anpAgênciaNacional doPetróleoURNF
Resultados - SIG
Geologia, Geofísica &Informática no Setor dePetróleo & Gás na UFRNANP-MME-MCT
anpAgênciaNacional doPetróleoURNF
Resultados - SIG
Tela Principal
Geologia, Geofísica &Informática no Setor dePetróleo & Gás na UFRNANP-MME-MCT
anpAgênciaNacional doPetróleoURNF
Resultados - SIG
Gerenciamento de camadas
Geologia, Geofísica &Informática no Setor dePetróleo & Gás na UFRNANP-MME-MCT
anpAgênciaNacional doPetróleoURNF
Resultados - SIG
Simbolização X Rotulação
Geologia, Geofísica &Informática no Setor dePetróleo & Gás na UFRNANP-MME-MCT
anpAgênciaNacional doPetróleoURNF
Resultados - SIG
Edição
Geologia, Geofísica &Informática no Setor dePetróleo & Gás na UFRNANP-MME-MCT
anpAgênciaNacional doPetróleoURNF
Resultados - SIG
Solução da rede
Geologia, Geofísica &Informática no Setor dePetróleo & Gás na UFRNANP-MME-MCT
anpAgênciaNacional doPetróleoURNF
Benefícios Sociais e Econômicos
• Soluções minimizam os custos de implantação / expansão das redes
• redução do impacto ambiental / social produzido pela intervenção
• O projeto automatizado da rede permite a realização de simulações, podendo prever dificuldades do processo, e prover soluções para as mesmas
Geologia, Geofísica &Informática no Setor dePetróleo & Gás na UFRNANP-MME-MCT
anpAgênciaNacional doPetróleoURNF Dúvidas e Sugestões