Como funciona a otimização de rotas (em linguagem simples)

Otimização de rotas é escolher a melhor ordem para visitar um conjunto de paradas, dados o ponto de partida e o lugar onde você precisa terminar. "Melhor" geralmente significa a menor distância ou o menor tempo de direção. Para uma empresa com vários veículos, significa também decidir qual veículo visita quais paradas.

Ela trabalha junto com a navegação, não no lugar dela. O seu app de navegação encontra as melhores vias de uma parada até a seguinte; a otimização de rotas decide qual parada vem depois. As duas se confundem porque ambas terminam em uma linha no mapa.

Todo otimizador de rotas, de uma ferramenta web gratuita a um sistema corporativo de despacho, executa alguma versão das mesmas quatro etapas.

1. Geocodificação

Cada endereço é comparado com uma base de dados de ruas e pontos de endereço e vira um par de coordenadas. É a etapa que as pessoas esquecem e a que está por trás da maioria das rotas ruins: uma parada marcada na cidade errada arrasta a ordem inteira. Veja por que endereços caem no lugar errado.

2. A matriz de distâncias

Em seguida vem uma tabela com a distância entre cada par de paradas: 20 paradas formam uma grade de 20 × 20 com 380 entradas que importam. Alguns otimizadores a preenchem com distâncias por estrada ou tempos de viagem de um serviço de rotas. Outros usam a distância em linha reta, que é instantânea e ordena as paradas próximas quase do mesmo jeito em áreas urbanas. Tabelas baseadas em estradas demoram mais para ser montadas e lidam melhor com rios, rodovias e ruas de mão única.

3. A ordem

A parte difícil: encontrar uma ordem curta sem conferir todas as possíveis. A próxima seção explica como.

4. Os trajetos

Por fim, a ordem escolhida passa por um motor de rotas rodoviárias, do mesmo tipo que o seu app de navegação usa, que devolve a linha pelas estradas reais, o comprimento de cada trecho e uma estimativa do tempo de direção.

Eles não testam todas as ordens; são ordens demais. Uma rota de ida e volta por 15 lugares já tem mais de 43 bilhões. Em vez disso, usam heurísticas: métodos que montam uma boa rota rapidamente e depois a melhoram, trocando a garantia de perfeição por uma resposta imediata que costuma ficar muito perto da melhor.

1. 1

   Montar uma primeira rota

   O vizinho mais próximo começa na base e sempre vai para a parada mais perto que ainda não foi visitada. É rápido e sensato, mas ganancioso: tende a deixar as paradas espalhadas para o final, e a rota se cruza. Os métodos de inserção, em vez disso, fazem um circuito crescer adicionando cada parada onde ela custa menos.

2. 2

   Melhorá-la com trocas

   O 2-opt pega dois trechos da rota e inverte o pedaço entre eles sempre que isso encurta a viagem. Isso elimina cruzamentos, e se repete até nenhuma troca ajudar. O Or-opt move uma sequência curta de uma a três paradas para um lugar melhor da rota.

3. 3

   Buscar mais fundo, se houver tempo

   Métodos mais pesados, como o Lin-Kernighan, mais conhecido pelo programa LKH, encadeiam muitas trocas. Metaheurísticas como o recozimento simulado, a busca tabu e os algoritmos genéticos às vezes aceitam de propósito uma rota pior para escapar de um beco sem saída. Solucionadores exatos conseguem provar a melhor rota possível, com um custo muito maior de tempo de processamento.

Depende do quanto as paradas estavam embaralhadas no começo. Nas nossas 48 rotas de exemplo de 7 a 12 paradas em estradas reais em 24 cidades, otimizar paradas que partiam de uma ordem aleatória reduziu a distância em uma mediana de 39% e o tempo de direção em uma mediana de 36%.

Mediana de distância economizada

39%

Mediana de tempo de direção economizado

36%

Rotas de exemplo medidas em estradas reais

48

Se você já ordena suas paradas com cuidado à mão, espere menos: o otimizador basicamente pega um ou outro cruzamento ou trecho em que se volta para trás. Quanto maior a lista e menos familiar a região, maior o ganho. Coloque um valor em dólares nisso com a calculadora de custo de rotas.

O problema do caixeiro-viajante (TSP) é um veículo visitando cada parada uma vez pela rota mais curta. O problema de roteirização de veículos (VRP) traz uma frota: vários veículos e a decisão de quais paradas cada um recebe. As versões do mundo real acrescentam regras por cima, e cada regra torna o problema mais difícil de resolver.

Isso explica em boa parte por que o software de rotas vai do gratuito a centenas de dólares por mês. As paradas de um dia para um veículo são um trabalho rápido para um computador. Vinte vans com janelas de horário e capacidades é um problema realmente difícil, e exige dados que precisam ser mantidos em dia: janelas, duração das visitas, tamanhos dos veículos.

O EZRoutePlanner resolve o problema de uma única rota: uma rota por vez, na ordem mais curta que ele encontra. Pressione Otimizar rota e as paradas são ordenadas pelo vizinho mais próximo, seguido de melhorias 2-opt, com o seu início fixo e o fim de volta ao início (Ida e volta) ou em uma parada que você fixou como a última.

Ele compara as ordens usando a distância em linha reta entre as paradas, o que é rápido o bastante para rodar no seu navegador enquanto você trabalha, e depois desenha o resultado em estradas reais com a distância de cada trecho. Os planos pagos acrescentam tempos de viagem e trajetos que evitam rodovias ou pedágios. Onde um rio ou uma rodovia separa duas paradas que parecem próximas, olhe a ordem e mova uma parada à mão se as vias não concordarem.

Para vários motoristas, você faz a divisão: selecione com o laço cada região do mapa como uma rota própria e depois otimize cada uma. Para uma empresa com poucas rotas em uma área conhecida, isso costuma ser mais rápido do que configurar um VRP completo. Veja como planejar rotas para vários motoristas.