[Talk-br] A importância de não quebrar a hierarquia das vias dentro de cidades.

Paulo Carvalho paulo.r.m.carvalho em gmail.com
Sábado Julho 19 20:56:04 UTC 2014


E qual sua opinião sobre o descarte de vias de baixa prioridade nos
roteamentos de longa distância em ambientes com baixa memória e
processamento mais lento?


Em 19 de julho de 2014 12:58, Fernando Trebien <fernando.trebien em gmail.com>
escreveu:

> Li sim, há bastante tempo. Mas acho que estás confundindo as
> hierarquias do OSM com a hierarquia de atalhos emergente que o
> algoritmo de "contraction hierarchies" produz (que inclusive pode ter
> muito mais níveis do que os poucos que existem no OSM). Os atalhos
> servem apenas para acelerar outro algoritmo de roteamento qualquer
> (geralmente se adota uma variação do Dijkstra, e nesse caso as
> heurísticas acabam preferindo usar os atalhos). E a hierarquia do OSM
> não se converte em atalhos automaticamente. A sequẽncia das coisas é
> assim:
> - cada arco original representa a ligação de duas interseções no mapa
> - o peso dos arcos originais é atribuído por velocidade X distância,
> onde velocidade é uma estimativa feita de forma diferente por cada
> aplicação (algumas usam a classificação da via, outras não)
> - (contraction hierarchies) os arcos de atalho são gerados eliminando
> sequências de arcos cujo peso total é muito alto
> - (contraction hierarchies) um grafo é formado combinando os arcos
> originais com os atalhos
> - um algoritmo de busca em grafos é aplicado sobre o grafo resultante
> (< ou seja, esse algoritmo vai usar tanto atalhos quanto arcos
> originais, possivelmente se intercalando entre os dois)
>
> Por exemplo, se você tiver dois caminhos de A a B com quase a mesma
> distância total, um deles é uma primária com velocidade de 10km/h, e
> outro é uma terciária intercalada com trechos de living_street que, na
> média, fica em torno de 80km/h, vai ser a primária que vai ser
> removida na geração dos atalhos e o segundo caminho (mais rápido,
> embora envolva vias de classificação inferior) que vai virar um
> atalho. O fato de ser primária, secundária, living street, não faz
> diferença alguma a princípio - a menos que exista um programa antes
> (como o mkgmap) que associa a classificação ao peso do arco (mais
> especificamente à velocidade, já que a distância é exata sempre). O
> OSRM, por exemplo, não associa quando a velocidade máxima é definida
> (ou seja, o segundo caso pode acontecer).
>
> Enfim, isso é um detalhe, a classificação tem que estar bem feita por
> diversos motivos, mas (se formos pensar genericamente, para vários
> sistemas) não se pode ignorar o mapeamento da velocidade máxima das
> vias.
>
> 2014-07-19 12:10 GMT-03:00 Paulo Carvalho <paulo.r.m.carvalho em gmail.com>:
> >> Pra esse algoritmo só importa a velocidade atribuída a cada trecho das
> >> vias (e a atribuição pode não ter relação direta com aquilo que foi
> >> mapeado, só indireta).
> >
> >
> > Não é bem assim.  Na graduação se ensina o Djkstra que leva a maioria das
> > pessoas focar apenas no custo de percurso.  Mas uma aplicação real é mais
> > complexa. O tamanho do grafo é um fator de extrema relevância.
> >
> > Acho que tu não leste o artigo sobre Hierarchy Contraction.  Existe uma
> > otimização que é feita nos dispositivos móveis.  Enfim, vou resumir: para
> > rotas de longa distância, em que analisar o grafo todo seria muito
> custoso
> > tanto em termos de desempenho quanto de memória, é feito um descarte de
> vias
> > de baixa hierarquia.  As vias de menor hierarquia só passam a ser
> computadas
> > nas proximidades dos pontos de origem e de destino.  Por causa desse
> > descarte, o cálculo de rotas longas pode falhar em smartphones, tablets e
> > GPSs para mapas mal desenhados.
> >
> >
> >
> >
> >
> > Em 19 de julho de 2014 11:56, Fernando Trebien <
> fernando.trebien em gmail.com>
> > escreveu:
> >
> >> Só acrescentando uns detalhes. Um resumo da ópera: em alguns sistemas,
> >> a classificação pode ter um efeito no roteamento, mas fundamentalmente
> >> o mais importante é mapear as características da via (velocidade
> >> máxima, superfície, etc.).
> >>
> >> Pra esse algoritmo só importa a velocidade atribuída a cada trecho das
> >> vias (e a atribuição pode não ter relação direta com aquilo que foi
> >> mapeado, só indireta). Se não for mapeada a velocidade máxima das
> >> vias, então a maioria dos roteadores tenta "adivinhar" a velocidade a
> >> partir da classificação. Como exemplo, eis aqui [1] como o OSRM faz
> >> essa adivinhação (lembrando que é um serviço mais voltado às
> >> características do trânsito na Europa).
> >>
> >> Então, sim, a classificação é importante para o roteamento caso não
> >> seja mapeada a velocidade máxima. Mas, fundamentalmente, o mais
> >> importante para o roteamento é a velocidade atribuída à via. Existem
> >> casos em que uma primária urbana tem velocidade reduzida num trecho
> >> curto e isso faz diferença pro roteamento decidir mandar o usuário por
> >> ali ou não. Só seria mapear para a aplicação se alguém mudasse a
> >> classificação naquele trecho por causa da velocidade, para forçar um
> >> roteador a evitar o trecho. (Um problema é que muita gente faz isso.)
> >>
> >> Especificamente para o Garmin/mkgmap, parece que ainda existe o
> >> conceito de "classe de velocidade", que não é nem a classificação da
> >> via (que se reflete no desenho), nem a velocidade máxima (que produz
> >> os alertas de velocidade). Essa é uma velocidade estimada de trânsito
> >> que no mkgmap [2] pode ter regras até bem complexas de derivação (nos
> >> exemplos que eu vi por aí o pessoal estava derivando esse campo a
> >> partir de uma combinação da classe da via e da velocidade máxima). Até
> >> daria pra mapear no OSM uma velocidade "esperada" pra via (que então
> >> se traduziria diretamente nessa velocidade do Garmin), mas isso é
> >> complicado de padronizar e por isso pode gerar divergências (e guerras
> >> de edição) e até pode acabar não sendo usado. [3] Algumas abordagens
> >> melhores são coletar a velocidade média [4] e monitorar o tráfego [5].
> >> Com essas duas abordagens, a classificação se torna irrelevante pro
> >> roteamento (por exemplo, no caso de uma primária estar sempre
> >> congestionada e uma secundária paralela estar sempre livre).
> >>
> >> [1]
> >> https://github.com/DennisOSRM/Project-OSRM/blob/master/profiles/car.lua
> >> [2] http://www.mkgmap.org.uk/doc/pdf/style-manual.pdf seção 4.6.5
> >> [3]
> >>
> http://wiki.openstreetmap.org/wiki/Talk:Proposed_features/traffic_speed#Practicality_of_Using_Info_in_Router
> >> [4] http://wiki.openstreetmap.org/wiki/Average_speed_per_way
> >> [5]
> https://lists.openstreetmap.org/pipermail/talk/2012-August/063985.html
> >>
> >> 2014-07-15 8:30 GMT-03:00 Paulo Carvalho <paulo.r.m.carvalho em gmail.com
> >:
> >> > Amigos,
> >> >
> >> >     Para compreender a razão de não quebrar a hierarquia de vias nos
> >> > pequenos trechos que rodovias passam por cidades, recomendo esta
> >> > leitura:
> >> >
> >> > http://en.wikipedia.org/wiki/Contraction_hierarchies
> >> >
> >> >    Aos que já estão com o argumento "isso é mapear para aplicação" na
> >> > ponta
> >> > da língua rogo um momento para parar e pensar:
> >> >
> >> > "For routing software to work well, the underlying map data must be of
> >> > good
> >> > quality. Essentially this means that ways that should be connected are
> >> > in
> >> > fact connected, one-way roads are tagged, turn restrictions are
> mapped,
> >> > and
> >> > so on. You should be familiar with the Map Features used, in
> particular
> >> > see
> >> > OSM tags for routing to understand the tags specific to routing."
> (grifo
> >> > meu)
> >> >
> >> > Palavras da própria comunidade OSM.
> >> >
> >> > Fonte:  http://wiki.openstreetmap.org/wiki/Routing
> >> >
> >> > [ ]s
> >> >
> >> > Paulo
> >> >
> >> > _______________________________________________
> >> > Talk-br mailing list
> >> > Talk-br em openstreetmap.org
> >> > https://lists.openstreetmap.org/listinfo/talk-br
> >> >
> >>
> >>
> >>
> >> --
> >> 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
> >
> >
> >
> > _______________________________________________
> > Talk-br mailing list
> > Talk-br em openstreetmap.org
> > https://lists.openstreetmap.org/listinfo/talk-br
> >
>
>
>
> --
> 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
>
-------------- Próxima Parte ----------
Um anexo em HTML foi limpo...
URL: <http://lists.openstreetmap.org/pipermail/talk-br/attachments/20140719/a01854a8/attachment-0001.html>


Mais detalhes sobre a lista de discussão Talk-br