Roteirização
Problema de roteamento de veículos explicado sem matemática
Por MoveControl · · 7 min de leitura
Resposta rápida
O problema de roteamento de veículos é o nome técnico da pergunta que todo gestor de frota faz de manhã: como distribuir as paradas do dia entre os veículos e em que ordem visitá-las, gastando o mínimo e respeitando as restrições. Ele é difícil porque o número de combinações cresce de forma explosiva a cada parada adicionada. Por isso os sistemas não testam todas as possibilidades: usam métodos que chegam a uma boa solução em tempo útil.
O problema em uma frase
Você tem uma base, alguns veículos e uma lista de endereços para visitar. Cada veículo sai da base, faz suas paradas e volta. A pergunta é: qual divisão de paradas e qual sequência gastam menos tempo e quilômetro, sem quebrar nenhuma regra? Na literatura de logística isso é conhecido pela sigla em inglês VRP.
O parente mais famoso é o problema do caixeiro viajante, em que há um único viajante e a pergunta é apenas a ordem das cidades. O roteamento de veículos é o caixeiro viajante com vários viajantes e com as regras do mundo real por cima.
Por que é tão difícil
Com três paradas, há seis ordens possíveis, e dá para comparar todas no papel. Com dez paradas, as ordens possíveis já passam de três milhões. Com vinte, o número tem dezenove dígitos. E isso para um único veículo, antes de decidir qual parada vai para qual motorista.
Esse crescimento é o motivo pelo qual nem a pessoa mais experiente nem o computador mais rápido resolvem o problema testando tudo. A pessoa experiente usa atalhos mentais: agrupa por bairro, começa pelo mais longe, deixa o centro para depois do almoço. O sistema usa atalhos parecidos, só que aplicados com disciplina e em todas as paradas ao mesmo tempo.
As variações que aparecem na vida real
O problema básico quase nunca aparece puro. Cada operação acrescenta regras, e cada regra tem nome na literatura. Não é preciso decorar os nomes, mas ajuda reconhecer qual é o seu caso:
- Com janela de tempo: cada cliente tem um intervalo de horário em que pode ser atendido.
- Com capacidade: o veículo tem limite de peso ou volume.
- Com coleta e entrega: o mesmo veículo recolhe em um ponto e entrega em outro, e a coleta precisa vir antes.
- Com prazo de retorno: o veículo precisa estar de volta à base até determinada hora.
- Dinâmico: paradas novas surgem com os veículos já na rua.
Uma transportadora urbana costuma viver quase todas ao mesmo tempo. A coleta fixa tem janela, a carga tem hora para voltar, e às 15h chega um pedido urgente.
Cada regra nova reduz o número de rotas válidas e, ao mesmo tempo, torna mais difícil encontrar uma boa. É por isso que uma rota que parecia óbvia no mapa deixa de servir quando se lembra que o cliente do meio do caminho só abre depois do almoço.
Ótimo, bom e explicável
Como não dá para provar qual é a melhor rota de todas em tempo útil, o objetivo prático é outro: uma rota boa, calculada em segundos, que respeite todas as restrições. A diferença entre a rota boa e a rota perfeita costuma ser pequena. A diferença entre a rota boa e a rota montada às pressas costuma ser grande.
Há ainda uma qualidade pouco comentada: a rota precisa ser explicável. Alguns métodos usam sorteio interno e devolvem resultados diferentes a cada execução com os mesmos dados. Isso confunde a equipe, porque a rota de hoje muda se alguém apertar o botão de novo. Um método determinístico devolve sempre o mesmo resultado para a mesma entrada.
É a escolha feita na otimização de rotas do MoveControl: o cálculo é determinístico e considera janela de horário e prazo de retorno à base. Mesmas paradas, mesmas regras, mesma rota.
O que o gestor precisa cobrar de um roteirizador
- Que aceite as restrições reais da operação, e não apenas distância.
- Que respeite a janela de horário como regra, e não como sugestão.
- Que permita ajuste manual, porque sempre haverá informação que só a equipe tem.
- Que mostre a hora prevista de cada parada, para ser possível avisar o cliente.
- Que lide com parada nova durante o dia sem desmontar o que já está em andamento.
Para o último item, o MoveControl tem a sugestão de motorista, que indica qual motorista encaixa melhor uma coleta nova considerando a rota que cada um ainda tem pela frente.
Um teste simples para qualquer roteirizador: leve um dia real da sua operação, com as janelas verdadeiras, e compare a rota calculada com a que a equipe praticou. Se o sistema propõe algo que o motorista mais antigo considera absurdo, descubra o motivo. Às vezes falta uma regra no cadastro. Às vezes o hábito é que estava errado.
Entender o problema não exige fórmula. Exige saber que ele é difícil de verdade, que a intuição humana resolve bem os casos pequenos e que, a partir de certo volume, a disciplina do cálculo ganha da memória.
Quer ver o problema resolvido com as paradas da sua operação? Fale com um especialista e leve um dia real de coletas e entregas para a conversa.
