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

Suite à un problème technique intervenu entre le 22 et le 23 mars, nous avons du procéder dans la soirée du 25 mars, à la restauration de la base de données du 24 mars (matinée).

En clair, nous avons perdu vos contributions et inscriptions du dimanche 24 et du lundi 25 mars.
Nous vous prions de nous excuser.

#1 Sat 24 June 2017 19:54

bruhnild
Participant actif
Lieu: Lyon
Date d'inscription: 7 Jun 2014
Messages: 130

Pgrouting - itinéraire en deux temps

Bonjour,

Je travaille actuellement sur une problématique d'optimisation de tournée de facteurs.
J'ai réussi à générer une série d'itinéraires partant d'un seul point (la poste) vers tous les points relais connus avec la fonction pgr_kdijkstraPat (voir : http://docs.pgrouting.org/2.0/fr/src/kd … kdijkstra)
Aujourd'hui je cherche à générer un itinéraire unique qui partirait de la poste pour aller desservir un à un tous les points relais en prenant en compte la notion de cout distance entre chacun d'eux.

Mon problème se décompose en deux temps :

1) Trouver un algorythme avec Pg Routing permettant de faire du calcul d'itinéraire en plusieurs temps (comme le fait Google Maps par exemple);
2) Trouver l'ordre de desserte entre les différents points relais.

Pourriez vous m'aider?

Hors ligne

 

#2 Sat 24 June 2017 21:47

Nicolas Ribot
Membre
Lieu: Toulouse
Date d'inscription: 9 Sep 2005
Messages: 1534

Re: Pgrouting - itinéraire en deux temps

Bonsoir,

C'est pas TSP l'algo qu'il vous faut ? http://pgrouting.org/docs/1.x/tsp.html

Nicolas

Hors ligne

 

#3 Sun 25 June 2017 21:15

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

Re: Pgrouting - itinéraire en deux temps

C'est ce que je me disais aussi,

mais j'ai peur de ne pas vraiment comprendre le besoin.

Hors ligne

 

#4 Mon 26 June 2017 12:18

tqhien
Participant actif
Lieu: Clamart
Date d'inscription: 22 Apr 2011
Messages: 78

Re: Pgrouting - itinéraire en deux temps

Bonjour,

J'avais été une fois confronté au même type de problématique : optimiser une tournée avec contrainte de charge/d'emport. J'avais trouvé le logiciel OpenSource Optaplanner (https://www.optaplanner.org/) qui permet avec un peu de codage, de définir les points à desservir, leur besoin, la capacité max du véhicule transporteur, etc. En sortie, on peut avoir 1,2, ou plus tournées repassant par le point de départ par exemple.

Remarque : il semble que dans ce type d'algo, la distance à vol d'oiseau est tout aussi efficace mais bien plus rapide en calculs que de faire un véritable routage sur le réseau.

Hien.

Hors ligne

 

#5 Tue 27 June 2017 07:18

bruhnild
Participant actif
Lieu: Lyon
Date d'inscription: 7 Jun 2014
Messages: 130

Re: Pgrouting - itinéraire en deux temps

Bonjour,

Merci pour vos réponses.
Nicolas Ribot, je ne vois pas comment utiliser TSP pour parvenir au résultat souhaité.
J'ai joins une pièce jointe qui permet de mieux comprendre mon besoin.


Le calcul d'itinéraire a été réalisé sur ce site : https://gebweb.net/optimap/
On y rentre une série de coordonnées en longitude et latitude et on choisit le "Fastest Round Trip".
Cela nous permet d'obtenir une proposition d'itinéraire en partant du point 1 (la poste) et qui va desservir les points relais tout autour.
A partir le 15 points, le tracé n'est pas garanti optimal..
Cette méthode n'est pas satisfaisante selon moi car je ne sais pas encore comment exploiter les résultats en sortie.
C'est pour cela que j'aimerais réussir à trouver une solution sous Pg routing.

Bonne journée.


Fichier(s) joint(s) :
Pour accéder aux fichiers vous devez vous inscrire.

Hors ligne

 

#6 Tue 27 June 2017 17:06

tqhien
Participant actif
Lieu: Clamart
Date d'inscription: 22 Apr 2011
Messages: 78

Re: Pgrouting - itinéraire en deux temps

Pour utiliser l'algo TSP de pgrouting : il faut procéder en deux temps.

Construire la requête des noeuds (variable sql dans la doc) : elle renvoit 3 colonnes : source_id, x et y. Il faut donc traduire tes champs en ces trois noms.

Par exemple :

Code:

SELECT mon_noeud_id as source_id, mon_noeud_x as x, mon_noeud_y as y from mon_reseau ;

ou autre exemple :

Code:

SELECT mon_noeud_id as source_id, ST_X(mon_noeud_geom) as x, ST_Y(mon_noeud_geom) as y from mon_reseau ;

Les noeuds à desservir sont à mettre dans une liste 'n1,n2,n3,n4'. Tu peux la générer selon la requête suivante par exemple:

Code:

SELECT string_agg(CAST(mon_noeud_id as varchar), ',') FROM mes_cibles

Si le noeud de départ a pour identifiant mon_noeud_id = xxx, la requête a faire est la suivante :

Code:

SELECT * from tsp ('SELECT mon_noeud_id as source_id, ST_X(mon_noeud_geom) as x, ST_Y(mon_noeud_geom) as y from mes_noeuds_a_desservir' , <- ici c'est la requete du réseau de noeud
'SELECT string_agg(CAST(mon_noeud_id as varchar), ',') FROM mes_cibles' , <- ici la liste des noeuds, soit par requete, soit en dur
xxx) <- ici le noeud de départ

En sortie, le numéro de la ligne correspond à l'ordre de passage du vertex_id (qui vaut source_id = mon_noeud_id) donc pour l'intégrer dans la requête, il suffit d'un :

Code:

SELECT a.*, 
row_number() OVER () as rnum
FROM tsp (<les deux requêtes et le noeud de départ>) as a

Bon, il y a peut-être des fautes de frappe dans ce que j'ai écrit, n'ayant pas de réseau à tester sous la main, mais dans le principe, c'est ça.

Hien.

Hors ligne

 

#7 Wed 28 June 2017 12:12

bruhnild
Participant actif
Lieu: Lyon
Date d'inscription: 7 Jun 2014
Messages: 130

Re: Pgrouting - itinéraire en deux temps

Bonjour,

Tout d'abord, merci pour votre aide et exemples de requetes.

Cette requête fonctionne bien (avec un temps de calcul anormalement long - 22 minutes) mais juste d'un point (6) à l'autre (5)

Code:

  SELECT seq, id1, id2, round(cost::numeric, 2) AS cost
FROM pgr_tsp('SELECT node_id as id, longitude as x,latitude as y FROM noeuds_a_desservir  ORDER BY id', 6, 5);

Tandis que cette requete, reprise de celle que vous m'indiquez dans votre dernier message ne fonctionne pas avec mes données :

Code:

SELECT * 
from pgr_tsp ('SELECT node_id as source_id, longitude as x, latitude as y from noeuds_a_desservir' , 
'SELECT string_agg(CAST(node_id as varchar), ',') FROM mes_cibles' , 6987)

Sauriez vous me dire d'où vient le problème?

Marine.

Hors ligne

 

#8 Wed 28 June 2017 12:43

Nicolas Ribot
Membre
Lieu: Toulouse
Date d'inscription: 9 Sep 2005
Messages: 1534

Re: Pgrouting - itinéraire en deux temps

bruhnild a écrit:

Tandis que cette requete, reprise de celle que vous m'indiquez dans votre dernier message ne fonctionne pas avec mes données :

Code:

SELECT * 
from pgr_tsp ('SELECT node_id as source_id, longitude as x, latitude as y from noeuds_a_desservir' , 
'SELECT string_agg(CAST(node_id as varchar), ',') FROM mes_cibles' , 6987)

Sauriez vous me dire d'où vient le problème?

Marine.


Bonjour,

Pensez à mettre le message d'erreur, et éventuellement un petit jeu de données permettant de reproduire le problème.
Une requête seule ne permet pas de voir ou se situe le pb (à moins d'une erreur de syntaxe évidente).

Nicolas

Hors ligne

 

#9 Wed 28 June 2017 13:30

bruhnild
Participant actif
Lieu: Lyon
Date d'inscription: 7 Jun 2014
Messages: 130

Re: Pgrouting - itinéraire en deux temps

Voici le message d'erreur pour cette requete :

Code:

SELECT * 
from pgr_tsp ('SELECT node_id as source_id, longitude as x, latitude as y from noeuds_a_desservir' , 
'SELECT string_agg(CAST(node_id as varchar), ',') FROM mes_cibles' , 6987)

ERREUR:  syntaxe en entrée invalide pour l'entier : « SELECT string_agg(CAST(node_id as varchar),  »
LINE 3: 'SELECT string_agg(CAST(node_id as varchar), ',') FROM mes_c...
        ^

********** Erreur **********

ERREUR: syntaxe en entrée invalide pour l'entier : « SELECT string_agg(CAST(node_id as varchar),  »
État SQL :22P02
Caractère : 113

J'ai également joins en PJ mon jeu de données  pour des tests éventuels.

Merci d'avance.

Marine.


Fichier(s) joint(s) :
Pour accéder aux fichiers vous devez vous inscrire.

Hors ligne

 

#10 Wed 28 June 2017 15:07

atilio
Participant actif
Lieu: Brest
Date d'inscription: 17 Jan 2006
Messages: 80

Re: Pgrouting - itinéraire en deux temps

est-ce qu'il ne serait pas plus approprié d'utiliser un array_agg au lieu du string_agg? Je pense que c'est une liste d'entiers et non de strings qui est utilisée par pgr_tsp

Hors ligne

 

#11 Thu 29 June 2017 09:51

tqhien
Participant actif
Lieu: Clamart
Date d'inscription: 22 Apr 2011
Messages: 78

Re: Pgrouting - itinéraire en deux temps

Je viens de voir qu'il y a une grosse modif des paramètres selon la version de pgrouting. Mes explications étaient valables pour la version 1.x.

Pour la version 2.x, c'est légèrement modifié : la première requête intègre tous les noeuds à desservir (idem qu'avant sauf que les champs sont id, x et y comme tu l'as indiqué Marine) Par contre, il suffit d'ajouter le noeud de départ (et éventuellement celui d'arrivée), donc la requête que tu trouves anormalement longue est pourtant la bonne, si tu souhaites passer par tous les noeuds du réseau. Or, ce sont plustôt tes cibles !

La requête serait plutôt celle-ci :

Code:

SELECT seq, id1, id2, round(cost::numeric, 2) AS cost
FROM pgr_tsp('SELECT node_id as id, longitude as x,latitude as y FROM mes_cibles  ORDER BY id', 6, 5);

Pour une tournée de 100 noeuds à desservir, le calcul se fait en 0.4s.

Hors ligne

 

#12 Thu 29 June 2017 10:03

tqhien
Participant actif
Lieu: Clamart
Date d'inscription: 22 Apr 2011
Messages: 78

Re: Pgrouting - itinéraire en deux temps

Autre précision : mon tableau résultat m'indique seulement l'ordre des noeuds à atteindre, les deux colonnes id1 (matrice de distance interne) et id2 (identifiant du noeud à atteindre) sont identiques -ici départ du noeud 50)

Code:

seq    id1    id2    cost
0    50    50    1466.10343482386
1    60    60    192.610186749464
2    59    59    774.945012095801
3    58    58    472.514839841867
4    16    16    735.235782257773
5    14    14    568.802381746603
6    17    17    261.616502798908
7    15    15    736.156584914652
8    3    3    512.742947608021
9    2    2    983.630360151605
10    4    4    690.105171508342

Pour avoir  sur la même ligne l'id2 de la ligne précédente, il y a la fonction window de postgresql :

Code:

select seq, id1, id2, cost, lag(id2)  OVER (ORDER by seq) as id_prec
from pgr_tsp (...)

ce qui donne

Code:

seq    id1    id2    cost    id_prec
0    50    50    1466.10343482386    
1    60    60    192.610186749464    50
2    59    59    774.945012095801    60
3    58    58    472.514839841867    59
4    16    16    735.235782257773    58
5    14    14    568.802381746603    16
6    17    17    261.616502798908    14
7    15    15    736.156584914652    17
8    3    3    512.742947608021    15
9    2    2    983.630360151605    3
10    4    4    690.105171508342    2

Hors ligne

 

Pied de page des forums

Powered by FluxBB