Uma metodologia heurística para minimizar o roteiro nos serviços de leitura de hidrômetros

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.