Como o Waze encontra o caminho mais curto ou mais rápido?

O Waze encontra o caminho mais curto ou o mais rápido entre dois pontos usando diversos recursos. Ele combina dados dos usuários em tempo real e informações do trânsito com algoritmos e princípios matemáticos, sem os quais ele não funcionaria.

Como o Waze encontra o caminho mais curto?

O Waze utiliza dados enviados em tempo real pelos celulares dos usuários, para encontra o caminho mais curto entre dois pontos ao sugerir uma rota. Ele aplica essas informações utilizando dois elementos principais: a Teoria dos Grafos e o Algoritmo A*.

O que é Teoria dos Grafos?

A Teoria dos Grafos é um ramo da Matemática que estuda relações entre elementos de um conjunto. Ela foi estabelecida pelo matemático Leonhard Euler em 1736, ao apresentar uma resolução para o problema das 7 Pontes de Königsberg: na época, a cidade (hoje Kaliningrado, Rússia) era cortada pelo rio Pérgola, dividindo a região em duas áreas continentais e duas ilhas no meio do rio, todas ligadas pelas pontes.

A proposta do problema era encontrar um meio de cruzar todas as sete pontes, passando apenas uma vez por cada uma. Euler demonstrou que não havia uma solução possível criando um diagrama, transformando as pontes em linhas e as porções da cidade em pontos. Este é considerado o primeiro grafo da história.

O grafo de Euler abriu um ramo que permite estudar ligações entre elementos de diversas maneiras; na Topologia, ele permite estudar rotas possíveis (as arestas) entre os pontos de origem/destino (os vértices, ou nós). Um grafo pode atribuir pesos (valores) às arestas e nós, enquanto as primeiras também podem ter uma direção. Neste caso, o grafo é chamado de dígrafo, grafo direcionado ou também quiver.

O que é Algoritmo A*?

Em um mapa, os nós são os pontos de origem e destino de uma rota, enquanto as arestas são as rotas possíveis. Para o Waze descobrir qual o melhor caminho, ele atribui pesos a cada uma das rotas, tendo como base informações recebidas em tempo real, tanto dos usuários quanto dos órgãos de trânsito e outras fontes.

O peso determina o tempo levado para concluir o trajeto, se mais ou menos demorado, e é aqui que entra o Algoritmo A* (lê-se “A estrela”), uma extensão do Algoritmo de Djikstra para o problema do caminho mais curto. Ele é um algoritmo de busca baseado em grafos com pesos, dedicado a encontrar o menor caminho possível entre dois pontos com o menor custo, que mantém todas as rotas armazenadas. Por isso é o mais usado em soluções computacionais para rotas.

Funciona assim: quanto maior o peso de uma aresta (rota), maior o tempo levado para percorrê-la. O A* analisa os caminhos possíveis, faz uma soma dos pesos das rotas e retorna a melhor rota, considerando distância e tempo. O nó seguinte (o ponto final de uma aresta, ou rota; no caso uma rua, avenida, etc.) é escolhido dada sua proximidade do nó de destino e peso.

No exemplo abaixo, o algoritmo A* analisa rotas possíveis para o ponto de destino, considerando o obstáculo encontrado. Quanto mais verde, mais distante da origem.

Lembre-se, o caminho que o Waze retorna não necessariamente é o menor, pois ele prioriza o que será percorrido em menor tempo. O aplicativo considera variáveis como velocidade média das vias, horário do dia (o que influi na quantidade de veículos), rodízio vigente ou não, acidentes, redução de velocidade em curvas e etc.

Mais importante, as informações sobre rotas e o peso atribuído a elas pode e irá variar durante o dia, por isso o Waze pode recomendar rotas diferentes a duas ou mais pessoas partindo do mesmo ponto rumo a um destino comum, mas em horários diferentes.

Com informações: Wazeopedia

Receba mais sobre Waze na sua caixa de entrada

E-mail:

* ao se inscrever você aceita a nossa política de privacidade