Modelagem do Roteamento de Leituristas : uma abordagem cluster first - route second para o problema do carteiro chinês capacitado

Abstract

O Problema de Roteamento de Leituristas (PRL) é um problema de otimização que contempla setores ligados ao fornecimento de gás natural, energia elétrica ou água encanada, onde empresas fornecedoras necessitam periodicamente mobilizar trabalhadores para vistoria e emissão de faturas dos pontos de consumo. O PRL trata as ruas da malha urbana estudada como arestas, às arestas estão relacionadas distâncias a serem percorridas, a essas arestas também estão associadas demandas de tempo para atravessamento e vistoria dos pontos de consumo. O PRL, por sua vez, consiste em encontrar rotas que minimizem a distância percorrida por leituristas dado uma carga de trabalho previamente atribuída, isso significa que as arestas dotadas de demandas de tempo para serem atravessadas e vistoriadas devem estar designadas aos leituristas buscando respeitar a carga de trabalho estabelecida. Por meio de uma revisão sistemática de literatura identificaram-se lacunas presentes na literatura, como o baixo número de publicações concernentes a técnicas de resolução do PRL. O presente trabalho propõe uma abordagem cluster first – route second para a resolução do PRL. A abordagem proposta é aplicada em duas fases, na primeira fase agrupa-se as ruas da localidade estudada em clusters por meio da aplicação do Problema das p-Medianas, a atribuição da demanda de cada rua ou segmento de rua aos clusters é limitada pela capacidade do leiturista, logo cada cluster corresponde a uma rota. Em uma segunda fase, a conectividade de cada cluster é verificada, caso o subgrafo de um cluster não seja conexo, as arestas que tornam esse subgrafo conexo são atribuídas e aplica-se o Problema do Carteiro Chinês. A abordagem proposta foi aplicada em duas localidades: um bairro da cidade de Recife e na cidade de Flores, ambas no Estado de Pernambuco. Para cada localidade foram criados cenários e situações, que serviram para realizar a análise de sensibilidade do modelo e permitir inferências. Verificou-se que, para a resolução do PRL em pequenas instâncias o modelo possui tempo de execução razoável, podendo ser aplicado a resolução do PRL em cidades e localidades de pequeno porte.