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 <[email protected]> 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 <[email protected]>: > >> 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 < > [email protected]> > > 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 <[email protected] > >: > >> > 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 > >> > [email protected] > >> > https://lists.openstreetmap.org/listinfo/talk-br > >> > > >> > >> > >> > >> -- > >> Fernando Trebien > >> +55 (51) 9962-5409 > >> > >> "Nullius in verba." > >> > >> _______________________________________________ > >> Talk-br mailing list > >> [email protected] > >> https://lists.openstreetmap.org/listinfo/talk-br > > > > > > > > _______________________________________________ > > Talk-br mailing list > > [email protected] > > https://lists.openstreetmap.org/listinfo/talk-br > > > > > > -- > Fernando Trebien > +55 (51) 9962-5409 > > "Nullius in verba." > > _______________________________________________ > Talk-br mailing list > [email protected] > https://lists.openstreetmap.org/listinfo/talk-br >
_______________________________________________ Talk-br mailing list [email protected] https://lists.openstreetmap.org/listinfo/talk-br
