Novas Propostas para o Problema de Recobrimento de Rotas

O Problema de Recobrimento de Rotas (PRR) é uma generalização do Problema do Caixeiro Viajante com várias aplicações reais. Seja G=(N,E) um grafo não direcionado, sendo N o conjunto de vértices formado pela união de dois conjuntos disjuntos V e W , e E={(vi,vj)|vi,vj E N} o conjunto de arestas. O conjunto V está associado aos vértices que podem ou não fazer parte da rota, ou seja, podem ou não ser visitados. T é o subconjunto de vértices de que obrigatoriamente devem fazer parte da rota. W é o conjunto de vértices que devem ser cobertos pelos vértices do conjunto V que fazem parte da rota. A partir destas considerações, temos que o PRR consiste em determinar uma rota de comprimento mínimo ou um ciclo Hamiltoniano sobre um subconjunto de V , tal que todos os vértices do conjunto T (T C V) estejam na rota e todo vértice de W seja coberto por esta rota. Nesta tese, propomos e analisamos uma nova formulação matemática para o PRR, uma nova regra de redução e seis algoritmos heurísticos. No final deste trabalho, apresentamos os resultados computacionais para um conjunto de problemas teste.