[Talk-br] Necessidade de intermediação

[Marcio - Thundercel]

Uma coisa é o esperado de acordo com a teoria e outra o observado na pratica 
em exaustivos testes.

> A criação do nó em si não interfere, a princípio, com o algoritmo.
> Será um nó a mais a ser visitado enquanto o grafo é explorado pelo
> algoritmo de roteamento.

O algoritmo, dentre outros, trata os nós e é por eles que ele traça a rota.

Já fizemos inúmeros testes de roteamento e identificamos que o roteamento, 
entre duas vias iguais, ele opta pela que tem menos nós.

Faça o teste chegando em um nó onde se abrem duas vias e que se fecham lá na 
frente, como um losango.
Divida um segmento de reta de uma das vias inserindo um nó nela.
Identificará que o roteamento se dá pela via que não tem o nó inserido.
Foi assim que nos testes constatamos a influência de partições de via em um 
roteamento.

-----Mensagem Original----- 
From: Fernando Trebien
Sent: Sunday, July 5, 2015 4:52 AM
To: OpenStreetMap no Brasil
Subject: Re: [Talk-br] Necessidade de intermediação

2015-07-05 1:40 GMT-03:00 Marcio - Thundercel <thundercel em gpsinfo.com.br>:
> Por outro lado lembro que classificação de vias e de velocidades 
> interferem
> no roteamento e, infelizmente, não dominamos ainda o algoritmo garmin. O 
> que
> sabemos sobre ele advém de exaustivos testes realizados.
> Não estamos debatendo tempo e sim roteamento e tudo que interfere nele.
> Como bem deve saber você o roteamento leva em consideração, além de 
> outros,
> a quantidade de nós empregados para unir os segmentos de reta na 
> retratação
> da via.
> Ao se reduzir a velocidade de um trecho de via o editor é obrigado a 
> dividir
> a via de forma a poder no trecho dividido estabelecer a velocidade. Isso 
> por
> si só já afeta o calculo de rota por aquele trecho.

Afeta, mas muito pouco, pelo menos na minha compreensão de algoritmos
de roteamento.

O que acontece é que ele cria um novo nó no grafo de roteamento para
representar o trecho. O nó contem o tempo total para percorrer o
trecho, calculado dividindo distância por velocidade. (há variações em
que o nó contem ambas velocidade e distância e o cálculo do tempo é
feito durante o processamento, mas elas são matematicamente
equivalentes)

A criação do nó em si não interfere, a princípio, com o algoritmo.
Será um nó a mais a ser visitado enquanto o grafo é explorado pelo
algoritmo de roteamento.

O que acontece é que algoritmos diferentes usam heurísticas
diferentes. Algumas dessas heurísticas decidem "descartar" alguns nós
que eles "acham" que têm pouca chance de conduzir à melhor rota.
"Heurística" é um método matematicamente impreciso para chegar a uma
solução sub-ótima mais rapidamente. Se é impreciso, há heurísticas
melhores e piores. Uma heurística comum é visitar primeiro os nós
relativos às vias de maior classificação. Nesse caso, como a
classificação não foi alterada, o nó seria visitado mesmo tendo uma
velocidade mais baixa. Mas o Garmin pode usar alguma outra heurística
que eu desconheço.

Outro insight: explorar o gráfico requer somar esses tempos, trecho
por trecho. São milhares de operação de soma. Se o programa não for
bem construído, ele pode acumular erros numéricos ao somar milhares de
números. O OSRM me parece particularmente sensível a esses erros. O
Garmin geralmente opera num hardware limitado e talvez também seja
sensível (tratar desses erros numéricos requer usar mais memória).

Mais um insight: classificação interfere com esses algoritmos "mais
simples" que usam "heurísticas". A classificação das vias não
interfere em nada com o algoritmo A* (a-estrela) puro, nem com o
algoritmo do OSRM. Por isso, classificações não devem ser alteradas
com vistas ao roteamento. No entanto, um bom método de classificação
serve bem a praticamente qualquer algoritmo de roteamento, não por ser
o objetivo da classificação, mas por ser efeito colateral dela.

Se, numa rota com vários quilômetros, a escolha de uma alternativa ou
outra depender de um trecho tão curto quanto o mencionado, é bem
provável que alguma dessas características esteja inteferindo no
resultado. Mas os mapeadores do OSM não podem fazer nada, e talvez nem
os desenvolvedores da aplicação sem ter que reescrevê-la por completo
para resolver algum problema mais profundo.

O que os roteadores prometem não é encontrar a melhor rota, mas uma
rota sub-ótima. Quanto mais longa a distância, maior o efeito desses
dois fatores (erro numérico e qualidade da heurística). Até mesmo o
Waze às vezes faz bobagem na tentativa de encontrar a melhor rota.

-- 
Fernando Trebien
+55 (51) 9962-5409

"Nullius in verba."

_______________________________________________
Talk-br mailing list
Talk-br em openstreetmap.org
https://lists.openstreetmap.org/listinfo/talk-br