Heurísticas GRASP para uma solução aproximada
do Problema de Recobrimento de Rotas Generalizado
Camilla Rodrigues de Melo
Universidade Federal Fluminense, Departamento de Ciência da Computação
24210-240, Niterói, RJ
E-mail: [email protected]
Luciene Cristina Soares Motta, Luiz Satoru Ochi
Universidade Federal Fluminense, Instituto de Computação
24210-240, Niterói, RJ
E-mail: {lmotta, satoru}@ic.uff.br
RESUMO
O Problema do Recobrimento de Rotas (PRR),
proposto por Current [1], é uma generalização
do Problema do Caixeiro Viajante que pode
ser definido na estrutura de um grafo G =
(V∪W, E), completo e não direcionado, onde
V∪W é o conjunto de vértices e E é o
conjunto de arestas. O PRR consiste em
encontrar um ciclo Hamiltoniano de
comprimento mínimo em um subconjunto de
V. Esta rota deve conter todos os vértices do
subconjunto T⊆V e deve cobrir cada vértice
do conjunto W, sendo V ∩ W=∅. O Problema
de Recobrimento de Rotas Generalizado
(PRRG), proposto por Motta et al. [2],
consiste em determinar uma rota de
comprimento mínimo sob um subconjunto de
V∪W, permitindo que os vértices de W façam
parte da solução.
metaheurística consiste em um processo
iterativo onde cada iteração possui duas fases:
uma fase de construção, onde uma solução
viável é construída componente a componente,
e uma fase de busca local. Um parâmetro
α∈[0,1] determina o quanto a fase de
construção é aleatória (α = 0 caracteriza uma
fase de construção totalmente gulosa e α = 1
uma construção totalmente aleatória).
São propostas três versões da metaheurística
GRASP, variando-se os procedimentos de
construção e busca local. Experimentos
computacionais foram realizados em um
conjunto de 48 instâncias com o objetivo de
realizar uma análise comparativa entre as três
versões propostas. Os resultados obtidos
mostraram-se promissores quando comparados
aos resultados obtidos usando métodos exatos.
Tanto o PRR quanto o PRRG tem sido pouco
explorado na literatura afim, apesar de possuir Referências
muitas aplicações, como o roteamento de
aeronaves em vôos noturnos, onde a rota não [1] J. Current, Multiobjective Design of
inclui a visita em todas as cidades diretamente
“Transportation Networks”, Ph.D. Tesis,
e o planejamento de paradas de um circo
Department
of
Geography
and
durante uma estação, onde as localidades não
Environmental Engineering, The Johns
incluídas no planejamento das paradas devem
Hopkins University, 1981.
estar acessíveis a pelo menos uma incluída.
[2] L. Motta, L. S. Ochi, C. Martinhon, Grasp
Sendo uma generalização do Problema do
metaheuristics for the Generalized
Caixeiro Viajante, o PRRG é classificado
Covering Tour Problem. MIC’2001 – IV
como NP-difícil, justificando o uso de
Metaheuristics International Conference.
metaheurísticas para obter uma solução
Porto, Portugal, (2001) 387-391.
aproximada para o problema. Neste sentido,
este trabalho propõe o uso da metaheurística [3] T. Feo and M. Resende, Greedy
GRASP (Greedy Randomized Adaptative
Randomized
Adaptative
Search
Search Procedure) [3] para a obtenção de
Procedure, Journal of Global Optimization
soluções aproximadas para o PRRG. Esta
6 (1995) 109-133.