Mapa de Roteamento, a la Google Maps?

Question

Eu sempre fui intrigado com o Mapa de Roteamento, mas eu nunca encontrei qualquer bom introdutório (ou até mesmo avançado!) nível de tutoriais sobre ele.Alguém tem alguma ponteiros, dicas, etc?

Atualização: Eu sou essencialmente à procura de ponteiros como um mapa do sistema é implementado (estruturas de dados, algoritmos, etc.).

Answer 1

Dê uma olhada no open street map projeto para ver como esse tipo de coisa está sendo abordada num verdadeiramente projeto de software livre, usando apenas o usuário fornecida e licenciada de dados e ter um wiki que contém coisas que você pode achar interessante.

Alguns anos atrás os caras envolvidos, onde muito fácil de ir e respondeu a muitas perguntas que eu tinha, então eu não vejo nenhuma razão por que eles ainda não são um grupo agradável.

Answer 2

Barry Brumitt, um dos engenheiros do Google maps para encontrar rotas recurso, escrevi um post sobre o tema, que podem ser de interesse:

A estrada para o melhor caminho-de encontrar 11/06/2007 03:47:00 PM

Answer 3

A* é, na verdade, muito mais perto de produção algoritmos de mapeamento.Isso requer um pouco menos de exploração comparado com Dijikstra do algoritmo original.

Answer 4

Pelo Mapa de Roteamento, você significa encontrar o caminho mais curto ao longo de uma rua de rede?

Dijkstra algoritmo do caminho mais curto é o melhor conhecido.A wikipédia não tem um mau intro: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Há um applet Java aqui, onde você pode vê-lo em ação: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html e o Google que levam você ao código-fonte em praticamente qualquer idioma.

Qualquer implementação real para a geração de rotas de condução vai incluir um pouco de dados sobre a rede de ruas que descreve os custos associar com atravessando links e nós—rede viária de hierarquia, média de velocidade, cruzamento de prioridade, sinal de trânsito de vinculação, banido curvas etc.

Answer 5

Em vez de aprender APIs para cada mapa fornecedor de serviços ( como Feitos, Ymaps api) é bom saber Mapstraction

"Mapstraction é uma biblioteca que fornece uma API comum para vários javascript mapeamento de APIs"

Eu sugiro que você vá para o URL e aprender uma API genérica.Há uma boa quantidade de How-Tos também.

Answer 6

Eu ainda tenho que encontrar um bom tutorial sobre o encaminhamento, mas há muitas código para ler:

Há GPL encaminhamento aplicações que utilizam dados do Openstreetmap, e.g. Gosmore que funciona em Windows (+ móvel) e Linux.Há um número interessante de [aplicações utilizando os mesmos dados, mas gosmore tem alguns legal usa exemplo:interface com web sites.

O maior problema de roteamento é ruim de dados, e você nunca fica bom o suficiente de dados.Então, se você quiser experimentá-lo a manter o seu teste local, assim você pode controlar os dados melhor.

Answer 7

A partir de um ponto de vista conceitual, imagine-se da queda de uma pedra em uma lagoa e assistir as ondas.As rotas representaria a lagoa e a pedra a sua posição inicial.

É claro que o algoritmo teria de pesquisar alguns proporção de n^2 caminhos, como a distância que n aumenta.Você tomaria posição inicial e verifique todos os caminhos disponíveis a partir de que ponto.Em seguida, chame recursivamente para os pontos ao final desses caminhos e assim por diante.

Você pode aumentar o desempenho, pelo duplo apoio no caminho, por não re-verificar as rotas de um ponto, se tiver já sido abrangidos e, dando-se em caminhos que estão tomando muito tempo.

Uma forma alternativa é usar o ant feromônio abordagem, onde formigas de rastreamento aleatoriamente a partir de um ponto de início e deixam uma trilha de cheiro, que acumula mais de formigas atravessar um determinado caminho.Se você enviar (o suficiente), formigas, tanto do ponto de partida e os pontos de extremidade, em seguida, eventualmente, o caminho com o perfume mais forte será o mais curto.Isto é porque o caminho mais curto terá sido visitado mais vezes em um determinado período de tempo, dado que as formigas andam em um ritmo uniforme.

EDIT @ Spikie

Como uma explicação mais detalhada de como implementar a lagoa do algoritmo de potencial estruturas de dados necessárias são destacadas:

Você vai precisar para armazenar o mapa como uma rede.Este é simplesmente um conjunto de nodes e edges entre eles.Um conjunto de nodes constituem um route.Uma aresta une dois nós (possivelmente o mesmo nó), e tem associado um cost como distance ou time para atravessar a borda.Uma aresta pode ser bidirecional ou unidirecional.Provavelmente o método mais simples para apenas ter a uni-direcional e de casal para duas maneira de viajar entre nós (i.e.uma aresta de a para B e de a para B para A).

A título de exemplo, imagine três estações ferroviárias dispostos em um triângulo apontando para cima.Há também mais três estações, cada uma a meio caminho entre eles.Bordas juntar todas as estações adjacentes juntos, o diagrama final vai ter um triângulo invertido sentado dentro do maior triângulo.

Etiqueta de nós, começando de baixo para a esquerda, indo da esquerda para a direita e para cima, como A,B,C,D,E,F (F no topo).

Suponha que as arestas podem ser utilizadas em qualquer direção.Cada aresta tem um custo de 1 km.

Ok, então desejamos a rota da esquerda inferior para o topo da estação de F.Há muitos caminhos possíveis, incluindo aqueles que dobrar-se sobre si mesmas, por exemplo,ABCEBDEF.

Nós temos uma rotina de dizer, NextNode, que aceita um node e um cost e chama-se para cada nó pode viajar.

Claramente se deixamos a rotina de executá-lo, eventualmente, irá descobrir todas as rotas, incluindo aquelas que são potencialmente infinito de comprimento (por exemplo, ABABABAB etc.).Impedir que isso aconteça, verificando-se contra o cost.Sempre que visitar um nó que não tenha sido visitado antes, nós colocamos o custo e o nó viemos contra esse nó.Se um nó tem sido visitado antes de verificar contra o custo existente e, se nós somos mais baratos que atualizar o nó e seguir em frente (recursing).Se formos mais caro, então vamos ignorar o nó.Se todos os nós são ignorados, em seguida, vamos sair da rotina.

Se nós batemos nosso nó de destino, em seguida, vamos sair da rotina também.

Desta forma, todas as rotas viáveis são verificadas, mas fundamentalmente apenas aqueles com o menor custo.Ao final do processo, cada nó terá o menor custo para chegar a esse nó, incluindo o nosso nó de destino.

Para obter a rota trabalhamos para trás a partir do nosso nó de destino.Desde que armazenado o nó de nós veio junto com o custo, nós apenas um salto para trás, construindo o percurso.Para o nosso exemplo teríamos algo como:

Nó - (Total) Custo 0 - A Partir Do Nó Nenhum
O Nó B - Custo 1 - A Partir Do Nó
O Nó C - Custo 2 - A Partir Do Nó B
O Nó D - Custo 1 - A Partir Do Nó
Nó de E - Custo 2 - a Partir do Nó D / Custo 2 - a Partir do Nó B (esta é uma exceção, pois não há igualdade de custo)
O Nó F - Custo 2 - A Partir Do Nó D

Assim, o caminho mais curto é do ADF.

Answer 8

A partir de minha experiência de trabalho neste campo,* faz o trabalho muito bem.É (como mencionado acima) mais rápido do que o algoritmo de Dijkstra, mas ainda é simples o suficiente para uma ordinariamente competente programador implementar e compreender.

Construção de rede de rotas é a parte mais difícil, mas que pode ser decomposto em uma série de passos simples:obter todas as estradas;ordenar os pontos em ordem;fazer grupos de idênticos pontos em diferentes estradas em interseções (nós);adicione arcos em ambas as direções onde os nós se conectam (ou em apenas uma direção para uma estrada de sentido único).

O A* algoritmo de si, é bem documentado na Wikipédia.A chave para optimizar é a seleção dos melhores nó da lista aberta, para que você precisa de um alto desempenho fila de prioridade.Se você estiver usando C++, você pode usar a STL priority_queue adaptador.

Personalizar o algoritmo de percurso em diferentes partes da rede (por exemplo, peão, carro, transporte público, etc.) de graça, velocidade, distância ou outros critérios é bastante fácil.Você faz isso escrevendo filtros para controlar quais os segmentos de rota estão disponíveis, quando da construção da rede, e qual o peso que é atribuído a cada um.

Answer 9

Outro pensamento me ocorre sobre o custo de cada travessia, mas seria aumentar o tempo e a potência de processamento necessária para calcular.

Exemplo: Existem 3 maneiras que eu posso tomar (onde eu moro) para ir do ponto a para B, de acordo com o GoogleMaps.Unidades Garmin oferecem cada um desses 3 caminhos na Quickest cálculo da rota.Depois de atravessar cada uma dessas rotas muitas vezes e a média (obviamente, haverá erros, dependendo da hora do dia, a quantidade de cafeína, etc.), Eu sinto os algoritmos pode levar em conta o número de curvas na estrada para o alto nível de precisão, exemplo: estrada reta de 1 milha, vai ser mais rápido do que um 1 quilômetro de estrada com curvas acentuadas em.Não é uma sugestão prática, mas certamente que eu uso para melhorar o resultado conjunto do meu trajeto diário.