Roteirização e otimização de rotas: do endereço ao roteiro que a operação cumpre

Há uma conversa que se repete em toda apresentação de software de roteirização. Alguém mostra um mapa antes, com linhas cruzadas e cores embaralhadas, e um mapa depois, com setores limpos e rotas em pétala. A plateia aprova. Seis meses depois, a operação está rodando com o roteiro editado à mão todo dia de manhã, e ninguém sabe explicar exatamente quando isso começou.

O diagnóstico costuma ser atribuído ao algoritmo, mas raramente é dele. O otimizador entrega, com bastante precisão, a melhor resposta para o problema que foi descrito a ele. Quando o roteiro não cola na realidade, quase sempre o que estava errado era a descrição: tempos que não existem, paradas no lugar errado, restrições que ficaram na cabeça do supervisor e um objetivo que ninguém definiu por escrito.

O que é roteirização, e o que ela não é

Vale separar três coisas que costumam ser tratadas como uma só, porque cada uma tem custo, dado e dono diferentes.

Confundir a primeira com a segunda é o erro mais comum. Um aplicativo de navegação resolve muito bem o cálculo de caminho, e resolve para um destino de cada vez. Roteirização é outra classe de decisão: envolve alocar dezenas ou centenas de paradas entre uma frota, respeitando capacidade, horário e jornada, com o agravante de que cada escolha muda o custo de todas as outras.

O problema tem nome e tem 1959 na certidão

A formulação original é mais antiga do que a maior parte dos sistemas que a implementam. Em 1959, G. B. Dantzig e J. H. Ramser publicaram na Management Science o artigo The Truck Dispatching Problem, tratando, segundo o resumo do próprio trabalho, "do roteamento ótimo de uma frota de caminhões de entrega de gasolina entre um terminal de distribuição e um grande número de postos de serviço abastecidos pelo terminal". O enunciado descrito ali é exatamente o que ainda se resolve hoje: dadas as rotas mais curtas entre quaisquer dois pontos do sistema e a demanda de cada posto, "deseja-se encontrar uma forma de atribuir postos a caminhões de tal maneira que as demandas sejam satisfeitas e a quilometragem total percorrida pela frota seja mínima".

Dois detalhes do artigo original merecem atenção porque explicam o campo inteiro. O primeiro é que os autores apresentam "um procedimento baseado em uma formulação de programação linear para obter uma solução quase ótima". Quase ótima, não ótima. O segundo é a franqueza da última linha do resumo: "nenhuma aplicação prática do método foi feita até o momento", embora vários problemas de teste tivessem sido calculados. Sessenta e sete anos depois, a busca por solução exata continua sendo exceção, e a norma continua sendo boa solução em tempo aceitável.

Na literatura e nas ferramentas atuais, a família de problemas ganhou o nome de Vehicle Routing Problem, o VRP. A documentação do Google OR-Tools, um dos pacotes de otimização de código aberto mais usados no assunto, define assim: "no Vehicle Routing Problem (VRP), o objetivo é encontrar rotas ótimas para múltiplos veículos visitando um conjunto de locais". E acrescenta a relação com o caixeiro viajante em uma frase: "quando há apenas um veículo, ele se reduz ao Traveling Salesperson Problem".

A pergunta que quase ninguém responde: otimizar o quê?

Este é o ponto que mais devolve projeto para a estaca zero. A palavra "ótimo" só significa alguma coisa depois que alguém define a função objetivo, e a própria documentação do OR-Tools chama atenção para isso, observando que a expressão rotas ótimas exige definição cuidadosa. Ela apresenta como alternativa prática "minimizar o comprimento da rota mais longa entre todos os veículos", registrando que essa é "a definição correta se o objetivo é concluir todas as entregas o quanto antes". No exemplo oficial, isso é feito atribuindo um coeficiente alto ao global span das rotas, que naquele caso é a maior das distâncias percorridas.

Já na variante com janelas de tempo, a mesma documentação descreve o objetivo de outra forma: "minimizar o tempo total de viagem dos veículos". São dois critérios legítimos e incompatíveis entre si. O quadro abaixo resume o que muda na prática.

Recomendação, e aqui falamos por experiência de implantação: escreva a função objetivo em português, com o cliente na sala, antes de ligar qualquer solver. Se a área comercial quer nível de serviço, a operação quer custo e o RH quer jornada equilibrada, esse conflito não vai ser resolvido pelo algoritmo. Ele vai ser resolvido por alguém escolhendo pesos, e é melhor que essa escolha seja explícita e assinada.

A matriz de tempos é a fundação de tudo

Antes de otimizar, o solver precisa saber quanto custa ir de cada ponto a cada outro ponto. Esse insumo é a matriz de origem e destino, e ela sai de um motor de roteamento que percorre a malha viária de verdade. O OSRM, motor de código aberto construído sobre dados do OpenStreetMap, é um exemplo instrutivo porque sua documentação separa com clareza os serviços disponíveis: route, para o caminho mais rápido entre coordenadas na ordem informada; nearest, para encaixar uma coordenada na malha; table, para a matriz; match, para casar pontos de GPS com as vias; trip, para ordenação de paradas; e tile, para tiles vetoriais do grafo de roteamento.

O serviço table é o que interessa aqui. Ele "retorna as durações, as distâncias ou ambas entre os pares de coordenadas" informados, com durações em segundos e distâncias em metros, calculadas a partir das rotas mais rápidas, e não de distâncias em linha reta. Essa última ressalva parece óbvia e é violada com frequência: matriz euclidiana, calculada por fórmula sobre coordenadas, é rápida, barata e produz roteiro que ignora rio, viaduto, mão única e serra.

Vale conhecer também o serviço trip, que resolve o caixeiro viajante para as paradas informadas. A documentação é transparente sobre o método: ele "resolve o Traveling Salesman Problem usando uma heurística gulosa (algoritmo de inserção mais distante) para 10 ou mais pontos de parada e usa força bruta para menos de 10", e o resultado é uma aproximação, não uma solução ótima, dada a complexidade do problema. É uma boa lembrança de que existe uma escada de sofisticação: ordenar paradas de um veículo é um degrau; distribuir paradas entre uma frota com capacidade e janela é outro, bem mais alto.

Restrições: onde o modelo encosta na realidade brasileira

Um VRP sem restrições é um exercício de sala de aula. O que transforma o roteiro em algo cumprível é o conjunto de limites que a operação já conhece, mas que costuma estar apenas na cabeça de quem programa as rotas há dez anos. A própria documentação do OR-Tools trata as duas mais comuns como variações do problema base: as restrições de capacidade, em que "os veículos precisam recolher itens em cada local que visitam, mas têm uma capacidade máxima de carga", e as janelas de tempo, em que "cada local deve ser visitado dentro de uma janela de tempo específica".

Sobre janelas, há um detalhe de modelagem que costuma passar batido. Na formulação com tempo, o custo de arco deixa de ser distância e passa a ser tempo de viagem, e o modelo precisa admitir espera: se o veículo chega antes da abertura da janela, ele fica parado até poder atender. Espera é tempo real, ocupa o veículo e o motorista, e um roteiro que parece excelente em quilometragem pode ser péssimo em horas pagas.

No Brasil, uma terceira família de restrições costuma pesar tanto quanto capacidade e janela: a regulação de circulação urbana. Em São Paulo, a Companhia de Engenharia de Tráfego registra que "a restrição ao trânsito de caminhões na Zona de Máxima Restrição de Circulação - ZMRC é de 2ª a 6ª feira das 5 às 21h e aos sábados das 10 às 14h", com regimes específicos de autorização por perfil de veículo e por tipo de carga. Isso significa que a pergunta "qual veículo atende esta parada" deixa de ser só sobre capacidade e passa a ser sobre elegibilidade em função do horário e do território.

Complete a lista com o que é específico do seu negócio: habilitação e certificação do motorista, compatibilidade de produto com o veículo, restrição de altura e de peso por trecho, tempo de atendimento por tipo de cliente, obrigatoriedade de dupla no embarque, jornada e descanso. Cada item desses tem um custo de modelagem, e vale a pena escolher: entram no modelo os que efetivamente inviabilizam o roteiro, não todos os que alguém consegue imaginar.

O dado que precisa estar pronto antes do otimizador

Nenhum solver conserta cadastro ruim. A checagem abaixo é a que fazemos antes de discutir algoritmo, e ela costuma consumir mais tempo do que a configuração da otimização em si.

• Coordenada da parada, não do CEP. Endereço geocodificado no nível de logradouro ou de CEP jogado no centroide produz sequência plausível no mapa e impossível na rua. O tema tem armadilhas próprias, tratadas no nosso guia de geocodificação de endereços.
• Tempo de atendimento por parada. Não é constante. Descarregar em um supermercado de bairro e em um centro de distribuição são eventos com ordem de grandeza diferente, e usar uma média única distorce todo o horário previsto do dia.
• Demanda na unidade certa. Peso, volume, paletes e caixas restringem de forma diferente. Frota que fecha por cubagem e é modelada por peso vai receber roteiro sistematicamente inviável.
• Malha viária atualizada. Loteamento novo, sentido invertido e via em obra mudam o tempo real e não mudam a matriz até que alguém atualize a base.
• Janela real, não a janela do contrato. A janela registrada no cadastro costuma ser mais folgada ou mais rígida do que a praticada. Vale conferir com quem entrega antes de tratá-la como restrição dura.

Um sinal prático de maturidade: se ninguém na empresa sabe dizer qual porcentagem das paradas tem coordenada validada, o projeto ainda não está na fase de otimização. Está na fase de cadastro, e é melhor admitir isso cedo.

Plano contra execução: a aderência que ninguém mede

O roteiro é um plano feito às 22h do dia anterior sobre premissas que começam a envelhecer às 6h do dia seguinte. Cliente ausente, carga recusada, trânsito atípico, veículo em manutenção. A pergunta que separa projeto maduro de projeto de vitrine é simples: alguém compara, todo dia, o roteiro planejado com o roteiro efetivamente percorrido?

Essa comparação depende de rastro de execução com qualidade, o que traz de volta um assunto conhecido de quem opera em campo: a coordenada coletada tem erro, e esse erro tem causas identificáveis, como detalhamos em precisão do GPS em campo. O ponto aqui é que aderência não se mede por percepção. Ela se mede por três indicadores baratos e brutalmente informativos:

1. Aderência de sequência. Percentual de paradas atendidas na ordem planejada. Queda persistente indica que o roteiro não convence quem dirige, e isso quase sempre tem um motivo legítimo por trás.
2. Desvio de horário por parada. Diferença entre horário previsto e realizado. Se o desvio cresce ao longo do dia, o tempo de atendimento ou a matriz de tempos estão subestimados.
3. Paradas fora do plano. Atendimentos e deslocamentos que não estavam no roteiro. É onde aparecem as regras informais que ninguém contou ao modelo.

O terceiro indicador é o mais valioso, porque é uma fonte gratuita de requisitos. Cada desvio recorrente é uma restrição real que ficou de fora da modelagem. Levantar isso de forma sistemática vale mais do que trocar de solver.

Do lado operacional, a execução só vira dado se a equipe conseguir registrar o que aconteceu no momento em que aconteceu, inclusive sem rede, assunto do nosso guia de trabalho offline em campo. Esse encadeamento entre planejamento e execução é justamente o que sustentamos nos projetos de gestão operacional com o Phrisma: o roteiro sai do otimizador, chega ao dispositivo do técnico ou do motorista e volta como evento datado e georreferenciado, alimentando o próximo ciclo de planejamento.

Sete armadilhas de projeto de roteirização

A lista a seguir é a nossa checagem de projeto, formada em implantações. Não é afirmação das fontes citadas.

1. Usar distância em linha reta na matriz. Barato no piloto, caro na operação. O roteiro fica bonito no mapa e ignora a malha.
2. Não escrever a função objetivo. Sem critério declarado, cada área julga o resultado por um padrão diferente e o projeto nunca é aprovado.
3. Ignorar tempo de atendimento. Otimizar deslocamento quando a maior parte do dia é permanência em cliente resolve a fração errada do problema.
4. Tratar restrição regulatória como exceção manual. Funciona enquanto o programador experiente estiver na empresa.
5. Rodar o otimizador só uma vez por dia. Sem replanejamento intradiário, o primeiro imprevisto devolve a operação ao improviso.
6. Comparar o resultado com o cenário errado. O ganho precisa ser medido contra a operação atual real, com as mesmas restrições, e não contra um cenário teórico sem janela nem capacidade.
7. Não medir aderência. Sem o comparativo entre planejado e realizado, o projeto vira uma opinião defendida em reunião.

Nenhum desses pontos exige tecnologia adicional. Todos exigem decisão tomada antes da primeira rodada. É por isso que, nos projetos de automação de decisões geoespaciais que a Felikis conduz, o desenho do dado e do objetivo vem antes da escolha da ferramenta. Se quiser ver como esse encadeamento aparece do lado de campo e do lado de monitoramento, os produtos da Felikis mostram o caminho do dado da coleta ao painel de decisão.

Perguntas frequentes

Fontes e referências