Wie berechnet man das kleinste Netzwerk, das alle Punkte mit PostGIS verbindet?

13

Ich habe eine Reihe von Postgis-Skripten, die zwei Tabellen erzeugen - eine aus einer Reihe von Punkten und die zweite aus einer Reihe von Straßen, die sie umgeben. Alle Daten befinden sich in der gleichen Projektion und beide Ausgaben werden mit postgis 2.1 in postgres 9.2-Tabellen gespeichert

Die Verfugungstopologie des Straßennetzes wurde erstellt und die Punktetabelle enthält eine Spalte mit dem nächstgelegenen Straßensegment.

Ich möchte dann eine Teilmenge des Straßennetzes generieren, die das kleinste Netzwerk darstellt, das alle Punkte mit einem Minimum Spanning Tree verbindet. Das Straßennetz ist ungerichtet und die Kosten sind einfach die Streckenlänge.

Ich kann dies in QGIS / Grass mit der v.net-Familie von Modulen tun, aber im Idealfall möchte ich diesen letzten Schritt auch in SQL beibehalten.

Ich habe mir die neue apspWarshall-Postgis-Funktion angeschaut, bin aber ratlos darüber, wie sie dazu angeregt werden kann, ihre Energie auf das Verbinden der Punkte und nicht auf das gesamte Netzwerk zu konzentrieren.

Dies ist das kurze Skript, das ich zusammengestellt habe, um ein Framework zur Lösung dieses Problems zu erstellen, aber ich kann nicht erkennen, wo es möglich ist, die Funktion zu fokussieren, um mit einer Teilmenge der Kanten zu beginnen.

SELECT seq, id1 AS node, id2 AS edge, cost, the_geom
FROM   pgr_apspWarshall('SELECT gid AS id, 
                                source, 
                                target, 
                                st_length(the_geom) AS cost 
                         FROM   road_network
                        ',
                        false, false
                       ) AS tree
JOIN   road_network As roads
ON     tree.id2 = roads.gid

Bei Problemen mit einem einzelnen Pfad und kürzesten Pfaden fragt die Funktion nach dem Anfang und dem Ende, aber anscheinend nicht bei allen Punktproblemen. Ebenso erwarten der v.net.spanningtree und der v.net.steiner in Grass eine Reihe von Punkten und Linien als ein kombiniertes Netzwerk, mit dem gearbeitet werden kann.

Hat jemand einen Vorschlag, wie das in PostGIS geht?

Adrian
quelle
Ich bin mir nicht sicher, ob ich die Frage verstehe, aber hilft Ihnen der docs.pgrouting.org/2.0/de/src/tsp/doc/index.html#pgr-tsp Algorithmus für reisende Verkäufer?
Simplexio
1
Vielen Dank. Ich fürchte mich nicht wirklich. Der reisende Verkäufer geht linear von einer Reise von a nach b nach c usw. aus. Was ich will, ist das minimale Netzwerk, das jeden Punkt effizient miteinander verbindet, sodass jeder Punkt eine Reise zu einem anderen Punkt in dem Wissen beginnen kann, dass es keine überflüssigen Pfade gibt, die verloren gehen können. Auf anderen Plattformen wird dies normalerweise mit einer Minimum Spanning Tree-Funktion, Steiner Tree ( en.wikipedia.org/wiki/Steiner_tree_problem ) oder ähnlichem durchgeführt. Wenn Sie möchten, ist TSP großartig für das Logistikunternehmen, aber ich möchte die Straßen planen, die sie nutzen würden.
Adrian

Antworten:

2

Diese Antwort ist nicht vollständig oder getestet, aber versuchen Sie es so:

laut fragen / 39210 :

with index_query as (
SELECT
        ,ST_Distance(i.geom, i.b_geom) AS dist
        ,ST_MakeLine(i.geom, i.b_geom) as geom
FROM(
SELECT
        ,a.geom
        ,b.geom AS b_geom
        ,rank() OVER (PARTITION BY a.id ORDER BY ST_Distance(a.centroid_geom, b.the_geom)) AS pos
FROM points a, points b 
WHERE a.id <> b.id) i
WHERE pos = 1
) select ST_Union(geom) from index_query;

Ich denke, das ist nicht sehr effizient.

youseeus
quelle
Wirklich zu schätzen - danke. Dies hat mir einige neue Perspektiven eröffnet, an die ich nicht gedacht hatte. Dieser Code findet die nächsten nicht verbundenen Nachbarn aus einer Punktetabelle. Die zusätzliche Komplikation besteht darin, dass die Punkte in meinem Fall über ein Netzwerk von Linienfolgen verbunden sind. Ich frage mich jedoch, ob ich die ST_Distance-Abfrage durch eine pgRouting-Straßenentfernung ersetzen kann, obwohl sie erheblich langsamer wäre als eine nicht weitergeleitete Punktabfrage.
Adrian
2

@Adrian, ich bin mit den Ergebnissen der Verfugung wirklich nicht vertraut, aber die Dokumentation ist sehr detailliert. Meine Antwort basiert auf einer zweistufigen Funktion, die in SQL sehr unzulänglich ist, aber [wahrscheinlich] die Ergebnisse liefert. Diese [ungetestete] Lösung optimiert NICHT den besten Ausgangspunkt, sondern reduziert das gesamte Streckennetz auf die Kanten, die alle Haltestellen verbinden, und führt dann effizient zu allen Haltestellen.

Schritt 1 (Unterauswahl einer Straßennetz-Teilmenge, die alle Haltestellen verbindet) Mit dieser Routing-Funktion werden mehrere Pfade (K Dijkstr-Pfad) zurückgegeben, die (bei Kosten <> -1) tatsächlich alle Ihre Pfade verbinden hört auf.

SELECT id1 as path, st_astext(st_linemerge(st_union(b.the_geom))) as the_geom
FROM pgr_kdijkstraPath(
SELECT id, source, target, cost FROM edge_table’,
min(all_your_stop_ids), [array_of_all_your_stop_ids], false, false
) a,
edge_table b
WHERE a.id3=b.id
GROUP by id1
ORDER by id1

Das Problem, das ich hier habe, ist die Syntax zum Zusammenstellen eines Arrays aus Ihrer Stopptabelle, da sie in der Frage nicht wirklich beschrieben wurde. Nehmen wir jedoch an, dass die SQL-Syntax dieses Array zusammenstellen kann und dass der minimale ID-Stopp der Ausgangspunkt für alle K-Pfade zu den verbleibenden Zielstopps sein sollte.

Schritt 2 (endgültige Auswahl der Mindestpfade auf der Grundlage der oben genannten Teilmenge der Straßennetzpfade, die alle Haltestellen verbinden) Dies ist im Wesentlichen das, womit Sie begonnen haben, aber ich schlage vor, dass Sie Ihr Straßennetz mit dem anfänglichen Ergebnis auf id1 (Pfad) gleich verbinden. so dass nur die Teilmenge der Straßen im endgültigen Field-Warshal-Routing verwendet wird :

SELECT seq, id1 AS node, id2 AS edge, cost, the_geom
FROM   pgr_apspWarshall('SELECT R.gid AS id, 
                                R.source, 
                                R.target, 
                                st_length(R.the_geom) AS cost 
             FROM   road_network AS R JOIN
                   (SELECT id1 as path
                     FROM pgr_kdijkstraPath(
                            ’SELECT id, source, target, cost FROM edge_table’,
                            min(all_your_stop_ids), 
                            [array_of_all_your_stop_ids], false, false
                           ) a,
                     edge_table b
                    WHERE a.id3=b.id
                    GROUP by id1
                    ORDER by id1
                        ',
                        false, false
                  ) AS  Just_K_Paths
         on R.id1 = just_K_paths.id1',       /* this join reduces R down to K paths */
         false, false
        ) AS tree
  JOIN   road_network As roads
  ON     tree.id2 = roads.gid

Fazit: Die innere Routing-Abfrage k_dijkstra_path reduziert das gesamte Straßennetz auf die Pfade, die alle Haltestellen verbinden, und die äußere Routing-Abfrage fField_Warshal verwendet nur diese Kanten-IDs, um die Abfrage zur Pfadoptimierung zu lösen.

JasonInVegas
quelle
Danke - das ist sehr hilfreich und mein erster neuer Lead. Ich schaue es jetzt an. Ich versuche nur herauszufinden, wie die minimale Stopp-ID und das Array generiert werden. Ich habe eine Tabelle mit den erforderlichen IDs, aber 'SELECT min (id) FROM Node_Table' und 'SELECT ARRAY [id] FROM Node_Table' führen zu Syntaxfehlern, wenn sie in Ihren Code eingefügt werden sicher)
Adrian