O problema de recobrimento por rotas: algoritmos e regras de redução

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=(VW, E), onde V é o conjunto dos vértices que podem ser visitados, W é o conjunto dos vértices que devem ser cobertos e TV é 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 wW, 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.

Author dc:creator

• Motta, Luciene Cristina Soares

Statement dc:rights

• Open Access

Language dc:language.iso

pt_BR

Repository record dc:identifier.uri

https://app.uff.br/riuff/handle/1/37938

OAI identifier oai:identifier

oai:app.uff.br:1/37938