Solucionador do problema do caixeiro-viajante

Porque o número de ordens possíveis explode. Com uma partida fixa, n paradas podem ser visitadas em (n − 1)! ordens, e uma volta e a sua inversa têm o mesmo tamanho, então existem (n − 1)! ÷ 2 voltas distintas.

Matematicamente, ele é NP-difícil: ninguém conhece um método que garanta achar rápido a melhor rota em todos os casos. Por isso os planejadores de rotas reais usam heurísticas: métodos rápidos que encontram rotas muito boas, normalmente a poucos pontos percentuais da melhor possível.

1. 1

   Vizinho mais próximo

   Comece na base e vá sempre para a parada mais próxima que você ainda não visitou. É rápido e geralmente razoável, mas ele se encurrala: as últimas paradas costumam ficar longe umas das outras e a rota se cruza.

2. 2

   2-opt

   Pegue dois trechos quaisquer da rota. Se inverter o trecho entre eles deixa a viagem mais curta, que é exatamente o que acontece quando dois trechos se cruzam, faça isso. Repita até nenhuma troca ajudar. O resultado não tem cruzamentos.

O Otimizar rota do EZRoutePlanner funciona da mesma forma, vizinho mais próximo seguido da melhoria 2-opt, com a sua partida mantida no lugar e o fim voltando ao início ou fixado em uma última parada. Depois ele desenha a rota nas estradas reais e mede cada trecho. Leia como funciona a otimização de rotas.

Rotas reais têm estradas. Duas paradas que parecem próximas podem estar em lados opostos de um rio ou de uma rodovia. Um planejador de rotas consulta cada endereço, ordena as paradas e depois segue a malha viária para obter a distância e o tempo reais de direção. Quanto maior a lista, maior a diferença entre a ordem em que ela por acaso está e uma boa ordem.