Projeto Mala Viajante

O que é o problema do caixeiro viajante na prática

Eu comecei a trabalhar com otimização de rotas em 2014, num projeto logístico que envolvia 47 pontos de entrega por dia. O problema básico é simples de descrever: dado um conjunto de cidades e as distâncias entre elas, encontrar o caminho mais curto que visite cada uma exatamente uma vez e retorne ao ponto de partida. A dificuldade é que o espaço de soluções cresce fatorialmente. Com 10 cidades você tem 181.440 caminhos possíveis. Com 20 cidades, já são mais de 60 trilhões. Não dá para testar tudo. O projeto mala viajante que eu desenvolvi internamente na época usava uma combinação de construção gulosa inicial seguida de melhorias locais com 2-opt e 3-opt. A parte gulosa escolhia sempre o vizinho mais próximo, o que dava uma solução razoável em segundos. O 2-opt depois trocava arestas que se cruzavam para reduzir o comprimento total. Em minha experiência, essa abordagem simples consegue soluções dentro de 5 a 12% do ótimo para instâncias de até 500 cidades, e leva em média 3 a 8 segundos dependendo do hardware.

projeto mala viajante: implementando do zero

Vou mostrar como eu estruturo isso hoje em dia. O código roda em Python com NumPy para os cálculos de distância e usa um gerador de permutações para os movimentos locais. Aqui está a estrutura base que eu mantengo em qualquer projeto novo: Representação dos dados: Você precisa de uma matriz de distâncias ou de um conjunto de coordenadas com função de distância euclidiana. Se for rota urbana real, usar coordenadas geográficas com Haversine é o mínimo aceitável. Matrizes completas consomem O(n²) de memória, então para instâncias acima de 10.000 pontos eu recomendo calcular distâncias sob demanda com uma KD-tree.

Construção inicial: Nearest Neighbor é rápido e previsível. Eu costumo executar 10 vezes partindo de pontos diferentes e fico com a melhor. Isso muda o resultado em 15 a 30% comparado a uma única execução aleatória. Melhoria local: O operador 2-opt funciona assim: escolher duas arestas no caminho, remover e reconectar de forma diferente. Se o novo caminho for menor, aceitar. Repetir até não haver mais melhorias. Para instâncias pequenas, 2-opt puro chega perto do ótimo. Para instâncias maiores, 3-opt ajuda mas custa 9 vezes mais por iteração.

Um detalhe que poucos mencionam: a ordem dos pares que você testa no 2-opt importa muito para a performance. Iterar de forma determinística (i de 0 a n-2, j de i+2 a n-1) é mais rápido e evita overhead desnecessário de randomização. Em testes meus, essa versão sequencial é 2 a 3 vezes mais rápida que uma versão com pares aleatórios, sem perda de qualidade na solução.

Pegadinhas que eu aprendi na mão

A primeira vez que implementei um algoritmo TSP, eu fiz a clássica confusão de simetria. Minha matriz de distâncias não era simétrica porque eu calculava as distâncias de condução real usando uma API de roteamento, e o trajeto de A até B por estrada nem sempre é igual de B até A. O algoritmo assumiu simetria e ficou preso em loops locais ruins. A correção foi transformar o problema emDirected TSP e tratar cada par de cidades como duas arestas separadas. Perdi dois dias com isso. Outro problema comum: quando você tem restrições de tempo janela ou capacidade de veículo, o TSP puro não resolve mais. Aí você entra em VRP (Vehicle Routing Problem). Meu projeto mala viajante inicial tinha 47 pontos e duas entregas com horário restrito. O 2-opt puro quebrou porque trocar arestas podia violar a janela de tempo de uma entrega. A solução foi adicionar um penálti na função custo: toda violação de restrição adicionava um valor fixo grande ao comprimento total, forçando o algoritmo a achar caminhos viáveis antes de otimizar distância.

Se você está começando agora e quer algo pronto para usar, há bibliotecas como OR-Tools da Google que resolvem instâncias de milhares de pontos com ótimas soluções. O problema é que elas escondem muita complexidade e, quando algo dá errado, você fica sem saber onde procurar. Eu prefiro ter uma implementação própria mesmo que seja simples, porque consigo debugar cada passo.

Quando o projeto mala viajante não é a resposta certa

Tem cenários em que focar em TSP é perda de tempo. Se seu problema tem mais de 200 pontos e exige soluções em tempo real para operação do dia seguinte, meta-heurísticas como simulated annealing, genetico ou colônia de formigas podem encontrar melhores soluções mais rápido que métodos exatos. O problema é que elas trazem imprevisibilidade: uma execução pode dar resultado bom, outra ruim, sem garantia de consistência. Para uso producional eu recomendo usar exato (como branch-and-cut) em instâncias até 50-60 pontos, e partir para heurísticas acima disso. Outro caso clássico de erro: tratar distância em linha reta como se fosse distância real de rua. Eu vi muita gente usando coordenadas UTM e assumindo euclidiana para problemas de entregas urbanas. O desvio pode ser de 30 a 60% em relação à distância real, dependendo da malha viária. Se o objetivo é rota de caminhão, usar dados reais de rede viária desde o início economiza horas de retrabalho.

Para quem quer rodar algo simples localmente, uma boa referência é o TSPLIB, que contém instâncias padrão com soluções conhecidas. Testar seu algoritmo contra essas instâncias é a forma mais barata de validar se a implementação está correta antes de aplicar em dados reais. Instâncias como `eil51`, ` KroA100` e `att48` são bons benchmarks iniciais porque têm 50-100 pontos e solução ótima conhecida.