Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Ochi, Luiz Satoru | - |
Autor(es): dc.contributor | Sales, Cláudia Linhares | - |
Autor(es): dc.contributor | Nogueira, Loana Tito | - |
Autor(es): dc.contributor | Fampa, Márcia Helena Costa | - |
Autor(es): dc.contributor | Martins, Simone de Lima | - |
Autor(es): dc.creator | Motta, Luciene Cristina Soares | - |
Data de aceite: dc.date.accessioned | 2025-08-21T20:10:26Z | - |
Data de disponibilização: dc.date.available | 2025-08-21T20:10:26Z | - |
Data de envio: dc.date.issued | 2025-04-25 | - |
Data de envio: dc.date.issued | 2025-04-25 | - |
Fonte completa do material: dc.identifier | https://app.uff.br/riuff/handle/1/37938 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/1055940 | - |
Descrição: dc.description | Este trabalho tem como objetivo apresentar novas alternativas de solução para uma generalização do Problema do Caixeiro Viajante (PCV) ainda pouco explorado na literatura, conhecido como Problema de Recobrimento por Rotas (PRR). O PRR é classificado como NP-Difícil e pode ser definido na estrutura de um grafo não direcionado G=(VW, E), onde V é o conjunto dos vértices que podem ser visitados, W é o conjunto dos vértices que devem ser cobertos e TV é o conjunto dos vértices que devem ser visitados. O problema consiste em determinar uma rota de comprimento mínimo sobre um subconjunto de V e contendo todos os vértices de T, de modo que todo vértice de W esteja no máximo a uma distância pré-estabelecida de algum vértice pertencente à rota. Adicionalmente, este trabalho aborda uma variante do PRR, chamada de Problema de Recobrimento por Rotas Generalizado (PRRG), onde os vértices wW, ao contrário do PRR, podem fazer parte da solução. Entre as contribuições apresentadas neste trabalho para o PRR e para o PRRG relacionam-se: novas regras de redução para os grafos associados, uma comparação entre as formulações matemáticas existentes na literatura para ambos os problemas, heurísticas de construção e busca local, versões da meta-heurística GRASP com e sem mecanismos baseados em memória, uma proposta baseada na meta-heurística Iterated Local Search, além de alguns resultados teóricos que estabelecem uma relação entre os referidos problemas. Experimentos computacionais apresentam as soluções exatas e heurísticas obtidas para um conjunto de instâncias do PRR e do PRRG e é verificado o impacto do uso de regras de redução na obtenção destas soluções. Uma análise estatística é realizada para avaliar o desempenho das heurísticas propostas. | - |
Descrição: dc.description | This work presents new alternative solutions to a generalization of the Traveling Salesman Problem (TSP) few explored in literature, known as the Covering Tour Problem (CTP). The CTP is classi ed as NP-Hard and can be modeled as an undirected graph G = (V ∪ W, E) where V is the set of vertices that can be visited, W is the set of vertices to be covered and T ⊆ V is the set of vertices that must be visited. The CTP consists in determining a minimum length cycle over a subset of V which contains all vertices of T, and every vertex of W must be at a distance not higher than d of any vertex present in the route. In addition, this work presents a generalization of CTP called Generalized Covering Tour Problem (GCTP), where the vertices w ∈ W can be part of the solution, in oposition to the CTP. The proposals presented in this thesis to the CTP and GCTP includes: new reduction rules to the associated graphs, a comparison between the mathematical formulations of the literature for both problems, constructive heuristics, local search algorithms, GRASP versions with and without memory-based mechanisms, a proposal based on Iterated Local Search metaheuristic and some theoretical results that establish a relation between the refferd problems. Computational experiments show the exact and heuristics solutions obtained for several instances of CTP and GCTP and the impact of the reduction rules on shuch instances is also discussed. An statistical analysis is performed to evaluate the proposed heuristics. | - |
Descrição: dc.description | 175 f. | - |
Formato: dc.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Direitos: dc.rights | Open Access | - |
Direitos: dc.rights | CC-BY-SA | - |
Palavras-chave: dc.subject | Problema de recobrimento por rotas | - |
Palavras-chave: dc.subject | Formulações matemáticas | - |
Palavras-chave: dc.subject | Regras de redução | - |
Palavras-chave: dc.subject | Heurísticas | - |
Palavras-chave: dc.subject | Heurística | - |
Palavras-chave: dc.subject | Regras de redução | - |
Palavras-chave: dc.subject | Algoritmo | - |
Palavras-chave: dc.subject | Problema de recobrimento por rota | - |
Palavras-chave: dc.subject | The covering tour problem | - |
Palavras-chave: dc.subject | Mathematical formulations | - |
Palavras-chave: dc.subject | Reduction rules | - |
Palavras-chave: dc.subject | Heuristics | - |
Título: dc.title | O problema de recobrimento por rotas: algoritmos e regras de redução | - |
Tipo de arquivo: dc.type | Tese | - |
Aparece nas coleções: | Repositório Institucional da Universidade Federal Fluminense - RiUFF |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: