Abstract:
Este trabalho tem por objetivo propor uma metodologia heurística para o Problema de
Cobertura de Arcos aplicado aos serviços de saneamento, em específico na leitura de
hidrômetros. Dentro deste contexto desenvolveu-se um aplicativo que permite o planejamento
de rotas de maneira que os custos em distância percorrida sejam reduzidos e mantenham-se
aproximadamente os mesmos em todos os percursos. A metodologia foi dividida em etapas. Na
primeira etapa, para compreender melhor o problema, fez-se uma pesquisa de campo
organizando os dados disponibilizados por uma empresa de saneamento. A segunda etapa foi
caracterizada pela determinação de pontos em cada metade de trechos de quadra e nas
interseções de ruas, os quais foram cadastrados, em um mapa georeferenciado. Este mapa
contemplou a região escolhida para o estudo e os pontos cadastrados serviram para determinar
e consequentemente, designar as medianas relacionadas, o que constitui a terceira etapa. Para
isso utilizou-se respectivamente o algoritmo de Teitz Bart Modificado por CADP e o algoritmo
de designação de Gillet e Johnson adaptado. Ao final desta etapa formaram-se subsetores dentro
de um setor específico. Na última etapa encontrou-se as rotas de cada subsetor através do
algoritmo genético. O aplicativo desenvolvido permitiu flexibilidade de ações, dando
autonomia para o usuário na escolha das opções de cálculo. Sua interface gráfica possibilitou a
elaboração de mapas e a visualização das rotas em cada subsetor. Além disso o aplicativo
minimizou os percursos e distribuiu os subsetores com distâncias aproximadas. A eficiência das
heurísticas que embasaram o aplicativo desenvolvido, foi comprovada através dos testes
realizados, os quais obtiveram resultados de boa qualidade.
This work aims to propose an heuristic methodology for the Arc Coverage Problem applied to
sanitation services, in particular in the meter reading. Within this context it was developed an
application that allows route planning so that the costs in distance are reduced and stay
approximately the same in all routes. The methodology was divided into stages. In the first
stage, to better understand the problem, a field research was done by organizing the data
provided by a sanitation company. The second stage was characterized by the determination of
points in each half block stretch and at the intersections of streets, which were registered on a
georeferenced map. This map included the region chosen for the study and the registered points
were used to determine and, therefore designate the related median, which is the third stage.
Thereunto, it was used respectively the algorithm Teitz Bart Modified by CADP and the
Algorithm of designation of Gillet and Johnson adapted. At the end of this stage, subsectors
were formed within a specific sector. In the last stage, routes of each subsector were found
through the Genetic Algorithm. The developed application allowed actions flexibility, giving
autonomy to the user in the choice of calculation options. Its graphical interface allowed the
maps elaboration and visualization of routes in each subsector. Besides that, the application
minimized the route and distributed the subsectors with approximate distances. The efficiency
of heuristics that based the developed application was proven through tests, which obtained
good quality results.
