Navegando por Autor "Silva, Ítalo Epifânio de Lima e"
Agora exibindo 1 - 1 de 1
- Resultados por página
- Opções de Ordenação
TCC Problema do caixeiro viajante: uma abordagem para o caso quadrático(Universidade Federal do Rio Grande do Norte, 2023-12-08) Silva, Ítalo Epifânio de Lima e; Maia, Sílvia Maria Diniz Monteiro; http://lattes.cnpq.br/1498104590221901; http://lattes.cnpq.br/5184113230581099; Goldbarg, Elizabeth Ferreira Gouvea; http://lattes.cnpq.br/2888641121265608; Diniz, Thatiana Cunha Navarro; http://lattes.cnpq.br/0745915626851539O problema do caixeiro viajante (PCV) é um dos problemas de otimização mais estudados da literatura, com diversas aplicações e variações. Uma dessas variações, o problema do caixeiro viajante quadrático (PCVQ), foi inicialmente introduzido na área de bioinformática, focada em encontrar sítios de ligações de forma ótima. Assim como o PCV, a variação PCVQ também é NP-difícil, não sendo conhecidas ainda soluções exatas em tempo polinomial para instâncias de tamanho relevante. O presente estudo visa investigar o estado da arte do PCVQ, empregando métodos exploratórios e experimentais. Avaliou-se tanto soluções exatas quanto heurísticas, além de introduzir duas novas abordagens meta-heurísticas: uma baseada em algoritmos genéticos e outra em algoritmos meméticos. A meta-heurística genética e a memética são comparadas em termos de eficácia e eficiência para diferentes tamanhos de instâncias do PCVQ. Os resultados obtidos indicam que o algoritmo memético se mostrou a melhor solução para instâncias maiores do problema, enquanto o algoritmo genético não demonstrou bons resultados, sendo por vezes pior que as heurísticas. Nas instâncias menores o algoritmo da inserção mais barata obteve melhores resultados. Concluímos que algoritmos meméticos podem ser uma solução promissora para resolver o PCVQ, oferecendo novas perspectivas para abordagens futuras.