Existem trabalhos como Reach for A * de pesquisadores da Microsoft e Hierarquias de rodovias de Sanders e Schtolz (se eu soletrar o nome corretamente) de Karlsruhe Uni . Ambos reduzem muito a ordem dos cálculos e aceleram milhares de vezes em gráficos grandes (consulte os resultados nos documentos vinculados). O último trabalho levou ao Open Source Routing Machine , que infelizmente não é popular o suficiente e não foi adaptado (eu não poderia compilá-lo, embora tenha se esforçado bastante).
Ao mesmo tempo, os dbs que tentei, Spatialite e PgRouting, de acordo com seus documentos, oferecem apenas os algoritmos Dijkstra e A * . Eu nem vi a pesquisa bidirecional mencionada, o que economiza o tempo de cálculo duas vezes na minha experiência.
Existem algoritmos melhores para bancos de dados ou outros aplicativos?
fonte
Respostas:
A verdade é que a maioria das pessoas usa uma variação personalizada do algoritmo A * . Você verá isso na maioria dos "grandões" (não sei dizer quem são eles em um fórum público, mas posso lhe dizer que você provavelmente usa um deles - garantido), onde a modificação das heurísticas é muito dependente dos conjuntos de dados que eles usam.
Você mencionou o pgrouting , o que eu consideraria uma opção "tradicional". É bom para executar algoritmos de roteamento simples e para a maioria dos problemas. Também é fácil de usar e usa um banco de dados tradicional em seu back-end.
No entanto, isso realmente depende da escala e do tipo de problema que você está tentando resolver e o roteamento é um problema gráfico .
Mais uma vez, os "grandões" geralmente têm muitos dados associados ao seu gráfico (por exemplo, dados de tráfego, rotas de ônibus, caminhos pedestres) que afetam o algoritmo de roteamento. Eles são conhecidos como planejadores de viagem multimodais (onde você também pode escolher "modos" - sem ciclovias - apenas transporte público - esse tipo de coisa). Você pode pensar como planejamento de viagem também se torna uma questão sensível tempo (ou seja, se você andar para trás algumas arestas para trás, você será capaz de pegar o metrô que leva você para o seu destino para a frente muito mais rápido do que se você apenas tentou navegar nas bordas frente usando o menor custo).
Os "grandões" não armazenam seus dados em um banco de dados tradicional em si, eles usam gráficos pré-computados (bem-vindo aos clusters hadoop / mapreduce!). Como você pode imaginar, esses gráficos se tornam realmente grandes, portanto, saber como conectar as bordas dos gráficos adjacentes pode ser um desafio.
De qualquer forma, eu recomendaria que você visse alguns projetos de gráficos de roteamento multimodais:
O Graphserver vem à mente. Não é muita documentação, mas muita grandeza de codificação pura (AFAIK, acredito que o MapQuest usa uma variação deste projeto para alguns de seus produtos de roteamento).
Outra opção seria o OpenTripPlanner, que tem muitas pessoas inteligentes por trás (incluindo pessoas do graphserver).
fonte
Não tenho certeza se é mais recente, mas o pgRouting possui um algoritmo Shooting-Star :
A extensão Network Analyst da ESRI usa a abordagem hierárquica mencionada para limitar os tempos de solução:
Há um white paper muito detalhado com exemplos dessa abordagem no site da ESRI - no entanto, é necessário fazer o login para fazer o download (White Paper de Rotas Hierárquicas no ArcGIS Network Analyst).
fonte
Hierarquia de contração é um algoritmo muito rápido:
Esse algoritmo é compatível com RAM durante a execução de uma consulta (para manter um gráfico contratado, é necessário mais RAM, além de pré-processamento em massa)
Existem alguns outros algoritmos - incluindo os que resolvem o roteamento de transporte público:
A Microsoft também está fazendo algumas pesquisas:
(bem, Daniel Delling também é de Karlsruhe)
Você pode obter uma boa introdução e uma visão geral dos algoritmos disponíveis:
Atenção: palestras em alemão (!). mas pelo menos os cabeçalhos podem ajudá-lo a obter mais informações (ALT, Arc-Flags, CHASE, ...) ou a literatura em anexo!
atualizar
Agora o GraphHopper implementa hierarquias de contração e também outros algoritmos, você também pode experimentar a demonstração .
fonte