CCH vs Dijkstra vs A*: Routing 3.200 Kali Lebih Cepat di ArcadeDB

Pada jaringan jalan DIMACS Florida dengan 1,07 juta persimpangan dan 2,7 juta segmen, Customizable Contraction Hierarchies (CCH) menjawab 12 kueri rute dalam 0,010 sampai 0,041 milidetik, sementara Dijkstra butuh 7,8 sampai 104 milidetik dan A* 3,1 sampai 132 milidetik. Selisihnya 300 sampai 3.200 kali lebih cepat, dan angka itu berasal dari benchmark yang dipublikasikan ArcadeDB bersama ArcadeDB 26.10.2.

TL;DR

• Dijkstra dan A* menghitung ulang graf setiap kueri, jadi waktu jawabnya tumbuh mengikuti panjang rute.
• CCH menyimpan struktur yang sudah dihitung lebih dulu, sehingga biaya kuerinya bergantung tinggi hierarki, bukan jarak.
• Pada jaringan Florida, memori per kueri CCH hanya 6 sampai 43 KB, sedangkan Dijkstra 11 sampai 44 MB.
• CCH tetap salah untuk graf tanpa pemisah kecil seperti jaringan sosial; ArcadeDB menandainya UNSUITABLE dan kembali ke Dijkstra.

Kenapa Dijkstra dan A* makin lambat pada rute yang panjang?

Karena keduanya menjelajah graf saat kueri dijalankan. Semakin jauh tujuan, semakin banyak simpul yang harus diperiksa, sehingga waktu jawab naik seiring panjang rute.

Di benchmark ArcadeDB pada jaringan Florida, 12 kueri berjarak bertambah dari Tallahassee menghasilkan waktu 7,8 milidetik sampai 104 milidetik untuk Dijkstra, dan 3,1 milidetik sampai 132 milidetik untuk A*. Menariknya, A* yang biasanya dianggap lebih pintar justru bisa lebih lambat pada kasus terburuk di sini, karena hasilnya bergantung kualitas heuristik jarak lurus terhadap medan jalan yang sebenarnya.

Rute Tallahassee ke Coral Gables memperlihatkan pola yang sama dengan angka tunggal: CCH 0,039 milidetik, Dijkstra 99 milidetik, dan A* 121 milidetik. Perhatikan bahwa waktu CCH nyaris tidak bergerak meski jaraknya jauh, sementara dua algoritma klasik tumbuh seiring rute memanjang.

Ada satu perbedaan sumber daya yang sering diabaikan. Memori per kueri pada Dijkstra 11 sampai 44 MB dan A* 9 sampai 52 MB, sedangkan CCH hanya 6 sampai 43 KB. Pada layanan yang melayani banyak kueri bersamaan, selisih memori ini menentukan berapa banyak permintaan bisa diproses paralel sebelum mesin kehabisan RAM.

Apa sebenarnya yang dilakukan Customizable Contraction Hierarchies?

CCH memindahkan pekerjaan berat ke tahap persiapan. Alih-alih menghitung ulang graf tiap kueri, ia memberi peringkat simpul sehingga himpunan simpul kecil yang memecah jaringan berada di atas, menambah sisi pintasan, lalu menjawab kueri dengan menaiki hierarki dari dua titik ujung menuju puncak.

Konsekuensinya, biaya kueri bergantung pada tinggi hierarki, bukan pada jarak antara dua simpul. Itu sebabnya rute sejauh apa pun di jaringan Florida tetap dijawab dalam hitungan mikrodetik. Struktur ini disebut customizable karena peringkat dan pintasan hanya bergantung pada topologi jaringan: ketika bobot sisi berubah, hanya biaya di atas sisi yang berubah itu yang dihitung ulang.

Yang membuat pendekatan ini masuk akal untuk sistem produksi adalah sifatnya yang topologi-agnostik terhadap perubahan bobot. Menambah bobot kemacetan pada satu ruas jalan tidak memaksa seluruh hierarki dibangun ulang, hanya bagian yang terdampak.

Aspek	CCH	Dijkstra	A*
Waktu jawab di jaringan Florida	0,010 sampai 0,041 ms	7,8 sampai 104 ms	3,1 sampai 132 ms
Rute Tallahassee ke Coral Gables	0,039 ms	99 ms	121 ms
Memori per kueri	6 sampai 43 KB	11 sampai 44 MB	9 sampai 52 MB
Tumbuh terhadap jarak rute	Tidak	Ya	Ya
Butuh tahap persiapan	Ya	Tidak	Tidak

Bagaimana rute bisa mengikuti perubahan lalu lintas secara langsung?

Bobot sisi adalah properti biasa, jadi satu UPDATE sudah cukup untuk mengubahnya, dan hierarki hanya menghitung ulang busur di atas sisi tersebut. Pada jaringan Florida, satu perubahan bobot butuh 0,8 milidetik dari commit sampai hierarki bisa menjawabnya, 100 perubahan sekitar 41 milidetik, dan penutupan satu jalan sekitar 1 milidetik.

Yang penting, kueri tidak pernah menunggu. Sampai hierarki selesai menyesuaikan diri, kueri tetap dijawab secara eksak oleh bidirectional Dijkstra. Jadi tidak ada jendela waktu di mana pengguna menerima rute yang salah karena bobot belum diperbarui, hanya jendela waktu di mana jawabannya belum secepat biasanya.

Untuk konteks penerapan, satu jaringan bisa punya beberapa biaya sekaligus. Sebuah Graph Analytical View menyimpan satu hierarki per properti bobot, misalnya CCH untuk kilometer dan CCH untuk menit, dan semuanya dijaga tetap mutakhir bersama-sama. Setiap kueri menyebut bobot mana yang diminimalkan.

Kapan sebaiknya tetap memakai Dijkstra atau A*?

Untuk kueri yang jarang, untuk jaringan yang bentuknya terus berubah, dan untuk graf tanpa pemisah kecil seperti jaringan sosial atau graf dengan supernode. Pada kasus seperti itu hierarki bisa jauh lebih besar daripada graf aslinya, sehingga keuntungan waktunya tidak sebanding biaya memorinya.

ArcadeDB menangani hal ini secara otomatis: graf semacam itu dideteksi, hierarkinya ditandai UNSUITABLE, dan mesin tetap menjawab memakai Dijkstra. Jika bobot bisa bernilai negatif, algoritma yang benar adalah Bellman-Ford, bukan Dijkstra.

Satu catatan batas yang jujur: untuk navigasi belokan demi belokan di peta jalan publik, mesin khusus yang dibangun di atas data OpenStreetMap masih menjadi alat yang tepat. Keuntungan ArcadeDB adalah ketika rutenya berada di jaringan milik sendiri, misalnya jaringan logistik, jaringan utilitas, atau graf internal perusahaan, karena tidak perlu ada ekspor data, job prapemrosesan terpisah, maupun sinkronisasi antara basis data dan layanan routing.

Bagaimana cara memakainya di ArcadeDB?

Panggil fungsi graf dari SQL atau Cypher. Dari SQL tersedia dijkstra(), astar(), cchShortestPath(), bellmanFord(), dan shortestPath(). Dari Cypher tersedia algo.dijkstra, algo.astar, algo.cch.shortestPath, algo.kShortestPaths, serta pola shortestPath(). Keduanya bisa dipanggil dari Java, HTTP API, dan driver.

CCH menjadi bagian dari mesin mulai ArcadeDB 26.10.2, ditulis dalam Java tanpa dependensi native, dan lisensinya Apache 2.0 sehingga bebas dipakai di produksi. Rincian lengkap benchmark, termasuk ukuran jaringan uji dan metodenya, ada di halaman route planning ArcadeDB, sedangkan kode dan catatan rilisnya ada di repositori ArcadeDB di GitHub.

Urutan adopsi yang masuk akal untuk tim backend: mulai dari Dijkstra untuk memastikan model graf dan bobotnya benar, bangun Graph Analytical View untuk properti bobot yang paling sering dipakai, lalu aktifkan CCH ketika pola kuerinya sudah jelas. Tanpa langkah pertama, hierarki yang dibangun di atas graf yang salah hanya akan menjawab dengan cepat pada jawaban yang keliru.

Bagaimana hierarki CCH disiapkan dan apa yang perlu diukur dari biayanya?

Penyiapan berjalan tiga tahap: memberi peringkat simpul, menambah sisi pintasan, lalu menghitung biaya di atas hierarki. Peringkat dan pintasan hanya bergantung pada topologi, sedangkan biaya bergantung pada bobot, dan pemisahan itulah yang membuat hierarki bisa dipakai ulang saat bobot berubah.

Dari sisi biaya ada dua hal yang perlu diukur: waktu penyiapan awal dan tambahan memori untuk menyimpan hierarki. Keduanya tidak muncul di angka waktu jawab yang mengesankan, tapi keduanya nyata di anggaran operasional. Pada jaringan besar, hierarki bisa beberapa kali lipat lebih besar daripada graf aslinya, jadi kapasitas RAM harus dihitung dengan asumsi itu, bukan dengan asumsi graf polos.

Untuk jaringan yang topologinya berubah terus, misalnya graf yang sisi dan simpulnya bertambah tiap jam, biaya penyiapan ulang bisa menggerus keuntungan kuerinya. Sebaliknya, untuk jaringan yang topologinya stabil dan hanya bobotnya yang bergerak, pola inilah yang paling menguntungkan: penyiapan berat terjadi sekali, lalu penyesuaian bobot berjalan dalam hitungan milidetik.

Apa yang perlu diukur sebelum memilih CCH?

Ukur distribusi panjang rute Anda lebih dulu, karena di situlah keuntungan CCH paling terasa. Jika hampir semua kueri Anda pendek, selisih waktu pada rute jauh tidak akan banyak mengubah latensi rata-rata, sementara biaya memori hierarkinya tetap harus dibayar.

Berikutnya, ukur tingkat perubahan graf. Graf yang bobotnya berubah tiap menit dan graf yang topologinya berubah tiap menit adalah dua masalah berbeda: yang pertama cocok untuk CCH, yang kedua belum tentu. Ketiga, ukur kebutuhan konkurensi. Jika satu instans harus melayani ratusan kueri bersamaan, keunggulan memori per kueri CCH yang hanya puluhan kilobyte, dibanding puluhan megabyte pada Dijkstra, bisa lebih menentukan daripada selisih waktunya.

Terakhir, uji pada data Anda sendiri, bukan pada jaringan uji mana pun. Angka benchmark pada jaringan jalan tidak otomatis berlaku untuk graf logistik atau graf internal perusahaan, karena bentuk grafnya berbeda, dan bentuk graf itulah yang menentukan hasilnya.

Ada satu hal yang tidak muncul di benchmark mana pun tapi menentukan umur pemakaian: kemudahan observasi. Hierarki yang dibangun otomatis perlu cara untuk memeriksa kapan penyiapan terakhir berjalan, apakah ada hierarki yang ditandai UNSUITABLE, dan berapa lama kueri benar-benar dilayani oleh Dijkstra cadangan. Tanpa tiga sinyal itu, penurunan performa hanya akan terlihat sebagai keluhan pengguna, bukan sebagai metrik yang bisa ditelusuri ke penyebabnya.

Yang terakhir, pertimbangkan pola kegagalan saat hierarki belum siap. Sistem yang menjawab lewat Dijkstra cadangan akan terasa lambat tetapi tetap benar, dan itu perilaku yang jauh lebih baik daripada sistem yang menjawab cepat dengan rute salah. Pastikan cadangan itu memang aktif, karena mempercayai hierarki yang belum selesai lebih berbahaya daripada tidak memakai hierarki sama sekali.

FAQ

Apakah CCH menggantikan mesin routing peta jalan publik?

Tidak. Untuk navigasi belokan demi belokan di peta publik, mesin berbasis OpenStreetMap tetap lebih tepat karena menangani detail seperti larangan belok dan struktur jalan. CCH unggul untuk routing di jaringan milik sendiri yang tidak perlu keluar dari basis data.

Berapa lama pembaruan bobot terasa di hasil kueri?

Pada benchmark jaringan Florida, satu perubahan bobot butuh 0,8 milidetik sampai hierarki bisa menjawab, dan penutupan satu jalan sekitar 1 milidetik. Selama hierarki belum selesai, kueri dijawab oleh bidirectional Dijkstra sehingga hasilnya tetap eksak.

Apakah hierarki harus dibangun ulang setiap kali bobot berubah?

Tidak. Hanya busur yang berada di atas sisi yang berubah yang dihitung ulang, karena peringkat dan pintasan hierarki bergantung pada topologi, bukan pada nilai bobotnya. Itulah alasan struktur ini disebut customizable.

Bisakah satu jaringan memakai beberapa jenis biaya sekaligus?

Bisa. Sebuah Graph Analytical View dapat menyimpan satu hierarki per properti bobot, misalnya kilometer dan menit, dan semuanya dijaga mutakhir bersama. Setiap kueri menyebut properti bobot mana yang ingin diminimalkan.

Rekomendasi Tools & Layanan

Mau langsung nyobain AI yang dibahas di artikel ini tanpa setup ribet? AI token plan Alibaba Cloud ngasih akses ke Qwen, DeepSeek, dan model lain lewat satu API — dan platform Qwen buat build agent sendiri. Free tier-nya cukup buat eksperimen pertama.