Bagaimana cara menghitung jaringan terkecil yang menghubungkan semua titik menggunakan PostGIS?

13

Saya memiliki satu set skrip postgis yang menghasilkan dua tabel - satu dari set poin dan yang kedua set jalan yang mengelilinginya. Semua data dalam proyeksi yang sama dan kedua output disimpan dalam tabel postgres 9.2 dengan postgis 2.1

Topologi pgrouting dari jaringan jalan telah dibuat dan tabel poin memiliki kolom yang berisi segmen jalan terdekat.

Saya ingin menghasilkan subset dari jaringan jalan yang mewakili jaringan terkecil yang menghubungkan semua titik menggunakan sesuatu seperti pohon spanning minimum. Jaringan jalan tidak diarahkan, dan biaya hanyalah panjang rute.

Saya bisa melakukan ini di QGIS / Grass menggunakan keluarga modul v.net tetapi idealnya saya ingin menjaga langkah terakhir ini dalam SQL juga.

Saya telah melihat fungsi postgis apspWarshall baru tapi saya bingung bagaimana hal itu dapat didorong untuk memfokuskan energinya pada menghubungkan titik-titik dan bukan seluruh jaringan.

Ini adalah skrip pendek yang saya kumpulkan dalam upaya untuk membuat kerangka kerja untuk menyelesaikan ini, tetapi saya tidak bisa melihat di mana dimungkinkan untuk memfokuskan fungsi untuk memulai dengan subset dari tepi.

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

Dalam jalur tunggal masalah jalur terpendek fungsi meminta awal dan akhir tetapi tampaknya tidak di semua titik masalah. Sama di Grass, v.net.spanningtree dan v.net.steiner mengharapkan satu set poin dan garis sebagai jaringan gabungan untuk bekerja dengannya.

Adakah yang punya saran untuk melakukan ini di PostGIS?

Adrian
sumber
saya tidak yakin bahwa saya mengerti pertanyaan tetapi apakah docs.pgrouting.org/2.0/id/src/tsp/doc/index.html#pgr-tsp algoritme Traveling Sales Person membantu Anda?
simplexio
1
Terima kasih. Aku tidak takut. Travelling salesman mengasumsikan perjalanan dari a ke b ke c dan seterusnya secara linear. Yang saya inginkan adalah jaringan minimum yang menghubungkan setiap titik secara efisien sehingga titik mana pun dapat memulai perjalanan ke titik lain dalam pengetahuan bahwa tidak ada jalan berlebihan untuk tersesat. Di platform lain ini biasanya dilakukan dengan fungsi Pohon Spanning Minimum, Steiner Tree ( en.wikipedia.org/wiki/Steiner_tree_problem ) atau serupa. Jika Anda suka, TSP sangat bagus untuk perusahaan logistik tetapi saya ingin merencanakan jalan yang mereka gunakan.
Adrian

Jawaban:

2

Jawaban ini tidak lengkap atau diuji, tetapi coba sesuatu seperti ini:

menurut pertanyaan / 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;

Saya pikir ini sangat tidak efisien.

Youseeus
sumber
Sangat menghargai ini - terima kasih. Ini telah memberi saya beberapa sudut pandang baru untuk mengeksplorasi yang tidak saya pikirkan. Kode ini akan menemukan tetangga terdekat yang tidak terhubung dari daftar poin. Komplikasi tambahan yang saya miliki adalah bahwa titik-titik dalam kasus saya terhubung di sepanjang jaringan linestrings tetapi saya bertanya-tanya apakah saya dapat mengganti kueri ST_Distance dengan jarak jalan pgRouting, meskipun itu akan jauh lebih lambat daripada kueri titik yang tidak dilarutkan.
Adrian
2

@Adrian, saya benar-benar tidak terbiasa dengan hasil pgrouting, namun dokumentasinya sangat rinci. Jawaban saya didasarkan pada fungsi dua langkah, yang akan sangat tidak efisien dalam SQL tetapi [kemungkinan] menghasilkan hasilnya. Solusi [yang belum diuji] ini TIDAK akan mengoptimalkan yang merupakan titik awal terbaik, tetapi akan mengurangi seluruh jaringan rute menjadi hanya tepi yang menghubungkan semua halte, kemudian rute secara efisien ke semua halte.

Langkah 1 (sub-pemilihan subset jaringan jalan yang menghubungkan semua halte) Ini menggunakan fungsi rute multi-tujuan (jalur K Dijkstr) untuk mengembalikan kumpulan jalur yang (saat biaya <> -1) benar-benar menghubungkan semua berhenti.

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

Masalah yang saya miliki di sini adalah sintaks untuk merakit array dari stop table Anda, karena tidak benar-benar dijelaskan dalam pertanyaan. Namun, mari kita asumsikan bahwa sintaks SQL dapat merakit array itu dan bahwa stop id minimum harus menjadi titik awal untuk semua path K ke target yang berhenti.

Langkah 2 (pemilihan akhir dari lintasan minimum berdasarkan lintasan jaringan jalan subset di atas yang menghubungkan semua pemberhentian) Ini pada dasarnya adalah apa yang Anda mulai, tetapi saya mengusulkan agar Anda bergabung dengan jaringan jalan Anda ke hasil awal pada id1 (jalur) sehingga hanya subset jalan yang digunakan dalam routing Field-Warshal terakhir :

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

Jadi, dalam ringkasan ... kueri perutean k_dijkstra_path internal mengurangi jaringan jalan total menjadi hanya jalur yang menghubungkan semua perhentian Anda, maka perutean fField_Warshal luar hanya menggunakan id tepi itu untuk menyelesaikan permintaan optimasi jalur .... mungkin.

JasonInVegas
sumber
Terima kasih - ini sangat membantu dan petunjuk baru pertama saya. Saya melihatnya sekarang. Saya hanya mencoba mencari cara untuk menghasilkan id berhenti minimum dan array. Saya memiliki tabel id yang diperlukan tetapi 'SELECT min (id) FROM node_table' dan 'SELECT ARRAY [id] FROM node_table' menghasilkan kesalahan sintaksis ketika dimasukkan ke dalam kode Anda tetapi berfungsi sebagai kode yang berdiri sendiri (pemahaman saya kurang, saya yakin)
Adrian