Warum gibt pgRouting nicht den besten Pfad zurück?

9

Lassen Sie den nächsten Teil eines Diagramms:

Geben Sie hier die Bildbeschreibung ein Wenn ich die Funktion shortest_path zwischen den Punkten A und B verwende, habe ich den blauen Pfad erhalten. Warum passiert das?

postgis postgresql pgrouting José Alejandro
quelle
In der Erklärung habe ich einen Fehler gemacht, ist rot blau nicht rot, sorry!
José Alejandro

Antworten:

7

So verhält sich shortest_path (Dijkstra-Algorithmus) in pgRouting. Wenn es zwei Kanten mit derselben Quelle und demselben Ziel gibt, wird eine zufällige (um genau zu sein: die erste, die aus der Datenbank stammt) verwendet. Ich kenne keine Lösung dafür, aber es gibt einige Problemumgehungen.

Wenn möglich, sollten Sie eine dieser Kanten in zwei teilen. Ich habe es nicht getestet, aber es sollte dieses Verhalten beheben.

Eine andere Lösung für den Fall, dass Sie Ihren Datensatz nicht ändern können. Fügen Sie Ihrer Tabelle das Feld 'kürzer_alternativ' hinzu. Beispielabfrage, ändern Sie sie an Ihre Bedürfnisse. Ich hoffe es erklärt die Idee:

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)

Jetzt enthält die Kante '0.098' die ID der Kante '0.011'. Alle anderen Kanten haben im Feld kürzer_alternativ null. Nachdem Sie die Abfrage "kürzester Pfad" durchgeführt haben, überprüfen Sie das zurückgegebene Dataset. Wenn für eine Zeile das Feld "kürzer_alternativ" festgelegt ist, ändern Sie es.

user1702401
quelle
2

Das Problem wurde bereits in der vorherigen Antwort beschrieben. Es ist ein Problem von "vertexbasierten" Algorithmen für kürzeste Wege, die sich nur um Quelle und Ziel kümmern.

Der Issue-Tracker enthält ein Ticket und eine mögliche Lösung zum Ändern der Algorithmusimplementierung: https://github.com/pgRouting/pgrouting/issues/34 (Wäre schön, wenn jemand dies ausprobieren und eine Pull-Anfrage senden könnte; - )

Eine andere Möglichkeit besteht darin, "parallele Straßenverbindungen" wie zuvor erwähnt aufzuteilen. Oder Sie können den Shooting Star-Algorithmus verwenden, der von Kante zu Kante verläuft, damit er beide Straßenverbindungen "kennt".

Oder Sie können versuchen, das Straßennetz nach Kosten zu ordnen und dann nur unterschiedliche Kombinationen von Quelle und Ziel auswählen:

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
);

Dies setzt voraus, dass Sie nach der günstigsten Route suchen. Sonst musst du ORDER BY ... DESC.

Sie müssen ausprobieren, ob dies die Leistung beeinträchtigt.

dkastl
quelle
Gestern habe ich die trsp-Funktion erstellt und sehe aus, als hätte ich dieses Problem nicht. Trotzdem danke für die Erklärung !!!.
José Alejandro