Otimizador de Rota TSP

O que é o Problema do Caixeiro Viajante (TSP)?

TSP pergunta: dada um conjunto de locais e distâncias, qual a rota mais curta que visita cada local exatamente uma vez e retorna ao início?

TSP é NP-difícil. Soluções práticas usam heurísticas: Vizinho mais próximo (rápido, ~25% acima do ótimo), Clarke-Wright e meta-heurísticas.

Aplicações: entregas última milha, serviço de campo, perfuração de PCB e rotas de picking em armazém.

Formula: Objetivo: min Σ d(route[i], route[i+1]) Vizinho mais próximo: visitar o local não visitado mais próximo Economia: s(i,j) = d(depósito,i) + d(depósito,j) − d(i,j)

Exemplo de cálculo

Depósito em (0,0), 4 paradas em (3,4), (6,1), (8,5), (2,7). Vizinho mais próximo a partir do depósito: (3,4) d=5,0, depois (2,7) d=3,2, depois (8,5) d=6,3, depois (6,1) d=4,5, retorno d=6,1. Total = 25,04 (os trechos arredondados somam 25,1). Com quatro paradas esta já é a rota mais curta — nenhuma das 24 ordens é mais curta — e o método de economias devolve os mesmos 25,04.

Quando usar esta calculadora

• Um despachante de entregas planejando uma rota diária para um único motorista visitando 10-30 locais de clientes
• Um gerente de serviço de campo otimizando rotas de técnicos para minimizar o tempo de viagem entre chamadas de serviço
• Um engenheiro de armazém projetando um caminho ótimo de separação através de múltiplas localizações de corredor
• Um representante de vendas planejando uma viagem a múltiplas cidades para visitar clientes com distância mínima de condução

Erros comuns a evitar

• Assumir que a solução do vizinho mais próximo é ótima — é uma heurística gulosa que pode estar 20-25% acima da rota ótima; sempre tente múltiplos algoritmos e compare
• Usar distâncias em linha reta (euclidiana) para roteamento rodoviário — as distâncias reais de condução podem ser 20-40% maiores devido às redes viárias; para roteamento rodoviário, use distâncias reais se disponíveis
• Esquecer de incluir a viagem de retorno ao depósito — TSP requer retornar ao ponto de partida; omitir o retorno subestima a distância total da rota
• Aplicar TSP a problemas que são realmente VRP — se você tem restrições de capacidade, janelas de tempo ou múltiplos veículos, use a ferramenta VRP para melhores resultados

Como interpretar os resultados

• Compare os resultados de Nearest Neighbor e Clarke-Wright: se diferem significativamente, o problema tem espaço para mais otimização com métodos mais avançados
• O tempo de computação em milissegundos ajuda a avaliar se o re-roteamento em tempo real é viável para o tamanho do seu problema
• A visualização do mapa da rota ajuda a identificar ineficiências óbvias como rotas que se cruzam ou retornos desnecessários que as heurísticas podem produzir

Normas e referências relacionadas

• Vizinho mais próximo e economias de Clarke-Wright (1964) — as heurísticas construtivas comparadas nesta ferramenta
• Busca local de Lin-Kernighan — a heurística de referência de facto para rotas TSP de alta qualidade
• TSPLIB — a biblioteca pública de referência padrão usada para comparar a qualidade dos solucionadores de TSP

Perguntas frequentes

Qual algoritmo devo usar?

Menos de 15 paradas: Vizinho mais próximo. 15-50: Clarke-Wright + 2-opt. 50+: meta-heurísticas ou Google OR-Tools.

Como TSP difere do roteamento real de entregas?

Roteamento real adiciona janelas de tempo, capacidade veicular, trânsito e múltiplos veículos. TSP fornece o limite inferior de distância como benchmark.