Nous utilisons des cookies pour vous garantir la meilleure expérience sur notre site. Si vous continuez à utiliser ce dernier, nous considèrerons que vous acceptez l'utilisation des cookies. J'ai compris ! ou En savoir plus !.
banniere

Le portail francophone de la géomatique


Toujours pas inscrit ? Mot de passe oublié ?
Nom d'utilisateur    Mot de passe              Toujours pas inscrit ?   Mot de passe oublié ?

Annonce

Printemps des cartes 2024

#1 Wed 21 August 2019 09:57

guil31
Participant actif
Date d'inscription: 22 Jan 2013
Messages: 79

pgrouting 1.x vers 2.x / Temps de traitement

Bonjour,

Je suis en train de faire passer du code ?crit pour pgrouting 1.x vers 2.x.
J'ai donc substitu? mes fonctions assign_vertex_id() et shortest_path() par pgr_createTopology() et pgr_dijkstra().
Tout ce passe bien et mon code fonctionne correctement avec pgrouting 2.x.

Cependant, pour un m?me jeu de donn?es je passe de 1 minute 50 de temps de traitement ? 6 minutes 30.
Mon jeu de donn?es est un petit jeu de donn?es test et j'ai un peu peur de ce que ?a va donner pour des plus gros volumes de donn?es.
Je cherche donc ? optimiser mes temps de traitements sous pgrouting 2.x


Les fonction shortest_path() et pgr_dijkstra() n?utilisent-t-elles pas toutes les deux dijskra ?
=> Si oui pourquoi cette diff?rence de temps de traitement ?

Dans pgrouting 2.x j'ai vu qu'il existe plusieurs fonctions correspondant ? diff?rentes m?thodes de calcul du plus court chemin (dijkstra, Floyd-Warshall, A*)
=> Est_ce qu'il y a des algorithmes plus rapides que d'autres en temps de traitements ?

Merci d'avance pour vos retours
Claire

Hors ligne

 

#2 Thu 22 August 2019 10:01

tumasgiu
Membre
Lieu: Ajaccio
Date d'inscription: 5 Jul 2010
Messages: 1132

Re: pgrouting 1.x vers 2.x / Temps de traitement

Les fonction shortest_path() et pgr_dijkstra() n?utilisent-t-elles pas toutes les deux dijskra ?
=> Si oui pourquoi cette diff?rence de temps de traitement ?


Selon la doc, shortest_path utilise bien Dijkstra.
Peut être avez vous mal utilisé pgr_createtopology ?
Un index sur une des tables serait peut être judicieux
(couplé avec un VACUUM ANALYZE)

Dans pgrouting 2.x j'ai vu qu'il existe plusieurs fonctions correspondant ? diff?rentes m?thodes de calcul du plus court chemin (dijkstra, Floyd-Warshall, A*)
=> Est_ce qu'il y a des algorithmes plus rapides que d'autres en temps de traitements ?


En fait, cela dépend de la nature de votre graphe.
Par exemple, Floyd-Warshall fonctionne bien sur des graphes denses,
càd ceux dont le nombre d'arêtes est proche du nombre maximum d'arête possible.

Dernière modification par tumasgiu (Thu 22 August 2019 10:20)

Hors ligne

 

#3 Mon 26 August 2019 17:11

guil31
Participant actif
Date d'inscription: 22 Jan 2013
Messages: 79

Re: pgrouting 1.x vers 2.x / Temps de traitement

En creusant je me suis rendu compte que ce n'etait pas pgrouting qui me faisait perdre du temps entre postgres 9.1 et 9.5.
Comme certains jeux de donnees etaient volumineux, le code avait ete optimise pour travailler par zone.
Le graphe etait construit sur l'ensemble du jeu de donnees mais ensuite il y avait une selection par intersection spatiale avec une couche de polygones pour ne travailler que par zone.
C'est cette requete d'intersection spatiale qui en passant de postgres 9.1 a 9.5 prenait plus de temps.

La requete spatiale etait du type

Code:

select mon_routing.edge_id,mon_routing.id,mon_routing.source,mon_routing.target,mon_routing.cost,mon_routing.iti,mon_routing.the_geom 
from mon_routing , mes_zones
where ST_Buffer(mes_zones.the_geom, 1000) && mon_routing.the_geom 
  and ST_Intersects(mon_routing.the_geom,ST_Buffer(mes_zones.the_geom, 1000)) IS TRUE 
  and mes_zones.zone_id = '1'

J'ai reecrit la requete de la facon suivante:

Code:

select mon_routing.edge_id,mon_routing.id,mon_routing.source,mon_routing.target,mon_routing.cost,mon_routing.iti,mon_routing.the_geom 
from mon_routing , mes_zones
where mes_zones.zone_id = '1'
  and st_dwithin(mes_zones.geom, mon_routing.geom, 1000)

Et j'ai gagne un temps phenomenal en 9.5 et aussi en 9.1
Par contre je ne sais pas pourquoi la requete d'origine prenait plus de temps en 9.5 qu'en 9.1
(Il faudrait peut-etre modifier le titre du sujet)

Concernant l'algorithme le plus adapte pour mon jeu de donnees, mes donnees sont assez simple.
Il s'agit d'un reseau FTTH. En general, il n'y a qu'un seul itineraire possible par couple [origine, destination].

Dernière modification par guil31 (Mon 26 August 2019 17:17)

Hors ligne

 

#4 Mon 26 August 2019 17:45

tumasgiu
Membre
Lieu: Ajaccio
Date d'inscription: 5 Jul 2010
Messages: 1132

Re: pgrouting 1.x vers 2.x / Temps de traitement

Et j'ai gagne un temps phenomenal en 9.5 et aussi en 9.1
Par contre je ne sais pas pourquoi la requete d'origine prenait plus de temps en 9.5 qu'en 9.1
(Il faudrait peut-etre modifier le titre du sujet)


Vous pouvez essayer de récupérer le plan des deux requêtes avec EXPLAIN,
pour voir en quoi elles différent.

Concernant l'algorithme le plus adapte pour mon jeu de donnees, mes donnees sont assez simple.
Il s'agit d'un reseau FTTH. En general, il n'y a qu'un seul itineraire possible par couple [origine, destination].


Oui donc j'imagine que votre graphe doit être creux, donc Dijkstra est indiqué.
A* donnera peut être de meilleures performances, mais ne donnera pas forcement 
le chemin optimal si l'heuristique n'est pas bonne.

Hors ligne

 

Pied de page des forums

Powered by FluxBB