Imagine que você pede um Uber ou qualquer outro aplicativo de corridas. O aplicativo diz que o motorista chegará em 5 minutos. Mas como ele sabe disso? Na verdade, a Uber usa um sistema extremamente sofisticado, combinando matemática, grafos, algoritmos inteligentes e aprendizado de máquina para prever o tempo de chegada. E tudo isso acontece em milissegundos!
Pense no trânsito como um grande tabuleiro de jogo, onde cada rua é uma peça conectada a outras. A Uber precisa descobrir o caminho mais rápido para o carro chegar até você e calcular quanto tempo isso levará. Mas esse caminho muda o tempo todo! Tem trânsito? Semáforos? Obras?
Neste artigo, vamos entender passo a passo como a Uber faz essa mágica e como você pode usar essas ideias em seus próprios projetos!
Primeiro, um resumo
Antes de entrarmos no detalhe de cada coisa, vou resumir aqui alguns passos de como a Uber faz isso e a partir daí, entramos um pouco mais no detalhe de cada etapa.
Primeiro, imagine o mapa como um Grafo: Cada rua é uma aresta, e cada interseção é um nó. Tudo aqui é um grafo e não mais um mapa.
Segundo, agora começa a busca pelo Caminho Mais Curto: O sistema encontra a rota mais rápida em um grafo direcionado e ponderado. O ShortestPath é um termo famoso na matemática que consiste na minimização do custo de travessia de um grafo entre dois nós (ou vértices); custo este dado pela soma dos pesos de cada aresta percorrida.
Dijkstra? Não! O Dijkstra é eficiente, mas não escala bem, então a Uber usa algoritmos otimizados. Não sabe o que é (quem) Dijkstra, isso fica para outro artigo, mas resumidamente é um dos algoritmos de busca de menor caminho mais famosos. Todo o começo de navegação de GPS utilizava Dijkstra no começo.
Particionamento do Grafo: O mapa é dividido em regiões menores, e os melhores caminhos dentro delas são pré-calculados. E aqui precisamos começar a separar o “padrão de mercado” para o “padrão Uber”, porque a partir do momento que a Uber começou a particionar o grafo em pequenas partes, o cálculo da rota se tornou muito eficiente!
Redução da Complexidade: De O(n²) para O(n) ao limitar a busca apenas à região relevante. Isso aqui parece óbvio, mas não é. Com o particionamento do grafo a Uber só calcula a rota para aquele pedacinho de mapa ao invés de olhar vários outras coisas que não fazem sentido para aquela corrida. Porque assim, o recorte é muito mais “certeiro” e menor para ser calculado.
Agora, um ajuste Dinâmico com Tráfego: O sistema atualiza os pesos das ruas com base em congestionamentos e dados históricos.
Após a rota traçada, se usa Map Matching que corrige a posição do GPS para alinhar corretamente o carro à via. Lembra que no começo as vezes motoristas que estavam em direção oposta a nossa aceitavam corridas e depois precisavam fazer grandes retornos e aquela estimativa de 2 minutos se transformava em 10? É justamente isso aqui que a Uber tenta corrigir.
E por último, mas não menos importante… precisamos lembrar que o GPS não é perfeito. Ele pode ter erros devido a interferências, reflexos em prédios ou baixa qualidade do sinal. Isso pode fazer com que um carro apareça em uma rua errada ou mesmo “pule” de um ponto para outro de forma não natural. Para corrigir isso, a Uber usa dois algoritmos matemáticos poderosos: Filtro de Kalman e Algoritmo de Viterbi para melhorar a precisão do GPS.
Filtro de Kalman: Prevendo a Próxima Posição
O Filtro de Kalman é um algoritmo estatístico que prevê a próxima posição de um objeto com base no movimento passado. Como funciona?
- Recebe a posição atual do GPS (com ruído e imprecisões).
- Compara com a posição anterior e calcula uma previsão corrigida.
- Ajusta continuamente a posição do carro, suavizando erros.
Exemplo prático:
Se o GPS diz que o carro está 20 metros fora da rua, mas ele estava seguindo uma trajetória estável, o Filtro de Kalman assume que a posição errada é um erro e a ajusta para a rua correta.
- Melhora a suavidade do movimento no mapa.
- Ajuda a prever onde o carro estará no próximo instante.
- Evita “saltos” abruptos na posição.
Bom, com isso acredito que já temos um resumo (mas poderoso) de como é o cálculo de rotas da Uber. Vamos agora aos detalhes:
Disclaimer: Eu não sou funcionário da Uber e todas as informações são com base do que encontro na internet e abaixo vou citar algumas ferramentas em que você pode estudar, mas isso não significa que a Uber utiliza as exatas ferramentas e/ou métodos, combinado?
1. Representação do Mapa como um Grafo
A Uber representa mapas físicos como grafos direcionados e ponderados. Cada interseção de ruas é um nó, enquanto as ruas são arestas com pesos associados, que podem representar distância, tempo de viagem ou outros fatores. Se você não está familiarizado com grafos, pense neles como uma forma de modelar caminhos e conexões:
- Peso: O custo de percorrer aquela rua (ex.: distância, tempo estimado, tráfego).
- Nó: Um ponto no mapa (ex.: cruzamento, semáforo, ponto de interesse).
- Aresta: A conexão entre dois nós (ex.: ruas, rodovias, túneis).
Ferramentas e Tecnologias:
- NetworkX (Python): Biblioteca para modelagem de grafos.
- GraphX (Apache Spark): Processamento de grafos distribuídos para grandes conjuntos de dados.
- OpenStreetMap (OSM): Fonte de dados geoespaciais para construção de grafos viários.
2. Cálculo da Rota Ótima
Para calcular o ETA, a Uber busca encontrar o caminho mais curto entre o ponto de origem e o destino final dentro do grafo viário.
Técnicas utilizadas:
- Grafo Direcionado e Ponderado: O tráfego influencia o peso das arestas.
- Não usam o Algoritmo de Dijkstra: Dijkstra possui complexidade O(n log n), tornando-se ineficiente em grafos muito grandes como redes de tráfego urbano.
- Uso de Algoritmos de Caminho Mais Curto Escaláveis: A Uber usa métodos mais eficientes, como A* e variantes otimizadas.
Ferramentas:
- Boost Graph Library (BGL): Implementação de algoritmos de grafos otimizados.
- Google OR-Tools: Conjunto de bibliotecas para otimização de rotas.
- GraphHopper: Motor de roteamento baseado em OpenStreetMap.
3. Particionamento do Grafo e Pré-Cálculo de Rotas
Para melhorar a escalabilidade, a Uber particiona o grafo em regiões menores e pré-calcula os melhores caminhos dentro de cada partição.
Vantagens dessa abordagem:
- Redução da complexidade: De O(n²) para O(n), pois reduz o espaço de busca do caminho ótimo.
- Maior eficiência: As buscas são feitas dentro de partições menores em vez de percorrer o grafo inteiro.
Técnicas e Algoritmos Utilizados:
- Contraction Hierarchies (CH): Reduz a busca para áreas mais relevantes.
- ALT (A* com Landmarks): Adiciona pontos de referência para acelerar buscas.
- Bidirectional Search: Executa buscas a partir da origem e destino simultaneamente.
Ferramentas:
- PGRouting: Extensão do PostgreSQL para cálculos de roteamento.
- igraph (Python, R, C): Biblioteca para análise e manipulação de grafos complexos.
4. Uso de Dados de Tráfego para Ajustar Pesos
O ETA não pode ser calculado apenas com base na distância. O tráfego influencia diretamente o tempo de deslocamento. A Uber atualiza os pesos das arestas do grafo utilizando informações em tempo real.
Fontes de dados de tráfego:
- Sensores e APIs externas: Google Maps Traffic, Waze, HERE.
- Histórico de viagens: Dados agregados de usuários da própria Uber.
- Machine Learning: Modelos que preveem padrões de congestionamento.
Ferramentas e Modelos:
- Apache Kafka: Para ingestão em tempo real de dados de tráfego.
- TensorFlow & PyTorch: Modelos de previsão de tráfego baseados em aprendizado de máquina.
5. Map Matching para Melhorar a Precisão
A posição reportada por GPS nem sempre corresponde exatamente a uma rua no grafo viário. Para corrigir isso, a Uber usa Map Matching, que ajusta a posição do veículo ao mapa mais próximo.
Algoritmos utilizados:
- Filtro de Kalman: Usa medidas passadas para suavizar a posição e prever movimentos futuros.
- Algoritmo de Viterbi: Usa aprendizado estatístico para escolher a melhor sequência de ruas correspondentes aos pontos de GPS.
Ferramentas:
- OSRM (Open Source Routing Machine): Implementa algoritmos de Map Matching.
- Valhalla (Mapbox): API para correção e roteamento geoespacial.
6. Fluxo Completo do Cálculo do ETA
- Recebimento de um pedido de viagem.
- Map Matching: Ajusta a posição do motorista e passageiro no grafo viário.
- Consulta ao Grafo: Encontra a melhor rota usando algoritmos otimizados (A*, ALT, CH).
- Ajuste de Pesos: Modifica o grafo em tempo real com base no tráfego.
- Cálculo do ETA: Tempo estimado baseado em velocidade, distância e condições de tráfego.
- Resposta para o usuário: O tempo de chegada é exibido no aplicativo.
Conclusão
A Uber usa uma combinação de algoritmos de grafos, técnicas estatísticas e aprendizado de máquina para calcular o ETA com alta precisão. O uso de particionamento de grafos, pesos dinâmicos e Map Matching permite estimativas rápidas e escaláveis. Incrível como algo que parece simples para o usuário, não é nem de perto aos olhos de um programador, não é mesmo?
Quer desenvolver sistemas similares? Explore estas tecnologias e implemente soluções otimizadas para roteamento e previsão!
