Algrorithms for the routing meter readers problem

Resumo: Esse trabalho se dedicou ao estudo dos algoritmos para roteamento de leituristas, incluindo propostas de alteração que resultem na melhoria da qualidade dos resultados. A motivação é proveniente da alta demanda por soluções computacionais para esse problema, ainda pouco estudado devido às peculiaridades que lhe são inerentes. Encontram-se na literatura duas heurísticas, de estratégias distintas e antagônicas para esse problema. Uma das heurísticas procura construir a rota ignorando a restrição de capacidade, para posterior particionamento dessa rota em subrotas, cada qual destinada a um leiturista (?route first, cluster second?). A outra heurística, em uma abordagem inversa, primeiramente subdivide a região de trabalho dos leituristas, para posterior roteamento dessas partições (?cluster first, route second?). Essas duas heurísticas foram testadas exaustivamente, tornando possível localizar aspectos sujeitos à melhoria, dando origem a duas novas heurísticas. Foi gerada uma base de testes contendo 144 instâncias que simulam as condições reais de trabalho dos leituristas, classificadas de acordo com o tamanho e dificuldade. A partir das soluções provenientes dos quatro algoritmos foi possível analisá-los comparativamente, avaliando o melhor em um âmbito geral (envolvendo todos os algoritmos) e específico (algoritmos de mesmo tipo, ?route first cluster second? ou ?cluster first route second?), segundo critérios de qualidade pré-definidos: número de rotas, tempo de percurso, violação da carga horária e tempo computacional. Os resultados revelam que os novos algoritmos foram melhores tanto na comparação específica quanto na comparação geralAbstract: This work?s main study object consists on algorithms for routing meter readers, from which proposals towards solution?s improvement are made. The demand for computational results concerning this problem, added to literature little attention due to its inherited peculiarities, has been the outmost motivation. Two preexisting heuristics from literature, with distinct and antagonic strategies, are pointed out. One of these heuristics atempt to create a single route, dismissing the capacity restriction, and then partitionates this route into subroutes, each of them destinated to one meter reader (route first, cluster second). The other heuristic, in an inverse approach, first splits the meter reader?s working area, and only then routes each of these partitions (cluster first, route second). The two heuristics were tested to exaustion, allowing enumeration of weak aspects subject to improvement. Therefore, two new heuristics were developed, based upon the originals, however adapted in order to outperform solution?s quality. A testing base containing 144 instances was generated, simulating meter readers realistic labor?s conditions, classified by size and difficulty. Through solutions provided by the four algorithms, comparison analyses have taken place, evaluating in a general (involving all algorithms) and specific manner (same kind algorithms, i.e., route first, cluster second or cluster first, route second), considering four predefined quality criteria: number of routes, deadheading time, violation of shiftwork time and computational time. Results revealed that the new algorithms achieved better solutions on specific and general comparison