A otimizacao de rotas e um dos problemas classsicos da ciencia da computacao aplicada a logistica. Apps como iFood, Uber Eats, Rappi e James processa milhoes de pedidos diariamente, e a qualidade do algoritmo de roteirizacao impacta diretamente o tempo de entrega, a satisfacao do cliente e a rentabilidade da operacao. Este artigo explica como funciona.
O problema do caixeiro viajante (TSP)
A roteirizacao na sua forma mais basica e o “Travelling Salesman Problem” (TSP): dado um conjunto de pontos geograficos, encontre o caminho mais curto que visita todos os pontos e retorna ao ponto de origem.
O TSP e NP-hard — nao existe algoritmo polinomial conhecido que resolva o problema otimamente para grandes instancias. Para N pontos, a solucao exata exigiria testar N! permutacoes (uma entregadora com 20 pedidos teria 2.4 quintilhoes de opcoes para verificar).
Na pratica, algoritmos de aproximacao e heuristicas sao usados para encontrar solucoes boas (nao necessariamente otimas) em tempo computacional viavel.
Algoritmos usados na pratica
Nearest Neighbor Heuristic
O algoritmo mais simples: a partir do ponto atual, sempre va para o ponto mais proximo ainda nao visitado. Simples de implementar, rapido de executar, mas produz solucoes 20-25% piores que o otimo em media.
2-opt e 3-opt
Melhorias iterativas sobre uma rota inicial: 2-opt testa todas as trocas de dois segmentos de rota e aceita trocas que reduzam a distancia total. Repetido ate nao haver mais melhorias. Na pratica, produz solucoes muito boas para instancias de ate algumas centenas de pontos.
Algoritmos geneticos e simulated annealing
Metaheuristicas que exploram o espaco de solucoes de forma mais global, escapando de otimos locais. Mais lentos que 2-opt mas produzem solucoes melhores para instancias maiores.
OR-Tools (Google)
Para projetos reais, a biblioteca open source OR-Tools do Google oferece solvers de VRP (Vehicle Routing Problem, a versao generalizada do TSP com multiplos veiculos e restricoes) que superam implementacoes customizadas na maioria dos casos.
Exemplo de uso com Python:
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywraprouting
def roteirizar_pedidos(pontos, deposito_idx=0):
manager = pywraprouting.RoutingIndexManager(len(pontos), 1, deposito_idx)
routing = pywraprouting.RoutingModel(manager)
def distancia_callback(from_index, to_index):
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return calcular_distancia(pontos[from_node], pontos[to_node])
transit_callback_index = routing.RegisterTransitCallback(distancia_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
search_params = pywraprouting.DefaultRoutingSearchParameters()
search_params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
solution = routing.SolveWithParameters(search_params)
return extrair_rota(manager, routing, solution)
Fatores reais alem da distancia
Em sistemas de delivery reais, otimizar so distancia nao e suficiente. Variaveis adicionais:
Tempo (nao so distancia): transito em tempo real via Google Maps API ou HERE Maps muda o tempo estimado de cada segmento dinamicamente.
Janelas de tempo: cada pedido tem um prazo de entrega. A restricao de janela de tempo torna o problema muito mais complexo (VRPTW — VRP with Time Windows).
Capacidade do entregador: um entregador de moto tem capacidade limitada de pedidos simultaneos. O algoritmo precisa respeitar isso alocando pedidos por capacidade.
Agrupamento geografico: pedidos proximos sao agrupados e alocados para o entregador mais proximo naquele cluster.
Matching em tempo real: o algoritmo de despacho
Um problema separado do roteamento e o matching: dado um novo pedido, qual entregador disponivel deve recebe-lo?
As variaveis consideradas: distancia do entregador ao restaurante, tempo estimado de preparo do pedido pelo restaurante (para nao deixar entregador esperando muito), avaliacao do entregador, taxa de aceitacao (entregadores que recusam muito perdem prioridade), e se o entregador ja tem outro pedido e pode realizar batching (dois pedidos na mesma rota).
O algoritmo de matching e um problema de alocacao que plataformas como Uber resolvem com modelos de programacao linear e machine learning treinado com historico de entregas.
Tem um projeto em mente?
Somos especialistas em transformar ideias em produtos digitais. Apps, sites, automações e IA — vamos construir juntos.
