Eu não trabalho com isso mas já estudei o assunto a fundo. Mudei de área quando vi que essa já estava muito avançada.
O que geralmente se faz é calcular o grafo dual do mapa geográfico: linhas viram nós e pontos de conexão entre elas viram linhas entre esses nós. Uma restrição de conversão se torna a exclusão de uma ou mais das linhas resultantes de um cruzamento. Os nós contém os pesos (tempo, ou velocidade e distância) de trafegar pela linha. O algoritmo então simplesmente explora essa estrutura de dados até chegar no destino. Conforme explora, vai somando os tempos. Quando encontrar a sequência que minimiza o tempo total, termina. Como o grafo geralmente é imenso, usam-se heurísticas para desconsiderar alguns caminhos. É aí que os algoritmos começam a dar resultados diferentes para os mesmos dados. Eu dei uma olhada por altos no projeto do mkgmap pra ver se poderia ajudar, mas achei confusa a sua organização. O projeto não tem um líder e "evolui" com contribuições eventuais. Também acho seu escopo limitado aos usuários de Garmin (eu não tenho um Garmin), e o meu interesse são sistemas open source que cheguem ao grande público. O OSRM é o contrário de tudo isso: algoritmo estado-da-arte, código muito bem escrito, comunidade organizada e responsiva, e utilizável pelo mundo todo sem precisar de ferramentas pagas. As dificuldades relatadas até aqui me fazem supor que o Mapfactor Navigator usa um algoritmo similar ao Garmin. É grátis e tem pra celular. E a comunidade do Mapfactor, embora pequena, me parece maior e mais organizada que a do mkgmap. Talvez o pessoal queira dar uma olhada no aplicativo. On 5 Jul 2015 11:17, "Aun Johnsen" <[email protected]> wrote: > 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 >
_______________________________________________ Talk-br mailing list [email protected] https://lists.openstreetmap.org/listinfo/talk-br
