Servidor de Rotas

De Wazeopedia

(Redirecionado de Routing server)

Ao utilizar o aplicativo Waze, os servidores do Waze usam algoritmos de roteamento para determinar a melhor rota para um dterminado destino naquele momento. Os detalhes de implementação do algoritmo de roteamento utilizado pelo Waze não são divulgados publicamente e as seguintes informações são baseadas em observações, especulação e alguns detalhes informados pelo staff do Waze. A operação do servidor de roteamento é considerada proprietaria e uma vantagem competitiva do Waze. Também é assumido que pode haver mudanças e que qualquer informação descoberta pode estar incompleta ou desatualizada.

Roteamento no aplicativo do usuário

Calcular a melhor rota é uma tarefa dificil, o aplicativo Waze possui um algoritmo interno de calculo de rota, no entanto este só é utilizado se não houver conexão com o servidor do Waze.

Pedidos de Roteamento

Quando você pede uma rota para o destino o pedido é enviado para o servidor do Waze. A rota calculada pelo servidor é enviada de volta para o dispositivo cliente e exibida.

Os pedidos de roteamento são diferenciados pelas configurações escolhidas no seu dispositivo. No menu de Navegação você pode escolher:

  • Rota mais rapida ou mais curta
  • Permitir ou evitar pedagios
  • Permitir ruas sem calçamento, não permitir ruas sem calçamento ou permitir ruas sem calçamento curtas
  • Evitar rodovias

A rota mais curta se refere a distância fisica. A maior parte das pessoas preferem a rota mais rapida, 100km em rodovias é melhor que 90 km em ruas.

Ruas faltando e Conexões incorretas em junções

Waze tenta encontrar a melhor rota entre você e seu destino baseado nas configurações de navegação, Obviamente só é possivel rotear por ruas que estejam registradas nos servidores do Waze, então pode existir uma rota melhor que não será escolhida por ruas estarem faltando ou junções serem incorretas, para corrigir estas faltas/erros utilize o Editor de Mapas (WME). Observe também que se [[Segment length|segments segmentos tiverem um comprimento menor que o minimo Segment length/Minimum]], pode haver erros de roteamento.

Velocidade de ruas em tempo real

O servidor de roteamento utiliza velocidades de ruas em tempo real (de usuários recentes do Waze se estiverem disponiveis) e os combina com velocidades historicas de cada segmento em periodos de 10 a 15 minutos. O tempo para percorrer cada segmento é monitorando separadamente para cada destino saindo do segmento. Por exemplo se um segmento tem uma curva a esquerda e uma a direita, então o servidor de roteamento armazena o tempo para percorrer o segmento virando a esquerda no fim e o tempo para percorrer o segmento virando a direita no fim. Estas informações detalhadas são proprietarias e parte dos dados vendidos ou planejados para ser vendidos pelo Waze e não serão vistos no editor de mapas.

Sabemos que o Waze utiliza dados de tempo real da velocidade das ruas em preferência aos dados historicos. Waze também utiliza dados de engarrafamento enviados pelos dispostivo dos usuários para rotear outros usuários desviando de transito lento. É assumido que a velocidade de um Wazer adiante de você será utilizado para calculos de roteamento.

A medida que o número e densidade de Wazers cresce, os dados de tempo real se tornam mais relevantes. A importancia destes dados existe devido ao objetivo inicial do Waze que é criar rotas ótimas. Como o Waze passou a ser utilizado como um GPS generico os dados historicos se tornaram mais importantes em ruas pouco trafegadas.

O algoritmo do Waze utiliza o tempo estimado para percorrer um segmento baseado na velocidade e comprimneto de cada segmento, então ele não pode usar dados de tempo real quando os segmentos estiverem a mais de 15 a 30 minutos da posição inicial. Para estes segmentos o Waze aguarda chegar neles e então faz um novo cálculo de rota exibindo o novo Horário Estimado de Chegada e verifica se existe uma rota melhor segundo as configurações do usuário.

Roteamento mais Rápido

O Waze sabe a velocidade média de cada segmento confirmado entre você e seu destino. O servidor Waze pode calcular qual sequencia de ruas utilizar para minimizar o tempo de percurso

Todos os pedidos de rota são processados em tempo real, no entanto foi observado que Waze memoriza algumas rotas ou rotas entre dois pontos. Isto quer dizer que se o servidor já conhece a melhor rota do ponto B para o ponto C e você pede a rota do ponto A para ponto C passando por B, então o servidor apenas calulca a rota entre A e B, também são calculadas rotas desviando de B para obter a rota mais rápida. No entanto, quando houver uma atualização do mapa algumas rotas podem não ser as mais eficientes enquanto o Waze recalcula e armazena as novas rotas.

A rota mais eficiente tem calculo complexo, a complexidade é relacionada as velocidades médias dos segmentos.

Mudanças na rota devido a mudança na origem

Considere uma rota de A para Z, a rota sugerida pode ser de A para B para C para D para Z. Posteriormente calcule a rota de B para Z, a rota calculada poderá ser de B para C para E para Z. Em um primeiro momento pode parecer que parde da primeira rota não era a melhor ao mudar a origem.

A diferença no resultado pode ter diversas razões, pode ser algo relacionado ao armazenamento de rotas no servidor, ou pode haver uma diferença devido aos cálculos em momentos diferentes, ou pode haver dados de tempo real diferentes, ou pode ter sido algum fator limitante no algoritmo de rotas que não foi excedido no caminho menor.

Este efeito pode ser observado se ao dirigir com uma rota calculada você solicitar uma nova rota para o mesmo destino, é possivel que a rota mais eficiente seja alterada.

Algumas vezes o Waze oferecerá rotas alternativas para desviar de transito pesado.

Mudanças em rotas devido a comprimentos distintos

O servidor Waze não tem a capacidade de calcular todas as possiveis rotas em rotas de longa distância, então ele usa otimizações para rotas mais longas, ao aumentar um pouco a rota pode haver resultados consideravelmente distintos. De acordo com o suporte do Waze, seções de uma rota entre pontos com mais de 10 km de distância irão evitar rotas por ruas (utilizando Rua Primarias ou Rodovias). O servidor de rotas ignora totalmente ruas fora desse área de 10 km.

Problemas com velocidades médias

Se a velocidade média do segmento não estiver correta, a rota calculada não será a ideal. No entanto, não é recomendado remover segmentos e readiciona-los para eliminar as velocidades médias daquele segmento. Waze utiliza dados dos Wazers atravessando cada segmento para atualizar a velocidade média do segmento. Se você suspeita que o Waze não está utilizando um determinado segmento é necessário verificar qual a razão especifica, cada caso tem explicação diferente. Não assuma que remover o segmento soluiconará o problema.

As seguintes razões explicam porque o mecanismo de calculo de rotas pode não utilizar a velocidade média do segmento;

Variações por hora do dia

Considere uma rua que Wazers dirigem as 17h00 a uma velocidade média de 20 Km/h. Se você escolher um rota as 10h00 a velocidade média nessa rua pode ser de 100 km/h. Essa é a melhor opção, mas devido ao Waze não ter informações deste horário ele pode sugerir uma rota alternativa por supor que a velocidade média da rua é de 20 Km/h o dia todo.

Obviamente você pode dirigir por esta rua melhor e posteriormente o Waze irá aprender a velocidade média para aquele horário. Não sabemos quanto tempo o servidor do waze armazena os dados para calcular a velocidade média. No entanto, se o ritmo de remoção de velocidades médias antigas não for rapido o suficiente, poderá haver uma demora para a rota ser escolhida. É possivel também que o servidor considere a sua velocidade como sendo anormal e a ignore.

Quanto mais Wazers trafegarem por um segmento, mais rápido será solucionado este problema.

Atraso devido a curva

Em um segmento de uma rua a velocidade media depende do que você faz no fim dele, trafego indo reto pode passar rapidamente pelo cruzamento enquanto trafego virando a esquerda ou direita pode esperar bastante. Em uma rodovia veiculos saindo dela podem andar rapido enquanto veiculas que continuam na rodovia andam lentamente
SegmentTraffic1.png
Waze tem a habilidade de armazenar dados diferentes dependendo do que acontece após passar pelo fim do segmento. O servidor de rotas considera essas diferenças, no diagrama multiplos tempos são rastreados na condução pelo segmento 4 dependendo de qual segmento seguinte é utilizado. Existem então duas velocidades médias:
  • Seg4 para Jnct2 para Seg5
  • Seg4 para Jnct2 para Seg6

Trafego sendo criado no Segmento 4 devido a um atraso para entrar no Segmento 6 não irá afetar tempo de rota em rotas que usem o Segmento 4 para ir ao Segmento 5. Por isso é necessário utilizar segmentos longos antes de junções para que o servidor de rotas consiga perceber essas diferenças.

Para entender melhor essa necessidade, suponha que um pequeno segmento de número 8 seja adicionado entre o Segmento 7 e a Junção 4. Se o transito no segmento 10 acumular e for até o Segmento 7 (devido ao segmento 8 ser curto) . Devido ao Segmento 7 ter apenas uma saida para o Segmento 8, o servidor de roteamento passa a ter apenas uma velocidade média entre os Segmentos 7 e 8 e não poderá distinguir a partir do 7 a diferença nas curvas no segmento 8. Para o servidor Waze trafego indo do Segmento 7 para o 9 irá diminuir de velocidade e ele não saberá por que. Isto pode causar erros no Horário Estimado de Chegada ou rotas completamente distintas.

Este tipo de informaçõ não está disponivel no Editor de Mapas do Waze (WME), é visto apenas no servidor de roteamento.

Sinais de transito e placas de parada

Waze não armazena a localização de sinais de transito, alguns aplicativos de GPS utilizam navegação por voz com instruções do tipo "Vire a direita no próximo sinal", esse tipo de informação frequentemente se torna desatualizado, incorreto ou incompleto. O consenso no Waze é que a localização dos sinais não devem ser armazenados.

Waze considera a localização dos sinais e placas de pare no efeito que eles tem sobre a velocidade do segmento. Sendo um sinal com longos tempos de espera o segmento com este sinal terá velocidades médias baixas, se o tempo se torna excessivamente longo Waze irá escolher uma outra rota que evite este sinal. Este comportamento foi observado experimentalmente como um comportamento adquirido, Waze não é programado para evitar sinais, ele é programado para evitar rotas lentas.

Alguns motoristas preferem rotas mais longas (até com curvas fechadas em ruas paralelas) para evitar sinais e placas de pare. Waze pode sugerir estas rotas e pode também voltar a sugerir as rotas com sinais e places de pare se a informação coletada no caminho alternativo for pior.

Velocidades desatualizadas ou anormais

Condições das ruas mudam, uma construção na via pode se iniciar e terminar, por isso a velocidade média pode ser alterada significamente. Um dia você pode estar preso atras de um caminhão lento, no outro preso em um engarrafamento as 2 da manhã. ou seu GPS pode ter um defeito e reportar você transitando a uma velocidade de 1000 Km/h.

Em resumo, velocidades médias mudam ao longo do tempo, essas velocidades armazenadas podem ser anormais ou simplesmente erradas, elas podem ficar erradas por algum tempo.

O Waze tem conhecimento destes problemas, há evidência que velocidades anormais e dados antigos são apagados ou pelo menos ignorados pelo servidor de calculo de rotas.

"Janela flexivel" de velocidade média

Se houver uma quantidade grande de velocidades médias em um segmento, o Waze irá diminuir a janela temporal de medidas de velocidade média para ter uma estimativa melhor para calculo de roteamento. A janela temporal pode ter um intervalo equivalente a 30 minutos, então um segmento com dois sentidos pode ter até 96 medidas de velocidade média. Quanto não há dados suficientes, a janela temporal pode ser de até 24 horas. A medida que mais motoristas trafegam pelo segmento a janela vai diminuindo.

Podemos também supor que outros dados são utilizados, como o dia da semana, por exemplo ruas tem mais transito durante a semana que em finais de semana.

Em algum momento o Waze terá que considerar as estações do ano, já que estes tem grande influência em alguns locais.

Waze utiliza a velocidade média do segmento no horário em que a sua chegada nele é prevista.

Devido as janelas de tempo, Waze irá sugerir rotas distintas durante o passar do dia. Isto irá depender na quantidade de janelas de tempo armazenadas no segmento. Se todas as medições ocorrerem no mesmo horário, então a janela não irá ajudar, se mil medições forem feitas as 17h e apenas 2 medições as 2 da mnhã, então a velocidade utilizada as 10 da manhã será a média das velocidades medidas as 17h.

Refinamentos do algoritmo de rotas

Opções de Rota

É fácil perceber como opções de roteamento pode ser implementadas, por exemplo para minimizar curvas podemos adicionar penalidades para cada curva se quisermos a rota mais rapida ou penalidades devido a distância para rotas mais longas.

Penalidades de junção

Para novas ruas Waze aplica uma penalidade de 5 segundos para cada junção que a rota atravessa. Uma vez que motoristas circulam por estas novas vias as penalidades são removidas

O que fazer se você acha que a rota gerada está errada

Primeiro, use a opção para gerar rotas alternativas. Isto poderá lhe dar aluma idéia de porque Waze ofereceu aquela rota.

Segundo, se você acha que existe uma rota melhor, verifique no WME se os segmentos na rota estão todos conectados.

Terceiro, poste uma mensagem detalhando o erro na rota, origem, destino e permalink do WME no fórum. Outras pessoas irão verificar e você realmente poderá ter descoberto uma falha no algoritmo de roteamento do Waze. Consertar esse erro fará o sistema melhor para todos.

Mudança na rota

Quando o Waze recebe informações de transito de outros Wazers o sistema utiliza a velocidade real das ruas na sua rota, ao invés de usar as velocidades médias. O sistema utiliza apenas informações recebidas automaticamente pelo sistema como transito lento, moderado, pesado ou completamente parado. Avisos de transito ou acidentes são apenas informativos e não mofidicam o roteamento.

Mesmo recebendo todas essas informações, Waze pode não ter uma rota melhor para sugerir.

Você é o motorista

Waze não pode ver se o sinal está verde ou se hoje é um feriado, ele pode te oferecer informações sobre qual a melhor rota sob as condições médias da via, mas você é o motorista e está na melhor posição para decidir que rota utilizar baseado nas condições vistas no momento de dirigir.

Se todos os motoristas seguissem as instruções do Waze o sistema nunca teria conhecimento de rotas melhores. Quando o Waze armazena informações das suas viagens, cada viagem ajuda a fazer o Waze melhor para todos. Isso inclui as viagens que você faz achando ser melhores que as sugeridas pelo Waze. Algumas vezes você estará certo e outras errado. Mas é melhor escolher a rota que você acha melhor, assim todos serão beneficiados por essa escolha.