#1 Thu 29 November 2007 10:28
- CarineS
- Participant occasionnel
- Date d'inscription: 19 Sep 2007
- Messages: 18
Performances de PgRouting
Bonjour à tous,
Je travaille actuellement sur un projet d’optimisation d’itinéraire pour le transport de conteneurs.
Je suis en charge de trouver des solutions libres et je me suis intéressée au module PgRouting.
J’aurai aimé avoir des infos sur ses performances.
En fait, dans l’idéal, il faudrait que je suis puisse calculer une distance routière entre n’importe quel point du globe en moins de 2 sec.
Cela est-il envisageable ?
Quels sont les moyens d'optimiser les temps de réponses ?
Je vous remercie d’avance pour vos réponses.
Carine S.
Hors ligne
#2 Thu 29 November 2007 13:30
- Cartosig
- Participant assidu
- Date d'inscription: 16 Oct 2006
- Messages: 222
Re: Performances de PgRouting
Je ne connais pas PgRouting, mais concernant les temps de réponse d'un service de calcul d'itinéraire les réponses sont multiples. Celà va dépendre de plusieurs facteurs :
- complexité du graphe (nombre d'arrêtes et de jonctions)
- complexité de l'algorithme de propagation (nombre de paramètres pris en compte)
- software : quelle BDD ? quel OS ?
- hardware : sur quelle plateforme tourne le service ?
Je supose que le fait d'utiliser PgRouting répond déjà implicitement à certaines de ces questions...
Ca m'interesserait de le savoir d'ailleurs !
Hors ligne
#3 Thu 29 November 2007 16:27
- Guillaume Sueur
- Participant assidu
- Lieu: Toulouse
- Date d'inscription: 23 Sep 2005
- Messages: 331
- Site web
Re: Performances de PgRouting
Bonjour,
PgRouting est un excellent module d'itinéraire qui offre la possibilité
d'utiliser trois algorithmes différents, ce qui est intéressant. Mais la
reponse à vos attentes côté performances ne dépendant pas que de
l'outil, mais aussi, et même surtout, du réseau routier que vous allez
utiliser. Si celui-ci ne contient que les routes principales ça restera
raisonnable, mais si vous intégrez tous les niveaux routiers, ce n'est
plus la même chose.
Reste que tout ceci n'a d'intérêt que s'il vous faut des distances
précises entre n'importe quels points du globe. Si un marge d'erreur est
acceptable pour vous, il existe des moyens beaucoup plus simples d'avoir
cette approximation.
Cordialement
Guillaume Sueur
Hors ligne
#4 Thu 29 November 2007 16:32
- Sylvain T.
- Membre
- Lieu: Musée de l'Homme, Paris France
- Date d'inscription: 7 Sep 2005
- Messages: 742
- Site web
Re: Performances de PgRouting
Bonjour,
Je supose que le fait d'utiliser PgRouting répond déjà implicitement à certaines de ces questions...
Oui
Algorithmes : http://www.postgis.fr/node/360
Software : http://www.postgis.fr/node/361
Plus d'infos sur le Wiki officiel
Cordialement,
Sylvain
Hors ligne
#5 Fri 30 November 2007 17:58
- CarineS
- Participant occasionnel
- Date d'inscription: 19 Sep 2007
- Messages: 18
Re: Performances de PgRouting
Bonjour à tous,
Merci pour vos réponses qui me permettent de poser de nouvelles questions
Est-ce qu’il vous parait envisageable de définir des « stratégies » de calcul en fonction de la distance à parcourir ?
Ex :
- Pour une distance inférieure à 50 km : On se base sur un réseau routier fin et on intègre éventuellement les restrictions de parcours (tunnels, sens unique etc.)
- Pour une distance inférieure à 1000 km : On calcule de façon fine sur les 20 kilomètres autour du point de départ et autour du point d’arrivée. Pour le reste, on se base sur le réseau routier principal.
- Pour une distance supérieure à 1000 km : On utilise le réseau routier principal. On réalise ensuite des approximations.
Quels sont alors « les moyens beaucoup plus simples » dont vous parlez pour obtenir ces approximations ? Quelles sont les marges d’erreur ?
Merci d’avance et bon week-end !
Carine
Hors ligne
#6 Sun 02 December 2007 19:47
- Guillaume Sueur
- Participant assidu
- Lieu: Toulouse
- Date d'inscription: 23 Sep 2005
- Messages: 331
- Site web
Re: Performances de PgRouting
Bonsoir,
Ce n'est pas si évident. Même pour une distance < 50 km, si vous voulez
utiliser le réseau le plus fin et que ce calcul doit pouvoir s'effectuer
n'importe où dans le monde, votre graphe n'en reste pas moins
gigantesque et très lourd pour les calculs. On pourrait imaginer des
graphes nationaux, mais alors cela interdirait un itinéraire fin
transfrontalier. Peut-être cela vous suffit-il.
Les moyens beaucoup plus simples, ou disons le moyen le plus simple, est
de prendre la distance à vol d'oiseau (calculée sur le sphéroïde pour
les grands distances) multipliée par 1.4142 (racine de 2), puis à
nouveau par un autre coefficient de pondération :
- en milieu urbain dense, la distance maximale à parcourir entre deux
points (sauf cas extrêmes de rues tortueuses) est de faire le trajet en
faisant un angle droit, la distance initiale est alors multipliée par la
racine de 2 (car la diagonale d'un carré de 1 de côté est racine de 2).
- en milieu moins dense, on peut pondérer ce facteur initial de manière
à limiter sont effet. Pour traverser les Etats-Unis par exemple, on a
environ 4100 km de San Francisco à Washington à vol d'oiseau, et 4550
par la route. Le rapport n'est donc que de 1.1.
Donc, si votre problématique tient surtout à du calcul de distance (ce
que vous sembliez indiquer dans votre premier mail) entre des points
très éloignés, ça peut être très simple.
Mais comme vous avez aussi évoqué dernièrement les restrictions de
parcours et des itinéraires fins, votre besoin est peut-être plus large.
Il n'empêche que, à mon sens, vous allez devoir trouver quelques
astuces, au-delà du simple choix de la solution logicielle car :
- tous les pays du monde ne sont pas couverts par NTQ ou TA
- le recollement de ces données en une seule base mondiale peut faire
froid dans le dos.
- les performances dépendront surtout de l'architecture système que
vous mettrez en place pour faire tourner tout ça.
Je ne sais pas pour qui vous travaillez, mais j'espère qu'ils ont les
moyens ;-)
Cordialement,
Guillaume SUEUR
Hors ligne
#7 Sun 02 December 2007 20:20
- ChristopheV
- Membre
- Lieu: Ajaccio
- Date d'inscription: 7 Sep 2005
- Messages: 3175
- Site web
Re: Performances de PgRouting
Bonjour,
Concernant la stratégie de calcul :
http://georezo.net/forum/viewtopic.php?id=49112
A+
Christophe
Christophe
L'avantage d'être une île c'est d'être une terre topologiquement close
Hors ligne