Tcc Melhor Caminho

GARDÊNIO PUIATTI RODRIGUES

OTIMIZAÇÃO DE ROTAS ATRAVÉS DA APLICAÇÃO DE
ALGORITMOS EXATOS E HEURÍSTICOS

Trabalho de conclusão de curso apresentado ao Curso de Ciência da Computação.

UNIVERSIDADE PRESIDENTE ANTÔNIO CARLOS

Orientador: Prof. Eduardo Bhering

BARBACENA
2004

2
GARDÊNIO PUIATTI RODRIGUES

OTIMIZAÇÃO DE ROTAS ATRAVÉS DA APLICAÇÃO DE
ALGORITMOS EXATOS E HEURÍSTICOS

Este trabalho de conclusão de curso foi julgado adequado à obtenção do grau de
Bacharel em Ciência da Computação e aprovado em sua forma final pelo Curso de Ciência da
Computação da Universidade Presidente Antônio Carlos.

Barbacena – MG, 14 de junho de 2004.

______________________________________________________
Prof. Eduardo Bhering - Orientador do Trabalho
______________________________________________________
Prof. Gustavo Campos Menezes - Membro da Banca Examinadora
______________________________________________________
Prof. Frederico de Miranda Coelho - Membro da Banca Examinadora

3

AGRADECIMENTOS

Agradeço a Deus, ao empenho de meu orientador, e ao apoio de familiares e amigos.

4

RESUMO

Este trabalho apresenta algumas técnicas para resolução de problemas relacionados à otimização utilizando algoritmos exatos como (Branch-and-Bound) e heurísticas como
Algoritmos Genéticos, e Vizinho Mais Próximo, sendo o Algoritmo Genético o foco do estudo. O problema se resume em dado um conjunto de rotas obter a melhor rota, com o menor tempo possível de processamento, visando minimizar os custos e otimizar os resultados alcançados. Palavras-chave: Otimização, Algoritmos Genéticos, Branch-and-Bound e Vizinho Mais
Próximo.

5

SUMÁRIO

LISTAS....................................................................................................................................................................7
1 INTRODUÇÃO.....................................................................................................................................................8
2