Uma Abordagem Paralela Baseada em Colônia de Formigas para o Problema do Caixeiro Viajante

Abstract

Neste artigo propomos uma versão paralela para umproblema clássico de otimização, denominado caixeiroviajante ou Travelling Salesman Problem (TSP). O TSPé um problema NP-completo de difícil solução. Um dosproblemas principais no TSP é o alto tempo decomputção necessário para encontrar uma solução.Uma das abordagens para resolver esse problemaconsiste em encontrar uma solução aproximada, atravésde alguma heurística conhecida, que pode serencontrada na literatura. Por exemplo, soluções queutilizam algoritmos genéticos e GRASP.O objetivo deste trabalho é descrever e avaliar umaversão paralela do TSP, utilizando como heurística asimulação de colônia de formigas. Nossos resultadosforam obtidos em um sistema SP2, com 2, 4 e 6processadores, e demonstram que obtivemos bonsspeedups, e soluções bem próximas do valor ótimo.