Novas abordagens para o problema de recobrimento de rotas

• Ano de defesa: 2008
• Autor(a) principal: Motta, Luciene Cristina Soares
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Programa de Pós-Graduação em Computação; Computação
• Palavras-chave em Português: Ciência da computação; Metaheurística GRASP; Metaheurística VNS; Regras de redução; Algoritmo em grafos; Metaheurística; Heurística; Problema de recobrimento de rotas generalizado; Metaheurística híbrida; Testes de redução; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::COMPUTABILIDADE E MODELOS DE COMPUTACAO
• Link de acesso: https://app.uff.br/riuff/handle/1/17882

The Covering Tour Problem is a job sequencing problem and it is defined on a graph G = (V U W; E), where W is a set of vertices that must be covered. The problem consists of determining a minimum length Hamiltonian cycle on a subset of V such that every vertex of W is within a distance a from at least one node in the cycle. Being a generalization of the Traveling Salesman Problem, this problem is NP-Hard. This work presents a new mathematical formulation based on flow variables, reduction rules for the associated graphs and original metaheuristic algorithms to solve a generalized version of Covering Tour Problem approximately.