Muitos problemas do cotidiano podem ser modelados como grafos. Caminhos, circuitos, fluxo em redes, fluxo de dados, roteamento, cortes, dentre vários outros. Muitos destes problemas possuem algoritmos heurísticos eficientes para instâncias relativamente grandes. Entretanto, o que se observa é que muitos destes algoritmos eficientes para estas instâncias não apresentam desempenho satisfatório para instância representadas por grafos massivos (grafos nos quais os conjuntos de vértices e arestas ultrapassam os milhões). Mesmo algoritmos heurísticos com ordem assintótica quadrática 0(n²) apresentam um desempenho insatisfatório para instâncias de grafos massivos. Portanto o novo desafio de pesquisa na área reside no desenvolvimento de métodos para o tratamento de grafos massivos. Em face do acima exposto, esta pesquisa tem por objetivo fazer um levantamento sobre o estado-da-arte no assunto: soluções heurísticas para grafos massivos e a adaptação de metaheurísticas clássicas, tais como, Simulated Annealing, Algoritmos Genéticos, GRASP, etc., para a solução de grafos massivos. Após um estudo sobre as possíveis metaheurísticas a serem implementadas, optou-se pelo algoritmo Simulated Annealing (SA). Para efeitos de comparação com trabalhos similares, existentes na literatura, optou-se pela implementação do SA para a resolução do problema da Cobertura Mínima de Vértices (PCMV). Os experimentos com o SA foram realizados sobre algumas instâncias de grafos massivos disponíveis no site Network Data Repository. A solução SA implementada foi comparada ao algoritmo FastVC que, atualmente, é o mais rápido método para solucionar o PCMV. Os resultados mostraram que o SA é bastante competitivo e apresenta bom desempenho quando aplicado a grafos massivos.