Entendendo o problema do caixeiro viajante na prática
Trabalhar com roteirização de entregas ou visitas comerciais nunca foi tão simples quanto dizem os manuais. O problema do caixeiro do comércio, conhecido internacionalmente como Traveling Salesman Problem (TSP), parece algo teórico até você precisar fazer doze visitas em um dia e voltar ao ponto de origem gastando o mínimo possível de combustível e tempo. A ideia central é straightforward: dado um conjunto de cidades e as distâncias entre cada par, encontrar o caminho mais curto que visite cada cidade exatamente uma vez e retorne ao ponto de partida. A parte que ninguém conta nos livros é que, assim que você passa de cerca de vinte pontos, a coisa sai do domínio da intuição e entra no território de algoritmos mesmo.
O que exatamente são os caixeiros do commercio e por que isso importa
O caixeiro do comércio representa o modelo clássico de otimização combinatória aplicado a logística e vendas. Na prática, você tem um roteiro onde cada parada é um cliente, um depósito, um ponto de entrega. O objetivo é minimizar distância, tempo ou custo. A dificuldade matemática é que o número de rotas possíveis cresce fatorialmente com o número de cidades. Com dez cidades, são 181.440 combinações. Com vinte, você já está falando de algo como 60 quintilhões de possibilidades. Isso significa que soluções exatas só funcionam para instâncias pequenas. Para o mundo real, você precisa de aproximações.
Como resolver na prática
Eu comecei tratando isso com força bruta em Python mesmo, num projeto pequeno de logística para uma distribuidora no interior de São Paulo. Tinha onze pontos de entrega. Consegui rodar o algoritmo exato usando programação dinâmica estilo Held-Karp em cerca de doze segundos num notebook comum. Foi quando percebi que o problema escalava mal. Passamos para trinta e dois pontos mês seguinte e o computador simplesmente não finalizava. O Held-Karp é o algoritmo exato mais viável para instâncias até uns quarenta pontos. Complexidade O(n² · 2). Não é bonito, mas funciona para tamanhos moderados. Implementação típica usa bitmask para representar subconjuntos de cidades já visitadas. Se você tem menos de quarenta destinos e precisa da rota ótima, esse é o caminho. Código aberto abundante no GitHub, bibliotecas como Concorde TSP Solver são o padrão da indústria para casos que exigem prova de optimalidade.
Para problemas maiores, a realidade é que você trabalha com heurísticas. O nearest neighbor é o mais básico: começa em um ponto e vai até a cidade mais próxima não visitada. Roda em tempo polinomial, mas a solução pode ser arbitrariamente pior que o ótimo. Não use isso como solução final se qualidade importa. O Christofides é um salto qualitativo. É um algoritmo de aproximação com garantia teórica de 1.5 vezes o ótimo para distâncias que satisfazem a desigualdade triangular. Na prática, costuma entregar rotas muito boas para duzias de cidades. Implementações existem em C++ e Python. A desvantagem é a complexidade de implementação maior e o fato de que, para grafos reais de logística, a garantia não se aplica exatamente porque distâncias rodoviárias nem sempre satisfazem triangulação estrita.
Genetic algorithms e simulated annealing são as ferramentas que eu uso no dia a dia. Para uma frota com cinquenta a duzentos pontos, o simulated annealing com cooling schedule razoável convergi para soluções dentro de dois a cinco por cento do ótimo em questões de minutos. Tem um custo de tuning: você precisa ajustar taxa de resfriamento, temperatura inicial e número de iterações por temperatura. Meu ponto de partida sempre é temperatura inicial equivalente a cem vezes o desvio padrão das distâncias entre pares de pontos, rate de resfriamento de 0.995, e rodar até o custo estabilizar por três iterações consecutivas de mil passos cada. Para quem quer algo pronto, o Google OR-Tools é a biblioteca mais completa atualmente. Suporta Vehicle Routing Problem com múltiplos veículos, janelas de tempo, capacidades, e usa solving híbrido que combina branch-and-cut com heurísticas. Roda em Python, C++ e Java. A curva de aprendizado é de umas duas semanas para dominar os conceitos de constraints e callbacks. O resultado compensa.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Um caso específico que quase me custou um contrato
Em 2023, fiz uma implementação de roteirização para uma empresa de delivery farmacêutico. O problema parecia simples: quinze farmácias, um depósito central, minimizar distância total. O algoritmo entregou um roteiro de 147 quilômetros. Parecia bom. Dois dias depois, o motorista relatou que o trecho entre a farmácia sete e a farmácia doze tinha um desvio obrigatório de dezoito quilômetros devido a obras na avenida principal que não constavam na base de distâncias que eu usava. O roteiro original estava matematicamente ótimo para o grafo que eu tinha, mas logisticamente inviável. A solução foi adicionar um penalty weight nos arestas que passavam por regiões conhecidas com restrições de tráfego e rodar o otimizador com esse custo modificado. Funcionou, mas o tempo de computação triplicou. Aprendi que a qualidade da matriz de distâncias é mais importante que a sofisticação do algoritmo. Uma matriz ruim com o melhor solver do mundo entrega uma solução ruim. Inverta os termos e um solver mediano com dados bons ainda entrega algo útil.
Pegadinhas que todo mundo ignora
O primeiro erro crônico é assumir simetria nas distâncias. A maioria dos implementadores tratar a matriz como simétrica porque simplifica a matemática. Estradas reais, porém, têm sentido único, horários de pico assimétricos, e pedágios que variam conforme a direção. Use directed graphs quando a realidade pedir. O custo computacional sobe, mas a solução reflete o mundo real. O segundo erro é ignorar janelas de tempo. O caixeiro viajante clássico não temporidade. Mas um vendedor que precisa chegar na loja nove entre às nove e às onze da manhã não pode ser roteirizado como se hora não importasse. Quando janelas entram no problema, você deixa de ter TSP e passa a ter VRPTW (Vehicle Routing Problem with Time Windows). A complexidade explode. Algoritmos exatos tornam-se impraticáveis acima de vinte pontos praticamente. Heurísticas tornam-se a única opção viável.
O terceiro erro, e talvez o mais caro, é não considerar a dimensão veicular. O TSP assumi um único agente. Frota real tem múltiplos veículos com capacidades diferentes, motoristas com turnos limitados, e centros de distribuição que podem não ser o ponto inicial e final de todos os veículos. Resolver TSP puro e depois tentar partitionar as rotas manualmente gera conflitos e ineficiências que um solver de VRP capturaria nativamente.
Quando o caixeiro do comércio simplesmente não resolve
Existem cenários onde modelar como TSP é contraproducente. Se você tem mais de trezentos pontos de entrega, nenhuma abordagem exata vai te dar úteis dentro de prazo razoável. Heurísticas vão entregar algo, mas a incerteza sobre a qualidade da solução aumenta. Nesses casos, o problema pode nem ser de roteirização pura. Pode ser de localização de depósitos, de divisão de zonas geográficas, ou de agendamento de prioridades. Decompor o problema em subproblemas menores e resolvelos separadamente costuma funcionar melhor do que atacar tudo de uma vez. Outro cenário onde TSP falha completamente é quando há dependências sequenciais entre visitas. Se o cliente três só pode ser atendido após o cliente um deixar algum material, o problema deixa de ser um ciclo hamiltoniano e vira um problema de precedência. A estrutura muda completamente e algoritmos de TSP não se aplicam diretamente.
Para quem quer começar a brincar com isso de forma prática, o dataset padrão da comunidade é o TSPLIB, mantido por Gerhard Reinelt. Contém instâncias de testes com soluções conhecidas para validação. Instâncias como rat99, d129 e kroA100 são bons pontos de partida. Compare seu algoritmo contra os valores ótimos reportados lá. Se seu nearest neighbor entrega 30% acima do ótimo em rat99, você tem uma noção realista do gap que precisa fechar. O campo de roteirização comercial avançou muito nos últimos anos com abordagens baseadas em machine learning também. Pesquisas recentes mostram que redes neurais podem aprender heurísticas de construção de rotas que competem com métodos clássicos em certos tipos de instâncias. Mas isso ainda é pesquisa acadêmica aplicável. Para produção, OR-Tools e Solvers comerciais como Gurobi com modelos de routing continuam sendo o estado da arte confiável.
