Saya sedang membangun sistem perencanaan rute, tetapi saya masih harus memutuskan mesin routing apa yang akan saya gunakan. Sejauh ini saya telah menemukan pgrouting dan neo4j.
Saya memiliki jaringan rute saya di database postgresql / postgis (diimpor dari shapefile). Saya telah membuat pertanyaan untuk mengekstrak node (titik akhir dari cara di mana Anda harus membuat keputusan ke arah mana harus pergi atau jalan buntu) dan untuk mengekstrak tepi (sering dibuat dengan beberapa cara berturut-turut). Semua tepi saya adalah dua arah.
Tujuan utama saya adalah untuk menghitung rute di jaringan ini menggunakan algoritma bintang-A di mana distance = biaya.
Perasaan saya memberi tahu saya bahwa basis data grafik seperti neo4j adalah cara untuk pergi (karena tampaknya dibuat hanya untuk tujuan ini), tetapi mereka tampaknya tidak mendukung bintang-A secara default dan juga tidak ada rasa geometri yang nyata . Tampaknya lebih cocok untuk jejaring sosial daripada peta.
- Akankah pemogokan memenuhi kebutuhan saya?
- Apakah cukup cepat untuk permintaan langsung (+ -2000 node, + -4000 edge)? Biasanya ini akan menjadi beberapa ms untuk bintang-A, tetapi saya tidak yakin tentang implementasi ini dalam sql.
- Apakah pgrouting A-star memberi saya daftar node dan edge?
- Dalam sebagian besar contoh saya melihat tentang pgrouting saya perhatikan biasanya ada daftar perintah setelah perhitungan rute (seperti "Di X belok kiri, dll"). Apakah pgrouting menghasilkan ini atau ini dari sistem lain?
Semoga seseorang dapat memberi saya beberapa informasi tentang sistem apa yang harus saya pilih. Neo4j, pgrouting, atau sistem lain.
Jawaban:
Saat ini saya sedang mengeksplorasi masalah yang sama seperti Anda, untuk tujuan makalah penelitian. Sebelum saya mulai menguji dua database ini, saya memiliki anggapan yang sama seperti Anda. Database grafik Neo4j itu akan menjadi solusi sempurna untuk masalah seperti ini. Dan sebagian memang demikian, tetapi dengan banyak masalah.
Masalah pertama adalah bahwa A-Star hanya diimplementasikan jika Anda menggunakan database tertanam, bukan melalui REST API (server). Jika Anda ingin menggunakan Neo4j dengan REST API, maka hanya algoritma Dijkstra yang didukung. Masalah kedua adalah persyaratan memori perangkat keras untuk Neo4j. Untuk perutean (Dijkstra) pada jaringan "lebih besar" Anda membutuhkan banyak RAM. Untuk jaringan besar saya maksudkan seperti ukuran basis data jalan OSM Jerman . Saya telah menjalankan tes pada server RAM 6GB (itu yang saya miliki saat ini) dan hanya jaringan yang lebih kecil yang dapat dialihkan tanpa kesalahan pengecualian OutOfMemory. Jaringan "kecil" dalam kasus pengujian saya misalnya, basis data jalan OSM untuk Austria atau Kroasia. Pertanyaan serentak saya masih belum diuji dengan Neo4j.
Semua masalah ini tidak ada di pgRouting. Memori bukan masalah seperti itu tetapi permintaan bersamaan meningkatkan jumlah memori yang dibutuhkan. Misalnya, jika Anda memiliki dua permintaan bersamaan, dibutuhkan jumlah memori ganda. Ini bukan masalah bahkan untuk dataset OSM Jerman, pgRouting dialihkan tanpa masalah semua permintaan bersamaan.
Kinerja: Dalam kebanyakan kasus, Neo4j mengungguli pgRouting. Tetapi hanya jika ada memori yang cukup untuk dataset yang diberikan dan jika semua node dan hubungan ada dalam memori (hot start). Peningkatan / penurunan kinerja tergantung pada banyak faktor tetapi sebagian besar pada ukuran jaringan dan jarak (hop) antara sumber dan target node.
Ukuran jaringan Anda cukup kecil, jadi Anda seharusnya tidak memiliki masalah dengan memori. Mungkin Neo4j bukan pilihan yang buruk tetapi Anda harus beradaptasi dengan model data yang "sedikit" berbeda dari pada database hubungan standar.
Untuk menjawab pertanyaan Anda:
Saya tidak tahu apakah itu akan membantu Anda secara langsung, tetapi salah satu server perutean tercepat yang saya temukan adalah osm2po . Ia bekerja dengan dataset OSM dan cukup cepat. Hanya dijkstra yang saat ini diterapkan tetapi pengembang juga mengumumkan AStar. Saya harap beberapa dari ini akan membantu Anda. :)
sumber
Anda juga dapat melihat paket RW Net 4 kami (www.routeware.dk). Itu dapat melakukan perhitungan jalur terpendek seperti menggunakan A * langsung dari file SHP. Paket Basic seharga € 500 tampaknya cukup untuk kebutuhan Anda.
sumber