Resolução do problema do caixeiro viajante através de técnicas heurísticas
O Problema do Caixeiro Viajante (PCV) é um problema clássico de otimização trabalhado por diversos pesquisadores pela sua simplicidade na formulação, complexidade na resolução e sua larga aplicabilidade no mundo real, e sua resolução podem trazer inúmeros benefícios para a sociedade. O presente trab...
| Autor principal: | RAMOS, Eliaquim Monteiro |
|---|---|
| Grau: | TCC |
| Idioma: | pt_BR |
| Publicado em: |
Universidade Federal do Oeste do Pará
2024
|
| Assuntos: | |
| Acesso em linha: |
https://repositorio.ufopa.edu.br/jspui/handle/123456789/1520 |
| Resumo: |
|---|
|
O Problema do Caixeiro Viajante (PCV) é um problema clássico de otimização trabalhado por diversos pesquisadores pela sua simplicidade na formulação, complexidade na resolução e sua larga aplicabilidade no mundo real, e sua resolução podem trazer inúmeros benefícios para a sociedade. O presente trabalho apresenta técnicas heurísticas de construção de rotas (vizinho mais próximo, inserção do mais próximo e inserção do mais distante) e heurísticas de melhoria de rotas (2-opt e 3-opt) que foram implementadas no ambiente MATLAB para otimizar o PCV. Para verificar suas performances, as abordagens foram testadas em instâncias , tais como: Att48, Berlin52 e Ulysses22 que estão disponíveis na TSPLIB. Verificou-se que a combinação entre as heurísticas de construção de rotas com mecanismo 3-opt apresentaram as melhores soluções. |