Trabalho de Conclus?o de Curso
Implementa??o de um algoritmo paralelo e escal?vel do Ant Colony System aplicado ao problema do roteamento de ve?culos
Autor
Pereira, Francisco Evangilo de Morais
Resumen
O presente trabalho apresenta a implementa??o de um algoritmo paralelo e escal?vel do Ant Colony System (ACS) na arquitetura de processadores multicore para resolver o Problema do Roteamento de Ve?culos. Apresenta-se um esquema geral explicando como foi paralelizado cada passo da meta-heur?stica ACS abordando os pontos mais importantes da implementa??o paralela. Os experimentos foram realizados em uma m?quina de mem?ria compartilhada com 4 n?cleos. Foram realizadas an?lises de desempenho atrav?s da compara??o entre a vers?o paralela do algoritmo e a sua respectiva vers?o sequencial.
Para a an?lise de escalabilidade foram realizados experimentos com diferentes tamanhos
de problemas e quantidades de formigas. As conclus?es deste trabalho caracterizam o ACS
como um bom algoritmo para ser paralelizado, se mostrando bastante promissor para
problemas de larga escala.