Sabendo que há trabalhos cientificos publicados descrevendo bons algoritmos para esses ambientes e que não descartam quaisquer vias (mesmo as de classe bem inferior), acho que não devemos fazer adaptações no mapa em favor de algoritmos menos inteligentes. (Isso seria mapear para a aplicação.)
Mas, ao mesmo tempo, acho que são muito raros os casos em que adaptações seriam necessárias para evitar problemas com esses algoritmos que descartam vias. A menos que eles estejam descartando até as vias primárias (arteriais urbanas), daí não tem como resolver mesmo. 2014-07-19 17:56 GMT-03:00 Paulo Carvalho <paulo.r.m.carva...@gmail.com>: > 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.treb...@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.carva...@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.treb...@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.carva...@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@openstreetmap.org >> >> > https://lists.openstreetmap.org/listinfo/talk-br >> >> > >> >> >> >> >> >> >> >> -- >> >> Fernando Trebien >> >> +55 (51) 9962-5409 >> >> >> >> "Nullius in verba." >> >> >> >> _______________________________________________ >> >> Talk-br mailing list >> >> Talk-br@openstreetmap.org >> >> https://lists.openstreetmap.org/listinfo/talk-br >> > >> > >> > >> > _______________________________________________ >> > Talk-br mailing list >> > Talk-br@openstreetmap.org >> > https://lists.openstreetmap.org/listinfo/talk-br >> > >> >> >> >> -- >> Fernando Trebien >> +55 (51) 9962-5409 >> >> "Nullius in verba." >> >> _______________________________________________ >> Talk-br mailing list >> Talk-br@openstreetmap.org >> https://lists.openstreetmap.org/listinfo/talk-br > > > > _______________________________________________ > Talk-br mailing list > Talk-br@openstreetmap.org > https://lists.openstreetmap.org/listinfo/talk-br > -- Fernando Trebien +55 (51) 9962-5409 "Nullius in verba." _______________________________________________ Talk-br mailing list Talk-br@openstreetmap.org https://lists.openstreetmap.org/listinfo/talk-br
