Novas abordagens para o problema de recobrimento de rotas

Detalhes bibliográficos
Ano de defesa: 2008
Autor(a) principal: Motta, Luciene Cristina Soares
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
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
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://app.uff.br/riuff/handle/1/17882
Resumo: 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.