Veja a otimização de rotas de entrega funcionando na prática

Otimização de rotas é o cálculo que define em que ordem visitar um conjunto de endereços para percorrer a menor distância — ou gastar o menor tempo — possível.

Parece simples até você tentar fazer na mão. Com 5 paradas existem 120 ordens possíveis. Com 10, mais de 3 milhões. Com 20, o número passa de 2 quintilhões. Ninguém resolve isso olhando um mapa, e é por isso que quase toda operação de entrega roda com uma sequência pior do que poderia — sem nunca perceber, porque não existe comparação com a rota que teria sido possível.

No mercado brasileiro de logística o mesmo processo costuma ser chamado de roteirização. São o mesmo conceito: explicamos a diferença de nomenclatura aqui.

O problema tem nome: Problema do Caixeiro Viajante. Dado um ponto de partida e uma lista de endereços, qual é a menor rota que passa por todos?

Testar todas as combinações é inviável acima de uma dúzia de pontos, mesmo com muito poder computacional. Então o algoritmo não busca a rota perfeita — ele busca uma rota comprovadamente boa, rápido. O processo, em quatro etapas:

1. Geocodificação. Cada endereço vira um par de coordenadas.
2. Matriz de distâncias. Calcula-se o custo real de ir de cada ponto a cada outro, usando a malha viária e não linha reta. Mão única, conversão proibida e velocidade média da via entram aqui.
3. Solução inicial. Uma heurística monta uma primeira sequência razoável — por exemplo, sempre seguir para o ponto não visitado mais próximo.
4. Refinamento. O algoritmo troca pares de paradas de lugar repetidamente e mantém as trocas que encurtam o total, até parar de melhorar.

O resultado costuma ficar a poucos por cento do ótimo teórico — uma diferença irrelevante na rua, onde um veículo parado em fila dupla pesa mais do que 200 metros de trajeto. A comparação no topo desta página é um exemplo dessa lógica: os mesmos cinco endereços, em ordem diferente, 21% menos quilômetro.

O Google Maps liga os endereços na ordem em que você digitou. Ele encontra o melhor caminho entre dois pontos, mas não decide a sequência dos pontos.

É uma diferença que passa despercebida e custa caro: você pode ter o trajeto perfeito entre cada par de endereços e ainda assim rodar muito mais do que o necessário porque a ordem geral está errada. O Maps também trava em 10 pontos por rota — a origem mais 9 paradas.

→ O Google Maps otimiza a ordem das paradas? (o teste na prática)→ Como adicionar mais de 10 paradas no Google Maps

A otimização começa a compensar por volta de 8 paradas por rota. Abaixo disso, a intuição de quem conhece o bairro costuma chegar perto o suficiente.

Se a dúvida é se dá para resolver sem pagar por isso, vale ler o que um roteirizador gratuito resolve e onde ele trava. Se a escolha já é entre ferramentas, o comparativo de roteirizadores coloca as opções lado a lado — e a calculadora de custo por entrega mostra quanto a sua operação gasta hoje.