Algrorithms for the routing meter readers problem / Algoritmos para o problema de roteamento de leituristas

AUTOR(ES)
DATA DE PUBLICAÇÃO

2007

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 geral

ASSUNTO(S)

pesquisa operacional operational research programação heuristica rural postman problem teoria dos grafos combinatorial optimization arc routing problem otimização combinatoria

ACESSO AO ARTIGO

Documentos Relacionados