Planejamento de rotas para leitura de medidores: uma aplicação do problema do carteiro chinês

Abstract

Alocar de forma eficiente mão de obra e recursos, garantindo a cobertura de determinada área geográfica e minimizando os custos operacionais, é um desfio que contempla empresas ligadas ao fornecimento de serviços essenciais, como água, gás e energia elétrica. Visando considerar a problemática de gerar rotas para realizar a leitura de medidores de determinada região, foi proposto este estudo. O objetivo foi simular um serviço de leitura, com base em dados geográficos reais, e obter um trajeto fechado de atendimento que garanta a cobertura de todos os medidores, e onde a distância total percorrida seja mínima. Instâncias de teste, baseadas em dados reais, foram geradas. O problema foi modelado como um Problema do Carteiro Chinês não direcionado e resolvido por meio de programação linear, usando um solver comercial. A partir da solução gerada pelo modelo, foi aplicado um algoritmo para obtenção do sequenciamento de atendimento. Os resultados mostraram que, para as instâncias criadas, que contemplaram até 200 vértices e 634 arcos, a metodologia aplicada foi eficiente, gerando a solução ótima de forma rápida.

Keywords

• otimização combinatória
• programação linear
• roteamento em arcos