Técnicas da pesquisa operacional aplicadas a um problema de cobertura de arcos

Abstract

Resumo: Neste trabalho é proposta uma solução para o trabalho de leitura dos medidores das contas de água dos clientes, efetuado por uma empresa de saneamento básico do município de Pato Branco, utilizando algumas técnicas da Pesquisa Operacional. A metodologia aqui apresentada divide o trabalho em duas fases distintas: a primeira onde são formados os grupos de atendimento para cada leiturista: e a segunda fase, onde propõe-se a melhor rota a ser seguida, de modo a minimizar a distância percorrida por cada trabalhador. Na primeira fase, compara-se a metanheurística do algoritmo genético com a heurística clássica de Teitz e Bart para a definição de 12-medianas. que em seguida servem como sementes para a formação dos 1 2 grupos de atendimento dos leituristas, obtidos através do algoritmo de designação <te Gillett e Johnson. O roteamento de cada um destes grupos caracteriza um problema de cobertura de arcos, que é resolvido na segunda fase, utilizando a formulação matemática do Problema Carteiro Chinês e o Algoritmo do Carteiro Clrâiês. O objetivo principal do trabalho é obter, de forma rápida e eficiente, o caminho otimizado de percorrida do leiturista para que se gaste menos tempo com o seu deslocamento, oferecendo um atendimento com maior qualidade aos usuários desses serviços

Abstract: This study proposes a solution for customers* water meter bill reading task, executed by a basic sanitation company o f Pato Branco, through the utilization o f some Operational Research techniques. The methodology presented here divides the work in iwo distinct phases: the first, where the Service groups for each meter reader are formed and: the second. where the best route to be followed is proposed, in order to minimize the Service distance for each server. In the first phase, the meta-heuristic o f the genetic algerithm is compared to the Teiz and B arf s classical heuristics. This defines twelve medsans that will serve as seeds to form the twelve groups o f meter reader Service, obtained through the Gillett and Johnson’s designation algorithms. The routing o f each group characterizes an are coveimg problcm. which is solved in the second phase by using the Chinese Postman Problem mathematieal form and the Chinese Postman Algorithms. The rnain purpose o f the work is to obtain, quicklv and efficiently. the optimized Service distance for the meter reader so that less time is spent on his covering eycle and better quality service is offered to the users o f this system