Pourquoi pgRouting ne retourne-t-il pas le meilleur chemin?

9

Soit la partie suivante d'un graphique:

entrez la description de l'image ici Lorsque j'utilise la fonction shortest_path entre les points A et B, j'ai le chemin bleu. Pourquoi cela arrive-t-il?

postgis postgresql pgrouting José Alejandro
la source
Dans l'explication, j'ai fait une erreur, c'est rouge bleu pas rouge, désolé!
José Alejandro

Réponses:

7

C'est ainsi que shortest_path (l'algorithme de Dijkstra) se comporte dans pgRouting. S'il y a deux bords avec la même source et la même cible, un aléatoire (pour être précis: le premier, qui provient de la base de données) est utilisé. Je ne connais aucune solution à cela, mais il existe des solutions de contournement.

Si possible, vous devez diviser l'un de ces bords en deux. Je ne l'ai pas testé, mais cela devrait corriger ce comportement.

Autre solution pour le cas où vous ne pouvez pas modifier votre jeu de données. Ajoutez le champ 'short_alternative' à votre table. Exemple de requête, modifiez-le selon vos besoins. J'espère que cela explique l'idée:

UPDATE roads t1
SET shorter_alternative = t2.id
FROM roads t2
WHERE 
((t2.source = t1.source AND t2.target = t1.target) OR
(t2.source = t1.target AND t2.target = t1.source)) AND
(t2.length < t1.length)

Maintenant, le bord «0,098» contiendra l'identifiant du bord «0,011». Tous les autres bords auront null dans le champ short_alternative. Après avoir effectué la requête shortest_path, vérifiez le jeu de données renvoyé - si des lignes ont un champ short_alternative défini, modifiez-le.

user1702401
la source
2

Le problème a déjà été décrit dans la réponse précédente. C'est un problème d'algorithmes de chemin le plus court "basés sur des sommets", qui ne se soucient que de la source et de la cible.

Il y a un ticket dans le tracker de problème et une solution possible pour changer l'implémentation de l'algorithme: https://github.com/pgRouting/pgrouting/issues/34 (Ce serait bien si quelqu'un pouvait l'essayer et envoyer une demande de tirage; - )

Une autre possibilité est de diviser les "liaisons routières parallèles" comme mentionné précédemment. Ou vous pouvez utiliser l'algorithme Shooting Star, qui route d'un bord à l'autre afin qu'il "connaisse" les deux liaisons routières.

Ou vous pouvez essayer de commander le réseau routier par coût, puis sélectionner uniquement des combinaisons distinctes de source et de cible:

SELECT * FROM shortest_path(
  'SELECT DISTINCT ON (source, target)
      gid as id,
      source::integer,
      target::integer,
      cost::double precision
    FROM ways ORDER BY source, target, cost',
  true,false
);

Cela suppose que vous recherchez l'itinéraire le moins cher. Sinon, vous devez ORDER BY ... DESC.

Vous devez essayer si cela affecte les performances.

dkastl
la source
Hier, j'ai créé la fonction trsp et je n'ai pas l'air d'avoir ce problème. Quoi qu'il en soit, merci pour l'explication !!!.
José Alejandro