Apakah ada algoritma perutean yang lebih baru (daripada Dijkstra, A *) di database GIS?

46

Ada karya-karya seperti Reach for A * dari para peneliti Microsoft dan Highway Hierarchies oleh Sanders dan Schtolz (jika saya mengeja namanya dengan benar) dari Karlsruhe Uni . Keduanya mengurangi urutan kalkulasi, dan mempercepat ribuan kali pada grafik besar (lihat hasilnya di dokumen yang ditautkan). Pekerjaan terakhir mengarah ke Open Source Routing Machine , yang sayangnya tidak cukup populer dan tidak diadaptasi (saya tidak bisa mengkompilasi walaupun berusaha keras).

Pada saat yang sama, dbs yang saya coba, Spatialite dan PgRouting, menurut dokumen mereka, hanya menawarkan algoritma Dijkstra dan A * . Saya bahkan belum pernah melihat pencarian dua arah yang disebutkan, yang menghemat waktu perhitungan dua kali dalam pengalaman saya.

Apakah ada algoritma yang lebih baik untuk database atau aplikasi lain?

culebrón
sumber
1
Sudahkah Anda memposting pertanyaan Anda ke daftar email pengguna atau pengembang pgRouting? Anda mungkin mendapat respons yang lebih baik langsung dari komunitas itu. Daftar pengguna: ( lists.osgeo.org/mailman/listinfo/pgrouting-users ) Daftar pengembang: ( lists.osgeo.org/mailman/listinfo/pgrouting-dev )
RyanDalton
+1 Pertanyaan bagus. Saya ingin tahu algoritma apa yang digunakan Google untuk Dapatkan Arah . Pertanyaan terkait di sini .
Kirk Kuykendall
1
Karena Google mendukung tim Karlsruhe ( algo2.iti.uni-karlsruhe.de/english/index.php ) Saya kira mereka menggunakan perangkat lunak mereka, yang pada dasarnya adalah Open Source Routing Machine.
culebrón

Jawaban:

23

Yang benar adalah bahwa kebanyakan orang menggunakan variasi khusus dari algoritma A * . Anda akan melihat ini di sebagian besar "orang besar" (saya tidak bisa mengatakan siapa mereka di forum publik, tetapi saya dapat memberitahu Anda bahwa Anda mungkin menggunakan salah satu dari mereka - dijamin), di mana modifikasi heuristik adalah sangat tergantung pada dataset yang mereka gunakan.

Anda sudah menyebutkan pgrouting , yang saya anggap sebagai opsi "tradisional". Ini baik untuk melakukan algoritma perutean sederhana dan untuk sebagian besar masalah. Juga mudah digunakan dan menggunakan database tradisional di backend-nya.

Namun demikian, itu benar-benar tergantung pada skala dan jenis masalah yang Anda coba selesaikan dan perutean adalah masalah grafik .

Sekali lagi, "orang besar" biasanya memiliki banyak data yang dikaitkan dengan grafik mereka (misalnya, data lalu lintas, rute bus, jalur pejalan kaki) yang memengaruhi algoritma perutean. Ini dikenal sebagai perencana perjalanan multi-modal (di mana Anda juga memiliki pilihan untuk merencanakan "mode" - tidak ada jalur sepeda - hanya angkutan umum - hal semacam itu). Anda bisa memikirkan bagaimana perencanaan perjalanan juga menjadi isu sensitif waktu (yaitu jika Anda berjalan kembali beberapa tepi kembali, Anda akan dapat menangkap kereta bawah tanah yang akan membawa Anda ke tujuan Anda ke depan jauh lebih cepat daripada jika Anda hanya mencoba untuk menavigasi tepi depan menggunakan biaya terendah).

"Orang besar" tidak menyimpan data mereka dalam basis data tradisional, mereka menggunakan grafik yang sudah dihitung sebelumnya (selamat datang di cluster himpunan / mapreduce!). Seperti yang dapat Anda bayangkan, grafik ini menjadi sangat besar, sehingga mengetahui cara menghubungkan tepi grafik yang berdekatan dapat menjadi tantangan.

Bagaimanapun, saya akan merekomendasikan Anda melihat beberapa proyek grafik routing multi-modal:

Graphserver muncul di pikiran. Tidak banyak dokumentasi tetapi banyak kemahiran pengkodean murni (AFAIK, saya percaya MapQuest menggunakan variasi proyek ini untuk beberapa produk routing mereka).

Opsi lain adalah OpenTripPlanner yang memiliki banyak orang pintar di belakangnya (termasuk orang-orang dari graphserver).

Ragi Yaser Burhum
sumber
15

Tidak yakin apakah itu lebih baru tetapi pgRouting memiliki algoritme Shooting-Star :

Algoritma Shooting-Star adalah yang terbaru dari algoritma jalur terpendek pgRouting. Keistimewaannya adalah ia merutekan dari tautan ke tautan, bukan dari titik ke titik seperti yang dilakukan algoritma Dijkstra dan A-Star. Ini memungkinkan untuk mendefinisikan hubungan antara tautan, dan itu memecahkan beberapa masalah algoritma berbasis simpul lain seperti “tautan paralel”, yang memiliki sumber dan target yang sama tetapi biaya yang berbeda.

Ekstensi Analis Jaringan ESRI menggunakan pendekatan hierarkis yang Anda sebutkan untuk membatasi waktu penyelesaian:

Menemukan jalur terpendek yang tepat pada dataset jaringan nasional memakan waktu karena banyaknya sisi yang perlu dicari. Untuk meningkatkan kinerja, dataset jaringan dapat memodelkan hierarki alami dalam sistem transportasi di mana berkendara di jalan raya antar negara lebih disukai daripada mengemudi di jalan lokal. Setelah jaringan hierarkis telah dibuat, modifikasi Dijkstra dua arah digunakan untuk menghitung rute antara asal dan tujuan.

Ada buku putih yang sangat rinci dengan contoh-contoh tentang pendekatan ini di situs ESRI - namun mengharuskan Anda untuk masuk untuk mengunduh (Rute Hierarkis Dalam Buku Putih Analis Jaringan ArcGIS).

geografi
sumber
11

Hierarki Kontraksi adalah algoritma yang sangat cepat:

Algoritma ini ramah RAM saat menjalankan kueri (untuk menahan grafik yang dikontrak, diperlukan lebih banyak RAM dan juga preprocessing masif)

Ada beberapa algoritma lain - termasuk yang memecahkan rute angkutan umum:

Microsoft juga melakukan beberapa penelitian:

(Yah, Daniel Delling juga dari Karlsruhe)

Anda bisa mendapatkan pengantar dan ikhtisar bagus dari algoritma yang tersedia:

Peringatan: kuliah bahasa Jerman (!). tetapi setidaknya tajuk dapat membantu Anda mendapatkan informasi lebih lanjut (ALT, Arc-Flags, CHASE, ...) atau literatur yang ditambahkan!

memperbarui

GraphHopper sekarang mengimplementasikan hierarki kontraksi dan juga algoritma lainnya, Anda juga dapat mencoba demo .

Karussell
sumber