Como encontrar a rota mais curta entre várias paradas

Nem sempre. A rota mais curta percorre menos quilômetros; a mais rápida leva menos tempo. Um contorno por rodovia pode ser mais longo, porém mais veloz, do que cortar pela cidade, e uma zona escolar às 15h pode deixar o caminho curto lento.

Com muitas paradas, porém, as duas costumam coincidir, porque a grande decisão é a ordem das paradas, não as ruas entre elas. Um percurso sensato pela área economiza muito mais do que uma via mais rápida entre duas paradas quaisquer. Por isso o jeito usual é escolher a ordem pela distância e deixar o app de navegação escolher as ruas mais rápidas de cada trecho enquanto você dirige, com trânsito ao vivo.

O Otimizar rota do EZRoutePlanner ordena as paradas por distância, não pelo trânsito ao vivo. Os planos pagos mostram o tempo de direção de cada trecho, e o Google Maps, o Apple Maps ou o Waze cuidam do trânsito no caminho.

Porque o número de ordens possíveis cresce mais rápido do que qualquer um consegue conferir. Com a partida fixa, 5 paradas podem ser visitadas em 120 ordens diferentes; 12 paradas têm 479.001.600. Achar a mais curta é o problema do caixeiro-viajante, um dos problemas difíceis mais conhecidos da matemática.

Os planejadores de rotas não conferem todas as ordens. Eles montam rápido uma boa rota e depois a melhoram com pequenas trocas até nenhuma ajudar mais. Você pode ver isso acontecer no solucionador do caixeiro-viajante: solte alguns pontos e veja o circuito se desembaraçar.

Até cerca de oito paradas, um mapa e alguns minutos levam você perto da melhor ordem. O truque é trabalhar de fora para dentro, não da partida para fora.

1. 1

   Coloque todas as paradas em um só mapa

   Marque-as em um app de mapas ou faça pontos numerados em um mapa impresso. Ver tudo de uma vez é metade do trabalho.

2. 2

   Estique um elástico em volta delas

   Imagine um elástico esticado em volta das paradas mais externas. Em um mapa plano, o circuito mais curto sempre visita essas paradas externas na ordem em que o elástico as toca, então elas são o esqueleto da sua rota.

3. 3

   Encaixe as paradas de dentro

   Encaixe cada parada interna entre as duas paradas vizinhas em que ela acrescenta menos distância. Comece pelas internas mais próximas do elástico.

4. 4

   Elimine todos os cruzamentos

   Se dois trechos se cruzam, inverta a ordem das paradas entre eles e a rota fica mais curta. É o mesmo movimento que os otimizadores repetem, chamado 2-opt.

5. 5

   Abra o circuito onde precisar

   Para uma ida e volta, comece o circuito na sua base e escolha um sentido. Para uma rota só de ida, comece na base e deixe a rota terminar no lado mais distante em vez de voltar.

Passando de cerca de oito paradas, ou se você planeja rotas mais de uma vez por semana, um otimizador é mais rápido do que ordenar à mão e geralmente dá um resultado mais curto. Ele também pega as rotas que parecem boas e não são, como o trecho de volta atrás que você nunca notaria em uma lista.

Para medir quanto vale a ordem, comparamos paradas em ordem aleatória, do jeito que uma lista ordenada por nome cai no mapa, com as mesmas paradas otimizadas, em 48 rotas de exemplo de 7 a 12 paradas em estradas reais em 24 cidades. Otimizar reduziu a distância em uma mediana de 39%, de 17% na lista com mais sorte a 65% na mais embaralhada.

1. Adicione as paradas no EZRoutePlanner: cole uma por linha ou importe uma planilha. Cada uma é localizada e marcada no mapa.
2. Crie uma rota com as paradas e defina onde ela começa: sua base ou qualquer endereço.
3. Escolha o fim. Ative Ida e volta para retornar, fixe uma última parada para terminar em um lugar específico, ou deixe as duas opções desligadas.
4. Aperte Otimizar rota. A partida fica onde está e o resto é reordenado pelo vizinho mais próximo, seguido de trocas 2-opt. A rota é desenhada em estradas reais com a distância de cada trecho.

O plano grátis otimiza rotas de até 30 paradas; os planos pagos vão até 200. Como funciona a otimização de rotas explica o método com mais detalhes.

Sim, e muitas vezes por completo. Uma rota só de ida pode deixar a parada mais distante para o fim e terminar ali. Uma ida e volta precisa retornar, então a melhor ordem sai por um lado da área e volta pelo outro. As mesmas paradas, outra resposta.

Imagine seis paradas enfileiradas ao longo de uma rodovia ao norte da cidade, com a oficina na ponta sul. Só de ida, a rota mais curta as visita em linha rumo ao norte e termina na última. Como ida e volta, você vai percorrer o trecho inteiro duas vezes de qualquer jeito, então compensa pegar as paradas a leste da rodovia na ida e as do oeste na volta, em vez de atravessar a cada uma.

Diga ao otimizador que tipo de rota é antes de apertar o botão, ou ele resolverá o problema errado. Mais em como planejar uma rota de ida e volta.

O Google Maps acha boas ruas entre as suas paradas, mas mantém as paradas na ordem em que você digitou e não as reordena. Ele também aceita até 10 lugares em uma rota. Então você pode dirigir a rota mais curta no Google Maps, mas precisa descobrir a ordem antes.

Há duas formas: ordenar as paradas à mão com o método acima e arrastá-las para o lugar no Google Maps, ou otimizá-las em um planejador de rotas e exportar o resultado como links do Google Maps, divididos para você em trechos de 10 paradas. Mais em o Google Maps otimiza rotas?.