O Problema de Recobrimento de Rotas (PRR) é um problema de seqüenciamento de tarefas definido sob um grafo G = (V U W;E) onde W é o conjunto de vértices que devem ser cobertos. O problema consiste em determinar uma rota ou um ciclo Hamiltoniano de comprimento mínimo sob um subconjunto de V, de modo que todo vértice de W diste no máximo d de algum vértice da rota. Sendo uma generalização do Problema do Caixeiro Viajante (PCV), o PRR é considerado NP-Difícil. Este trabalho apresenta uma nova formulação matemática baseada em variáveis de fluxo, regras para a redução do grafo associado e metaheurísticas para solucionar aproximadamente uma versão generalizada do Problema de Recobrimento de Rotas (PRRG).