Otimização de rotas urbanas no sul fluminense

uma aplicação do problema do caixeiro viajante utilizando algoritmo de força bruta para determinação de ciclos Hamiltonianos

Resumo

O presente estudo investiga a aplicação do Problema do Caixeiro Viajante (TSP - Traveling Salesman Problem) na otimização de rotas urbanas entre seis municípios da região Sul Fluminense do Estado do Rio de Janeiro. Utilizando Volta Redonda como ponto de partida e retorno, foi implementado um algoritmo de força bruta para determinar o ciclo hamiltoniano de menor custo, visitando todas as cidades exatamente uma vez. As distâncias entre os municípios foram obtidas através do Google Maps, representando as distâncias reais por via rodoviária. O estudo empregou a biblioteca NetworkX em Python para modelagem do grafo e visualização dos resultados, além de algoritmos de permutação para exploração exaustiva do espaço de soluções. Os resultados demonstraram que, entre as 120 permutações possíveis, o algoritmo identificou uma rota ótima com distância total de aproximadamente 187,3 quilômetros, oferecendo insights relevantes para planejamento logístico regional e otimização de deslocamentos urbanos. A metodologia empregada, embora computacionalmente intensiva para instâncias maiores, mostrou-se eficaz para problemas de pequena escala, fornecendo soluções exatas e servindo como base comparativa para algoritmos heurísticos mais avançados.