Ajude a escolher um mecanismo de roteamento adequado

16

Estou construindo um sistema de planejamento de rota, mas ainda tenho que decidir qual mecanismo de roteamento subjacente vou usar. Até agora eu encontrei pgrouting e neo4j.

Eu tenho minha rede de rotas em um banco de dados postgresql / postgis (importado de um shapefile). Fiz consultas para extrair nós (pontos finais de maneiras em que você deve tomar uma decisão em que direção seguir ou sem saída) e para extrair arestas (geralmente compostas por várias maneiras consecutivas). Todas as minhas arestas são bidirecionais.

Meu principal objetivo é calcular rotas nesta rede usando um algoritmo A-star em que distance = cost.

Meu sentimento me diz que um banco de dados de gráficos como o neo4j é o caminho a seguir (como parece ser feito para esse fim), mas eles não parecem suportar a estrela A por padrão e também não há um senso real de geometria . Parece mais adequado para redes sociais em vez de mapas.

  • O pgrouting atenderia minhas necessidades?
  • É rápido o suficiente para consultas dinâmicas (+ -2000 nós, + -4000 arestas)? Normalmente, isso seria alguns ms para a estrela A, mas não tenho certeza sobre essa implementação no sql.
  • O pgrouting A-star me fornece uma lista de nós e arestas?
  • Na maioria dos exemplos que vejo sobre pgrouting, noto que geralmente existe uma lista de comandos após o cálculo da rota (como "No X, vire à esquerda, etc"). O pgrouting produz isso ou é de outro sistema?

Espero que alguém possa me dar algumas informações sobre qual sistema escolher. Neo4j, pgrouting ou algum outro sistema.

mrg
fonte
3
Eu acho que a maioria dos algoritmos de roteamento não opera com um "senso de geometria", em vez disso, um atributo geométrico é calculado e usado como custo (isto é, medida da distância de uma polilinha). Eu nunca usei o Neo4j, mas parece realmente capaz e posso usá-lo em breve. Acabei de examinar a documentação e parece possível usar o A-Star: docs.neo4j.org/chunked/stable/graph-algo.html docs.neo4j.org/chunked/stable/… pgRouting também é capaz, e Eu sou um grande fã disso. Seria interessante comparar o desempenho dessas duas soluções.
Allan Adair
Primeiro, eu sugeriria examinar Urbansim, um modelo de uso da terra de código aberto. Quanto à sua pergunta de roteamento, se este é um aplicativo de planejamento, sugiro que primeiro analise software como TransCAD, CUBE, PLANAR ou EMME / 2 para funcionalidade e interface do usuário. Eles geralmente distribuem CDs de demonstração de 1 ou 2 horas de seu software (software que você pode executar por uma hora ou duas para ter uma ideia). Se você deseja criar algo para uso online ou desktop, consulte pgRouting; no entanto, por experiência, às vezes, não é tão fácil como o workshop / tutorial o retrata.
dassouki
Fiquei irritado com o trabalho de uma estrela e é incrível! Responde sim nas minhas 3 primeiras perguntas. Ainda me pergunto se alguém aqui sabe alguma coisa sobre a geração de instruções de navegação detalhadas. Existe alguma ferramenta que coopera com o pgrouting que gera direções detalhadas ("Depois de 200m vire à esquerda, etc") a partir da saída da rota calculada?
mrg

Respostas:

8

Atualmente, estou explorando o mesmo problema que você, para fins de trabalho de pesquisa. Antes de começar a testar esses dois bancos de dados, eu tinha a mesma presunção que você. Esse banco de dados de gráficos Neo4j seria a solução perfeita para esse tipo de problema. E parcialmente é, mas com muitos problemas.

O primeiro problema é que o A-Star será implementado apenas se você estiver usando um banco de dados incorporado, não pela API REST (servidor). Se você deseja usar o Neo4j com a API REST, apenas o algoritmo Dijkstra é suportado. O segundo problema são os requisitos de memória de hardware para o Neo4j. Para roteamento (Dijkstra) em redes "maiores", você precisa de muita RAM. Para rede grande, quero dizer algo como o tamanho do banco de dados rodoviário da Alemanha OSM . Eu executei meus testes no servidor de 6 GB de RAM (é tudo o que tenho atualmente) e apenas redes menores podem ser roteadas sem erros de exceção OutOfMemory. Redes "pequenas" em meus casos de teste são, por exemplo, banco de dados de estradas OSM para Áustria ou Croácia. Consultas simultâneas ainda não testei com o Neo4j.

Todos esses problemas não existem no pgRouting. A memória não é um problema, mas as consultas simultâneas aumentam a quantidade necessária de memória. Por exemplo, se você tiver duas solicitações simultâneas, será necessária uma quantidade dupla de memória. Isso não foi um problema, mesmo para um conjunto de dados OSM da Alemanha, o pgRouting roteado sem problemas para todas as solicitações simultâneas.

Desempenho: Na maioria dos casos, o Neo4j supera o pgRouting. Mas apenas se houver memória suficiente para o conjunto de dados fornecido e se todos os nós e relacionamentos estiverem na memória (hot start). O aumento / diminuição do desempenho depende de muitos fatores, mas principalmente do tamanho da rede e da distância (saltos) entre o nó de origem e o destino.

O tamanho da sua rede é muito pequeno, portanto você não deve ter problemas com a memória. Provavelmente, o Neo4j não é uma má escolha, mas você precisa se adaptar a um "pequeno" modelo de dados diferente dos bancos de dados de relações padrão.

Para responder às suas perguntas:

  • No pgRouting, você não precisa se preocupar com a implementação do AStar no sql, que já foi implementada.
  • Sim, o pgRouting pode fornecer uma lista de nós e arestas
  • Eu não acho que o pgRouting possa fornecer essas informações sem um trabalho personalizado sobre as consultas. Mas talvez eu esteja errado, talvez alguém tenha feito isso e possa ajudá-lo mais sobre esta questão.

Não sei se o ajudará diretamente, mas um dos servidores de roteamento mais rápido que encontrei é o osm2po . Funciona com o conjunto de dados OSM e é bastante rápido. Atualmente, dijkstra está implementado, mas o desenvolvedor também anunciou a AStar. Espero que isso ajude você. :)

Mario Miler
fonte
É bom ouvir de alguém que realmente testou os dois sistemas. Enquanto isso, tenho muito mais experiência com pgrouting. Notei que o pgrouting constrói o gráfico inteiro para cada consulta e isso o torna bastante lento para redes grandes (tamanho da Alemanha), então não vejo por que o pgrouting exigiria menos memória que o Neo4j. Minha próxima tentativa será obter o gráfico inteiro estático no ram e direcioná-lo (com neo4j, nx_spatial etc) para garantir uma resposta mais rápida para o roteamento em tempo real.
Mrg
Sim, quanto maior o gráfico, maior a diferença entre pgrouting e neo4j. Provavelmente, se você colocar um gráfico inteiro na memória, essa seria a solução mais rápida, sem dúvida. O Neo4j é bastante rápido quando todo o gráfico é carregado na memória. Não sei sobre o nx_spatial, eu não testei, mas talvez eu o faça. Eu acredito que poderia superar o Neo4j. Mas esta solução é boa se for aceitável para a sua aplicação.
Mario Miler
1
@ MRG não tenho certeza se ainda é um problema para você, mas há OSRM (C ++) e GraphHopper (Java). Tanto a escala de gráficos mundiais e ex GraphHopper precisa sob 1gb para a Alemanha (onde eu sou o autor de)
Karussell
Karussell, obrigado pela informação! Eu já havia encontrado o OSRM, mas o GraphHopper é novo para mim.
Mrg
0

Você também pode dar uma olhada no nosso pacote RW Net 4 (www.routeware.dk). Ele pode fazer cálculos de caminho mais curto usando A * diretamente de um arquivo SHP. O pacote básico de € 500 parece suficiente para suas necessidades.

Uffe Kousgaard
fonte
Obrigado por sua resposta rápida, mas meu projeto ainda está em uma fase em que não tenho certeza se merece gastar dinheiro agora. Também tenho o pgrouting trabalhando nos meus dados, então por enquanto esse desconhecido foi abordado.
mrg