UMA NOVA HEURÍSTICA PARA O PROBLEMA DE COBERTURA DE ARCOS APLICADO AOS SERVIÇOS DE SANEAMENTO

Resumo

Esse trabalho tem por objetivo, testar um novo algoritmo que utiliza resultados matemáticos da Teoria Espectral sobre o Problema de Cobertura de Arcos aplicado aos serviços de saneamento, mais especificamente na leitura de hidrômetros. A metodologia utilizada no desenvolvimento do trabalho foi dividida em três etapas. Na primeira etapa, foi realizada uma pesquisa de campo organizando os dados disponibilizados por uma empresa de saneamento. A segunda etapa foi caracterizada pela determinação das medianas e dos subsetores, a partir da determinação dos pontos em cada metade de trechos de quadra e nas interseções de ruas, cadastrados em um mapa georeferenciado. Finalmente, na terceira etapa, foram determinadas as rotas para cada subsetor. Foi desenvolvida uma ferramenta computacional que integra um algoritmo elaborado a partir de uma nova medida de centralidade, denominada de autovetor distância-peso (C_ADP) na determinação das medianas, do algoritmo de designação Gillet e Johnson e do algoritmo genético na determinação das rotas de cada subsetor. O aplicativo se mostrou flexível e permitiu a elaboração de mapas e a visualização das rotas em cada subsetor. O estudo da teoria espectral combinada com estudos em otimização combinatória, torna-se uma ferramenta a mais no auxílio da tomada de decisão.