Mengapa pgRouting tidak mengembalikan jalur terbaik?

9

Biarkan bagian grafik berikutnya:

masukkan deskripsi gambar di sini Ketika saya menggunakan fungsi shortest_path antara titik A dan B, saya mendapat jalur biru. Mengapa ini terjadi?

postgis postgresql pgrouting José Alejandro
sumber
Dalam penjelasannya, saya melakukan kesalahan, merah biru bukan merah, maaf!
José Alejandro

Jawaban:

7

Begitulah perilaku shortest_path (algoritma Dijkstra) di pgRouting. Jika ada dua sisi dengan sumber dan target yang sama, satu acak (tepatnya: yang pertama, yang keluar dari database) digunakan. Saya tidak tahu perbaikan untuk itu, tetapi ada beberapa solusi.

Jika memungkinkan, Anda harus membagi salah satu ujung menjadi dua. Saya belum mengujinya, tetapi harus memperbaiki perilaku itu.

Solusi lain untuk kasus, ketika Anda tidak dapat mengubah dataset Anda. Tambahkan bidang 'short_alternative' ke tabel Anda. Contoh permintaan, modifikasi sesuai kebutuhan Anda. Saya harap ini menjelaskan ide:

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)

Sekarang, tepi '0,098' akan berisi id tepi '0,011'. Semua tepi lainnya akan memiliki null di bidang short_alternative. Setelah Anda membuat kueri shortest_path, periksa dataset yang dikembalikan - jika ada baris yang mengatur bidang short_alternative, ubahlah.

pengguna1702401
sumber
2

Masalahnya sudah dijelaskan pada jawaban sebelumnya. Ini masalah algoritma jalur terpendek "berbasis vertex", yang hanya peduli pada sumber dan target.

Ada tiket di pelacak masalah dan solusi yang memungkinkan untuk mengubah implementasi algoritma: https://github.com/pgRouting/pgrouting/issues/34 (Akan menyenangkan jika seseorang dapat mencoba ini dan mengirim permintaan tarik; - )

Kemungkinan lain adalah dengan memisahkan "jalur jalan paralel" seperti yang disebutkan sebelumnya. Atau Anda bisa menggunakan algoritma Shooting Star, yang merutekan dari ujung ke ujung sehingga "tahu" tentang kedua ruas jalan.

Atau Anda dapat mencoba memesan jaringan jalan berdasarkan biaya dan kemudian hanya memilih kombinasi sumber dan target yang berbeda:

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

Ini mengasumsikan bahwa Anda mencari rute yang paling murah. Kalau tidak, Anda perlu ORDER BY ... DESC.

Anda perlu mencoba jika ini mempengaruhi kinerja.

dkastl
sumber
Kemarin saya membangun fungsi trsp dan sepertinya tidak memiliki masalah ini. Bagaimanapun, terima kasih atas penjelasannya !!!.
José Alejandro