Suite

Aide au choix d'un moteur de routage adapté

Aide au choix d'un moteur de routage adapté


Je construis un système de planification d'itinéraire, mais je dois encore décider quel moteur de routage sous-jacent j'utiliserai. Jusqu'à présent, j'ai trouvé pgrouting et neo4j.

J'ai mon réseau de routes dans une base de données postgresql/postgis (importée à partir d'un shapefile). J'ai fait des requêtes pour extraire des nœuds (extrémités de chemins où vous devez prendre une décision dans quelle direction aller ou impasses) et pour extraire des bords (souvent constitués de plusieurs chemins consécutifs). Tous mes bords sont bidirectionnels.

Mon objectif principal est de calculer des itinéraires sur ce réseau à l'aide d'un algorithme A-star où distance = coût.

Mon sentiment me dit qu'une base de données de graphes comme neo4j est la voie à suivre (car elle semble être conçue à cet effet), mais ils ne semblent pas prendre en charge A-star par défaut et il n'y a pas non plus de sens réel de la géométrie . Il semble mieux adapté aux réseaux sociaux qu'aux cartes.

  • Est-ce que pgrouting répondrait à mes besoins ?
  • Est-il assez rapide pour les requêtes à la volée (+-2000 nœuds, +-4000 arêtes) ? Normalement, cela prendrait quelques ms pour A-star, mais je ne suis pas sûr de cette implémentation dans SQL.
  • Est-ce que pgrouting A-star me donne une liste de nœuds et d'arêtes ?
  • Dans la plupart des exemples que je vois à propos de pgrouting, je remarque qu'il y a généralement une liste de commandes après le calcul de l'itinéraire (comme "A X tournez à gauche, etc"). Est-ce que pgrouting produit ceci ou est-ce à partir d'un autre système?

J'espère que quelqu'un pourra me renseigner sur le système à choisir. Neo4j, pgrouting ou un autre système.


J'explore actuellement le même problème que vous, dans le cadre d'un mémoire de recherche. Avant de commencer à tester ces deux bases de données, j'avais la même présomption que vous. Cette base de données de graphes Neo4j serait une solution parfaite pour ce genre de problème. Et c'est partiellement le cas, mais avec beaucoup de problèmes.

Le premier problème est qu'A-Star n'est implémenté que si vous utilisez une base de données intégrée, et non via l'API REST (serveur). Si vous souhaitez utiliser Neo4j avec l'API REST, seul l'algorithme Dijkstra est pris en charge. Le deuxième problème concerne la mémoire matérielle requise pour Neo4j. Pour le routage (Dijkstra) sur des réseaux "plus grands", vous avez besoin de beaucoup de RAM. Pour un grand réseau, je veux dire quelque chose comme la taille de la base de données routière allemande OSM. J'ai exécuté mes tests sur un serveur RAM de 6 Go (c'est tout ce que j'ai actuellement) et seuls les réseaux plus petits pourraient être routés sans erreurs d'exception OutOfMemory. Les "petits" réseaux dans mes cas de test sont par exemple la base de données routière OSM pour l'Autriche ou la Croatie. Requêtes simultanées que je n'ai toujours pas testées avec Neo4j.

Tous ces problèmes n'existent pas dans pgRouting. La mémoire n'est pas un tel problème, mais les requêtes simultanées augmentent la quantité de mémoire nécessaire. Par exemple, si vous avez deux requêtes simultanées, une double quantité de mémoire est nécessaire. Ce n'était pas un problème même pour un ensemble de données OSM en Allemagne, pgRouting a acheminé sans aucun problème toutes les demandes simultanées.

Performances : dans la plupart des cas, Neo4j surpasse pgRouting. Mais seulement s'il y a suffisamment de mémoire pour l'ensemble de données donné et si tous les nœuds et relations sont en mémoire (démarrage à chaud). L'augmentation/la diminution des performances dépend de nombreux facteurs, mais principalement de la taille du réseau et de la distance (sauts) entre le nœud source et le nœud cible.

La taille de votre réseau est assez petite, vous ne devriez donc pas avoir de problèmes de mémoire. Neo4j n'est probablement pas un mauvais choix mais vous devez vous adapter à un modèle de données "un peu" différent de celui des bases de données relationnelles standard.

Pour répondre à vos questions :

  • Dans pgRouting, vous n'avez pas à vous soucier de l'implémentation d'AStar dans SQL, qui est déjà implémentée.
  • Oui, pgRouting peut vous donner une liste de nœuds et d'arêtes
  • Je ne pense pas que pgRouting puisse vous donner de telles informations sans un travail personnalisé autour des requêtes. Mais peut-être que je me trompe, peut-être que quelqu'un l'a fait et peut vous aider davantage sur cette question.

Je ne sais pas si cela vous aidera directement, mais l'un des serveurs de routage les plus rapides que j'ai trouvé est osm2po. Il fonctionne avec le jeu de données OSM et est assez rapide. Seul dijkstra est actuellement implémenté, mais le développeur a également annoncé AStar. J'espère qu'une partie de cela vous aidera. :)


Vous pouvez également consulter notre package RW Net 4 (www.routeware.dk). Il peut effectuer ces calculs de chemin le plus court en utilisant A* directement à partir d'un fichier SHP. Le forfait Basic à 500€ semble suffisant pour vos besoins.