Quais algoritmos direções de computação do ponto A ao ponto B em um mapa?

StackOverflow https://stackoverflow.com/questions/430142

  •  08-07-2019
  •  | 
  •  

Pergunta

Como provedores de mapa (como o Google ou o Yahoo! Maps) sugerem direções?

Quer dizer, eles provavelmente têm dados do mundo real, de alguma forma, certamente incluindo as distâncias mas também, talvez coisas como velocidades de condução, presença de calçadas, horários de comboios, etc. Mas suponha que os dados estavam em um formato mais simples, dizer muito grande grafo orientado com pesos das arestas reflectindo distâncias. Eu quero ser capaz de direções rapidamente de computação de um ponto arbitrário para outro. Às vezes, estes pontos serão juntos (dentro de uma cidade), enquanto às vezes eles vão estar distantes (cross-country).

algoritmos gráfico como o algoritmo de Dijkstra não vai funcionar porque o gráfico é enorme. Felizmente, algoritmos heurísticos como A * provavelmente trabalho. No entanto, os nossos dados é muito estruturado, e talvez algum tipo de trabalho poderia abordagem em camadas? (Por exemplo, armazenar as direções entre certos pontos "chave" distantes, bem como algumas direcções locais pré-computados. Direções, então por dois pontos distantes envolverá direcções locais para alguns pontos-chave, orientações globais para outro ponto-chave e, em seguida locais direções novamente).

O que os algoritmos são realmente utilizados na prática?

PS. Esta questão foi motivado por encontrar peculiaridades em direções mapeamento online. Ao contrário da desigualdade do triângulo, por vezes, o Google Maps pensa que XZ leva mais tempo e é mais distante do que usando um ponto intermediário como em XYZ . Mas talvez as suas instruções de pé otimizar para um outro parâmetro, também?

PPS. Aqui está outra violação da desigualdade do triângulo que sugere que (para mim) que eles usam algum tipo de abordagem faseada: XZ contra XYZ . O ex parece usar proeminente Boulevard de Sebastopol, mesmo que seja um pouco fora do caminho.

Editar :. Nenhum desses exemplos parecem trabalhar mais, mas ambos fizeram na época do post original

Outras dicas

Esta questão tem sido uma área ativa de pesquisa nos últimos anos. A idéia principal é fazer um pré-processamento no gráfico uma vez , a acelerar todas as seguintes consultas . Com este itinerários Informações adicionais podem ser computados muito rápido. Ainda assim, Algoritmo de Dijkstra é a base para todas as otimizações.

Aracnídeo descreveu o uso de busca bidirecional e borda poda com base em informações hierárquica. Estas técnicas speedup funcionar muito bem, mas os algoritmos mais recentes superar estas técnicas por todos os meios. Com algoritmos atuais de caminhos mais curtos pode ser calculado em tempo considerável menos de um milissegundo em uma rede de estradas continental. A rápida implementação do algoritmo não modificada do Dijkstra precisa de cerca de 10 segundos .

O artigo Engenharia rápido Route Planning Algoritmos dá uma visão geral do progresso da pesquisar nesse campo. Veja as referências de que o papel para obter mais informações.

Os algoritmos mais rápidos conhecidos não use informações sobre o status hierárquico da estrada nos dados, ou seja, se é uma estrada ou uma estrada local. Em vez disso, eles calcular em uma etapa de pré-processamento de uma própria hierarquia que otimizado para acelerar o planejamento da rota. Este precomputation pode então ser usada para podar a pesquisa: Longe de início e de destino estradas lentos não precisam ser considerados durante o algoritmo de Dijkstra. Os benefícios são muito bons desempenho e correção garantia para o resultado.

Os algoritmos de planeamento de rota primeiro otimizados tratados apenas com redes de estradas estáticos, o que significa uma vantagem no gráfico tem um valor de custo fixo. Isso não é verdade, na prática, uma vez que queremos levar informações dinâmicas, como engarrafamentos ou restrictrions dependentes de veículos em conta. Algoritmos mais recentes também pode lidar com essas questões, mas ainda há problemas a resolver ea pesquisa está em curso.

Se você precisa as distâncias caminho mais curto para calcular uma solução para o TSP , então você provavelmente está interessado em matrizes que contêm todas as distâncias entre as fontes e destinos. Para isso, você poderia considerar Computação Muitos-para-muitos caminhos mais curtos Usando estrada Hierarquias . Note, que este foi melhorado por novas abordagens nos últimos 2 anos.

Apenas abordar as violações da desigualdade do triângulo, espero que o fator extra que está otimizando para o senso comum. Você não necessariamente querem o caminho mais curto ou mais rápido, uma vez que pode levar a caos e destruição . Se você quer que seus sentidos a preferir as principais rotas que são amigáveis-caminhão e podem lidar com ter todos os sat-nav-seguinte driver enviado-los, você rapidamente descartar a desigualdade do triângulo [1].

Se Y é uma rua residencial estreita entre X e Z, você provavelmente só quer usar o atalho via Y se o usuário explicitamente peça X-Y-Z. Se eles pedem X-Z, eles devem ficar com as principais estradas, mesmo que seja um pouco mais e demora um pouco mais. É semelhante a de Braess paradoxo - se todo mundo tenta tomar o caminho mais curto, mais rápido, os meios de congestionamento resultantes que não é a rota mais rápida para qualquer um mais. A partir daqui podemos desviar a teoria dos grafos em teoria dos jogos.

[1] Na verdade, qualquer esperança de que as distâncias produzidos será uma função distância em matrizes sentido matemático quando você permite que estradas de sentido único e perder a exigência de simetria. Perder a desigualdade triangular também é apenas esfregando sal na ferida.

Aqui está algoritmos mais rápido encaminhamento do mundo comparados e comprovada para a correção:

http://algo2.iti.uka.de/schultes/hwy/ schultes_diss.pdf

Aqui está uma conversa google tecnologia sobre o assunto:

http://www.youtube.com/watch?v=-0ErpE8tQbw

Aqui está uma implementação da rodovia-hierarquias algoritmo como discutido por Schultes (atualmente em Berlim única, estou escrevendo a interface e uma versão móvel está sendo desenvolvido também):

http://tom.mapsforge.org/

Eu não tenho trabalhado no Google ou Microsoft ou Yahoo Maps antes, então eu não posso te dizer como eles funcionam.

No entanto, eu fiz arquiteto de um sistema de otimização da cadeia de suprimentos personalizado para uma empresa de energia que incluiu uma programação e aplicação de roteamento para a sua frota de caminhões. No entanto, os nossos critérios de encaminhamento foi específico business-muito mais do que é de construção ou de tráfego retarda ou fechamento de pista.

Nós empregamos uma técnica chamada ACO (otimização de colônia de formigas) para agendar e encaminhar caminhões. Esta técnica é uma técnica de IA que foi aplicado para o problema do caixeiro viajante para resolver problemas de roteamento. O truque com ACO é a construção de um erro de cálculo baseada em fatos conhecidos do roteamento de modo que o modelo gráfico de resolução sabe quando parar (quando é o erro pequeno o suficiente).

Você pode google ACO ou TSP para encontrar mais sobre esta técnica. Eu não usei qualquer um dos open-source ferramentas de IA para este no entanto, portanto, não pode sugerir uma (embora eu ouvi SWARM foi bastante abrangente).

algoritmos gráfico como o algoritmo de Dijkstra não vai funcionar porque o gráfico é enorme.

Este argumento não necessariamente segurar porque Dijkstra não costumam olhar para o gráfico completo, mas sim apenas um subconjunto muito pequeno (o melhor interligados gráfico, o menor este subconjunto).

Dijkstra pode realmente executar muito bem para gráficos bem-comportados. Por outro lado, com parametrização cuidadosa A * terá sempre um desempenho tão bom, ou melhor. Você já experimentou como ele iria realizar em seus dados?

Dito isso, eu também estaria muito interessado em ouvir sobre as experiências de outras pessoas. Claro, exemplos de destaque, como a busca do Google Map são particularmente interessantes. Eu poderia imaginar algo como uma heurística do vizinho mais próximo indicado.

O actual estado da arte em termos de tempos de consulta para redes rodoviárias estáticos é o algoritmo rotulagem Hub proposto por Abraham et al. http://link.springer.com/chapter/10.1007/978-3-642- 20662-7_20 . Um meio e pesquisa excelentemente escrita do campo foi recentemente publicado como um relatório técnico Microsoft http: / /research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf .

A versão curta é ...

O algoritmo rotulagem Hub fornece as consultas mais rápidas para redes rodoviárias estáticos, mas exige uma grande quantidade de RAM para executar (18 GiB).

roteamento nó Transit é um pouco mais lento, embora, ele requer apenas cerca de 2 GiB de memória e tem um tempo mais rápido de pré-processamento.

Contração hierarquias fornecem um bom trade-off entre os tempos rápidos de pré-processamento, baixos requisitos de espaço (0,4 GIB) e tempos de consulta rápida.

Ninguém algoritmo é dominar completamente ...

Esta Tech Talk Google por Peter Sanders pode ser de interesse

https://www.youtube.com/watch?v=-0ErpE8tQbw

Também esta conversa por Andrew Goldberg

https://www.youtube.com/watch?v=WPrkc78XLhw

Uma implementação open source de hierarquias de contração está disponível a partir de Peter Sanders website grupo de pesquisa na KIT. http://algo2.iti.kit.edu/english/routeplanning.php

Também um post facilmente acessível escrito por Microsoft lá uso da CRP algoritmo ... http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/

Estou um pouco surpreso de não ver Floyd Warshall algoritmo mencionado aqui. Este trabalho algoritmo é muito parecido com Dijkstra. Ele também tem uma característica muito agradável que é que lhe permite calcular o tempo que você gostaria de continuar permitindo vértices mais intermediários. Por isso vai naturalmente encontrar as rotas que usam interestaduais ou rodovias rapidamente.

Eu fiz isso um monte de vezes, na verdade, tentando vários métodos diferentes. Dependendo do tamanho (geográfica) do mapa, você pode querer considerar usando a função haversine como uma heurística.

A melhor solução que eu fiz foi usar A * com uma distância em linha reta como uma função heurística. Mas então você precisa de algum tipo de coordenadas para cada ponto (intersecção ou vértice) no mapa. Você também pode tentar diferentes ponderações para a função heurística, ou seja 

f(n) = k*h(n) + g(n)

onde k é um pouco maior constante do que 0.

Provavelmente similar à resposta em rotas pré-computados entre os principais locais e mapas em camadas, mas o meu entendimento é que nos jogos, para acelerar A *, você tem um mapa que é muito grossa para navegação macro, e um bom- mapa de grão para a navegação até o limite de direções macro. Então você tem 2 pequenos caminhos para calcular e, portanto, o seu espaço de busca é muito, muito menor do que simplesmente fazer um único caminho para o destino. E se você está no negócio de fazer isso muito, você tem um monte de que os dados pré-computados assim pelo menos parte da busca é uma busca de dados pré-computados, ao invés de uma busca por um caminho.

Isso é pura especulação da minha parte, mas eu suponho que eles podem usar uma estrutura de dados mapa influência sobrepondo o mapa dirigido, a fim de estreitar o domínio de pesquisa. Isso permitiria que o algoritmo de busca para direcionar o caminho para as principais rotas quando a viagem pretendida é longa.

Tendo em conta que este é um aplicativo do Google, também é razoável supor que um monte da mágica é feita através de extensa cache. :) Eu não ficaria surpreso se o cache o top 5% mais comuns Google mapa da rota pedidos permitiu uma grande fatia (20%? 50%?) De pedidos a serem respondidas por um look-up simples.

Tive mais alguns pensamentos sobre isso:

1) Lembre-se que os mapas representam uma organização física. Armazenar o / longitude latitude de cada cruzamento. Você não precisa verificar muito além dos pontos que estão na direção de seu alvo. Só se você se encontra bloqueado você precisa ir além disso. Se você armazenar uma sobreposição de conexões superiores você pode limitá-lo ainda mais -. Você normalmente nunca atravessar um daqueles de uma forma que vai longe do seu destino final

2) Divide o mundo em um monte de zonas definidas pela conectividade limitada, definir todos os pontos de conectividade entre as zonas. Encontre o que zonas de sua origem e de destino estão em, para o início eo fim rota zona da sua localização para cada ponto de conexão, para as zonas entre o mapa simplesmente entre pontos de conexão. (Eu suspeito que uma grande parte do último é já pré-calculados.)

Note que as zonas pode ser menor do que a área metropolitana. Qualquer cidade com terreno características que dividi-lo (por exemplo, um rio) seria várias zonas.

Eu estava muito curioso sobre a heurística usada, quando um tempo atrás que temos rotas a partir do mesmo local de partida perto de Santa Rosa, a dois acampamentos diferentes em Yosemite National Park. Estes destinos diferentes produzidos bastante diferentes rotas (via I-580 ou CA-12), apesar do fato de que ambas as rotas convergentes para os últimos 100 milhas (junto CA-120) antes divergentes novamente por algumas milhas no final. Este foi bastante repetitivo. As duas rotas foram até 50 milhas para além de cerca de 100 milhas, mas as distâncias / tempos foram muito próximos uns dos outros como seria de esperar.

Infelizmente eu não posso reproduzir isso - os algoritmos deve ter mudado. Mas tinha-me curioso sobre o algoritmo. Tudo o que posso especular é que houve alguma poda direcional que passou a ser extremamente sensível à diferença angular pequena entre os destinos como visto de longe, ou não eram diferentes segmentos pré-computadas selecionados pela escolha do destino final.

Falando de GraphHopper , um planejador rápido rota Open Source baseado em OpenStreetMap, eu li uma literatura pouco e implementados alguns métodos. A solução mais simples é um Dijkstra e uma melhoria simples é uma Dijkstra bidirecional que explora cerca de apenas a metade dos nós. Com Dijkstra bidirctional uma rota através de toda a Alemanha leva já 1seg (para o modo de carro), em C seria provavelmente apenas 0,5s ou menos;)

Eu criei um GIF animado de um caminho de procura real com bidirecional Dijkstra aqui . Além disso, existem mais algumas ideias para fazer Dijkstra mais rápido como fazer a *, que é um "Dijkstra goal-oriented". Também eu criar um gif-animação para ele.

Mas como fazê-lo (muito) mais rápido?

O problema é que, para um caminho de pesquisa todos os nós entre os locais tem que ser explorado e isso é realmente caro, já na Alemanha há vários milhões deles. Mas um ponto de dor adicional de Dijkstra etc é que tais buscas usa muita memória RAM.

Existem soluções heurísticas, mas também soluções exatas que organzize o gráfico (rede rodoviária) em camadas hierárquicas, ambos têm pro & contras e, principalmente, resolver o problema de velocidade e RAM. Eu listei alguns deles em esta resposta .

Para GraphHopper eu decidi usar Contração Hierarquias porque é relativamente 'fácil' para implementar e não leva as idades para a elaboração do gráfico. Ele ainda resulta em tempos de resposta muito rápido como você pode testar no nosso exemplo em linha GraphHopper Mapas . Por exemplo. da África do Sul para leste da China, que resultados em uma distância 23 mil quilômetros e cerca de 14 dias o tempo de condução automóvel e levou apenas ~ 0.1s no servidor.

Eu tenho trabalhado em roteamento por alguns anos, com uma explosão recente da atividade solicitado pelas necessidades de meus clientes, e eu descobri que A * facilmente é rápido o suficiente; não há realmente nenhuma necessidade de procurar otimizações ou algoritmos mais complexos. Encaminhamento ao longo de um gráfico enorme não é um problema.

Mas a velocidade depende da existência de toda a rede de roteamento, pelo qual quero dizer o grafo direcionado de arcos e nós que representam segmentos de rota e cruzamentos, respectivamente, na memória. A principal sobrecarga tempo é o tempo necessário para criar esta rede. Algumas figuras ásperas com base em um laptop comum com o Windows, e encaminhamento ao longo de toda a Espanha: tempo necessário para criar a rede: 10-15 segundos; tempo necessário para calcular uma rota:. demasiado curta para medida

A outra coisa importante é ser capaz de re-utilizar a rede para tantos cálculos de roteamento como você gosta. Se o seu algoritmo tem marcado os nós de alguma forma para registrar a melhor rota (custo total para o nó atual e melhor arco para ele) -, pois tem no A * - você tem que redefinir ou limpar esta informação idade. Ao invés de ir através de centenas de milhares de nós, é mais fácil de usar um sistema de número de geração. Marcar cada nó com o número de geração de seus dados; incrementar o número de geração quando você calcular um novo percurso; qualquer nó com um número geração mais velha é obsoleto e suas informações podem ser ignorados.

Eu vejo o que se passa com os mapas no OP:

Olhe para a rota com o ponto intermédio especificado:. A rota vai ligeiramente para trás devido a esse caminho que não é reto

Se seu algoritmo não vai voltar atrás, não vai ver a rota mais curta.

Um todos os pares de algoritmo de caminho mais curto irá calcular os caminhos mais curtos entre os vértices de um grafo. Isso permitirá que os caminhos para ser pré-computados em vez de exigir um caminho a ser calculado cada vez que alguém quer encontrar o caminho mais curto entre uma origem e um destino. O algoritmo de Floyd-Warshall é um algoritmo de caminho todos os pares mais curto.

Mapas nunca tomar em consideração todo o mapa. Meu palpite é:- 1. De acordo com a sua localização, eles carregam um lugar e os marcos nesse lugar. 2. Quando você procura o destino, é quando eles carregam a outra parte do mapa e fazer um gráfico a partir de dois lugares e, em seguida, aplicar os algoritmos de menor caminho.

Além disso, há uma importante técnica de programação dinâmica que eu suspeito é usado no cálculo de caminhos mais curtos. Você pode se referir a isso também.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top