Fernando, Se eu entendo esse certa o graf de roteamento, alias o produto do algoritmo, não ha informação geográfico mas tem linhas que representa tempo e distancia entre nos que representando locações fisico, um no pode ser um ponto onde 2 vias cruzam, mas pode também ser a rotatório completo, ou ate um trevo complicado como um ponto so. Um ponto pode ser um referencia da rota (vira a esquerda no BR-101), ou um ponto do penalidade (espera 2 segundos no semáforo). Esses linhas e pontos e abstratos, e não direitamente retirado do mapa física.
Se voce trabalho com isso, talvez voce posso ajudar identificar os objetos que pode/deve dar penalidade de roteamento? On 7/5/15, Fernando Trebien <[email protected]> wrote: > Aí você que entra na minha área de expertise como se soubesse mais. Sou > mestre em computação, li várias versões desses algoritmos. > > O nó a que me refiro é o do grafo de roteamento. Não é o nó do mapa (com > coordenadas e tal). O nó do grafo de roteamento sequer tem coordenadas, > possui apenas propriedades abstratas como o tempo para atravessar uma linha > de uma ponta à outra, e a referência a essa linha daí sim no mapa > geográfico. > On 5 Jul 2015 05:44, "Marcio - Thundercel" <[email protected]> > wrote: > >> 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 >> <[email protected]>: >> >>> 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 >> [email protected] >> https://lists.openstreetmap.org/listinfo/talk-br >> >> _______________________________________________ >> 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
