Le portail francophone de la géomatique

bruhnild · Sat 24 June 2017 19:54

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?

Nicolas Ribot · Sat 24 June 2017 21:47

Bonsoir,

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

Nicolas

tumasgiu · Sun 25 June 2017 21:15

C'est ce que je me disais aussi,

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

tqhien · Mon 26 June 2017 12:18

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.

bruhnild · Tue 27 June 2017 07:18

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.

tqhien · Tue 27 June 2017 17:06

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.

bruhnild · Wed 28 June 2017 12:12

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.

Nicolas Ribot · Wed 28 June 2017 12:43

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

bruhnild · Wed 28 June 2017 13:30

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.

atilio · Wed 28 June 2017 15:07

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

tqhien · Thu 29 June 2017 09:51

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.

tqhien · Thu 29 June 2017 10:03

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

Communauté	Ressources	L'emploi	Le marché	L'association	Fils RSS
Forum Blogs Wiki Planet Sites amis	Agenda Biblio Fiches AMO-CNIG Paris PCGIS Téléchargements	Offres d'emploi Banque de CV Formations Démarche Métiers	Geo-Entreprises Geo-Communiqué Appels d'offres	L'association Qui sommes-nous ? Nous aider Bienfaiteurs Partenaires Historique Statuts	Tout le site Job Géomatique Services GeoBlogs ...	Faire un don Mentions légales

Le portail francophone de la géomatique

Annonce

#1 Sat 24 June 2017 19:54

Pgrouting - itinéraire en deux temps

#2 Sat 24 June 2017 21:47

Re: Pgrouting - itinéraire en deux temps

#3 Sun 25 June 2017 21:15

Re: Pgrouting - itinéraire en deux temps

#4 Mon 26 June 2017 12:18

Re: Pgrouting - itinéraire en deux temps

#5 Tue 27 June 2017 07:18

Re: Pgrouting - itinéraire en deux temps

#6 Tue 27 June 2017 17:06

Re: Pgrouting - itinéraire en deux temps

Code:

Code:

Code:

Code:

Code:

#7 Wed 28 June 2017 12:12

Re: Pgrouting - itinéraire en deux temps

Code:

Code:

#8 Wed 28 June 2017 12:43

Re: Pgrouting - itinéraire en deux temps

Code:

#9 Wed 28 June 2017 13:30

Re: Pgrouting - itinéraire en deux temps

Code:

#10 Wed 28 June 2017 15:07

Re: Pgrouting - itinéraire en deux temps

#11 Thu 29 June 2017 09:51

Re: Pgrouting - itinéraire en deux temps

Code:

#12 Thu 29 June 2017 10:03

Re: Pgrouting - itinéraire en deux temps

Code:

Code:

Code:

Pied de page des forums