Procedimentos heurísticos na definição de rotas de leitura para os funcionários de uma companhia de energia elétrica : uma aplicação a um município no estado do Paraná

Abstract

Resumo: O presente estudo propõe a utilização de uma metodologia para solucionar o problema de roteamento dos leituristas de uma companhia de energia elétrica. Esta metodologia é form ada pela junção do Problema de Localização de Facilidades (PLF) com o Problema do Carteiro Chinês (PCC). O primeiro busca definir clusters para cada leiturista e o segundo, procura encontrar a melhor rota dentro de cada um dos clusters. Como o PLF é classificado como NP-hard, a utilização de heurísticas reduz o seu tempo computacional e apresenta resultados que podem estar próximos da otimalidade. Portanto para selecionar um procedimento heurístico adequado para a resolução do problema, é preciso medir a sua eficiência e eficácia por meio da comparação com diferentes procedimentos. Neste trabalho, optou-se pela utilização da meta-heurística Algoritm o Genético (AG), a heurística de Teitz & Bart, um método híbrido, form ado pela combinação do AG com o Algoritm o de Teitz & Bart, além do método exato do PLF. Esta metodologia, composta pelas técnicas mencionadas, foi aplicada a um município do Estado do Paraná, mais especificamente, São José dos Pinhas, objetivando a redução e um equilíbrio das rotas a serem percorridas pelos leituristas de uma companhia de energia elétrica. Como resultado, foi possível verificar que a utilização do método híbrido apresentou os melhores resultados, quando comparados com o método exato, ou seja, os mais próximos da otimalidade, sendo possível reduzir a rota dos leituristas na região analisada, assim como obter um melhor balanceamento de seu trabalho. Palavras-chave: Problemas de Roteamento. Problemas de Localização de Facilidades. Procedimentos Heurísticos. Leituristas.

Abstract: The present study proposes a methodology to solve the routing problem for the readers of an electric power company. This m ethodology is the result on merging the Facilities Location Problem (FLP) along with the Chinese Postman Problem (CPP). The form er will provide the division of the area into clusters and the latter will provide us with an improved route inside each cluster. Since FLP is classified as NP-hard, the use of heuristics reduces computational time and is able to achieve results close to optimality. In order to select a suitable heuristic procedure to solve this problem, it is necessary to measure its effectiveness and efficiency by comparing different procedures. W e chose the m eta-heuristic Genetic Algorithm (GA), the Teitz & Bart Algorithm, a hybrid method, formed by the combination of GA and the Teitz & Bart Algorithm, and the FLP exact method. The methodologies were applied in a real case, in the city of São José dos Pinhais, located on the state of Paraná, aiming the reduction and a balance of the routes. As a result, it was possible to verify that the use of the hybrid method presented a result closer to the optimality, and it was possible to reduce the route in the analyzed region, as well as to balance the workload. Key-words: Routing problem. Facility location problem. Heuristic procedures. Readers.